30203 LI Systems Programming in C and C++
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
30203 LI Systems Programming in C and C++
Main Summer Examinations 2022
Exam paper
Question 1
The code below defines a singly-linked list . This consists of the following definition of node:
1 struct node –
2 int val;
3 struct node * next; 4 ˝
Also, it uses the following insert function:
5 struct node * insert(struct node * first, const int val) –
6 struct node * pred = NULL, * succ = first;
7 while (succ != NULL) –
8 if (succ-¿val ¡ val)
9 pred = succ;
10 if (succ-¿val ¿ val)
11 break;
12 succ = succ-¿next; 13 ˝
14 struct node * this = malloc(sizeof(struct node));
15 this-¿val = val;
16 this-¿next = succ;
17 if (pred != NULL) –
18 pred-¿next = this;
19 return first; 20 ˝ else –
21 return this; 22 ˝
23 ˝
Note that the code above compiles correctly.
(a) Give an implementation in C for a function that prints all values in the singly-linked
starting from the first node and following the next node one by one along the list . Use the following signature:
(b) Give a function in C that frees all nodes in the list . Use the following signature:
void destroy(struct node * first); [3 marks]
(c) Refer to the insert function above . Briefly describe what the sequence of printed value will be, with respect to any sequence of inserted values . Note that values are supposedly inserted as follows:
struct node * list = NULL;
while (¡there is a value to insert¿)
list = insert(list, ¡next value to insert¿);
[7 marks]
(d) Consider a program that inserts a sequence of values, prints the list, and destroys the list . Assume that print and destroy work as intended . The given insert function causes a memory leak . Identity where it is and how it occurs . Correct the insert function to remove the leak . Your solution should not alter the elements that are inserted and their order
[7 marks]
Question 2
(a) The question is about Main and Virtual Memory. Provide a brief answer .
(i) Why does a processor have a set of registers in addition to a large main memory?
[1 mark]
(ii) A long-term scheduler controls the degree of multi-programming in an Oper-
ating System . The long-term scheduler can send a process to which state(s)?
[1 mark]
(iii) Does adding more frames during Page Replacement always lead to improved
performance? [1 mark]
(iv) A system is running with following measure behaviour: CPU utilization 10%;
Paging disk 95% Other I/O devices 3% . Explain which of the following actions will improve CPU utilization and why?
i . Install more main memory
ii . Install a faster disk
iii . Changing the degree of multi programming [3 marks]
(b) Briefly describe what the possible consequences are of a buffer overflow in the kernel .
[6 marks]
(c) Consider the following piece of kernel code. The intention is that whenever data is written to a proc-file, this data is written to a device . The device provides two functions: start transfer starts the transfer of count bytes to the device and returns immediately, and transfer finished, which is called by the device when the data transfer is finished . The function kernelWrite should return the number of bytes transferred to the device .
1 int total˙transferred = 0;
2 /* total number of bytes transferred since module loaded */ 3 int transferred = 0;
4 /* bytes transferred to device in single transaction */ 5
6 /* called by device when transfer finished */
7 /* called in interrupt mode */
8 void transfer˙finished(int count) –
9 transferred = transferred + count;
10 /* wakeup waiting process */
11 ˝
12
13 /* called every time data is transferred to kern
14 ,as a result of writing to proc-file */
15 int kernelWrite(char * buffer, int count) – 16 /* buffer is pointer to user space */
17 start˙transfer(buffer, count);
18 /* go to sleep until woken up in transfer finish */ 19 transferred = transferred + count;
20 return transferred; 21 ˝
22
23 void init module(void) –
24 /* set up proc-structure - code omitted */
25 proc-¿write˙proc = kernelWrite;
26 ˝
27 ˝
This kernel code compiles correctly but does not work as intended . Identify these errors and suggest remedies . If you think critical sections are required, it is sufficient to indicate begin and end of a critical section, and whether you would use semaphores or spinlocks to protect the critical section .
[8 marks]
Question 3
(a) Four processes running on a single-core processor (Table 1) . Among all the Schedul-
ing Algorithms, briefly explain which one you will prefer and which one you would like to avoid for the given scenario? [5 marks]
Table 1: List of Processes
(b) Predict all possible outputs that the following C program will print to the console
and briefly explain your answer . What will be the state of parent process? Briefly explain the behaviour of the program if we comment out the line number 16 .
1 #include ¡sys/types .h¿
2 #include ¡sys/wait .h¿
3 #include ¡unistd .h¿
4 #include ¡stdio .h¿
5 #include ¡stdlib .h¿
6 int main() –
7 pid˙t wpid, child˙pid;
8 int status = 0;
9 int i;
10 for(i = 0; i ¡ 2; i++) –
11 if ((child˙pid = fork()) == 0) –
12 printf(”process “n”);
13 exit(0);
14 ˝
15 ˝
16 while ((wpid = wait(&status)) ¿ 0);
17 return 0; 18 ˝
[5 marks]
(c) Your computer system uses Round Robin scheduler and is not very responsive and so you decide to change the scheduling time quantum from 50 msec to 1 msec . Now the performance is even worse . Why is this happening? [4 marks]
(d) Consider a concurrent system with two processes A and B (Figure 1) . Assume y is a shared variable with value of 5 . Describe how a race condition is possible and provide a solution to prevent the race condition from occurring . [6 marks]
Figure 1: Concurrent processes A and B
2022-08-09