Problem 1: (6 points) True/False:
7J7
(write your answers in the.following table)
(1) (2) (5)
(4) '
1. The processor can be switched to kernel mode during execution of a user process, if the user
process issues a syste1n call.
2. A syste111 call is a function linked into a user-mode program that executes a "~ransition to
kernel n1ode" instruction, then begins to execute arbitrary code with kernel privileges.
3. Every user-level thread must have a unique kernel-level thread in order to facilitate
multithreading (and allow concurrency).
,, I 4. The number of threads in the system 1nay exceed the number of CPU _cores.
5. ·A·. successful caIT to fork is guaranteed to return different values in the parent and child
---:-
processes. •
6. Modern operating systen1s, like Linux, use Banker's Algorithm to avoid deadlock.
Problem 2: (3 points) Of those the following components of a process, circle that are shared
across threads in a multithreaded process
(a) Register values /"
@) Heap Memory
@ Global variables
(d) Stack n1en1ory /
~Code/text
Problem 3: (3 points) Of those the following CPU scheduling algorithms, circle that could result
s~
(a) First come, first served (FCFS) /
Shortest job first (SJF)
y~hortest Remaining Time First (SRTF) {j
(d) Round robin (RR) /
'/ ~Priority
,WLottery
2
Problem 4: (4 points) Using the numbers from the following thread state graph, indicate which
transition(s) might happen for the various events/situations described.
( 1)
(2)
(3) (4)
- - ~ - A requested 1/0 operation completes.
_ __;_'I_ The running thread requests an 1/0 operation
j.___ The running thread exhausts its time slice
___
4- The dispatcher gives control to a ready thread.
Problem 5: (4 points) Short Answer
What is multiprogramn1ing? How is multiprogramming able to improve CPU utilization, even
there is only one CPU in th~ system?'
1'-1" It, r;"" ;"~ ; 11 ; n~ rro lti PYV(.Q..~ JZi, 0- lt..i<. • oJ 4e &l ,ne. -h'nt
hut Cl p~% ru nl'li, .eac-h fjr(l,t • .foY-
(I~ oY\(. mrlt, i CO.fl l \ l V'
+wo a~ co.:h'o.., Qf bvoLv~ o.,-t -1}~ &!ffU- -Irr<'!- •
ara~llll<f rw.pvvt C{)u () Ji/i-ioA, 0 II
fv\ O1-t; 4'1a.11 i "6 M.v'l-fi pie. ptoa~_Qi
oYlcl kw~ -tkf\"\ .scWu½ -lo i,ori in -;flL ihttf ,,., 1'S fY'l)~-f u+dr U-e
;" p,ocff-3Si'tj ~;mt,
3
Problem 6 (6 points)
#includ e <iostrea m>
#includ e <thread >
#includ e <sys/w ait.h>
#includ e <unistd .h>
using namespa ce std;
void helper (int &number)
{
number++· I
tnt main(in t argc, char *argv[] )
int data= 10·
0~reo J ef)p hufpcf
thread cthread ·
I
cthread = thre~ hel er ref(dat a));
w 1+1' i f\Cfe,,,n-e01-' r~<h +o.
cthread . join () .
• • I
pr1ntf ( "data is %d\n", data); II .
data = 10 • - - - - - - - 7 Jo..f&- fb ,e~t ... KJ
~id_t @= fork();
1f (cpid == 0) •
{ '
he~p er~;
pr1ntf( "data is
return' 0· I
}
else
{
wait(NU LL);
}
printf( "data is
}
What does this C°!ran roU~T here should be 3 lines) . Expla·in your answer and be specific.
l\
~2
4
Problem 7 (20 points) Considering the following code
int y = \; x = O; 0
/ I \
foo O l
y =y + 2; :; '-I F
}
bar() {
y=y+ l;
X = y;
main() {
Thread t 1 =createThread (foo);
Thread t2 = createThread(bar);
WaitForAllDone();
cout << x << "," << y <<end!;
Note that function WaitForAl\Done blocks the main thread until both
threads it creates are
done. Assume that memory load and memory store are atomic, but
add and time are not
atomic.
a) (2 points) What is the maximum number of threads that are ever
rj;:~ re~~o r ;;; ~i;o~~tfh~~rogram?
alive (this includes those
b) ( l Opoints) Give all possible outputs of this program. Explain your
answer and be
specific.
fOO f\JV' \;,--~+ v:».~ ~r f" °"tt..tY-
- - - - - - , -- ---- -·-- --- - -·-,.. --·-·· ··-· ••
. 'fV'O((:,
\,p., Yl11" f
11,-t WO' \ ~ef fe>'1) &; &
5
c) (8 points) Using semaphores for synchronization, modify functions foo() and bar(), to
ensure that statement y =y + 1 is always executed after the statement y =y + 2.
inf ~::: A. )~ -:.O , JjO +\--.. -t r ' ;::o -1-\-rta.J.). , ~\J""' O
(oO ( ) \
w~,lL
Problem 8: (4 points) I~ an attempt to become the most successful computer scientist, Prof.
Feckless C. Coder has built yet another scheduler for interactive multitaskin° o erating systems.
Intended for modest desktop computers running at about l O million instructions c
MIPS), the scheduler is based on a preemptive round-robin scheme with a time quantum of l
microsecond (l/1,000,000 of a second). J(JO. 00 0 r,oO ; .-1 ~, \
f . - I
l
J f
Discuss the perfo rma== ~spec ially with respect to efficiency and response
time. 60 I ,. l lD ,5 I·11s..f.....r,.,...) ·or, Yd,c
• .....,,.... ~' - ...
r'- Cl~ l',V~(
6
Pro lem 9: ( 15 points) Suppose that the following processes arrive for execution at the times
indicated. Each process will run the listed amount of time.
Process Arri val Time Burst Time
Pl 0.0 5 : 2)
P2 2.0 8 .. }(
P3 4.0 1. < ,,
P4 5.0 4 2-
Compute the avera 0 tilnes fort ses with FCFS (first-come, first-served)
sc e uling algorithn1, nonpreen1ptive SJF (shortest job first) scheduling algorithm, and Round
Robin scheduling algorithm with tin1e quantum= 2, respectively. Note that the response time is
the interval fro1n th~ti111e of sub1nission (arrival) of a process to the time of completion.
p pz _b--1
/1 -\ 1
l-,
u : rC, f 3 ,t9 -I 5 .,- I -: !J, 5
0 5 6
~J F
7
Problem 10 ( 15 points) Consider the following snapshot of a system
Allocation Max Available
ABCD ABCD ABCD
PO 00l 2 0012 1520
Pl 1000 175 0
P2 1354 2356
P3 0632 0652
P4 0014 0656
Answer the following questions using the banker's algorithm:
(a) What is content of the matrix Need?
(b) Is the system in a safe state? Explain.
(c) If a request from process P 1 arrives for (0, 4, 2, 0), can the request be 0oranted
immediately? Explain.
8
blem
Problem 11: A Saving Account Pro thd ra~
by sev era l peo ple (th rea ds) . Each person may deposit ~nd wi
A saving account is shared osits to date
oun t. The cur ren t bal anc e in the account is the sum of all dep
acc d~posit
funds from the
hdr aw s to dat ~ The 12_ alance must never become negative. A
minuses rbesum of all wit ion), but a withdrawal has to wa
it until there are
del ay (ex cep t for ml.1 tual exc lus
~ r has to •
%tf1c1ent funds.
e two
velop a mo nito r to sol ve this problem. The monitor should hav
(a) (10 points) De osit and
oun t) and wit hdr aw (a,n oun t). Assume the arguments to dep
procedures: deposit(am ·
withdraw are positive.
als:
we r to (a) so that the sys tem supports two kinds of withdraw
(b) (10 points) Modify your ans must ensure that
h~r aw( a11 zou11t) and pre fer red -withdraw(amount). The system
ordina_ry-wit iting to occure.
there is a preferred withdrawal wa
no ordinary withdrawal occurs if
a)
w~ ·d ra ~
fJ.i, c;lflt a)) /ie_ U!),~ M J
