Spring '25 - S18 - CSC 345 - Midterm

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

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

chmod = change file permissions (read, write, or execute the file) 

kill = send a signal to a process (sends SIGTERM to the process with that PID)

wait - parent waits for one of its child processes to terminate

THEY CAN FAIL:

chmod: fails if the process doesn’t have permission to change the file’s permissions

kill: fails if the specified process does not exist/ caller has no permission to send a signal to process

wait: fails if the calling process has no child processes

chmod → permission problem

kill → process doesn’t exist

wait → no child

chmod: Fails if the process does not have permission to change the file's permissions, such as when it is not the file owner.

kill: Fails if the specified process does not exist or the process does not have permission to send it a signal.

wait: Fails if the calling process has no unwaited-for child processes.

(I-2) [35 points]

What are the major differences between monolithic kernel and microkernel? Explain with pros and cons of each kernel type.

Difference [15 points]:

Monolithic kernel: Most OS services run inside the kernel. Its main advantage is fast performance because components communicate directly, but it is less reliable because a failure in one kernel component can affect the entire system.

Microkernel: Only essential services run in the kernel, while other services run in user space. It is more reliable and secure because services are isolated, but it can be slower due to message-passing and communication overhead.

	Monolithic	Microkernel
Where are most OS services?	Kernel space	User space
Performance	Faster	Slower
Reliability	Lower	Higher
Security	Lower	Higher
Communication	Direct	Message passing
Main problem	Large/complex kernel	Communication overhead

	Monolithic Kernel	Microkernel
Difference	Most OS services, such as process management, memory management, file systems, and device drivers, run in kernel mode as one large kernel.	Only essential services run in kernel mode, while other services run in user mode and communicate through message passing.
Merits	Faster performance because services communicate directly within the kernel.	More reliable, secure, and modular because services are isolated from the kernel.
Demerits	A failure in one service can crash the entire system. It is harder to maintain and debug.	Slower performance due to message passing and communication between services.

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?

The kernel uses a separate kernel stack to safely store kernel-specific data, such as registers, return addresses, and local variables, without interfering with the interrupted process's user stack. This also provides protection and isolation between user programs and the operating system.

A separate kernel stack is used to provide a safe, protected stack for the OS when handling an interrupt or system call, preventing the user process from interfering with kernel data.

(II-2) [20 points; 4 points each]

Name 5 process states during the process life cycle. Explain briefly what each one means.

1. New: The process is being created.

2. Ready: The process is waiting to be assigned to the CPU.

3. Running: The process is currently executing on the CPU.

4. Waiting/Blocked: The process is waiting for an event or I/O to complete.

5. Terminated: The process has finished execution and is being removed.

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

• Zombie: A child process has finished execution, but its parent is still running and has not called wait() to collect its exit status.

• Orphan: A child process is still running, but its parent process has terminated.

(II-4) [10 points; 5 points each]

Briefly explain the two models of inter-process communication (IPC) within an operating system.

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 shared 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

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 P1 and P2 both want to enter and the critical section is empty, one 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) [10 points]

Briefly explain the differences between test_and_set() and compare_and_swap()?

• test_and_set(): Atomically reads the value of a variable and sets it to true. It returns the old value. It is commonly used to implement locks.

• compare_and_swap(): Atomically compares a variable with an expected value. If they are equal, it replaces the variable with a new value. It returns the old value (or indicates whether the swap occurred).

Main difference:

test_and_set() always sets the value to true, while compare_and_swap() changes the value only if it matches the expected value.

(III-3) [10 points]

Briefly explain what Peterson’s algorithm and its usage in operating system synchronization

Peterson’s Algorithm: A software-based solution to the critical-section problem for two processes. It uses two shared variables, flag[] to indicate that a process wants to enter the critical section and turn to indicate whose turn it is.

Usage: It provides mutual exclusion, progress, and bounded waiting, allowing two processes to safely access shared data without both entering the critical section at the same time.

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 wait for the second chopstick, which is held by a neighboring philosopher. Therefore, no philosopher can continue.

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

(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).

Since all processes arrive at time 0, turnaround time = completion time.

IV-1 Turnaround Times

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

Schedules used

FCFS:
P1 → P2 → P3 → P4 → P5

SJF:
P2 → P4 → P1 → P3 → P5

Priority:
P3 → P1 → P2 → P5 → P4
(smaller number = higher priority)

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

(IV-2) [20 points; 5 points for each scheduler] What is the waiting time of each process for each of these scheduling algorithms?

Since all processes arrive at time 0:

Waiting time = Turnaround time − Burst time

IV-2 Waiting Times

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

Copy-ready final table:

FCFS: P1 = 0, P2 = 3, P3 = 4, P4 = 11, P5 = 13
SJF: P1 = 3, P2 = 0, P3 = 6, P4 = 1, P5 = 13
Priority: P1 = 7, P2 = 10, P3 = 0, P4 = 21, P5 = 11
RR: P1 = 7, P2 = 2, P3 = 12, P4 = 5, P5 = 13

(IV-3) [10 points]

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

SJF results in the minimum average waiting time.

Calculation:

3+0+6+1+135=235=4.6 ms\frac{3+0+6+1+13}{5}=\frac{23}{5}=\mathbf{4.6\ ms}

Answer: SJF, with an average waiting time of 4.6 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 (RAG)

To determine whether there is a deadlock, look for cycles in the resource allocation graph.

1. No cycle → 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

Example:

P1 → R1 → P2 → R2 → P1

There is a cycle, and each resource has only one instance. Therefore, there is a deadlock.

3. Cycle + at least one resource has multiple instances → May or may not be deadlock

Example:

P1 → R1 → P2 → R2 → P1

If R1 has multiple instances, the cycle alone does not prove deadlock. We need further analysis to determine whether the processes can still proceed.

Key rule to remember

• No cycle → No deadlock

• Cycle + single instance → 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 Answer

Need = Max − Allocation

Process	Allocation (A B C)	Max (A B C)	Need (A B C)
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)

Safety check

Start: Work = (3, 3, 2)

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

• P3 Need (0,1,1) ≤ Work → finishes → Work = (7,4,3)

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

• P2 Need (6,0,0) ≤ Work → finishes → Work = (10,5,5)

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

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

Final answer:

Yes, the system is in a safe state.

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