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

ตัวกำหนดตารางเวลากระบวนการจัดกำหนดการกระบวนการต่างๆที่จะกำหนดให้กับ 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 ตามอัลกอริทึมที่กำหนดให้กับคิว