Process synchronization คือเทคนิคแก้ปัญหาการเข้าถึงข้อมูลร่วมกันแบบ concurrent ที่อาจทำให้ข้อมูลไม่สอดคล้อง (data inconsistency) กระบวนการร่วมมือ (Cooperating process) คือกระบวนการที่ส่งผลหรือได้รับผลจากกระบวนการอื่น นำไปสู่ inconsistency จึงต้องมี synchronization
The Critical-Section Problem (ปัญหาส่วนสำคัญ)
ทุกกระบวนการมีส่วนโค้ดสำรองไว้ เรียกว่า Critical Section ในส่วนนี้ เปลี่ยนตัวแปรร่วม อัปเดตตาราง เขียนไฟล์ ฯลฯ จุดสำคัญ: เมื่อกระบวนการหนึ่งอยู่ใน critical section กระบวนการอื่นไม่เข้าได้ แต่ละกระบวนการต้องขออนุญาตก่อนเข้า ส่วนโค้ดที่ทำหน้าที่นี้คือ Entry Section ส่วนท้ายคือ Exit Section ส่วนที่เหลือคือ Remainder Section
เงื่อนไข 3 ข้อสำหรับ Critical Section:
- Mutual Exclusion (การขับ逐แบบ Mutex) - กระบวนการหนึ่งอยู่ใน CS อีกตัวไม่เข้าได้
- Progress (ความก้าวหน้า) - ไม่มีกระบวนการใน CS และมีกระบวนการรอเข้า เฉพาะกระบวนการที่ไม่อยู่ใน remainder section ถึงขอเข้าได้ การเลือกอาจเลื่อนได้ไม่จำกัด
- Bounded Waiting (การรอที่มีขอบเขต) - มีขีดจำกัดจำนวนครั้งที่กระบวนการเข้า CS ได้ หลังจากขอเข้าและก่อนได้รับอนุญาต
2 แนวทางใน OS:
- Preemptive Kernel - อนุญาตให้ preempt กระบวนการขณะรันใน kernel mode
- Non-Preemptive Kernels - ไม่อนุญาตให้ preempt ใน kernel mode
Peterson's Solution
Classic software solution สำหรับ 2 กระบวนการ สลับทำงานระหว่าง CS และ remainder ต้องการ shared data 2 ตัว:
- int turn;
- boolean flag[2];
turn บอกว่าเป็นตาของใคร flag[j] = true หมายถึงกระบวนการ j พร้อมเข้า CS
Synchronization Hardware
ใช้ instruction 2 แบบ: TestAndSet() และ swap()
TestAndSet(): ตัวแปรร่วม lock (0=unlocked, 1=locked) กระบวนการตรวจสอบ lock ก่อนเข้า CS
Semaphores
Semaphore คือ synchronization tool แก้ปัญหาจาก TestAndSet/Swap เป็นตัวแปร int เข้าถึงผ่าน wait() และ signal()
wait(S) { while S <= 0; S--; }
signal(S) { S++; }
2 ประเภท: Counting Semaphore (ค่าไม่จำกัด) และ Binary Semaphore (0 หรือ 1) เรียกว่า Mutex Locks
