## Description

Q. Consider the following memory reference string (only page numbers are shown):

6 6 3 3 3 4 4 4 4 4 7 7 7 2 2 7 4 4 4 4 4 4 3 3 3 4 5 5 5 5 5 5 7 7 7 4 4 4 2 2 2 2 2 3 3

0 0 0 1 1 1. Assume at every tick, we have a memory reference. The first memory

reference is done at tick 1. Assume at every 10 ticks, reference bits are cleared, just

after making the 10th memory reference. We use a single reference bit for each page.

Assume there are 3 frames allocated to a process. All frames are initially empty.

Assume we use clock algorithm (i.e., a second change algorithm) as the page

replacement algorithm. Find out how many page faults we will have (note that we are

not using Modified/Dirty bit). Assume for a new page that is brought in, its reference

bit is set to 1.

Q. Consider a computer that is uses segmentation and paging. The segment table of a

process is the following:

Segment Base Length

0 1024 1024

1 4196 512

2 128 256

3 2048 768

Assume page size is 64 bytes. Assume virtual addresses are 16 bits long. Assume

physical addresses are also 16 bits long. Assume a page i is located in a frame i+10

(for example, page #11 of linear logical memory is in frame #21 of physical memory).

Convert the following logical addresses to their physical ones:

a) (0, 50)

b) (1,0)

c) (1,100)

d) (1,700)

e) (2,10)

f) (3,200)

All numbers above are decimal.

Q. Assume a cigarette requires three ingredients (items) to smoke: Tobacco (t), Paper

(p) and a Match (m). Assume there are 3 smokers around a table, each of whom has

an infinite supply of one of the three ingredients (items) — one smoker has an infinite

supply of tobacco, another has an infinite supply of paper, and the third has an infinite

supply of matches. Assume there is also a non-smoking agent which has also an

infinite supply of these items. The agent enables the smokers to make their cigarettes

by randomly selecting and putting two items (out of three items) on the table. Then

the smoker having the missing item will take the items from the table (in this way will

make the table empty), will make his cigarette, and will be able to smoke for a while.

When table becomes empty, agent again chooses two items in random and places

them on the table. Another smoker can now smoke (or maybe the currently smoking

smoker will take those items again and start smoking again after it has finished its

current smoking). This process continues forever. Synchronize the agent and 3

smokers by use of semaphores to act in this way.

Q. Assume we have processes A, B, C, D, E arriving to a system at the following

times shown in the table below. The CPU time required by each process is also shown

in the table. Assume the CPU scheduling algorithm is Round-Robin with time

quantum q. Assume q is very small (very close to zero, but is not zero), hence perfect

processor sharing is happening. Ignore the context switching overhead, i.e. context

switch time is equal to 0. Compute the waiting time and finish time of each process.

Arrival Time CPU Time

Process A 0 145

Process B 50 40

Process C 90 70

Process D 210 95

Process E 240 45

Q. Consider a disk with N tracks numbered from 0 to N-1, and assume that requested

sectors are distributed randomly and evenly over the disk. We want to calculate the

average number of tracks (i.e., cylinders) traversed by a seek.

a) Calculate the probability of a seek of length j when the head is currently

positioned over track t.

b) Calculate the probability of a seek of length K, for an arbitrary current

position of the head.

c) Calculate the average number of tracks traversed by a seek.

Q. Assume block size in a file system that is using hierarchical indexed allocation is

4KB. Assume disk pointer size is 8 bytes. The hierarchy can grow to 3 levels at most

(like Unlix/Linux file system). How many index blocks are required for a file of size

1 MB, 100 MB, 4 GB and 1 TB? What can be the maximum file size in bytes?

Assume no caching of index blocks, how many disk accesses are required on the

average to randomly access (uniform random) the 4 GB file?