Lock, Semaphore และ Condition variable

นึกภาพก่อน

• Lock เหมือนห้องน้ำที่มีกลอน: เข้าได้ทีละคน คนข้างในเท่านั้นที่ปลดกลอนได้
• Semaphore เหมือนลานจอดรถที่มีป้ายบอกจำนวนช่องว่าง: รถเข้าลดเลขลงหนึ่ง รถออกเพิ่มหนึ่ง ถ้าเป็นศูนย์ต้องรอ
• Condition variable เหมือนห้องรอเรียกคิว: เข้าไปแล้วพบว่ายังทำสิ่งที่ต้องการไม่ได้ จึง ออกมานั่งรอและคืนกุญแจ จนมีคนมาเรียก

Lock

คุณสมบัติสามข้อ:

1. มีผู้ถือ lock ได้ ไม่เกินหนึ่ง ในเวลาหนึ่ง (safety)
2. ถ้าไม่มีใครถือ acquire จะได้ lock (progress)
3. ถ้าผู้ถือ lock ทุกคนทำเสร็จ และไม่มีผู้รอที่ priority สูงกว่า ผู้รอจะได้ lock ในที่สุด (progress)

ตัวอย่าง: malloc / free

char *malloc (n) {
    heaplock.acquire();
    p = allocate memory
    heaplock.release();
    return p;
}

void free(char *p) {
    heaplock.acquire();
    put p back on free list
    heaplock.release();
}

heap เป็นโครงสร้างข้อมูลที่ทุก thread ใช้ร่วมกัน malloc และ free จึงใช้ lock ตัวเดียวกัน (heaplock) ถ้าใช้ lock คนละตัว thread หนึ่งอาจกำลัง malloc ขณะที่อีก thread free และแก้ free list ชนกัน

กฎการใช้ lock

• lock เริ่มต้นเป็น free
• acquire ก่อน เข้าถึง shared data structure เสมอ — ที่ ต้น procedure
• release หลัง ใช้ shared data เสร็จเสมอ — ที่ ท้าย procedure
• เฉพาะผู้ถือ lock เท่านั้นที่ release ได้ — อย่าโยน lock ให้คนอื่น release
• ห้ามเข้าถึง shared data โดยไม่มี lock — อันตราย

Will this code work?

if (p == NULL) {
    lock.acquire();
    if (p == NULL) {
        p = newP();
    }
    lock.release();
}
use p->field1

newP() {
    p = malloc(sizeof(p));
    p->field1 = …
    p->field2 = …
    return p;
}

รูปแบบนี้เรียกว่า double-checked locking: ตรวจนอก lock ก่อนเพื่อไม่ต้องเสียเวลา acquire ถ้า p ถูกสร้างแล้ว

ไม่ถูก เพราะบรรทัดแรก if (p == NULL) อ่าน shared data โดยไม่ถือ lock ซึ่งผิดกฎข้อสุดท้าย ใน newP ตัวแปร p ถูกกำหนดค่าตั้งแต่บรรทัดแรก ก่อนที่ field1 จะถูกตั้งค่า thread อื่นที่ตรวจอยู่นอก lock จึงเห็น p != NULL แล้วข้ามไปใช้ p->field1 ที่ยังไม่มีค่า และต่อให้เขียน newP ใหม่ให้กำหนด p เป็นบรรทัดสุดท้าย compiler/CPU ก็ยังเรียงคำสั่งใหม่ได้ (ดูเรื่อง reordering ในบทก่อน)

Semaphore

semaphore มีค่าเป็น จำนวนเต็มไม่ติดลบ

semaphore เหมือนจำนวนเต็ม ยกเว้น:

• มี operation แค่ P กับ V — อ่านค่าตรง ๆ ไม่ได้
• operation เป็น atomic

ถ้าค่าเป็น 1 แล้วมี P สองครั้ง ผลคือค่า 0 และมีผู้รอหนึ่งตัว

semaphore เหมาะกับ unlocked wait: interrupt handler และ fork/join

ไล่ค่า semaphore

เริ่มที่ค่า 1 มี thread A, B, C:

semaphore ที่เริ่มด้วย 1 จึงทำหน้าที่เหมือน lock: P = acquire, V = release ค่าไม่เคยติดลบ

Condition variable

ใช้สำหรับ รออยู่ภายใน critical section — เรียกได้เฉพาะตอนถือ lock อยู่

Design pattern

methodThatWaits() {
    lock.acquire();
    // Pre-condition: State is consistent
    // Read/write shared state
    while (!testSharedState()) {
        cv.wait(&lock);
        // WARNING: shared state may have changed
    }
    // Read/write shared state
    lock.release();
}

methodThatSignals() {
    lock.acquire();
    // Pre-condition: State is consistent
    // Read/write shared state

    // If testSharedState is now true
    cv.signal(&lock);
    // NO WARNING: signal keeps lock

    // Read/write shared state
    lock.release();
}

กฎของ condition variable

1. ถือ lock เสมอเมื่อเรียก wait, signal, broadcast

condition variable เป็น synchronization สำหรับ shared state และต้องถือ lock เสมอเมื่อเข้าถึง shared state

2. Condition variable ไม่มีความจำ (memoryless)

• signal ตอนไม่มีใครรอ = ไม่เกิดอะไร (no-op)
• wait ก่อนแล้วค่อยมี signal = ผู้รอตื่น

3. wait ปล่อย lock แบบ atomic

สไลด์ถามว่าถ้าไม่ atomic จะเป็นอย่างไร:

• wait ก่อน แล้วค่อย release: thread หลับไปทั้งที่ยังถือ lock ไม่มีใคร acquire ได้ จึงไม่มีใครเข้าไปเปลี่ยน state และ signal ได้เลย → รอตลอดกาล
• release ก่อน แล้วค่อย wait: ในช่องว่างระหว่างสองคำสั่ง thread อื่นอาจ acquire, เปลี่ยน state แล้ว signal — ซึ่งไม่มีผลเพราะยังไม่มีใครรอ (ข้อ 2) จากนั้น thread แรกค่อยหลับ และพลาด signal นั้นไปตลอด (lost wakeup)

4. wait ต้องอยู่ใน while loop เสมอ

while (needToWait()) {
    condition.Wait(lock);
}

thread ที่ถูกปลุกจาก wait อาจไม่ได้ทำงานทันที: signal/broadcast แค่ย้าย thread ไป ready list และเมื่อ lock ถูกปล่อย ใครก็อาจ acquire ได้ก่อน กว่า thread ที่ถูกปลุกจะได้ lock เงื่อนไขอาจกลับเป็นเท็จไปแล้ว จึงต้องตรวจซ้ำ ซึ่ง while ทำให้เอง ส่วน if ไม่ทำ

ตัวอย่างไล่ทีละขั้น

คิวที่มีของ 0 ชิ้น thread C1 และ C2 ต้องการหยิบของ thread P ใส่ของ 1 ชิ้น โดยผู้หยิบเขียนว่า if (empty) cv.wait(&lock); (ผิด)

1. C1 acquire, เห็นว่าว่าง, wait → ปล่อย lock และหลับ
2. P acquire, ใส่ของ 1 ชิ้น, signal → C1 ย้ายไป ready list (ยังไม่ได้ lock), P release
3. C2 มาถึงก่อน acquire ได้ เห็นว่าไม่ว่าง หยิบของไป release
4. C1 ได้ lock และ return จาก wait → ใช้ if จึงไม่ตรวจซ้ำ → หยิบจากคิวที่ ว่าง → พัง

ถ้าเป็น while (empty) cv.wait(&lock); ที่ขั้น 4 C1 จะตรวจซ้ำ เห็นว่าว่าง แล้ว wait ต่ออย่างถูกต้อง

ใน C#

// Lock
static object _Lock = new object();
lock (_Lock)
{
    …
}

// Condition variable
lock (_Lock)
{
    …
    Monitor.Wait(_Lock);
    // or
    Monitor.Pulse(_Lock);
    Monitor.PulseAll(_Lock);
    …
}

// Semaphore
Semaphore s = new Semaphore(1, 1);
s.WaitOne();   // P()
…
s.Release();   // V()

เทียบสามเครื่องมือ

จุดที่มักพลาด

1. ใช้ if แทน while รอบ wait

ผิดเสมอ ต่อให้ "ดูเหมือน" มีผู้รอคนเดียว

2. คิดว่า signal ส่ง lock ให้ผู้ถูกปลุก

ไม่ใช่ ผู้ signal ยังถือ lock ต่อ ผู้ถูกปลุกไป ready list และต้องแย่ง lock เอง

3. คิดว่า signal ถูกเก็บไว้ถ้าไม่มีใครรอ

condition variable ไม่มีความจำ ต่างจาก semaphore ที่ V ถูกจำไว้ในค่า

4. คิดว่าค่า semaphore ติดลบได้

ไม่ได้ P จะรอจนค่า > 0 ก่อนลด

5. ให้ thread อื่น release lock แทน

เฉพาะผู้ถือเท่านั้นที่ release ได้

6. อ่าน shared data นอก lock "เพราะแค่อ่าน"

การอ่านก็ต้องถือ lock (ตัวอย่าง double-checked locking)

ที่มา: 05-Synchronization-part1_v2.pdf หน้า 12–21 · 05-Synchronization-part4-Conclusion_v2_1.pdf หน้า 3–5