OS · บทที่ 6 Scheduling

หัวข้อ 15 · 20 นาที

Scheduling: FIFO, SJF และ Round Robin

นึกภาพก่อน

แถวจ่ายเงินในซูเปอร์มาร์เก็ต คนหน้าสุดมีของเต็มสองรถเข็น ข้างหลังมีสี่คนถือของคนละชิ้น

  • ให้บริการตามลำดับที่มา: ยุติธรรมในแง่ลำดับ แต่สี่คนหลังรอนานมากเพื่อของชิ้นเดียว
  • ให้คนของน้อยไปก่อน: เวลารอเฉลี่ยลดลงมาก แต่คนของเยอะอาจไม่ได้จ่ายเลยถ้ามีคนของน้อยมาเรื่อย ๆ
  • คิดเงินให้คนละชิ้นแล้ววนไปคนถัดไป: ไม่มีใครถูกทิ้ง แต่เสียเวลาสลับคน

สามแบบนี้คือ FIFO, SJF และ Round Robin scheduling policy คือการตัดสินว่าจะทำอะไรต่อไปเมื่อมีหลาย thread พร้อมทำงาน (หรือหลาย packet รอส่ง หรือหลาย web request รอตอบ)

นิยาม

คำความหมาย
Task / Jobคำขอของผู้ใช้ เช่น คลิกเมาส์, web request, คำสั่ง shell
Latency / Response timetask ใช้เวลานานเท่าใดจึงเสร็จ
Throughputทำ task เสร็จได้กี่ชิ้นต่อหน่วยเวลา
Overheadscheduler ทำงานเพิ่มเติมไปเท่าใด
Fairnessperformance ที่ผู้ใช้ต่าง ๆ ได้รับ เท่าเทียมกันเพียงใด
Predictabilityperformance สม่ำเสมอเพียงใดเมื่อเวลาผ่านไป
Workloadชุดของ task ที่ระบบต้องทำ
Preemptive schedulerscheduler ที่ดึง resource คืนจาก task ที่กำลังทำอยู่ได้
Work-conservingresource ถูกใช้เสมอเมื่อมี task ให้ทำ (ไม่ปล่อยว่างทั้งที่มีงาน)
Scheduling algorithmรับ workload เป็น input, ตัดสินว่าจะทำ task ใดก่อน, ได้ performance metric (throughput, latency) เป็น output

สไลด์พิจารณาเฉพาะ scheduler ที่ preemptive และ work-conserving

FIFO (First In First Out)

  • ทำ task ตามลำดับที่มาถึง
  • ทำต่อไปจน task เสร็จ หรือสละ processor เอง
  • ตัวอย่าง: memcached (cache ของ Facebook สำหรับ friend list ฯลฯ)

ข้อดี: ง่าย และ overhead น้อยที่สุด เพราะสลับงานน้อยที่สุด

FIFO แย่เป็นพิเศษกับ workload แบบใด: เมื่อ task ยาวมาก่อน task สั้น task สั้นทั้งหมดต้องรอ task ยาวจนเสร็จ

SJF (Shortest Job First)

  • ทำ task ที่ เหลืองานน้อยที่สุด เสมอ
  • มักเรียกว่า Shortest Remaining Time First (SRTF)

SJF optimal สำหรับ average response time — ทำไม

สมมติมี task ยาวทำก่อน task สั้น ถ้าสลับให้ task สั้นทำก่อน: task สั้นเสร็จเร็วขึ้นเท่ากับความยาวของ task ยาว ส่วน task ยาวเสร็จช้าลงแค่เท่ากับความยาวของ task สั้น ผลรวมจึงลดลงเสมอ ทำซ้ำไปเรื่อย ๆ จนไม่มีคู่ให้สลับ ก็ได้ลำดับจากสั้นไปยาวซึ่งคือ SJF

ข้อเสียของ SJF

  • Starvation: task ยาวอาจไม่ได้ทำเลย ถ้ามี task สั้นเข้ามาเรื่อย ๆ
  • Variance ของ response time แย่ที่สุด: task สั้นเสร็จเร็วมาก task ยาวช้ามาก
  • ต้องรู้ว่าแต่ละ task เหลืองานเท่าใด ซึ่งในความเป็นจริงมักไม่รู้ล่วงหน้า (เสริม)

ตัวอย่างไล่ทีละขั้น

โจทย์ (ตามภาพในสไลด์ p.7): task ห้าชิ้นมาถึงต่อกันที่เวลา 0 ตามลำดับ A, B, C, D, E โดย A ยาว 10 ที่เหลือยาวชิ้นละ 1

FIFO ทำตามลำดับ A, B, C, D, E

taskช่วงที่ทำเสร็จที่response time
A0–101010
B10–111111
C11–121212
D12–131313
E13–141414

average = (10 + 11 + 12 + 13 + 14) / 5 = 60 / 5 = 12

SJF ทำชิ้นที่เหลืองานน้อยสุดก่อน: B, C, D, E แล้วจึง A

taskช่วงที่ทำเสร็จที่response time
B0–111
C1–222
D2–333
E3–444
A4–141414

average = (1 + 2 + 3 + 4 + 14) / 5 = 24 / 5 = 4.8

งานทั้งหมดเสร็จที่เวลา 14 เท่ากัน (throughput เท่ากัน) แต่ average response time ต่างกัน 2.5 เท่า A ช้าลง 4 หน่วย แลกกับอีกสี่ชิ้นเร็วขึ้นชิ้นละ 10

ขั้นที่ 1 / 6เริ่มต้น

รูปแบบ: ชื่อ เวลามาถึง ความยาว เช่น A 0 10 — แก้แล้ว simulation เริ่มใหม่

นโยบาย

เวลา = 0 · ready queue = A(10) → B(1) → C(1) → D(1) → E(1)

0
งานมาถึงยาวเหลือเสร็จresponse
A01010––
B011––
C011––
D011––
E011––
ready queue: ชื่อ(งานที่เหลือ)response = เสร็จ − มาถึง
1.0×

คำอธิบายทีละขั้น

สถานะเริ่มต้น

FIFO ทำงานตามลำดับที่มาถึง และทำจนเสร็จหรือจนงานสละ processor เอง response time ของงาน = เวลาที่งานเสร็จ − เวลาที่มาถึง

Round Robin

  • แต่ละ task ได้ resource เป็นช่วงเวลาคงที่ เรียกว่า time quantum
  • ถ้า task ไม่เสร็จในช่วงนั้น กลับไปต่อท้ายแถว

เลือก time quantum อย่างไร

time quantumผล
ยาวมาก (ถึงอนันต์)task แรกทำจนเสร็จก่อนเสมอ → กลายเป็น FIFO
สั้นมาก (เช่น หนึ่ง instruction)สลับถี่มาก → overhead สูง เวลาส่วนใหญ่หมดไปกับการสลับ ไม่ได้ทำงานจริง

จึงต้องเลือกค่ากลาง: สั้นพอให้ตอบสนองเร็ว ยาวพอให้ overhead ของการสลับเป็นสัดส่วนเล็ก

Round Robin กับ FIFO: RR ดีกว่าเสมอไหม

สมมติการสลับไม่มีต้นทุนเลย RR ก็ยัง ไม่ ดีกว่า FIFO เสมอ

task ขนาดเท่ากัน: A, B, C ยาวชิ้นละ 4 มาถึงพร้อมกัน

นโยบายลำดับการทำเสร็จที่average
FIFOAAAA BBBB CCCC4, 8, 12(4 + 8 + 12) / 3 = 8
RR (quantum 1)ABC ABC ABC ABC10, 11, 12(10 + 11 + 12) / 3 = 11

RR ทำให้ทุก task เสร็จช้าเกือบเท่า task สุดท้าย เพราะทุกชิ้นค้างไว้จนรอบท้าย ๆ ส่วน FIFO ปล่อยชิ้นแรกออกไปเร็ว เมื่อ task เท่ากัน FIFO ทำตัวเหมือน SJF (ทุกชิ้น "สั้นที่สุด" เท่ากัน) จึง optimal

task ขนาดต่างกัน: กับโจทย์ A ยาว 10 และอีกสี่ชิ้นยาว 1 ด้วย quantum 1: ลำดับ A B C D E แล้ว A ที่เหลือ เสร็จที่ B = 2, C = 3, D = 4, E = 5, A = 14 → average = (14 + 2 + 3 + 4 + 5) / 5 = 5.6 ใกล้ SJF (4.8) และดีกว่า FIFO (12) มาก โดยไม่ต้องรู้ความยาวของ task ล่วงหน้า

Round Robin = ยุติธรรม?

RR ไม่ได้ยุติธรรมเสมอไป และ "ยุติธรรม" นิยามได้หลายแบบ: ตามลำดับที่มา (FIFO)? ได้ CPU เท่ากัน? แล้วถ้าบาง task ไม่ต้องการส่วนแบ่งเต็ม? หรือลดความต่างกรณีแย่ที่สุด ระหว่างเวลาที่ task ใช้ถ้าไม่มีใครอื่น กับเวลาที่ใช้จริงภายใต้ scheduler? ปัญหานี้ชัดเมื่อ workload ผสม task ที่ใช้ I/O มากกับ task ที่ใช้ CPU มาก ซึ่งเป็นเรื่องของบทถัดไป

สรุปเปรียบเทียบ

FIFOSJFRound Robin
หลักการตามลำดับที่มาเหลืองานน้อยสุดก่อนทีละ time quantum วนกันไป
task ขนาดเท่ากันoptimal สำหรับ average response timeเหมือน FIFOแย่มาก
task ขนาดต่างกันแย่มากได้optimalใกล้เคียง SJF
overheadน้อยที่สุด–ขึ้นกับ time quantum
starvation–เกิดได้ (task ยาว)ไม่เกิด
variance ของ response time–แย่ที่สุด (pessimal)–
task ที่ผสม CPU กับ I/O–ได้ประโยชน์ทำได้ไม่ดี

จุดที่มักพลาด

1. คิดว่า Round Robin ดีกว่า FIFO เสมอ

กับ task ขนาดเท่ากัน RR แย่กว่ามาก

2. คิดว่า SJF ดีทุกด้าน

optimal เฉพาะ average response time แต่ variance แย่ที่สุดและเกิด starvation ได้

3. คิด response time จากเวลาที่เริ่มทำ

ตามสไลด์คือเวลาจนเสร็จ: เวลาที่เสร็จ − เวลาที่มาถึง

4. คิดว่า time quantum ยิ่งสั้นยิ่งดี

สั้นเกินไป overhead ของการสลับกินเวลาหมด

5. คิดว่า FIFO ไม่เคย optimal

optimal เมื่อ task ขนาดเท่ากัน และมี overhead น้อยที่สุดเสมอ

6. ลืมว่า SJF ในสไลด์เป็นแบบ preemptive

task ที่สั้นกว่ามาถึงกลางทางจะแทรกได้

ที่มา: 06-scheduling_v5 (1).pdf หน้า 2–14, 20–21