Spring '25 - F17 - CSC 345 - Midterm

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

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

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

• exec: Fails if the specified executable file does not exist or is not executable.

• unlink: Fails if the specified 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 other system resources.

Merits of dual-mode OS design:

• Provides protection and security by preventing user programs from directly accessing or modifying critical OS resources.

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

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

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

Direct memory access is used for high-speed I/O devices in order to avoid increasing the CPU’s execution load.

(a) How does the CPU interface with the device to coordinate the transfer?

(b) How does the CPU know when the memory operations are complete?

(c) The CPU is allowed to execute other programs while the DMA controller is transferring data. Does this process interfere with the execution of the user programs? If so, describe what forms of interference are caused.

(a) The CPU initializes the DMA controller by giving it the device, memory address, direction of transfer, and amount of data to transfer. The DMA controller then manages the data transfer directly between the device and memory.

(b) The DMA controller sends an interrupt to the CPU when the memory operations are complete.

(c) Yes. DMA can interfere with user programs because it uses the memory bus, which can temporarily prevent the CPU from accessing memory. This can slow down CPU execution and reduce overall system performance.

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 store kernel-specific information, such as registers, return addresses, and local variables, without interfering with the interrupted process's user stack. It also provides protection between the user program and the OS.

II-2

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 from the system.

II-3

• 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

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 solve 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 between mutex and semaphore.

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

Busy waiting: A process repeatedly checks a condition or lock 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 that allows only one thread/process to access a critical section at a time. It has two states: locked or unlocked.

• Semaphore: An integer synchronization variable controlled by wait() and signal(). It can allow one or multiple processes/threads to access a resource depending on its value.

Main difference: A mutex provides mutual exclusion for one resource, while a semaphore can control access to multiple instances of a resource.

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

III-5

Heuristic solution: 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 larger priority number implies a higher priority), and RR (quantum = 2).

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

IV-1 Turnaround TimesFCFS

Order: P1 → P2 → P3 → P4 → P5

Process	Turnaround Time
P1	3
P2	4
P3	11
P4	13
P5	23

SJF

Order: P2 → P4 → P1 → P3 → P5

Process	Turnaround Time
P1	6
P2	1
P3	13
P4	3
P5	23

Non-Preemptive Priority

Larger number = higher priority.

Order: P3 → P1 → P2 → P5 → P4

Process	Turnaround Time
P1	10
P2	11
P3	7
P4	23
P5	21

Round Robin, Quantum = 2

Order of execution:
P1 → P2 → P3 → P4 → P5 → P1 → P3 → P5 → P3 → P5 → P3 → P5 → P5

Process	Turnaround Time
P1	10
P2	3
P3	19
P4	7
P5	23

Final answer

Process	FCFS	SJF	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

(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

Since all processes arrive at time 0:

Waiting time = Turnaround time − Burst time

Process	FCFS	SJF	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

IV-3

The algorithm with the maximum average waiting time is non-preemptive Priority.

7+10+0+21+115=495=9.8 ms\frac{7+10+0+21+11}{5} =\frac{49}{5} =\boxed{9.8\text{ ms}}

Answer: Non-preemptive Priority, 9.8 ms average waiting time.

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

To analyze a resource-allocation graph, look for cycles.

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
   Since each resource has one instance and there is a cycle, the processes are deadlocked.

3. Cycle + at least one resource has multiple instances → May or may not be deadlock
   Example: P1 → R1 → P2 → R2 → P1, where R1 has multiple instances.
   The cycle alone does not prove deadlock, so further analysis is needed.

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

Yes. The system is in a safe state.

Need = Max − Allocation:

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

Available = (3, 3, 2)

A safe sequence is:

P1 → P3 → P0 → P2 → P4

Therefore:

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

file:///Users/afshansultana/Desktop/PracticeMidtermExams/MidtermExamF17-CSC345.pdf