L4

COMP3320 - Design Principles of Operating Systems

Lecture 4: Concurrency: Mutual Exclusion and Synchronization

Dr. Ilenius Ildephonce - The UWI, Five Islands

Table of Contents

  1. Introduction

  2. Mutual Exclusion: Software Approaches

  3. Principles of Concurrency

  4. Semaphore

  5. Monitors

  6. Message Passing

  7. Readers/Writers Problem

  8. Conclusion

1. Introduction

  • Multiple Processes

    • Operating System design is focused on managing processes and threads:

      • Multiprogramming: Management of multiple processes on a uniprocessor.

      • Multiprocessing: Management of multiple processes on a multiprocessor system.

      • Distributed Processing: Management of processes across distributed computer systems, often seen in clusters.

2. Mutual Exclusion: Software Approaches

  • Implementations for concurrent processes on single or multiprocessor machines with shared memory.

  • Assumes elementary mutual exclusion at the memory access level:

    • Memory Arbiter: Serializes simultaneous accesses to shared memory, access order unspecified.

    • No specific hardware, OS, or programming language support expected.

Key Algorithms

  • Dijkstra's Algorithm: For mutual exclusion with two processes, inspired by Dekker's method.

3. Principles of Concurrency

  • Interleaving and Overlapping: Examples of concurrent processing presenting challenges in execution speed prediction, influenced by other processes' activities and OS interrupt handling.

Difficulties of Concurrency

  • Sharing Global Resources:

    • Challenges in optimal resource allocation.

    • Hard to trace non-deterministic programming errors.

  • Race Condition: Occurs when processes or threads access shared data, result depends on the order of execution.

4. Semaphore

  • Definition: Integer value used for signaling between processes.

  • Operations:

    1. Initialize

    2. Decrement (semWait)

    3. Increment (semSignal)

  • Binary Semaphore: Only values 0 and 1; ensures mutual exclusion but requires the locking process to release the lock.

  • Structure:

    struct semaphore {  
    int count;  
    queueType queue;  
};

5. Monitors

  • Description: A higher-level synchronization construct; encapsulates access procedures and local data.

  • Characteristics:

    • Only one process can access the monitor at a time.

    • Synchronization uses condition variables (e.g., cwait, csignal).

6. Message Passing

  • Use: For interprocess communication and synchronization in distributed systems.

  • Primitives:

    • Send(destination, message)

    • Receive(source, message)

  • Characteristics: Enables synchronization and mutual exclusion; works with varying communication scenarios and message formats.

7. Readers/Writers Problem

  • Involves processes sharing data, categorized as either readers (who read) or writers (who write).

  • Conditions:

    • Multiple readers can read simultaneously.

    • Only one writer can write at a time; if a writer is writing, no reader can read.

  • Example Implementation:

    void reader() {  
    semWait(x);  
    readcount++;  
    if (readcount == 1) semWait(wsem);  
    semSignal(x);  
    READUNIT();  
    ...  
}

8. Conclusion

  • Summary of key concepts: mutual exclusion, concurrency approaches, semaphore functionality, monitor control, and the readers/writers problem.