代写 data structure algorithm Java MPI operating system database software security Operating Systems Lecture 5b

Operating Systems Lecture 5b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018

Previously 1 Process Synchronisation
 Inter-Process Communication  Race conditions
 Communication models
 Critical section
 Software vs. Hardware solutions  Condition synchronisation

Today 2 Process Synchronisation
 CriticalSections
 Commonapplicationproblems:  Producer-Consumer
 Readers-Writers (Lab next week)
 Synchronisationprimitives:
 Mutex, Semaphore, Monitor, Condition Variable, . . .  Transactional Memory
 Message Passing

Recap: Synchronisation 3 Questions
 What are mechanisms with which processes can communicate with each other?  Which problem can occur when processes communicate via shared memory?  What is mutual exclusion?
 What is busy waiting?
 What is condition synchronisation?
 What is an example of a hardware-supported synchronisation primitive?

Recap: Critical Section 4
Process 1:
entry protocol
x++;
exit protocol
Critical section
 Mutual exclusion: If a process is executing in its critical section, then other processes must not execute in their critical section.
 Progress (Prevent deadlock): If no process is executing in its critical section and some processes wish to enter their critical sections, then the selection of which process may enter cannot be postponed indefinitely.
 Bounded waiting (Prevent starvation): If a process wishes to enter the critical section then only a bounded number of processes may enter the critical section before it.
Process 2:
entry protocol
x–;
exit protocol

Recap: Critical Section 5 Where is the critical section?

Recap: Critical Section 6
Token-controlled synchronisation

Recap: Critical Section solutions 7 Software
 Assume atomicity of read and write operations Hardware-supported
 More powerful instructions (e.g. test-and-set) Higher-level APIs
 Wrap low-level primitives into library: Semaphores, monitors, condition variables, etc
 Thread-safe data structures:
Blocking queues, synchronised maps, etc

Bakery algorithm (Leslie Lamport 1974) 8 How does it work?
 Customers draw a ticket as they arrive
 The ticket has a number that indicates when it is the customer’s turn to be served
 When translated to operating systems, the processes are the customers

Bakery algorithm (Leslie Lamport 1974) 9
 We have n processes
 Shared variables: boolean[n] choosing; int[n] number;
 There is a chance that tickets may have the same number
 if number == 0 for any process, then that process does not request entering the critical section (already in it)
 Instead of keeping busy waiting, the current thread can also yield the CPU to the next thread (Cooperative multithreading)
do {
choosing[i] = true; number[i]=1+max(number[0],…,number[n-1]); choosing[i]=false;
for(intj=0;j