CSE 330 - Operating Systems
Fall 2018
Final Exam
Open book, open notes, computers allowed (no Internet).
Answer four questions. Neatness counts.
If any answer is copied verbatim from a note you will get 0 for that answer

1. [25 points]

Consider 3 smokers and an agent. Each smoker wants to roll a cigarette and smoke it
immediately. To smoke a cigarette, the smoker needs three ingredients – paper,
tobacco, and a match. Each smoker has only one ingredient – smoker 1 has paper,
smoker 2 has tobacco, and smoker 3 has matches. The agent has access to all three
items. However, at a time the agent selects two items randomly and puts them on the
table. The smoker with the remaining ingredients immediately takes them, rolls, and
smokes. When finished, the agent is woken up who then places another two randomly
selected items on the table. Write the code for the agent and smokers using
Semaphores


Name:
_________SOLUTIONS____________
________________
Books, notes,
computer is OK.
Internet access is
not ok.
Answer
here
and on
reverse
of this
sheet
2. [25 poinys]
Consider the following snapshot of a system:
Allocation Max Available ----
ABCD ABCD ABCD
Po 0012 0012 1520
pl 1000 1750
p2 1354 2356
p3 0632 0652
p4 0014 0656

Answer the following questions using the banker's algorithm:
a. What is the content of the matrix Need?
b. Is the system in a safe state? Explain, no explanation no points
c. If a request from process P1 arrives for (0,4,2,0), can the request be granted
immediately? Explain, no explanation no points.






























3) [25 points]
Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1,
2, 3, 6. How many page faults would occur for the following replacement algorithms,
assuming three and four frames? Remember that all frames are initially empty, so your
first unique pages will cost one fault each.
a) LRU replacement
b) FIFO replacement
c) Optimal replacement
d) Prove that optimal placement has the least possible page faults.

a) LRU

3 Frame == > 15 page fault, 4 Frame == > 10 page fault

b) FIFO

3 Frame == > 16 page fault, 4 Frame == > 14 page fault
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame 1 1 1 1 4 4 5 5 5 1 1 7 7 2 2 2
Frame 2 2 2 2 2 2 6 6 6 3 3 3 3 3 3
Frame 3 3 3 1 1 1 2 2 2 2 6 6 1 6
Page Fault # # # # # # # # # # # # # # #


1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame 1 1 1 1 1 1 1 1 1 6 6
Frame 2 2 2 2 2 2 2 2 2 2
Frame 3 3 3 5 5 3 3 3 3
Frame 4 4 4 6 6 7 7 1
Page Fault # # # # # # # # # #
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame 1 1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6
Frame 2 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1
Frame 3 3 3 3 5 5 5 1 1 1 6 6 6 3 3
Page Fault # # # # # # # # # # # # # # # #


1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame 1 1 1 1 1 5 5 5 5 3 3 3 3 1 1
Frame 2 2 2 2 2 6 6 6 6 7 7 7 7 3
Frame 3 3 3 3 3 2 2 2 2 6 6 6 6
Frame 4 4 4 4 4 1 1 1 1 2 2 2
Page Fault # # # # # # # # # # # # # #

C) OPT


3 Frame == > 11 page fault, 4 Frame == > 8 page fault


























1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame 1 1 1 1 1 1 1 3 3 3 3 3
Frame 2 2 2 2 2 2 2 7 2 2 2
Frame 3 3 4 5 6 6 6 6 1 6
Page Fault # # # # # # # # # # #


1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame 1 1 1 1 1 1 1 7 1
Frame 2 2 2 2 2 2 2 2
Frame 3 3 3 3 3 3 3
Frame 4 4 5 6 6 6
Page Fault # # # # # # # #












































4) [25 points]
Assume that we have a demand-paged memory. The page table is held in registers. It
takes 8 milliseconds to service a page fault if an empty frame is available or if the
replaced page is not modified and 20 milliseconds if the replaced page is modified.
Memory-access time is 100 nanoseconds. Assume that the page to be replaced is
modified 70 percent of the time. What is the maximum acceptable page-fault rate for
an effective access time of no more than 200 nanoseconds? Explain your work. No
explanation no points.



pf = page fault rate


200 × 10−9 ≥ (1 − ) × 100 × 10−9 + (100 × 10−9 + 0.3 × 8
× 10−3 + 0.7 × 20 × 10−3)


100 × 10−9 ≥ (0.3 × 8 × 10−3 + 0.7 × 20 × 10−3)


100 × 10−9
16.4 × 10−3
≥


6.0975 × 10−6 ≥















5) Assuming a 1-KB page size, what are the page numbers and offsets for the following
address references (provided as decimal numbers):
a. 2375
b. 19366
c. 30000
d. 256
e. 16385

Show your work for each option in order to get any credit. If you do not show your work
you get 0.


Page number = address / page size
Page offset = address % page size


a)
page number = 2375 / 1024 = 2
page offset = 2375 % 1024 = 327

b)
page number = 19366 / 1024 = 18
page offset = 19366 % 1024 = 934

c)
page number = 30000 / 1024 = 29
page offset = 30000 % 1024 = 304

d)
page number = 256 / 1024 = 0
page offset = 256 % 1024 = 256

e)
page number = 16385 / 1024 = 16
page offset = 16385 % 1024 = 1