การจัดตารางเวลา (คอมพิวเตอร์)

จากวิกิพีเดีย สารานุกรมเสรี
ข้ามไปที่การนำทาง ข้ามไปที่การค้นหา

ใน การ คำนวณการจัดตารางเวลา คือการกระทำ ของการกำหนดทรัพยากรเพื่อดำเนินงาน แหล่งข้อมูลอาจเป็นโปรเซสเซอร์ลิงค์เครือข่ายหรือการ์ดเอ็กซ์แพนชัน งานอาจเป็น เธรดกระบวนการหรือกระแสข้อมูล_

กิจกรรมการจัดกำหนดการดำเนินการโดยกระบวนการที่เรียกว่าตัวจัดกำหนดการ ตัวจัดกำหนดการมักจะได้รับการออกแบบมาเพื่อให้ทรัพยากรคอมพิวเตอร์ทั้งหมดไม่ว่าง (เช่นใน การจัดสรร ภาระงาน ) อนุญาตให้ผู้ใช้หลายคนแบ่งปันทรัพยากรระบบอย่างมีประสิทธิภาพ หรือเพื่อให้บรรลุเป้าหมายคุณภาพของบริการ

การจัดตารางเวลาเป็นพื้นฐานของการคำนวณเอง และเป็นส่วนสำคัญของรูปแบบการดำเนินการของระบบคอมพิวเตอร์ แนวคิดของการจัดตารางเวลาทำให้คอมพิวเตอร์ทำงานหลายอย่างพร้อมกันได้ด้วยหน่วยประมวลผลกลาง (CPU) ตัวเดียว

เป้าหมาย

ผู้จัดกำหนดการอาจมุ่งเป้าไปที่เป้าหมายอย่างน้อยหนึ่งเป้าหมาย ตัวอย่างเช่น

  • การ เพิ่มปริมาณ งานสูงสุด (จำนวนงานที่เสร็จสมบูรณ์ต่อหน่วยเวลา)
  • ลด เวลารอ (เวลาจากงานพร้อมจนถึงจุดแรกที่เริ่มดำเนินการ);
  • ลดเวลาแฝงหรือเวลาตอบสนอง ให้น้อย ที่สุด (เวลาจากงานพร้อมจนกว่าจะเสร็จในกรณีของกิจกรรมแบบกลุ่ม[1] [2] [3]หรือจนกว่าระบบตอบสนองและส่งเอาต์พุตแรกให้กับผู้ใช้ในกรณีที่มีกิจกรรมแบบโต้ตอบ); [4]
  • เพิ่มความเป็นธรรม ให้สูงสุด (เวลา CPU เท่ากันในแต่ละกระบวนการ หรือเวลาที่เหมาะสมโดยทั่วไปตามลำดับความสำคัญและปริมาณงานของแต่ละกระบวนการ)

ในทางปฏิบัติ เป้าหมายเหล่านี้มักขัดแย้งกัน (เช่น ปริมาณงานกับเวลาแฝง) ดังนั้นตัวจัดกำหนดการจะปรับใช้การประนีประนอมที่เหมาะสม การตั้งค่าวัดจากข้อกังวลข้อใดข้อหนึ่งที่กล่าวถึงข้างต้น ขึ้นอยู่กับความต้องการและวัตถุประสงค์ของผู้ใช้

ใน สภาพแวดล้อม แบบเรียลไทม์เช่นระบบฝังตัวสำหรับการควบคุมอัตโนมัติในอุตสาหกรรม (เช่นวิทยาการหุ่นยนต์ ) ตัวจัดกำหนดการต้องตรวจสอบให้แน่ใจว่ากระบวนการสามารถบรรลุตามกำหนดเวลา นี่เป็นสิ่งสำคัญในการรักษาระบบให้เสถียร งานตามกำหนดการสามารถแจกจ่ายไปยังอุปกรณ์ระยะไกลผ่านเครือข่ายและจัดการผ่านส่วนหลังของผู้ดูแลระบบได้

ประเภทของตัวกำหนดตารางเวลาระบบปฏิบัติการ

ตัวจัดกำหนดการคือโมดูลระบบปฏิบัติการที่เลือกงานถัดไปที่จะเข้าระบบและกระบวนการถัดไปที่จะรัน ระบบปฏิบัติการอาจมีตัวกำหนดตารางเวลาที่แตกต่างกันถึงสามประเภท: ตัวกำหนดตารางเวลาระยะยาว (หรือเรียกอีกอย่างว่าตัวจัดกำหนดการการรับเข้าเรียนหรือตัวจัดกำหนดการระดับสูง) ตัวจัดกำหนดการระยะกลางหรือระยะกลางและตัวจัดกำหนดการระยะสั้น ชื่อแนะนำความถี่สัมพัทธ์กับการทำงานของมัน

ตัวกำหนดตารางเวลากระบวนการ

ตัวกำหนดตารางเวลากระบวนการเป็นส่วนหนึ่งของระบบปฏิบัติการที่ตัดสินใจว่ากระบวนการใดทำงานในช่วงเวลาหนึ่ง โดยปกติแล้วจะมีความสามารถในการหยุดกระบวนการที่กำลังทำงานอยู่ชั่วคราว ย้ายไปยังด้านหลังของคิวที่กำลังทำงานอยู่ และเริ่มกระบวนการใหม่ ตัวจัดกำหนดการดังกล่าวเรียกว่าตัวจัดกำหนดการ แบบ ยึดเอา เสียก่อน มิฉะนั้น ตัวกำหนดตารางเวลาแบบร่วมมือ [5]

เราแยกความแตกต่างระหว่าง "การจัดกำหนดการระยะยาว" "การจัดกำหนดการระยะกลาง" และ "การจัดกำหนดการระยะสั้น" ตามความถี่ที่ต้องทำ [6]

กำหนดการระยะยาว

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

โดยทั่วไป กระบวนการส่วนใหญ่สามารถอธิบายเป็นI/O-boundหรือCPU-bound. กระบวนการที่ผูกกับ I/O คือกระบวนการที่ใช้เวลาทำ I/O มากกว่าที่ใช้ในการคำนวณ ในทางตรงกันข้าม กระบวนการที่ผูกกับ CPU จะสร้างคำขอ I/O นานๆ ครั้ง โดยใช้เวลามากขึ้นในการคำนวณ เป็นสิ่งสำคัญที่ตัวจัดกำหนดการระยะยาวจะเลือกกระบวนการที่ดีที่ผสมผสานระหว่าง I/O-bound และ CPU-bound ถ้ากระบวนการทั้งหมดถูกผูกไว้กับ I/O คิวที่พร้อมจะว่างเปล่าเกือบทุกครั้ง และตัวจัดกำหนดการระยะสั้นจะแทบไม่ต้องทำอะไรเลย ในทางกลับกัน หากกระบวนการทั้งหมดผูกกับ CPU คิวรอ I/O จะว่างเปล่าเกือบตลอดเวลา อุปกรณ์จะไม่ได้ใช้งาน และระบบจะไม่สมดุลอีกครั้ง ระบบที่มีประสิทธิภาพดีที่สุดจะมีการผสมผสานระหว่างกระบวนการที่ผูกกับ CPU และ I/O ในระบบปฏิบัติการสมัยใหม่ ค่านี้ใช้เพื่อให้แน่ใจว่ากระบวนการตามเวลาจริงจะมีเวลา CPU เพียงพอสำหรับทำงานให้เสร็จ[7]

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

ระบบปฏิบัติการบางระบบอนุญาตให้เพิ่มงานใหม่ได้ก็ต่อเมื่อมั่นใจว่ายังตรงตามกำหนดเวลาทั้งหมดตามเวลาจริง อัลกอริธึมฮิวริสติกเฉพาะที่ใช้โดยระบบปฏิบัติการเพื่อยอมรับหรือปฏิเสธงานใหม่คือกลไกการควบคุมการรับเข้า [8]

กำหนดการระยะกลาง

ตัวจัดกำหนดการระยะกลางจะลบกระบวนการออกจากหน่วยความจำหลักชั่วคราวและวางไว้ในหน่วยความจำรอง (เช่นฮาร์ดดิสก์ไดรฟ์ ) หรือในทางกลับกัน ซึ่งโดยทั่วไปจะเรียกว่า "สลับออก" หรือ "สลับเข้า" (หรือเรียกอีกอย่างว่า " การเพจ อย่างไม่ถูกต้อง) ออก" หรือ "เพจเข้า") ตัวจัดกำหนดการระยะกลางอาจตัดสินใจสลับกระบวนการที่ไม่ได้ใช้งานมาระยะหนึ่ง หรือกระบวนการที่มีลำดับความสำคัญต่ำ หรือกระบวนการที่มีข้อบกพร่องของหน้าบ่อยครั้งหรือกระบวนการที่ใช้หน่วยความจำจำนวนมากเพื่อเพิ่มหน่วยความจำหลักสำหรับกระบวนการอื่น ๆ สลับกระบวนการกลับเข้าไปใหม่ในภายหลังเมื่อมีหน่วยความจำมากขึ้นหรือเมื่อกระบวนการถูกปลดบล็อกและไม่รออีกต่อไป ทรัพยากร [สตอลลิงส์ 396] [สตอลลิงส์ 370]

ในหลายระบบในปัจจุบัน (ที่รองรับการแมปพื้นที่ที่อยู่เสมือนกับที่เก็บข้อมูลสำรองนอกเหนือจากไฟล์ swap) ตัวจัดกำหนดการระยะกลางอาจทำหน้าที่ของตัวจัดกำหนดการระยะยาวได้จริง โดยถือว่าไบนารีเป็น "เปลี่ยนกระบวนการ" ตามระบบ การดำเนินการ ด้วยวิธีนี้ เมื่อจำเป็นต้องใช้เซ็กเมนต์ของไบนารี มันสามารถสลับได้ตามต้องการ หรือ "ขี้เกียจโหลด",[Stallings, 394] เรียกอีกอย่างว่าดีมานด์เพจจิ้

กำหนดการระยะสั้น

ตัวกำหนดตารางเวลาระยะสั้น (หรือที่รู้จักในชื่อตัวกำหนดตารางเวลาของ CPU ) ตัดสินใจว่าจะประมวลผลกระบวนการใดในหน่วยความจำที่พร้อมใช้งาน (จัดสรร CPU) หลังจากนาฬิกาขัดจังหวะ การขัดจังหวะ I/O การเรียกระบบ ปฏิบัติการ หรือรูปแบบอื่น ของสัญญาณ _ ดังนั้นตัวจัดกำหนดการระยะสั้นจึงตัดสินใจจัดกำหนดการได้บ่อยกว่าตัวจัดกำหนดการระยะยาวหรือระยะกลาง การตัดสินใจจัดกำหนดการอย่างน้อยที่สุดจะต้องทำหลังจากการแบ่งเวลาทุกครั้ง และสิ่งเหล่านี้สั้นมาก ตัวกำหนดตารางเวลานี้สามารถยึดเอา เสียก่อนได้หมายความว่าสามารถบังคับให้ลบกระบวนการออกจาก CPU เมื่อตัดสินใจจัดสรร CPU นั้นไปยังกระบวนการอื่นหรือแบบไม่ยึดถือ (เรียกอีกอย่างว่า "สมัครใจ" หรือ "ร่วมมือ") ซึ่งในกรณีนี้ตัวกำหนดตารางเวลาไม่สามารถทำได้ เพื่อ "บังคับ" ประมวลผลออกจาก CPU

ตัวจัดกำหนดการแบบยึดเอาเสียก่อนอาศัยตัวจับเวลาแบบช่วงเวลาที่ตั้งโปรแกรม ได้ ซึ่งเรียกใช้ตัวจัดการการขัดจังหวะที่ทำงานในโหมดเคอร์เนลและใช้ฟังก์ชันการจัดกำหนดการ

เจ้าหน้าที่จัดส่ง

องค์ประกอบอื่นที่เกี่ยวข้องกับฟังก์ชันการตั้งเวลา CPU คือโปรแกรมเลือกจ่ายงาน ซึ่งเป็นโมดูลที่ให้การควบคุม CPU กับกระบวนการที่เลือกโดยตัวจัดกำหนดการระยะสั้น ได้รับการควบคุมในโหมดเคอร์เนลอันเป็นผลมาจากการขัดจังหวะหรือการเรียกระบบ หน้าที่ของผู้มอบหมายงานเกี่ยวข้องกับสิ่งต่อไปนี้:

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

โปรแกรมเลือกจ่ายงานควรเร็วที่สุดเท่าที่เป็นไปได้ เนื่องจากจะมีการเรียกใช้งานทุกครั้งที่สลับกระบวนการ ในระหว่างการสลับบริบท ตัวประมวลผลจะไม่ได้ใช้งานจริงเพียงเสี้ยวเวลา ดังนั้นควรหลีกเลี่ยงการสลับบริบทที่ไม่จำเป็น เวลาที่ใช้ในการส่งผู้มอบหมายงานเพื่อหยุดกระบวนการหนึ่งและเริ่มกระบวนการอื่นเรียกว่าเวลาแฝง ใน การ จัดส่ง [7] : 155 

สาขาวิชากำหนดการ

ระเบียบวินัยการจัดกำหนดการ ( เรียกอีกอย่างว่านโยบายการจัด กำหนดการ หรืออัลกอริธึมการจัดกำหนดการ ) เป็นอัลกอริธึมที่ใช้สำหรับแจกจ่ายทรัพยากรระหว่างฝ่ายต่างๆ ซึ่งร้องขอพร้อมกันและไม่พร้อมกัน สาขาวิชาการตั้งเวลาใช้ในเราเตอร์ (เพื่อจัดการการรับส่งข้อมูลแพ็คเก็ต) เช่นเดียวกับในระบบปฏิบัติการ (เพื่อแบ่งเวลา CPUระหว่างทั้งเธรดและกระบวนการ ), ดิสก์ไดรฟ์ ( การตั้งเวลา I/O ), เครื่องพิมพ์ ( ตัวจัดคิวงานพิมพ์ ) ระบบฝังตัวส่วนใหญ่ ฯลฯ .

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

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

อัลกอริธึมการจัดตารางเวลาที่ใช้ความพยายามอย่างดีที่สุดที่ง่ายที่สุดคือRound-robinการจัดคิวที่ยุติธรรม ( อัลกอริธึมการจัดตารางเวลาที่ยุติธรรมสูงสุดขั้นต่ำ ) การจัดตารางเวลา ตามสัดส่วนและปริมาณ งาน สูงสุด หากมีการเสนอบริการที่แตกต่างหรือรับประกันคุณภาพแทนที่จะใช้การสื่อสารอย่างดีที่สุดอาจใช้ การจัดคิวที่ถ่วงน้ำหนัก

ในเครือข่ายไร้สายวิทยุแพ็คเก็ตขั้นสูง เช่นระบบเซลลูลาร์3.5G HSDPA (การเข้าถึงดาวน์ลิงก์ความเร็วสูง) การตั้งเวลาขึ้นอยู่กับช่องสัญญาณอาจใช้เพื่อใช้ประโยชน์จากข้อมูลสถานะช่องสัญญาณ หากเงื่อนไขของช่องสัญญาณเป็นที่น่าพอใจปริมาณ งาน และประสิทธิภาพของสเปกตรัมของระบบอาจเพิ่มขึ้น ในระบบที่ล้ำหน้ากว่านั้น เช่นLTEการตั้งเวลาจะรวมกันโดยการจัดสรรช่องสัญญาณแบบไดนามิกแบบ แพ็คเก็ตต่อแพ็กเก็ตที่ขึ้นกับช่อง หรือโดยการกำหนดOFDMAผู้ให้บริการหลายรายหรือ ส่วนประกอบ การทำให้เท่าเทียมกันในโดเมนความถี่ อื่นๆ ให้กับผู้ใช้ที่สามารถใช้งานได้ดีที่สุด[9]

มาก่อนได้ก่อน

กลุ่ม เธรดตัวอย่าง(กล่องสีเขียว) พร้อมคิว (FIFO) ของงานรอ (สีน้ำเงิน) และคิวของงานที่เสร็จสมบูรณ์ (สีเหลือง)

เข้าก่อนออก ก่อน ( FIFO ) หรือที่เรียกว่ามาก่อนได้ก่อน (FCFS) เป็นอัลกอริทึมการจัดตารางเวลาที่ง่ายที่สุด FIFO จะจัดคิวกระบวนการตามลำดับที่มาถึงในคิวที่พร้อม ซึ่งมักใช้สำหรับ aคิวงานเช่น ดังแสดงในหัวข้อนี้

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

การจัดลำดับความสำคัญ

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

เวลาที่เหลือสั้นที่สุดก่อน

คล้ายกับ งานที่ สั้นที่สุดก่อน (SJF) ด้วยกลยุทธ์นี้ ตัวจัดกำหนดการจะจัดการกระบวนการโดยเหลือเวลาการประมวลผลโดยประมาณน้อยที่สุดที่เหลืออยู่ในคิว สิ่งนี้ต้องการความรู้ขั้นสูงหรือการประมาณค่าเกี่ยวกับเวลาที่จำเป็นสำหรับกระบวนการให้เสร็จสมบูรณ์

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

การจัดกำหนดการล่วงหน้าที่มีลำดับความสำคัญคงที่

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

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

กำหนดการแบบ Round-robin

ตัวจัดกำหนดการจะกำหนดหน่วยเวลาคงที่ต่อกระบวนการ และหมุนเวียนไปตามนั้น หากกระบวนการเสร็จสิ้นภายในการแบ่งเวลานั้น จะถูกยกเลิก มิฉะนั้น จะถูกจัดกำหนดการใหม่หลังจากให้โอกาสกับกระบวนการอื่นๆ ทั้งหมด

  • การจัดกำหนดการ RR เกี่ยวข้องกับค่าใช้จ่ายที่กว้างขวาง โดยเฉพาะอย่างยิ่งกับหน่วยเวลาขนาดเล็ก
  • ปริมาณงานที่สมดุลระหว่าง FCFS/ FIFO และ SJF/SRTF งานที่สั้นกว่าจะเสร็จเร็วกว่าใน FIFO และกระบวนการที่ยาวกว่าจะเสร็จเร็วกว่าใน SJF
  • เวลาตอบสนองโดยเฉลี่ยที่ดี เวลารอขึ้นอยู่กับจำนวนกระบวนการ ไม่ใช่ระยะเวลาเฉลี่ยของกระบวนการ
  • เนื่องจากมีเวลารอสูง จึงไม่ตรงตามกำหนดเวลาในระบบ RR ที่บริสุทธิ์
  • ความอดอยากไม่สามารถเกิดขึ้นได้ เนื่องจากไม่มีการให้ความสำคัญ ลำดับของการจัดสรรหน่วยเวลาขึ้นอยู่กับเวลาที่มาถึงของกระบวนการ ซึ่งคล้ายกับ FIFO
  • หาก Time-Slice มีขนาดใหญ่ จะกลายเป็น FCFS /FIFO หรือหากสั้นก็จะกลายเป็น SJF/SRTF

การจัดตารางคิวหลายระดับ

ใช้สำหรับสถานการณ์ที่กระบวนการแบ่งออกเป็นกลุ่มต่างๆ ได้ง่าย ตัวอย่างเช่น มีการแบ่งส่วนร่วมกันระหว่างกระบวนการเบื้องหน้า (เชิงโต้ตอบ) และกระบวนการเบื้องหลัง (แบทช์) กระบวนการทั้งสองประเภทนี้มีข้อกำหนดด้านเวลาตอบสนองที่แตกต่างกัน ดังนั้นจึงอาจมีความต้องการด้านการจัดกำหนดการที่แตกต่างกัน มีประโยชน์มากสำหรับปัญหา หน่วยความจำ ที่ใช้ร่วมกัน

ตัวกำหนดตารางเวลาการอนุรักษ์งาน

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

ปัญหาการเพิ่มประสิทธิภาพการจัดกำหนดการ

มีปัญหาการตั้งเวลาหลายอย่างซึ่งเป้าหมายคือการตัดสินใจว่างานใดจะไปที่สถานีใดในเวลาใด ซึ่งจะทำให้makespan ทั้งหมด ลดลง:

  • การจัดตารางเวลาร้านงาน  – มีnงานและmสถานีที่เหมือนกัน แต่ละงานควรดำเนินการในเครื่องเดียว ซึ่งมักจะถือเป็นปัญหาออนไลน์
  • กำหนดการเปิดร้าน  – มีnงานและmสถานีที่แตกต่างกัน งานแต่ละงานควรใช้เวลาพอสมควรในแต่ละสถานีในการสั่งซื้อฟรี
  • Flow shop scheduling  – มีnงานและmสถานีต่างกัน งานแต่ละงานควรใช้เวลาพอสมควรในแต่ละสถานีตามลำดับที่กำหนดไว้ล่วงหน้า

การจัดตารางเวลาด้วยตนเอง

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

  • หมดปัญหาขาดแคลนทรัพยากร
  • คาดการณ์ได้สูงมาก อนุญาตให้ใช้ระบบเรียลไทม์แบบฮาร์ด
  • แทบไม่มีค่าโสหุ้ย
  • อาจไม่เหมาะกับทุกการใช้งาน
  • ประสิทธิผลขึ้นอยู่กับการนำไปปฏิบัติโดยสมบูรณ์

การเลือกอัลกอริธึมการตั้งเวลา

เมื่อออกแบบระบบปฏิบัติการ โปรแกรมเมอร์ต้องพิจารณาว่าอัลกอริธึมการจัดตารางเวลาใดจะทำงานได้ดีที่สุดสำหรับการใช้งานที่ระบบจะได้เห็น ไม่มีอัลกอริธึมการจัดตารางเวลาที่ "ดีที่สุด" สากล และระบบปฏิบัติการจำนวนมากใช้อัลกอริธึมการตั้งเวลาแบบขยายหรือรวมกันด้านบน

ตัวอย่างเช่นWindows NT /XP/Vista ใช้คิวคำติชมแบบหลายระดับซึ่งเป็นการรวมกันของการจัดกำหนดการที่มีลำดับความสำคัญคงที่ การปัดเศษ และอัลกอริธึมเข้าก่อนออกก่อน ในระบบนี้ เธรดสามารถเพิ่มหรือลดลำดับความสำคัญแบบไดนามิกได้ ขึ้นอยู่กับว่าเธรดได้รับการบริการแล้วหรือรอนานมากหรือไม่ ทุกระดับความสำคัญจะแสดงด้วยคิวของตัวเอง โดยมีการจัดกำหนดการแบบ วนซ้ำ ระหว่างเธรดที่มีลำดับความสำคัญสูงและFIFOในหมู่ผู้ที่มีลำดับความสำคัญต่ำกว่า ในแง่นี้ เวลาตอบสนองสั้นสำหรับเธรดส่วนใหญ่ และเธรดของระบบที่สั้นแต่สำคัญจะเสร็จสิ้นอย่างรวดเร็ว เนื่องจากเธรดสามารถใช้หน่วยเวลาของ round-robin ได้เพียงครั้งเดียวในคิวที่มีลำดับความสำคัญสูงสุด ความอดอยากอาจเป็นปัญหาสำหรับเธรดที่มีลำดับความสำคัญสูงอีกต่อไป

การใช้งานตัวกำหนดตารางเวลากระบวนการของระบบปฏิบัติการ

อัลกอริธึมที่ใช้อาจจะง่ายพอๆ กับRound-robinซึ่งแต่ละกระบวนการจะได้รับเวลาเท่ากัน (เช่น 1 ms โดยปกติระหว่าง 1 ms ถึง 100 ms) ในรายการการวน ดังนั้น กระบวนการ A จะดำเนินการเป็นเวลา 1 มิลลิวินาที จากนั้นจึงประมวลผล B จากนั้นจึงดำเนินการ C จากนั้นกลับไปที่กระบวนการ A

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

OS/360 และผู้สืบทอด

IBM OS/360พร้อมใช้งานกับตัวกำหนดตารางเวลาที่แตกต่างกันสามตัว ความแตกต่างดังกล่าวมักถูกมองว่าเป็นระบบปฏิบัติการที่แตกต่างกันสามระบบ:

  • ตัว เลือก Single Sequential Schedulerหรือที่เรียกว่าPrimary Control Program (PCP)ให้การดำเนินการตามลำดับของงานสตรีมเดียว
  • ตัว เลือก Multiple Sequential Schedulerหรือที่เรียกว่าMultiprogramming with a Fixed Number of Tasks (MFT)ให้การทำงานพร้อมกันหลายงาน การดำเนินการถูกควบคุมโดยลำดับความสำคัญซึ่งมีค่าเริ่มต้นสำหรับแต่ละสตรีมหรือสามารถขอแยกกันสำหรับแต่ละงาน MFT เวอร์ชัน II เพิ่มงานย่อย (เธรด) ซึ่งดำเนินการตามลำดับความสำคัญตามงานหลัก สตรีมงานแต่ละรายการกำหนดจำนวนหน่วยความจำสูงสุดที่งานในสตรีมนั้นสามารถใช้ได้
  • ตัว เลือก Multiple Priority SchedulersหรือMultiprogramming with a Variable Number of Tasks (MVT)ซึ่งเป็นงานย่อยที่มีคุณลักษณะตั้งแต่เริ่มต้น แต่ละงานร้องขอลำดับความสำคัญและหน่วยความจำที่จำเป็นก่อนดำเนินการ

MVS เวอร์ชันหน่วยเก็บข้อมูลเสมือนในภายหลังได้เพิ่ม คุณลักษณะ Workload Managerให้กับตัวจัดกำหนดการ ซึ่งจัดกำหนดการทรัพยากรตัวประมวลผลตามรูปแบบที่ซับซ้อนซึ่งกำหนดโดยการติดตั้ง

วินโดว์

ระบบ MS-DOS และ Microsoft Windows รุ่น แรกๆ นั้นไม่ใช่มัลติทาสก์ ดังนั้นจึงไม่มีตัวกำหนดตารางเวลา Windows 3.1xใช้ตัวกำหนดตารางเวลาแบบไม่ยึดเอาเสียก่อน ซึ่งหมายความว่าจะไม่ขัดจังหวะโปรแกรม มันอาศัยโปรแกรมเพื่อยุติหรือบอกระบบปฏิบัติการว่าไม่ต้องการโปรเซสเซอร์เพื่อที่จะสามารถไปยังกระบวนการอื่นได้ ซึ่งมักจะเรียกว่าการทำงานหลายอย่างพร้อมกันแบบร่วมมือกัน Windows 95 แนะนำตัวกำหนดตารางเวลาเชิงป้องกันเบื้องต้น อย่างไรก็ตาม สำหรับการสนับสนุนแบบเดิมเลือกที่จะให้แอปพลิเคชัน 16 บิตทำงานโดยไม่มีการสำรองล่วงหน้า [10]

ระบบปฏิบัติการที่ใช้ Windows NTใช้คิวคำติชมหลายระดับ มีการกำหนดระดับความสำคัญ 32 ระดับ ตั้งแต่ 0 ถึง 31 โดยที่ระดับความสำคัญ 0 ถึง 15 เป็นลำดับความสำคัญ "ปกติ" และระดับความสำคัญ 16 ถึง 31 เป็นระดับความสำคัญแบบเรียลไทม์แบบซอฟต์ ซึ่งต้องใช้สิทธิ์ในการกำหนด 0 สงวนไว้สำหรับระบบปฏิบัติการ ส่วนต่อประสานผู้ใช้และ API ทำงานกับคลาสลำดับความสำคัญสำหรับกระบวนการและเธรดในกระบวนการ ซึ่งระบบจะรวมเข้ากับระดับความสำคัญสัมบูรณ์

เคอร์เนลอาจเปลี่ยนระดับความสำคัญของเธรดขึ้นอยู่กับการใช้งาน I/O และ CPU และไม่ว่าจะเป็นแบบโต้ตอบ (เช่น ยอมรับและตอบสนองต่ออินพุตจากมนุษย์) เพิ่มลำดับความสำคัญของกระบวนการแบบโต้ตอบและ I/O ที่มีขอบเขต และลดระดับของ กระบวนการที่ผูกกับ CPU เพื่อเพิ่มการตอบสนองของแอปพลิเคชันแบบโต้ตอบ [11]ตัวกำหนดเวลาได้รับการแก้ไขในWindows Vistaเพื่อใช้ตัวนับรอบของโปรเซสเซอร์ที่ทันสมัยเพื่อติดตามจำนวนรอบของ CPU ที่เธรดดำเนินการ มากกว่าแค่การใช้รูทีนการขัดจังหวะตัวจับเวลาแบบช่วงเวลา [12] Vista ยังใช้ตัวจัดกำหนดการลำดับความสำคัญสำหรับคิว I/O เพื่อให้ตัวจัดเรียงข้อมูลบนดิสก์และโปรแกรมอื่นๆ ดังกล่าวไม่รบกวนการทำงานเบื้องหน้า [13]

Mac OS แบบคลาสสิกและ macOS

Mac OS 9 ใช้การจัดกำหนดการแบบร่วมมือสำหรับเธรด โดยที่กระบวนการหนึ่งควบคุมเธรดที่ทำงานร่วมกันหลายรายการ และยังจัดเตรียมการตั้งเวลาล่วงหน้าสำหรับงานที่มีการประมวลผลหลายตัว เคอร์เนลจัดกำหนดการงานการประมวลผลหลายตัวโดยใช้อัลกอริธึมการจัดกำหนดการชั่วคราว กระบวนการตัวจัดการกระบวนการทั้งหมดทำงานภายในงานการประมวลผลหลายตัวพิเศษ เรียกว่า "งานสีน้ำเงิน" กระบวนการเหล่านั้นถูกจัดกำหนดการร่วมกันโดยใช้อัลกอริธึมการจัดกำหนดการแบบวนซ้ำ กระบวนการให้ผลการควบคุมของตัวประมวลผลไปยังกระบวนการอื่นโดยเรียกใช้ฟังก์ชันการบล็อกWaitNextEvent อย่าง ชัดเจนเช่น แต่ละกระบวนการมีสำเนาของตัวเองของThread Managerซึ่งจัดกำหนดการเธรดของกระบวนการนั้นอย่างร่วมมือกัน เธรดให้การควบคุมตัวประมวลผลไปยังเธรดอื่นโดยเรียกYieldToAnyThreadหรือYieldToThread. [14]

macOS ใช้คิวความคิดเห็นแบบหลายระดับ โดยมีสี่แถบลำดับความสำคัญสำหรับเธรด – ปกติ ลำดับความสำคัญสูงของระบบ โหมดเคอร์เนลเท่านั้น และแบบเรียลไทม์ [15]เธรดถูกกำหนดไว้ชั่วคราว macOS ยังสนับสนุนเธรดที่กำหนดเวลาร่วมกันในการใช้งาน Thread Manager ในCarbon [14]

เอไอเอ

ใน AIX เวอร์ชัน 4 มีค่าที่เป็นไปได้สามค่าสำหรับนโยบายการกำหนดตารางเวลาของเธรด:

  • เข้าก่อนออกก่อน: เมื่อกำหนดเวลาเธรดที่มีนโยบายนี้แล้ว เธรดจะทำงานจนเสร็จเว้นแต่จะถูกบล็อก ยินยอมให้ควบคุม CPU หรือส่งเธรดที่มีลำดับความสำคัญสูงกว่าได้ เฉพาะเธรดที่มีลำดับความสำคัญคงที่เท่านั้นที่สามารถมีนโยบายการจัดกำหนดการ FIFO
  • Round Robin: สิ่งนี้คล้ายกับโครงร่างการปัดเศษของตัวจัดกำหนดการ AIX เวอร์ชัน 3 โดยอิงตามการแบ่งเวลา 10 ms เมื่อเธรด RR มีการควบคุมที่ส่วนท้ายของการแบ่งเวลา เธรดจะย้ายไปยังส่วนท้ายของคิวของเธรดที่จัดส่งได้ที่มีลำดับความสำคัญ เฉพาะเธรดที่มีลำดับความสำคัญคงที่เท่านั้นที่สามารถมีนโยบายการจัดกำหนดการ Round Robin
  • อื่นๆ: นโยบายนี้กำหนดโดย POSIX1003.4a ตามที่กำหนดไว้ในการดำเนินการ ใน AIX เวอร์ชัน 4 นโยบายนี้ถูกกำหนดให้เทียบเท่ากับ RR ยกเว้นว่าใช้กับเธรดที่มีลำดับความสำคัญที่ไม่คงที่ การคำนวณค่าลำดับความสำคัญของเธรดที่ทำงานอยู่ใหม่ทุกครั้งที่มีการขัดจังหวะสัญญาณนาฬิกา หมายความว่าเธรดอาจสูญเสียการควบคุมเนื่องจากค่าลำดับความสำคัญสูงกว่าค่าของเธรดที่จัดส่งได้อื่น นี่คือลักษณะการทำงานของ AIX เวอร์ชัน 3

เธรดเป็นที่สนใจของแอปพลิเคชันซึ่งปัจจุบันประกอบด้วยกระบวนการแบบอะซิงโครนัสหลายขั้นตอน แอปพลิเคชันเหล่านี้อาจกำหนดให้ระบบมีภาระงานที่เบากว่า หากแปลงเป็นโครงสร้างแบบมัลติเธรด

AIX 5 ใช้นโยบายการจัดกำหนดการต่อไปนี้: FIFO, round robin และ fair round robin นโยบาย FIFO มีการใช้งานที่แตกต่างกันสามแบบ: FIFO, FIFO2 และ FIFO3 นโยบาย Round robin ชื่อ SCHED_RR ใน AIX และ robin ที่ยุติธรรมเรียกว่า SCHED_OTHER [16]

ลินุกซ์

โครงสร้างที่ง่ายมากของเคอร์เนล Linux ซึ่งรวมถึงตัวกำหนดเวลากระบวนการ ตัวกำหนดตารางเวลา I/O และตัวกำหนดตารางเวลาแพ็กเก็ต

ลินุกซ์ 2.4

ในLinux 2.4 ใช้ตัวจัดกำหนดการ O(n)ที่มีคิวคำติชมหลายระดับ ที่มีระดับความ สำคัญตั้งแต่ 0 ถึง 140 0–99 สงวนไว้สำหรับงานแบบเรียลไทม์และ 100–140 ถือเป็นระดับงานที่ดี สำหรับงานแบบเรียลไทม์ ควอนตัมเวลาสำหรับกระบวนการสลับอยู่ที่ประมาณ 200 มิลลิวินาที และสำหรับงานที่ดีประมาณ 10 มิลลิวินาที [ จำเป็นต้องอ้างอิง ]ตัวจัดกำหนดการวิ่งผ่านคิวการรันของกระบวนการที่พร้อมใช้งานทั้งหมด ปล่อยให้กระบวนการที่มีลำดับความสำคัญสูงสุดไปก่อนและรันผ่านไทม์สไลซ์ หลังจากนั้น จะถูกวางในคิวที่หมดอายุ เมื่อคิวที่ใช้งานอยู่ว่างเปล่า คิวที่หมดอายุจะกลายเป็นคิวที่ใช้งานอยู่และในทางกลับกัน

อย่างไรก็ตามลีนุกซ์รุ่น องค์กรบางรุ่น เช่นSUSE Linux Enterprise Serverแทนที่ตัวกำหนดตารางเวลานี้ด้วยแบ็คพอร์ตของตัวจัดกำหนดการ O(1) (ซึ่งดูแลโดยAlan Coxในซีรีส์เคอร์เนล Linux 2.4-ac ของเขา) เป็นเคอร์เนล Linux 2.4 ที่ใช้โดยการกระจาย .

Linux 2.6.0 ถึง Linux 2.6.22

ในเวอร์ชัน 2.6.0 ถึง 2.6.22 เคอร์เนลใช้ตัวกำหนดตารางเวลา O(1)ที่พัฒนาโดยIngo Molnarและผู้พัฒนาเคอร์เนลอื่นๆ อีกจำนวนมากในระหว่างการพัฒนา Linux 2.5 สำหรับเคอร์เนลจำนวนมากในกรอบเวลาCon Kolivasได้พัฒนาชุดโปรแกรมแก้ไขซึ่งปรับปรุงการโต้ตอบกับตัวกำหนดเวลานี้ หรือแม้แต่แทนที่ด้วยตัวกำหนดตารางเวลาของเขาเอง

ตั้งแต่ Linux 2.6.23

งานของ Con Kolivas ซึ่งสำคัญที่สุดในการใช้ " กำหนดเวลาที่ยุติธรรม " ที่ชื่อว่า "Rotating Staircase Deadline" เป็นแรงบันดาลใจให้ Ingo Molnár พัฒนาCompletely Fair Schedulerแทนตัว กำหนดตารางเวลา O(1) รุ่นก่อนหน้า โดยให้เครดิตกับ Kolivas ในประกาศของเขา [17] CFS เป็นการดำเนินการครั้งแรกของตัว กำหนดตารางเวลากระบวนการ เข้าคิวที่ยุติธรรม ซึ่ง ใช้กันอย่างแพร่หลายในระบบปฏิบัติการทั่วไป [18]

Completely Fair Scheduler (CFS) ใช้อัลกอริธึมการจัดตารางเวลาแบบคลาสสิกที่ได้รับการศึกษามาเป็นอย่างดีซึ่งเรียกว่าการจัดคิวที่ยุติธรรมซึ่งเดิมคิดค้นขึ้นสำหรับเครือข่ายแพ็คเก็ก่อนหน้านี้ Fair Queuing ถูกนำไปใช้กับการจัดกำหนดการ CPU ภายใต้ชื่อstride scheduling ตัวกำหนดตารางเวลา CFS ของการจัดคิวที่ยุติธรรมมีความซับซ้อนในการจัดกำหนดการของ, ที่ไหนคือจำนวนงานในรันคิว การเลือกงานสามารถทำได้ในเวลาคงที่ แต่การแทรกงานกลับเข้าไปใหม่หลังจากรันแล้วจำเป็นต้องมีการดำเนินการ เนื่องจากคิวการรันถูกนำไปใช้เป็นต้นไม้สีแดง-ดำ

Brain Fuck Schedulerซึ่งสร้างโดย Con Kolivas เป็นทางเลือกแทน CFS

FreeBSD

FreeBSDใช้คิวความคิดเห็นแบบหลายระดับที่มีลำดับความสำคัญตั้งแต่ 0-255 0–63 สงวนไว้สำหรับการขัดจังหวะ 64–127 สำหรับครึ่งบนของเคอร์เนล 128–159 สำหรับเธรดผู้ใช้แบบเรียลไทม์ 160–223 สำหรับเธรดผู้ใช้ที่แบ่งเวลา และ 224–255 สำหรับเธรดผู้ใช้ที่ไม่ได้ใช้งาน เช่นเดียวกับ Linux จะใช้การตั้งค่าคิวที่ใช้งานอยู่ แต่ก็มีคิวที่ไม่ได้ใช้งานด้วยเช่นกัน (19)

NetBSD

NetBSDใช้คิวความคิดเห็นแบบหลายระดับที่มีลำดับความสำคัญตั้งแต่ 0–223 0–63 สงวนไว้สำหรับเธรดที่แบ่งเวลา (ค่าเริ่มต้น, นโยบาย SCHED_OTHER), 64–95 สำหรับเธรดผู้ใช้ที่เข้าสู่พื้นที่เคอร์เนล , 96-128 สำหรับเธรดเคอร์เนล, 128–191 สำหรับเธรดแบบเรียลไทม์ของผู้ใช้ (นโยบาย SCHED_FIFO และ SCHED_RR) และ 192–223 สำหรับการขัดจังหวะของ ซอฟต์แวร์

โซลาริส

Solarisใช้คิวความคิดเห็นหลายระดับที่มีลำดับความสำคัญตั้งแต่ 0 ถึง 169 ลำดับความสำคัญ 0–59 สงวนไว้สำหรับเธรดที่แบ่งเวลา 60–99 สำหรับเธรดของระบบ 100–159 สำหรับเธรดแบบเรียลไทม์ และ 160–169 สำหรับการขัดจังหวะที่มีลำดับความสำคัญต่ำ . ต่างจากลินุกซ์[19]เมื่อกระบวนการเสร็จสิ้นโดยใช้ควอนตัมเวลา จะได้รับการจัดลำดับความสำคัญใหม่และใส่กลับเข้าไปในคิว Solaris 9 เปิดตัวคลาสการจัดตารางเวลาใหม่ 2 คลาส ได้แก่ คลาสที่มีลำดับความสำคัญคงที่และคลาสแชร์ที่ยุติธรรม เธรดที่มีลำดับความสำคัญคงที่จะมีช่วงลำดับความสำคัญเดียวกันกับคลาสการแบ่งเวลา แต่ลำดับความสำคัญจะไม่ถูกปรับแบบไดนามิก คลาสการจัดตารางเวลาที่ยุติธรรมใช้การ แชร์ CPUเพื่อจัดลำดับความสำคัญของเธรดสำหรับการตัดสินใจกำหนดเวลา การแชร์ CPU บ่งบอกถึงสิทธิ์ในทรัพยากรของ CPU พวกเขาถูกจัดสรรให้กับชุดของกระบวนการซึ่งเรียกรวมกันว่าโครงการ [7]

สรุป

ระบบปฏิบัติการ Preemption อัลกอริทึม
Amiga OS ใช่ การจัดกำหนดการแบบวนรอบลำดับความสำคัญ
FreeBSD ใช่ คิวความคิดเห็นหลายระดับ
เคอร์เนล Linuxก่อน 2.6.0 ใช่ คิวความคิดเห็นหลายระดับ
เคอร์เนล Linux 2.6.0–2.6.23 ใช่ O(1) ตัวกำหนดตารางเวลา
เคอร์เนล Linux หลัง 2.6.23 ใช่ ตัวกำหนดตารางเวลาที่ยุติธรรมอย่างสมบูรณ์
Mac OS แบบคลาสสิกก่อน-9 ไม่มี กำหนดการสหกรณ์
Mac OS 9 บาง ตัวจัดกำหนดการชั่วคราวสำหรับงาน MP และความร่วมมือสำหรับกระบวนการและเธรด
macOS ใช่ คิวความคิดเห็นหลายระดับ
NetBSD ใช่ คิวความคิดเห็นหลายระดับ
Solaris ใช่ คิวความคิดเห็นหลายระดับ
Windows 3.1x ไม่มี กำหนดการสหกรณ์
Windows 95 , 98 , ฉัน ครึ่ง ตัวจัดกำหนดการชั่วคราวสำหรับกระบวนการ 32 บิต และความร่วมมือสำหรับกระบวนการ 16 บิต
Windows NT (รวมถึง 2000, XP, Vista, 7 และเซิร์ฟเวอร์) ใช่ คิวความคิดเห็นหลายระดับ

ดูเพิ่มเติม

หมายเหตุ

  1. ^ ซีแอล หลิว; James W. , Layland (มกราคม 2516) "อัลกอริธึมการตั้งเวลาสำหรับ Multiprogramming ในสภาพแวดล้อมแบบ Hard-Real-Time" วารสาร อสม . อสม. 20 (1): 46–61. ดอย : 10.1145/321738.321743 . S2CID  207669821 . เรากำหนดเวลาตอบสนองของคำขอสำหรับงานบางอย่างให้เป็นช่วงเวลาระหว่างคำขอและจุดสิ้นสุดของการตอบสนองต่อคำขอนั้น
  2. ไคลน์ร็อก, ลีโอนาร์ด (1976). ระบบการจัดคิว ฉบับที่. 2: โปรแกรมคอมพิวเตอร์ (1 ed.) Wiley-Interscience. หน้า 171 . ISBN 047149111X. สำหรับลูกค้าที่ต้องการบริการ x วินาที เวลาตอบสนองของเขาจะเท่ากับเวลาให้บริการ x บวกกับเวลารอของเขา
  3. ^ Feitelson, Dror G. (2015). แบบจำลองปริมาณงานสำหรับการประเมินประสิทธิภาพของระบบคอมพิวเตอร์ สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. มาตรา 8.4 (หน้า 422) ในเวอร์ชัน 1.03 ของต้นฉบับที่หาอ่านได้ฟรี ISBN 9781107078239. สืบค้นเมื่อ2015-10-17 . หากเราระบุเวลาที่งานรออยู่ในคิวโดย t wและเวลาที่ทำงานจริงโดย t r เวลาตอบสนองคือ r = t w + t r
  4. ซิลเบอร์ชาตซ์, อับราฮัม; กัลวิน, ปีเตอร์ แบร์; แก๊ก, เกร็ก (2012). แนวคิดระบบปฏิบัติการ (ฉบับที่ 9) สำนักพิมพ์ไวลีย์. หน้า 187. ISBN 978-0470128725. ในระบบโต้ตอบ เวลาตอบสนองอาจไม่ใช่เกณฑ์ที่ดีที่สุด บ่อยครั้ง กระบวนการสามารถให้ผลลัพธ์ได้ค่อนข้างเร็ว และสามารถคำนวณผลลัพธ์ใหม่ต่อไปในขณะที่ผลลัพธ์ก่อนหน้าจะส่งไปยังผู้ใช้ ดังนั้น การวัดอื่นคือเวลาตั้งแต่ยื่นคำร้องจนถึงการตอบสนองครั้งแรก การวัดนี้เรียกว่าเวลาตอบสนอง คือเวลาที่ใช้ในการเริ่มตอบสนอง ไม่ใช่เวลาที่ใช้ในการส่งออกการตอบสนอง
  5. พอล คริสซานอฟสกี้ (2014-02-19). "การจัดตารางกระบวนการ: ใครจะได้ดำเนินการต่อไป" . cs.rutgers.edu _ สืบค้นเมื่อ2015-01-11 .
  6. ^ ราฟาเอล ฟิ งเคิล . "ระบบปฏิบัติการ Vade Mecum " ศิษย์ฮอลล์. 2531 "บทที่ 2: การบริหารเวลา" หน้า 27.
  7. a b c Abraham Silberschatz , Peter Baer Galvin and Greg Gagne (2013). แนวคิดระบบปฏิบัติการ . ฉบับที่ 9. John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.{{cite book}}: CS1 maint: ใช้พารามิเตอร์ผู้เขียน ( ลิงค์ )
  8. โรเบิร์ต โครเกอร์ (2004). "การควบคุมการรับสมัครสำหรับแอปพลิเคชันเรียลไทม์ที่เขียนโดยอิสระ " ยูดับเบิลยูสเปซ http://hdl.handle.net/10012/1170 _ ส่วน "2.6 การควบคุมการรับเข้า" หน้า 33.
  9. ^ กัววัง เหมียว ; เจนส์ แซนเดอร์; กีวอนซัง; เบน สลิมาน (2016). พื้นฐานของเครือข่ายข้อมูลมือถือ สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ . ISBN 978-1107143210.
  10. ^ Windows รุ่นแรกที่เครื่อง Wayback (ดัชนีเก็บถาวร)
  11. ^ ศรีราม กฤษณะ. "เรื่องราวของตัวกำหนดตารางเวลาสองตัว Windows NT และ Windows CE" . เก็บจากต้นฉบับเมื่อ 22 กรกฎาคม 2555
  12. ^ "การดูแลระบบ Windows: ภายในเคอร์เนล Windows Vista: ส่วนที่ 1 " Technet.microsoft.com . 2016-11-14 . สืบค้นเมื่อ2016-12-09 .
  13. ^ "สำเนาที่เก็บถาวร" . บล็อก . gabefrost.com เก็บถาวรจากต้นฉบับเมื่อ 19 กุมภาพันธ์ 2551 . สืบค้นเมื่อ15 มกราคม 2022 .{{cite web}}: CS1 maint: สำเนาที่เก็บถาวรเป็นชื่อ ( ลิงก์ )
  14. ^ a b "หมายเหตุทางเทคนิค TN2028: สถาปัตยกรรมการทำเกลียว " developer.apple.com ครับ สืบค้นเมื่อ2019-01-15 .
  15. ^ "Mach Scheduling และ Thread Interfaces" . developer.apple.com ครับ สืบค้นเมื่อ2019-01-15 .
  16. ^ [1] เก็บถาวร 2011-08-11 ที่ Wayback Machine
  17. โมลนาร์, อินโก (2007-04-13). "[แพทช์] ตัวกำหนดตารางเวลาแบบแยกส่วนและตัวกำหนดตารางเวลาที่ยุติธรรมอย่างสมบูรณ์ [CFS] " linux-kernel (รายชื่อส่งเมล)
  18. ^ ถงลี่; แดน Baumberger; สก็อตต์ ฮาห์น. "การจัดตารางเวลาแฟร์สำหรับโปรเซสเซอร์หลายตัวที่มีประสิทธิภาพและปรับขนาดได้โดยใช้ Round-Robin แบบถ่วงน้ำหนักแบบกระจาย" (PDF ) Happyli.org _ สืบค้นเมื่อ2016-12-09 .
  19. ^ a b "การเปรียบเทียบ Solaris, Linux และ FreeBSD Kernels" (PDF ) เก็บถาวรจากต้นฉบับ(PDF)เมื่อวันที่ 7 สิงหาคม 2551

อ้างอิง

อ่านเพิ่มเติม