EECE-4029 Operating Systems Fall 2016
Lab 3

processes, mutex, semaphores, memory management, producer-consumer, files, deadlock, more..

Kernel module: multiple threads accessing single variable

Due: Sep 16 (submit instructions: here)

Rationale:
    Multiple threads improves overall performance by allowing tasks to be run simultaneously and cooperate with each other. However, care must be taken not allow one thread to interfere with the actions of another.
 
Lab:
Write a kernel module that creates and executes two kernel threads that associate with the same function which will be named incrementer. Function incrementer is responsible for incrementing the values of the elements of a global array which will be called arr. The size of arr is 1000000 and each element of arr is of type int. Both threads are used simultaneously to increment each element of arr through incrementer. It is required that when the incrementing operation is completed, every element has been incremented exactly by one and each incrementer has incremented at least 50000 elements. Complete this lab in two steps:
  1. Do not worry about synchronizing the two threads but make sure they run simultaneously, not sequentially (that is, first one, then the other). In init_module create two threads like this:
       int id1 = 1, id2 = 2;
       t1 = kthread_create(incrementer, (void*)id1, "inc1");
       t2 = kthread_create(incrementer, (void*)id2, "inc2");
       if (t1 && t2) {
          printk(KERN_INFO "Starting..\n");
          wake_up_process(t1);
          wake_up_process(t2);
       } else {
          printk(KERN_EMERG "Error\n");
       }
    
    Function incrementer should contain a loop that increments a global index variable, say idx, and increments arr[idx] and idx. In order to ensure that each thread will have the opportunity to call incrementer add a call to schedule to the loop. Thus, something like this:
       int incrementer(void *ptr) {
          printk(KERN_INFO "Consumer TID %d\n", (int)ptr);
    
          while (idx < 1000000) {
             arr[idx++] += 1;
             schedule();
          }
          return 0;
       }
    
    Variables arr and idx are, of course, defined globally like this:
       int arr[1000000];
       int idx = 0;
    
    and arr elements should be initialized to 0 in init_module. The following includes should be sufficient:
       #include <linux/module.h>
       #include <linux/kernel.h>
       #include <linux/kthread.h>
    
    To make things simple, statistics are collected when the module is unloaded: that way we are sure all the computation has been completed as required. To that end, define global array stat of size 1000000 elements of type int, all initialized to 0. In cleanup_module write a loop that adds 1 to stat[x] for each i from 0 to 999999 where arr[i] has value x. We will be interested in how many times incrementer is called (it is desired to be 1000000 times). To this end define variables cs1 and cs2 globally, initialized to 0. Add a test to the loop of incrementer: if (int)ptr is 1 then increment cs1, otherwise increment cs2. In cleanup_module print (KERN_INFO) values for stat[i] for every i where stat[i]>0 and print cs1, cs2, and cs1+cs2. What happened? Remove schedule() from the loop of incrementer. What happened? Note: ask yourself where id1 and id2 should be declared.

  2. Fix the above module so that each element is incremented exactly once. Success should be apparent from the module's output.

    There are several ways to fix the module. One is to use a semaphore to lock the statement that changes the value of arr[idx] in the loop of incrementer. Semaphores are defined in linux/semaphore.h as struct semaphore. Globally declare a variable of this type, call it lock. In init_module initialize this variable to be unlocked with sema_init(&lock, 1). To protect the line that increments elements of arr preceed it with a test that causes the thread to wait until the lock is unlocked then resumes the thread and locks lock (typically using this: !down_interruptible(&lock)), and unlocks lock when finished (using up(&lock)). There are several other ways to accomplish this synchronization and you would do well to try some others. Compare them with gettimeofday which is available through linux/time.h.

    All elements should have value 1 when the module is unloaded. But the number of times idx is incremented may be 1000001. Why is that?