อัลกอริทึมการตั้งเวลาระบบปฏิบัติการ

ตัวกำหนดตารางเวลากระบวนการจัดกำหนดการกระบวนการต่างๆที่จะกำหนดให้กับ CPU ตามอัลกอริทึมการจัดตารางเวลาเฉพาะ มีอัลกอริธึมการตั้งเวลากระบวนการยอดนิยมหกรายการซึ่งเราจะพูดถึงในบทนี้ -

• การจัดกำหนดการมาก่อนได้ก่อน (FCFS)
• การจัดกำหนดการที่สั้นที่สุดงานถัดไป (SJN)
• การจัดลำดับความสำคัญ
• เวลาที่เหลืออยู่สั้นที่สุด
• การตั้งเวลา Round Robin (RR)
• การจัดตารางคิวหลายระดับ

อัลกอริทึมเหล่านี้เป็นอย่างใดอย่างหนึ่ง non-preemptive or preemptive. อัลกอริทึมที่ไม่ได้รับการป้องกันล่วงหน้าได้รับการออกแบบมาเพื่อให้เมื่อกระบวนการเข้าสู่สถานะที่กำลังทำงานอยู่จะไม่สามารถถูกจองไว้ก่อนจนกว่าจะเสร็จสิ้นเวลาที่กำหนดในขณะที่การจัดกำหนดการล่วงหน้าจะขึ้นอยู่กับลำดับความสำคัญซึ่งตัวกำหนดตารางเวลาอาจนำกระบวนการทำงานที่มีลำดับความสำคัญต่ำมาก่อนได้ตลอดเวลาเมื่อมีลำดับความสำคัญสูง กระบวนการเข้าสู่สถานะพร้อม

มาก่อนได้ก่อน (FCFS)

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

Wait time ของแต่ละกระบวนการมีดังนี้ -

กระบวนการ	เวลารอ: เวลาให้บริการ - เวลามาถึง
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

เวลารอเฉลี่ย: (0 + 4 + 6 + 13) / 4 = 5.75

งานที่สั้นที่สุดถัดไป (SJN)

• นี้เรียกอีกอย่างว่า shortest job firstหรือ SJF

• นี่คืออัลกอริธึมการจัดกำหนดการล่วงหน้าแบบไม่ตัดทอนล่วงหน้า

• แนวทางที่ดีที่สุดในการลดเวลารอ

• ใช้งานง่ายในระบบ Batch ซึ่งทราบเวลา CPU ที่ต้องการล่วงหน้า

• เป็นไปไม่ได้ที่จะนำไปใช้ในระบบโต้ตอบที่ไม่ทราบเวลา CPU ที่ต้องการ

• ผู้ประมวลผลควรทราบล่วงหน้าว่าจะใช้เวลาดำเนินการเท่าใด

ระบุ: ตารางของกระบวนการและเวลาที่มาถึงเวลาดำเนินการ

กระบวนการ	เวลาถึง	เวลาดำเนินการ	เวลาให้บริการ
P0	0	5	0
P1	1	3	5
P2	2	8	14
P3	3	6	8

Waiting time ของแต่ละกระบวนการมีดังนี้ -

กระบวนการ	รอเวลา
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	14 - 2 = 12
P3	8 - 3 = 5

เวลารอเฉลี่ย: (0 + 4 + 12 + 5) / 4 = 21/4 = 5.25

การจัดกำหนดการตามลำดับความสำคัญ

• การจัดกำหนดการตามลำดับความสำคัญเป็นอัลกอริทึมที่ไม่มีการป้องกันล่วงหน้าและเป็นหนึ่งในอัลกอริทึมการจัดกำหนดการที่พบบ่อยที่สุดในระบบแบตช์

• แต่ละกระบวนการถูกกำหนดลำดับความสำคัญ กระบวนการที่มีลำดับความสำคัญสูงสุดจะต้องดำเนินการก่อนและอื่น ๆ

• กระบวนการที่มีลำดับความสำคัญเท่ากันจะดำเนินการตามลำดับก่อนหลัง

• ลำดับความสำคัญสามารถตัดสินใจได้ตามความต้องการหน่วยความจำข้อกำหนดเวลาหรือความต้องการทรัพยากรอื่น ๆ

ระบุ: ตารางของกระบวนการและเวลามาถึงเวลาดำเนินการและลำดับความสำคัญ เรากำลังพิจารณาว่า 1 คือลำดับความสำคัญต่ำสุด

กระบวนการ	เวลาถึง	เวลาดำเนินการ	ลำดับความสำคัญ	เวลาให้บริการ
P0	0	5	1	0
P1	1	3	2	11
P2	2	8	1	14
P3	3	6	3	5

Waiting time ของแต่ละกระบวนการมีดังนี้ -

กระบวนการ	รอเวลา
P0	0 - 0 = 0
P1	11 - 1 = 10
P2	14 - 2 = 12
P3	5 - 3 = 2

เวลารอเฉลี่ย: (0 + 10 + 12 + 2) / 4 = 24/4 = 6

เวลาที่เหลืออยู่สั้นที่สุด

• เวลาที่เหลืออยู่ที่สั้นที่สุด (SRT) คืออัลกอริธึม SJN เวอร์ชันล่วงหน้า

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

• เป็นไปไม่ได้ที่จะนำไปใช้ในระบบโต้ตอบที่ไม่ทราบเวลา CPU ที่ต้องการ

• มักใช้ในสภาพแวดล้อมแบบกลุ่มที่งานสั้น ๆ ต้องให้ความสำคัญ

การตั้งเวลา Round Robin

• Round Robin เป็นอัลกอริธึมการตั้งเวลากระบวนการล่วงหน้า

• แต่ละกระบวนการมีเวลาแก้ไขเพื่อดำเนินการเรียกว่าไฟล์ quantum.

• เมื่อกระบวนการดำเนินการในช่วงเวลาหนึ่งกระบวนการจะถูกยกเลิกและกระบวนการอื่น ๆ จะดำเนินการตามช่วงเวลาที่กำหนด

• การสลับบริบทใช้เพื่อบันทึกสถานะของกระบวนการที่ถูกจองไว้ล่วงหน้า

Wait time ของแต่ละกระบวนการมีดังนี้ -

กระบวนการ	เวลารอ: เวลาให้บริการ - เวลามาถึง
P0	(0 - 0) + (12 - 3) = 9
P1	(3 - 1) = 2
P2	(6 - 2) + (14 - 9) + (20 - 17) = 12
P3	(9 - 3) + (17 - 12) = 11

เวลารอเฉลี่ย: (9 + 2 + 12 + 11) / 4 = 8.5

การจัดตารางคิวหลายระดับ

คิวหลายระดับไม่ใช่อัลกอริทึมการจัดกำหนดการที่เป็นอิสระ พวกเขาใช้ประโยชน์จากอัลกอริทึมอื่น ๆ ที่มีอยู่เพื่อจัดกลุ่มและกำหนดเวลางานที่มีลักษณะทั่วไป

• หลายคิวจะถูกรักษาไว้สำหรับกระบวนการที่มีลักษณะทั่วไป
• แต่ละคิวสามารถมีอัลกอริทึมการตั้งเวลาของตัวเอง
• ลำดับความสำคัญจะถูกกำหนดให้กับแต่ละคิว

ตัวอย่างเช่นงานที่เชื่อมต่อกับ CPU สามารถกำหนดเวลาในคิวเดียวและงานที่ผูกกับ I / O ทั้งหมดในคิวอื่น จากนั้น Process Scheduler จะเลือกงานจากแต่ละคิวและกำหนดให้กับ CPU ตามอัลกอริทึมที่กำหนดให้กับคิว