Please enable JavaScript.
Coggle requires JavaScript to display documents.
บทที่3 การประสานเวลาของโพรเซส - Coggle Diagram
บทที่3 การประสานเวลาของโพรเซส
3.1 การประสานเวลาของโพรเซส
โดยทั่วไปทุกโพรเซสต้องการให้มีการประมวลผลอย่างเป็นอิสระ เสมือนมีโพรเซสเดียวที่กำลังทำงานอยู่ ลักษณะความเป็นอิสระนี้เรียกว่า Asynchronous
ระบบปฏิบัติการจึงเข้ามาช่วยจัดการแต่ละโพรเซส ให้สามารถประมวลผลได้พร้อมกัน (Concurrent processing) และมีการทำงานร่วมกัน (Cooperating) เป็นผลให้โพรเซสในระบบได้มี การใช้ทรัพยากร ร่วมกัน ช่วยเพิ่มความเร็วในการทำงานของระบบสูงขึ้นและมีความสะดวกในการทำงานจำเป็นต้องมีการสื่อสารกันระหว่างโพรเซส
3.2 ปัญหาภาวะพร้อมกัน
ในระบบที่มีการทำงานบนซีพียูเดียว หรือทำงานบนซีพียูหลายตัว บางครั้งมีความจำเป็นที่ต้องใช้
ทรัพยากรร่วมกัน และเป็นทรัพยากรที่ต้องทำงานครั้งละ 1 งาน ทำงานพร้อมกันไม่ได้ เรียกว่าทรัพยากรที่ไม่สามารถใช้ร่วมกันได้(Non-dedicated resources) ดังนั้น ในขณะที่โพรเซสหนึ่งกำลังใช้ทรัพยากรอยู่ โพรเซสอื่นจะไม่สามารถใช้ทรัพยากรนั้น ๆ ได้ เพื่อผลของการทำงานที่ถูกต้อง โพรเซสที่ใช้ข้อมูลร่วมกันหรือร่วมกันทำงาน การใช้ทรัพยากรต่าง ๆ เช่น หน่วยความจำ
3.3 สภาวะการแย่งชิง
ลำดับของการแก้ไขก่อนหรือหลังมีความสำคัญต่อค่าของข้อมูลตัวนั้น ทำให้โพรเซสสองโพรเซสที่ต้องการใช้ทรัพยากรที่แชร์ไว้พร้อมกันในเวลาเดียวกัน เช่น หน่วยความจำ ซึ่งโพรเซสทั้งสองสามารถอ่านหรือเขียนทรัพยากรเหล่านี้ได้พร้อมกัน ทำให้ผลลัพธ์อาจจะเกิดการผิดพลาดขึ้นได้ ขึ้นอยู่ว่าโพรเซสใดเข้ามาใช้ก่อนขึ้นอยู่กับว่าโพรเซสใดทำเสร็จก่อนเรียกสภาวะนี้ว่า สภาวะเงื่อนไขการแย่งชิง (Race condition)
3.4 การแก้ปัญหาส่วนวิกฤติ
3.4.1 การกีดกัน (Mutual exclusion)
ในขณะใดขณะหนึ่งมีเพียงโพรเซสเดียวเท่านั้นที่อยู่ในส่วนวิกฤติของตน
3.4.2 ความก้าวหน้า (Progress)
ถ้าไม่มีโพรเซสใดกำลังทำงานอยู่ในส่วนวิกฤติ แล้วมีบางโพรเซสเข้าสู่ส่วนวิกฤติ ในการเลือกว่าโพรเซสใดจะได้เข้าสู่ส่วนวิกฤติต่อไปนั้น ระบบก็จะพิจารณาจากทุก ๆ โพรเซส ยกเว้นโพรเซสที่กำลังทำงานอยู่ในส่วนที่เหลือนั้น โดยการเลือกนี้ต้องไม่เลื่อนออกไปอย่างไม่มีกำหนด
3.4.3 การรออย่างมีขอบเขต (Bounded waiting)
การรอแบบไม่ว่าง (Preemptive kernels)
ในระหว่างรอโพรเซสนั้นยังต้องทำคำสั่งทำซ้ำและทดสอบเงื่อนไขอยู่เรื่อย ๆ
การขัด (Non-preemptive kernels)
การพัฒนาให้ทำการบล็อกโพรเซสที่ต้องการเข้าสู่ส่วนวิกฤติแต่ยังไม่อาจเข้าได้ เนื่องจากมีโพรเซสอื่นกำลังทำงานอยู่ในส่วนวิกฤติ ซึ่งการบล็อกนี้ระบบจะนำโพรเซสเหล่านั้นไปรออยู่ในแถวของแต่ละเงื่อนไขและตัวแปรที่ใช้ในการตรวจสอบก่อนเข้าสู่ส่วนวิกฤติทำให้โพรเซสเหล่านี้ไม่ต้องเข้ามาแย่งชิงกันใช้ซีพียู
3.5 การประมวลผลพร้อมกันโดยวิธีการทางซอฟต์แวร์
3.5.1 อัลกอริทึมของเดกเกอร์
ทำการพัฒนาโปรแกรมที่ประกอบด้วย 2 โพรเซสโดยสามารถทำงานพร้อมกันและเกิดคุณสมบัติการไม่เกิดร่วม
3.5.2 อัลกอริทึมปีเตอร์สันโซลูชั่น (Peterson’s Solution)
อัลกอริทึมนี้จะจำกัดโพรเซสสองโพรเซสที่สลับการดำเนินการระหว่างส่วนวิกฤติและส่วนที่เหลือ
3.6 ฮาร์ดแวร์ประสานเวลา
3.6.1 การปิดกั้น (Lock)
3.6.2 การปิดทางขัดจังหวะ (Disable Interrupt)
3.6.3 คำสั่งทดสอบและเซต (Test and Set Instruction)
3.7 โครงสร้างพื้นฐานสำหรับการซินโครไนซ์
3.7.1 เซมาฟอร์(Semaphore)
เซมาฟอร์แทนได้ด้วย S ซึ่งมีค่าเป็นเลขจำนวนเต็ม (Integer) การเรียกใช้งานจะทำได้ผ่านทาง 2 คำสั่ง คือ Signal (แทนด้วย V ย่อมาจากคำว่า Verhogen) และ Wait (แทนด้วย P ย่อมาจากคำว่า Proberen)
3.7.2 การใช้งานเซมาฟอร์
สามารถนำเซมาฟอร์ไปใช้ในการแก้ไขปัญหาส่วนวิกฤตของโพรเซส n ตัว
โพรเซส n ตัวจะร่วมใช้เซมาฟอร์ที่ชื่อ mutex (ใช้แทน Mutual exclusion)
3.7.3 การสร้างเซมาฟอร์
(Semaphore Implementation)
กำหนดให้เซมาฟอร์เป็นตัวแปรประเภท Structure ใน
ภาษาซี ตัวแปรเซมาฟอร์จะประกอบด้วยตัวเลขจำนวนเต็มและแถวคอยของโพรเซส เมื่อโพรเซสหนึ่งต้องคอยเซมาฟอร์นี้ มันก็จะถูกใส่ชื่อลงในแถวคอย L การใช้คำสั่ง signal จะดึงโพรเซสออกจากหัวแถวคอยนี้ และปลุกโพรเซสที่ได้ให้กลับไปทำงานต่อ
3.7.4 เซมาฟอร์แบบทวิภาค
(Binary Semaphore)
ส่วนในเซมาฟอร์แบบทวิภาคจะกำหนดให้ใช้ตัวแปรจำนวนเต็มได้ 2 ค่าคือ 0 และ 1 เท่านั้น ทำให้สามารถสร้างได้ง่ายกว่าเซมาฟอร์แบบนับ ซึ่งสามารถสร้างเซมาฟอร์แบบนับให้อยู่ในรูปแบบทวิภาคได้
3.8 การติดตายและอดตาย
เกิดเหตุการณ์ที่สองโพรเซสหรือมากกว่านั้นรอแบบไม่มีที่สิ้นสุด เรียกว่าการติดตาย (Deadlock)
3.9 ปัญหาพื้นฐานของการประสานเวลา
3.9.1 ปัญหาที่พักข้อมูลขนาดจำกัด (Bounded-Buffer Problem)
3.9.2 ปัญหาผู้อ่านและผู้เขียน
(The Readers/Writers Problem)
มีพื้นที่ข้อมูลซึ่งใช้ร่วมกัน และมีโพรเซสจำนวนมากที่ต้องการอ่านพื้นที่ดังกล่าวเพียงอย่างเดียว และมีโพรเซสที่ต้องการเขียนบนพื้นที่ดังกล่าวเพียงโพรเซสเดียวในเวลาเดียวกัน จึงมีการนำเอาเซมาฟอร์ช่วยในการแก้ไขปัญหาเหล่านี้ โดยให้มีโครงสร้างของการใช้ตัวแปรร่วมกัน