Solutions
Question1 solution
i. First Come,
First Served.
First come, first served (FCFS) is a simple non-preemptive scheduling algorithm
that is only suitable for non-interactive batch systems. It isn't appropriate
for an interactive system because it allows for arbitrarily long delays
before responding to user input. (For example, if the CPU is allocated to
process A, it can keep using it indefinitely, despite the fact that a user
is providing input to process B.) For this reason, it isn't reasonable to
try to measure its performance with respect to response time (RT), which
is only an appropriate performance measure for interactive systems - RT
measures how quickly the system responds to user input.
On the other hand, turnaround time (TT) is an appropriate performance measure
for non-interactive systems but not for interactive ones. In a non-interactive
system, we can consider the the time it takes to get jobs done and, in many
cases, doing more jobs more quickly is better. In an interactive system,
however, TT will be dependent on user responses and the speed and order of
them. This means that measuring TT in an interactive system is not reasonable.
For these reasons, measuring TT for FCFS is reasonable, even thought it will
not perform well on this measure.
ii. Shortest Job Next.
As with FCFS, shortest job next (SJN) is a non-preemptive scheduling algorithm
that is only suitable for batch (non-interactive) systems and for the same
reason. The same logic that we applied to FCFS can be applied to SJN to
determine that it is reasonable to use TT as a performance measure with
SJN but that RT is not a reasonable performance measure to use.
iii. Earliest Deadline First Scheduling.
The earliest deadline first scheduling strategy is used for real time systems,
where TT & RT are irrelevant. What is important in real time systems
is that deadlines are met. To try to use either TT or RT in this case is
not reasonable.
iv. Round Robin.
Round robin (RR) is a preemptive scheduling strategy that can be used in
both interactive and non-interactive batch systems. When it is used in an
interactive system, RT is reasonable to measure, even though RR will not
do well in that regard as compared to a priority scheduling strategy with
higher priorities for interactive processes. When it is used in a batch system,
it is reasonable to measure TT.
v. Priority Scheduling using Multi-Level Queues.
Priority scheduling using multi-level queues is another preemptive scheduling
strategy that can be used in both interactive and non-interactive batch
systems. As with RR, therefore, both RT and TT are reasonable performance
measures to use.
Question 2 - solution
A. There are two equally valid ways to answer this question, depending
on whether you are thinking of direct communication:
A process cannot read from any environment except its own, so there is
no way for a child process to (directly) receive information from its parent's
environment.
If the parent sets its environment before forking and the child reads from
its environment, then the parent is using its own environment to (indirectly)
communicate information to a child process. This is because, when the fork
happens, the OS makes a copy of the parent's environment that is given to
the child and from which the child will subsequently read.
B. As with part A, there are two equally valid ways to answer this question,
depending on whether you are thinking of direct communication:
A process cannot modify the environment of another process, so it is not
possible for a process to use an environment belonging to one of its children
to (directly) communicate with that child.
If the parent sets its environment before forking and the child reads from
its environment, then the parent is (indirectly) using the child's environment
to communicate information to a child process. This is because, when it
forks, the parent process is requesting that the OS create the child's environment
as a copy of the parent's environment. That copy is given to the child and
the child will subsequently read from it.
C. Regardless of whether you are thinking of direct or indirect communication,
there are no circumstances under which a process can use its own environment
to communicate information to its parent process. The parent cannot read
the child's environment, nor can the child request that the OS modify or
set its parent's environment based on the child's environment.
D. As with part C, regardless of whether you are thinking of direct or
indirect communication, there are no circumstances under which a process
can use its parent's environment to communicate information to its parent
process. The child process cannot modify its parent's environment, nor can
it request that the OS modify or set its parent's environment on the child's
behalf.
Question 3 - solution
The remainder of the output of the code is likely to be:
My process ID is 31266
My process ID is 31266
My process ID is 31266
.
.
.
The same line will be printed over and over until the process is halted
(e.g., if the user interrupts process execution by pressing ctrl+c).
The reason: When execl is called in this code, it starts executing the
same code from the beginning. Thus, the same data is initialized every time
execl is called.
Many students thought that the output of the code will like be something
along the lines of:
My process ID is 31267
My process ID is 31268
My process ID is 31269
.
.
.
This is wrong because exec-family functions do not create new processes
(new processes are created using fork) and only new processes have different
process ID numbers. Because exec-family functions simply continue the same
process, the process ID number (and many other elements of the process control
block) remain unchanged. This is true even if they are used to run different
code, which is how they are generally used.
Some students also thought that the execl call would fail because fork
was not called first. This is also wrong. We often use fork before calling
an exec-family function, in order to have a new process accomplish something
on behalf of an existing process. However, it is important to know that
this is just a common way of doing things - there is nothing manditory about
it. If the code of the existing process is done with what it needs to do,
there is no reason for it to fork before calling execl, Instead, it can
call execl, which throws away the old (completed) code and replaces it with
the new code. (In this question, the old and new code were simply the same
code.)
Question 4 - solution
Method:
o Update 'count' within a critical section
o Busy wait on count (outside the critical section) until it reaches 0
Initialization:
count = N; // initial count
lock = 0; // free lock
Each Process:
R0 <-- 1; // get lock
L1: R0 <--> lock;
if R0!=0 goto L1;
// begin critical section
R1 <-- count; // update count
decr R1;
R1 --> count;
R0 <-- 0;
R0 --> lock; // release lock
// end critical section
L2: R1 <-- count; // wait for 0 count
if R1!=0 goto L2;
...
Question 5 - solution
A. Assume every process is blocked
with one less than its maximum allocation.This leaves 1 resource unit which
will unblock 1 process. When it finishes, it will release 2 units and the
other processes will become unblocked. So,no infinite blocking will occur
no matter what the allocation order because there is no circular waiting
B.Deadlock can not occur since there is preemption (no hold and wait).However,
there can be livelock where no progress is made since processes could be continuously
taking resources from each other.
Question 6 - solution
a) Let the turnaround and service times for process i be T_i and S_i respectively.
Then, T_i = T_{i-1} + S_i So, the average turnaround time is:
t_T = (5 S_1 + 4 S_2 + 3 S_3 + 2 S_2 + S_1) / 5
= (80 + 32 + 12 + 12 + 14) / 5
= 150/5 = 30 seconds
The average waiting time is:
t_W = t_T - t_S
where t_S is the average service time. So, t_W = 30 - 48/5 = 20.4
seconds
b) Round robin works in rounds giving 1 second to each process. C will
finish first because it has the least service demand. A will finish last
because it has the largest service demand. The finishing times will be 18
seconds and 48 seconds respectively. C goes through 3 complete rounds of
5 seconds. A will complete at the same time that the last process completed
in Part a; i.e., the sum of the service demands. The completion order will
be C, D, B, E, A; i.e., in order of their service demands.
c) Since the CPU is fully utilized, the thruput is the same for both policies
if x = 0, and the highest for FCFS when x > 0. So, FCFS is better (as
expected since it has the least overhead).
Question 7- solution
a) VA: 2 KB page ==> 11 bits; 32 pages ==> 5 bits.
PA: 1 MB address ==> 20 bits.
5 bits 11 bits
-----------------------------------------------
VA:
| |
|
===============--------------------------------
|
/ 5 bits
|
v
Page Table
|
/ 20 bits
|
-------
|
v
===============================--------------------------------
PA: |
| |
|
---------------------------------------------------------------
b) Page table length = 32 rows long, (20 + 2 + ...) bits wide:
20-bits for the PA, 1 modified bit, 1 invalid, any other
bits
(e.g., protection).
Question 8 - solution
a) 2 x 20 ns = 40 ns
b) 0.25 x 20 ns + 20 ns = 25 ns
Question 9 - solution
a) 0, 1, 2, 3, 0, 0, 1, 2, 3.
0, 1, 2, 3,
0, 0, 1, 2, 3
Frame
0 *0 *0 *0
*3 *3 *3 *3 *2
*2
1 *1
*1 1 *0 *0 *0
0 *3
2
*2 2 2 2
*1 1 1
F F F
F F
F F
b) The clock algorithm is a simple approximation of the LRU algorithm.
As such it may not perform as well as the LRU algorithm.
Question 10 - solution
struct {
int manager;
// manager of new team
int worker[2];
// which workers are forming a new team
int n=0;
// how many entries in whichWorkers[]
} newTeam;
semaphore newTeam=1;
// only 1 manager can be forming a team
semaphore managerReady=0;
// manager signals workers to find out
// who is their manager
semaphore workersReady=0;
// workers signal manager to read who
// is on the team
semaphore beginWork[M]=0;
// signal workers to begin working
semaphore leave[M]=0;
// signal manager of leaving worker
semaphore updateNewTeam=1; // protect
workers' shared data
process manager (i) {
int myTeam[2];
// who is on my team
do forever {
Wait (newTeam);
newTeam.manager = i;
newTeam.worker[0] = newTeam.worker[1]
= -1;
newTeam.n = 0;
do 2 times { Signal (managerReady);
}
Wait (workersReady);
for n = 0 to 1 {
myTeam[n] = newTeam.worker[n]; }
Signal (newTeam);
do 2 times { Signal (beginWork[i]); }
... work ...
Wait (leave[i]); Wait (leave[i]);
... go home ...
}
}
process worker (i) {
// NOT REQUIRED
int myManager;
do forever {
Wait (managerReady);
myManager = newTeam.manager;
Wait (updateNewTeam);
newTeam.worker[newTeam.n] = i;
newTeam.n= newTeam.n + 1;
if (newTeam.n >= 2)
Signal (workersReady);
Signal (updateNewTeam);
Wait (beginWork[i]);
... work ...
Signal(leave[myManager]);
... go home ...
}
}