Transcript Powerpoint format

Teaching Operating
Systems With
Programming and
Freeware
Lecture 2: Concurrency Issues, processor scheduling (Lab2 and 3)
A workshop by
Dr. Junaid Ahmed Zubairi
Visiting Associate Professor
CIT, Agriculture University, Rawalpindi
Workshop Overview
Operating Systems Course Outline
Topics Suited for Programming Assignments
Process Model and IPC (Lab1)
Concurrency Issues (Lab2)
Processor Scheduling (Lab3)
Disk Scheduling and RAID
Programming Project
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Concurrency
Concurrent processing involves a set of
two or more processes that run at the
same time (apparently or physically)
Multiple applications run concurrently
through Multiprogramming whereas a
structured application may be a set of
concurrent processes
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Difficulties with
Concurrency
Sharing global resources with read/write
permissions
Management of allocation of resources
to avoid starvation and deadlocks
Programming errors become difficult to
locate (and fix)
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
A Simple Example
void echo()
{
chin = getchar();
chout = chin;
putchar(chout);
}
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
A Simple Example
Process P1
Process P2
.
.
chin = getchar();
.
.
chin = getchar();
chout = chin;
chout = chin;
putchar(chout);
.
.
putchar(chout);
.
.
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Operating System
Concerns
Keep track of active processes
Allocate and deallocate resources




Processor time
Memory
Files
I/O devices
Protect data and resources
Result of process must be independent of the
speed of execution of other concurrent
processes
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Process Interaction
Processes unaware of each other
Processes indirectly aware of each
other
Process directly aware of each other
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Competition Among
Processes for
Resources
Mutual Exclusion

Critical sections
Only one program at a time is allowed in its
critical section
 Example only one process at a time is allowed
to send command to the printer

Deadlock
Starvation
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Cooperation Among
Processes by Sharing
Writing must be mutually exclusive
Critical sections are used to provide
data integrity
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Cooperation Among
Processes by
Communication
Messages are passes

Mutual exclusion is not a control
requirement
Possible to have deadlock

Each process waiting for a message from
the other process
Possible to have starvation

Two processes sending message to each
other while another process waits for a
message
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Requirements for Mutual
Exclusion
Only one process at a time is allowed in
the critical section for a resource
A process that halts in its non-critical
section must do so without interfering
with other processes
No deadlock or starvation
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Requirements for Mutual
Exclusion
A process must not be delayed access
to a critical section when there is no
other process using it
No assumptions are made about
relative process speeds or number of
processes
A process remains inside its critical
section for a finite time only
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
First Attempt
Busy Waiting
Process is always checking to see if it can
enter the critical section
 Process can do nothing productive until it
gets permission to enter its critical section

Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Second Attempt
Each process can examine the other’s status
but cannot alter it
When a process wants to enter the critical
section it checks the other processes first
If no other process is in the critical section, it
sets its status for the critical section
This method does not guarantee mutual
exclusion
Each process can check the flags and then
proceed to enter the critical section at the
same
time
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Third Attempt
Set flag to enter critical section before
checking other processes
If another process is in the critical section
when the flag is set, the process is blocked
until the other process releases the critical
section
Deadlock is possible when two process set
their flags to enter the critical section. Now
each process must wait for the other process
to release the critical section
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Fourth Attempt
A process sets its flag to indicate its
desire to enter its critical section but is
prepared to reset the flag
Other processes are checked. If they
are in the critical region, the flag is reset
and later set to indicate desire to enter
the critical region. This is repeated until
the process can enter the critical region.
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Fourth Attempt
It is possible for each process to set
their flag, check other processes, and
reset their flags. This scenario will not
last very long so it is not deadlock. It is
undesirable
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Correct Solution
Each process gets a turn at the critical
section
If a process wants the critical section, it
sets its flag and may have to wait for its
turn
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Mutual Exclusion:
Hardware Support
Special Machine Instructions
Performed in a single instruction cycle
 Not subject to interference from other
instructions
 Reading and writing
 Reading and testing

Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Mutual Exclusion:
Hardware Support
Test and Set Instruction
boolean testset (int i) {
if (i == 0) {
i = 1;
return true;
}
else {
return false;
}
}
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Mutual Exclusion:
Hardware Support
Exchange Instruction
void exchange(int register,
int memory) {
int temp;
temp = memory;
memory = register;
register = temp;
}
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Mutual Exclusion
Machine Instructions
Advantages
Applicable to any number of processes on
either a single processor or multiple
processors sharing main memory
 It is simple and therefore easy to verify
 It can be used to support multiple critical
sections

Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Mutual Exclusion
Machine Instructions
Disadvantages
Busy-waiting consumes processor time
 Starvation is possible when a process
leaves a critical section and more than one
process is waiting.
 Deadlock


If a low priority process has the critical region
and a higher priority process needs it , the
higher priority process will obtain the processor
to wait for the critical region
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Semaphores
Special variable called a semaphore is
used for signaling
If a process is waiting for a signal, it is
suspended until that signal is sent
Wait and signal operations cannot be
interrupted
Queue is used to hold processes
waiting on the semaphore
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Semaphores
Semaphore is a variable that has an
integer value
May be initialized to a nonnegative number
 Wait operation decrements the semaphore
value
 Signal operation increments semaphore
value

Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Wait Pseudocode
struct semaphore {
int count;
queueType queue;
}
void wait(semaphore s)
{
s.count--;
if (s.count < 0)
{
place this process in s.queue;
block this process
}
}
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Signal Pseudocode
void signal(semaphore s)
{
s.count++;
if (s.count <= 0)
{
remove a process P from s.queue;
place process P on ready list;
}
}
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Semaphore Example
Semaphore door=1;
Process p1 executes wait (door), the
final value of door=0 and p1 enters the
critical section
Process p2 now executes wait (door),
the value of door = -1 and p2 is blocked
outside the critical section
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Semaphore Example
Process p1 completes its critical section
and executes signal (door), thus
incrementing door to 0. When a signal
operation results in a value less than
the initial value (1), it means some
processes are sleeping on this
semaphore. Thus the system will wake
up the process at the head of the queue
(i.e. p2)
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Using BACI
BACI (Ben-Ari Concurrent Interpreter) is
developed to help in teaching concurrency
Obtain and install BACI from
http://www.mines.edu/fs_home/tcamp/baci/
BACI supports C, Pascal and C++
It is originally based on Pascal
BACI uses some special concurrent
constructs
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Using BACI
Multiple blocks can be run concurrently
by using cobegin {…} construct
cobegin construct appears in the main
function and all processes listed within
cobegin{…} start running at the same
time
BACI includes semaphores, binary
semaphores and monitors
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Using BACI
initialsem(sem,int) initializes the semaphore
sem to the value int
p(sem) and wait(sem) calls decrement sem
by one if sem is greater than zero and block
the caller if sem is already zero
v(sem) or signal(sem) calls increment sem by
1 or wake up a process if sem is found to be
zero
empty(sem) returns true if there are no
processes waiting on sem and false
otherwise
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Using BACI
atomic keyword: if a function is defined as atomic,
then the function is non-preemptible.
void suspend ( void ): puts the calling thread to
sleep.
void revive ( int process_id ): revives the process
with the given id.
int which_proc( void ): returns the process number
of the current thread.
int random (int range): returns a "randomly chosen"
integer between 0 and range -1, inclusive
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Example Source Code
semaphore door;
void coordinate() {
initialsem(door,1);
}
void myturn() {
int ct;
wait(door);
cout<<"MANGO: My turn is now\n";
signal(door);
}
void yourturn() {
wait(door);
cout<<"APPLE: No it is my turn\n";
signal(door);
Operating Systems Workshop CIT, Arid Agriculture University
Aug 2002
Example Source Code
void theirturn() {
wait(door);
cout<<"ORANGE: No it is now my game\n";
signal(door);
}
void main() {
coordinate();
cobegin {
myturn();
yourturn();
theirturn();
}
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
How to Run the Program
Enter and save the sample source code
in a file whose name ends in .cm
Use “bacc filename” to compile and
obtain a pcode file whose name ends in
.pco
Run the interpreter by using “bainterp
filename”
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Programming
Assignment 1 Lab 2
Modify the example program by defining
a global variable int count. The critical
section in each function will modify the
count based on user input. Show , with
displayed messages, how one process
acquires the critical section and the
other process blocks for the critical
section
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Barbershop Problem
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Barbershop Problem
The number of barber chairs is 3 so the
semaphore chair will be initialized to 3
Only four customers can sit on the sofa so the
semaphore sofa will be initialized to 4
Complete the barbershop program (limit
chairs to 1, sofa to 3, customers to 5 and
barbers to 1)
Use messages to see what is going on and
don’t panic on barber’s deadlock condition as
far as it does not stop the customers from
getting haircut
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Readers/Writers
Problem
Any number of readers may
simultaneously read the file
Only one writer at a time may write to
the file
If a writer is writing to the file, no reader
may read it
It is left as an exercise problem for the
participants
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Processor Scheduling
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Short-Term Scheduling
Known as the dispatcher
Executes most frequently
Invoked when an event occurs
Clock interrupts
 I/O interrupts
 Operating system calls
 Signals

Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Decision Mode
Nonpreemptive

Once a process is in the running state, it will
continue until it terminates or blocks itself for I/O
Preemptive


Currently running process may be interrupted and
moved to the Ready state by the operating system
Allows for better service since any one process
cannot monopolize the processor for very long
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Process Scheduling
Example
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
First-Come-First-Served
(FCFS)
0
5
10
15
20
1
2
3
4
5
Each process joins the Ready queue
When the current process ceases to execute,
the oldest process in the Ready queue is
selected
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
First-Come-First-Served
(FCFS)
A short process may have to wait a very
long time before it can execute
Favors CPU-bound processes

I/O processes have to wait until CPUbound process completes
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Round-Robin
0
5
10
15
1
2
3
4
5
Uses preemption based on a clock
An amount of time is determined that allows
each process to use the processor for that
length of time
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
20
Round-Robin
Clock interrupt is generated at periodic
intervals
When an interrupt occurs, the currently
running process is placed in the read
queue

Next ready job is selected
Known as time slicing
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Shortest Process Next
0
5
10
15
1
2
3
4
5
Nonpreemptive policy
Process with shortest expected processing
time is selected next
Short process jumps ahead of longer
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
processes
20
Shortest Process Next
Predictability of longer processes is
reduced
If estimated time for process not correct,
the operating system may abort it
Possibility of starvation for longer
processes
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Shortest Remaining
Time
0
5
10
15
20
1
2
3
4
5
Preemptive version of shortest process
next policy
Must estimate processing time
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Highest Response Ratio
Next (HRRN)
0
5
10
15
1
2
3
4
5
Choose next process with the lowest
ratio
time spent waiting + expected service time
expected service time
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
20
Feedback
0
5
10
15
1
2
3
4
5
Penalize jobs that have been running
longer
Don’t know remaining time process
needs to execute
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
20
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Traditional
UNIX Scheduling
Multilevel feedback using round robin
within each of the priority queues
Priorities are recomputed once per
second
Base priority divides all processes into
fixed bands of priority levels
Adjustment factor used to keep process
in its assigned band
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Programming
Assignment Lab3
Use the sample code provided to
generate random numbers and store
them in an array. These numbers are
assumed to indicate the length of a
process
Use FCFS and SPN to display which
process will be scheduled next
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002
Sample Code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void main(void)
{
const int MAX_LIMIT=55;
int key;
srand( (unsigned)time( NULL ) );
key = rand()%MAX_LIMIT;
printf("%d\n",key);
}
Operating Systems Workshop CIT, Arid Agriculture University Aug 2002