Operating Systems, Past Papers

Operating System Past Paper 2015 – MSc IT 2nd Term UOS

Operating System Past Paper 2015 MSc IT 2nd Term UOS – Page 1

University of Sargodha (UOS) M.Sc. IT 2nd term Operating System (CMP-3611) past paper 2015, with the full question paper in text form and solved answers, including Gantt charts, memory placement and page-replacement working.

Operating System Past Paper 2015 MSc IT 2nd Term UOS – Page 2
Page 2 of 2

Print / download (A4, high quality): Page 1 · Page 2

Operating System Past Paper 2015 MSc IT (text version)

University of Sargodha – M.Sc. 2nd Term Exam 2015, Subject: I.T
Paper: Operating System (CMP-3611) · Time: 2:30 hours · Maximum marks: 80

Objective part (compulsory) – Q1: Answer in 2–3 lines, 2 marks each (32 marks)

  1. What is the difference between internal fragmentation and external fragmentation?
  2. Define virtual memory.
  3. Define system calls.
  4. Define interrupts.
  5. What are the three major activities of an operating system with regard to memory management?
  6. What is processor affinity?
  7. What is the medium-term scheduler?
  8. What is a critical section?
  9. What are the four conditions of deadlock?
  10. Differentiate between dynamic loading and dynamic linking.
  11. Differentiate between paging and segmentation.
  12. What are the main parts of a process?
  13. What are semaphores?
  14. How to avoid deadlock?
  15. How to handle deadlock?
  16. Differentiate between the long-term and short-term scheduler.

Subjective part – Attempt any four questions, all carry equal marks (12 × 4 = 48)

Q2. (a) Define PCB and what type of information is saved in it. (b) Define multithreading and its advantages.

Q3. (a) Explain the Resource Allocation Graph algorithm. (b) Write down the code using semaphores that synchronizes the reader–writer problem.

Q4. Given memory partitions of 100K, 600K, 200K, 300K and 500K (in order), how would each of the First-fit, Best-fit and Worst-fit algorithms place processes of 409K, 236K, 125K and 514K (in order)? Also define the First-fit, Best-fit and Worst-fit algorithms.

Q5. (a) Briefly explain the operating system services. (b) Briefly explain segmentation.

Q6. Consider the following set of processes, with the length of the CPU burst given in milliseconds:

ProcessBurst timePriority
P1103
P211
P323
P414
P552

The processes are assumed to arrive in the order P1, P2, P3, P4, P5, all at time 0. (a) Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, non-preemptive priority (a smaller priority number implies a higher priority) and RR (quantum = 1). (b) Obtain the average waiting time. (c) Obtain the average waiting time. (Printed twice on the paper; the standard version of this question asks for turnaround time in one part, so both are solved below.)

Q7. (a) Define a page-replacement algorithm using this basic idea. What is the minimum number of page faults for an optimal page-replacement strategy for the reference string with four page frames: 1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2. (b) Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 milliseconds. Addresses are translated through a page table in main memory, with an access time of 1 microsecond per memory access. Thus, each memory … (the rest of the question is cut off in our copy of the paper; the standard textbook version is solved below).

Original paper (scanned copy)

The clean paper above is retyped by Shining Study from this original University of Sargodha question paper. Click a scan to view it full size.

Operating System Past Paper 2015 MSc IT 2nd Term UOS – original scan

Solved answers

Q1 – Short questions

1. Internal fragmentation: wasted space inside an allocated block because the block is bigger than the request (e.g. fixed partitions, paging’s last page). External fragmentation: enough total free memory exists but it is split into small non-contiguous holes, so a request cannot be satisfied (variable partitions, segmentation). Compaction or paging solves external fragmentation.

2. Virtual memory is a technique that lets a process run even if it is not completely in main memory. Each process gets a large logical address space; only needed pages are loaded (demand paging), the rest stay on disk. Programs can be larger than physical memory and more processes fit in RAM.

3. System calls are the programming interface to OS services. A user program uses them to request kernel work, e.g. fork(), open(), read(), write(). Types: process control, file management, device management, information maintenance and communication.

4. An interrupt is a signal from hardware (or software, a trap) that makes the CPU stop the current work, save its state and run an interrupt service routine through the interrupt vector, then resume. Examples: I/O completion, timer, divide-by-zero.

5. (i) Keeping track of which parts of memory are in use and by whom; (ii) deciding which processes (or parts) and data to move into and out of memory; (iii) allocating and deallocating memory space as needed.

6. Processor affinity: on a multiprocessor system, a process prefers to keep running on the same CPU, because its data is already in that CPU’s cache. Soft affinity = OS tries to keep it; hard affinity = the process is bound to specific CPUs.

7. The medium-term scheduler swaps processes out of memory (to disk) and later back in, to reduce the degree of multiprogramming or improve the process mix. It sits between the long-term and short-term schedulers.

8. A critical section is the part of a program where a process accesses shared data (variables, files). Only one process may be in its critical section at a time. A solution must ensure mutual exclusion, progress and bounded waiting.

9. Mutual exclusion, hold and wait, no preemption, circular wait. Deadlock can occur only if all four hold at the same time.

10. Dynamic loading: a routine is not loaded into memory until it is called, saving memory; handled by the program. Dynamic linking: linking to library routines (DLL/.so) is postponed until run time through a stub; one shared copy of the library serves many programs and needs OS support.

11. Paging divides memory into fixed-size pages/frames, is invisible to the programmer, has no external fragmentation but has internal fragmentation, and uses a page table (page number, offset). Segmentation divides a program into variable-size logical units (code, stack, data), is visible to the programmer, has external fragmentation, and uses a segment table (base, limit).

12. A process in memory has: text section (program code), program counter and registers, stack (function parameters, return addresses, local variables), data section (global variables) and heap (dynamically allocated memory).

13. A semaphore is an integer variable S used for synchronization, accessed only by two atomic operations: wait(S) (P – decrement, block if not available) and signal(S) (V – increment, wake a waiting process). Types: counting and binary (mutex).

14. Deadlock avoidance: the OS needs advance information about maximum resource needs and grants a request only if the system stays in a safe state. Algorithms: resource-allocation graph (single instance) and Banker’s algorithm (multiple instances).

15. Three ways: (i) prevention or avoidance – make sure deadlock never happens (break one of the four conditions, or Banker’s algorithm); (ii) detection and recovery – allow it, detect it, then abort processes or preempt resources; (iii) ignore it (ostrich approach, used by most OSs including UNIX and Windows).

16. Long-term (job) scheduler selects processes from the job pool and loads them into memory; runs infrequently and controls the degree of multiprogramming. Short-term (CPU) scheduler selects which ready process gets the CPU next; runs very often (milliseconds) so it must be fast.

Q2

(a) PCB (process control block): the data structure the OS keeps for each process; it represents the process in the OS and is saved/restored during a context switch. Information stored: process state (new, ready, running, waiting, terminated); process ID; program counter; CPU registers; CPU-scheduling information (priority, queue pointers); memory-management information (base/limit registers, page or segment tables); accounting information (CPU time used, time limits); I/O status information (allocated devices, list of open files).

(b) Multithreading: a process contains several threads, each with its own program counter, registers and stack, but sharing code, data and open files. Advantages: responsiveness (one thread can keep the program responsive while another blocks); resource sharing (threads share memory automatically); economy (creating and switching threads is much cheaper than processes); scalability (threads can run in parallel on multicore CPUs). Models: many-to-one, one-to-one, many-to-many.

Q3

(a) Resource-allocation graph algorithm (deadlock avoidance, single instance of each resource): the graph has process nodes and resource nodes, request edges P → R, assignment edges R → P, and a claim edge P ⇢ R (dashed) showing P may request R in the future. All claim edges must be declared in advance. When P requests R, the claim edge becomes a request edge; the request is granted only if converting the request edge into an assignment edge R → P does not create a cycle in the graph (cycle detection takes O(n²)). If a cycle would form, the system would be unsafe, so P must wait. When P releases R, the assignment edge turns back into a claim edge. For detection: if each resource has one instance, a cycle means deadlock; with multiple instances a cycle means a possible deadlock.

(b) Readers–writers with semaphores (first readers–writers problem):

semaphore rw_mutex = 1;   // shared by readers and writers
semaphore mutex = 1;      // protects read_count
int read_count = 0;

/* Writer */
do {
    wait(rw_mutex);
        /* writing is performed */
    signal(rw_mutex);
} while (true);

/* Reader */
do {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);       // first reader locks out writers
    signal(mutex);

        /* reading is performed */

    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);     // last reader lets writers in
    signal(mutex);
} while (true);

Many readers can read at the same time, but a writer gets exclusive access. (Writers may starve in this version.)

Q4 – First-fit, Best-fit, Worst-fit

First-fit: allocate the first hole that is big enough. Best-fit: allocate the smallest hole that is big enough (least leftover). Worst-fit: allocate the largest hole (largest leftover).

ProcessFirst-fitBest-fitWorst-fit
409K600K (191K left)500K (91K left)600K (191K left)
236K300K (64K left)300K (64K left)500K (264K left)
125K191K hole from 600K (66K left)200K (75K left)300K (175K left)
514KMust wait – no hole ≥ 514K600K (86K left)Must wait

Only Best-fit places all four processes, so it uses memory most efficiently here.

Q5

(a) Operating system services: user interface (CLI, GUI, batch); program execution (load, run, end normally or abnormally); I/O operations; file-system manipulation (create, delete, read, write, search, permissions); communication between processes (shared memory or message passing); error detection (hardware, I/O, program errors). For system efficiency: resource allocation, accounting, and protection and security.

(b) Segmentation: a memory-management scheme that supports the user’s view of memory: a program is a collection of variable-size segments (main program, functions, stack, symbol table, arrays). A logical address is <segment number, offset>. The segment table holds a base (starting physical address) and limit (length) for each segment. If offset < limit, physical address = base + offset; otherwise a trap (addressing error). It allows protection and sharing per segment but suffers from external fragmentation.

Q6 – CPU scheduling

FCFS:
| P1                       | P2 | P3   | P4 | P5          |
0                          10   11     13   14            19

SJF (non-preemptive):
| P2 | P4 | P3   | P5          | P1                       |
0    1    2      4             9                          19

Non-preemptive priority:
| P2 | P5          | P1                       | P3   | P4 |
0    1             6                          16     18   19

Round Robin (q = 1):
|P1|P2|P3|P4|P5|P1|P3|P5|P1|P5|P1|P5|P1|P5|P1|P1|P1|P1|P1|
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19

Waiting time = turnaround time − burst time (all arrive at 0, so turnaround = completion time).

ProcessFCFSSJFPriorityRR
P10969
P210001
P3112165
P4131183
P514419
Average waiting9.6 ms3.2 ms8.2 ms5.4 ms
Turnaround timeFCFSSJFPriorityRR
P1 / P2 / P3 / P4 / P510 / 11 / 13 / 14 / 1919 / 1 / 4 / 2 / 916 / 1 / 18 / 19 / 619 / 2 / 7 / 4 / 14
Average13.4 ms7.0 ms12.0 ms9.2 ms

SJF gives the minimum average waiting time (3.2 ms), as expected.

Q7

(a) Optimal (OPT) replacement replaces the page that will not be used for the longest time in the future. It gives the lowest possible fault rate and is used as a benchmark. With 4 frames:

Ref:  1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2
Fault F F F F F . . . F F F . . F . . . . F . . F
Replacements: 5 (out 2), 6 (out 1), 7 (out 3), 8 (out 6),
9 (out 4), 4 (out 7), 2 (out 8)
Final frames: 5 4 9 2

First 4 references fill the frames (4 faults), then 7 more faults with replacement: minimum page faults = 11.

(b) The question is cut off in our copy. The standard textbook version continues: each memory reference through the page table takes two accesses; an associative memory (TLB) is added that reduces access to one memory reference when the entry is found there; 80% of accesses are found in the associative memory, and of the remaining, 10% (2% of the total) cause page faults. What is the effective memory access time?

EAT = 0.80 × 1 µs + 0.18 × 2 µs + 0.02 × (20,000 µs + 2 µs) = 0.80 + 0.36 + 400.04 ≈ 401.2 µs. Page faults dominate the access time even when they are only 2% of references.

Answers prepared by Shining Study for revision. Check them against your class notes and teacher’s guidance.

About Saif R

An educator and technology enthusiast passionate about empowering students through quality education and digital learning. Dedicated to making academic resources and opportunities accessible to everyone.