• İhsan Doğramacı Bilkent University

• CS 342

CS342 Operating Systems - Spring 2015

Homework 3 Solutions

Note that:

1 KB = 2^10 Bytes

1 MB = 2^20 Bytes

1 GB = 2^30 Bytes

1.

Monitor AccessFile {

condition c;

int count;

int sum;

request (int id) // id of the process requesting access to the file

{

while ( (count >=4) or (sum+id >= M) ) do

c.wait();

count++;

sum = sum + id;

}

release (int id)

{

count--;

sum = sum – id;

c.broadcast();

}

} // end of monitor definition

A process will use it as follows:

..

AccessFile Mon;

pid = Id-of-this-process ();

Mon.request (pid);

// Access File

Mon.release (pid);

2.

Define the following semaphores.

sem table = 1;

sem smoke[3] = {0,0,0}. // 3 semaphores – i.e. a semaphore array.

Arbiter()

{ int i; 1 <= i <= 3

wait(T); // wait until table is empty

Select an i in random. Put items for that smoker.

signal (smoke[i]);//wake smoker

}

Smoker(k) 1 <= k <= 3

{

wait(smoke[k]);

signal (T); // now table became empty

}

3.

a) page size = 1024 bytes = 1 KB.

b) Each 2^8 x 2^10 = 256 KB contiguous virtual memory space is mapped by a third level

table.

Each 2^8 x 2^8 x 2^10 = 64 MB contiguous virtual memory space is mapped by a

second level table.

Total number of second level tables: ceiling(200 / 64) + ceiling (140/64) = 4 + 3 = 7

second level tables.

Total number of third level tables: ceiling(200x1024 / 256) + ceiling(140x1024 /

256) = 800 + 560 = 1360 third level tables.

4.

First let us find the linear addresses:

0,50: 1024+50 = 1074

1,0: 4196+0 = 4196

1,100: 4196+100 = 4296

1,700: 4196+700 = 4896

2,10: 128+10 = 138

3,200: 2048+200 = 2248

Now for each linear virtual address, let us find the respective physical address.

Page size is 64 bytes.

1074: is on page #16, which is on frame #26, then phy address is: 26x64+50 = 1714.

4196: is on page #65, which is on frame #75, then phy address is: 75x64+36 = 4836.

4296: is on page #67, which is on frame #77, then phy address is: 77x64+8 = 4936.

…

2248: is on page #35, which is on frame #45, then phy address is: 45x64+8 = 2888.