อัลกอริธึมการจัดลำดับความสำคัญ: ตัวอย่างแบบยึดเอาเสียก่อนและไม่ยึดเสียก่อน
การจัดลำดับความสำคัญคืออะไร?
การจัดลำดับความสำคัญ เป็นวิธีการจัดกำหนดการกระบวนการที่ยึดตามลำดับความสำคัญ ในอัลกอริทึมนี้ ตัวจัดกำหนดการจะเลือกงานที่จะทำงานตามลำดับความสำคัญ
กระบวนการที่มีลำดับความสำคัญสูงกว่าควรดำเนินการก่อน ในขณะที่งานที่มีลำดับความสำคัญเท่ากันจะดำเนินการแบบ Round-Robin หรือ FCFS ลำดับความสำคัญขึ้นอยู่กับข้อกำหนดหน่วยความจำ ความต้องการเวลา ฯลฯ
ประเภทของการจัดลำดับความสำคัญ
การจัดลำดับความสำคัญแบ่งออกเป็นสองประเภทหลัก:
การจัดกำหนดการชั่วคราว
ในการจัดกำหนดการล่วงหน้า งานส่วนใหญ่จะได้รับมอบหมายตามลำดับความสำคัญ บางครั้งสิ่งสำคัญคือต้องรันงานที่มีลำดับความสำคัญสูงกว่าก่อนงานอื่นที่มีลำดับความสำคัญต่ำกว่า แม้ว่างานที่มีลำดับความสำคัญต่ำกว่ายังคงรันอยู่ก็ตาม งานที่มีลำดับความสำคัญต่ำกว่าจะพักไว้ระยะหนึ่งและดำเนินการต่อเมื่องานที่มีลำดับความสำคัญสูงกว่าเสร็จสิ้นการดำเนินการ
การจัดกำหนดการแบบไม่ยึดถือล่วงหน้า
ในวิธีการกำหนดเวลาประเภทนี้ CPU ได้รับการจัดสรรให้กับกระบวนการเฉพาะ กระบวนการที่ทำให้ CPU ไม่ว่าง จะปล่อย CPU โดยการสลับบริบทหรือยุติ เป็นวิธีเดียวที่สามารถใช้ได้กับแพลตฟอร์มฮาร์ดแวร์ต่างๆ นั่นเป็นเพราะว่าไม่จำเป็นต้องใช้ฮาร์ดแวร์พิเศษ (เช่น ตัวจับเวลา) เช่น การตั้งเวลาล่วงหน้า
ลักษณะของการจัดลำดับความสำคัญ
- อัลกอริธึม 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 ซึ่งมีเวลาระเบิด 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) ณ เวลา=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) ณ เวลา =14 กระบวนการ P2 ได้เสร็จสิ้นการดำเนินการแล้ว P4 และ P5 อยู่ในสถานะรอ P5 มีลำดับความสำคัญสูงสุดและเริ่มดำเนินการ
ขั้นตอน 15) ณ เวลา =15 P5 ดำเนินการต่อไป
ขั้นตอน 16) ณ เวลา = 16, P5 เสร็จสิ้นการดำเนินการแล้ว P4 เป็นกระบวนการเดียวที่เหลืออยู่ มันเริ่มดำเนินการ
ขั้นตอน 17) ณ เวลา =20 P5 ได้เสร็จสิ้นการดำเนินการแล้ว และไม่มีกระบวนการใดเหลืออยู่
ขั้นตอน 18) ลองคำนวณเวลารอโดยเฉลี่ยสำหรับตัวอย่างข้างต้น
เวลารอ = เวลาเริ่มต้น – เวลาที่มาถึง + เวลาที่รอการระเบิดครั้งถัดไป
P1 = o - o = o P2 =4 - o + 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 เนื่องจากกระบวนการอื่นกำลังทำงานอยู่ในขณะนี้
- หากกระบวนการที่มีลำดับความสำคัญสูงกว่าใหม่ยังคงอยู่ในคิวที่พร้อม กระบวนการที่อยู่ในสถานะรออาจต้องรอเป็นระยะเวลานาน
สรุป
- การจัดกำหนดการลำดับความสำคัญเป็นวิธีหนึ่งของการจัดกำหนดการกระบวนการที่ยึดตามลำดับความสำคัญ ในอัลกอริทึมนี้ ตัวจัดกำหนดการจะเลือกงานที่จะทำงานตามลำดับความสำคัญ
- ในการจัดกำหนดการล่วงหน้าตามลำดับความสำคัญ งานส่วนใหญ่จะได้รับมอบหมายตามลำดับความสำคัญ
- ในวิธีการจัดตารางเวลาแบบ Priority Non-preemptive CPU ได้รับการจัดสรรให้กับกระบวนการเฉพาะ
- กระบวนการต่างๆ จะดำเนินการตามลำดับความสำคัญ ดังนั้นลำดับความสำคัญที่สูงจึงไม่จำเป็นต้องรอนาน ซึ่งจะช่วยประหยัดเวลา
- หากกระบวนการที่มีลำดับความสำคัญสูงใช้เวลา CPU มาก กระบวนการที่มีลำดับความสำคัญต่ำกว่าอาจหยุดทำงานและจะถูกเลื่อนออกไปเป็นเวลาไม่มีกำหนด