Birla Institute of Technology & Science, Pilani Comprehensive Examination

IDNO: NAME:
BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE, PILANI

I SEMESTER 2008-2009
Comprehensive Examination
CS C372/IS C362 - Operating System
Weightage: 40% (120 marks)
Date: 06/12/2008
Time: 3 Hours
PART A (Short Answer Questions) - 40 marks (CLOSED BOOK)
Answer in the space provided in the question paper
1. In a paging system a frame in memory can have four possible states: 1) free, available for
use; 2) used, being used to store a page; 3) copyin, currently a page is being copied into the
frame from disk; and 4) c opyout, currently the page in the frame is being copied out to disk.
These states are shown in the following diagram. Show the possible transitions between
these states and the reason for each transition .
2. Suppose, on a machine with 16 -bit virtual and physical addresses and a page size of 256
bytes, a process is running and the TLB contains the following:
1 (valid) 32 4F
1 1A C3
1 89 22
0 (invalid) 42 B2
where, from left to right, the columns contain the valid bit, the virtual page number, and the
page frame number. All numbers are given in hexadecimal. If the process issues the virtual
address 1AF2 hex, what physical address (in hex) will the MMU issue? Show your work,
but without giving a long explanation.
Page 1 of 6
3. It is said that the implementation of the MFU or the LFU page replacement algorithms is
fairly ‘expensive’. Explain why?
4. Briefly describe a scenario where spinlocks would be more efficient than blocking locks.
5. On a uniprocessor, mutual exclusion can be guaranteed by di sabling interrupts before

entering the critical section and enabling interrupts after leaving the critical section. Give
two reasons why it is not a preferred method?
6. A system uses FCFC scheduling policy. Twenty identical computational requests arr ive in
the system during the first second. It is desired that the mean wait time for these 20 requests
should not exceed 2.0 seconds. Compute the size of each request in CPU seconds.
Page 2 of 6
7. Explain briefly how maximum file protection can be achieved. List the implementation
issues. Write in brief how operating systems overcome these issues to offer suitable file
protection features.
8. Give a detailed process state diag ram of the UNIX operating system.
Page 3 of 6
BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE, PILANI
I SEMESTER 2008-2009
Comprehensive Examination
CS C372/IS C362 - Operating System
Weightage: 40% (120 marks)
Date: 06/12/2008
Time: 3 Hours
PART B - 80 marks (OPEN BOOK )
1. (a) Suppose there is a machine with 32 -bit addresses and a two-level page table (in memory)
such that the first most significant 10 bits of an address is an index into the first level page
table and the next 10 bits are an index into a second level page table. Suppose also that each
entry in the page tables is 3 2-bits. How much space is occupied in memory by the page
tables for a process that has 64MB of virtual address space allocated. Show your work
without giving a long explanation.
[10]
(b) In a system using pure segmentation, the scheduler decides to put a r unning process P1
into a ready-suspend state and starts executing a process P2 from the ready queue. Later,
process P1 is swapped back in and put in the ready queue. P1 then starts executing at a later
point of time. Give all the steps (in proper order) i nvolved in swapping out, swapping in,
and resumption of execution of P1. (write only the steps concerned with segmentation)
[10]
2. (a) A 4-KB block of memory is allocated using the binary buddy system. Show the allocation
result of the following sequence:
Request A 2000; Request B 900; Request C 600; Release B; Request D 500; Release C; Request
E 600; Request F 300; Release D; Release F.
(b) Devise a Buddy system using the Fibonacci sequence which is defined as follows:
F0=0, F1=1 & Fn+1=Fn+Fn-1 (n>=1). Show the allocation result for a memory block of 4181
bytes (1597 + 2584) for the request sequence given in part (a).
[8+12]
3. Suppose that pages in a virtual address space are referenced in the following order:
S=1 2 4 1 1 5 6 8 1 2 5 3 4 6 7 1 5
There are 3 empty frames available. Show the contents of frames after each memory
reference and find the total number of page faults for “Optimal” and “LRU” page
replacement algorithms. Write the number of page faults for both the algorithms if the
reference string S is reversed.
[5+5]
Page 4 of 6
4. A system has three processes (P1, P2, P3) and three resources (R1, R2, R3). There are two
instances of R1 and R2 and one instance of R3. P1 holds an R1 and is requesting an R2. P2
holds an R1 and an R2 and is requesting an R3. P3 holds an R2 and an R3 and is requesting
an R1. Draw the resource allocation graph for this situation.
Does a deadlock situation exist?
Draw the wait for graph for the above situation.
[8]
5. Assume that each of the five philosophers , i, in the dining philosophers problem executes
the following segment of code: (assume: mutex is initialized to 1, the fork[i] array is also
initialized to 1 for all five forks in the array).
PTO 
1. do
2. /* get hungry, Pick up forks */
3. wait(mutex);
4. wait(fork[i]);
5. signal(mutex);
6. wait(mutex);
7. wait(fork[(i+1)% 5]);
8. signal(mutex);
9. Eat();
10. /* Put down forks */
11. signal(fork[i]);
12. signal(fork[(i+1)% 5]);
13. Think();
14.while (1);
Does this code satisfy all the requirement of the dining philosophers problem? Explain.
Write no more than three sentences for your explanation. If the solution suffers from a
problem explain how the problem could arise: (e.g. philosopher 1 does X, philospher 2 does
X, etc and thus, …..)
[10]
6. Consider a variation of the bounded buffer producer/consumer problem in which there are
many concurrent producers and the items produced and consumed vary in size. The total
capacity of the buffer is N. These processes use two semaphores to syn chronize access to the
buffer: full is a counting semaphore with initial value 0 and empty is a counting semaphore
with initial value N. Each producer executes the following code when it wishes to insert an
item of size k (1 <= k <= N) into the buffer:
for i from 1 to k do {
wait(empty)
}
insert item of size k into buffer
signal(full)
Page 5 of 6
The consumer executes the following code when it wishes to remove an item from the buffer:
wait(full)
remove item of size k from the buffer
for i from 1 to k do {
signal(empty)
}
In each of the code fragments shown above, i is an integer variable that is local to each
process.
Answer each of the following questions. In each case, you must (briefly) justify your answer
to get credit.
(a) Does the code above ensure that produce rs do not insert items into the buffer unless the
buffer has room to hold them?
(b) Does the code above ensure that the consumer does not remove items from the buffer
unless the buffer contains items to remove?
(c) Does the code above ensure only one pro cess (producer or consumer) will use (insert or
remove items from) the buffer at a time?
(d) Does the code above ensure that processes using the buffer will not deadlock?
[3*4=12]
Page 6 of 6

Birla Institute of Technology & Science, Pilani Comprehensive Examination

Uploaded by

Copyright:

Available Formats

Birla Institute of Technology & Science, Pilani Comprehensive Examination

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Birla Institute of Technology & Science, Pilani Comprehensive Examination

Uploaded by

Copyright:

Available Formats

IDNO: NAME:

BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE, PILANI

5. On a uniprocessor, mutual exclusion can be guaranteed by di sabling interrupts before

You might also like