การซิงโครไนซ์โปรเซส

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

1. Race Condition

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

2. Mutual Exclusion and Critical Region

– เป็นการแก้ปัญหา Race Condition คือ ป้องกันไม่ให้โปรเซสอื่นเข้ามาครองครองทรัพยากรได้ในขณะที่โปรเซสอื่นครอบครองอยู่เรียกว่า Mutual Exclusion : ทำทีละprocess

– บริเวณที่โปรเซสเข้าไปครอบครองทรัพยากร เรียกว่าCritical Region : Process ครอบครอง resource อยู่

– คือ เมื่อโปรเซสใดก็ตามอยู่ใน Critical Region แล้วโปรเซสอื่นจะเข้าไปอยู่ใน Critical Region ไม่ได้ ต้องรอให้โปรเซสนั้นออกจาก Critical Region ก่อน

2. Mutual Exclusion and Critical Region

– คุณสมบัติ 4 ประการของ Mutual Exclusion

• จะต้องไม่มีโปรเซส 2 โปรเซสอยู่ใน Critical Regionพร้อมกัน

• ไม่มีข้อจำกัดด้านความเร็ว และจำนวยซีพียูมาเกี่ยวข้อง

• จะต้องไม่มีโปรเซสที่อยู่นอก Critical Region บล็อกการทำงานของโปรเซสอืื่น

• จะต้องไม่มีโปรเซสใดที่รอการเข้า Critical Regionตลอดเวลา

Clock Interrupt เป็นการขัดจังหวะที่บอกซีพียูว่าอยู่ในสถานะรันครบเวลาควันตัม แล้ว

• I/O Interrupt เป็นการขัดจังหวะที่บอกซีพียูว่าโปรเซสที่อยู่ในสถานะบล็อกทำงานกับ I/O เสร็จแล้ว เมื่อซีพียูรับทราบ ซีพียูก็จะหยุดโปรเซสที่กำลังรันอยู่ แล้วให้มาจัดการกับโปรเซสที่อยู่ในสถานะบล็อกที่ส่งอินเทอรร์รัพท์ไปยังสถานะพร้อมเพื่อทำงานต่อไป

4. Sleep and Wakeup

– ถ้าโปรเซสใดต้องการเข้า Critical Region แต่ยังไม่ได้รับอนุญาตก็วนรอบรอจนกว่าโปรเซสที่กำลังอยู่ใน Critical

Region เสร็จออกมา ทำให้้เสียเวลารอ ดังนั้นจึงแก่ปััญหาโดยการบล็อก (Sleep and Wakeup)แทนการ วนรอ โดย

• Sleep เป็น system call เพื่อบล็อกให้โปรเซสหยุดทำงานจนกว่าจะมีโปรเซสอื่นมาปลุกให้ทำงานต่อ

• Wakeup เปน็น system call ที่ปลุกใหโ้โปรเซสทำางานตอ่อ

• Sleep และ Wakeup จะทำ งานสลับกันมีการใช้พารามิเตอร์และแอ็ดเดรสของหน่วยความจำที่สัมพันธ์กัน

ตัวอย่าง Sleep and Wakeup คือ ปัญหาของ Producer-Consumerผู้ผลิต – ผู้บริโภค

• ทั้ง 2 จะใช้ buffer ที่ share ร่วมกันในขนาดคงที่ กำาหนดให้มี

Producer และ Consumer ได้อย่างละ 1 ตัว โดยทำงานดังนี้

– Producer จะทำหน้าที่ผลิตข้อมูลเก็บไว้ใน buffer และหยุดผลิตเมื่อ buffer เต็ม

– Consumer จะนำข้อมูลจาก buffer ไปใช้ ( ใน buffer ต้องมี

ข้อมูลอย่างน้อย 1 ชิ้น ) และหยุดนำข้อมูลออกเมื่อ bufferว่าง

– ดังนั้น Producer จะ sleep เมื่อ buffer เต็ม และ wakeup

เมื่อ Consumer นำข้อมูลไปใช้ เมื่อมีข้อมูลอย่างน้อน 1ชุด ในบัฟเฟอร์

– ดังนั้น Consumer จะ sleep ตัวเอง เมื่อ buffer ว่าง และ

wakeup เมื่อ Producer ผลิตข้อมูล เพื่อนำข้อมูลออกไป

– Sleep เป็นการเปลี่ยนสถานะ Running ไปเป็น Blocked

– Wakeup เป็นการเปลี่ยนสถานะ Blocked ไปเป็นRunning

5. Semaphore

– เป็นตัวแปรจำนวนเต็ม เพื่อนับจำนวน wakeup ที่จะนำไปใช้ใน

อนาคต โดยกำหนดให้

• ค่าเริ่มต้นเป็น 0 --> ไม่มีการwakeup

• ถ้าค่าเป็น + --> มีการwakeup

– จะมี 2 ปฏิบัติการ คือ Down และ Up ทั้ง 2 ปฏิบัติการจะใช้

ตัวแปรร่วมกันคือ s (semaphore เป็นค่า integer)

– ปฏิบัติการ Down ใน Semaphore จะตรวจสอบค่าตัวแปร

• ถ้าค่า s มากว่า 0 จะลดค่า s ลงที่ละ 1 และดำเนินการต่อ

• ถ้าค่า s = 0 ; Process จะ sleep โดยไม่สนใจใด ๆ ทั้งสิ้น

• การตรวจสอบ หรือการเช็คค่า s ลดลง ไปสู่การ sleep นั้น จะถูก

กระทำด้วย คำสั่งที่ไม่สามารถถูกรบกวนได้ (การรบกวนจากการของใช้ s จาก process อื่น) ทำให้ค่า s ถูกใช้เพียงครั้งเดียวจนทุกอย่่างเสร็จสิิ้น เรียกว่่า indivisible automatic action

1. The Dining Philosophers Problem

• เป็นปัญหาในการเกิด Deadlock อันเนื่องมาจากการใช้ทรัพยากรที่มีการใช้ร่วมกัน โดยปัญหาที่เกิดจากการที่นักปราชญ์ได้ล้อมวงทานอาหาร โดยที่ข้างชามจะมีตะเกียบอยู่ 1 อัน ดังรูป

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

• 2. The Readers-Writers Problem

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

• 3. The Sleeping Barber Problem

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

• การแก้ปัญหาส่วนวิกฤติ (The Critical-Section Problem)

• คำตอบสำหรับการแก้ปัญหาส่วนวิกฤติต้อวงเป็นไปตามเงื่อนไขทั้งสามข้อต่อไปนี้

• 1. การกีดกัน (Mutual exclusion) ถ้าโปรเซส Pi กำลังปฏิบัติการอยู่ในส่วนวิกฤติแล้ว ต้องไม่มีโปรเซสอื่นใดกำลังอยู่ในส่วนวิกฤติของโปรเซสเหล่านั้นด้วย นั่นคือ ในขณะใดขณะหนึ่งมีเพียงโปรเซสเดียวเท่านั้นที่อยู่ในส่วนวิกฤติของตน

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

• 3. การรออย่างมีขอบเขต (Bounded waiting) จะต้องมีขอบเขตของเวลาในการรอโดยเริ่มนับตั้งแต่เวลาที่โปรเซสอื่นได้รับอนุญาตให้เข้าสู่ส่วนวิกฤติไปหลังจากมีโปรเซสหนึ่งร้องขอจนมาถึงเวลาที่ระบบทำตามคำร้องขอของโปรเซสนั้น

• โปรเซสที่เข้าสู่ส่วนวิกฤติไม่ได้ในขณะนั้นจะดำเนินการรอต่อไปอย่างไร ทั้งนี้แนวคิดในการแก้ปัญหาโดยทั่วไปมี 2 รูปแบบคือ

•

• 1. การรอแบบไม่ว่าง (preemptive kernels) ในแต่ละโปรเซสมีการกำหนดเงื่อนไขที่ต้องการใช้ในการตรวจสอบก่อนเข้าสู่ส่วนวิกฤติ ซึ่งถ้าหากไม่สามารถผ่านเงื่อนไขนี้ไปได้ โปรเซสไม่สามารถเข้าสู่ส่วนวิกฤติของตนเองได้ และวนเวียนตรวจสอบเงื่อนไขนั้นอยู่ตลอดเวลาจนกว่าจะได้เข่าสู่ส่วนวิกฤติ นั่นคือ ในระหว่างรอโปรเซสนั้นไม่ได้อยู่นิ่งเฉยแต่ยังต้องทำคำสั่งทำซ้ำและทดสอบเงื่อนไขอยู่เรื่องยๆ

• 2. การขัด (nonpreemptive kernels) ในการรอแบบไม่ว่างนั้นไม่ได้ทำให้ระบบเกิดผลงานใดๆ ขึ้นมา จึงการเป็นการใช้วงรอบการทำงานของหน่วยประมวลผลกลางที่ไม่ได้ประโยชน์ และยังต้องแย่งชิงกันเข้าใช้หน่วยประมวลผลกลางระหว่างโปรเซสร่วมงานอื่นๆ ที่กำลังวนลูปรอเข้าสู่ส่วนวิกฤติ รวมทั้งโปรเซสที่เป็นแบบอิสระทั้งหลายในระบบด้วย ดังนั้นจึงได้มีการพัฒนาให้ทำการบล็อกโปรเซสที่ต้องการเข้าสู่ส่วนวิกฤติแต่ยังไม่อาจเข้าได้เนื่องจากมีโปรเซสอื่นกำลังทำงานอยู่

•