Answer the following, without exceeding 150
words per subquestion.
a)
What is the difference between user mode and
kernel mode and why is it necessary to have these two modes of execution?
b)
What are the three most common events that lead
to a process switch? Describe them briefly.
c) How is a thread different from a process? List
three main differences.
d)
What operations can be performed on a semaphore?
Do these depend on whether the semaphore is general or binary?
e) What are the differences between deadlock,
livelock and starvation?
f)
What is the main benefit of dynamic
partitioning? What is its main drawback and how is it addressed?
g)
What is the purpose of introducing multi-level
and inverted page tables? How does an inverted table differ from a standard
one?
h) How can the use of priorities in scheduling lead
to starvation? How can this be avoided?
i) What is Direct Memory Access (DMA) and why is it
useful?
j)
Why does it take less, on average, to find a
record in an indexed sequential file than in a sequential file?
Question 2 [4 +
3 = 7%]
A system has four processes and five allocatable
resource types. Consider the following state:
R1 R2 R3 R4 R5
|
R1 R2 R3 R4 R5
|
||||||||||||||||
P1
|
9
|
5
|
5
|
5
|
5
|
P1
|
2
|
0
|
2
|
1
|
2
|
||||||
P2
|
2
|
2
|
3
|
3
|
0
|
P2
|
0
|
1
|
1
|
1
|
0
|
||||||
P3
|
4
|
3
|
3
|
2
|
0
|
P3
|
4
|
1
|
0
|
2
|
0
|
||||||
P4
|
4
|
4
|
4
|
4
|
4
|
P4
|
1
|
1
|
0
|
0
|
1
|
||||||
Claim
Matrix
|
Allocation Matrix
|
||||||||||||||||
R1 R2 R3 R4 R5
|
R1 R2 R3 R4 R5
|
||||||||||||||||
15
|
6
|
9
|
10
|
5
|
8
|
3
|
6
|
6
|
2
|
||||||||
Resource Vector
|
Available Vector
|
||||||||||||||||
a)
Is this a safe state? Justify your answer by
applying the Banker’s Algorithm. If your answer is yes, show a sequence of
process executions and how the available vector changes after each execution.
If your answer is no, is this state deadlocked, or is there a way to arrive at
a safe state?
Page 2 of 6
R1 R2 R3 R4 R5
|
R1 R2 R3 R4 R5
|
||||||||||||||||
P1
|
9
|
5
|
5
|
5
|
5
|
P1
|
2
|
0
|
2
|
1
|
2
|
||||||
P2
|
2
|
4
|
3
|
3
|
0
|
P2
|
0
|
1
|
1
|
1
|
0
|
||||||
P3
|
4
|
3
|
3
|
2
|
0
|
P3
|
4
|
1
|
0
|
2
|
0
|
||||||
P4
|
4
|
4
|
4
|
4
|
4
|
P4
|
1
|
1
|
0
|
0
|
1
|
||||||
Claim
Matrix
|
Allocation Matrix
|
||||||||||||||||
R1 R2 R3 R4 R5
|
R1 R2 R3 R4 R5
|
||||||||||||||||
9
|
5
|
5
|
6
|
6
|
2
|
2
|
2
|
2
|
3
|
||||||||
Resource Vector
|
Available Vector
|
||||||||||||||||
Question 3 [2 x
3 = 6%]
To
which physical address (in binary format) does the logical address
0011011010101010 correspond, under the following hypothetical memory management
schemes? Justify your answers.
a)
A paging system with a page table containing 512
entries and in which the frame number happens to be two times smaller than the
page number.
b) A segmentation
system with a maximum segment size of 2,048 bytes, using a segment table in
which bases happen to be regularly placed at real addresses equal to 22 + 4,096
+ segment number.
Question 4 [4 x
3 = 12%]
Suppose that a
system has 32-bit physical addresses and 48-bit virtual addresses. Answer the
following:
a) If page size is
8KB, how many entries are in the page table (assume that it has only a single
level)? Justify your answer.
b)
If accessing a page directly from main memory
takes 100ns, while having to retrieve the page from the disk takes 2ms, what is
the average access time when the page fault rate is 0.005%?
c)
What is the maximum required page fault rate in
order to ensure average memory access time does not increase more than 25% of
the direct memory access time?
d)
A Translation Lookaside Buffer (TLB) is added to
the system. In case of a TLB hit, memory access is reduced to 30ns. The TLB hit
rate is 95%. What is the average access time if we assume a page fault rate of
0.005%, as in (a)?
Page 3 of 6
The table below gives a list of processes along
with their burst times and priorities. We assume that the processes have
arrived in the order P1, P2, P3, P4, P5, all at time 0.
Process
|
Burst Time
|
Priority
|
||||||
P1
|
3
|
3
|
||||||
P2
|
3
|
1
|
||||||
P3
|
4
|
3
|
||||||
P4
|
2
|
4
|
||||||
P5
|
7
|
2
|
||||||
Assuming only one single-core CPU, answer the
following:
a)
Show the schedule using a time scale diagram (as
in Lecture/Tutorial 8) if we use the First Come First Served (FCFS) scheduling
policy. What is the average turnaround and waiting time?
b) Repeat (a), this time using Round-Robin (RR)
with a time quantum equal to 2.
c) Repeat (a), this time using Shortest Job First
(SJF).
Question 6 [3 x
3 = 9%]
Consider the following
sequence of disk track requests: 120, 50, 11, 22, 27, 76, 166, 52 and 140.
Assume that the disk head is initially positioned over track 50 and is moving
in the direction of increasing track number.
a)
How many tracks will have to be traversed (total
seek length) and what is the average number of tracks to be traversed (average
seek length) if we use the SSTF scheduling policy?
b) Repeat (a), this time using the SCAN scheduling
policy.
c) Repeat (a), this time using the C-SCAN
scheduling policy.
To assist in answering the questions, you may
fill in the table that follows:
SSTF
|
SCAN
|
C-SCAN
|
|||
Next
|
Number
|
Next
|
Number
|
Next
|
Number
|
track
|
of tracks
|
track
|
of tracks
|
track
|
of tracks
|
accessed
|
traversed
|
accessed
|
traversed
|
accessed
|
traversed
|
Page 4 of 6
Consider a file consisting of 2000 records of
size 250B stored on a disk with a block size of 512B using fixed blocking.
a)
How many blocks are required to store the file
and how much space is wasted due to internal fragmentation?
b) Repeat (a), for a block size of 8KB.
c) Repeat (b), this time assuming that spanned
blocking is used: a record can span two blocks.
Question 8 [8 +
10 = 18%]
In the Serengeti National
Park in Tanzania, Africa, there is a deep canyon that can only be crossed by
the baboons living in the park using a rope that has been fastened on both
sides by the park administration. Several baboons can cross at the same time,
provided they are all going in the same direction. If eastward-moving and
westward-moving baboons ever get onto the rope at the same time, the baboons
will get stuck in a deadlock because it is impossible for one baboon to climb
over another one while suspended over the canyon.
a)
Using Java semaphores or Java synchronisation
(or any other language you prefer), design an algorithm that prevents deadlock.
Implement and test your algorithm by designing two threads, one representing an
eastward-moving baboon and the other representing a westward-moving baboon.
Once both are on the bridge, each will sleep for a random period of time to
simulate traveling across the bridge. Initially, do not be concerned about
starvation (the situation in which eastward-moving baboons hold up
westward-moving baboons indefinitely, or vice-versa).
b) Modify your algorithm in (a) so that it is
starvation-free, implement and test it.
Page 5 of
Marking
Criteria for Question 1
For each subquestion:
1 out of 3 points: Without
exceeding the maximum words limit, barely adequate response in terms of
explanation, depth, structure and presentation.
2 out of 3 points: Without exceeding the maximum
words limit, adequate but incomplete response.
3 out of 3 points: Without
exceeding the maximum words limit, complete response in terms of explanation,
depth, structure and presentation.
Marking
Criteria for Question 2
For (a): 1 point given for
identifying correctly whether it is a safe or unsafe state and 3 points are
given for a correct explanation.
For (b): 1 point given for
identifying correctly whether it is a safe or unsafe state and 2 points are
given for a correct explanation.
Marking
Criteria for Question 3
For (a): 1 point given for
correctly calculating the page number, 1 point for correctly calculating the
frame number and 1 point for correctly calculating the complete physical
address.
For (a): 1 point given for
correctly calculating the segment number, 1 point for correctly calculating the
base address and 1 point for correctly calculating the complete physical
address.
Marking
Criteria for Question 4 and Question 7
For each subquestion:
1 out of 3 points:
calculated value is incorrect but some of the steps towards calculating it are
correct. Alternatively, calculated value is correct but there is no explanation
as to how it was calculated.
2 out of 3 points:
calculated value is correct but only some of the steps towards calculating it
are correct.
3 out of 3 points: calculated value is correct and
all of the steps towards calculating are correct.
Marking
Criteria for Question 5
For each subquestion:
2 points out of 4 are given
for a complete time scale diagram, 1 point for correctly calculated turnaround
times for all processes and 1 point for correctly calculated waiting times for
all processes.
Marking
Criteria for Question 6
For each subquestion:
1 out of 3 points: at least 3 of the lines in
the table are correctly filled in
2 out of 3 points: at least 6 of the lines in
the table are correctly filled in
3 out of 3 points: all of the lines in the table
are correctly filled in
Marking
Criteria for Question 8
For (a): 4 points out of 8
are given for a complete and correct algorithm that prevents deadlock, while
the rest are given for a complete and correct code that implements and tests
the algorithm
For (b): 4 points out of 10
are given for a complete and correctly redesigned starvation-free algorithm,
while the rest are given for a complete and correct implementation of the
redesigned algorithm.
Page 6 of 6
No comments:
Post a Comment