Operating Systems Chapter 5: Concurrency and Synchronization

Operating System Design and Concurrency

• Operating System design is concerned with the management of processes and threads
• Multiple applications are invented to allow processing time to be shared among active applications
• Structured Applications are an extension of modular design and structured programming

Operating System Structure

• Operating Systems themselves are implemented as a set of processes or threads
• Interleaving and overlapping can be viewed as examples of concurrent processing

Difficulties of Concurrency

• Sharing of global resources
• Difficulty for the OS to manage the allocation of resources optimally
• Difficulty in locating programming errors as results are not deterministic and reproducible
• Occurs when multiple processes or threads read and write data items
• The final result depends on the order of execution

Operating System Concerns

• Design and management issues raised by the existence of concurrency
• The OS must be able to:
  • Manage the allocation of resources
  • Prevent interference between processes
  • Ensure that the processes and outputs are independent of the processing speed

Mutual Exclusion

• Mutual exclusion is necessary to ensure that only one process or thread can access a shared resource at a time
• Implemented using binary semaphores or other mechanisms
• A solution to the bounded-buffer producer/consumer problem using semaphores is shown in Figure 5.13

Semaphores

• A semaphore is a variable that has an integer value upon which only three operations are defined:
  • Initialize to a nonnegative integer value
  • Decrement the value (semWait)
  • Increment the value (semSignal)
• There is no way to inspect or manipulate semaphores other than these three operations
• Consequences of using semaphores:
  • No way to know before a process decrements a semaphore whether it will block or not
  • No way to know which process will continue immediately on a uniprocessor system when two processes are running concurrently
  • Don't know whether another process is waiting, so the number of unblocked processes may be zero or one

Message Passing

• Message passing is one approach to providing both synchronization and communication
• Works with distributed systems and shared memory multiprocessor and uniprocessor systems
• The actual function is normally provided in the form of a pair of primitives:
  • send (destination, message)
  • receive (source, message)
• A process sends information in the form of a message to another process designated by a destination
• A process receives information by executing the receive primitive, indicating the source and the message
• Both sender and receiver are blocked until the message is delivered

Non-Blocking Send and Receive

• Non-blocking send, blocking receive: sender continues on but receiver is blocked
• Non-blocking send, non-blocking receive: neither party is required to wait

Mutual Exclusion Using Message Passing

• A solution to the bounded-buffer producer/consumer problem using messages is shown in Figure 5.21

Readers/Writers Problem

• A data area is shared among many processes
• Some processes only read the data area (readers) and some only write to the data area (writers)
• Conditions that must be satisfied:
  • No reader can access the data area while a writer is accessing it
  • No writer can access the data area while a reader is accessing it
  • No writer can access the data area while another writer is accessing it

Test your knowledge on Operating System design principles, focusing on concurrency, mutual exclusion, and synchronization. Learn about multiprogramming, multiprocessing, and distributed processing in this chapter 5 quiz from William Stallings' Seventh Edition.