Operating Systems Homework #4 Solution

1) Assume virtual addresses are 16 bits. Physical addresses are 16 bits. Page size is 256 Bytes. We have the following page table (partially given). Find the physical addresses of the following virtual addresses. Express your physical addresses in hexadecimal.

0010 1011 1100 0101
0001 0011 0001 1100
1110 0100 1010 0011

0010 1011 0001 0111

Page Table


…

0x13  0xa3

…

0x2b  0xfc

…

0xe4  0xe5

..


    2) Assume virtual addresses are 48 bits. Address division is as follows: [9,9,9,9,12]. How many first, second, third and fourth level tables are required for a process that is using 32 MB contiguous virtual memory starting at virtual address 0? If a page table entry (any level) is 8 bytes, what is the required RAM space to hold page table information?

    3) How many different integer sequences (order is important) may be printed out by the following pseudo-code? Write down all of them.

Semaphore X = 0; //shared by all processes

Semaphore Y = 0; //shared by all processes
Semaphore Z = 0; //shared by all processes

int n;

main() {

n = fork();
if (n==0) {
signal(X)
print (40);
wait (Y);
print (30);
wait(Z);



1
print(45);

exit (0);
}
signal (Y);
print (60);
wait (X);
print (10);
print(80);
signal(Z);
}



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


    5) Consider the following page reference string of a process. Assume the process has 3 frames. For the following replacement algorithms, show the memory state after each reference. Also indicate, if a reference causes a page fault or not.

3543562523425427473.

Memory state means pages in memory (in frames) and their R bit value (of applicable). For example, the following is a memory state.

    • (1)

3 (0)

7 (1)

That means, the pages 4, 3, and 7 are in memory and their R bits are 1, 0, and 1, respectively.

    a) FIFO.

    b) LRU.

    c) Optimal.

    d) R bit algorithm. Assume, in case of a tie, lower page number is removed. R bits are cleared after every 4 references.
    e) Second chance. Reference bits are cleared after every 6 references.

    f) LFU.



2




    6) 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.

    7) Assume there are 3 resource types A, B and C; and initially there exist 9 A, 6 B, and 6 C in the system. There are 5 processes (P1, …, P5). The following is the current Alloc and MaxDemand matrix. Prove whether it is safe or not. If it is safe, would you grant a request (2, 0, 0) from P1 (prove your answer)?
Alloc
MaxDem
1 2 1
5 4 2
1 0 2
3 1 3
2 2 2
6 6 4
0 0 1
2 2 1
3 1 0
5 2 2

    8) Consider the following situation in a system where there are 5 processes (P1, … , P5) and 3 resource types A, B, C. No deadlock avoidance or prevention applied. Initially, there exist 10 A, 6 B, and 4 C in the system. Is there a deadlock at the moment? Prove your answer.
Alloc Request
100    001
301    040
022    312
101    230
210    333

    9) Simulate semaphore S and its operations with a monitor. That means implement wait(S) and sigal(S) by using a monitor. S is an integer variable. We are assuming monitor construct (together with condition variables) is available for us to use in the programming language. So we will use them to implement something like semaphores.






3








































































4