งานที่สั้นที่สุดก่อน (SJF): ตัวอย่างที่ยึดเอาเสียก่อนและไม่ยึดเสียก่อน

โดยทั่วไปมีวิธี SJF สองประเภท:

• SJF แบบไม่ยึดถือ
• SJF เชิงรุก

ลักษณะของการจัดตารางเวลา SJF

• โดยเชื่อมโยงกับแต่ละงานเป็นหน่วยของเวลาในการทำให้เสร็จ
• วิธีอัลกอริธึมนี้มีประโยชน์สำหรับการประมวลผลแบบแบตช์ โดยที่การรองานให้เสร็จสิ้นนั้นไม่สำคัญ
• สามารถปรับปรุงปริมาณงานของกระบวนการได้โดยทำให้แน่ใจว่างานที่สั้นกว่าจะถูกดำเนินการก่อน ดังนั้นจึงอาจมีระยะเวลาตอบสนองที่สั้น
• ช่วยปรับปรุงผลงานโดยเสนองานที่สั้นกว่า ซึ่งควรดำเนินการก่อน ซึ่งส่วนใหญ่จะมีระยะเวลาดำเนินการที่สั้นกว่า

SJF แบบไม่ยึดถือ

ในการกำหนดเวลาแบบไม่ยึดล่วงหน้า เมื่อมีการจัดสรรวงจรของ CPU ให้กับการประมวลผล กระบวนการจะคงไว้จนกว่าจะถึงสถานะรอหรือสิ้นสุด

ลองพิจารณากระบวนการทั้งห้าประการต่อไปนี้ ซึ่งแต่ละกระบวนการจะมีเวลาการระเบิดและเวลาที่มาถึงเฉพาะของตัวเอง

คิวกระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 0) เมื่อเวลา=0 P4 มาถึงและเริ่มดำเนินการ

ขั้นตอน 1) ณ เวลา= 1 กระบวนการ P3 มาถึง แต่ P4 ยังคงต้องการหน่วยดำเนินการ 2 หน่วยจึงจะเสร็จสมบูรณ์ จะดำเนินการต่อไป

ขั้นตอน 2) ณ เวลา =2 กระบวนการ P1 มาถึงและถูกเพิ่มในคิวที่รอ P4 จะดำเนินการต่อไป

ขั้นตอน 3) ณ เวลา = 3 กระบวนการ P4 จะดำเนินการเสร็จสิ้น มีการเปรียบเทียบเวลาระเบิดของ P3 และ P1 กระบวนการ P1 ถูกดำเนินการเนื่องจากเวลาในการระเบิดน้อยกว่าเมื่อเปรียบเทียบกับ P3

ขั้นตอน 4) ณ เวลา = 4 กระบวนการ P5 มาถึงและถูกเพิ่มในคิวที่รอ P1 จะดำเนินการต่อไป

ขั้นตอน 5) ณ เวลา = 5 กระบวนการ P2 มาถึงและถูกเพิ่มในคิวที่รอ P1 จะดำเนินการต่อไป

ขั้นตอน 6) ณ เวลา = 9 กระบวนการ P1 จะดำเนินการเสร็จสิ้น มีการเปรียบเทียบเวลาในการระเบิดของ P3, P5 และ P2 กระบวนการ P2 ถูกดำเนินการเนื่องจากเวลาการระเบิดต่ำสุด

ขั้นตอน 7) ณ เวลา=10 P2 กำลังดำเนินการ และ P3 และ P5 อยู่ในคิวรอ

ขั้นตอน 8) ณ เวลา = 11 กระบวนการ P2 จะดำเนินการเสร็จสิ้น มีการเปรียบเทียบเวลาระเบิดของ P3 และ P5 กระบวนการ P5 ถูกดำเนินการเนื่องจากเวลาการระเบิดต่ำกว่า

ขั้นตอน 9) ณ เวลา = 15 กระบวนการ P5 จะดำเนินการเสร็จสิ้น

ขั้นตอน 10) ณ เวลา = 23 กระบวนการ P3 จะดำเนินการเสร็จสิ้น

ขั้นตอน 11) ลองคำนวณเวลารอโดยเฉลี่ยสำหรับตัวอย่างข้างต้น

Wait time 
P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14

Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

SJF เชิงรุก

ใน Preemptive SJF Scheduling งานจะถูกจัดไว้ในคิวที่พร้อมใช้งานทันทีที่มาถึง กระบวนการที่มีเวลาระเบิดสั้นที่สุดจะเริ่มดำเนินการ หากมาถึงกระบวนการที่มีเวลาต่อเนื่องสั้นกว่า กระบวนการปัจจุบันจะถูกลบออกหรือระงับจากการดำเนินการ และงานที่สั้นกว่าจะถูกจัดสรรรอบ CPU

ลองพิจารณากระบวนการทั้งห้าต่อไปนี้:

คิวกระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 0) เมื่อเวลา=0 P4 มาถึงและเริ่มดำเนินการ

คิวกระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 1) ณ เวลา= 1 กระบวนการ P3 มาถึง แต่ P4 มีระยะเวลาการระเบิดที่สั้นกว่า จะดำเนินการต่อไป

ขั้นตอน 2) ที่เวลา = 2 กระบวนการ P1 มาถึงพร้อมกับเวลาต่อเนื่อง = 6 เวลาการระเบิดมากกว่าเวลาของ P4 ดังนั้น P4 จะดำเนินการต่อไป

ขั้นตอน 3) ณ เวลา = 3 กระบวนการ P4 จะดำเนินการเสร็จสิ้น มีการเปรียบเทียบเวลาระเบิดของ P3 และ P1 กระบวนการ P1 ถูกดำเนินการเนื่องจากเวลาการระเบิดต่ำกว่า

ขั้นตอน 4) ณ เวลา = 4 กระบวนการ P5 จะมาถึง มีการเปรียบเทียบเวลาในการระเบิดของ P3, P5 และ P1 กระบวนการ P5 ถูกดำเนินการเนื่องจากเวลาการระเบิดต่ำสุด กระบวนการ P1 ได้รับการยึดถือไว้แล้ว

คิวกระบวนการ	ระเบิดเวลา	เวลาถึง
P1	เหลืออีก 5 จาก 6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 5) ณ เวลา = 5 กระบวนการ P2 จะมาถึง มีการเปรียบเทียบเวลาในการระเบิดของ P1, P2, P3 และ P5 กระบวนการ P2 ถูกดำเนินการเนื่องจากเวลาต่อเนื่องน้อยที่สุด กระบวนการ P5 ได้รับการยึดถือไว้แล้ว

คิวกระบวนการ	ระเบิดเวลา	เวลาถึง
P1	เหลืออีก 5 จาก 6	2
P2	2	5
P3	8	1
P4	3	0
P5	เหลืออีก 3 จาก 4	4

ขั้นตอน 6) ณ เวลา =6 P2 กำลังดำเนินการ

ขั้นตอน 7) ณ เวลา =7 P2 ดำเนินการเสร็จสิ้น มีการเปรียบเทียบเวลาในการระเบิดของ P1, P3 และ P5 กระบวนการ P5 ถูกดำเนินการเนื่องจากเวลาต่อเนื่องน้อยกว่า

คิวกระบวนการ	ระเบิดเวลา	เวลาถึง
P1	เหลืออีก 5 จาก 6	2
P2	2	5
P3	8	1
P4	3	0
P5	เหลืออีก 3 จาก 4	4

ขั้นตอน 8) ณ เวลา =10 P5 จะดำเนินการเสร็จสิ้น มีการเปรียบเทียบเวลาระเบิดของ P1 และ P3 กระบวนการ P1 ถูกดำเนินการเนื่องจากเวลาในการระเบิดน้อยกว่า

ขั้นตอน 9) ณ เวลา =15 P1 ดำเนินการเสร็จสิ้น P3 เป็นกระบวนการเดียวที่เหลืออยู่ จะเริ่มดำเนินการ

ขั้นตอน 10) ณ เวลา =23 P3 ดำเนินการเสร็จสิ้น

ขั้นตอน 11) ลองคำนวณเวลารอโดยเฉลี่ยสำหรับตัวอย่างข้างต้น

Wait time 
P4= 0-0=0
P1=  (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14

Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

ข้อดีของเอสเจเอฟ

นี่คือประโยชน์/ข้อดีของการใช้วิธีการ SJF:

• SJF มักใช้สำหรับการจัดกำหนดการระยะยาว
• จะช่วยลดเวลารอโดยเฉลี่ยเหนืออัลกอริธึม FIFO (เข้าก่อนออกก่อน)
• วิธี SJF ให้เวลารอโดยเฉลี่ยต่ำสุดสำหรับชุดกระบวนการเฉพาะ
• เหมาะสำหรับงานที่รันเป็นแบตช์โดยทราบเวลารันล่วงหน้า
• สำหรับระบบแบทช์ของการจัดกำหนดการระยะยาว สามารถรับการประมาณเวลาต่อเนื่องได้จากคำอธิบายงาน
• สำหรับ Short-Term Scheduling เราจำเป็นต้องทำนายค่าของการระเบิดครั้งถัดไป
• อาจเหมาะสมที่สุดโดยคำนึงถึงเวลาตอบสนองโดยเฉลี่ย

ข้อเสีย/ข้อเสียของ SJF

นี่คือข้อเสีย/ข้อเสียของอัลกอริทึม SJF:

• ต้องทราบเวลาเสร็จงานให้เร็วขึ้น แต่ก็คาดเดาได้ยาก
• มักใช้ในระบบแบทช์สำหรับการจัดกำหนดการระยะยาว
• SJF ไม่สามารถนำไปใช้ได้ การตั้งเวลาซีพียู สำหรับระยะสั้น เนื่องจากไม่มีวิธีการเฉพาะในการทำนายความยาวของ CPU ที่จะเกิดขึ้น
• อัลกอริธึมนี้อาจทำให้เวลาตอบสนองหรือความอดอยากยาวนานมาก
• ต้องใช้ความรู้ว่ากระบวนการหรืองานจะดำเนินการนานแค่ไหน
• นำไปสู่ความอดอยากที่ไม่ลดเวลาตอบสนองโดยเฉลี่ย
• เป็นการยากที่จะทราบความยาวของคำขอ CPU ที่จะเกิดขึ้น
• ควรบันทึกเวลาที่ผ่านไป ซึ่งส่งผลให้โปรเซสเซอร์มีค่าใช้จ่ายมากขึ้น

สรุป

• SJF เป็นอัลกอริธึมที่เลือกกระบวนการที่มีเวลาดำเนินการน้อยที่สุดสำหรับการดำเนินการครั้งถัดไป
• SJF Scheduling เชื่อมโยงกับแต่ละงานเป็นหน่วยเวลาในการทำให้เสร็จ
• วิธีอัลกอริธึมนี้มีประโยชน์สำหรับการประมวลผลแบบแบตช์ โดยที่การรองานให้เสร็จสิ้นนั้นไม่สำคัญ
• โดยพื้นฐานแล้ววิธีการ SJF มีสองประเภท 1) SJF แบบไม่ยึดถือ และ 2) SJF เชิงยึดถือ
• ในการกำหนดเวลาแบบไม่ยึดล่วงหน้า เมื่อมีการจัดสรรวงจรของ CPU ให้กับการประมวลผล กระบวนการจะคงไว้จนกว่าจะถึงสถานะรอหรือสิ้นสุด
• ใน Preemptive SJF Scheduling งานจะถูกจัดไว้ในคิวที่พร้อมใช้งานทันทีที่มาถึง
• แม้ว่ากระบวนการที่มีเวลาต่อเนื่องสั้นจะเริ่มต้นขึ้น แต่กระบวนการปัจจุบันจะถูกลบออกหรือระงับจากการดำเนินการ และงานที่สั้นกว่าจะถูกดำเนินการเป็นอันดับแรก
• SJF มักใช้สำหรับการจัดกำหนดการระยะยาว
• จะช่วยลดเวลารอโดยเฉลี่ยเหนืออัลกอริธึม FIFO (เข้าก่อนออกก่อน)
• ในการกำหนดเวลา SJF จะต้องทราบเวลาที่เสร็จงานล่วงหน้า แต่ก็คาดเดาได้ยาก
• ไม่สามารถใช้ SJF กับการตั้งเวลา CPU ในระยะสั้นได้ เนื่องจากไม่มีวิธีการเฉพาะในการทำนายความยาวของ CPU ที่จะเกิดขึ้น