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:

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