There are 3 problems totaling 100 points:

Problem 1: 32 points

Problem 2: 27 points

Problem 3: 41 points

Assume the following programming environment unless noted otherwise:

- Current release of Arch Linux with 4.9.81 kernel, 64-bit x86 version,

running under VirtualBox, with 2 CPUs and 2G RAM assigned to the VM .

- All user level programs are compiled with gcc with no optimization.

- The host computer is equipped with a recent model of Intel x86 processor

which contains 2 or more CPU cores .

- All library function calls and system calls are successful when they are

invoked correctly . For example, you can assume that fork() will

successfully create a child process and malloc() will not return NULL

when it is called with a reasonable argument .

- Some of the programs omit #include statements to save space . Assume that

all necessary #includes are there . If the exam refers to code from

homework assignments, assume that it is referring to the solution code .

What to hand in and what to keep:

- At the end of the exam, you will hand in only the answer sheet, which is

the last two pages (one sheet printed double-sided) of the exam booklet .

- Make sure you write your name & UNI on the answer sheet.

- All other pages (i .e ., the rest of this exam booklet and any scratch

papers you have used during the exam) are yours to keep .

- Before you hand in your answer sheet, please copy down your answers back

onto the exam booklet so that you can verify your grade when the

solution is published in the mailing list .

- Please be clear and succinct on your answer sheet .  If a question asks

for a single number or a single word, do not write anything else .  If a

question asks for a short explanation, keep it short and precise .  If

you give two different answers, we will take the one that will result in

a LOWER grade .  If you give a vague explanation that can be interpreted

in multiple ways, we will choose the interpretation that will result in

the LOWEST possible grade .

+---------------------------------------------------------------------+

|  PLEASE DO NOT OPEN THIS EXAM BOOKLET UNTIL YOU ARE TOLD TO DO SO!  |

+---------------------------------------------------------------------+

[blank page]

Problem [1]: 32 points

----------------------------------------------------------------------------

For each of the following statements, please write "TRUE" or "FALSE".

(1.1)

BFS uses a single runqueue across all CPUs, but MuQSS, which is an evolution

of BFS, uses per-cpu multiple runqueues .

(1.2)

Unlike mutex and semaphore, spin locks can be used in interrupt context.

(1.3)

The Least-Recently-Used (LRU) page replacement algorithm is an approximation

of the clock algorithm .

(1.4)

Physical Address Extension (PAE), available on some x86 processors, uses

36-bit virtual address, increasing the range of virtual address space of

each process to 64GB .

 

____________________________________________________________________________

 

For (1 .5) and (1 .6), assume that a process executing a system call has

called spin_lock() function and has successfully acquired the spin lock .

(1.5)

The process holding the spin lock can be preempted by another process.

(1.6)

The process holding the spin lock can be preempted by an interrupt handler.

Problem [1] continued

----------------------------------------------------------------------------

For (1 .7)- (1 .8), recall the Freezer scheduling class .  Assume that the

behavior of Freezer’s select_task_rq has been changed as follows:

 

static int select_task_rq_freezer(struct task_struct *p,

int _cpu, int _sd_flag, int _flags)

{

int cpu, cpu_choice;

int num_rq_task = 0;

struct rq *rq;

struct cpumask allowed = (struct cpumask) p->cpus_allowed;

/* assume that the SET_DEFAULT_CPU() macro exists */

cpu_choice = SET_DEFAULT_CPU(&allowed);

for_each_cpu(cpu, &allowed) {

rq = cpu_rq(cpu);

if (num_rq_task < rq->freezer .nr_running) {

num_rq_task = rq->freezer .nr_running;

cpu_choice = cpu;

}

}

return cpu_choice;

}

 

Answer the following TRUE/FALSE questions:

(1.7)

All CPU runqueues will contain roughly the same number of processes over

time .

(1.8)

A multi-threaded program will likely perform better under this

implementation than under the original Freezer implementation .

Problem [2]: 27 points

----------------------------------------------------------------------------

Consider the following program that inspects various memory addresses using

the inspect_cabinet system call that we have developed in HW7 .

For (2 .1)- (2 .5), complete the outputs by writing 0 or 1 or UNPREDICTABLE in

the blanks on the answer sheet . Write UNPREDICTABLE if the output can vary

from one run of the program to another .  For (2 .6)- (2 .9), answer the

questions by writing SAME or DIFFERENT in the blanks on the answer sheet .

Recall that the program is run under the following condition: 4.9.81 kernel,

x86-64, running under VirtualBox with 2 CPUs and 2G RAM assigned to the VM .

/***********************************************************

* The following is the struct cab_info definition from HW7 .

* Note that uint64_t is the same as unsigned long .

*/

struct cab_info {

uint64_t

uint64_t

uint64_t

uint64_t

uint64_t

uint64_t

int soft_dirty;

int refcount;

};

static inline int inspect(void *vaddr, struct cab_info *inventory) {

int nr = 405;    // syscall number for inspect_cabinet

pid_t pid = -1;  // -1 for the calling process

return syscall(nr, pid, (uint64_t)vaddr, inventory);

}

int main(void)

{

int x = 0;

struct cab_info a;

inspect(&x, &a);  // inspect address of a local variable

printf("(2 .1) a .paddr >= a .pf_paddr: %d\n",

a .paddr >= a .pf_paddr);

printf("(2 .2) a .pf_paddr == a .pgd_paddr: %d\n",

a.pf_paddr == a .pgd_paddr);

printf("(2 .3) a .paddr > (uint64_t) &x: %d\n",

a .paddr > (uint64_t) &x);

struct cab_info b;

inspect(&main, &b);  // inspect address of a function

printf("(2 .4) b .dirty: %d\n",

b .dirty);

assert((unsigned long) &x > (unsigned long) &main);

printf("(2 .5) a .paddr > b .paddr: %d\n",

a .paddr > b .paddr);

// code continued on the next page

Problem [2] continued

----------------------------------------------------------------------------

// (2.6)

char *buf1 = malloc(4096);

assert(buf1 != NULL);

*buf1 = ’A’;

pid_t pid = fork();

struct cab_info c;

if (pid == 0) {  // child process

inspect(buf1, &c);

printf("[A]: c .paddr: %lx\n", c .paddr);

exit(0);  // child process terminates

} else {

waitpid(pid, NULL , 0);  // wait for child process to terminate

inspect(buf1, &c);

printf("[A]: c .paddr: %lx\n", c .paddr);

}

// The above if/else block prints two lines that start with "[A]" .

// Are they same or different? Write SAME or DIFFERENT on answer sheet .

printf("(2.6) Two [A] lines are ________________\n");

 

 

// (2.7)

pid = fork();

if (pid == 0) {  // child process

*buf1 = ’B’;

inspect(buf1, &c);

printf("[B]: c .paddr: %lx\n", c .paddr);

exit(0);  // child process terminates

} else {

waitpid(pid, NULL , 0);  // wait for child process to terminate

inspect(buf1, &c);

printf("[B]: c .paddr: %lx\n", c .paddr);

}

// The above if/else block prints two lines that start with "[B]" .

// Are they same or different? Write SAME or DIFFERENT on answer sheet .

printf("(2.7) Two [B] lines are ________________\n");

 

 

// Code continued on the next page

Problem [2] continued

----------------------------------------------------------------------------

// (2.8)

// The following mmap() call correctly creates a shared memory

// segment of 4096 bytes using anonymous memory mapping .

char *buf2 = mmap(NULL, 4096, PROT_READ | PROT_WRITE,

MAP_SHARED | MAP_ANONYMOUS, -1, 0);

assert(buf2 != NULL);

*buf2 = ’C’;

pid = fork();

if (pid == 0) {  // child process

assert(*buf2 == ’C’);

inspect(buf2, &c);

printf("[C]: c .paddr: %lx\n", c .paddr);

exit(0);  // child process terminates

} else {

waitpid(pid, NULL , 0);  // wait for child process to terminate

assert(*buf2 == ’C’);

inspect(buf2, &c);

printf("[C]: c .paddr: %lx\n", c .paddr);

}

// The above if/else block prints two lines that start with "[C]" .

// Are they same or different? Write SAME or DIFFERENT on answer sheet .

printf("(2.8) Two [C] lines are ________________\n");

 

 

// (2.9)

pid = fork();

if (pid == 0) {  // child process

*buf2 = ’D’;

inspect(buf2, &c);

printf("[D]: c .paddr: %lx\n", c .paddr);

exit(0);  // child process terminates

} else {

waitpid(pid, NULL , 0);  // wait for child process to terminate

inspect(buf2, &c);

printf("[D]: c .paddr: %lx\n", c .paddr);

}

// The above if/else block prints two lines that start with "[D]" .

// Are they same or different? Write SAME or DIFFERENT on answer sheet .

printf("(2.9) Two [D] lines are ________________\n");

return 0;

}

Problem [3]: 41 points

----------------------------------------------------------------------------

The following kernel module implements two Linux system calls,

update_temperature() and set_oven_alarm() .

A process can call set_oven_alarm() with a desired temperature, and they

will block until the oven reaches the desired temperature . Another process

can call update_temperature() to set the oven temperature, and wake up all

the processes which have been waiting on a temperature equal to or lower

than the new temperature .

 

 

1  struct temp_event {

2           long temperature;

3           int count;

4           struct list_head entries;

5           wait_queue_head_t q;

6  };

7

8  struct oven {

9           long temperature;

10           struct list_head entries;

11  };

12

13  struct oven kitchen_oven; 14

15  long update_temperature(long temp) {

16           struct list_head *pos;

17           struct temp_event *te;

18

19           kitchen_oven .temperature = temp;

20           list_for_each(pos, &kitchen_oven .entries) {

21                     te = list_entry(pos, struct temp_event, entries);

22                     if (temp >= te->temperature) {

23                              wake_up_all(&te->q);

24                     }

25            }

26           return 0;

27  }

28

29  struct temp_event *find_alarm(long temperature) {

30           struct list_head *pos;

31           struct temp_event *te;

32

33           list_for_each(pos, &kitchen_oven .entries) {

34                     te = list_entry(pos, struct temp_event, entries);

35                     if (te->temperature == temperature) {

36                              return te;

37                     }

38            }

39           return NULL;

40  }

41                                 // code continued on the next page

// Problem [3] continued

42   long set_oven_alarm(long temperature) {

43             struct temp_event *te;

44             struct temp_event *new;

45             char delete_new  = 0x0;

46           char delete_curr = 0x0; 47

48            DEFINE_WAIT(wait);

49             new = kmalloc(sizeof(*new), GFP_KERNEL);

50             if (!new) {

51                      return -ENOMEM;

52             }

53             if (kitchen_oven .temperature >= temperature) {

54                      return 0;

55             }

56             te = find_alarm(temperature);

57             if (te) {

58                      te->count++;

59                      delete_new = 0x1;

60             } else {

61                      te = new;

62                      te->count = 1;

63                      te->temperature = temperature;

64                      init_waitqueue_head(&te->q);

65                      list_add_tail(&te->entries, &kitchen_oven .entries);

66             }

67            while(1) {

68                      prepare_to_wait(&te->q, &wait,TASK_UNINTERRUPTIBLE);

69                      if ( _________________________________ ) {

70                               _________________________ ;

71                               _________________________ ;

72                      }

73                      if (delete_new) {

74                               kfree(new);

75                      }

76                      schedule();

77             }

78             finish_wait(&te->q, &wait);

79             if (te->count == 0) {

80                      list_del(&te->entries);

81                      delete_curr = 0x1;

82             }

83             if (delete_curr) {

84                      kfree(te);

85             }

86             return 0;

87   }

88

89   extern long (*update_temperature_ptr)(long temperature);

90   extern long (*set_oven_alarm_ptr)(long temperature); 91

92   int oven_init(void) {

93             update_temperature_ptr = update_temperature;

94             set_oven_alarm_ptr     = set_oven_alarm;

95             kitchen_oven .temperature = 0;

96             INIT_LIST_HEAD(&kitchen_oven .entries);

97             return 0;

98   }

// Problem [3] continued

99  void oven_exit(void) {

100           update_temperature_ptr = NULL;

101           set_oven_alarm_ptr     = NULL; 102  }

103  module_init(oven_init);

104  module_exit(oven_exit);

105  MODULE_LICENSE("GPL");

106  MODULE_DESCRIPTION("oven");

107  MODULE_AUTHOR("cs4118");

----------------------------------------------------------------------------

(3 .1) Fill in the blanks in the if statement of line numbers from 69 to 72.

You may write up to two statements inside the curly braces .

 

 

The code as shown above is not guarded against race conditions of multiple

threads concurrently updating temperatures and setting alarms .  In

(3 .2)- (3 .4), we add a spinlock to make the two system calls fully

thread-safe .

 

 

(3.2) Between which adjacent lines should the following declaration appear?

spinlock_t lock;

If you think it should go between lines 200 and 201, you should write

"200,201" .  Add only one spinlock declaration . The spinlock object

should not be declared as a global variable .

 

(3.3) Now we will add the following function/macro calls:

spin_lock_init(spinlock_t *lock)

spin_lock(spinlock_t *lock)

spin_unlock(spinlock_t *lock)

On the answer sheet, indicate where these calls should be inserted by

writing the two adjacent line numbers and the call . Example:

247,248: spin_unlock(CORRECT_ARGUMENT);

250,251: spin_lock(CORRECT_ARGUMENT);

289,290: spin_lock_init(CORRECT_ARGUMENT);

294,295: spin_unlock(CORRECT_ARGUMENT);

Substitute CORRECT_ARGUMENT with the actual argument, of course . The

function calls must be placed to make the critical sections as small

as possible .

 

(3 .4) Even after successfully writing in all of the spinlock calls, you

realize that your module causes a kernel panic under a highly

concurrent workload . Add a single line of code that will fix this

issue .

Write the two adjacent line numbers and the code. (Hint: memory!)

COMS 4118 Spring 2018: Exam #2 Answer Sheet, page 1 of 2

UNI:                       Name:

----------------------------------------------------------------------------

[1] Write TRUE or FALSE:

(1.1) ____________________________

(1.2) ____________________________

(1.3) ____________________________

(1.4) ____________________________

(1.5) ____________________________

(1.6) ____________________________

(1.7) ____________________________

(1.8) ____________________________

 

 

 

 

 

 

 

 

 

 

 

[2]

For (2.1)- (2.5), write 0 or 1 or UNPREDICTABLE.

(2.1)     a.paddr >= a.pf_paddr: ________________________________

(2.2) a.pf_paddr == a.pgd_paddr: ________________________________

(2.3)   a.paddr > (uint64_t) &x: ________________________________

(2.4)                   b.dirty: ________________________________

(2.5)         a.paddr > b.paddr: ________________________________

For (2.6)- (2.9), write SAME or DIFFERENT.

(2.6) Two [A] lines are ________________________________

(2.7) Two [B] lines are ________________________________

(2.8) Two [C] lines are ________________________________

(2.9) Two [D] lines are ________________________________

 

COMS 4118 Spring 2018

Exam #2

Answer Sheet, page 2 of 2

+---+---+---+---+---+---+---+---+

Your UNI: |    |    |    |    |    |    |    |    |

+---+---+---+---+---+---+---+---+