CPU Scheduling Algorithm SRTF (Shortest Remaining Time First)

สวัสดีครับวันนี้ผู้เขียนจะมาพูดถึง Algorithm หนึ่ง Algorithm ใน ระบบ OS ก็คือ SRTF (Shortest Remaining Time First)

เป็น algorithm ที่ได้รับการปรับปรุงมาจาก SJF โดยจะกำหนดให้ process ที่ 1 มี burst time น้อยที่ 1 สุด ณ เวลานั้น ๆ เป็ นprocess ที1 จะได้ CPU ใช้ก่อนดังนั้นสิ่งที่ เราต้องคำนึงถึงก็คือเวลาที่ process เข้าสู่ ready queue เราจะใช้ข้อมูลในตาราง 2 ในการหาเวลาที่ ใช้ไปทั้งหมดของ process ที่มีอยู่ในระบบ

เงื่อนไขที่ต้องคำนึงถึงเมื่อออกแบบหรือเลือกใช้ scheduling algorithm

CPU utilization -> ความต้องการที่จะใช้ CPU อย่างเต็มที่และสูงสุด (ให้ CPU ทำงานตลอดเวลา)
Throughput -> จำนวนของ process ที่มีการประมวลผลเสร็จในหนึ่งชวงเวลา
Turnaround time -> เวลาที่ใช้ในการทํงานของ process ตั้งแต่เริ่มต้นจนกระทั่งเสร็จงาน โดยนับรวมทั้งหมด เช่น การรอใช้ หน่วยความจำการรรอใน ready queue การประมวลผลใน CPU และการทำ I/O
Waiting time -> เวลาที่ process ต้องอยู่ใน ready queue
Response time -> เวลาที่ระบบสนองตอบต่อการร้องของ

ยกตัวอย่างเช่น

Gantt chart ที่เราได้จากข้อมูลในตารางคือ

Process: P1 เริ่มการประมวลผลใน CPU ก่อน ณ เวลาที่ เข้ามา (arrival time = 0) process: P2 เข้ามาใน queue เมื่อเวลาเท่ากับ 1 เมื่อเปรียบเทียบเวลาที่ต้องการใช้ CPU กับ P2 แลว P2 มี burst time = 4 ms แต่ P1 ยังเหลือ burst time อีก 7 ms ซึ่งเป็นเวลาที่ มากกว่า P2 ของดังนั้น P1 จึงถูกดึงออกจาก (preempt) CPU และ P2 ก็ได้สิทธิในการใช้ CPU แทนต่อมาP3 เข้าสู่ queue ที่เวลาเท่ากับ 2 เมื่อเปรียบเทียบ burst time ของทั้งสาม process -> P1 = 7, P2 = 3, และ P3 = 9 ดังนั้น P2 ก็ได้ใช้ CPU ต่อไป และเมื่อ P4 เข้าสู่ queue เมื่อเวลาเท่ากับ 3 ณ เวลานี้ burst time ของ P1 = 7, P2 = 2, P3 = 9, และ P4 = 5 จึงทำให้า P2 ได้ ใช้ CPU ต่อจนสิ้นสุการทำงาน หลังจากนั้นเวลาใน CPU ก็เป็นของ P4 ตามด้วย P1 และ P3 ตามลําดับดังรูป

รูป Diagram การทำงานของ Process State

การทำงานมี process เข้ามาอยู่ใน ready รอ CPU จัดการ scheduler แล้วนำงานนั้นเข้าไปที่ running ถ้าทำงานอยู่ แล้วมีงานที่มี burst time น้อยกว่าเข้ามาใน ready งานที่ running จะถูก interrupt กลับมาที่ ready หรืองานที่ทำเสร็จเเล้วต้องรอ I/O หรือต้องรองานอื่นๆ เพื่อให้เสร็จ ก็จะกลับมาอยู่ใน waiting ถ้าพร้อมแล้วก็กลับมาใน ready แล้วทำเหมือนเดิม ละก็ออกไป terminated

Code