Transcript Module 7: Process Synchronization

Operating Systems
Lecture 23
Classic Synchronization Problems
Operating System Concepts
7.1
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
The Bounded Buffer Problem
 Two processes access the same buffer, which
is of finite size.
 The Producer writes to the buffer.
 The Consumer reads from the buffer.
 The two processes should not access the
buffer at the same time to avoid creating
inconsistent data.
Operating System Concepts
7.2
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Bounded-Buffer Problem
 Assume n buffer slots for data
 Shared data
semaphore full, empty, mutex;
Initially:
full = 0, empty = n, mutex = 1
Operating System Concepts
7.3
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Bounded-Buffer Problem Producer Process
do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);
Operating System Concepts
7.4
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Bounded-Buffer Problem Consumer Process
do {
wait(full);
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);
Operating System Concepts
7.5
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
The Readers-Writers Problem
 Several processes share a buffer for reading and
writing.
 Some processes (readers) only read from the buffer.
 Some processes (writers) write to the buffer (and may
also read).
 Readers can access the buffer at the same time as
other readers without problem.
 No other processes can be allowed to access the
buffer at the same time as a writer, to avoid creating
inconsistent data.
Operating System Concepts
7.6
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Readers-Writers Problem
 Shared data
semaphore mutex, wrt;
int readcount;
Initially
mutex = 1, wrt = 1, readcount = 0
Writer's code:
wait(wrt);
…
writing is performed
…
signal(wrt);
Operating System Concepts
7.7
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Readers-Writers Problem Reader Process
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex):
Questions: Which processes does this favor (readers or
writers)?
What potential problem does this algorithm have?
Operating System Concepts
7.8
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Dining-Philosophers Problem
 Philosophers are seated around a table.
 They alternate thinking and eating.
 One chopstick is placed in between each pair of philosophers.
 A philosopher needs the chopsticks on both sides to eat.
 A philosopher can only pick up one chopstick at a time.
 We want to guarantee that we don't generate deadlock.
 We want to guarantee that no philosopher starves.
Operating System Concepts
7.9
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Dining-Philosophers Problem
 Shared data
semaphore chopstick[5];
Initially all values are 1
 Philosopher i:
Operating System Concepts
do {
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);
Silberschatz, Galvin and Gagne 2002
7.10
Modified for CSCI 399, Royden, 2005
Dining-Philosophers Problem
Deadlock: If all philosophers decide to eat at the same
time and pick up the chopstick on their left. None will be
able to pick up a chopstick on their right.
Possible Solutions:
1)Allow at most 4 philosophers at the table
2)Allow philosopher to pick up chopsticks only if both
available.
3)Odd philosophers pick up left first then right.
Even philosophers pick up right first then left.
Starvation: A philosopher may never have access to two
chopsticks if the philosophers next to him are always
eating.
Operating System Concepts
7.11
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Project Description
 Write a CPU simulator to run scheduling
algorithms:
 FCFS (first come first serve)
 SRTN (shortest remaining time next)
 Collect statistics:
 CPU utilization
 Time to execute all processes
 Service time
 I/O time
 Turnaround time for each process
Operating System Concepts
7.12
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Next Event Model
 Simulation state can change only at event times
 An event is an occurrence that may change the state of
the system.
 Process arrival
 Change of process state (e.g. interrupt at end of time
slice changes process state from running to ready)
 When an event occurs, the clock is advanced to the next
time.
 An event queue is used to schedule events.
 Main loop:
 Process next event
 Perhaps add future events to the queue
 Advance the clock
Operating System Concepts
7.13
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Part 1: Writing a Driver
 The driver should do three things:
 Determine which flags have been provided as arguments.
 Read in the data from the input file.
 Call the function stub for the appropriate scheduling algorithm.
 Dealing with flags:
sim [-d] [-v] [-a algorithm] < input_file
Flags will always be in order, but may not all be present.
Example:
%sim -d < input_file
%sim -a FCFS < input_file
Note that the input is redirected from a file. How will you
read that input in your program?
Operating System Concepts
7.14
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Dealing with flags
 Use argc to figure out how many flags or
arguments
 Use argv to figure out what they are.
 Note: 2 arguments (argc == 3) could mean
two flags, -d -v, or one flag and algorithm, -a
FCFS.
 Write the code for this first.
 Test it extensively.
Operating System Concepts
7.15
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Input Format
 First line of file: number_processes switch_time
 Next lines of file: Set of lines for each process:
 First line:
process_num arrival_time num_CPU_bursts
 Next lines:
burst_number CPU_time IO_time
 Last line:
burst_number CPU_time
 Repeated for each process in input file
Operating System Concepts
7.16
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Sample Input
INPUT
4 5
1 0
1 15
2 18
3 15
4 14
5 25
6 240
2 12
1 4
2 30
3 90
4 15
. . .
Operating System Concepts
6
400
200
100
400
100
4
150
50
75
MEANING
4 processes, switch_time = 5
Process 1, arrival time 0, 6 bursts
Burst 1, CPU time 15, IO time 400
Burst 2, CPU time 18, IO time 200
Last burst, no I/O
Process 2, arrival time 12, 4 bursts
7.17
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Things to think about
What data structure(s) will you use to store the process
information?
What parameters need to be passed to the function stubs
that will run the schedule simulations?
Event Queue:
event.cc allows you to get next event and update the time.
You can also insert new events in the correct order.
How will you build the initial event queue from the process
information?
Look at event.h, list.h.
(We will discuss this more later).
Operating System Concepts
7.18
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005