CSE 330 – Operating Systems Summer 2018 Final Exam Answer all questions

CSE 330 – Operating Systems
Summer 2018
Final Exam
Answer all questions. Neatness counts.

1. 25 points

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

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

Initialize semaphores to 0.
Initialize lock to 1, lock is a mutex variable.
Agent:
while (1) {
P(lock);
Random = rand (1, 3); //random number from 1 to 3
if (Random == 1) {
place paper on table
place tobacco on table
V (smokerMatch);
}
else if (Random == 2) {
place match on table
place tobacco on table
V (smokerPaper);
}
else if (Random == 3) {
place match on table
place paper on table
V (smokerTobacco);
}
V(lock);
P(agent);
}
Name:
Abdulwahab Jasam

Smokers:
while (1) {
P(smokerPaper); //sleep
P(lock);
take match
take tobacco
V(agent);
V(lock);
}

while (1) {
P(smokerTobacco); //sleep
P(lock);
take match
take paper
V(agent);
V(lock);
}

while (1) {
P(smokerMatch); //sleep
P(lock);
take paper
take tobacco
V(agent);
V(lock);
}

2. 25 points Consider the following snapshot of a system:
Allocation Max
ABCD ABCD
P0 3014 5117
P1 2210 3211
P2 3121 3321
P3 0510 4612
P4 4212 6325
Using the banker’s algorithm, determine whether or not each of the following states is
unsafe. If the state is safe, illustrate the order in which the processes may complete.
Otherwise, illustrate why the state is unsafe.
a. Available = (0, 3, 0, 1)
b. Available = (1, 0, 0, 2)

Max – Allocation
Process A B C D
P0 2 1 0 3
P1 1 0 0 1
P2 0 2 0 0
P3 4 1 0 2
P4 2 1 1 3

a) Available = (0, 3, 0, 1) Using the banker’s algorithm, we can see that all processes
will not be able to terminate, and that means the state is unsafe.
b) Available = (1, 0, 0, 2) Here we see that all processes will be able to terminate, so
the state is safe.

3. 25 Points
Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (ill order),
how would the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB,
417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use
of memory?

First-fit:
212 KB is placed in 500 KB partition, and it leaves 288 KB in partition.
417 KB is placed in 600 KB partition, and it leaves 183 KB in partition.
112 KB is placed in 288 KB partition, and it leaves 176 KB in partition.
426 KB must wait because there is no larger partition that allows it to be allocated in.

Best-fit:
212 KB is placed in 300 KB partition, and it leaves 88 KB in partition.
417 KB is placed in 500 KB partition, and it leaves 83 KB in partition.
112 KB is placed in 200 KB partition, and it leaves 88 KB in partition.
426 KB is placed in 600 KB partition, and it leaves 174 KB in partition.

Worst-fit:
212 KB is placed in 600 KB partition, and it leaves 388 KB in partition.
417 KB is placed in 500 KB partition, and it leaves 83 KB in partition.
112 KB is placed in 388 KB partition, and it leaves 276 KB in partition.
426 KB must wait because there is no larger partition that allows it to be allocated in.

Best-fit makes the most efficient use of memory because it can perform all memory
requests. Both first-fit and worst fit won’t be able to allocate 426 KB.

4. 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

a) LRU replacement:
3 frames:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame1 1 4 5 1 7 2 –
Frame2 2 – 6 3 – –
Frame3 3 1 2 – 6 1 6
15 faults

4 frames:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame1 1 – – 6 –
Frame2 2 – – – – –
Frame3 3 5 3 – –
Frame4 4 6 7 1
10 faults

b) FIFO replacement:
3 frames:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame1 1 4 6 3 – 2 – 6
Frame2 2 – 1 2 – 7 1
Frame3 3 5 1 6 3
16 faults

4 frames:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame1 1 – 5 3 – 1
Frame2 2 – 6 7 3
Frame3 3 2 – 6 –
Frame4 4 1 2 –
14 faults

c) Optimal replacement:
3 frames:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame1 1 – – 3 – –
Frame2 2 – – – 7 2 –
Frame3 3 4 5 6 – 1 6
11 faults

4 frames:
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Frame1 1 – – 7 1
Frame2 2 – – – – –
Frame3 3 – – –
Frame4 4 5 6 – –
8 faults