ระบบปฏิบัติการเบื้องต้น
สวัสดีฮับ! ฉันอยากจะนำเสนอชุดบทความแปลของวรรณกรรมเรื่องหนึ่งที่น่าสนใจในความคิดเห็นของฉัน - OSTEP เนื้อหานี้จะตรวจสอบการทำงานของระบบปฏิบัติการที่มีลักษณะคล้ายยูนิกซ์อย่างลึกซึ้ง กล่าวคือ การทำงานกับกระบวนการ ตัวกำหนดเวลาต่างๆ หน่วยความจำ และส่วนประกอบอื่น ๆ ที่คล้ายกันซึ่งประกอบเป็นระบบปฏิบัติการสมัยใหม่ คุณสามารถดูต้นฉบับของวัสดุทั้งหมดได้ที่นี่ . โปรดทราบว่าการแปลจัดทำขึ้นอย่างไม่เป็นมืออาชีพ (ค่อนข้างอิสระ) แต่ฉันหวังว่าฉันจะคงความหมายทั่วไปไว้
งานห้องปฏิบัติการในเรื่องนี้สามารถพบได้ที่นี่:
ส่วนอื่น ๆ :
คุณสามารถตรวจสอบช่องของฉันได้ที่ =)
การวางแผน: คิวคำติชมหลายระดับ
ในการบรรยายนี้เราจะพูดถึงปัญหาในการพัฒนาแนวทางหนึ่งที่มีชื่อเสียงที่สุด
การวางแผนซึ่งเรียกว่า คิวคำติชมหลายระดับ (MLFQ) ตัวกำหนดเวลา MLFQ ได้รับการอธิบายครั้งแรกในปี 1962 โดย Fernando J. Corbató ในระบบที่เรียกว่า
ระบบแบ่งเวลาที่ใช้ร่วมกันได้ (CTSS) งานเหล่านี้ (รวมถึงงานในภายหลังด้วย
Multics) ได้รับการเสนอชื่อเข้าชิงรางวัล Turing Award ในเวลาต่อมา ผู้วางแผนก็คือ
ต่อมาได้ปรับปรุงให้มีลักษณะที่ปรากฏอยู่แล้ว
ระบบที่ทันสมัยบางอย่าง
อัลกอริธึม MLFQ พยายามแก้ไขปัญหาพื้นฐาน 2 ประการที่ทับซ้อนกัน
ประการแรกมันพยายามปรับเวลาตอบสนองให้เหมาะสมซึ่งดังที่เราได้พูดคุยไปแล้วในการบรรยายครั้งก่อนนั้นถูกปรับให้เหมาะสมโดยวิธีการเริ่มต้นที่จุดเริ่มต้นของคิวมากที่สุด
งานสั้น อย่างไรก็ตามระบบปฏิบัติการไม่ทราบว่ากระบวนการใดกระบวนการหนึ่งจะทำงานได้นานเท่าใดและสิ่งนี้
ความรู้ที่จำเป็นสำหรับการทำงานของอัลกอริทึม SJF, STCF ในประการที่สอง, MLFQ กำลังพยายาม
ทำให้ระบบตอบสนองต่อผู้ใช้ (เช่น สำหรับผู้ที่นั่งและ
จ้องมองที่หน้าจอเพื่อรอให้งานเสร็จสิ้น) และลดเวลาลง
การตอบสนอง. น่าเสียดายที่อัลกอริทึมเช่น RR ช่วยปรับปรุงเวลาตอบสนองได้อย่างมาก
ส่งผลเสียต่อการวัดเวลาตอบสนอง ดังนั้นปัญหาของเรา: วิธีการออกแบบ
ตัวกำหนดตารางเวลาที่จะตอบสนองความต้องการของเราโดยไม่ต้องรู้อะไรเลย
ลักษณะของกระบวนการโดยทั่วไป? ผู้จัดกำหนดการสามารถเรียนรู้ลักษณะของงานได้อย่างไร
ซึ่งเปิดตัวแล้วจึงตัดสินใจวางแผนได้ดีขึ้น?
สาระสำคัญของปัญหา: จะวางแผนการทำงานโดยปราศจากความรู้ที่สมบูรณ์ได้อย่างไร?
วิธีการออกแบบตัวกำหนดเวลาที่ลดเวลาตอบสนองไปพร้อม ๆ กัน
สำหรับงานแบบโต้ตอบและในขณะเดียวกันก็ลดเวลาตอบสนองให้สั้นลงโดยไม่รู้ตัว
ความรู้เรื่องเวลาปฏิบัติงาน?
หมายเหตุ: เราเรียนรู้จากเหตุการณ์ครั้งก่อนๆ
คิว MLFQ เป็นตัวอย่างที่ดีเยี่ยมของระบบที่เรียนรู้จาก
เหตุการณ์ในอดีตเพื่อทำนายอนาคต แนวทางที่คล้ายกันมักเป็นเช่นนั้น
พบได้ในระบบปฏิบัติการ (และสาขาวิทยาการคอมพิวเตอร์อื่นๆ อีกมากมาย รวมทั้งสาขาต่างๆ
การทำนายฮาร์ดแวร์และอัลกอริธึมการแคช) ที่เที่ยวคล้ายๆกัน
จะถูกกระตุ้นเมื่องานมีระยะพฤติกรรมและสามารถคาดเดาได้
อย่างไรก็ตามคุณควรระมัดระวังกับเทคนิคนี้เนื่องจากการทำนายนั้นง่ายมาก
อาจกลับกลายเป็นว่าไม่ถูกต้องและทำให้ระบบตัดสินใจแย่กว่านั้น
ก็คงไม่มีความรู้เลย
MLFQ: กฎพื้นฐาน
มาดูกฎพื้นฐานของอัลกอริทึม MLFQ กัน และถึงแม้การนำอัลกอริธึมนี้ไปใช้
มีหลายวิธี วิธีพื้นฐานก็คล้ายกัน
ในการนำไปใช้งาน เราจะมาดูกัน MLFQ จะมีหลายอย่าง
แยกคิวซึ่งแต่ละคิวจะมีลำดับความสำคัญที่แตกต่างกัน เมื่อไหร่ก็ได้
งานที่พร้อมสำหรับการดำเนินการจะอยู่ในคิวเดียว MLFQ ใช้ลำดับความสำคัญ
เพื่อตัดสินใจว่าจะรันงานใดเพื่อดำเนินการ เช่น งานที่สูงขึ้น
ลำดับความสำคัญ (งานจากคิวที่มีลำดับความสำคัญสูงสุด) จะถูกเปิดใช้งานก่อน
คิว.
แน่นอนว่าอาจมีมากกว่าหนึ่งงานในคิวที่กำหนด
ดังนั้นพวกเขาจะมีลำดับความสำคัญเท่ากัน ในกรณีนี้จะใช้กลไก
RR เพื่อกำหนดเวลาการทำงานระหว่างงานเหล่านี้
ดังนั้นเราจึงมาถึงกฎพื้นฐานสองข้อสำหรับ MLFQ:
- กฎข้อที่ 1: ถ้าลำดับความสำคัญ(A) > ลำดับความสำคัญ(B) งาน A จะถูกเปิดตัว (B จะไม่)
- กฎข้อที่ 2: หากลำดับความสำคัญ (A) = ลำดับความสำคัญ (B) A&B จะเริ่มต้นโดยใช้ RR
จากที่กล่าวมาข้างต้น องค์ประกอบสำคัญในการวางแผน MLFQ
เป็นลำดับความสำคัญ แทนที่จะให้ความสำคัญกับแต่ละคนเป็นหลัก
งาน MLFQ จะเปลี่ยนลำดับความสำคัญขึ้นอยู่กับพฤติกรรมที่สังเกตได้
ตัวอย่างเช่น หากงานส่งงานไปที่ CPU อย่างต่อเนื่องในขณะที่รออินพุตจากแป้นพิมพ์
MLFQ จะรักษาลำดับความสำคัญของกระบวนการให้สูงเพราะเป็นเช่นนั้น
กระบวนการโต้ตอบควรใช้งานได้ ในทางกลับกัน หากงานนั้นเกิดขึ้นอย่างต่อเนื่องและ
ใช้ CPU อย่างหนักในระยะเวลานาน MLFQ จะลดระดับลง
ลำดับความสำคัญ. ดังนั้น MLFQ จะศึกษาพฤติกรรมของกระบวนการในขณะที่กำลังทำงานอยู่
และใช้พฤติกรรม
ลองวาดตัวอย่างว่าคิวอาจมีลักษณะอย่างไร ณ จุดใดจุดหนึ่ง
เวลา จากนั้นคุณจะได้สิ่งนี้:
ในรูปแบบนี้ 2 กระบวนการ A และ B อยู่ในคิวที่มีลำดับความสำคัญสูงสุด กระบวนการ
C อยู่ที่ไหนสักแห่งตรงกลาง และกระบวนการ D อยู่ที่ท้ายสุดของคิว ตามข้างต้น
ตามคำอธิบายของอัลกอริทึม MLFQ ตัวกำหนดเวลาจะดำเนินการงานที่มีค่าสูงสุดเท่านั้น
ลำดับความสำคัญตาม RR และงาน C, D จะไม่ทำงาน
โดยปกติแล้ว สแน็ปช็อตแบบคงที่จะไม่ให้ภาพที่สมบูรณ์เกี่ยวกับวิธีการทำงานของ MLFQ
สิ่งสำคัญคือต้องเข้าใจว่าภาพเปลี่ยนแปลงไปอย่างไรเมื่อเวลาผ่านไป
ความพยายามที่ 1: วิธีเปลี่ยนลำดับความสำคัญ
ณ จุดนี้ คุณต้องตัดสินใจว่า MLFQ จะเปลี่ยนระดับความสำคัญอย่างไร
งาน (และตำแหน่งของงานในคิว) ขณะที่ดำเนินไปตลอดวงจรชีวิต สำหรับ
สิ่งนี้จำเป็นต้องคำนึงถึงขั้นตอนการทำงาน: จำนวนหนึ่ง
งานแบบโต้ตอบที่มีรันไทม์สั้น (และดังนั้นจึงมีการรีลีสบ่อยครั้ง
CPU) และงานที่ต้องใช้เวลานานหลายอย่างซึ่งใช้ CPU ตลอดเวลาในการทำงาน
เวลาตอบสนองไม่สำคัญสำหรับงานดังกล่าว และด้วยวิธีนี้คุณสามารถลองครั้งแรกได้
ใช้อัลกอริทึม MLFQ ด้วยกฎต่อไปนี้:
- กฎข้อที่ 3: เมื่องานเข้าสู่ระบบ งานนั้นจะอยู่ในคิวที่มีคะแนนสูงสุด
- ลำดับความสำคัญ.
- กฎข้อที่ 4a: หากงานใช้กรอบเวลาทั้งหมดที่ได้รับมอบหมาย งานนั้นก็จะเป็นเช่นนั้น
- ลำดับความสำคัญจะลดลง
- กฎข้อที่ 4b: ถ้างานปล่อย CPU ก่อนกรอบเวลาจะหมดลง แสดงว่างานนั้นปล่อย CPU ก่อนหมดเวลา
- ยังคงมีลำดับความสำคัญเหมือนเดิม
ตัวอย่างที่ 1: งานเดียวที่ใช้เวลานาน
ดังที่เห็นในตัวอย่างนี้ งานการรับเข้าถูกกำหนดไว้สูงสุด
ลำดับความสำคัญ. หลังจากกรอบเวลา 10ms กระบวนการจะถูกลดระดับตามลำดับความสำคัญ
นักวางแผน หลังจากหน้าต่างเวลาถัดไป งานก็จะถูกลดระดับเป็นในที่สุด
ลำดับความสำคัญต่ำสุดในระบบ โดยที่ยังคงอยู่
ตัวอย่างที่ 2: ส่งมอบงานสั้นๆ
ตอนนี้เรามาดูตัวอย่างว่า MLFQ จะพยายามเข้าใกล้ SJF อย่างไร ในนั้น
ตัวอย่าง สองงาน: A ซึ่งเป็นงานที่ต้องใช้เวลานานอย่างต่อเนื่อง
ครอบครอง CPU และ B ซึ่งเป็นงานโต้ตอบสั้นๆ สมมติ
ว่า A ทำงานมาระยะหนึ่งแล้วเมื่อถึงเวลาที่งาน B มาถึง
กราฟนี้แสดงผลลัพธ์ของสถานการณ์ งาน A ก็เหมือนกับงานอื่นๆ
การใช้งาน CPU อยู่ที่ด้านล่างสุด งาน B จะมาถึงเวลา T=100 และจะถึง
วางไว้ในคิวที่มีลำดับความสำคัญสูงสุด เนื่องจากเวลาใช้งานมันสั้นแล้ว
จะเสร็จก่อนถึงคิวสุดท้าย
จากตัวอย่างนี้ ควรเข้าใจเป้าหมายหลักของอัลกอริทึม: เนื่องจากอัลกอริทึมไม่เป็นเช่นนั้น
รู้ว่างานนั้นยาวหรือสั้น อันดับแรกเขาถือว่างานนั้นเป็นงานนั้น
สั้นและให้ความสำคัญสูงสุด หากนี่เป็นงานที่สั้นจริงๆ
จะเสร็จเร็วไม่อย่างนั้นงานยาวก็จะเคลื่อนช้าๆ
ลำดับความสำคัญลงและในไม่ช้าจะพิสูจน์ว่าเธอเป็นงานที่ยาวนานซึ่งไม่ได้ทำ
ต้องการการตอบสนอง
ตัวอย่างที่ 3: แล้ว I/O ล่ะ?
ตอนนี้เรามาดูตัวอย่าง I/O กัน ตามที่ระบุไว้ในกฎข้อ 4b
หากกระบวนการปล่อยโปรเซสเซอร์โดยไม่ใช้เวลาโปรเซสเซอร์ทั้งหมด
จากนั้นจะยังคงอยู่ในระดับความสำคัญเท่าเดิม จุดประสงค์ของกฎนี้ค่อนข้างง่าย
- หากงานแบบโต้ตอบดำเนินการ I/O จำนวนมาก เช่น การรอ
จากการกดปุ่มผู้ใช้หรือการกดเมาส์ งานดังกล่าวจะทำให้โปรเซสเซอร์ว่าง
ก่อนถึงหน้าต่างที่กำหนด เราไม่ต้องการลดลำดับความสำคัญของงานดังกล่าว
และก็จะยังคงอยู่ระดับเดิม
ตัวอย่างนี้แสดงให้เห็นว่าอัลกอริทึมจะทำงานอย่างไรกับกระบวนการดังกล่าว - งานแบบโต้ตอบ B ซึ่งต้องการ CPU เป็นเวลา 1 มิลลิวินาทีเท่านั้นก่อนดำเนินการ
กระบวนการ I/O และงาน A ที่ใช้เวลานาน ซึ่งใช้เวลาทั้งหมดกับ CPU
MLFQ เก็บกระบวนการ B ไว้ในลำดับความสำคัญสูงสุดเนื่องจากยังคงดำเนินต่อไป
ปล่อยซีพียู หาก B เป็นงานแบบโต้ตอบ แสดงว่าอัลกอริทึมสำเร็จ
เป้าหมายของคุณคือการทำงานแบบโต้ตอบได้อย่างรวดเร็ว
ปัญหากับอัลกอริทึม MLFQ ปัจจุบัน
ในตัวอย่างก่อนหน้านี้ เราได้สร้าง MLFQ เวอร์ชันพื้นฐาน และดูเหมือนว่าเขา
ทำงานได้ดีและตรงไปตรงมา โดยกระจายเวลา CPU อย่างยุติธรรมระหว่างกัน
งานที่ยาวนานและอนุญาตให้งานระยะสั้นหรืองานปริมาณมาก
ทำงานกับ I/O ได้อย่างรวดเร็ว น่าเสียดายที่แนวทางนี้มีหลายวิธี
ปัญหาร้ายแรง
ประการแรกปัญหาความหิวโหย: หากระบบมีการโต้ตอบมากมาย
งานต่างๆ จะใช้เวลาประมวลผลทั้งหมดจึงไม่ใช่งานเดียวเป็นเวลานาน
งานจะไม่สามารถดำเนินการได้ (พวกเขากำลังหิวโหย)
ในประการที่สองผู้ใช้ที่ชาญฉลาดสามารถเขียนโปรแกรมของตนได้
หลอกผู้กำหนดเวลา การหลอกลวงอยู่ที่การทำบางสิ่งเพื่อบังคับ
ตัวกำหนดเวลาทำให้กระบวนการมีเวลา CPU มากขึ้น อัลกอริธึมนั้น
ที่อธิบายไว้ข้างต้นค่อนข้างเสี่ยงต่อการโจมตีที่คล้ายกัน: ก่อนกรอบเวลาจริง
สิ้นสุดแล้ว คุณต้องดำเนินการ I/O (สำหรับบางคน ไม่ว่าจะเป็นไฟล์ใดก็ตาม)
และทำให้ CPU ว่างมากขึ้น พฤติกรรมดังกล่าวจะทำให้คุณคงอยู่เหมือนเดิม
คิวเองและได้รับเวลา CPU ที่มากขึ้นอีกครั้ง ถ้าคุณทำ
สิ่งนี้ถูกต้อง (เช่น ดำเนินการ 99% ของเวลาหน้าต่างก่อนที่จะปล่อย CPU)
งานดังกล่าวสามารถผูกขาดโปรเซสเซอร์ได้อย่างง่ายดาย
ในที่สุด โปรแกรมก็สามารถเปลี่ยนพฤติกรรมของมันเมื่อเวลาผ่านไปได้ งานเหล่านั้น
ซึ่งใช้ซีพียูสามารถโต้ตอบได้ ในตัวอย่างของเราคล้ายกัน
งานต่างๆ จะไม่ได้รับการรักษาที่พวกเขาสมควรได้รับจากผู้จัดกำหนดการเหมือนที่คนอื่นๆ จะได้รับ
(เริ่มต้น) งานแบบโต้ตอบ
คำถามสำหรับผู้ชม: การโจมตีกำหนดการใดที่สามารถทำได้ในโลกสมัยใหม่?
ความพยายามที่ 2: การเพิ่มลำดับความสำคัญ
ลองเปลี่ยนกฎและดูว่าเราสามารถหลีกเลี่ยงปัญหาได้หรือไม่
การอดอาหาร สิ่งที่เราสามารถทำได้เพื่อให้แน่ใจว่าเกี่ยวข้อง
งาน CPU จะได้รับเวลา (แม้ว่าจะไม่นานก็ตาม)
วิธีแก้ปัญหาง่ายๆ คุณสามารถแนะนำเป็นระยะๆ
เพิ่มลำดับความสำคัญของงานดังกล่าวทั้งหมดในระบบ มีหลายวิธี
เพื่อให้บรรลุเป้าหมายนี้ เรามาลองใช้สิ่งง่ายๆ เป็นตัวอย่าง: แปล
งานทั้งหมดจะได้รับลำดับความสำคัญสูงสุดทันที ดังนั้นกฎใหม่:
- Rule5: หลังจากช่วง S ระยะหนึ่ง ให้ย้ายงานทั้งหมดในระบบไปยังคิวสูงสุด
กฎใหม่ของเราแก้ไขปัญหาสองข้อพร้อมกัน ขั้นแรกให้กระบวนการต่างๆ
รับประกันว่าจะไม่อดอยาก: งานที่มีลำดับความสำคัญสูงสุดจะถูกแบ่งออก
เวลา CPU ตามอัลกอริธึม RR ดังนั้นกระบวนการทั้งหมดจะได้รับ
เวลาซีพียู ประการที่สองหากกระบวนการบางอย่างที่เคยใช้มาก่อน
มีเพียงโปรเซสเซอร์เท่านั้นที่สามารถโต้ตอบได้ โดยจะยังคงอยู่ในคิวที่มีคะแนนสูงสุด
ลำดับความสำคัญหลังจากได้รับการเพิ่มลำดับความสำคัญเป็นสูงสุดเพียงครั้งเดียว
ลองดูตัวอย่าง ในสถานการณ์สมมตินี้ ให้พิจารณาหนึ่งกระบวนการที่ใช้
CPU และกระบวนการโต้ตอบสั้น ๆ สองกระบวนการ ทางด้านซ้ายของรูปภาพ รูปภาพแสดงพฤติกรรมที่ไม่มีการเลื่อนระดับตามลำดับความสำคัญ ดังนั้นงานที่ใช้เวลานานจึงเริ่มอดอยากหลังจากงานโต้ตอบสองงานเข้ามาในระบบ ในรูปทางด้านขวา การเพิ่มลำดับความสำคัญจะดำเนินการทุกๆ 50 มิลลิวินาที ดังนั้นกระบวนการทั้งหมดจึงรับประกันว่าจะได้รับเวลา CPU และจะเปิดตัวเป็นระยะๆ ในกรณีนี้คือ 50ms เป็นตัวอย่าง แต่ในความเป็นจริงตัวเลขนี้สูงกว่าเล็กน้อย
แน่นอนว่าการเพิ่มระยะเวลา S ที่เพิ่มขึ้นเป็นระยะๆ
คำถามเชิงตรรกะ: ควรตั้งค่าอะไร? หนึ่งในผู้ได้รับเกียรติ
วิศวกรระบบ John Ousterhout เรียกปริมาณดังกล่าวในระบบว่า voo-doo
คงที่ เนื่องจากในทางใดทางหนึ่งจำเป็นต้องใช้มนต์ดำเพื่อแก้ไข
การจัดแสดง และน่าเสียดายที่ S มีกลิ่นเช่นนี้ หากตั้งค่าไว้ด้วย
งานใหญ่-ยาวจะเริ่มอดอยาก และถ้าคุณตั้งค่าต่ำเกินไป
งานแบบโต้ตอบจะไม่ได้รับเวลา CPU ที่เหมาะสม
ความพยายามที่ 3: การบัญชีที่ดีขึ้น
ตอนนี้เรามีปัญหาอื่นที่ต้องแก้ไข: จะทำอย่างไร
ปล่อยให้กำหนดการของเราถูกหลอกเหรอ? คนที่ถูกตำหนิสำหรับความเป็นไปได้นี้คือ
กฎ 4a, 4b ซึ่งอนุญาตให้งานรักษาลำดับความสำคัญ ทำให้โปรเซสเซอร์ว่าง
ก่อนเวลาที่กำหนดจะหมดลง จะจัดการกับสิ่งนี้อย่างไร?
วิธีแก้ปัญหาในกรณีนี้ถือได้ว่าเป็นการบัญชีเวลา CPU ที่ดีขึ้นในแต่ละรายการ
ระดับ MLFQ แทนที่จะลืมเวลาที่โปรแกรมใช้งาน
โปรเซสเซอร์ตามระยะเวลาที่กำหนดควรนำมาพิจารณาและบันทึกไว้ หลังจาก
กระบวนการได้ใช้เวลาที่กำหนดไปแล้ว ควรลดระดับเป็นขั้นตอนถัดไป
ระดับความสำคัญ ตอนนี้ไม่สำคัญว่ากระบวนการจะใช้เวลาอย่างไร - อย่างไร
ประมวลผลบนโปรเซสเซอร์อย่างต่อเนื่องหรือเป็นการโทรหลายครั้ง ดังนั้น,
กฎข้อ 4 ควรเขียนใหม่เป็นรูปแบบต่อไปนี้:
- Rule4: หลังจากที่งานใช้เวลาที่จัดสรรในคิวปัจจุบันจนหมด (ไม่ว่างานนั้นจะปล่อย CPU ว่างกี่ครั้งก็ตาม) ลำดับความสำคัญของงานนั้นจะลดลง (งานจะเลื่อนลงไปตามคิว)
ลองดูตัวอย่าง:
»
รูปนี้แสดงให้เห็นว่าจะเกิดอะไรขึ้นหากคุณพยายามหลอกผู้กำหนดเวลา เช่น
ถ้าเป็นไปตามกฎ 4a ก่อนหน้านี้ 4b จะได้ผลลัพธ์ทางด้านซ้าย สุขสันต์ใหม่ครับ
กฎคือผลลัพธ์ทางด้านขวา ก่อนที่จะมีการป้องกัน กระบวนการใดๆ ก็ตามสามารถเรียก I/O ก่อนที่จะเสร็จสิ้น และ
จึงครอง CPU หลังจากเปิดใช้งานการป้องกัน โดยไม่คำนึงถึงพฤติกรรม
I/O เขาจะยังคงอยู่ในคิวจึงไม่สามารถทุจริตได้
เข้าครอบครองทรัพยากร CPU
การปรับปรุง MLFQ และปัญหาอื่นๆ
ด้วยการปรับปรุงข้างต้นทำให้เกิดปัญหาใหม่: หนึ่งในปัญหาหลัก
คำถาม - จะกำหนดพารามิเตอร์ของตัวกำหนดเวลาได้อย่างไร? เหล่านั้น. ควรจะเท่าไหร่.
คิว? หน้าต่างโปรแกรมภายในคิวควรมีขนาดเท่าใด? ยังไง
ควรเพิ่มลำดับความสำคัญของโปรแกรมเพื่อหลีกเลี่ยงความอดอยากและ
คำนึงถึงการเปลี่ยนแปลงพฤติกรรมของโปรแกรมด้วยหรือไม่? ไม่มีคำตอบง่ายๆ สำหรับคำถามเหล่านี้
ตอบและทำการทดลองกับโหลดและการกำหนดค่าที่ตามมาเท่านั้น
ผู้วางแผนอาจนำไปสู่ความสมดุลที่น่าพอใจ
ตัวอย่างเช่น การใช้งาน MLFQ ส่วนใหญ่อนุญาตให้คุณกำหนดที่แตกต่างกันได้
ช่วงเวลาสำหรับคิวที่แตกต่างกัน คิวที่มีลำดับความสำคัญสูงมักจะ
มีการกำหนดช่วงเวลาสั้น ๆ คิวเหล่านี้ประกอบด้วยงานแบบโต้ตอบ
การสลับระหว่างซึ่งค่อนข้างละเอียดอ่อนและควรใช้เวลา 10 หรือน้อยกว่า
นางสาว. ในทางตรงกันข้าม คิวที่มีลำดับความสำคัญต่ำประกอบด้วยงานที่ใช้เวลานาน
ซีพียู และในกรณีนี้ ช่วงเวลาที่ยาวนานพอดีมาก (100ms)
ในตัวอย่างนี้ มี 2 งานที่ทำงานในคิวที่มีลำดับความสำคัญสูง 20
ms แบ่งออกเป็นหน้าต่าง 10ms 40ms ในคิวกลาง (หน้าต่าง 20ms) และในลำดับความสำคัญต่ำ
กรอบเวลาคิวกลายเป็น 40ms โดยที่งานต่างๆ เสร็จสิ้น
การใช้งาน Solaris OS ของ MLFQ คือคลาสของตัวกำหนดเวลาการแบ่งใช้เวลา
ผู้วางแผนจะจัดเตรียมชุดตารางที่กำหนดตรงตามที่ควร
ลำดับความสำคัญของกระบวนการเปลี่ยนแปลงตลอดช่วงชีวิต ขนาดที่ควรจะเป็น
หน้าต่างที่จัดสรรไว้ และความถี่ที่คุณต้องเพิ่มลำดับความสำคัญของงาน ผู้ดูแลระบบ
ระบบสามารถโต้ตอบกับตารางนี้และทำให้ตัวกำหนดตารางเวลาทำงาน
แตกต่างกัน ตามค่าเริ่มต้น ตารางนี้มี 60 คิวโดยเพิ่มขึ้นทีละน้อย
ขนาดหน้าต่างตั้งแต่ 20ms (ลำดับความสำคัญสูง) ถึงหลายร้อย ms (ลำดับความสำคัญต่ำ) และ
พร้อมทั้งเพิ่มภารกิจทั้งหมดหนึ่งครั้งต่อวินาที
ผู้วางแผน MLFQ อื่นๆ ไม่ได้ใช้ตารางหรือข้อมูลเฉพาะเจาะจงใดๆ
กฎเกณฑ์ที่อธิบายไว้ในการบรรยายนี้ ตรงกันข้ามกลับใช้การคำนวณลำดับความสำคัญ
สูตรทางคณิตศาสตร์ ตัวอย่างเช่น ตัวกำหนดเวลา FreeBSD ใช้สูตรสำหรับ
คำนวณลำดับความสำคัญปัจจุบันของงานตามระยะเวลาของกระบวนการ
ซีพียูที่ใช้ นอกจากนี้ การใช้งาน CPU ก็จะลดลงตามกาลเวลา เป็นต้น
ดังนั้น การเพิ่มลำดับความสำคัญจึงค่อนข้างแตกต่างไปจากที่อธิบายไว้ข้างต้น นี่เป็นเรื่องจริง
เรียกว่าอัลกอริธึมการสลายตัว ตั้งแต่เวอร์ชัน 7.1 FreeBSD ได้ใช้ตัวกำหนดเวลา ULE
ในที่สุด ตัวกำหนดเวลาจำนวนมากก็มีคุณสมบัติอื่นๆ ตัวอย่างเช่นบางส่วน
ตัวกำหนดเวลาสงวนระดับสูงสุดสำหรับการทำงานของระบบปฏิบัติการดังนั้น
ดังนั้นจึงไม่มีกระบวนการของผู้ใช้ใดสามารถรับลำดับความสำคัญสูงสุดได้
ระบบ. บางระบบสามารถให้คำแนะนำช่วยเหลือได้
ผู้วางแผนสามารถจัดลำดับความสำคัญได้อย่างถูกต้อง เช่น การใช้คำสั่ง ดี
คุณสามารถเพิ่มหรือลดลำดับความสำคัญของงานได้และเพิ่มหรือ
ลดโอกาสในการใช้เวลา CPU ของโปรแกรม
MLFQ: สรุป
เราได้อธิบายแนวทางการวางแผนที่เรียกว่า MLFQ ชื่อของเขา
อยู่ในหลักการทำงาน - มีหลายคิวและใช้คำติชม
เพื่อกำหนดลำดับความสำคัญของงาน
รูปแบบสุดท้ายของกฎจะเป็นดังนี้:
- Rule1: ถ้าลำดับความสำคัญ(A) > ลำดับความสำคัญ(B) งาน A จะถูกเปิดตัว (B จะไม่)
- Rule2: ถ้าลำดับความสำคัญ(A) = ลำดับความสำคัญ(B) A&B จะเริ่มใช้ RR
- Rule3: เมื่องานเข้าสู่ระบบจะถูกจัดไว้ในคิวที่มีลำดับความสำคัญสูงสุด
- Rule4: หลังจากที่งานใช้เวลาที่จัดสรรในคิวปัจจุบันจนหมด (ไม่ว่างานนั้นจะปล่อย CPU ว่างกี่ครั้งก็ตาม) ลำดับความสำคัญของงานนั้นจะลดลง (งานจะเลื่อนลงไปตามคิว)
- Rule5: หลังจากช่วง S ระยะหนึ่ง ให้ย้ายงานทั้งหมดในระบบไปยังคิวสูงสุด
MLFQ มีความน่าสนใจด้วยเหตุผลต่อไปนี้ แทนที่จะต้องอาศัยความรู้
ลักษณะของงานล่วงหน้า อัลกอริธึมจะศึกษาพฤติกรรมที่ผ่านมาของงานและชุด
ลำดับความสำคัญตามลำดับ ดังนั้นเขาจึงพยายามนั่งบนเก้าอี้สองตัวพร้อมกัน - เพื่อให้ได้ประสิทธิผลสำหรับงานเล็ก ๆ (SJF, STCF) และวิ่งระยะยาวโดยสุจริต
งานโหลด CPU ดังนั้นหลายๆ ระบบ รวมถึง BSD และอนุพันธ์ของระบบต่างๆ
Solaris, Windows, Mac ใช้อัลกอริทึมบางรูปแบบเป็นตัวกำหนดตารางเวลา
MLFQ เป็นพื้นฐาน
วัสดุเพิ่มเติม:
- (คอมพิวเตอร์)
ที่มา: will.com