IT-501 Operating System - Nov 2022 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aExplain how protection is provided for the hardware resources by the operating system?
   How to answer

   • Define protection goals: prevent interference, ensure authorized access
   • Explain dual-mode operation, privileged instructions
   • Explain memory protection, I/O protection, CPU protection with hardware support
   • Give examples: base-limit registers, timers, system calls
2. 7 Marks
   bSuppose that a disk drive has 5000 cylinders numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending request in the FIFO order is 86,1470,913,1774, 948,1509, 1022,1750,130 starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk scheduling algorithms?

   1. i)FCFS
   2. ii)SSTF
   3. iii)SCAN
   4. iv)Look
   How to answer

   • List head movement order for FCFS, SSTF, SCAN, LOOK from 143
   • Compute seek distance as sum of absolute differences
   • Give total distance in cylinders for each algorithm
   • Compare results
3. 3 Marks
   aIn the round-robin scheduling, new processes are placed at the end of the queue, rather than at the beginning. Suggest a reason for this.
   How to answer

   • State fairness / FIFO order within round-robin
   • New process has not waited; placing at front would starve old
   • Preserves time-slice equity and arrival order
4. 4 Marks
   bExplain why wait and signal operations on semaphores need to be atomic?
   How to answer

   • Define race condition on semaphore value
   • Show interleaving of wait/signal without atomicity breaks count
   • Explain need for mutual exclusion
5. 7 Marks
   cShow how to implement the wait() and signal() semaphore operations in multiprocessor environments using the TestandSet() instruction. The solution should exhibit minimal busy waiting. Develop pseudo code for implementing the operations.
   How to answer

   • Introduce TestandSet lock for multiprocessor mutual exclusion
   • Show wait() with blocking queue to minimize busy waiting
   • Show signal() waking blocked process
   • Give pseudo-code for both
6. 7 Marks
   aConstruct a Resource Allocation Graph for the following scenario. At time 't' Process P1 request for a resource X, process P2 requests for a resource Y. Both the resources are available and they are allocated to the requesting process. At time $t_1$ where $t_1 > t_2$ both the processes are still holding the resources, however process P1 request for Y which is held by P2, process P2 request for X held by P1. Will there be a deadlock? If there is a deadlock discuss the four necessary conditions for deadlock, else justify there is no deadlock.
   How to answer

   • Draw RAG: P1->Y, P2->X requests and P1 holds X, P2 holds Y
   • Show cycle indicating deadlock
   • List four Coffman conditions: mutual exclusion, hold-and-wait, no preemption, circular wait
   • Conclude deadlock exists
7. 7 Marks
   bAssume the following processes arrive for execution at the time indicated and also mention with the length of the CPU-burst time given in milliseconds. Give a Gantt chart illustrating the execution of these processes using FCFS, Round Robin (quantum = 1), and Priority (Preemptive and Non preemptive). Calculate the average waiting time and average turnaround time for each of the above scheduling algorithm. Which algorithm will give the minimum average waiting time? Discuss.

   How to answer

   • Tabulate arrival, burst, priority for P1-P5
   • Draw Gantt charts for FCFS, RR q=1, Priority preemptive and non-preemptive
   • Compute waiting = turnaround - burst and averages
   • Identify minimum average waiting algorithm
8. 3 Marks
   aWhat is the difference between local and global page allocation? What are their respective advantages and disadvantages?
   How to answer

   • Define local vs global frame allocation
   • Explain behavior on page fault under each
   • List advantages: isolation vs flexibility
   • List disadvantages: limited sharing vs thrashing propagation
9. 4 Marks
   bCompare the segmented paging scheme with the hashed page table scheme for handling large address spaces. Under what circumstances is one scheme preferable over the other?
   How to answer

   • Describe segmented paging structure
   • Describe hashed page table structure
   • Compare on size, sparsity, sharing
   • State when each is preferable
10. 7 Marks
    cConsider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 How many page faults would occur for the following page replacement algorithm, assuming one, two three, four, five, six or seven frames? Assume that all the frames are initially empty, so your first unique pages will all cost one fault each

    1. i)LRU replacement
    2. ii)FIFO replacement
    3. iii)Optimal replacement
    How to answer

    • State reference string 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
    • Simulate LRU, FIFO, Optimal for 1-7 frames counting faults
    • Tabulate faults vs frames
    • Note Belady anomaly for FIFO if present
11. 3 Marks
    aFind out the effective memory-access time with an 80% hit ratio and the following access times: TLB access time: 20ns; Memory access time: 100ns.
    How to answer

    • State EMAT = h*(TLB+Mem)+(1-h)*(TLB+2*Mem) or variant
    • Substitute h=0.8, TLB=20ns, Mem=100ns
    • Compute effective time
12. 7 Marks
    bConsider a paging system with the page table stored in memory. If a memory reference takes 200 nano seconds, how long does a paged memory reference take? If we add associative registers, and 75 percent of all page table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a pager table entry in the associative registers takes zero time, if the entry is there?
    How to answer

    • Paged access needs 2 memory refs = 400ns
    • With TLB hit 0.75, EMAT = 0.75*200 + 0.25*400
    • Compute 250ns (with zero TLB search time)
13. 4 Marks
    cOn a system with paging, a process cannot access memory that it does not own, why? How could the operating system allow access to other memory? Why should it or should it not?
    How to answer

    • Explain per-process page tables and valid-invalid bits
    • Explain protection via isolation
    • Explain shared pages / capabilities for controlled sharing
    • Discuss pros/cons of sharing
14. 7 Marks
    aWhich file-allocation method would you use for a system whose main task is database management? Why?
    How to answer

    • Compare contiguous, linked, indexed on random access and growth
    • Argue indexed / indexed-sequential suits database
    • Mention direct access and reliability
15. 7 Marks
    bWhen a file is removed, the blocks it occupies are simply placed back onto the free list. Can you see any problems with this? If so, how would you overcome them and what problems, if any, would now exist and how would you resolve these?
    How to answer

    • Explain free-list reuse without erasure
    • Identify security / data remanence problem
    • Propose zeroing / secure delete and trade-offs
16. 4 Marks
    aExplain the indexed and linked file allocation methods. Discuss the advantages and disadvantages in those methods.
    How to answer

    • Define linked allocation structure
    • Define indexed allocation with index block
    • Compare advantages: no fragmentation, direct access vs overhead
17. 3 Marks
    bGive an example for an application that could benefit from operating system support for random access to indexed files.
    How to answer

    • Define random access requirement
    • Give example: database, editor needing direct block access
    • Explain benefit of index
18. 7 Marks
    cSome file system allows disk storage to be allocated at different levels of granularity. For instance, a file system could allocate 4KB of disk space as a single 4KB block or as eight 512 byte blocks. How could we take advantage of the flexibility to improve performance? What modifications would have to be made to the free-space management scheme in order to support this feature?
    How to answer

    • Explain mixed granularity: large and small blocks
    • Show use for small files vs large sequential
    • Describe free-space bitmap modifications for two sizes
19. 7 Marks
    aHow long does it take to load 64 Kbyte program from a disk whose average seek time is 10msec, rotation time is 20msec and track holds 32 Kbytes. Calculate time when page size is 2 Kbyte and also when page size is 4 Kbyte. Assume that pages are spread around the disk and no two pages are on the same cylinder.
    How to answer

    • Compute pages = 64KB / page size (32 vs 16 pages)
    • Time per page = seek 10ms + rotational latency 10ms avg + transfer
    • Multiply by pages since different cylinders
    • Compare 2KB vs 4KB total
20. 7 Marks
    bGiven a disk with 200 tracks, where track requests are received in the following order: 55, 58, 39, 18, 90, 160, 150, 38, 184. The starting position for the arm is track 100. Calculate the number of tracks crossed when the following algorithms are used

    1. i)First Come First Serve
    2. ii)Shortest Seek First
    3. iii)The elevator algorithm starting in the direction
    How to answer

    • Order service for FCFS from 100
    • Order service for SSTF / Shortest Seek First
    • Order service for elevator (SCAN) and count tracks
    • Sum absolute movements