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

การจัดกำหนดการงานที่สั้นที่สุดครั้งแรกคืออะไร?

งานที่สั้นที่สุดก่อน (SJF) เป็นอัลกอริธึมที่เลือกกระบวนการที่มีเวลาดำเนินการน้อยที่สุดสำหรับการดำเนินการครั้งถัดไป วิธีการจัดกำหนดการนี้สามารถยึดถือหรือไม่ยึดถือก็ได้ ช่วยลดเวลารอโดยเฉลี่ยสำหรับกระบวนการอื่นที่รอการดำเนินการได้อย่างมาก 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 นั้น งานต่างๆ จะถูกใส่เข้าไปในคิวพร้อมทำงานตามลำดับที่เข้ามา กระบวนการที่มีเวลาประมวลผลสั้นที่สุดจะเริ่มทำงาน หากมีกระบวนการที่มีเวลาประมวลผลสั้นกว่าเข้ามา กระบวนการปัจจุบันจะถูกนำออกหรือถูกขัดจังหวะจากการทำงาน และงานที่มีเวลาประมวลผลสั้นกว่าจะได้รับการจัดสรรรอบการทำงานของ 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) เมื่อเวลา t = 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) เมื่อเวลา t = 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 จะถูกประมวลผลเนื่องจากเวลาประมวลผลของ 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 (First In First Out)
• วิธี SJF ให้ค่าเวลาการรอเฉลี่ยต่ำที่สุดสำหรับชุดกระบวนการที่กำหนดไว้
• เหมาะสำหรับงานที่รันเป็นแบตช์โดยทราบเวลารันล่วงหน้า
• สำหรับระบบแบทช์ของการจัดกำหนดการระยะยาว สามารถรับการประมาณเวลาต่อเนื่องได้จากคำอธิบายงาน
• สำหรับ Short-Term Scheduling เราจำเป็นต้องทำนายค่าของการระเบิดครั้งถัดไป
• น่าจะเป็นวิธีที่ดีที่สุดเมื่อพิจารณาจากระยะเวลาดำเนินการโดยเฉลี่ย

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

ต่อไปนี้คือข้อเสีย/ข้อจำกัดบางประการของอัลกอริทึม SJF:

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

คำถามที่พบบ่อย