CS2850 2022 Past Paper Solution

Here are the answers to the questions in the provided CS2850/CS2850R Operating Systems exam paper from 2022, with explanations.

Question 1

(a) Kernel vs. User CPU Execution Modes

User Mode: This is the default mode for executing user applications. In user mode, processes have limited access to system resources and instructions. They cannot directly access hardware or critical memory areas. If a user program needs to perform a privileged operation (like I/O), it must make a system call to the operating system kernel.
Kernel Mode (also known as Supervisor Mode or Privileged Mode): This mode is reserved for the operating system kernel. In kernel mode, the CPU has unrestricted access to all system resources, including hardware, memory, and privileged instructions. The kernel executes in this mode to manage the system, handle interrupts, perform system calls, and manage processes and memory.
Example of an operation only in kernel mode: Directly accessing the hard disk controller to perform a read or write operation. User programs cannot do this directly; they must request the operating system (running in kernel mode) to perform the operation on their behalf via a system call.

(b) Short-Job First (SJF) Scheduling Algorithm
Shortest Job First (SJF) is a non-preemptive batch scheduling algorithm where the process with the smallest estimated running time is selected to run next. When the currently executing job finishes, the scheduler examines the ready queue and picks the job with the shortest remaining execution time.

Advantage over First-Come First-Served (FCFS): One significant advantage of SJF over FCFS is that it generally provides a lower average turnaround time. By prioritizing shorter jobs, SJF allows them to complete quickly, reducing their waiting time and thus the average waiting and turnaround times for the system compared to FCFS, which simply processes jobs in the order they arrive, regardless of their length.

(c) Not-Frequently Used (NFU) Page Replacement Algorithm
The Not-Frequently Used (NFU) page replacement algorithm approximates the Least Frequently Used (LFU) algorithm. It associates a counter with each page. At regular intervals (e.g., on each clock interrupt), the R (Referenced) bit for all pages is checked. If the R bit is 1, it means the page has been referenced during the last interval, and the page’s counter is incremented by the value of the R bit (which is 1). The R bit is then reset to 0.

The provided page table shows the R (Referenced) and M (Modified) bits:

Page 1: RM = 11
Page 2: RM = 10
Page 3: RM = 01
Page 4: RM = 11

In NFU, the algorithm would evict the page with the smallest counter value. Assuming the counters were previously based on past references, the current R bits are used to update these counters.
Let’s consider the current state based on the R bits:

Page 1 R bit = 1: Counter would be incremented.
Page 2 R bit = 1: Counter would be incremented.
Page 3 R bit = 0: Counter would not be incremented based on this interval’s R bit.
Page 4 R bit = 1: Counter would be incremented.

Assuming the counters were previously equal or zero, after this interval, Page 3’s counter would be the lowest because its R bit was 0. If the counters reflect accumulated references, the page with the lowest historical count, adjusted by the current R bit, is chosen.

Page to be evicted: Page 3.
Justification: The NFU algorithm evicts the page that has been referenced least frequently. In this snapshot, Page 3 has an R bit of 0, meaning it was not referenced in the most recent interval. Assuming the counters accurately reflect historical usage, and given that Page 3’s counter would not be incremented based on this interval’s activity, it is the most likely candidate for being the least frequently used page overall and thus selected for eviction.

(d) Concurrent Processes and Shared Variable
Consider processes P1 and P2 sharing variable x, initially not specified but the outcomes suggest it starts before being set by either process.

P1: x = 7; if (x < 5) x = x + 3;
P2: x = 3; if (x > 4) x = x - 9;

We need to find the possible values of x when the program terminates and provide an execution sequence for each case.

Let’s analyze the possible interleavings:

Case 1: P1 executes fully, then P2 executes fully.
- P1:
  - x = 7; (x is now 7)
  - if (x < 5) is false (x is 7)
- P2:
  - x = 3; (x is now 3)
  - if (x > 4) is false (x is 3)
- Final value of x: 3
- Execution sequence: P1 (x=7), P1 (if), P2 (x=3), P2 (if)
Case 2: P2 executes fully, then P1 executes fully.
- P2:
  - x = 3; (x is now 3)
  - if (x > 4) is false (x is 3)
- P1:
  - x = 7; (x is now 7)
  - if (x < 5) is false (x is 7)
- Final value of x: 7
- Execution sequence: P2 (x=3), P2 (if), P1 (x=7), P1 (if)
Case 3: Interleaving where P2 sets x before P1’s if statement.
- P1: x = 7; (x is now 7)
- P2: x = 3; (x is now 3)
- P1: if (x < 5) is true (x is 3)
- P1: x = x + 3; (x is now 3 + 3 = 6)
- P2: if (x > 4) is true (x is 6)
- P2: x = x - 9; (x is now 6 - 9 = -3)
- Final value of x: -3
- Execution sequence: P1 (x=7), P2 (x=3), P1 (if), P1 (x=x+3), P2 (if), P2 (x=x-9)
Case 4: Another interleaving.
- P2: x = 3; (x is now 3)
- P1: x = 7; (x is now 7)
- P2: if (x > 4) is true (x is 7)
- P2: x = x - 9; (x is now 7 - 9 = -2)
- P1: if (x < 5) is false (x is -2)
- Final value of x: -2
- Execution sequence: P2 (x=3), P1 (x=7), P2 (if), P2 (x=x-9), P1 (if)

The different possible values for the variable x when the program terminates are 3, 7, -3, and -2.

Question 2

(a) Importance of “No assumptions about speeds or number of CPUs”
One of the required properties for any correct algorithm to solve the mutual exclusion problem is that “No assumptions may be made about speeds or the number of CPUs.”

Importance: The importance of this property lies in ensuring the correctness and reliability of the mutual exclusion algorithm in various execution environments. If an algorithm relies on specific assumptions about the relative speeds of processes or the exact number of CPUs available, its correctness could be violated if those assumptions do not hold. For example, an algorithm might fail to provide mutual exclusion or could lead to deadlock or starvation if a process runs faster or slower than expected, or if the number of available processors changes. A correct mutual exclusion algorithm must work correctly regardless of the scheduling of processes or the underlying hardware parallelism.

(b) Mutual Exclusion Algorithm with v1 and v2
Consider the proposed mutual exclusion solution for two processes (P1 and P2) sharing variables v1 and v2, initially set randomly to 0 or 1.

P1:

while (1) {
    while (v1 == v2); // Busy-wait while v1 equals v2
    critical_region1();
    v1 = v2; // Update v1 to the current value of v2
    non_critical_region1();
}

P2:

while (1) {
    while (v1 != v2); // Busy-wait while v1 does not equal v2
    critical_region2();
    v2 = 1 - v1; // Update v2 to the complement of v1
    non_critical_region2();
}

i. Operation and Strict Alternation
The algorithm attempts to control access to the critical regions based on the equality or inequality of v1 and v2.
- P1 waits as long as v1 is equal to v2. Once v1 is not equal to v2, P1 can enter its critical region. After the critical region, P1 sets v1 to the current value of v2.
- P2 waits as long as v1 is not equal to v2. Once v1 is equal to v2, P2 can enter its critical region. After the critical region, P2 sets v2 to the complement of v1.
This algorithm attempts to enforce strict alternation. If P1 enters its critical region (because v1 != v2), it then sets v1 = v2. This action makes v1 == v2, which should then allow P2 to proceed past its waiting loop. When P2 finishes its critical region, it sets v2 = 1 - v1. Since P1 had set v1 = v2 (the old value of v2), and P2 now flips v2, the new v2 will be different from v1, potentially allowing P1 to proceed again. The dependency is that each process sets its variable in a way that should allow the other process to proceed, enforcing a turn-taking mechanism.
ii. Violated Condition
This algorithm does not comply with the progress condition.
- Example of execution order violating that condition: Suppose v1 and v2 are initially equal (e.g., both 0). P1 is stuck in its while (v1 == v2) loop. If P2 is in its non-critical region and does not wish to enter its critical region, P1 remains blocked indefinitely even though the critical region might be free. P1 cannot make progress because it is waiting for a condition (v1 != v2) that only P2 can change by entering and exiting its critical region, but P2 is not attempting to do so. This violates the progress condition, which states that a process should not be prevented from entering its critical region by the activity of other processes outside their critical regions.

iii. Revised version using a semaphore (pseudo-code)
A semaphore can be used to correctly implement mutual exclusion. A binary semaphore (mutex) initialized to 1 can ensure that only one process is in the critical region at a time.

semaphore mutex = 1; // Initialize semaphore to 1

Process P1:
    while (true) {
        wait(mutex); // Acquire the lock (wait if mutex is 0)
        critical_region1();
        signal(mutex); // Release the lock (increment mutex)
        non_critical_region1();
    }

Process P2:
    while (true) {
        wait(mutex); // Acquire the lock (wait if mutex is 0)
        critical_region2();
        signal(mutex); // Release the lock (increment mutex)
        non_critical_region2();
    }

This solution fully complies with the conditions for mutual exclusion:

Mutual Exclusion: Only one process can hold the semaphore (mutex value is 0) and be in the critical region at a time.
Progress: If the critical region is empty, a process wishing to enter can do so if the semaphore value is 1. The decision is not dependent on processes outside their critical regions.
Bounded Waiting: Assuming a fair semaphore implementation, there is a bound on the number of times other processes can enter the critical region after a process has requested entry and before its request is granted.
No assumptions about speeds or number of CPUs: The semaphore mechanism works correctly regardless of process speeds or the number of processors.

Question 3

(a) File Allocation Table (FAT)
In the context of file systems, a File Allocation Table (FAT) is a system-level data structure that the operating system uses to manage how files are stored on a disk. The FAT is essentially an array where each entry corresponds to a cluster (a block of disk sectors). The value in each FAT entry indicates the next cluster in the file or a special marker indicating the end of a file, a bad cluster, or a free cluster. The directory entry for a file stores the number of the first cluster of the file. The OS can then traverse the FAT to find all the clusters belonging to the file.

Advantage over Linked-List Implementation: One advantage of using a FAT over a pure linked-list implementation (where each block contains a pointer to the next) is improved random access performance. In a linked-list implementation, to access a block in the middle of a file, the system must read all the preceding blocks to follow the pointers. With FAT, the FAT table can be kept in memory, allowing the system to quickly look up the next cluster number for any given cluster in a file. To find the i-th block of a file, the system can traverse the FAT starting from the first cluster number listed in the directory entry, following the chain of pointers in the FAT until the i-th entry is reached. This avoids reading all the intermediate data blocks from the disk, significantly speeding up random access.

(b) Virtual to Physical Address Translation with MMU
Consider a virtual memory system with 16-bit virtual addresses, 14-bit physical addresses, and a page size of 2K (2048 bytes).

The Memory Management Unit (MMU) is responsible for translating virtual addresses generated by the CPU into physical addresses in main memory.

Address Partitioning:
- Page size is 2K = 2048 bytes.
- Number of bits for page offset = $\log_2(2048) = 11$ bits. This is the offset within a page.
- Virtual address is 16 bits.
- Number of bits for the virtual page number (VPN) = Total virtual address bits - Page offset bits = 16 - 11 = 5 bits. The VPN identifies the specific virtual page.
- Physical address is 14 bits.
- Number of bits for the physical frame number (PFN) = Total physical address bits - Page offset bits = 14 - 11 = 3 bits. The PFN identifies the specific physical frame in memory.
Translation Process (Page is in Physical Memory):
- When the CPU generates a 16-bit virtual address, the MMU splits it into two parts: the 5-bit Virtual Page Number (VPN) and the 11-bit page offset.
- The MMU uses the VPN to index into the process’s page table. The page table is a data structure (typically stored in main memory, with a pointer to it stored in a CPU register) that maps virtual pages to physical frames.
- Each entry in the page table corresponds to a virtual page. A page table entry (PTE) contains the Physical Frame Number (PFN) where the corresponding virtual page is loaded in physical memory, along with other control bits (like valid, dirty, referenced, permissions).
- The MMU retrieves the PTE for the given VPN. It checks the “valid” bit in the PTE. If the valid bit is set, it means the page is currently in physical memory.
- The MMU extracts the PFN from the PTE.
- The MMU constructs the final 14-bit physical address by combining the PFN (as the high-order bits) with the original 11-bit page offset (as the low-order bits). The physical address is formed by $(PFN \ll 11) | \text{offset}$.
- The MMU then sends this physical address to the memory bus to access the desired data in RAM.
Translation Process (Page is Not in Physical Memory - Page Fault):
- If the MMU retrieves the PTE for the given VPN and finds that the “valid” bit is not set, it means the corresponding virtual page is not currently in physical memory (it might be on disk in the swap space). This triggers a page fault.
- The MMU traps to the operating system kernel.
- The kernel’s page fault handler takes over. It identifies the virtual address that caused the fault and the process that caused it.
- The handler determines the location of the required page on the disk (e.g., in the swap file) by consulting other system-level data structures.
- The kernel needs to bring the required page into physical memory. It first finds a free physical frame. If no free frames are available, the kernel invokes a page replacement algorithm (like LRU, FIFO, etc.) to select a victim page currently in memory to be evicted.
- If the victim page has been modified (its “dirty” bit is set), it must be written back to disk (to the swap file) before the physical frame can be reused.
- Once a free physical frame is available, the kernel initiates a disk I/O operation to read the required page from disk into the allocated physical frame.
- While the I/O is in progress, the process that caused the page fault is typically put into a waiting state, and the CPU can be scheduled to run another process.
- Once the disk read is complete, the kernel updates the page table entry for the faulting page, setting the valid bit and entering the PFN of the physical frame where the page was loaded.
- The kernel then changes the state of the faulting process from waiting back to ready.
- When the process is next scheduled to run, it will re-execute the instruction that caused the page fault. This time, when the MMU translates the virtual address, it will find the valid bit set, and the translation will proceed successfully, allowing the instruction to complete.

(c) C Program with fork()
Consider the following C program:

#include <unistd.h>
#include <stdio.h>

int main() {
    int x = 3; // Line 5

    if (!fork()) // Line 7
    {
        x = 5; // Line 8
    }

    printf("&x=%p, x=%d\n", (void *)&x, x); // Line 11
    return 0; // Line 12
}

i. Operations performed by Linux when line 7 is executed and data structures created/initialised.
When fork() is executed on line 7, the Linux operating system performs the following operations to create a new process (the child process) that is a nearly identical copy of the calling process (the parent process):
1. Process Duplication: The kernel creates a new process control block (PCB) for the child process. The PCB contains information about the process, including its state, process ID (PID), parent PID (PPID), scheduling information, etc.
2. Address Space Copying (typically Copy-on-Write): The child process is given a copy of the parent’s address space. Initially, this is often implemented using a copy-on-write mechanism. This means that the parent and child processes share the same physical pages of memory for their code and data segments. However, these shared pages are marked as read-only. When either the parent or the child attempts to write to a shared page, the kernel intercepts the write attempt (via a page fault), creates a private copy of that specific page for the writing process, and then allows the write to proceed on the private copy. This makes the copying efficient, delaying the actual copying until a modification occurs.
3. File Descriptors: The child process inherits copies of all open file descriptors from the parent process. These file descriptors refer to the same underlying files or resources, and their file offsets are shared (unless the close-on-exec flag is set).
4. Signal Handlers: The child process inherits copies of the parent’s signal handlers.
5. Return Value of fork(): The fork() system call returns a value. In the parent process, fork() returns the Process ID (PID) of the newly created child process. In the child process, fork() returns 0. The if (!fork()) condition is true only in the child process because !0 is true.
- Process Data Structures Created/Initialised:
  - Process Control Block (PCB): A new PCB is created for the child process, initialized with values copied from the parent’s PCB, with modifications for the child’s unique PID, its state (typically ‘ready’ or ‘running’), and its parent’s PID.
  - Page Table: A new page table is created for the child’s address space. Initially, entries in this page table will point to the same physical pages as the parent’s page table, but they are marked as copy-on-write.
  - File Descriptor Table: A new table for file descriptors is created for the child, initially copying the entries from the parent’s file descriptor table.
ii. Output Explanation
The provided output is:
1
2
&x=0x7fff6ee32544, x=5 &x=0x7fff6ee32544, x=3
- Why the values of &x are the same: The output shows that the memory address of the variable x (&x) is the same in both lines printed. This is because, due to the copy-on-write mechanism used by fork(), the parent and child processes initially share the same physical memory pages containing the variable x. Although they have separate virtual address spaces, the virtual address &x in both processes initially maps to the same physical memory location.
- Why the values of x are different: The values of x are different (5 in the first line, 3 in the second). This is because after the fork(), the child process enters the if (!fork()) block and modifies its copy of x by setting x = 5; This write operation triggers the copy-on-write mechanism for the memory page containing x. The kernel creates a private copy of this page for the child process. The parent process does not enter the if block, so its copy of x retains its original value of 3. When each process executes the printf statement on line 11, they are accessing their own separate copies of x in their respective address spaces (which now map to different physical memory locations), hence the different values. The order of the output lines depends on which process (parent or child) is scheduled to run first and reaches the printf statement first. In the provided output, the child process ran first (printing x=5), followed by the parent process (printing x=3).

Question 4: A dynamically allocated string

Let’s examine the C code in Figure 1 and answer the questions.

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

void copyString (char *in, char *out) {
    int i = 0;
    while (*(in + i) != '\0' && i < SIZE - 1) {
        *(out + i) = *(in + i);
        i++;
    }
    *(out + i) = '\0';
}

int main() {
    char *s = malloc(SIZE); // Line in main
    char *t = "CS2850 Operating Systems"; // Line in main
    copyString(t, s); // Line in main
    printf("s=%s\n", s); // Line in main
    printf("t=%s\n", t); // Line in main
    return 0;
}

(a) Program purpose and dynamic allocation

Program Purpose: The program defines a copyString function that copies characters from an input string (in) to an output buffer (out). The copying stops when a null terminator (\0) is encountered in the input string or when SIZE - 1 characters have been copied, whichever comes first. The output buffer is always null-terminated. The main function allocates memory dynamically for a character array s of size SIZE, initializes a string literal t, calls copyString to copy from t to s, and then prints the contents of s and t.
Dynamic Allocation: The string s is dynamically allocated because memory for it is requested at runtime using the malloc() function: char *s = malloc(SIZE);. malloc() allocates a block of memory from the heap and returns a pointer to the beginning of the allocated block. This is in contrast to static or automatic allocation (e.g., declaring char s[SIZE]; inside a function), where memory is allocated on the stack or in the data segment at compile time.

(b) Passing strings to copyString, s content change, and segmentation errors

Passing strings without &: You can pass the input and output strings (t and s) to copyString without using the address operator & because both t and s are already pointers (char *). When an array name is used in most contexts in C (including as a function argument), it decays into a pointer to its first element. malloc() returns a pointer to the allocated memory. String literals like "CS2850 Operating Systems" are typically stored in a read-only data segment, and the variable t is a pointer to the first character of this literal string. The copyString function expects char * arguments, and passing the pointers t and s directly provides the function with the addresses of the start of the input and output buffers, respectively.
How main knows s changed: The main program knows that the content of s has changed because the copyString function modifies the memory location pointed to by the out parameter, which in the call copyString(t, s) is the memory allocated for s. In C, arguments are passed by value. However, when a pointer is passed by value, the function receives a copy of the pointer. Both the original pointer in main (s) and the copied pointer in copyString (out) point to the same block of dynamically allocated memory. Therefore, modifications made through the out pointer inside copyString directly affect the contents of the memory block that s in main points to.
Segmentation errors with SIZE: Yes, the fact that SIZE (10) is smaller than the length of t (“CS2850 Operating Systems”, length 25) can cause issues, although not necessarily a segmentation fault in this specific code, it is a potential buffer overflow. The copyString function is designed to copy at most SIZE - 1 characters from in to out and then null-terminate out. In this case, it will copy the first 9 characters of t (“CS2850 Op”) into s and add a null terminator. The remaining characters of t are not copied. While this specific copyString implementation prevents writing beyond the allocated SIZE for s by stopping at i < SIZE - 1, passing a smaller buffer (s) to copy a larger string (t) is a common cause of buffer overflows if the copying function doesn’t have adequate boundary checks. If the copyString function simply copied until a null terminator was found in in without checking the size of out, it would write past the end of the buffer s, leading to a buffer overflow, which can cause unpredictable behavior, including segmentation faults (accessing memory that does not belong to the process). The provided copyString mitigates the segmentation fault risk for the output buffer out by checking i < SIZE - 1, but it doesn’t prevent the loss of data from the input string t.

(c) Output with added lines
Let’s add the lines and determine the output:

// ... (previous code) ...
    printf("t=%s\n", t);

    char c1 = *(s + 3) - '2'; // Line to add
    char c2 = *(s + 3 - 2); // Line to add
    printf("c1=%d, c2=%c\n", c1, c2); // Line to add

    return 0;
}

After copyString(t, s);, the content of s will be the first 9 characters of t followed by a null terminator: “CS2850 Op\0”.

char c1 = *(s + 3) - '2';
- *(s + 3) accesses the character at index 3 of the string s. The string s is “CS2850 Op”. The character at index 3 is ‘8’.
- '2' is a character literal.
- In C, character arithmetic is performed using their ASCII values. We are subtracting the ASCII value of ‘2’ from the ASCII value of ‘8’.
- Using the hint that digits are encoded consecutively in ASCII, ASCII('8') - ASCII('2') is equivalent to the integer difference between the numbers 8 and 2, which is 6.
- So, c1 will be assigned the integer value 6.
- The printf for c1 uses %d, which prints the integer value.
char c2 = *(s + 3 - 2);
- 3 - 2 is evaluated first, resulting in 1.
- *(s + 1) accesses the character at index 1 of the string s.
- The character at index 1 of “CS2850 Op” is ‘S’.
- So, c2 will be assigned the character value ‘S’.
- The printf for c2 uses %c, which prints the character value.

Output:

1
2
3

s=CS2850 Op
t=CS2850 Operating Systems
c1=6, c2=S

Justification of difference between statements:
- The first statement char c1 = *(s + 3) - '2'; performs pointer arithmetic (s + 3) to get the address of the character at index 3, dereferences it (*) to get the character value (‘8’), and then performs integer subtraction between the ASCII value of ‘8’ and the ASCII value of ‘2’. The result is an integer.
- The second statement char c2 = *(s + 3 - 2); performs integer subtraction (3 - 2) first to get the value 1. Then it performs pointer arithmetic (s + 1) to get the address of the character at index 1, and finally dereferences it (*) to get the character value (‘S’). The result is a character. The key difference is the order of operations and the types involved in the subtraction and dereferencing.

(d) Compilation with gcc flags and Valgrind warnings

Compilation with gcc -Werror -Wall -Wpedantic:
- The program should compile without errors using these flags, although it might produce warnings. Let’s consider potential warnings:
  - -Wall enables a large set of warnings, including those for unused variables, potentially uninitialized variables, etc. In this code, all variables appear to be used.
  - -Wpedantic warns about constructs that are outside of strict ISO C and ISO C++ standards. String literals like "CS2850 Operating Systems" are stored in read-only memory, but in older C standards, they were treated as arrays of characters, which could potentially be modified (though attempting to modify them resulted in undefined behavior). Modern C standards guarantee that string literals are constant. Assigning a string literal to a char * like char *t = "..." is considered deprecated in modern C++ (prefer const char *) and might produce a pedantic warning in C depending on the exact standard being enforced, but it’s typically allowed for backward compatibility in C. However, the core logic of the program is generally standard-compliant.
  - -Werror treats all warnings as errors. If any warnings are generated by -Wall or -Wpedantic, the compilation will fail. Given the standard nature of the code, it’s likely to compile, but minor stylistic or deprecated usage warnings from -Wpedantic are possible.
- Conclusion for compilation: It should compile, but there’s a small chance of a -Wpedantic warning being treated as an error depending on the gcc version and specific standard settings. Assuming typical usage, it should compile.
Valgrind warnings:
- Yes, you should expect Valgrind to produce a warning message.
- Justification: The program allocates memory using malloc(SIZE) for s but does not free this allocated memory before the program exits. Memory allocated with malloc on the heap persists until it is explicitly deallocated using free() or the program terminates. Although the operating system reclaims the memory upon program termination, tools like Valgrind are designed to detect potential memory leaks, which occur when dynamically allocated memory is no longer reachable by the program but has not been freed. Valgrind will report a “definitely lost” or “possibly lost” memory leak for the memory pointed to by s because free(s) is never called. To avoid this warning and prevent memory leaks in larger, long-running applications, free(s); should be added before the return 0; in main.

Question 5: Interactive sum

This question involves completing a C program that mimics parts of a UNIX shell to compute a sum based on user input characters, using fork(). We are given a code template (Figure 2).

#include <stdio.h>
#include <stdlib.h> // Needed for exit() and WEXITSTATUS
#include <unistd.h> // Needed for fork() and wait()
#include <sys/wait.h> // Needed for wait() and WEXITSTATUS

void readAndSum (int *sum, char *c) {
    if (*c >= '0' && *c <= '9') { // Check if character is a digit
        *sum = *sum + (*c - '0'); // Add the integer value of the digit
    }
}

int main() {
    int sum = 0; // Initialize sum
    int status;
    char c = '\0';

    while (c != '=') { // Loop until user enters '='
        while ((c = getchar()) != '=' && c != EOF) { // Read character by character until '=' or EOF
            if (fork() == 0) { // Child process
                readAndSum(&sum, &c); // Call readAndSum in the child
                exit(sum); // Exit child process, returning the updated sum
            }
            wait(&status); // Parent waits for the child to terminate
            sum = WEXITSTATUS(status); // Parent retrieves the child's exit status (the updated sum)
        }
    }

    printf("sum=%d\n", sum); // Print the final sum

    return 0;
}

(a) Implementing a prototype of the UNIX shell in C using fork()
A prototype of a UNIX shell in C using fork() can be implemented by following these steps:

Main Loop: The shell would have an infinite loop that prompts the user for a command, reads the command from standard input (e.g., using fgets), and processes it.
Parsing: The entered command string is parsed to separate the command name from its arguments.
fork(): When a command needs to be executed, the shell process calls fork(). This creates a child process that is a copy of the shell.
Child Process (fork() returns 0): The child process is responsible for executing the user’s command. It typically uses one of the exec() family of functions (e.g., execlp, execvp) to replace its own process image with the image of the command to be executed. The exec() call does not return on success; if it fails, the child process can print an error message and exit.
Parent Process (fork() returns child PID): The parent process (the shell) typically waits for the child process to complete its execution. This is done by calling the wait() or waitpid() system call, passing the child’s PID. Waiting prevents the shell from prompting for the next command or executing further commands before the current one finishes.
Command Execution: The exec() function in the child process loads the specified command into memory and starts its execution.
Handling Built-in Commands: Some commands, like cd (change directory) or exit, are built-in to the shell and are executed directly by the shell process without forking a new process.
I/O Redirection and Pipes: A more advanced shell would handle I/O redirection (>, <, >>) and pipes (|) by manipulating file descriptors in the child process before the exec() call.

(b) Completing the C code in Figure 2
Here is the completed C code based on the template and requirements:

#include <stdio.h>
#include <stdlib.h> // Needed for exit() and WEXITSTATUS
#include <unistd.h> // Needed for fork() and wait()
#include <sys/wait.h> // Needed for wait() and WEXITSTATUS

void readAndSum (int *sum, char *c) {
    if (*c >= '0' && *c <= '9') { // Check if character is a digit
        *sum = *sum + (*c - '0'); // Add the integer value of the digit
    }
}

int main() {
    int sum = 0; // Initialize sum
    int status;
    char c = '\0'; // Initialize c

    while (c != '=') { // Loop until user enters '='
        while ((c = getchar()) != '=' && c != EOF) { // Read character by character until '=' or EOF
            if (fork() == 0) { // Child process (fork() returns 0 in the child)
                // Child process code
                int child_sum = sum; // Child gets a copy of the current sum
                readAndSum(&child_sum, &c); // Update sum in the child's copy
                exit(child_sum); // Exit child process, returning the updated sum as exit status
            }
            // Parent process code (fork() returns child PID, which is non-zero)
            wait(&status); // Parent waits for the child to terminate. status will hold the child's exit status.
            sum = WEXITSTATUS(status); // Parent retrieves the child's exit status (the updated sum) using WEXITSTATUS macro.
        }
    }

    printf("sum=%d\n", sum); // Print the final sum

    return 0;
}

Explanation of changes:
- Included necessary headers <stdlib.h>, <unistd.h>, and <sys/wait.h>.
- Initialized sum to 0 in main.
- Initialized c to '\0' to ensure the outer loop starts.
- Completed the readAndSum function to check if the character pointed to by c is a digit and add its integer value to the integer pointed to by sum. Subtracting '0' from a digit character converts its ASCII value to its integer value (e.g., '8' - '0' = 8).
- In the child process (if (fork() == 0)):
  - Created a local variable child_sum and initialized it with the current value of sum. This is important because the child gets a copy of the parent’s memory space at the time of the fork(). Modifying sum directly in the child would not affect the parent’s sum due to copy-on-write.
  - Called readAndSum with the address of child_sum and the address of the character c that was read.
  - Called exit(child_sum). The exit() function terminates the child process and its argument (an integer) is typically used as the exit status. We are using the updated child_sum as the exit status to return it to the parent.
- In the parent process (after the if block):
  - Called wait(&status) to wait for the child process to terminate. The child’s exit status and other information are stored in the status variable.
  - Used the WEXITSTATUS(status) macro to extract the lower 8 bits of the child’s exit status. This is where the value passed to exit() is typically stored (though it can be truncated). We assign this value back to the parent’s sum, effectively updating the total sum in the parent process with the result from the child’s calculation for that character.

(c) Changing readAndSum for lowercase letters
We need to modify the readAndSum function to check for lowercase letters and add the ASCII value of the corresponding uppercase letter to the sum.
The hint mentions that the difference between the ASCII value of any lowercase letter and its corresponding uppercase letter is a constant. Let’s find this constant. ASCII('a') - ASCII('A'), ASCII('b') - ASCII('B'), etc., will all be the same value. This constant is the difference in their positions in the ASCII table.

void readAndSum (int *sum, char *c) {
    if (*c >= 'a' && *c <= 'z') { // Check if character is a lowercase letter
        // Calculate the ASCII value of the corresponding uppercase letter
        // 'a' - 'A' gives the constant difference between lowercase and uppercase ASCII values
        *sum = *sum + (*c - ('a' - 'A'));
    } else if (*c >= '0' && *c <= '9') { // Keep the digit check from the original
         *sum = *sum + (*c - '0');
    }
}

Explanation of change:
- An if condition is added to check if the character pointed to by c is within the ASCII range for lowercase letters ('a' to 'z').
- If it is a lowercase letter, the expression *c - ('a' - 'A') is evaluated.
  - 'a' - 'A' calculates the constant difference between the ASCII value of ‘a’ and ‘A’.
  - Subtracting this constant difference from the ASCII value of the lowercase character *c gives the ASCII value of the corresponding uppercase character. For example, 'b' - ('a' - 'A') is equivalent to 'b' - (a constant), which results in the ASCII value of 'B'.
- This uppercase ASCII value is then added to the sum.
- The original check for digits is kept with an else if to handle both cases.

This revised readAndSum would be used in the main function in the same place as before, but now it handles both digits and lowercase letters according to the new logic.

I hope this detailed explanation is helpful for your revision! Let me know if you have any more questions.

Revision

#CS2850

CS2850 2022 Past Paper Solution

https://blog.pandayuyu.zone/2025/05/09/CS2850-2022-Past-Paper-Solution/

Author

Panda

Posted on

May 9, 2025

Licensed under

CS2855 Databases Revision Notes Previous

CS2850 2023 Past Paper Solution Next