อัลกอริธึมการจัดลำดับความสำคัญ: ตัวอย่างแบบยึดเอาเสียก่อนและไม่ยึดเสียก่อน

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

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

กระบวนการที่มีลำดับความสำคัญสูงกว่าควรดำเนินการก่อน ในขณะที่งานที่มีลำดับความสำคัญเท่ากันจะดำเนินการแบบ 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 มาก กระบวนการที่มีลำดับความสำคัญต่ำกว่าอาจหยุดทำงานและจะถูกเลื่อนออกไปเป็นเวลาไม่มีกำหนด