Spring '25 - F16 - CSC 345 - Midterm

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

How are iOS and Android similar? How are they different? (

I-2) [25 points; 5 points each] What are the five major activities of an operating system in regard to file management?

(I-3) [10 points] Why is the separation of mechanism and policy desirable?

(I-4) [5 points] What are the advantages of using loadable kernel modules?

I. General Concepts

I-1) How are iOS and Android similar? How are they different?

Similarities:

• Both are mobile operating systems designed for smartphones and tablets.

• Both provide multitasking, memory management, security, networking, and file management.

• Both support application development using software development tools and APIs.

Differences:

• iOS is developed by Apple and is mainly used on Apple devices such as iPhones and iPads.

• Android is developed by Google and is used by many different device manufacturers.

• iOS is more closed and controlled by Apple, while Android is more open and customizable.

---

I-2) What are the five major activities of an operating system in regard to file management?

1. Create and delete files.

2. Create and delete directories.

3. Provide primitives for manipulating files and directories.

4. Map files onto secondary storage.

5. Back up files on stable, nonvolatile storage.

---

I-3) Why is the separation of mechanism and policy desirable?

It separates how something is done (mechanism) from what should be done (policy). This makes the OS more flexible because policies can be changed without having to change the underlying mechanisms.

---

I-4) What are the advantages of using loadable kernel modules?

• Modules can be added or removed while the system is running.

• They make the kernel more modular and easier to maintain.

• New functionality can be added without rebuilding the entire kernel.

• They can reduce memory usage by loading only needed modules.

II. Process / Threads (II-1) [20 points]

Describe the actions taken by a kernel to context-switch between processes.

(II-2) [15 points] In class, we discussed Google’s Chrome browser and its practice of opening each new website in a separate process. Would the same benefits have been achieved if instead Chrome had been designed to open each new website in a separate thread? Explain.

(II-3) [15 points] Is it possible to have concurrency but not parallelism? Explain.

II. Process / ThreadsII-1) Describe the actions taken by a kernel to context-switch between processes.

1. Save the state of the currently running process, including its registers and program counter, into its PCB.

2. Change the process state and select another ready process to run.

3. Load the saved state of the selected process from its PCB.

4. Restore its registers, program counter, and other needed information.

5. Resume execution of the selected process.

---

II-2) Chrome: separate process vs. separate thread

No, the same benefits would not have been achieved.

Using a separate process for each website provides better isolation. If one website crashes or has a security problem, it is less likely to affect the other websites because processes have separate address spaces.

If Chrome used separate threads, the threads would share the same process address space and resources. Therefore, a crash or memory corruption in one thread could affect the other websites.

Main benefit of separate processes: better isolation, stability, and security.

---

II-3) Is it possible to have concurrency but not parallelism? Explain.

Yes.

Concurrency means multiple tasks are making progress during the same period, but they do not have to execute at the exact same time.

For example, on a single-core CPU, the OS can rapidly switch between two processes. Both processes make progress, so there is concurrency, but only one process executes at any given instant, so there is no parallelism.

(II-4) [20 points; 5 points each] Using the following program, identify the values of pid at lines A, B, C, and D. (Assume that the actual pids of the parent and child are 1885 and 1900, respectively.)

#include #include #include int main() { pid t pid, pid1; /* fork a child process / pid = fork(); if (pid < 0) { / error occurred / fprintf(stderr, "Fork Failed"); return 1; } else if (pid == 0) { / child process / pid1 = getpid(); printf("child: pid = %d",pid); / A / printf("child: pid1 = %d",pid1); / B / } else { / parent process / pid1 = getpid(); printf("parent: pid = %d",pid); / C / printf("parent: pid1 = %d",pid1); / D */ wait(NULL); } return 0; }

II-4) Values of pid at lines A, B, C, and D

Given:

• Parent PID = 1885

• Child PID = 1900

Remember:

• fork() returns 0 to the child

• fork() returns the child's PID to the parent

• getpid() returns the PID of the process currently running

Line	Process	Value	Why
A	Child	0	fork() returns 0 in the child
B	Child	1900	getpid() returns the child's PID
C	Parent	1900	fork() returns the child's PID to the parent
D	Parent	1885	getpid() returns the parent's PID

Final answer:

A = 0
B = 1900
C = 1900
D = 1885

III. Concurrency / Synchronization [70 points]

Suppose we have designed an algorithm for a bounded-buffer monitor in which the buffers (portions) are embedded within the monitor itself like below. Fill in the blanks [10 points each].

monitor bounded_buffer { int items[MAX ITEMS]; int numItems = 0; condition full, empty; void produce(int v) { while (numItems == MAX ITEMS) ______________.wait(); items[numItems++] = v; ______________.signal(); } int consume() { int retVal; while (numItems == 0) empty.____________________; retVal = items[--numItems]; full._____________________; return retVal; } }

Here, we impose a strict mutual exclusion within the monitor. This makes the monitor mainly suitable for small portions. Briefly explain why this is true [15 points] and suggest a workaround so that it becomes suitable for larger portions [15 points].

III. Concurrency / SynchronizationBlanks [10 points each]

The completed code is:

void produce(int v) {
    while (numItems == MAX_ITEMS)
        full.wait();

    items[numItems++] = v;
    empty.signal();
}

int consume() {
    int retVal;

    while (numItems == 0)
        empty.wait();

    retVal = items[--numItems];
    full.signal();

    return retVal;
}

Answers:

1. full

2. empty

3. wait()

4. signal()

---

Why is the monitor mainly suitable for small portions? [15 points]

Because mutual exclusion is enforced for the entire monitor. While one thread is producing or consuming, other threads cannot enter the monitor. If the portion of work takes a long time, other threads must wait, which reduces concurrency and performance.

Workaround for larger portions [15 points]

Keep only the short critical sections inside the monitor. Move the large or time-consuming portions of the work outside the monitor, using the monitor only to safely access the shared buffer and update its state.

Exam-ready answer:

The monitor is suitable for small portions because mutual exclusion prevents other threads from entering the monitor while one thread is executing inside it. For larger portions, keep only the shared-data operations inside the monitor and perform the time-consuming work outside the monitor.

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 each] Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, non-preemptive priority (a larger priority number implies a higher priority), and RR (quantum = 2).

IV-1) Gantt Charts

Given:

Process	Burst	Priority
P1	3	3
P2	1	2
P3	7	4
P4	2	1
P5	10	2

All arrive at time 0 in order P1, P2, P3, P4, P5.

1. FCFS

Order: P1 → P2 → P3 → P4 → P5

0      3    4        11   13              23
|  P1  | P2 |   P3   | P4 |      P5       |

2. SJF

Shortest burst first: P2 → P4 → P1 → P3 → P5

0   1     3       6             13              23
| P2 | P4 |  P1   |      P3     |       P5      |

3. Non-preemptive Priority

Larger priority number = higher priority.

Order: P3 (4) → P1 (3) → P2 (2) → P5 (2) → P4 (1)

For the tie between P2 and P5, use their arrival order, so P2 comes before P5.

0       7       10   11              21    23
|  P3   |  P1   | P2 |       P5       | P4 |

4. Round Robin, quantum = 2

Execution order:

P1 → P2 → P3 → P4 → P5 → P1 → P3 → P5 → P3 → P5 → P3 → P5 → P5

0    2  3    5    7    9   10   12   14   16   18   20   22  23
| P1 |P2| P3 | P4 | P5 |P1| P3 | P5 | P3 | P5 | P3 | P5 |P5|

Final orders:

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

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

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

• 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 turnaround time of each process for each of the scheduling algorithms in part a?

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

(IV-4) [10 points] Which of the algorithms results in the maximum average waiting time (over all processes)?

IV-2) Turnaround Time

Since all processes arrive at time 0:

Turnaround time = Completion time − Arrival time = Completion time

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

Priority order: P3 → P1 → P2 → P5 → P4, because larger priority number = higher priority.

---

IV-3) Waiting Time

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-4) Maximum Average Waiting Time

Calculate the averages:

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

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

• Priority: (7 + 10 + 0 + 21 + 11) / 5 = 9.8 ms

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

Answer:

Non-preemptive Priority has the maximum average waiting time: 9.8 ms.

V. Deadlocks

(V-1) [40 points] In class, we describe a situation in which we prevent deadlock by ensuring that all locks are acquired in a certain order. However, we also point out that deadlock is possible in this situation if two threads simultaneously invoke the transaction() function. Fix the transaction() function to prevent deadlocks.

void transaction(Account from, Account to, double amount) { mutex lock1, lock2; lock1 = get lock(from); lock2 = get lock(to); acquire(lock1); acquire(lock2); withdraw(from, amount); deposit(to, amount); release(lock2); release(lock1); }

(V-2) [30 points] Explain how you analyze resource allocation graph with examples to find deadlocks. (10 points for each case you identify; thus, you need to identify three cases for full credit)

V. DeadlocksV-1) Fix transaction() to prevent deadlocks

The problem is that two threads could acquire the two account locks in opposite orders.

For example:

• Thread 1: locks A, then waits for B

• Thread 2: locks B, then waits for A

To prevent this, always acquire locks in a consistent order, such as based on the account ID.

void transaction(Account from, Account to, double amount) {
    mutex lock1, lock2;

    if (from.id < to.id) {
        lock1 = get_lock(from);
        lock2 = get_lock(to);
    } else {
        lock1 = get_lock(to);
        lock2 = get_lock(from);
    }

    acquire(lock1);
    acquire(lock2);

    withdraw(from, amount);
    deposit(to, amount);

    release(lock2);
    release(lock1);
}

Exam answer: Always acquire the two locks in the same global order. This prevents circular wait, so the two threads cannot deadlock.

---

V-2) Resource Allocation Graph

A resource-allocation graph uses:

• Process → Resource: process is requesting the resource.

• Resource → Process: resource has been allocated to the process.

There are three cases:

Case 1: No cycle → No deadlock

Example:

P1 → R1 → P2 → R2

There is no cycle, so there is no deadlock.

Case 2: Cycle + one instance of each resource → Deadlock

Example:

P1 → R1 → P2 → R2 → P1

If R1 and R2 each have only one instance, the cycle means each process is waiting for a resource held by the other.

Therefore, there is a deadlock.

Case 3: Cycle + multiple instances of a resource → May or may not be deadlock

Example:

P1 → R1 → P2 → R2 → P1

If R1 or R2 has multiple instances, a cycle does not necessarily mean deadlock. Another instance of the needed resource may be available, allowing a process to continue.

Therefore, further analysis is needed.

Easy way to remember:

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

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