Please enable JavaScript.
Coggle requires JavaScript to display documents.
บทที่ 3 การประสานเวลาของโพรเซส, บทที่ 3 การประสานเวลาของโพรเซส - Coggle…
บทที่ 3 การประสานเวลาของโพรเซส
บทที่ 3 การประสานเวลาของโพรเซส
การประมวลผลพร้อมกันโดยวิธีการทางซอฟต์แวร์
อัลกอริทึมของเดกเกอร์
พัฒนาโปรแกรมที่ประกอบด้วย 2 โพรเซส โดยสามารถทำงานพร้อมกัน และเกิดคุณสมบัติการไม่เกิดร่วม
อาจเกิดปัญหา Lock Step Synchronization คือ การที่โพรเซสใดๆจะเข้าทำงานในส่วนวิกฤติ จะต้องทำงานเรียงตามลำดับ
อัลกอริทึมของปีเตอร์สัน
อัลกอริทึมนี้จำกัดโพรเซสสองโพรเซสที่สลับการดำเนินการระหว่างส่วนวิกฤติและส่วนที่เหลือ
สามารถแก้ปัญหาการไม่เกิดร่วมสำหรับ 2 โพรเซส ที่สามารถพัฒนาให้มีการทำงานเป็น n โพรเซสได้
การติดตายและอดตาย
การสร้างเซมาฟอร์ด้วยการให้โพรเซสที่รอการทำงานไปอยู่ในคิว อาจจะทำให้เกิดเหตุการณ์ที่สองโพรเซสหรือมากกว่านั้นรอแบบไม่มีที่สิ้นสุด เนื่องจากโพรเซสไปรอการทำงานของโพรเซสที่รอการทำงานเช่นกัน ลักษณะนี้เรียกว่า การติดตาย(Deadlock)
การประสานเวลาของโพรเซส
การทำงานของโพรเซสที่ต้องมีการเกี่ยวข้องกันอาจจะเป็นเพราะการใช้งานทรัพยากรร่วมกัน หรืออาจจะเป็นการรอให้โพรเซสทำงานหลังจากที่โพรเซสอื่นทำงานแล้ว
ตัวอย่างเช่น
โพรเซส B ต้องรอให้โพรเซส A ทำงานเสร็จสิ้นก่อนถึงจะทำงานได้ ในขณะที่โพรเซส C สามารถทำงานได้เลยโดยไม่ต้องรอ และ โพรเซส D ต้องรอให้ โพรเซส B และ โพรเซส C ทำงานเสร็จสิ้นก่อนถึงจะทำงานได้
สภาวะการแย่งชิง
เนื่องจากโพรเซสใช้ข้อมูลในหน่วยความจำร่วมกันทั้งสองโพรเซสแล้ว การแก้ไขข้อมูล ลำดับการแก้ไข้ก่อนหรือหลังมีความสำคัญต่อค่าข้อมูลตัวนั้น ซึ่งทั้งสองโพรเซสสามารถอ่านหรือเขียนทรัพยากรเหล่านี้ได้พร้อมกัน แต่ผลลัพธ์อาจจะเกิดความผิดพลาด ขึ้นอยู่กับว่าโพรเซสไหนเข้ามาใช้งานก่อน
โครงสร้างพื้นฐานสำหรับการซินโครไนซ์
โพรเซสที่ทำงานร่วมกับโพรเซสอื่น จำเป็นต้องอาศัยซินโครไนซ์ที่เหมาะสมเพื่อการทำงานที่ถูกต้อง
คำสั่งพื้นฐาน
เซมาฟอรฺ์แบบนับ(Counting Semaphore)
เซมาฟอร์แทนได้ด้วย S ซึ่งมีค่าเป็นเลขจำนวนเต็ม เป็นเครื่องมือประสานเวลาที่ไม่ต้องการเวลาคอย การเรียกใช้งานจะทำได้ผ่านทาง 2 คำสั่ง คือ Signal(แทนด้วย V) และ Wait(แทนด้วย P)
คำสั่ง Wait() เป็นการทดสอบค่าของ S และจะทำการลดค่าลงเมื่อตรวจสอบข้อมูลแล้วพบว่ามีค่ามากกว่า 0
คำสั่ง Signal() เป็นการทำงานเพื่อเพิ่มค่า S
การใช้งานเซมาฟอร์
สามารถนำเซมาฟอร์ไปใช้ในการแก้ปัญหาส่วนวิกฤติของโพรเซส n ตัว โดยโพรเซส n ตัวจะร่วมใช้เซมาฟอร์ ที่ชื่อ mutex
การส้รางเซมาฟอร์
กำหนดให้เซมาฟอร์เป็นตัวแปรประเภท Structure ในภาษาซี ตัวแปรเซมาฟอร์จะประกอบไปด้วย ตัวเลขจำนวนเต็ม และแถวคอยของโพรเซส เมื่อโพรเซสหนึ่งต้องคอยเซมาฟอร์นี้ มันจะถูกใส่ชื่อลงในแถวคอย การใช้คำสั่ง signal จะดึงโพรเซสิิกจากหัวแถวคอยนี้และปลุกโพรเซสที่ได้ให้กลับไปทำงานต่อ ค่าเซมาฟอร์จะไม่ติดลบ
คำสั่ง block
จะทำให้โพรเซสที่ทำคำสั่งนี้หยุดชั่วขณะ
คำสั้ง wakeup(P)
จะปลุกโพรเซส P ให้กลับไปทำงานต่อ
ต้องไม่ให้มีโพรเซสสองตัวทำคำสั่ง wait แบะ signal บนเซมาฟอร์ตัวเดียวกันในเวลาเดียวกัน ซึ่งจะทำให้เกิดปัญหา
วิธีจัดการปัญหา
ถ้าเป็นระบบที่มีหน่วยประมวลผลตัวเดียว ห้ามขัดจังหวะขณะที่กำลังทำงานคำสั่ง wait และ signal
ถ้าเป็นระบบที่มีหน่วยความประมวลผลหลายตัว การห้ามขัดจังหวะไม่เพียงพอ เพราะโพรเซสอื่นอาจจะทำงานอยู่ในหน่วยประมวลผลคนละตัวกับโพรเซสที่ห้ามขัดจังหวะ อาจจัดการโดยการแก้ไขส่วนวิกฤติ แล้วเอาคำสั่ง wait และ signal ไปใส่ไว้ในส่วนวิกฤติ
เซมาฟอร์แบบทวิภาค(Binary Semaphore)
จะกำหนดตัวแปรจำนวนเต็มได้ 2 ค่า คือ 0 และ 1 เท่านั้น ทำให้สามารถสร้างง่ายกว่าเซมาฟอร์แบบนับ ซึ่งสามารถสร้างเซมาฟอร์แบบนับให้อยู่ในแบบทวิภาคได้
การแก้ปัญหาส่วนวิกฤติ
สาเหตุที่ต้องมีการแก้ปัญหานี้เนื่องจากแต่ละโพรเซสมีการเข้าใช้ข้อมูลบางอย่างร่วมกัน โดยไม่มีการประสานการทำงานระหว่างกัน ซึ่งอาจทำให้เกิดข้อผิดพลาดได้
การแก้ไขปัญหาส่งงนวิกฤติต้องเป็นไปตามเงื่อนไข
ความก้าวหน้า
ถ้าไม่มีโฑรเซสใดกำลังปฏิบัติอยู่ในส่วนวิกฤติ ระบบจะพิจารณาจากทุกๆโพรเซสว่าโฑรเซสใดจะเข้าสู่ส่วนวิกฏติของตน ยกเว้นโพรเซสที่กำลังทำงานอยู่ในส่วนวิกฤติของตน โดยจะไม่เลื่อนออกไปอย่างไม่มีกำหนด
การรออย่างมีขอบเขต
ต้องมีขอบเขตของเวลาในการรอ โดยเริ่มนับตั้งแต่เวลาที่โพรเซสได้รับอนุญาตให้เข้าสู๋ส่วนวิกฤติไป หลังจากนั้นมีโพรเซสหนึ่งร้องขอจนมาถึงเวลาที่ระบบทำตามคำขอร้องของโฑรเซสนั้น
การรอแบบไม่ว่าง
ในระหว่างรอโพรเซสนั้นยังต้องทำคำสั่งทำซ้ำและทดสอบเงื่อนไขอยู่เรื่อยๆ
การขัด
ระบบจะนำโพรเซสเหล่านั้นไปรออยู่ในแถวของแต่ละเงื่อนไขและตัวแปลที่ใช้ในการตรวจสอบก่อนเข้าสู่ส่วนวิกฤติ ทำให้ไม่ต้องวนตรวจสอบเงื่อนไขโดยไม่ได้ประโยชน์ และเมื่อโฑรเซสล่าสุดที่เข้าใช้ส่วนวิกฤติของตนได้ออกจากส่วนวิกฤตินั้นแล้ว จะต้องใช้คำสั่งหรือปลุกบอกให้ระบบทราบเพื่อนำโพรเซสที่อยู่ในแถวคอยเข้าส่วนวิกฤติ
การกีดกัน
ในขณะใดขณะหนึ่งมีเพียงโพรเซสเดียวเท่านั้นที่อยู่ในส่วนวิกฤติของตน
ปัญหาภาวะพร้อมกัน
ในระบบที่มีการทำงานบนซีพียูตัวเดียวและหลายตัว บางครั้งอาจมีความจำเป็นที่ต้องใช้ทรัพยากรร่วมกัน และเป็นทรัพยากรที่ต้องทำงานครั้งละ 1 งาน ไม่สามารถทำงานพร้อมกันได้ เรียกว่าทรัพยากรที่ไม่สามารถใช้ร่วมกันได้
หาก 2 โพรเซสทำงานพร้อมกันแล้วจะทำให้เกิดข้อผิดพลาดเนื่องจากข้อมูลที่ได้ออกมาไม่เหมือนกัน ขึ้นอยู่กับว่าโพรเซสไหนเสร็จก่อน
ฮาร์ดแวร์ประสานเวลา
การปิดทางขัดจังหวะ(Disble interrupt)
ขณะโพรเซสหนึ่งกำลังทำงานในส่วนวิกฤติ อาจมีโพรเซสอื่นขอขัดจังหวะเพื่อขอโอกาสเข้าไปทำงานในส่วนวิกฤติ ทำให้โพรเซสที่กำลังทำงานอยู่ในส่วนวิกฤติต้องหยุดการทำงานโดยที่การทำงานยังไม่เสร็จสมบูรณ์ และสลับให้โพรเซสอื่นเข้าไปทำงานในส่วนวิกฤติแทน วิธีนี้จึงไม่เป็นที่นิยม เพราะอาจเกิดการแทรกแซงการทำงานได้
คำสั่งทดสอบและเซต(Test and Set instruction)
วิธีนี้พยายามแก้ไขปัญหาของวิธีการปิดกั้นและการปิดทางขัดจังหวะ ด้วยการใช้คำสั่งทดสอบและเซตโดยการทำงานของคำสั่งไม่สามารถถูกขัดจังหวะได้
การทำงานของวิธีนี้คือ โพรเซสที่ต้องการเข้าไปทำงานในส่วนวิกฤติจะต้องใช้คำสั่งทดสอบและเซต เพื่อตรวจสอบว่ามีโพรเซสไหนทำงานในส่วนวิกฤติหรือไม่ หากไม่มีโพรเซสจะเซตค่าล็อคเพื่อป้องกันไม่ให้โพรเซสอื่นเข้าไปทำงานในส่วนวิกฤติพร้อมกันได้ ทำให้ระบบสามารถมีโพรเซสจำนวนมากทำงานร่วมกัน โดยมีคุณสมบัติการไม่เกิดร่วม
คำสั่ง TestAndSet() ลักษณะที่สำคัญคือจะทำงานคำสั่งนี้แบบ Atomically ดังนั้นคำสั่ง TestAndSet() ที่ทำงานในเวลาเดียวกัน แต่ทำบนซีพียูที่แตกต่าง คำสั่งนี้จะถูกรันตามลำดับแบบสุ่ม
การปิดกั้น(Lock)
เมื่อโพรเซสต้องการเข้าไปทำงานในส่วนวิกฤติ โพรเซสจะต้องตรวจสอบก่อนว่าส่วนวิกฤตินั้นล็อคหรือไม่(มีโพรเซสอื่นทำงานอยู่) เมื่อตรวจสอบแล้วไม่มีจึงเข้าไปทำงานในส่วนวิกฤตินั้นและก่อนที่จะเข้าไปทำงานโพรเซสต้องใส่ล็อคเพื่อปิดกั้นไม่ให้โพรเซสอื่นเข้าไปทำงานได้ และเมื่อทำงานเสร็จสิ้นแล้วจึงปลดล็อค เพื่อให้โพรเซสอื่นสามารถเข้ามาทำงานในส่วนวิกฤติได้
การทำงานด้วยวิธีนี้ระบบสามารถมีมากกว่า 1 โพรเซสที่ทำงานพร้อมกันได้ โดยมีคุณสมบัติทำงานในส่วนวิกฤติ
แต่อาจจะเกิดปัญหาในกรณีที่มีมากกว่า 1 โพรเซสต้องการเข้าทำงานในส่วนวิกฤติพร้อมกัน
Swap Instruction
คำสั่ง Swap() จะตรงข้ามกับ TestAndSet() คำสั่ง Swap() จะทำงานในเนื้อหาของคำสองคำ เช่นเดียวกับคำสั่ง TestAndSet() จะรัน Atomically หากครื่องสบันสนุนคำสั่ง Swap() แล้วการเอาออกทั้งสองฝ่ายโดยมีเงื่อนไขว่า การล็อคตัวแปร Global Boolean จะถูกประกาศและทำให้เป็นเท็จตั้งแต่เริ่มต้น นอกจากนี้แต่ละโพรเซสมีคีย์ของตัวแปร Local Boolean โครงสร้างของโพรเซส Pi
ปัญหาพื้นฐานของการประสานเวลา
ปัญหาที่พักข้อมูลขนาดจำกัด
บางทีเรียกว่าปัญหาผู้ผลิต-ผู้บริโภค เป็นปัญหาที่ใช้ในการทดสอบประสิทธิภาพของเทคนิคการประสานเวลา มีผู็ผลิตหนึ่งคนหรือมากกว่าทำการผลิตข้อมูลบางชนิด และใส่ลงในบัฟเฟอร์ และ ณ ขณะใดขณะหนึ่งจะมีเพียงคนเดียวเท่านั้นที่สามารถเข้าถึงบัฟเฟอร์ได้
ปัญหาผู้อ่านและผู้เขียน
ข้อมูลในระบบที่มีการทำงานของโฑรเซสพร้อมกันหลายตัวจะถูกร่วมกันใช้งาน บางโพรเซสต้องการอ่านข้อมูล บางโพรเซสต้องการเขียนข้อมูล โดยที่ความแตกต่างของทั้งสองก็คือ Readers จะเป็นโพรเซสที่ต้องการอ่านข้อมูลเพียงอย่างเดียว ส่วนโพรเซส Writer จะต้องการเพียงแค่การเขียนข้อมูลเท่านั้น
เกิดปัญหาขึ้นเมื่อมีโพรเซสจำนวนมากที่ต้องการอ่านบนพื้นที่ดังกล่าวและมีโพรเซสจำนวนมากที่ต้องการเขียนบนพื้นที่ดังกล่าวในเวลาเดียวกัน จึงมีการนำเอาเซมาฟอร์มาช่วยแก้ปัญหาเหล่านี้
การจัดการต้องเข้ากันได้กับเงื่อนไขเหล่านี้
ณ เวลาใดเวลาหนึ่งมีเพียงผู้เขียนคนเดียวเท่านั้นที่สามารถเขียนแฟ้มได้
ถ้ามีผู้เขียนรอที่จะเขียนแฟ้ม จะต้องไม่มีผู้อ่านคนใดสามารถอ่านแฟ้มนั้นได้
ผู้อ่านสามารถอ่านแฟ้มได้พร้อมกันหลายคน
จากเงื่อนไขของการจัดการที่ต้องเข้ากันอาจจะทำให้เกิดภาวะงูกินหาง
กรณีแรกผู้เขียนอาจจะต้องเป็นฝ่ายรออย่างไม่รู้จบ
กรณีที่สองผู้อ่านอาจต้องเป็นฝ่ายรออย่างไม่รู้จบ
ปัญหาอาหารเย็นของนักปราชญ์
เป็นปัญหาที่ต้องการให้มีการจัดการเรื่องการใช้ทรัพยากรที่มีอยู่อย่างจำกัดร่วมกันระหว่างหลายโพรเซส ปัญหาการติดตายจะเกิดขึ้นเมื่อนักปราชญ์ทั้งห้าหยิบตะเกียบคนละข้างพร้อมกัน ปัญหาการรอดตาย การที่นักปราชญ์ทางด้านซ้ายและด้านขาวของนักปราชญ์ผู้โชคร้ายสลับกันทานอาหาร
การแก้ปัญหานี้ทำได้โดยการกำหนดตัวแปรร่วม
วิธีนี้อาจป้องกันไม่ให้นักปราชญ์นั่งติดกัน กินพร้อมกันได้ แต่อาจเกิดปัญหาวงจรอับขึ้นในระบบ
หยิบตะเกียบด้วยคำสั่ง wait
วางตะเกียบด้วยคำสั่ง signal
ให้ตะเกียบ(อาร์เรย์ chopstick) เป็นเซมาฟอร์โดยนักปราชญ์
ค่าเริ่มต้นของตะเกียบ(chopstick) =1
กำหนดเซมาฟอร์เป็นอาร์เรย์ชื่อ chopstick[5];
วิธีแก้ปัญหาวงจรอับ ไม่ให้มีการแย่งชิงที่เป็นสาเหตุให้นักปราชญ์คนหนึ่งเข้าสู่ภาวะติดตาย แต่วิธีนี้ไม่ได้ป้องกันสภาวะการรออย่างไม่รู้จบ
ให้นักปราชญ์หยิบตะเกียบก็ต่อเมื่อตะเกียบทั้งสองข้าง(ซ้ายและขาว)ว่างทั้งคู่(ต้องทำในเขตวิกฤติ)
ใช้วิธีแก้ปัญหาแบบอสมมาตร โดยให้นักปราชญ์คนที่เลขคี่ให้หยิบตะเกียบข้างซ้ายก่อน ถ้าได้แล้วจึงหยิบตะเกียบข้างขวา
ให้นักปราชญ์นั่งโต๊ะได้ไม่เกิน 4 คน
นักปราชญ์คนที่เลขคู่หยิบตะเกียบข้างขวาก่อนแลัวจึงหยิบตะเกียบซ้าย
