• The fastest computer gets the toughest job and the slowest computer gets the easiest job.
• Every computer gets at least one job.

1. int counter = 0
2. Semaphore S = init(5);
3. void parop(void)
4. {
5.       wait(S);
6.       wait(S);
7.       counter++;
8.       signal(S);
9.       signal(S);
10. }  

Consider the resource allocation graph given in the figure.

(a) Find if the system is in a deadlock state. (b) Otherwise, find a safe sequence.

Consider the following heap (figure) in which blank regions are not in use and hatched region are in use.

The sequence of requests for blocks of size 300, 25, 125, 50 can be satisfied if we use

A memory page containing a heavily used variable that was initialized very early and is in constant use is removed when

The head of a moving head disk with 100 tracks numbered 0 to 99 is currently serving a request at tract 55. If the queue of requests kept in FIFO order is

  10, 70, 75, 23, 65 

Which of the two disk scheduling algorithms FCFS (First Come First Served) and SSTF (Shortest Seek Time First) will require less head movement? Find the head movement for each of the algorithms.

Consider the following program segment for concurrent processing using semaphore operators P and V for synchronization. Draw the precedence graph for the statements S1 to S9.

 var
 a, b, c, d, e, f, g, h, i, j, k : semaphore;
 begin
 cobegin
    begin S1; V(a); V(b) end;
    begin P(a); S2; V(c); V(d) end;
    begin P(c); S4; V(c) end; 
    begin P(d); S5; V(f) end;
    begin P(e); P(f); S7; V(k) end;
    begin P(b); S3;V(g);V(h) end;
    begin P(g); S6; V(i) end;
    begin P(h); P(i); S8; V(j) end;
    begin P(j); P(j); P(k); S9 end;
 coend
 end; 

A computer installation has 1000k of main memory. The jobs arrive and finish in the following sequences.

 Job 1 requiring 200k arrives
 Job 2 requiring 350k arrives
 Job 3 requiring 300k arrives
 Job 1 finishes
 Job 4 requiring 120k arrives 
 Job 5 requiring 150k arrives
 Job 6 requiring 80k arrives 

(a) Draw the memory allocation table using Best Fit and First fit algorithms.
(b) Which algorithm performs better for this sequence?

In a virtual memory system the address space specified by the address lines of the CUP must be __________ than the physical memory size and _______ than the secondary storage size.

The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 records per page with 1 free main memory frame is recorded as follows. What is the number of page faults?

 0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370 

The sequence …………… is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for …………… unit(s) of time.

Which scheduling policy is most suitable for a time shared operating system?

Which of the following page replacement algorithms suffers from Belady’s anamoly?

In a paged segmented scheme of memory management, the segment table itself must have a page table because

Which of the following statements is true?

Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ______.

Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.

         (P, 155), (Q, 85), (R, 110), (S, 30), (T, 115) 

Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.

Which one of the following statements is FALSE?

Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

wait (a); count = count+1;
if (count==n) signal (b);
signal (a); wait (b); signal (b);

What does the code achieve?

Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P₁,P₂,P₃,P₄.

If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is _____.

Consider the following statements about process state transitions for a system using preemptive scheduling.

I. A running process can move to ready state.
II. A ready process can move to running state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.

Which of the above statements are TRUE?

Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?

Consider the virtual page reference string

1, 2, 3, 2, 4, 1, 3, 2, 4, 1  

On a demand paged virtual memory system running on a computer system that main memory size of 3 pages frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacements policy. Then

A file system with 300 GByte disk uses a file descriptor with 8 direct block addresses, 1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes. The maximum possible file size in this file system is

Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.

  AcquireLock(L){
         while (Fetch_And_Add(L,1))
               L = 1;
   }
  ReleaseLock(L){
         L = 0;
   }

This implementation

Consider the 3 processes, P1, P2 and P3 shown in the table.

Process           Arrival time         Time Units Required
   P1                0                         5
   P2                1                         7
   P3                3                         4

The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are

A process executes the code

fork();
fork();
fork();

The total number of child processes created is

A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the table below, where P0, P1, P2 are processes, and R0, R1, R2 are resources types.

(a) Show that the system can be in this state.
(b) What will the system do on a request by process P0 for one unit of resource type R1?

A file system with a one-level directory structure is implemented on a disk with disk block size of 4K bytes. The disk is used as follows:

 Disk-block 0: File Allocation Table, consisting of one 8-bit entry per date block, 
               representing the data block address of the next date block in the file
 Disk block 1: Directory, with one 32 bit entry per file:
 Disk block 2: Data block 1;
 Disk block 3: Data block 2; etc. 

(a) What is the maximum possible number of files?
(b) What is the maximum possible file size in blocks?

The concurrent programming constructs fork and join are as below:
fork which creates a new process executing from the specified label
join which decrements the specified synchronization variable (by 1) and terminates the process if the new value is not 0.
Show the precedence graph for S1, S2, S3, S4, and S5 of the concurrent program below.

   N = 2
   M = 2
   fork L3
   fork L4
   S1
L1:join N
   S3
L2:join M
   S5
L3:S2
   goto L1
L4:S4
   goto L2
next: 

A demand paged virtual memory system uses 16 bit virtual address, page size of 256 bytes, and has 1 Kbyte of main memory. LRU page replacement is implemented using a list whose current status (page number in decimal) is

For each hexadecimal address in the address sequence given below

 00FF, 010D, 10FF, 11B0

indicate
(i) the new status of the list
(ii) page faults, if any, and
(iii) page replacements, if any

Four jobs to be executed on a single processor system arrive at time 0⁺ in the order A, B, C, D. their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is

The correct matching for the following pairs is

         A. Activation record	   1. Linking loader
         B. Location counter	   2. Garbage collection
         C. Reference counts	   3. Subroutine call
         D. Address relocation	   4. Assembler 

A solution to the Dining Philosophers Problem which avoids deadlock is

A 1000 Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes 200 Kbytes and 260 Kbytes respectively. The smallest allocation request in Kbytes that could be denied is for

A critical section is a program segment

Which of the following is an example of spooled device?

The process state transition diagram in below figure is representative of

Each Process P_i, i = 1.......9 is coded as follows

    repeat 
           P(mutex)
           {Critical section}
           V(mutex)
    forever   

The code for P₁₀ is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?

An operating system contains 3 user processes each requiring 2 units of resource R. The minimum number of units of r such that no deadlocks will ever arise is

I/O redirection

Thrashing

Dirty bit for a page in a page table

Locality of reference implies that the page reference being made by a process

The correct matching for the following pairs is

(A) Disk Scheduling        (1) Round robin
(B) Batch Processing       (2) SCAN
(C) Time sharing           (3) LIFO
(D) Interrupt processing   (4) FIFO  

(a) Free disk space can be kept track of using a free list or a bit map. Disk addresses require d bits. For a disk with 13 blocks, F of which is free, state the condition under which the free list uses less space than the bit map.

(b) Consider a disk with C cylinders, t tracks per cylinder, s sectors per track and a sector length sl. A logical file dl with fixed record length rl is stored continuously on this disk starting at location (c_L,t_L,s_L), where c_L, t_L and S_L are the cylinder, track and sector numbers, respectively. Derive the formula to calculate the disk address (i.e. cylinder, track and sector) of a logical record n assuming that rl=sl.

Consider n processes sharing the CPU in a round-robin fashion. Assuming that each process switch takes s seconds, what must be the quantum size q such that the overhead resulting from process switching is minimized but at the same time each process is guaranteed to get its turn at the CPU at least every t seconds?