Spring '25 - S18 - CSC 345 - Midterm

I. General Concepts (I-1) [10 points; 5 points each]

For each of the following system call, give a condition (or situation) that causes it to fail: fork and unlink

fork:

unlink:

fork: Fails if the system cannot create a new process, such as when the process limit is reached or there are insufficient resources.

unlink: Fails if the file does not exist or the process does not have permission to remove it.

(I-2) [20 points; 10 points each]

What is the difference between kernel and user mode? Explain how having two distinct modes aids in designing an operating system.

Difference:

Merits of dual-mode OS design:

Difference:

• User mode: Programs run with limited privileges and cannot directly access protected hardware or critical OS resources.

• Kernel mode: The OS kernel runs with full privileges and can access hardware, memory, and system resources.

Merits of dual-mode OS design:

• Protects the OS and hardware from user programs.

• Prevents faulty or malicious programs from interfering with other programs or crashing the system.

• Allows the OS to control privileged operations through system calls.

(I-3) [20 points; 5 points each]

What is the purpose of interrupts? What are the differences between a trap and an interrupt? Can traps be generated intentionally by a user program? If so, for what purpose?

Purpose of interrupts:
Interrupts allow the CPU to stop its current execution and respond to an event that needs attention, such as I/O completion or a hardware event.

Difference between a trap and an interrupt:

• Interrupt: Generated by hardware or an external event, usually asynchronously.

• Trap: Generated by software or as a result of the current instruction, synchronously.

Can traps be generated intentionally?
Yes. A user program can intentionally generate a trap to request an OS service through a system call, such as reading a file or creating a process.

II. Process / Threads

(II-1) [10 points] When an interrupt or a system call transfers control to the operating system, a kernel stack area separate from the stack of the interrupted process is generally used. Why?

(II-2) [20 points; 4 points each] Name 5 process states during the process life cycle. Explain briefly what each one means.

(II-3) [10 points] Explain the differences between zombies and orphans in processes.

(II-4) [10 points; 5 points each] Briefly explain the two models of inter-process communication (IPC) within an operating system.

II-1

A separate kernel stack is used to protect the user stack and store kernel-specific information, such as registers, return addresses, and local variables, while the OS handles the interrupt or system call.

II-2

Process State	Meaning
New	Process is being created.
Ready	Process is waiting to be assigned the CPU.
Running	Process is currently executing on the CPU.
Waiting/Blocked	Process is waiting for an event or I/O to complete.
Terminated	Process has finished execution and is being removed.

II-3

• Zombie: The child process has finished execution, but its parent has not yet called wait() to collect its exit status.

• Orphan: The parent process has terminated while the child process is still running.

II-4

1. Message Passing: Processes communicate by sending and receiving messages through the operating system.

2. Shared Memory: Processes communicate by accessing a shared region of memory where they can read and write data.

III. Concurrency / Synchronization (III-1) [15 points; 5 points each]

There are three issues that must be solved by any valid solution to the critical-section problem. Name what they are, and briefly explain what each of them is, using an example.

(III-2) [10 points] What does it mean by “busy waiting”?

(III-3) [10 points] Briefly explain the differences among mutex, semaphore, and condition variables

III-1

1. Mutual Exclusion: Only one process/thread can be in the critical section at a time.
   Example: If P1 is accessing shared data, P2 must wait.

2. Progress: If no process is in the critical section, a process that wants to enter should not be delayed indefinitely.
   Example: If the critical section is empty and P1 wants to enter, P1 should be allowed to enter.

3. Bounded Waiting: A process should not have to wait forever to enter the critical section.
   Example: P1 should eventually get its turn instead of P2 repeatedly entering first.

III-2

Busy waiting means a process repeatedly checks a condition while waiting instead of giving up the CPU. This wastes CPU time.

Example: A process continuously checks whether a lock is available.

III-3

• Mutex: A lock used for mutual exclusion. Only one thread can hold the mutex at a time.

• Semaphore: An integer synchronization variable controlled by wait() and signal(). It can control access to one or multiple resources.

• Condition Variable: Allows a thread to wait until a specific condition becomes true, usually while working with a mutex.

Following code snippet is an algorithm attempting to solve the dining-philosophers problem.

do { wait (chopstick[i] ); wait (chopStick[ (i + 1) % 5 ] ); // eat signal (chopstick[i] ); signal (chopstick[ (i + 1) % 5 ] ); // think } while (true);

(III-4) [10 points; 5 points each] Any problem with the above algorithm? If so (or If not), why?

(III-5) [5 points] Give a heuristic solution to resolve the potential deadlock situation above.

III-4

Yes, there is a problem. The algorithm can cause deadlock. If all 5 philosophers pick up their first chopstick at the same time, each philosopher will hold one chopstick and wait forever for the second chopstick held by another philosopher.

III-5

A heuristic solution is to allow at most 4 philosophers to try to pick up chopsticks at the same time. This guarantees that at least one philosopher can obtain both chopsticks, eat, and release them, preventing deadlock.

IV. Scheduling

Consider the following set of processes, with the length of the CPU burst time given in milliseconds: Process Burst Time Priority P1 3 3 P2 1 2 P3 7 4 P4 2 1 P5 10 2

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

(IV-1) [20 points; 5 points for each scheduler] What is the turnaround time of each process using the following scheduling algorithms: FCFS, SJF, non-preemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 2

IV-1 Turnaround Times

Turnaround Time = Completion Time − Arrival Time
Since all processes arrive at time 0, turnaround time = completion time.

Process	FCFS	SJF	Non-preemptive Priority	RR (q=2)
P1	3	6	13	10
P2	4	1	3	3
P3	11	13	23	19
P4	13	3	2	7
P5	23	23	13	23

Scheduling orders:

• FCFS: P1 → P2 → P3 → P4 → P5

• SJF: P2 → P4 → P1 → P3 → P5

• Priority: P4 → P2 → P5 → P1 → P3
  (smaller priority number = higher priority; P2 comes before P5 because P2 arrived first)

• RR (q = 2): P1 → P2 → P3 → P4 → P5 → P1 → P3 → P5 → P3 → P5 → P3 → P5 → P5

(IV-2) [20 points; 5 points for each scheduler]

What is the waiting time of each process for each of these scheduling algorithms?

(IV-3) [10 points]

Which of the algorithms results in the maximum average waiting time (over all processes)?

IV-2 Waiting Times

Waiting Time = Turnaround Time − Burst Time

Process	FCFS	SJF	Non-preemptive Priority	RR (q=2)
P1	0	3	13	7
P2	3	0	2	2
P3	4	6	16	12
P4	11	1	0	5
P5	13	13	3	13

IV-3

Average waiting times:

• FCFS: (0 + 3 + 4 + 11 + 13) / 5 = 6.2 ms

• SJF: (3 + 0 + 6 + 1 + 13) / 5 = 4.6 ms

• Priority: (13 + 2 + 16 + 0 + 3) / 5 = 6.8 ms

• RR: (7 + 2 + 12 + 5 + 13) / 5 = 7.8 ms

Answer: RR results in the maximum average waiting time, 7.8 ms.

V. Deadlocks (V-1) [30 points]

Explain how you would analyze resource allocation graph with examples to find deadlocks. You need to identify three cases we discussed in class for full credit. 10 points for each case you identify (5 points for each case, 5 points for corresponding example graph).

V-1: Resource Allocation Graph

There are 3 cases to check:

1. No cycle → No deadlock
If the resource-allocation graph has no cycle, there is no deadlock.

Example:
P1 → R1 → P2 → R2
There is no cycle, so there is no deadlock.

2. Cycle + each resource has only one instance → Deadlock
If there is a cycle and every resource in the cycle has only one instance, the processes are deadlocked.

Example:
P1 → R1 → P2 → R2 → P1
R1 and R2 each have one instance, so this cycle means deadlock.

3. Cycle + at least one resource has multiple instances → May or may not be deadlock
A cycle alone does not prove deadlock when resources have multiple instances. More analysis is needed.

Example:
P1 → R1 → P2 → R2 → P1, where R1 has multiple instances.
The cycle exists, but the system may or may not be deadlocked.

Easy way to remember

Graph situation	Result
No cycle	No deadlock
Cycle + single instance resources	Deadlock
Cycle + multiple instances	May or may not be deadlock

(V-2) [20 points]

Using the Banker’s algorithm, show what Need matrix will be at T0 (15 points; 3 points per process) and determine whether the following system is in safe state or not (5 points).

5 processes P0 through P4;

3 resource types:

A (10 instances), B (5 instances), and C (7 instances)

Snapshot at time T0: Allocation Max Available Need A B C A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3

Is the system in safe state? Yes / No

V-2

Need = Max − Allocation

Process	Allocation	Max	Need
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Available = (3, 3, 2)

Check a safe sequence:

• P1 Need (1,2,2) ≤ Available (3,3,2) → finishes, Available = (5,3,2)

• P3 Need (0,1,1) ≤ (5,3,2) → finishes, Available = (7,4,3)

• P0 Need (7,4,3) ≤ (7,4,3) → finishes, Available = (7,5,3)

• P2 Need (6,0,0) ≤ (7,5,3) → finishes, Available = (10,5,5)

• P4 Need (4,3,1) ≤ (10,5,5) → finishes

Safe sequence:
P1 → P3 → P0 → P2 → P4

Answer: YES, the system is in a safe state.

file:///Users/afshansultana/Desktop/PracticeMidtermExams/MidtermExamS18-CSC345-01.pdf