Midterm Examination

A1

Which of the following is the best description of the operating system as an "extended machine"?

• It manages the hardware resources of the computer.
• It provides a convenient abstraction that hides hardware complexity from applications.
• It schedules processes on the CPU.
• It enforces security policies on files.

A2

Which Linux directory contains the device files?

• /etc
• /proc
• /dev
• /bin

A3

In the process state model, which transition is caused by a timer interrupt?

• New → Ready
• Running → Ready
• Running → Blocked
• Blocked → Ready

A4

Which of the following is not stored in a process control block (PCB)?

• The program counter.
• The process ID.
• The contents of the process's stack.
• The open file descriptors.

A5

Which threading model multiplexes many user-level threads onto a smaller or equal number of kernel threads?

• Many-to-one
• One-to-one
• Many-to-many
• Kernel-only

A6

Which of the following is not a benefit of threads over processes?

• Cheaper context switching.
• Faster creation.
• Stronger isolation.
• Sharing of memory by default.

A7

Which scheduling algorithm provably minimises average waiting time for a given set of processes?

• First-Come, First-Served.
• Shortest Job First.
• Round Robin.
• Priority scheduling.

A8

What is the "convoy effect"?

• Many short processes waiting behind one long CPU-bound process.
• Multiple CPUs processing requests from a single shared queue.
• A process that never terminates because it is starved.
• A deadlock among processes waiting for I/O.

A9

Which of the following is not one of the three classical requirements for a correct critical-section solution?

• Mutual exclusion.
• Progress.
• Bounded waiting.
• Deadlock freedom.

A10

Which primitive is best suited to implementing a bounded buffer between a producer and a consumer?

• A spinlock.
• A mutex plus condition variables.
• A barrier.
• A reader-writer lock.

A11

Which of the following is not one of the four necessary conditions for deadlock?

• Mutual exclusion.
• Hold and wait.
• Preemption.
• Circular wait.

A12

In the Banker's algorithm, what does a "safe state" mean?

• No process is currently running.
• There exists a sequence in which all processes can finish.
• No deadlock has occurred yet.
• All resources are currently free.

A13

Which memory allocation algorithm selects the smallest hole that is large enough for the request?

• First-fit
• Best-fit
• Worst-fit
• Next-fit

A14

Which of the following is an example of external fragmentation?

• A 4 KB page whose last 1 KB is unused.
• Free memory scattered in small holes between allocated blocks.
• A file whose last block is partly unused.
• Memory wasted inside a page table.

A15

A page fault occurs when:

• The page's contents are corrupt.
• The page is not currently in physical memory.
• The page's protection bits are violated.
• The page table is corrupted.

A16

Which page-replacement algorithm can exhibit Belady's anomaly?

• LRU
• Optimal
• FIFO
• Clock

A17

In a system with a 4 KB page size and a 32-bit virtual address, how many bits are used for the page offset?

• 10 bits
• 12 bits
• 16 bits
• 20 bits

A18

What does the translation lookaside buffer (TLB) cache?

• Data blocks read from disk.
• Recent page-table entries.
• Process control blocks.
• Inodes of recently opened files.

A19

Which of the following best describes thrashing?

• High CPU utilisation with low disk I/O.
• Excessive paging that consumes CPU and I/O bandwidth, leaving little time for useful work.
• A deadlock in the memory subsystem.
• Fragmentation that wastes physical memory.

A20

Which scheduling algorithm gives the best response time for interactive processes?

• First-Come, First-Served.
• Shortest Job First (non-preemptive).
• Round Robin with a small quantum.
• Non-preemptive priority scheduling.

B1

Explain the difference between a process and a thread. State one resource that is shared between threads of the same process and one resource that is private to each thread.

B2

What is the purpose of the fork() system call? Explain how copy-on-write makes fork() efficient.

B3

Explain the difference between preemptive and non-preemptive scheduling. Give one advantage of each.

B4

What is a race condition? State the three conditions that must all hold for a race condition to occur.

B5

Explain why pthread_cond_wait must be called inside a while loop rather than an if statement.

B6

List the four necessary conditions for deadlock and give a one-sentence explanation of each.

B7

Explain the difference between internal fragmentation and external fragmentation. Which does paging eliminate, and which does it not?

B8

What is the TLB, and why is it important for performance? Explain what happens on a TLB miss.

C1

Process state transitions (6 marks). The diagram below shows a five-state process model. Identify each of the five labelled transitions (T1–T5) and give one cause of each.

        ┌──────┐          ┌───────┐          ┌────────┐
        │ New  │──T1────▶│ Ready │──T2────▶│Running │
        └──────┘          └───────┘          └────────┘
                              ▲                  │
                              │                  │
                              T5                 T3
                              │                  │
                              │                  ▼
                          ┌───────┐          ┌────────┐
                          │Blocked│◀───T4────│Running │
                          └───────┘          └────────┘

C2

Scheduling (8 marks). Four processes arrive at a single-CPU system as follows:

For each of the following algorithms, draw a Gantt chart, and compute the average waiting time, the average turnaround time, and the average response time:

1. FCFS (2 marks)
2. SJF, non-preemptive (3 marks)
3. Round Robin with quantum = 3 (3 marks)

C3

Bounded buffer with semaphores (8 marks). A bounded buffer of size B is shared by a single producer and a single consumer. The solution uses three semaphores: empty (initially B), full (initially 0), and mutex (initially 1).

1. Write the producer's sequence of semaphore operations for inserting one item. (3 marks)
2. Write the consumer's sequence of semaphore operations for removing one item. (3 marks)
3. A student modifies the producer to acquire mutex before empty. Explain the deadlock that results when the buffer is full. (2 marks)

C4

Banker's algorithm (8 marks). A system has five processes (P0–P4) and three resource types (A, B, C) with total instances (10, 5, 7). The current state is:

Currently available: (3, 3, 2).

1. Compute the Need matrix. (2 marks)
2. Is the state safe? If so, give a safe sequence and show the intermediate Work values. (4 marks)
3. P1 requests (1, 0, 2). Can the request be granted immediately? Justify your answer with the safety check. (2 marks)

C5

Page replacement (6 marks). A system uses demand paging with three physical frames. The reference string is:

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

1. Compute the number of page faults under FIFO with 3 frames. (2 marks)
2. Compute the number of page faults under FIFO with 4 frames. (2 marks)
3. What does the difference between (a) and (b) demonstrate? Name the phenomenon and explain it in one sentence. (2 marks)

D1

Sleeping barber (10 marks). A barber shop has one barber, one barber's chair, and N waiting chairs. Customers arrive at random; if a waiting chair is free, the customer sits; if the barber is asleep, the customer wakes him; if no chair is free, the customer leaves. The barber cuts hair, then sleeps if there are no customers.

Design a solution using semaphores. Your answer must include:

1. The semaphores you use, their initial values, and the shared variables they protect. (3 marks)
2. The pseudocode for the barber thread and for the customer thread. (4 marks)
3. An argument that your solution is free of race conditions, deadlock, and starvation. (3 marks)

D2

Scheduling policy analysis (10 marks). A server runs a mix of two kinds of processes: interactive processes that perform many short CPU bursts and block frequently on I/O, and batch processes that perform long CPU-bound computations with few I/O operations. The system administrator is considering three scheduling policies:

• Policy 1 — FCFS (non-preemptive).
• Policy 2 — Round Robin with a quantum of 10 ms.
• Policy 3 — Multilevel Feedback Queue with three levels: level 0 (quantum 8 ms), level 1 (quantum 16 ms), and level 2 (FCFS with aging). New processes enter at level 0; a process that exhausts its quantum is demoted; a process that blocks before exhausting its quantum remains at its current level; processes in level 2 are promoted after waiting longer than a threshold.

Write an analysis that addresses:

1. The effect of each policy on the response time of interactive processes. (3 marks)
2. The effect of each policy on the throughput of batch processes. (3 marks)
3. The risk of starvation under each policy, and how each policy (or the MLFQ's aging mechanism) addresses it. (2 marks)
4. A recommendation for a server with this mixed workload, with a justification that refers to the trade-offs you have identified. (2 marks)

C1

C2

Gantt: | P1 |  P2  |P3| P4  |
       0    7      11  12   16
Completion: P1=7, P2=11, P3=12, P4=16
Waiting:    P1=0, P2=5,  P3=7,  P4=7   → avg = 4.75
Turnaround: P1=7, P2=9,  P3=8,  P4=11  → avg = 8.75
Response:   same as waiting            → avg = 4.75

Gantt: |  P1   |P3|  P2  | P4  |
       0       7   8      12    16
Completion: P1=7, P2=12, P3=8, P4=16
Waiting:    P1=0, P2=6,  P3=3, P4=7   → avg = 4.00
Turnaround: P1=7, P2=10, P3=4, P4=11  → avg = 8.00
Response:   same as waiting            → avg = 4.00

Gantt: |P1|P2 |P3|P4 |P1 |P2|P4|P1|
       0  3   6  7   10  13 14 15  16
Completion: P1=16, P2=14, P3=7, P4=15
Waiting:    P1=9,  P2=8,  P3=2, P4=6   → avg = 6.25
Turnaround: P1=16, P2=12, P3=3, P4=10  → avg = 10.25
Response:   P1=0,  P2=1,  P3=2, P4=2   → avg = 1.25

C3

sem_wait(&empty);   /* claim an empty slot */
sem_wait(&mutex);   /* enter critical section */
/* insert item into buffer */
sem_post(&mutex);   /* leave critical section */
sem_post(&full);    /* signal a filled slot */

sem_wait(&full);    /* claim a filled slot */
sem_wait(&mutex);   /* enter critical section */
/* remove item from buffer */
sem_post(&mutex);   /* leave critical section */
sem_post(&empty);   /* signal an empty slot */

C4

        Need (A B C)
P0      7 4 3
P1      1 2 2
P2      6 0 0
P3      0 1 1
P4      4 3 1

Work = 3 3 2
P1 need 1 2 2 ≤ 3 3 2 → Work = 3 3 2 + 2 0 0 = 5 3 2
P3 need 0 1 1 ≤ 5 3 2 → Work = 5 3 2 + 2 1 1 = 7 4 3
P4 need 4 3 1 ≤ 7 4 3 → Work = 7 4 3 + 0 0 2 = 7 4 5
P0 need 7 4 3 ≤ 7 4 5 → Work = 7 4 5 + 0 1 0 = 7 5 5
P2 need 6 0 0 ≤ 7 5 5 → Work = 7 5 5 + 3 0 2 = 10 5 7

Allocation[P1] = (2,0,0) + (1,0,2) = (3, 0, 2)
Need[P1]       = (1,2,2) − (1,0,2) = (0, 2, 0)
Available      = (3,3,2) − (1,0,2) = (2, 3, 0)

P1 need 0 2 0 ≤ 2 3 0 → Work = 2 3 0 + 3 0 2 = 5 3 2
P3 need 0 1 1 ≤ 5 3 2 → Work = 5 3 2 + 2 1 1 = 7 4 3
P4 need 4 3 1 ≤ 7 4 3 → Work = 7 4 3 + 0 0 2 = 7 4 5
P0 need 7 4 3 ≤ 7 4 5 → Work = 7 4 5 + 0 1 0 = 7 5 5
P2 need 6 0 0 ≤ 7 5 5 → Work = 7 5 5 + 3 0 2 = 10 5 7

C5

1: F  [1]
2: F  [1 2]
3: F  [1 2 3]
4: F  evict 1 → [2 3 4]
1: F  evict 2 → [3 4 1]
2: F  evict 3 → [4 1 2]
5: F  evict 4 → [1 2 5]
1: H
2: H
3: F  evict 1 → [2 5 3]
4: F  evict 2 → [5 3 4]
5: H  (5 is still in frames)

1: F  [1]
2: F  [1 2]
3: F  [1 2 3]
4: F  [1 2 3 4]
1: H
2: H
5: F  evict 1 → [2 3 4 5]
1: F  evict 2 → [3 4 5 1]
2: F  evict 3 → [4 5 1 2]
3: F  evict 4 → [5 1 2 3]
4: F  evict 5 → [1 2 3 4]
5: F  evict 1 → [2 3 4 5]

D1

sem_t customers;   /* init 0 — counts waiting customers */
sem_t barber;      /* init 0 — barber is ready to cut */
sem_t mutex;       /* init 1 — protects the waiting count */
int   waiting = 0; /* number of customers currently waiting */
const int CHAIRS = N; /* number of waiting-room chairs */

void *barber_thread(void *) {
    while (1) {
        sem_wait(&customers);      /* sleep until a customer arrives */
        sem_wait(&mutex);
        waiting--;
        sem_post(&barber);         /* barber ready for this customer */
        sem_post(&mutex);
        cut_hair();
    }
}

void *customer_thread(void *) {
    sem_wait(&mutex);
    if (waiting < CHAIRS) {
        waiting++;
        sem_post(&customers);      /* wake the barber */
        sem_post(&mutex);
        sem_wait(&barber);         /* wait until barber is ready */
        get_haircut();
    } else {
        sem_post(&mutex);          /* no chair, leave */
    }
}

D2