อัลกอริทึมการจัดลำดับความสำคัญ: แบบแทรกแซงได้ และแบบไม่แทรกแซงได้

การจัดลำดับความสำคัญคืออะไร?

การจัดลำดับความสำคัญ เป็นวิธีการจัดกำหนดการกระบวนการที่ยึดตามลำดับความสำคัญ ในอัลกอริทึมนี้ ตัวจัดกำหนดการจะเลือกงานที่จะทำงานตามลำดับความสำคัญ

กระบวนการที่มีลำดับความสำคัญสูงกว่าควรดำเนินการก่อน ในขณะที่งานที่มีลำดับความสำคัญเท่ากันจะดำเนินการแบบ Round-Robin หรือ FCFS ลำดับความสำคัญขึ้นอยู่กับข้อกำหนดหน่วยความจำ ความต้องการเวลา ฯลฯ

ประเภทของการจัดลำดับความสำคัญ

การจัดลำดับความสำคัญของงานแบ่งออกเป็นสองประเภทหลัก:

การจัดกำหนดการชั่วคราว

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

การจัดกำหนดการแบบไม่ยึดถือล่วงหน้า

ในวิธีการจัดตารางเวลาแบบนี้ ซีพียูจะถูกจัดสรรให้กับกระบวนการเฉพาะ กระบวนการที่ใช้ซีพียูอย่างต่อเนื่องจะปล่อยซีพียูโดยการเปลี่ยนบริบทหรือยุติการทำงาน วิธีนี้เป็นวิธีเดียวที่สามารถใช้ได้กับแพลตฟอร์มฮาร์ดแวร์ที่หลากหลาย เนื่องจากไม่จำเป็นต้องใช้ฮาร์ดแวร์พิเศษ (เช่น ตัวจับเวลา) เหมือนกับการจัดตารางเวลาแบบแย่งชิง

ลักษณะของการจัดลำดับความสำคัญ

• อัลกอริธึม CPU ที่จัดตารางเวลากระบวนการตามลำดับความสำคัญ
• มันถูกใช้ใน Operaระบบ ting สำหรับการดำเนินการกระบวนการแบทช์
• หากงานสองงานที่มีลำดับความสำคัญเท่ากันนั้นเป็นงาน READY งานนั้นจะทำงานใน มาก่อนเสริฟก่อน รากฐาน
• ในการจัดกำหนดการลำดับความสำคัญ จะมีการกำหนดหมายเลขให้กับแต่ละกระบวนการที่ระบุระดับลำดับความสำคัญ
• ยิ่งตัวเลขต่ำ ความสำคัญยิ่งสูง
• ในอัลกอริธึมการจัดตารางเวลาแบบนี้ หากมีกระบวนการใหม่เข้ามาที่มีลำดับความสำคัญสูงกว่ากระบวนการที่กำลังทำงานอยู่ กระบวนการที่กำลังทำงานอยู่จะถูกขัดจังหวะ

ตัวอย่างการจัดลำดับความสำคัญ

พิจารณาห้ากระบวนการต่อไปนี้ P1 ถึง P5 แต่ละกระบวนการมีลำดับความสำคัญ เวลาประมวลผล และเวลามาถึงที่ไม่ซ้ำกัน

กระบวนการ	ลำดับความสำคัญ	ระเบิดเวลา	เวลาถึง
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

ขั้นตอน 0) ณ เวลา = 0 กระบวนการ P1 และ P2 มาถึง โดย P1 มีลำดับความสำคัญสูงกว่า P2 การประมวลผลเริ่มต้นด้วยกระบวนการ P1 ซึ่งมีเวลาในการประมวลผล (burst time) เท่ากับ 4

ขั้นตอน 1) เมื่อเวลา = 1 จะไม่มีกระบวนการใหม่เข้ามา การทำงานจะดำเนินต่อไปด้วย P1

ขั้นตอน 2) ณ เวลาที่ 2 ไม่มีกระบวนการใหม่มาถึง ดังนั้นคุณจึงสามารถดำเนินการต่อด้วย P1 ได้ P2 อยู่ในคิวรอ

ขั้นตอน 3) ณ เวลา 3 ไม่มีกระบวนการใหม่เข้ามา คุณจึงสามารถดำเนินการต่อด้วย P1 ได้ กระบวนการ P2 ยังคงอยู่ในคิวรอ

ขั้นตอน 4) ณ เวลา 4 P1 ได้เสร็จสิ้นการดำเนินการแล้ว P2 เริ่มดำเนินการ

ขั้นตอน 5) เมื่อเวลา = 5 ไม่มีกระบวนการใหม่เข้ามา ดังนั้นเราจึงดำเนินการต่อด้วย P2

ขั้นตอน 6) เมื่อเวลา = 6, P3 มาถึง P3 มีลำดับความสำคัญสูงกว่า (1) เมื่อเทียบกับ P2 ที่มีลำดับความสำคัญ (2) P2 ถูกขัดจังหวะ และ P3 เริ่มดำเนินการ

กระบวนการ	ลำดับความสำคัญ	ระเบิดเวลา	เวลาถึง
P1	1	4	0
P2	2	1 ใน 3 อยู่ระหว่างการพิจารณา	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

ขั้นตอน 7) เมื่อถึงเวลา 7 ไม่มีกระบวนการใหม่เข้ามา ดังนั้นเราจึงดำเนินการต่อด้วย P3 ส่วน P2 อยู่ในคิวรอ

ขั้นตอน 8) เมื่อเวลา = 8 ไม่มีกระบวนการใหม่เข้ามา ดังนั้นเราจึงสามารถดำเนินการต่อด้วย P3 ได้

ขั้นตอน 9) เมื่อเวลา = 9 ไม่มีกระบวนการใหม่เกิดขึ้น ดังนั้นเราจึงสามารถดำเนินการต่อด้วย P3 ได้

ขั้นตอน 10) เมื่อถึงช่วงเวลาที่ 10 จะไม่มีกระบวนการใหม่เกิดขึ้น ดังนั้นเราจึงดำเนินการต่อด้วย P3

ขั้นตอน 11) เมื่อเวลา = 11, P4 มาถึงด้วยลำดับความสำคัญ 4 P3 มีลำดับความสำคัญสูงกว่า จึงดำเนินการต่อไป

กระบวนการ	ลำดับความสำคัญ	ระเบิดเวลา	เวลาถึง
P1	1	4	0
P2	2	1 ใน 3 อยู่ระหว่างการพิจารณา	0
P3	1	2 ใน 7 อยู่ระหว่างการพิจารณา	6
P4	3	4	11
P5	2	2	12

ขั้นตอน 12) เมื่อเวลา = 12, P5 มาถึง P3 มีลำดับความสำคัญสูงกว่า ดังนั้นจึงดำเนินการต่อ

ขั้นตอน 13) ณ เวลา t = 13, P3 ทำงานเสร็จสิ้น เรามี P2, P4, P5 อยู่ในคิวพร้อมทำงาน P2 และ P5 มีลำดับความสำคัญเท่ากัน เวลาที่ P2 มาถึงเร็วกว่า P5 ดังนั้น P2 จึงเริ่มทำงาน

กระบวนการ	ลำดับความสำคัญ	ระเบิดเวลา	เวลาถึง
P1	1	4	0
P2	2	1 ใน 3 อยู่ระหว่างการพิจารณา	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

ขั้นตอน 14) ณ เวลา t = 14 กระบวนการ P2 ได้เสร็จสิ้นการทำงานแล้ว กระบวนการ P4 และ P5 อยู่ในสถานะรอ กระบวนการ P5 มีลำดับความสำคัญสูงสุดและเริ่มการทำงาน

ขั้นตอน 15) เมื่อเวลา = 15, P5 ดำเนินการต่อไป

ขั้นตอน 16) เมื่อเวลา = 16 กระบวนการ P5 เสร็จสิ้นการทำงานแล้ว เหลือเพียงกระบวนการ P4 เท่านั้น และกระบวนการ P4 ก็เริ่มทำงาน

ขั้นตอน 17) ณ เวลา = 20, P4 ได้ดำเนินการเสร็จสิ้นแล้ว และไม่มีกระบวนการใดเหลืออยู่

ขั้นตอน 18) เรามาคำนวณเวลาการรอเฉลี่ยสำหรับตัวอย่างข้างต้นกัน

เวลารอ = เวลาเริ่มต้น – เวลาที่มาถึง + เวลาที่รอการระเบิดครั้งถัดไป

P1 = 0 - 0 = 0
P2 = 4 - 0 + 7 = 11
P3 = 6 - 6 = 0
P4 = 16 - 11 = 5
Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6

ข้อดีของการจัดลำดับความสำคัญ

ต่อไปนี้คือข้อดี/ประโยชน์ของการใช้วิธีการจัดตารางเวลาตามลำดับความสำคัญ:

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

ข้อเสียของการจัดลำดับความสำคัญ

ต่อไปนี้คือข้อเสีย/ข้อจำกัดของการจัดตารางเวลาตามลำดับความสำคัญ:

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

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