CS2850 2024 Past Paper Solution

CS2850: Operating Systems - 2024 Past Paper Solution

Question 1: Theory Questions (25 marks)

(a) Briefly describe I/O handling based on interrupts. Give one advantage of this method over busy waiting.

Description of Interrupt-based I/O Handling:
Interrupt-based I/O handling is a mechanism where the CPU initiates an I/O operation with a device and then continues executing other tasks. Instead of the CPU continuously checking the status of the I/O device (as in busy waiting), the I/O device itself notifies the CPU once the requested operation is complete or if an error occurs. This notification is called an interrupt.

The process is as follows:

  1. The CPU issues a command to an I/O module (e.g., disk controller) to perform an operation (e.g., read data).
  2. The I/O module starts the operation. The CPU is now free to perform other tasks or run other processes.
  3. When the I/O module completes the operation (or an error occurs), it sends an interrupt signal to the CPU.
  4. The CPU detects the interrupt. It suspends its current execution (saving its state, like the program counter and registers).
  5. The CPU then executes a special routine called an Interrupt Service Routine (ISR) or interrupt handler, which is specific to the type of interrupt received. This routine determines the cause of the interrupt, performs any necessary data transfer, and clears the interrupt.
  6. After the ISR completes, the CPU restores the saved state of the suspended task and resumes its execution.

Advantage over Busy Waiting:

  • Increased CPU Efficiency: The primary advantage of interrupt-based I/O over busy waiting is significantly improved CPU utilization. In busy waiting, the CPU wastes cycles repeatedly polling the device status. With interrupts, the CPU can perform useful work on other processes or tasks while the I/O operation is in progress, only attending to the device when it explicitly signals completion. This leads to better overall system performance and responsiveness.

(b) This question is about the Round Robin scheduling algorithm for interactive systems:

i. Briefly explain how the algorithm works.

Round Robin (RR) Algorithm Explanation:
The Round Robin scheduling algorithm is designed primarily for time-sharing systems. It is a preemptive scheduling algorithm.

  1. Ready Queue as FIFO: Processes ready to run are kept in a First-In, First-Out (FIFO) queue called the ready queue.
  2. Time Quantum (Time Slice): Each process is allocated a small unit of CPU time called a time quantum or time slice (typically 10-100 milliseconds).
  3. Execution and Preemption:
    • The scheduler picks the first process from the ready queue and dispatches it to the CPU.
    • The process runs for, at most, the duration of one time quantum.
    • If the process completes its CPU burst before the time quantum expires, it voluntarily relinquishes the CPU. The scheduler then proceeds to the next process in the ready queue.
    • If the CPU burst of the currently running process is longer than the time quantum, the timer goes off, generating an interrupt. The OS then preempts the process, context-switches it out, moves it to the tail of the ready queue, and dispatches the next process from the head of the ready queue.
  4. Fairness: RR ensures that each process gets a fair share of the CPU over time, preventing any single process from monopolizing the CPU. This makes it suitable for interactive systems where responsiveness is important.

ii. Consider four processes A, B, C, and D. Suppose their running times are:
A: 3ms, B: 7ms, C: 4ms, D: 5ms.
Indicate how these processes are scheduled by the Round Robin scheduling algorithm until all finish their execution, assuming a quantum length of 4ms. The initial list of runnable processes is A, B, C, D (A is at the head). Make sure to show all your workings.

Round Robin Scheduling Execution:
Quantum = 4ms
Initial Ready Queue: [A, B, C, D]
Process Running Times: A=3, B=7, C=4, D=5

Time Process Running CPU Time Used Remaining Time Ready Queue Notes
0 A A=3, B=7, C=4, D=5 [B, C, D] A starts
3 A 3 (ends) A=0, B=7, C=4, D=5 [B, C, D] A finishes (used 3ms < 4ms quantum)
3 B B=7, C=4, D=5 [C, D] B starts
7 B 4 B=3, C=4, D=5 [C, D, B] B quantum expires, B preempted
7 C B=3, C=4, D=5 [D, B] C starts
11 C 4 (ends) B=3, C=0, D=5 [D, B] C finishes (used 4ms = 4ms quantum)
11 D B=3, D=5 [B] D starts
15 D 4 B=3, D=1 [B, D] D quantum expires, D preempted
15 B B=3, D=1 [D] B starts (remaining 3ms)
18 B 3 (ends) B=0, D=1 [D] B finishes (used 3ms < 4ms quantum)
18 D D=1 [] D starts (remaining 1ms)
19 D 1 (ends) D=0 [] D finishes (used 1ms < 4ms quantum)

Execution Order & Gantt Chart:

1
2
A (3ms) | B (4ms) | C (4ms) | D (4ms) | B (3ms) | D (1ms)
0-------3---------7---------11--------15--------18--------19 ms

Workings:

  1. 0-3ms: A runs for 3ms and finishes. Ready Queue: [B, C, D].
  2. 3-7ms: B runs for its quantum of 4ms. Remaining time for B is 7-4 = 3ms. B is moved to the end of the queue. Ready Queue: [C, D, B].
  3. 7-11ms: C runs for 4ms and finishes. Ready Queue: [D, B].
  4. 11-15ms: D runs for its quantum of 4ms. Remaining time for D is 5-4 = 1ms. D is moved to the end of the queue. Ready Queue: [B, D].
  5. 15-18ms: B runs for its remaining 3ms and finishes. Ready Queue: [D].
  6. 18-19ms: D runs for its remaining 1ms and finishes. Ready Queue: [].

All processes have completed execution.

(c) Explain in which scenario context switching is faster for threads than for processes.

Context switching is faster for threads within the same process (often called kernel-level threads or lightweight processes if they share the same address space) than for traditional heavyweight processes primarily because:

  1. Shared Address Space: Threads within the same process share the same memory address space. When switching between these threads, the operating system does not need to change the memory management context (e.g., page tables, TLB entries). This is a significant overhead in process context switching, as each process typically has its own distinct address space. Flushing and reloading page table information can be time-consuming.
  2. Shared Resources: Besides the address space, threads within the same process also share other resources like open files, global variables, and child processes. Switching between threads of the same process involves saving and restoring fewer resources compared to switching between different processes which have their own isolated sets of these resources.

Therefore, a context switch between threads of the same process mainly involves saving and restoring the thread-specific context, such as the program counter, registers, stack pointer, and thread-specific data. This is a much lighter operation than a full process context switch which requires changing the entire memory map and managing a larger set of distinct resources.

User-level threads, if managed entirely within a single process without kernel involvement for each switch, can be even faster, as a context switch might just involve a procedure call within the process. However, the question likely refers to kernel-supported threads where the OS is aware of them.

(d) Consider a program that consists of the following two concurrent processes sharing the variable x:
P1: x=4; if (x>3) { x=x+5; } else { x=x*3; }
P2: x=2; x=x*2;
How many different values may the variable x have when the program terminates? Give a possible execution sequence for each case.

Let’s analyze the possible interleavings of operations. Assume x is initially undefined or 0 before P1 or P2 assign to it. The critical operations are the assignment to x and the read of x in P1’s conditional.

Operations:

  • P1_assign_4: x = 4
  • P1_check_cond: if (x > 3)
  • P1_add_5: x = x + 5
  • P1_mul_3: x = x * 3
  • P2_assign_2: x = 2
  • P2_mul_2: x = x * 2

Possible Final Values of x:

  1. Scenario 1: P1 executes completely, then P2 executes completely.

    • P1_assign_4 (x becomes 4)
    • P1_check_cond (4 > 3 is true)
    • P1_add_5 (x becomes 4 + 5 = 9)
    • P2_assign_2 (x becomes 2)
    • P2_mul_2 (x becomes 2 * 2 = 4)
    • Final x = 4

  2. Scenario 2: P2 executes completely, then P1 executes completely.

    • P2_assign_2 (x becomes 2)
    • P2_mul_2 (x becomes 2 * 2 = 4)
    • P1_assign_4 (x becomes 4)
    • P1_check_cond (4 > 3 is true)
    • P1_add_5 (x becomes 4 + 5 = 9)
    • Final x = 9

  3. Scenario 3: P1 starts, P2 interrupts before P1’s conditional.

    • P1_assign_4 (x becomes 4)
    • P2_assign_2 (x becomes 2)
    • P2_mul_2 (x becomes 2 * 2 = 4)
    • P1_check_cond (x is 4, so 4 > 3 is true)
    • P1_add_5 (x becomes 4 + 5 = 9)
    • Final x = 9 (Same as Scenario 2 in this case because P2’s final x is 4, which P1 then overwrites its initial assignment with and proceeds based on that.)

  4. Scenario 4: P1 starts, P2 interrupts P1 after P1’s assignment x=4 but before if (x>3) and P2 completes.

    • P1_assign_4 (x becomes 4)
    • P2_assign_2 (x becomes 2)
    • P2_mul_2 (x becomes 2 * 2 = 4)
    • P1_check_cond (current x is 4, 4 > 3 is true)
    • P1_add_5 (x becomes 4 + 5 = 9)
    • Final x = 9

  5. Scenario 5: P2 starts, P1 interrupts P2 after P2’s assignment x=2 but before x=x*2, and P1 completes.

    • P2_assign_2 (x becomes 2)
    • P1_assign_4 (x becomes 4)
    • P1_check_cond (4 > 3 is true)
    • P1_add_5 (x becomes 4 + 5 = 9)
    • P2_mul_2 (x, which is 9, becomes 9 * 2 = 18)
    • Final x = 18

  6. Scenario 6: P1 assigns x=4, P1 checks x>3 (true). P2 interrupts before x=x+5 and completes.

    • P1_assign_4 (x becomes 4)
    • P1_check_cond (4 > 3 is true, so P1 will execute x=x+5)
    • P2_assign_2 (x becomes 2)
    • P2_mul_2 (x becomes 2 * 2 = 4)
    • P1_add_5 (P1 now uses the current value of x, which is 4, so x becomes 4 + 5 = 9)
    • Final x = 9

  7. Scenario 7: P2 assigns x=2. P1 executes completely. Then P2 does x=x*2.

    • P2_assign_2 (x becomes 2)
    • P1_assign_4 (x becomes 4)
    • P1_check_cond (4 > 3 is true)
    • P1_add_5 (x becomes 4 + 5 = 9)
    • P2_mul_2 (P2 now uses the current value of x, which is 9, so x becomes 9 * 2 = 18)
    • Final x = 18

  8. Scenario 8: P1 assigns x=4. P2 executes x=2. P1 checks condition (x is 2, 2>3 is false). P1 does x=x*3. Then P2 does x=x*2.

    • P1_assign_4 (x becomes 4)
    • P2_assign_2 (x becomes 2)
    • P1_check_cond (current x is 2; 2 > 3 is false)
    • P1_mul_3 (x becomes 2 * 3 = 6)
    • P2_mul_2 (x becomes 6 * 2 = 12)
    • Final x = 12

  9. Scenario 9: P2 assigns x=2. P1 assigns x=4. P2 does x=x*2 (x becomes 4*2=8). P1 checks condition (x is 8, 8>3 is true). P1 does x=x+5.

    • P2_assign_2 (x becomes 2)
    • P1_assign_4 (x becomes 4)
    • P2_mul_2 (current x is 4, so x becomes 4 * 2 = 8)
    • P1_check_cond (current x is 8, 8 > 3 is true)
    • P1_add_5 (x becomes 8 + 5 = 13)
    • Final x = 13

Let’s re-evaluate systematically by considering the point where P1 reads x for its condition and P1 writes its final result, relative to P2’s operations.

P1’s operations:

  1. x = 4 (Write_P1_init)
  2. Read x for if (x > 3) (Read_P1_cond)
  3. If true: x = x + 5 (Write_P1_true)
  4. If false: x = x * 3 (Write_P1_false)

P2’s operations:

  1. x = 2 (Write_P2_init)
  2. x = x * 2 (Write_P2_final)

Consider the value of x when P1 executes Read_P1_cond:

  • Case A: P1’s Write_P1_init is the last write to x before Read_P1_cond.

    • x is 4. Condition (4 > 3) is true. P1 will execute x = x + 5.
    • Subcase A1: P1 executes Write_P1_true (to 9). Then P2 runs.
      • P2_Write_P2_init (x becomes 2)
      • P2_Write_P2_final (x becomes 2 * 2 = 4). Final x = 4.
      • Sequence: P1_init(x=4) -> P1_read(x=4, true) -> P1_true(x=9) -> P2_init(x=2) -> P2_final(x=4)
    • Subcase A2: P2 runs. Then P1 executes Write_P1_true.
      • P2_Write_P2_init (x becomes 2)
      • P2_Write_P2_final (x becomes 2 * 2 = 4)
      • P1_Write_P1_true (using its original read of x=4 for x+5, so x becomes 4+5=9, or if it re-reads, x is 4, x becomes 4+5=9. Let’s assume it uses value from when condition was evaluated for the calculation, or current value if not stored locally. The code x=x+5 implies current x. So if P2 ran completely in between P1’s check and P1’s update, x would be 4. So P1 sets x = 4+5=9). Final x = 9.
      • Sequence: P1_init(x=4) -> P1_read(x=4, true) -> P2_init(x=2) -> P2_final(x=4) -> P1_true(x=4+5=9)
    • Subcase A3: P2’s Write_P2_init happens, then Write_P2_final, then P1’s Write_P1_true. (This means P1 did P1_init, P1_read, then P2 ran, then P1_true).
      • P1_init (x=4) -> P1_read (x=4, cond is true).
      • P2_init (x=2) -> P2_final (x=4).
      • P1_true (x=x+5, current x is 4, so x=4+5=9). Final x = 9.
      • Sequence: P1_init(x=4) -> P1_read(x=4, true) -> P2_init(x=2) -> P2_final(x=4) -> P1_true(x=4+5=9)
    • Subcase A4: P1_init, P1_read. Then P2_init. Then P1_true. Then P2_final.
      • P1_init (x=4) -> P1_read (x=4, cond is true).
      • P2_init (x=2).
      • P1_true (x=x+5, current x is 2, so x=2+5=7).
      • P2_final (x=x2, current x is 7, so x=72=14). Final x = 14.
      • Sequence: P1_init(x=4) -> P1_read(x=4, true) -> P2_init(x=2) -> P1_true(x=2+5=7) -> P2_final(x=72=14)*
    • Subcase A5: P1_init, P1_read. Then P1_true. Then P2_init. Then P2_final. (Covered by A1, x=4)
    • Subcase A6: P2_init. Then P1_init, P1_read. Then P2_final. Then P1_true.
      • P2_init (x=2).
      • P1_init (x=4) -> P1_read (x=4, cond is true).
      • P2_final (x=x2, current x is 4, so x=42=8).
      • P1_true (x=x+5, current x is 8, so x=8+5=13). Final x = 13.
      • Sequence: P2_init(x=2) -> P1_init(x=4) -> P1_read(x=4, true) -> P2_final(x=42=8) -> P1_true(x=8+5=13)*

  • Case B: P2’s Write_P2_init is the last write to x before Read_P1_cond.

    • x is 2. Condition (2 > 3) is false. P1 will execute x = x * 3.
    • Subcase B1: P1 executes Write_P1_false. Then P2’s Write_P2_final executes.
      • P1_Write_P1_false (x becomes 2 * 3 = 6).
      • P2_Write_P2_final (x becomes 6 * 2 = 12). Final x = 12.
      • Sequence: P1_init(x=4) (or P2_init first, doesn’t matter for P1_read if P2_init is the most recent) -> P2_init(x=2) -> P1_read(x=2, false) -> P1_false(x=23=6) -> P2_final(x=62=12)
    • Subcase B2: P2’s Write_P2_final executes. Then P1 executes Write_P1_false.
      • P2_Write_P2_final (x becomes 2 * 2 = 4).
      • P1_Write_P1_false (current x is 4, so x becomes 4 * 3 = 12). Final x = 12.
      • Sequence: P1_init(x=4) -> P2_init(x=2) -> P1_read(x=2, false) -> P2_final(x=22=4) -> P1_false(x=43=12)

  • Case C: P2’s Write_P2_final is the last write to x before Read_P1_cond.

    • This implies P2 ran completely. x is 4. Condition (4 > 3) is true. P1 will execute x = x + 5.
    • P1_Write_P1_true (x becomes 4 + 5 = 9). Final x = 9.
    • Sequence: P2_init(x=2) -> P2_final(x=4) -> P1_init(x=4, no effect) -> P1_read(x=4, true) -> P1_true(x=4+5=9)

Let’s list the distinct values found so far: 4, 9, 18 (from earlier manual trace), 12, 13, 14.

Let’s ensure all operations are atomic for simplicity (each line is one atomic step).

Possible values and one sequence for each:

  1. x = 4
    • Sequence: P1_assign_4 (x=4) -> P1_check_cond (true) -> P1_add_5 (x=9) -> P2_assign_2 (x=2) -> P2_mul_2 (x=4).
  2. x = 9
    • Sequence: P2_assign_2 (x=2) -> P2_mul_2 (x=4) -> P1_assign_4 (x=4) -> P1_check_cond (true) -> P1_add_5 (x=9).
  3. x = 12
    • Sequence: P1_assign_4 (x=4) -> P2_assign_2 (x=2) -> P1_check_cond (x=2, false) -> P1_mul_3 (x=23=6) -> P2_mul_2 (x=62=12).
  4. x = 13
    • Sequence: P2_assign_2 (x=2) -> P1_assign_4 (x=4) -> P2_mul_2 (x=4*2=8) -> P1_check_cond (x=8, true) -> P1_add_5 (x=8+5=13).
  5. x = 14
    • Sequence: P1_assign_4 (x=4) -> P1_check_cond (x=4, true) -> P2_assign_2 (x=2) -> P1_add_5 (x=2+5=7) -> P2_mul_2 (x=7*2=14).
  6. x = 18 (This was: P2_assign_2 (x=2) -> P1_assign_4 (x=4) -> P1_check_cond (true) -> P1_add_5 (x=9) -> P2_mul_2 (x=9*2=18) )
    • Sequence: P2_assign_2 (x=2) -> P1_assign_4 (x=4) -> P1_check_cond (x=4, true) -> P1_add_5 (x=4+5=9) -> P2_mul_2 (x=9*2=18).

The distinct values for x are: 4, 9, 12, 13, 14, 18.
There are 6 different possible values.

Question 2: Theory Questions (25 marks)

(a) In the context of Inter-Process Communication, explain how the sleep and wakeup primitives work. Give one advantage of semaphores over these primitives.

Sleep and Wakeup Primitives:
sleep and wakeup are system calls used for process synchronization, often in the context of producer-consumer problems or other situations where one process needs to wait for an event triggered by another.

  • sleep(): When a process calls sleep(), it voluntarily blocks itself (i.e., suspends its execution) until another process wakes it up. The sleep() call typically takes an address (or an event identifier) as a parameter, which specifies the event for which the process is waiting. The process is moved from the running state to a blocked/waiting state.

  • wakeup(event): When a process calls wakeup(event), it signals that the event (identified by the event parameter) has occurred. The operating system then searches its list of blocked processes for any process that is sleeping on this specific event. If one or more such processes are found, one or all of them (depending on the implementation) are moved from the blocked state to the ready state, making them eligible to be scheduled by the CPU.

A Problem with Sleep/Wakeup: The Lost Wakeup Signal
A critical issue with basic sleep/wakeup is the “lost wakeup signal.” This can occur if:

  1. A process (consumer) checks a condition (e.g., buffer is empty) and decides to go to sleep.
  2. Before the consumer actually calls sleep(), it is preempted.
  3. Another process (producer) produces an item, sees the consumer is (about to be) waiting, and calls wakeup() for the consumer.
  4. This wakeup() signal is lost because the consumer is not yet asleep (it was preempted just before calling sleep()).
  5. The consumer resumes, calls sleep(), and may sleep forever if the producer doesn’t produce again.

Advantage of Semaphores over Sleep/Wakeup:
One significant advantage of semaphores over basic sleep/wakeup primitives is that semaphores remember wakeup signals.

  • A semaphore has an internal counter. When a signal (or V or up) operation is performed on a semaphore, its counter is incremented. If there are processes blocked on that semaphore (due to a previous wait or P or down operation finding the counter at 0), one of them is awakened.
  • Crucially, if signal is called and no process is currently waiting, the semaphore “remembers” this by keeping its counter incremented. A subsequent wait operation by another process will find the counter positive, decrement it, and proceed without blocking.
  • In contrast, with raw sleep/wakeup, if wakeup is called before sleep, the wakeup signal is lost. Semaphores solve this lost wakeup problem by storing the signals (as a count). This makes them a more robust mechanism for synchronization.

(b) In the context of deadlock avoidance algorithms, consider the following states, assuming there is only one type of resource: … For each of the states (X and Y), indicate whether it is safe or unsafe, and justify your classification.

Total resources in the system = 10.
To determine if a state is safe, we use an algorithm similar to the Banker’s Algorithm. We need to find if there’s a sequence of process completions such that all processes can finish. A process can finish if its remaining Need (Max - Has) is less than or equal to the Available resources. Once a process finishes, it releases its Has resources, increasing the Available resources.

State X:
Total Resources = 10

Process Has Max Need (Max - Has)
A 1 8 7
B 3 9 6
C 1 2 1
D 1 5 4
Total Has 6

Available Resources = Total Resources - Total Has = 10 - 6 = 4.

Let’s try to find a safe sequence:

  1. Initial Available = 4.
    • Process A needs 7 (7 > 4, cannot run).
    • Process B needs 6 (6 > 4, cannot run).
    • Process C needs 1 (1 <= 4, can run). Assume C runs and finishes.
      • New Available = Available + C.Has = 4 + 1 = 5.
      • Processes remaining: A, B, D. Sequence: <C>
  2. Available = 5.
    • Process A needs 7 (7 > 5, cannot run).
    • Process B needs 6 (6 > 5, cannot run).
    • Process D needs 4 (4 <= 5, can run). Assume D runs and finishes.
      • New Available = Available + D.Has = 5 + 1 = 6.
      • Processes remaining: A, B. Sequence: <C, D>
  3. Available = 6.
    • Process A needs 7 (7 > 6, cannot run).
    • Process B needs 6 (6 <= 6, can run). Assume B runs and finishes.
      • New Available = Available + B.Has = 6 + 3 = 9.
      • Processes remaining: A. Sequence: <C, D, B>
  4. Available = 9.
    • Process A needs 7 (7 <= 9, can run). Assume A runs and finishes.
      • New Available = Available + A.Has = 9 + 1 = 10.
      • Processes remaining: None. Sequence: <C, D, B, A>

Since we found a safe sequence (<C, D, B, A>), State X is SAFE.

State Y:
Total Resources = 10

Process Has Max Need (Max - Has)
A 2 9 7
B 2 10 8
C 3 5 2
D 1 6 5
Total Has 8

Available Resources = Total Resources - Total Has = 10 - 8 = 2.

Let’s try to find a safe sequence:

  1. Initial Available = 2.
    • Process A needs 7 (7 > 2, cannot run).
    • Process B needs 8 (8 > 2, cannot run).
    • Process C needs 2 (2 <= 2, can run). Assume C runs and finishes.
      • New Available = Available + C.Has = 2 + 3 = 5.
      • Processes remaining: A, B, D. Sequence: <C>
  2. Available = 5.
    • Process A needs 7 (7 > 5, cannot run).
    • Process B needs 8 (8 > 5, cannot run).
    • Process D needs 5 (5 <= 5, can run). Assume D runs and finishes.
      • New Available = Available + D.Has = 5 + 1 = 6.
      • Processes remaining: A, B. Sequence: <C, D>
  3. Available = 6.
    • Process A needs 7 (7 > 6, cannot run).
    • Process B needs 8 (8 > 6, cannot run).

At this point, neither Process A nor Process B can acquire the resources they need to complete (A needs 7, B needs 8, but only 6 are available). There is no process that can run to completion and release its resources.
Therefore, we cannot find a safe sequence.

State Y is UNSAFE.

(c) Ext4 i-nodes are 256 bytes in size. Suppose there are 2,000 files on the disk, 200 of which are currently open by processes. What is the total main memory usage of i-nodes in this scenario? Justify your answer.

Justification and Calculation:

  • An i-node (index node) stores metadata about a file (e.g., permissions, ownership, timestamps, disk block locations).
  • When a file is open, its i-node is typically read from the disk into main memory to allow for faster access to its metadata and data blocks.
  • I-nodes for files that are not open generally reside on the disk and are not continuously kept in main memory just because they exist. They are loaded on demand when the file is accessed.

Given:

  • Size of one Ext4 i-node = 256 bytes.
  • Number of currently open files = 200.

The main memory usage for i-nodes will primarily be for the i-nodes of the files that are currently open. The i-nodes for the other 1,800 (2000 - 200) closed files remain on disk.

Total main memory usage for i-nodes = (Number of open files) * (Size of one i-node)
Total main memory usage = 200 files * 256 bytes/file
Total main memory usage = 51,200 bytes

This can also be expressed in kilobytes:
51,200 bytes / 1024 bytes/KB = 50 KB.

Therefore, the total main memory usage of i-nodes in this scenario is 51,200 bytes (or 50 KB). This is because only the i-nodes of open files are generally required to be in main memory for active use.

(d) This question is about the Working Set page replacement algorithm. The following table shows the time of last use, and the R and M bits for each memory page (the times are in ms).
Assuming a page fault occurs at virtual time 200ms, and the Working Set algorithm is used with $\tau=100ms$.

Page Time of Last Use (ms) R M
1 90 10
2 100 00
3 30 11
4 50 01

Current virtual time (VT) = 200ms.
Working set window ($\tau$) = 100ms.

i. For each page, indicate whether it is in the working set or not, and justify your conclusion.

A page is in the working set if it has been referenced within the last $\tau$ time units.
The age of a page is VT - Time of Last Use.
A page is in the working set if its R bit is 1 OR if its age $\le \tau$. (Some definitions strictly use age, others consider the R bit which indicates recent use even if Time of Last Use hasn’t been updated for this exact tick but was used within the interval where R bits are periodically cleared).
Let’s primarily use age: (VT - Time of Last Use) $\le \tau$.

  • Page 1:

    • Time of Last Use = 90ms.
    • Age = 200ms - 90ms = 110ms.
    • Is age (110ms) $\le \tau$ (100ms)? No (110 > 100).
    • R bit is 1. This indicates it was referenced recently, potentially within the current or previous $\tau$ interval before R bits were last cleared.
    • Strictly by “Time of Last Use” and age: Not in working set.
    • If “R=1” means “referenced in current window $\tau$”: In working set.
    • Standard interpretation: If R=1, it implies the page has been used since the R bit was last cleared. The Working Set algorithm typically scans pages. If R=1, the page is considered part of the working set for the current window, and its “Time of Last Use” is updated to the current virtual time, and R is cleared. If R=0, then its age is checked.
    • Let’s assume if R=1, it’s considered in the working set for this scan.
    • Page 1: IN WORKING SET. Justification: R bit is 1, indicating recent use. (Alternatively, if strictly by age: Age (110ms) > $\tau$ (100ms), so if R bit was ignored or just cleared, it would be out. But R=1 usually keeps it in for one more round). The problem phrasing “Time of Last Use” combined with R bits suggests R bits are important.

  • Page 2:

    • Time of Last Use = 100ms.
    • Age = 200ms - 100ms = 100ms.
    • Is age (100ms) $\le \tau$ (100ms)? Yes (100 <= 100).
    • R bit is 0.
    • Page 2: IN WORKING SET. Justification: Age (100ms) is equal to $\tau$ (100ms).

  • Page 3:

    • Time of Last Use = 30ms.
    • Age = 200ms - 30ms = 170ms.
    • Is age (170ms) $\le \tau$ (100ms)? No (170 > 100).
    • R bit is 1.
    • Page 3: IN WORKING SET. Justification: R bit is 1, indicating recent use.

  • Page 4:

    • Time of Last Use = 50ms.
    • Age = 200ms - 50ms = 150ms.
    • Is age (150ms) $\le \tau$ (100ms)? No (150 > 100).
    • R bit is 0.
    • Page 4: NOT IN WORKING SET. Justification: R bit is 0 AND Age (150ms) > $\tau$ (100ms).

Summary for i:

  • Page 1: In working set (due to R=1).
  • Page 2: In working set (due to age $\le \tau$).
  • Page 3: In working set (due to R=1).
  • Page 4: Not in working set (R=0 and age > $\tau$).

ii. Indicate which page is selected for eviction, and describe how the information in the table above is updated by the algorithm.

The Working Set algorithm evicts pages that are NOT in the working set.
From part (i), Page 4 is the only page not in the working set.
Page selected for eviction: Page 4.

How information is updated by the algorithm (typically during a pass, often triggered by a page fault or periodically):

  1. Scan Pages: The algorithm scans through all resident pages.
  2. Check R Bit:
    • If R=1 for a page:
      • The page is considered part of the working set for this window.
      • Its “Time of Last Use” is updated to the current virtual time (200ms in this case).
      • The R bit for this page is cleared (set to 0). This is to detect if it’s used in the next interval.
    • If R=0 for a page:
      • Calculate its age (Current VT - Time of Last Use).
      • If age > $\tau$: The page is not in the working set. It is a candidate for eviction. If a page fault has occurred and a page needs to be replaced, this page (or one of these pages if multiple) would be chosen.
      • If age $\le \tau$: The page is in the working set. It is kept in memory.
  3. Eviction: If a page fault occurred (as stated), and Page 4 was identified as not in the working set, it would be evicted to make space for the new page.
  4. M Bit: The M bit (Modified/Dirty bit) is used by the OS. If an evicted page has M=1, it means the page has been modified since it was loaded into memory, and its contents must be written back to the disk before the page frame can be reused. If M=0, the page frame can be reused immediately as its disk copy is still valid. Page 4 has M=1, so it would need to be written to disk.

Updated Table Information (after the scan at VT=200ms, and assuming Page 4 is evicted):

  • For pages that were R=1 (and thus in the working set):
    • Page 1: Time of Last Use becomes 200ms, R M becomes 00 (R is cleared, M was 0).
    • Page 3: Time of Last Use becomes 200ms, R M becomes 01 (R is cleared, M was 1).
  • For pages that were R=0 but in the working set (due to age):
    • Page 2: Time of Last Use remains 100ms (as R was 0, it wasn’t just referenced this exact tick, but its age kept it in. Some implementations might update its time if it’s kept, but typically only R=1 pages get their time updated aggressively). R M remains 00.
  • For the evicted page:
    • Page 4: This page is removed from memory. If it were to be brought back in later due to another fault, its R and M bits would be reset (likely to 00 initially).

So, the updated state for pages remaining in memory:

Page Time of Last Use (ms) R M Notes
1 200 00 R bit cleared, Time updated
2 100 00 Kept due to age, R was already 0
3 200 01 R bit cleared, Time updated, M was 1
(4) (Evicted) Was 50, 01. Would be written to disk.

The new page brought in by the page fault would have its own entry, its Time of Last Use set to 200ms, and R bit likely set to 1 (or 0 depending on policy), M bit to 0.

Question 3: Swap two characters (25 marks)

**(a) Write a function, void swapChar (char c1, char c2), that swaps the values of two character variables. 

1
2
3
4
5
6
7
#include <stdio.h> // For printf in main, not strictly needed for swapChar

void swapChar(char *c1, char *c2) {
    char temp = *c1; // Store the value pointed to by c1 in a temporary variable
    *c1 = *c2;       // Assign the value pointed to by c2 to the location pointed to by c1
    *c2 = temp;      // Assign the original value of c1 (stored in temp) to the location pointed to by c2
}

Explanation:

  • The function takes two pointers to characters, char *c1 and char *c2. These pointers hold the memory addresses of the characters to be swapped.
  • char temp = *c1;: We dereference c1 (i.e., get the character value at the address c1) and store it in a temporary character variable temp. This is necessary because if we directly assigned *c1 = *c2;, the original value of *c1 would be lost.
  • *c1 = *c2;: We dereference c2 and assign its value to the location pointed to by c1. Now, the character variable that c1 points to holds the original value of the character c2 pointed to.
  • *c2 = temp;: We assign the value stored in temp (which was the original value of the character c1 pointed to) to the location pointed to by c2.

(b) Write a function, char* initializeString(char *buf), that

  • takes a string constant as input,
  • dynamically allocates a string of the same length as the input,
  • copies the content of the input into the dynamic string,
  • returns a pointer to the dynamic string.
    Hint: the function should consist of two while loops, one for determining the length of the input and the other for copying the content of the input into the newly allocated string. Do not forget to null-terminate the string at the end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdlib.h> // For malloc and NULL

char* initializeString(char *buf) {
    if (buf == NULL) {
        return NULL; // Handle null input gracefully
    }

    // First while loop: Determine the length of the input string
    int length = 0;
    char *temp_ptr = buf; // Use a temporary pointer to iterate
    while (*temp_ptr != '\0') {
        length++;
        temp_ptr++;
    }

    // Dynamically allocate memory for the new string
    // Need length + 1 characters to store the string and the null terminator
    char *dynamic_string = (char *)malloc((length + 1) * sizeof(char));

    if (dynamic_string == NULL) {
        // Memory allocation failed
        return NULL; 
    }

    // Second while loop: Copy the content of the input string into the dynamic string
    int i = 0;
    while (i < length) {
        dynamic_string[i] = buf[i];
        i++;
    }
    
    // Null-terminate the newly allocated string
    dynamic_string[length] = '\0';  

    return dynamic_string;
}

Explanation:

  1. Input Validation: Checks if the input buffer buf is NULL.
  2. Determine Length:
    • A length variable is initialized to 0.
    • A temporary pointer temp_ptr is set to buf.
    • The first while loop iterates through the input string buf using temp_ptr until the null terminator (\0) is encountered. In each iteration, length is incremented.
  3. Dynamic Allocation:
    • malloc((length + 1) * sizeof(char)) allocates memory for length + 1 characters. We need length characters for the string content and one extra character for the null terminator. sizeof(char) is typically 1, but it’s good practice to include it.
    • The result of malloc is cast to (char *).
    • Error checking is performed: if malloc fails (returns NULL), the function returns NULL.
  4. Copy Content:
    • The second while loop iterates from i = 0 up to (but not including) length.
    • dynamic_string[i] = buf[i]; copies each character from the input string buf to the dynamic_string.
  5. Null Termination:
    • dynamic_string[length] = '\0'; adds the null terminator at the end of the copied content in the dynamic_string. This is crucial for it to be treated as a valid C string.
  6. Return Value: The function returns the pointer dynamic_string which points to the newly allocated and initialized string in the heap memory.

(c) Complete the following main function,
The program should print s=SC2850 and it should not leak memory when it runs.
You can assume the function definitions and the #include statements are appended on top of the file. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
#include <stdlib.h> // For malloc, free, NULL

// Assume swapChar and initializeString are defined above as per parts (a) and (b)

/*
void swapChar(char *c1, char *c2) {
    char temp = *c1;
    *c1 = *c2;
    *c2 = temp;
}

char* initializeString(char *buf) {
    if (buf == NULL) return NULL;
    int length = 0;
    char *temp_ptr = buf;
    while (*temp_ptr != '\0') {
        length++;
        temp_ptr++;
    }
    char *dynamic_string = (char *)malloc((length + 1) * sizeof(char));
    if (dynamic_string == NULL) return NULL;
    int i = 0;
    while (i < length) {
        dynamic_string[i] = buf[i];
        i++;
    }
    dynamic_string[length] = '\0';
    return dynamic_string;
}
*/

int main() {
    char *buf = "CS2850"; // String literal
    char *s = initializeString(buf); // Call initializeString with buf

    if (s == NULL) {
        fprintf(stderr, "Memory allocation failed for s\n");
        return 1; // Indicate an error
    }

    // To print "s=SC2850", we need to swap 'C' (s[0]) and 'S' (s[1])
    // The string "CS2850" has 'C' at index 0 and 'S' at index 1.
    // The initializeString function copies "CS2850" into s.
    // So, s[0] is 'C' and s[1] is 'S'.
    // We need to swap them.

    if (s[0] != '\0' && s[1] != '\0') { // Ensure the string has at least two characters
        swapChar(&s[0], &s[1]); // Pass addresses of the first two characters of s
    } else {
        // Handle case where string is too short, though "CS2850" is not.
        // This might just involve printing the original if swapping isn't possible.
        // For this specific problem, we know the string.
    }
    
    printf("s=%s\n", s); // Print the modified string s

    // Free the dynamically allocated memory for s to prevent memory leaks
    free(s); 
    s = NULL; // Good practice to set pointer to NULL after freeing

    return 0; // Indicate successful execution
}

Explanation of main completion:

  1. char *s = initializeString(buf);:
    • The initializeString function is called with buf (which is “CS2850”).
    • s will now point to a dynamically allocated copy of “CS2850”.
  2. Error Check:
    • Added a check if (s == NULL) to handle potential memory allocation failure from initializeString.
  3. swapChar(&s[0], &s[1]);:
    • The desired output is “s=SC2850”. The original string in s is “CS2850”.
    • To achieve “SC2850”, we need to swap the first character s[0] (‘C’) with the second character s[1] (‘S’).
    • swapChar expects pointers to characters. So, we pass the addresses of s[0] and s[1] using the address-of operator &.
    • A check if (s[0] != '\0' && s[1] != '\0') is added for robustness, ensuring the string is long enough to perform the swap, though for the given buf it is.
  4. printf("s=%s\n", s);:
    • This prints the string pointed to by s. After the swap, s will be “SC2850”.
    • The output format matches “s=…” as required.
  5. free(s);:
    • Since s points to memory allocated by malloc (inside initializeString), this memory must be deallocated using free(s) when it’s no longer needed. This prevents memory leaks, as required.
  6. s = NULL;:
    • Setting s to NULL after freeing is a good defensive programming practice to prevent dangling pointer issues if s were accidentally used later (though not strictly required for this problem’s constraints).

Question 4: A linked list of integers (25 marks)

The provided code snippet: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>

struct node {
    int label;
    float value;
    struct node *next;
};

int main() {
    struct node *head = NULL; // Corrected: should be pointer
    int i = 0;
    char c = '\0'; // Corrected: initialize char

    while ((c = getchar()) != '\n' && c != EOF) {
        if (c <= '9' && c >= '0') {
            struct node *new_node = (struct node *)malloc(sizeof(struct node)); // Renamed 'new' to 'new_node'
            if (new_node == NULL) { /* handle allocation error */ return 1; }
            new_node->label = i;
            new_node->value = c - '0';
            i++;
            new_node->next = head;
            head = new_node;
        }
    }

    // Store the sum of values here
    float sum_of_values = 0; // To correctly answer part (e) as per the original code's likely intent for i
    int initial_i_val_before_loop = i; // Store i's value before it's modified by head->value

    while (head) {
        printf("label=%d, ", head->label);
        printf("value=%f\n", head->value);
        struct node *temp = head;
        head = head->next; // Corrected: this was 'head->next;' then 'head' on separate line in snippet
        
        // Original code's intent for 'i = i + temp->value;'
        // If 'i' in printf("i=%d\n",i) is supposed to be the sum of *integer parts* of values:
        // sum_of_values += (int)temp->value; // This matches the printf format specifier %d for i
        // If 'i' in printf is the *count* plus sum of values:
        sum_of_values += temp->value; // Storing sum as float

        free(temp);
    }

    // The question implies 'i' is printed. If 'i' from the first loop is intended to be summed with values:
    // i = initial_i_val_before_loop + (int)sum_of_values; // This is a bit convoluted based on original code
    // Let's assume the last printf("i=%d\n",i) prints the sum of the digits entered.
    // The original code has i = i + temp->value; which is problematic since i is int and temp->value is float.
    // Let's assume the goal was to sum the integer values represented by characters.
    // If the original i (count of nodes) is reused and accumulated:
    // The original 'i = i + temp->value;' would sum floats into an int, truncating.
    // Let's stick to sum_of_values for clarity and then decide what 'i' means in the final printf.

    // For part (e), if the input is "1423\n"
    // Nodes created (LIFO):
    // label=3, value=3.0
    // label=2, value=2.0
    // label=1, value=4.0
    // label=0, value=1.0
    // i (count) becomes 4.
    // Loop sum: head->value (3) + head->value (2) + head->value (4) + head->value (1) = 10.0
    // The final printf has "i=%d\n", i. The variable 'i' is modified in the second loop by 'i = i + temp->value;'
    // This implies 'i' is being used to accumulate.
    // Initial i (after first loop, for input "1423") = 4.
    // 1st iteration (temp->value=3): i = 4 + 3 = 7
    // 2nd iteration (temp->value=2): i = 7 + 2 = 9
    // 3rd iteration (temp->value=4): i = 9 + 4 = 13
    // 4th iteration (temp->value=1): i = 13 + 1 = 14
    // So, the final printf would print i=14.

    printf("i=%d\n", i); // Using the 'i' as modified by the loop in the original snippet
    
    return 0;
}

Corrections made to the provided snippet for analysis:

  • struct node head = NULL; changed to struct node *head = NULL; (head should be a pointer).
  • char c = '0'; (or '\0') for initialization. The snippet had char c=^{,10} which is unusual. Assume char c; or char c = '\0';
  • struct node *new = malloc... changed to struct node *new_node = ... because new is a keyword in C++.
  • Added error check for malloc.
  • Corrected head->next; head to head = head->next; for list traversal.
  • The line i=i+temp->value; in the second loop is problematic as i is an int and temp->value is a float. This will cause truncation. The behavior for part (e) will follow this truncation.

(a) What is the size of the structure? Why is it always better to use sizeof instead of computing the sum of the member sizes?

Size of the structure struct node:
The structure has three members:

  • int label; (typically 4 bytes on most systems)
  • float value; (typically 4 bytes for single-precision float)
  • struct node *next; (a pointer, size depends on architecture: 4 bytes on 32-bit, 8 bytes on 64-bit systems)

So, the sum of member sizes could be:

  • On a 32-bit system: 4 (int) + 4 (float) + 4 (pointer) = 12 bytes.
  • On a 64-bit system: 4 (int) + 4 (float) + 8 (pointer) = 16 bytes.

However, the actual size determined by sizeof(struct node) might be larger due to padding. Compilers may add padding bytes between members or after the last member to ensure that members are aligned to certain memory boundaries (e.g., a 4-byte integer might need to start at an address divisible by 4). This alignment can improve access speed.

Why it is always better to use sizeof:

  1. Portability: The sizes of basic data types (like int, pointers) and the rules for padding/alignment can vary across different compilers, operating systems, and hardware architectures. Manually summing sizes makes the code non-portable. sizeof queries the compiler, which knows the exact size on the current target system, ensuring the code works correctly everywhere.
  2. Padding and Alignment: sizeof automatically accounts for any padding bytes inserted by the compiler for alignment purposes. Manual calculation would likely miss this, leading to incorrect size determination, which can cause buffer overflows or other memory corruption issues when allocating memory or performing pointer arithmetic.
  3. Maintainability: If the structure definition changes (e.g., a member is added, removed, or its type changes), code using sizeof will automatically adapt. Code with manually calculated sizes would need to be found and updated, which is error-prone.
  4. Readability and Correctness: Using sizeof clearly expresses the intent of getting the actual size of the type or variable and is less prone to calculation errors than manual summing.

(b) What is the difference between \0 and 0? Why do you need to subtract 0 in new->value = c - '0'?

Difference between \0 and '0':

  • \0 (Null Character):

    • This is a character literal representing the null character (also called null terminator).
    • Its ASCII (or UTF-8) value is 0.
    • It is primarily used to mark the end of strings in C. Functions that operate on strings (like strcpy, strlen, printf %s) rely on this null character to know where the string data ends.
    • In terms of integer value, \0 is equivalent to the integer 0.

  • '0' (Character Zero):

    • This is a character literal representing the digit character ‘0’.
    • Its ASCII value is typically 48 (this can vary on non-ASCII systems, but is standard on most).
    • It is a printable character.

Why subtract '0' in new->value = c - '0':
The line if (c <= '9' && c >= '0') checks if the character c (read by getchar()) is a digit character (from ‘0’ through ‘9’).

  • Character variables in C store ASCII values (or values from the system’s character set). For example, if c is ‘1’, its ASCII value is 49. If c is ‘7’, its ASCII value is 55.
  • The goal is to convert the digit character into its corresponding integer value. For instance, if the user types ‘1’, we want to store the integer 1.0 in new->value.
  • In ASCII (and compatible character sets), the digit characters ‘0’ through ‘9’ are represented by consecutive integer codes.
    • ‘0’ has ASCII value X
    • ‘1’ has ASCII value X + 1
    • ‘2’ has ASCII value X + 2
    • …
    • ‘9’ has ASCII value X + 9
      (For ASCII, X=48).
  • So, c - '0' performs arithmetic on the character codes.
    • If c is ‘1’ (ASCII 49) and '0' is ASCII 48, then '1' - '0' is 49 - 48 = 1.
    • If c is ‘7’ (ASCII 55) and '0' is ASCII 48, then '7' - '0' is 55 - 48 = 7.
  • This subtraction effectively converts the ASCII representation of a digit character into its numerical integer equivalent. This integer is then assigned to the float variable new->value (which will be, e.g., 1.0, 7.0, etc.).

(c) Why are the nodes printed from the last to the first? Why does the second while loop end after the program prints the node with the label 0?

Why nodes are printed from last to first:
The nodes are printed from the last input digit to the first input digit because of how the linked list is constructed:

  1. new_node->next = head;
  2. head = new_node;

This sequence of operations adds each new node to the front of the list.

  • Initially, head is NULL.
  • When the first digit is read (e.g., ‘1’ in “1423”), a node is created for it. new_node->next becomes NULL, and head points to this new node. List: Node(1) -> NULL.
  • When the second digit is read (e.g., ‘4’), a new node is created. new_node->next is set to the current head (which points to Node(1)). Then, head is updated to point to this newest node. List: Node(4) -> Node(1) -> NULL.
  • This continues for all input digits. If the input is “1423”, the list becomes: Node(3) -> Node(2) -> Node(4) -> Node(1) -> NULL. (Node(3) was the last char entered).

The printing loop (while (head) { ... head = head->next; }) traverses the list starting from the head and following the next pointers. Since the head always points to the most recently added node (which corresponds to the last character entered by the user before newline/EOF), the list is printed in reverse order of input.

Why the second while loop ends after printing the node with label 0:
The label field is assigned sequentially starting from 0 and incrementing (new_node->label = i; i++;).

  • The first node created (corresponding to the first digit entered by the user) gets label = 0.
  • The second node created gets label = 1, and so on.

Since new nodes are added to the front of the list, the node with label = 0 will be the last node in the linked list (the one whose next pointer is NULL, assuming at least one digit was entered).

The printing loop is while (head). This loop continues as long as head is not NULL.
Inside the loop:

  • printf("label=%d, ...", head->label); prints the current node’s data.
  • struct node *temp = head;
  • head = head->next; advances head to the next node in the list.
  • free(temp); frees the node that was just printed.

When head points to the node with label = 0 (which is the original first node entered, now at the end of the list being traversed):

  1. Its data is printed.
  2. temp is set to this node.
  3. head is updated to head->next. Since this is the last node, its next field is NULL. So, head becomes NULL.
  4. The node (pointed to by temp) is freed.
    After this iteration, the condition while (head) (which is now while (NULL)) becomes false, and the loop terminates. Thus, the loop ends after processing and printing the node that had label = 0.

(d) How many dynamic allocations does the program perform? How many times does it call free?

  • Dynamic Allocations (malloc):
    A dynamic allocation (malloc(sizeof(struct node))) is performed once for each valid digit character entered by the user before a newline or EOF. The if (c <= '9' && c >= '0') condition ensures this.
    So, if the user enters N digit characters, malloc is called N times.

  • free Calls:
    The second while (head) loop iterates through each node in the list and calls free(temp) for each node. This loop continues until head becomes NULL, meaning all nodes that were added to the list are freed.
    So, if N nodes were allocated and added to the list, free will be called N times.

Therefore, the program performs N dynamic allocations and N calls to free, where N is the number of digit characters entered by the user. This means that, assuming malloc always succeeds, the program should not leak memory from the linked list nodes themselves.

(e) Can you predict the output of the last call of printf if you assume the user enters 1423\n on the terminal after the program has started? Is the argument of printf correct?

User input: 1423\n

Execution Trace:

  1. First while loop (reading input and building list):

    • i starts at 0. head is NULL.
    • c = '1':
      • new_node allocated. new_node->label = 0, new_node->value = '1' - '0' = 1.0.
      • i becomes 1. new_node->next = NULL. head points to this node.
      • List: Node(label=0, value=1.0) -> NULL
    • c = '4':
      • new_node allocated. new_node->label = 1, new_node->value = '4' - '0' = 4.0.
      • i becomes 2. new_node->next points to Node(label=0). head points to this new node.
      • List: Node(label=1, value=4.0) -> Node(label=0, value=1.0) -> NULL
    • c = '2':
      • new_node allocated. new_node->label = 2, new_node->value = '2' - '0' = 2.0.
      • i becomes 3. new_node->next points to Node(label=1). head points to this new node.
      • List: Node(label=2, value=2.0) -> Node(label=1, value=4.0) -> Node(label=0, value=1.0) -> NULL
    • c = '3':
      • new_node allocated. new_node->label = 3, new_node->value = '3' - '0' = 3.0.
      • i becomes 4. new_node->next points to Node(label=2). head points to this new node.
      • List: Node(label=3, value=3.0) -> Node(label=2, value=2.0) -> Node(label=1, value=4.0) -> Node(label=0, value=1.0) -> NULL
    • c = '\n': First loop terminates. At this point, i = 4.

  2. Second while loop (printing, summing into i, and freeing):

    • Current head points to Node(label=3, value=3.0). i is currently 4.
    • Iteration 1:
      • Prints “label=3, value=3.000000”
      • temp points to Node(label=3). head moves to Node(label=2).
      • i = i + temp->value; => i = 4 + 3.0; (float 3.0 is converted to int 3 for addition, or result truncated) => i = 4 + 3 = 7.
      • free(temp).
    • Iteration 2:
      • head points to Node(label=2, value=2.0). i is 7.
      • Prints “label=2, value=2.000000”
      • temp points to Node(label=2). head moves to Node(label=1).
      • i = i + temp->value; => i = 7 + 2.0; => i = 7 + 2 = 9.
      • free(temp).
    • Iteration 3:
      • head points to Node(label=1, value=4.0). i is 9.
      • Prints “label=1, value=4.000000”
      • temp points to Node(label=1). head moves to Node(label=0).
      • i = i + temp->value; => i = 9 + 4.0; => i = 9 + 4 = 13.
      • free(temp).
    • Iteration 4:
      • head points to Node(label=0, value=1.0). i is 13.
      • Prints “label=0, value=1.000000”
      • temp points to Node(label=0). head moves to NULL.
      • i = i + temp->value; => i = 13 + 1.0; => i = 13 + 1 = 14.
      • free(temp).
    • head is now NULL. Second loop terminates. i is 14.

  3. Last printf:

    • printf("i=%d\n", i);
    • This will print the final value of i, which is 14.

Predicted output of the last call of printf:
i=14

Is the argument of printf correct?
The last printf is printf("i=%d\n", i);.

  • The format specifier is %d, which expects an argument of type int.
  • The variable i is declared as int i;.
  • Throughout the code, i is used as an integer. The operation i = i + temp->value; involves adding a float (temp->value) to an int (i). In C, when a float is added to an int and the result is assigned back to an int, the float value is typically truncated to its integer part before the addition (or the sum is truncated if the addition happens as float then assigned to int). For example, i = (int)( (float)i + temp->value ). Given temp->value are whole numbers like 1.0, 2.0, etc., (int)temp->value will be 1, 2, etc. So, the calculation i = i + (int)temp->value is effectively what happens.

Yes, the argument i is of type int, which matches the %d format specifier. So, in terms of type matching, the argument is correct.

The meaning of i at the end is the sum of its initial value after the first loop (which was the count of digits, 4) and the integer parts of the digits entered (1+4+2+3 = 10). So, 4 + 10 = 14. If the intent was to print the simple sum of the digits entered (1+4+2+3=10), then the logic for updating i is a bit convoluted as it incorporates its previous value (the count). If the intent was just to print the count, it should have been printed before the second loop or stored in another variable. However, given the code structure, i=14 is the correct output.

This concludes the detailed answers to the exam paper.

Revision
#CS2850
CS2850 2024 Past Paper Solution
https://blog.pandayuyu.zone/2025/05/09/CS2850-2024-Past-Paper-Solution/
Author
Panda
Posted on
May 9, 2025
Licensed under