กระบวนการ Syncการทำเวลา: ปัญหาส่วนสำคัญในระบบปฏิบัติการ

กระบวนการคืออะไร Syncพรหมลิขิต?

กระบวนการ Syncการทำให้เป็นพงศาวดาร เป็นงานในการประสานงานการดำเนินการของกระบวนการในลักษณะที่ไม่มีสองกระบวนการสามารถเข้าถึงข้อมูลและทรัพยากรที่ใช้ร่วมกันได้

โดยเฉพาะอย่างยิ่งในระบบมัลติโปรเซส เมื่อมีหลายโปรเซสทำงานพร้อมกัน และมากกว่าหนึ่งโปรเซสพยายามเข้าถึงทรัพยากรหรือข้อมูลที่ใช้ร่วมกันเดียวกันในเวลาเดียวกัน

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

วิธีการดำเนินการ Syncการทำให้เที่ยงตรงใช้งานได้หรือไม่?

ตัวอย่างเช่น กระบวนการ A กำลังเปลี่ยนแปลงข้อมูลในตำแหน่งหน่วยความจำ ในขณะที่กระบวนการ B พยายามอ่านข้อมูลจากตำแหน่งนั้น เดียวกัน ตำแหน่งหน่วยความจำ มีความเป็นไปได้สูงที่ข้อมูลที่อ่านโดยกระบวนการที่สองจะผิดพลาด

ส่วนของโปรแกรม

ต่อไปนี้คือองค์ประกอบสำคัญสี่ประการของส่วนวิเคราะห์วิจารณ์:

• ส่วนรายการ: มันเป็นส่วนหนึ่งของกระบวนการที่ตัดสินการเข้าสู่กระบวนการเฉพาะ
• ส่วนสำคัญ: ส่วนนี้อนุญาตให้กระบวนการหนึ่งป้อนและแก้ไขตัวแปรที่แชร์
• ส่วนทางออก: ส่วน Exit อนุญาตให้กระบวนการอื่นๆ ที่รออยู่ในส่วน Entry เข้าสู่ส่วน Critical ได้ นอกจากนี้ยังตรวจสอบว่ากระบวนการที่เสร็จสิ้นการทำงานแล้วควรถูกลบออกผ่านส่วนนี้หรือไม่
• ส่วนที่เหลือ: ส่วนอื่นๆ ทั้งหมดของ Codeชิ้นส่วนที่ไม่ได้อยู่ในส่วนวิกฤต ส่วนเข้า และส่วนออก จะเรียกว่า ส่วนที่เหลือ

ปัญหาส่วนสำคัญคืออะไร?

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

• การเข้าสู่ส่วนวิกฤติได้รับการจัดการโดยฟังก์ชัน wait() และแสดงเป็น P()
• ทางออกจากส่วนวิกฤติจะถูกควบคุมโดยฟังก์ชัน signal() ซึ่งแสดงเป็น V()

ในส่วนที่สำคัญ สามารถดำเนินการได้เพียงกระบวนการเดียวเท่านั้น กระบวนการอื่นๆ ที่รอดำเนินการในส่วนที่สำคัญ ต้องรอจนกว่ากระบวนการปัจจุบันจะดำเนินการเสร็จสิ้น

กฎเกณฑ์สำหรับมาตราที่สำคัญ

ส่วนสำคัญต้องบังคับใช้กฎทั้งสามข้อนี้:

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

แนวทางแก้ไขในส่วนสำคัญ

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

ต่อไปนี้เป็นวิธีการที่ใช้กันอย่างแพร่หลายในการแก้ปัญหาส่วนวิกฤติ

โซลูชั่นปีเตอร์สัน

วิธีแก้ปัญหาของปีเตอร์สันเป็นวิธีแก้ปัญหาที่ใช้กันอย่างแพร่หลายสำหรับปัญหาในส่วนวิกฤต อัลกอริทึมนี้ได้รับการพัฒนาโดยนักวิทยาศาสตร์คอมพิวเตอร์ชื่อปีเตอร์สัน จึงเป็นที่มาของชื่อวิธีแก้ปัญหาของปีเตอร์สัน

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

ตัวอย่าง

PROCESS Pi
FLAG[i] = true
while( (turn != i) AND (CS is !free) ){ wait;
}
CRITICAL SECTION FLAG[i] = false
turn = j; //choose another process to go to CS

• สมมติว่ามีกระบวนการ N กระบวนการ (P1, P2, … PN) และทุกกระบวนการจะต้องเข้าสู่ส่วนวิกฤต (Critical Section) ในช่วงเวลาใดเวลาหนึ่ง
• มีการเก็บรักษาอาร์เรย์ FLAG[] ขนาด N ซึ่งค่าเริ่มต้นคือ false ดังนั้น เมื่อใดก็ตามที่กระบวนการต้องการเข้าสู่ส่วนวิกฤต กระบวนการนั้นจะต้องตั้งค่าแฟล็กเป็น true ตัวอย่างเช่น หาก Pi ต้องการเข้าสู่ส่วนวิกฤต มันจะตั้งค่า FLAG[i]=TRUE
• ตัวแปรอีกตัวหนึ่งชื่อ TURN ระบุหมายเลขกระบวนการที่กำลังรอเข้าสู่ระบบ CS อยู่
• กระบวนการที่เข้าสู่ส่วนวิกฤติขณะออกจะเปลี่ยน TURN เป็นหมายเลขอื่นจากรายการกระบวนการที่พร้อม
• ตัวอย่าง: เทิร์นคือ 2 จากนั้น P2 เข้าสู่ส่วนวิกฤต และขณะออกจากส่วนวิกฤต เทิร์นคือ 3 ดังนั้น P3 จึงออกจากลูปการรอคอย

Syncฮาร์ดแวร์เสียงสะท้อน

บางครั้งปัญหาของส่วนวิกฤต (Critical Section) ก็ได้รับการแก้ไขด้วยฮาร์ดแวร์เช่นกัน ระบบปฏิบัติการบางระบบมีฟังก์ชันการล็อก ซึ่งกระบวนการจะล็อกตัวเองเมื่อเข้าสู่ส่วนวิกฤต และจะปลดล็อกหลังจากออกจากส่วนวิกฤตแล้ว

ดังนั้นเมื่อกระบวนการอื่นพยายามเข้าสู่ส่วนสำคัญ กระบวนการนั้นจะไม่สามารถเข้าไปได้เนื่องจากถูกล็อค สามารถทำได้ก็ต่อเมื่อมันว่างโดยการรับล็อคมาเอง

มูเท็กซ์ล็อค

Syncการซิงโครไนซ์ด้วยฮาร์ดแวร์ไม่ใช่เรื่องง่ายสำหรับทุกคน ดังนั้นจึงมีการนำวิธีการทางซอฟต์แวร์ที่เข้มงวดกว่าที่เรียกว่า Mutex Locks มาใช้ด้วย

ในแนวทางนี้ ในส่วนการป้อนข้อมูลของโค้ด จะได้รับ LOCK เหนือทรัพยากรสำคัญที่ใช้ภายในส่วนสำคัญ ในส่วนทางออกที่ล็อคจะถูกปลดล็อค

Semaphore Solution

Semaphore เซมาฟอร์เป็นเพียงตัวแปรที่ไม่ติดลบและใช้ร่วมกันระหว่างเธรดต่างๆ มันเป็นอัลกอริทึมหรือวิธีการแก้ปัญหาอีกแบบหนึ่งสำหรับปัญหาของส่วนวิกฤต (critical section problem) มันเป็นกลไกการส่งสัญญาณ และเธรดที่กำลังรอเซมาฟอร์สามารถรับสัญญาณจากเธรดอื่นได้

มันใช้การดำเนินการพื้นฐานสองอย่าง: 1) รอ และ 2) ส่งสัญญาณเพื่อซิงโครไนซ์กระบวนการ

ตัวอย่าง

WAIT ( S ):
while ( S <= 0 );
S = S - 1;
SIGNAL ( S ):
S = S + 1;

คำถามที่พบบ่อย