程序代写代做代考 Java database algorithm file system data structure Object-Oriented Programming

Object-Oriented Programming

Operating Systems

Lecture 5b

Dr Ronald Grau School of Engineering and Informatics Spring term 2018

Previously

Process Synchronisation

 Inter-Process Communication

 Race conditions

 Communication models

 Critical section

 Software vs. Hardware solutions

 Condition synchronisation

1

Today

Process Synchronisation

 Critical Sections

 Common application problems:

 Producer-Consumer

 Readers-Writers (Lab next week)

 Synchronisation primitives:

 Mutex, Semaphore, Monitor, Condition Variable, . . .

 Transactional Memory

 Message Passing

2

Recap: Synchronisation

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?

3

Recap: 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.

4

Process 1:
entry protocol

x++;

exit protocol

Process 2:
entry protocol

x–;

exit protocol

Critical section

Recap: Critical Section 5

Where is the critical section?

Recap: Critical Section 6

Token-controlled

synchronisation

Recap: Critical Section solutions

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

7

Bakery algorithm (Leslie Lamport 1974)

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

8

Bakery algorithm (Leslie Lamport 1974)

 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)

9

do {
choosing[i] = true;
number[i]=1+max(number[0],…,number[n-1]);
choosing[i]=false;
for(intj=0;j