ระบบปฏิบัติการเบื้องต้น
สวัสดีฮับ! ฉันอยากจะนำเสนอชุดบทความแปลของวรรณกรรมเรื่องหนึ่งที่น่าสนใจในความคิดเห็นของฉัน - OSTEP เนื้อหานี้จะตรวจสอบการทำงานของระบบปฏิบัติการที่มีลักษณะคล้ายยูนิกซ์อย่างลึกซึ้ง กล่าวคือ การทำงานกับกระบวนการ ตัวกำหนดเวลาต่างๆ หน่วยความจำ และส่วนประกอบอื่น ๆ ที่คล้ายกันซึ่งประกอบเป็นระบบปฏิบัติการสมัยใหม่ คุณสามารถดูต้นฉบับของวัสดุทั้งหมดได้ที่นี่ . โปรดทราบว่าการแปลจัดทำขึ้นอย่างไม่เป็นมืออาชีพ (ค่อนข้างอิสระ) แต่ฉันหวังว่าฉันจะคงความหมายทั่วไปไว้
งานห้องปฏิบัติการในเรื่องนี้สามารถพบได้ที่นี่:
ส่วนอื่น ๆ :
คุณสามารถตรวจสอบช่องของฉันได้ที่ =)
ความรู้เบื้องต้นเกี่ยวกับตัวกำหนดเวลา
สาระสำคัญของปัญหา: วิธีการพัฒนานโยบายตัวกำหนดเวลา
กรอบนโยบายตัวกำหนดตารางเวลาพื้นฐานควรได้รับการออกแบบอย่างไร สมมติฐานที่สำคัญควรเป็นอย่างไร? ตัวชี้วัดใดมีความสำคัญ? เทคนิคพื้นฐานใดบ้างที่ใช้ในระบบคอมพิวเตอร์ยุคแรกๆ
สมมติฐานภาระงาน
ก่อนที่จะหารือเกี่ยวกับนโยบายที่เป็นไปได้ ก่อนอื่นเรามาทำความเข้าใจเกี่ยวกับกระบวนการที่ทำงานอยู่ในระบบให้ง่ายขึ้นก่อน ซึ่งเรียกรวมกันว่า ภาระงาน. การกำหนดปริมาณงานเป็นส่วนสำคัญของการสร้างนโยบาย และยิ่งคุณทราบเกี่ยวกับปริมาณงานมากเท่าใด คุณก็จะเขียนนโยบายได้ดีขึ้นเท่านั้น
เรามาตั้งสมมติฐานต่อไปนี้เกี่ยวกับกระบวนการที่ทำงานอยู่ในระบบ บางครั้งเรียกว่า ตำแหน่งงาน (งาน). สมมติฐานเหล่านี้เกือบทั้งหมดไม่เป็นไปตามความเป็นจริง แต่จำเป็นสำหรับการพัฒนาความคิด
- แต่ละภารกิจดำเนินไปในระยะเวลาเท่ากัน
- งานทั้งหมดถูกตั้งค่าพร้อมกัน
- งานที่ได้รับมอบหมายจะทำงานไปจนเสร็จสิ้น
- งานทั้งหมดใช้เฉพาะ CPU
- ทราบเวลาทำงานของแต่ละงาน
ตัวชี้วัดตัวจัดกำหนดการ
นอกเหนือจากสมมติฐานบางประการเกี่ยวกับโหลดแล้ว ยังจำเป็นต้องมีเครื่องมืออื่นสำหรับการเปรียบเทียบนโยบายการจัดกำหนดการที่แตกต่างกัน: ตัวชี้วัดตัวกำหนดตารางเวลา เมตริกเป็นเพียงการวัดบางสิ่งบางอย่าง มีเมตริกจำนวนหนึ่งที่สามารถใช้เพื่อเปรียบเทียบตัวกำหนดเวลาได้
ตัวอย่างเช่น เราจะใช้หน่วยเมตริกที่เรียกว่า เวลาตอบสนอง (เวลาตอบสนอง) เวลาตอบสนองของงานถูกกำหนดให้เป็นความแตกต่างระหว่างเวลาทำงานให้เสร็จสิ้นและเวลามาถึงของงานในระบบ
Tturnaround=Tcompletion−การมาถึง
เนื่องจากเราถือว่างานทั้งหมดมาถึงในเวลาเดียวกัน ดังนั้น Ta=0 และด้วยเหตุนี้ Tt=Tc ค่านี้จะเปลี่ยนแปลงตามธรรมชาติเมื่อเราเปลี่ยนสมมติฐานข้างต้น
ตัวชี้วัดอื่น - ความเป็นธรรม (ความยุติธรรมความซื่อสัตย์) ผลผลิตและความเป็นธรรมมักขัดแย้งกับคุณลักษณะในการวางแผน ตัวอย่างเช่น ตัวกำหนดเวลาอาจปรับประสิทธิภาพให้เหมาะสม แต่ต้องแลกกับการรอให้งานอื่นทำงาน ดังนั้นจึงลดความเป็นธรรมลง
เข้าก่อนออกก่อน (FIFO)
อัลกอริธึมพื้นฐานที่สุดที่เราสามารถนำมาใช้ได้เรียกว่า FIFO หรือ มาก่อน (เข้า), เสิร์ฟก่อน (ออก). อัลกอริธึมนี้มีข้อดีหลายประการ: ใช้งานง่ายมากและเหมาะกับสมมติฐานทั้งหมดของเราและทำงานได้ค่อนข้างดี
ลองดูตัวอย่างง่ายๆ สมมติว่ามีการตั้งค่างาน 3 งานพร้อมกัน แต่สมมติว่างาน A มาถึงเร็วกว่างานอื่นๆ ทั้งหมดเล็กน้อย ดังนั้นงานดังกล่าวจะปรากฏในรายการดำเนินการก่อนงานอื่นๆ ทั้งหมด เช่นเดียวกับ B ที่สัมพันธ์กับ C สมมติว่าแต่ละงานจะถูกดำเนินการเป็นเวลา 10 วินาที เวลาเฉลี่ยในการทำงานเหล่านี้ให้เสร็จสิ้นในกรณีนี้คือเท่าใด?
โดยการนับค่า - 10+20+30 และหารด้วย 3 เราจะได้เวลาดำเนินการโปรแกรมโดยเฉลี่ยเท่ากับ 20 วินาที
ทีนี้ลองเปลี่ยนสมมติฐานของเราดู โดยเฉพาะอย่างยิ่งสมมติฐานที่ 1 ดังนั้นเราจะไม่ถือว่าแต่ละงานใช้เวลาในการดำเนินการเท่ากันอีกต่อไป FIFO จะดำเนินการอย่างไรในครั้งนี้?
ปรากฎว่าเวลาในการดำเนินการที่แตกต่างกันมีผลกระทบเชิงลบอย่างมากต่อประสิทธิภาพของอัลกอริทึม FIFO สมมติว่างาน A จะใช้เวลา 100 วินาทีในขณะที่ B และ C ยังคงใช้เวลา 10 วินาทีต่องาน
จากรูปจะเห็นได้ว่าเวลาเฉลี่ยของระบบจะเป็น (100+110+120)/3=110 เอฟเฟกต์นี้เรียกว่า เอฟเฟกต์ขบวนรถเมื่อผู้บริโภคระยะสั้นของทรัพยากรจะเข้าคิวตามผู้บริโภคจำนวนมาก มันเหมือนกับการต่อแถวที่ร้านขายของชำเมื่อมีลูกค้าเต็มตะกร้าอยู่ตรงหน้าคุณ วิธีแก้ปัญหาที่ดีที่สุดคือพยายามเปลี่ยนเครื่องบันทึกเงินสดหรือผ่อนคลายและหายใจลึกๆ
งานที่สั้นที่สุดก่อน
เป็นไปได้ไหมที่จะแก้ไขสถานการณ์ที่คล้ายกันด้วยกระบวนการที่มีน้ำหนักมาก? แน่นอน. การวางแผนอีกประเภทหนึ่งเรียกว่างานที่สั้นที่สุดก่อน (เอสเจเอฟ). อัลกอริธึมของมันยังค่อนข้างดั้งเดิม - ตามชื่อที่บ่งบอกว่างานที่สั้นที่สุดจะถูกเปิดตัวก่อนทีละงาน
ในตัวอย่างนี้ ผลลัพธ์ของการรันกระบวนการเดียวกันจะเป็นการปรับปรุงเวลาตอบสนองโดยเฉลี่ยของโปรแกรม และจะเท่ากับ 50 แทน 110ซึ่งดีกว่าเกือบ 2 เท่า
ดังนั้น สำหรับสมมติฐานที่ว่างานทั้งหมดมาถึงในเวลาเดียวกัน อัลกอริธึม SJF ดูเหมือนจะเป็นอัลกอริธึมที่เหมาะสมที่สุด อย่างไรก็ตาม สมมติฐานของเรายังคงดูไม่สมจริง ครั้งนี้เราเปลี่ยนสมมติฐานที่ 2 และคราวนี้ลองจินตนาการว่างานสามารถเกิดขึ้นได้ตลอดเวลา และไม่ใช่ทั้งหมดในเวลาเดียวกัน สิ่งนี้สามารถนำไปสู่ปัญหาอะไรได้บ้าง?
ลองจินตนาการว่างาน A (100c) มาถึงก่อนและเริ่มดำเนินการ ที่ t=10 งาน B และ C มาถึง แต่ละงานจะใช้เวลา 10 วินาที ดังนั้นเวลาในการดำเนินการโดยเฉลี่ยคือ (100+(110-10)+(120-10))3 = 103 ผู้จัดกำหนดการจะทำอะไรได้บ้างเพื่อปรับปรุงสิ่งนี้
ระยะเวลาที่สั้นที่สุดในการทำให้เสร็จก่อน (STCF)
เพื่อปรับปรุงสถานการณ์ เราข้ามสมมติฐานที่ 3 ที่ว่าโปรแกรมเปิดตัวและรันจนกว่าจะเสร็จสมบูรณ์ นอกจากนี้เรายังต้องการการสนับสนุนด้านฮาร์ดแวร์และเราจะใช้งานอย่างที่คุณเดาได้ เครื่องจับเวลา เพื่อขัดจังหวะงานที่กำลังดำเนินอยู่และ การสลับบริบท. ดังนั้นตัวกำหนดเวลาสามารถทำบางสิ่งบางอย่างในขณะที่งาน B, C มาถึง - หยุดการดำเนินการงาน A และนำงาน B และ C เข้าสู่การประมวลผลและหลังจากเสร็จสิ้นแล้ว ให้ดำเนินการตามกระบวนการ A ต่อไป ตัวกำหนดตารางเวลาดังกล่าวเรียกว่า สสสหรือ งานยึดเอาเสียก่อน.
ผลลัพธ์ของผู้วางแผนนี้จะเป็นผลลัพธ์ต่อไปนี้: ((120-0)+(20-10)+(30-10))/3=50 ดังนั้นตัวกำหนดเวลาดังกล่าวจึงเหมาะสมที่สุดสำหรับงานของเรามากยิ่งขึ้น
เวลาตอบสนองเมตริก
ดังนั้น หากเราทราบเวลาทำงานของงานและงานเหล่านี้ใช้เฉพาะ CPU เท่านั้น STCF จะเป็นทางออกที่ดีที่สุด และครั้งหนึ่งในยุคแรกๆ อัลกอริธึมเหล่านี้ทำงานได้ค่อนข้างดี อย่างไรก็ตาม ขณะนี้ผู้ใช้ใช้เวลาส่วนใหญ่ที่เทอร์มินัลและคาดหวังว่าจะได้รับประสบการณ์โต้ตอบที่มีประสิทธิผล จึงมีการวัดใหม่เกิดขึ้น - เวลาตอบสนอง (การตอบสนอง).
เวลาตอบสนองจะถูกคำนวณดังนี้:
Tresponse=Tfirstrun−การมาถึง
ดังนั้น สำหรับตัวอย่างก่อนหน้านี้ เวลาตอบสนองจะเป็น: A=0, B=0, C=10 (abg=3,33)
และปรากฎว่าอัลกอริทึม STCF ไม่ค่อยดีนักในสถานการณ์ที่มี 3 งานมาถึงพร้อมกัน - จะต้องรอจนกว่างานเล็ก ๆ จะเสร็จสมบูรณ์ ดังนั้น อัลกอริธึมจึงดีสำหรับเมตริกเวลาตอบสนอง แต่ไม่ดีสำหรับเมตริกการโต้ตอบ ลองนึกภาพว่าคุณกำลังนั่งอยู่ที่เทอร์มินัลพยายามพิมพ์อักขระลงในโปรแกรมแก้ไขและต้องรอนานกว่า 10 วินาทีเพราะงานอื่นบางอย่างกำลังใช้งาน CPU มันไม่น่ารื่นรมย์นัก
ดังนั้นเราจึงเผชิญกับปัญหาอื่น - เราจะสร้างตัวกำหนดเวลาที่ไวต่อเวลาตอบสนองได้อย่างไร?
โรบินรอบ
อัลกอริธึมได้รับการพัฒนาเพื่อแก้ไขปัญหานี้ โรบินรอบ (ร.ร.) แนวคิดพื้นฐานนั้นค่อนข้างง่าย: แทนที่จะรันงานจนกว่าจะเสร็จสิ้น เราจะรันงานในช่วงระยะเวลาหนึ่ง (เรียกว่าการแบ่งเวลา) จากนั้นจึงสลับไปยังงานอื่นจากคิว อัลกอริทึมจะทำซ้ำงานจนกว่างานทั้งหมดจะเสร็จสิ้น ในกรณีนี้ เวลารันของโปรแกรมจะต้องเป็นทวีคูณของเวลา หลังจากนั้นตัวจับเวลาจะขัดจังหวะกระบวนการ ตัวอย่างเช่น หากตัวจับเวลาขัดจังหวะกระบวนการทุกๆ x=10ms ขนาดของหน้าต่างการดำเนินการกระบวนการควรเป็นผลคูณของ 10 และเป็น 10,20 หรือ x*10
ลองดูตัวอย่าง: งาน ABC มาถึงพร้อมกันในระบบ และแต่ละงานต้องการรันเป็นเวลา 5 วินาที อัลกอริธึม SJF จะทำงานแต่ละงานให้เสร็จสิ้นก่อนที่จะเริ่มงานอื่น ในทางตรงกันข้าม อัลกอริธึม RR ที่มีหน้าต่างเรียกใช้ = 1s จะผ่านงานดังต่อไปนี้ (รูปที่ 4.3):
(SJF อีกครั้ง (ไม่ดีสำหรับเวลาตอบสนอง)
(Round Robin (เหมาะสำหรับเวลาตอบสนอง)
เวลาตอบสนองโดยเฉลี่ยสำหรับอัลกอริทึม RR คือ (0+1+2)/3=1 ในขณะที่สำหรับ SJF (0+5+10)/3=5
มีเหตุผลที่จะถือว่ากรอบเวลาเป็นพารามิเตอร์ที่สำคัญมากสำหรับ RR ยิ่งมีค่าน้อยเท่าใด เวลาตอบสนองก็จะยิ่งสูงขึ้นเท่านั้น อย่างไรก็ตาม คุณไม่ควรทำให้น้อยเกินไป เนื่องจากเวลาในการเปลี่ยนบริบทจะมีบทบาทต่อประสิทธิภาพโดยรวมด้วย ดังนั้นตัวเลือกของกรอบเวลาการดำเนินการจะถูกกำหนดโดยสถาปนิกระบบปฏิบัติการและขึ้นอยู่กับงานที่วางแผนไว้ว่าจะดำเนินการในนั้น บริบทการสลับไม่ใช่การดำเนินการบริการเพียงอย่างเดียวที่เสียเวลา - โปรแกรมที่รันอยู่ทำงานกับสิ่งอื่น ๆ มากมายเช่นแคชต่าง ๆ และในแต่ละสวิตช์จำเป็นต้องบันทึกและกู้คืนสภาพแวดล้อมนี้ซึ่งอาจใช้เวลามากเช่นกัน เวลา.
RR เป็นตัวกำหนดเวลาที่ดีหากเราพูดถึงเฉพาะตัววัดเวลาตอบสนองเท่านั้น แต่การวัดเวลาตอบสนองของงานจะทำงานอย่างไรกับอัลกอริทึมนี้ ลองพิจารณาตัวอย่างข้างต้น เมื่อเวลาทำงานของ A, B, C = 5 วินาที และมาถึงในเวลาเดียวกัน งาน A จะสิ้นสุดที่ 13 วินาที, B ที่ 14 วินาที, C ที่ 15 วินาที และเวลาตอบสนองโดยเฉลี่ยคือ 14 วินาที ดังนั้น RR จึงเป็นอัลกอริธึมที่แย่ที่สุดสำหรับการวัดการหมุนเวียน
โดยทั่วไปแล้ว อัลกอริธึมประเภท RR ใดๆ ก็ยุติธรรม โดยแบ่งเวลา CPU เท่าๆ กันระหว่างกระบวนการทั้งหมด ดังนั้นตัวชี้วัดเหล่านี้จึงขัดแย้งกันอยู่เสมอ
ดังนั้นเราจึงมีอัลกอริธึมที่ตัดกันหลายตัว และในเวลาเดียวกันก็ยังมีข้อสันนิษฐานอีกหลายข้อ - ทราบเวลาของงานและงานนั้นใช้เฉพาะ CPU เท่านั้น
ผสมกับ I/O
ก่อนอื่น ให้ลบสมมติฐานที่ 4 ที่ว่ากระบวนการใช้เฉพาะ CPU เท่านั้น ซึ่งปกติแล้วจะไม่เป็นเช่นนั้นและกระบวนการสามารถเข้าถึงอุปกรณ์อื่นๆ ได้
ทันทีที่กระบวนการใดๆ ร้องขอการดำเนินการ I/O กระบวนการจะเข้าสู่สถานะที่ถูกบล็อก โดยรอให้ I/O เสร็จสิ้น หากส่ง I/O ไปยังฮาร์ดไดรฟ์ การดำเนินการดังกล่าวอาจใช้เวลานานหลายมิลลิวินาทีหรือนานกว่านั้น และโปรเซสเซอร์จะไม่ได้ใช้งานในขณะนี้ ในช่วงเวลานี้ ตัวกำหนดเวลาสามารถครอบครองโปรเซสเซอร์ร่วมกับกระบวนการอื่นใดได้ การตัดสินใจครั้งต่อไปที่ผู้จัดกำหนดการจะต้องทำคือเมื่อใดที่กระบวนการจะเสร็จสิ้น I/O เมื่อสิ่งนี้เกิดขึ้น การขัดจังหวะจะเกิดขึ้นและระบบปฏิบัติการจะทำให้กระบวนการที่เรียกว่า I/O อยู่ในสถานะพร้อม
ลองดูตัวอย่างงานต่างๆ แต่ละรายการต้องใช้เวลา CPU 50ms อย่างไรก็ตาม อันแรกจะเข้าถึง I/O ทุกๆ 10 มิลลิวินาที (ซึ่งจะถูกดำเนินการทุกๆ 10 มิลลิวินาทีด้วย) และกระบวนการ B ใช้โปรเซสเซอร์ 50ms โดยไม่มี I/O
ในตัวอย่างนี้ เราจะใช้ตัวกำหนดเวลา STCF ตัวกำหนดเวลาจะทำงานอย่างไรหากมีการเปิดตัวกระบวนการเช่น A เขาจะทำสิ่งต่อไปนี้: ขั้นแรกเขาจะทำกระบวนการ A ให้สมบูรณ์ จากนั้นจึงดำเนินการ B
แนวทางดั้งเดิมในการแก้ปัญหานี้คือการปฏิบัติต่องานย่อย 10 มิลลิวินาทีของกระบวนการ A ให้เป็นงานที่แยกจากกัน ดังนั้น เมื่อเริ่มต้นด้วยอัลกอริธึม STJF ตัวเลือกระหว่างงาน 50 มิลลิวินาทีและงาน 10 มิลลิวินาทีจึงชัดเจน จากนั้น เมื่องานย่อย A เสร็จสิ้น กระบวนการ B และ I/O จะเปิดตัว หลังจาก I/O เสร็จสมบูรณ์ เป็นธรรมเนียมที่จะเริ่มกระบวนการ 10ms A อีกครั้งแทนที่จะเป็นกระบวนการ B ด้วยวิธีนี้ จึงเป็นไปได้ที่จะปรับใช้การทับซ้อน โดยที่ CPU ถูกใช้โดยกระบวนการอื่นในขณะที่กระบวนการแรกกำลังรอการ ฉัน/โอ และเป็นผลให้ระบบใช้งานได้ดีขึ้น ในขณะที่กระบวนการโต้ตอบกำลังรอ I/O กระบวนการอื่นๆ ก็สามารถดำเนินการบนโปรเซสเซอร์ได้
ออราเคิลไม่มีอีกแล้ว
ทีนี้ลองกำจัดสมมติฐานที่ว่าทราบเวลาทำงานของงานแล้ว โดยทั่วไปนี่เป็นสมมติฐานที่แย่ที่สุดและไม่สมจริงที่สุดในรายการทั้งหมด ในความเป็นจริง ใน OS ทั่วไปโดยเฉลี่ย OS เองมักจะรู้น้อยมากเกี่ยวกับเวลาดำเนินการของงาน ดังนั้นคุณจะสร้างตัวกำหนดเวลาโดยไม่รู้ว่างานนั้นจะใช้เวลาดำเนินการนานเท่าใด บางทีเราอาจใช้หลักการ RR บางอย่างเพื่อแก้ไขปัญหานี้
ทั้งหมด
เราดูแนวคิดพื้นฐานของการจัดกำหนดการงานและดูที่ตัวกำหนดเวลา 2 ตระกูล งานแรกจะเริ่มงานที่สั้นที่สุดก่อน และเพิ่มเวลาตอบสนอง ในขณะที่งานที่สองจะถูกแยกระหว่างงานทั้งหมดเท่าๆ กัน ส่งผลให้เวลาตอบสนองเพิ่มขึ้น อัลกอริธึมทั้งสองไม่ดีโดยที่อัลกอริธึมของตระกูลอื่นดี นอกจากนี้เรายังดูว่าการใช้ CPU และ I/O แบบขนานสามารถปรับปรุงประสิทธิภาพได้อย่างไร แต่ไม่ได้แก้ปัญหาด้วยการมีญาณทิพย์ของระบบปฏิบัติการ และในบทเรียนถัดไป เราจะดูนักวางแผนที่มองไปยังอดีตอันใกล้นี้และพยายามทำนายอนาคต และเรียกว่าคิวคำติชมหลายระดับ
ที่มา: will.com