การจัดตารางเวลาโปรเซส — แนวคิดระบบปฏิบัติการ

การจัดตารางเวลาโปรเซสคือการที่ระบบปฏิบัติการตัดสินใจว่าโปรเซสใดในคิวพร้อมจะได้ใช้ CPU เป็นลำดับถัดไป พูดง่าย ๆ มันคือกฎสำหรับเลือกว่าตอนนี้ใครได้รัน และใครต้องรอ กฎนี้ส่งผลต่อ waiting time, response time, ความยุติธรรม และ throughput โดยรวม

การจัดตารางเวลาโปรเซสสำคัญเพราะโปรเซสชุดเดียวกันอาจเสร็จสิ้นในลำดับที่ต่างกันมากภายใต้ FCFS, SJF หรือ round robin ถ้าเข้าใจแนวคิดนี้เพียงข้อเดียว ตัวอย่างส่วนใหญ่ในตำราจะอ่านง่ายขึ้นมาก

การจัดตารางเวลาโปรเซสใน OS หมายถึงอะไร

ในโมเดล OS ทั่วไป โปรเซสจะย้ายไปมาระหว่างสถานะต่าง ๆ เช่น ready, running และ waiting ตัว scheduler จะเลือกจากโปรเซสที่อยู่ในสถานะ ready

นี่จึงเป็นเหตุผลว่าทำไม process scheduling มักถูกเรียกว่า CPU scheduling มันไม่ได้สร้างงานใหม่ แต่เป็นการตัดสินใจลำดับที่งานซึ่งกำลังรอจะได้รับบริการจาก CPU

ในระบบสมัยใหม่ kernel มักจัดตารางเวลาให้ thread โดยตรง แต่คำคลาสสิกอย่าง "process scheduling" ก็ยังเป็นคำมาตรฐานที่ใช้ในการสอน

Scheduler พยายามปรับให้เหมาะกับอะไร

โดยทั่วไป scheduler จะพยายามสร้างสมดุลระหว่างหลายเป้าหมาย:

• waiting time ต่ำ
• ตอบสนองเร็วสำหรับงานแบบโต้ตอบ
• throughput ที่ดี
• ความยุติธรรม
• พฤติกรรมที่คาดเดาได้

เป้าหมายเหล่านี้อาจขัดกันได้ นโยบายที่ลด waiting time เฉลี่ยในตัวอย่างแบบง่ายตัวหนึ่ง อาจยังรู้สึกไม่ยุติธรรมในทางปฏิบัติ และนโยบายแบ่งเวลาอย่างยุติธรรมก็อาจทำให้งานสั้นเสร็จช้าลง

การจัดตารางเวลาแบบแย่ง CPU ได้ กับแบบแย่งไม่ได้

scheduler แบบ non-preemptive จะปล่อยให้โปรเซสที่กำลังรันใช้ CPU ต่อไปจนกว่าจะจบ CPU burst หรือถูกบล็อก ตัวอย่างมาตรฐานคือ first-come, first-served

scheduler แบบ preemptive สามารถขัดจังหวะโปรเซสที่กำลังรันและยก CPU ให้โปรเซสอื่นได้ round robin และ scheduler แบบ priority หลายแบบทำเช่นนี้

ความแตกต่างนี้สำคัญ เพราะ response time มักดีขึ้นเมื่อระบบสามารถแย่ง CPU จากงานที่รันนานได้

อัลกอริทึมการจัดตารางเวลาโปรเซสที่พบบ่อย

First-Come, First-Served

First-come, first-served หรือ FCFS จะรันโปรเซสตามลำดับที่มาถึง เข้าใจง่ายและนำไปใช้ได้ไม่ซับซ้อน แต่ถ้ามีงานยาวอยู่หน้าคิว งานสั้นทุกงานที่อยู่ข้างหลังก็ต้องรอนาน

Shortest Job First

Shortest job first หรือ SJF จะเลือกโปรเซสที่มี CPU burst สั้นที่สุด ในสถานการณ์แบบง่ายที่รู้ความยาว burst ได้แม่นยำ มันสามารถลด waiting time เฉลี่ยได้ แต่ในระบบจริง ความยาว burst นี้มักต้องอาศัยการประมาณ

Round Robin

Round robin จะแบ่งเวลาให้แต่ละโปรเซสที่พร้อมทำงานเป็นช่วงสั้น ๆ ที่เรียกว่า quantum ถ้าโปรเซสยังไม่เสร็จภายในช่วงนั้น มันจะกลับไปต่อท้ายคิว ready วิธีนี้มักช่วยเพิ่มความยุติธรรมและการตอบสนองสำหรับงานแบบโต้ตอบ

Priority Scheduling

Priority scheduling จะรันโปรเซสที่มี priority สูงสุดก่อน มันมีประโยชน์เมื่อบางงานสำคัญกว่างานอื่น แต่ถ้างาน priority ต่ำต้องรอนานเกินไป ก็มีความเสี่ยงที่จะเกิด starvation

ตัวอย่างคำนวณหนึ่งข้อพร้อม waiting time

สมมติว่ามีสามโปรเซสมาถึงพร้อมกันที่เวลา $0$ และแต่ละโปรเซสต้องใช้เพียงเวลา CPU:

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

กำหนดให้:

• มี CPU หนึ่งตัว
• ไม่มีการบล็อกจาก I/O
• ไม่นับต้นทุนของ context switch

ภายใต้เงื่อนไขเหล่านี้ waiting time หมายถึงเวลาที่โปรเซสใช้ไปกับการรออยู่ในคิว ready ก่อนจะได้รัน ส่วน turnaround time คือ

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

ถ้าใช้ FCFS ลำดับจะเป็น $P_1 \rightarrow P_2 \rightarrow P_3$

ไทม์ไลน์:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

waiting time:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

waiting time เฉลี่ย:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

ถ้าใช้ SJF แบบ non-preemptive ลำดับจะเป็น $P_3 \rightarrow P_2 \rightarrow P_1$

ไทม์ไลน์:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

waiting time:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

waiting time เฉลี่ย:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

ตัวอย่างนี้แสดงให้เห็นสัญชาตญาณหลัก ภาระงานไม่ได้เปลี่ยน แต่กฎที่ใช้เปลี่ยนผลลัพธ์ ในกรณีนี้ SJF ให้ waiting time เฉลี่ยต่ำกว่า เพราะงานสั้นไม่ต้องติดอยู่หลังงานยาว

แต่นั่นไม่ได้แปลว่า SJF เป็นตัวเลือกที่ดีที่สุดเสมอในโลกจริง มันหมายความว่า ภายใต้สมมติฐานของตัวอย่างนี้ ลำดับการจัดตารางเวลามีผลอย่างมาก

แนวคิดสำคัญที่ควรจำ

ให้มอง process scheduling เป็นกฎการเข้าคิวของ CPU คิว ready อาจมีงานชุดเดิมอยู่ แต่กฎในการให้บริการคิวนั้นเปลี่ยนสิ่งที่ผู้ใช้สัมผัสได้

ถ้าคุณสนใจการตอบสนองครั้งแรกที่รวดเร็วที่สุด คุณอาจชอบการแบ่งเวลาแบบถี่ ๆ ถ้าคุณสนใจให้งานสั้นจำนวนมากเสร็จเร็ว คุณอาจชอบนโยบายที่ให้ความสำคัญกับ burst สั้น ถ้าคุณสนใจเรื่องเวลาที่เคร่งครัด คุณอาจต้องใช้ scheduler อีกแบบหนึ่ง

ข้อผิดพลาดที่พบบ่อยในโจทย์การจัดตารางเวลา

คิดว่านโยบายหนึ่งดีที่สุดเสมอ

ไม่มีผู้ชนะเพียงหนึ่งเดียวสำหรับทุกลักษณะงาน นโยบายหนึ่งอาจดูยอดเยี่ยมในแง่ waiting time เฉลี่ย แต่กลับแย่ในเรื่องความยุติธรรมหรือ deadline

สับสนระหว่าง waiting time, response time และ turnaround time

ตัวชี้วัดเหล่านี้เกี่ยวข้องกัน แต่ไม่เหมือนกัน โดยเฉพาะ response time มักหมายถึงเวลาจนกว่าจะได้รับบริการจาก CPU ครั้งแรกหรือเกิดการตอบสนองที่ผู้ใช้เห็นได้ ขณะที่ turnaround time วัดทั้งงานตั้งแต่มาถึงจนเสร็จสิ้น

มองข้ามเงื่อนไขที่อยู่เบื้องหลังสูตร

ตัวชี้วัดจะมีความหมายก็ต่อเมื่ออยู่ภายใต้สมมติฐานที่ระบุไว้ ถ้าโจทย์มีการบล็อกจาก I/O เวลามาถึงต่างกัน หรือมี overhead จาก context switch ไทม์ไลน์และผลลัพธ์ก็จะเปลี่ยนไป

ลืมดูว่านโยบายเป็นแบบ preemptive หรือไม่

SJF กับ shortest remaining time first ไม่ใช่กฎเดียวกัน และ priority scheduling ก็มีพฤติกรรมต่างกันด้วย ขึ้นอยู่กับว่างานที่มี priority สูงกว่าสามารถแย่ง CPU จากงานปัจจุบันได้หรือไม่

การจัดตารางเวลาโปรเซสถูกใช้ที่ไหน

การจัดตารางเวลาโปรเซสสำคัญทุกที่ที่ระบบปฏิบัติการต้องแบ่งเวลา CPU ร่วมกัน:

• ระบบเดสก์ท็อปและมือถือที่ต้องการให้แอปตอบสนองไว
• เซิร์ฟเวอร์ที่ต้องจัดการคำขอจำนวนมาก
• ระบบแบตช์ที่สนใจ throughput
• ระบบเรียลไทม์ที่สนใจการรับประกันด้านเวลา

scheduler จริงมักซับซ้อนกว่าฉบับในตำรา แต่ tradeoff แบบเดียวกันก็ยังปรากฏอยู่เสมอ

ลองทำเวอร์ชันของคุณเอง

ลองเปลี่ยนตัวอย่างให้ $P_2$ มาถึงช้ากว่าเดิม หรือแทน FCFS ด้วย round robin ที่ใช้ quantum $2\ \mathrm{ms}$ แล้วดูว่ารูปแบบการรอเปลี่ยนไปอย่างไร ถ้าคุณอยากทำต่ออีกขั้นหลังจากลองคำนวณด้วยมือแล้ว ให้ลองเวอร์ชันของคุณเองใน GPAI Solver และเปรียบเทียบไทม์ไลน์ที่คุณคาดไว้กับผลที่ระบบคำนวณได้