EECE-4029 Operating Systems Fall 2016
Lab 6

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

Read-write Semaphore

Due: Oct 14 (submit instructions: here)

Rationale:
    Semaphores, used as mutexes, allow one thread at a time to use a resource by blocking all but one thread from executing a (critical) section of code that controls that resource. But, since there is no change to data when a shared resource is only read from and not written to, if multiple processes want to only read from a shared resource there should not be any problem in allowing access to all readers. Linux provides a special read-write semaphore that allows multiple readers into the critical section yet allows at most one writer into the critical section at any given time. This exercise is intended to show how this works in a device driver.
 
Lab:
Write a kernel module that has the following properties, and an application that makes use of those properties as described below:
  • There is a global array, called array, of 100 elements of type int.
  • Access to the global array from user space is via a character device, called interface. Thus, while the module is loaded, an application can do this:
       int fd;
       fd = open("/dev/interface", O_RDWR);
    
    to open the device for reading and writing, this:
       char read_buf[100];
       read(fd, read_buf, sizeof(read_buf));
    
    to read from the device to the read_buf array, and this:
        char write_buf[100];
        write(fd, write_buf, sizeof(write_buf));
    
    to write to the device from the write_buf array.
  • Any number of applications may perform a read operation at any time, simultaneously.
  • If several applications attempt to perform a write simultaneously, only one will be allowed to write at a time, each of the others having to wait until the operating system allows it to proceed when the current writer leaves.
The application, called app, is run from the command line like this:
   prompt> app write "Some string of less than 100 characters"
to write a string to array through /dev/interface, or like this:
   prompt> app read
to read a string from array. Practically all the code that is sufficient for app is shown above. Of course, the motivated student is free to make embellishments.
 
Assistance:
Recall that a character device driver should implement the functions stated here:
   struct file_operations fops = {
     .read = read,
     .write = write,
     .open = open,
     .release = release
   };
where read, write, open, and release have these prototypes:
   ssize_t read(struct file *filp, char *buff, size_t count, loff_t *offp);
   ssize_t write(struct file *filp, const char *buff, size_t count, loff_t *offp);
   int open(struct inode *inode, struct file *filp);
   int release(struct inode *inode, struct file *filp);
and read uses copy_to_user and write uses copy_from_user. The fops object gets tied to /dev/interface like this:
   struct cdev *kernel_cdev;  /* declared globally */
   dev_t dev_no;              /* declared globally */
   ...
   int ret;
   kernel_cdev = cdev_alloc();    
   kernel_cdev->ops = &fops;
   ret = alloc_chrdev_region(&dev_no , 0, 1, "interface");
with the last five lines expressed in init_module. The following is done in init_module (except the first line is global) to add (register) the character device interface to (with) the operating system:
   int Major;   /* declared globally */
   ...
   int dev;
   Major = MAJOR(dev_no);
   dev = MKDEV(Major,0);
   ret = cdev_add(kernel_cdev, dev, 1);
Cleanup looks like this:
   cdev_del(kernel_cdev);
   unregister_chrdev_region(dev_no, 1);
   unregister_chrdev(Major, "interface");
which shows why Major is global.

Now, about the new stuff. The copy_to_user call in read and the copy_from_user call in write should be controlled by the read-write semaphore. The sempahore structure is defined in linux/rwsem.h which is included in linux/sched.h. Since sched.h will be needed (see below), It is sufficient to use it to get the semaphore. The structure is defined like this:

   struct rw_semaphore {
      long              count;
      raw_spinlock_t    wait_lock;
      struct list_head  wait_list;
   };
and it is used like this:
   void init_rwsem(struct rw_semaphore);    Initialize the semaphore
void down_read(struct rw_semaphore *sem); Hold semaphore for reading, sleep if not available
void up_read(struct rw_semaphore *sem); Release semaphore for reading
void down_write(struct rw_semaphore *sem); Hold semaphore for writing, sleep if not available
void down_write_trylock(struct rw_semaphore *sem); Hold semaphore for writing, error if not available
void up_write(struct rw_semaphore *sem); Release semaphore for writing

The module will be tested by an application that is run in three separate shells. Since it takes some time to set that up, a delay will have to be added before executing the copy_to_read and copy_from_read. Consider the following execution sequence:

  1. Grab the semaphore
  2. Print a message indicating arrival in critical section
  3. Wait for, say, 20 seconds
  4. Print a message indicating the start of the copy
  5. Copy data to/from array
  6. Print a message indicating the end of the copy
  7. Release the semaphore
  8. Print a message indicating exit from the critical section
Implementing the above will demonstrate the action of the rw_semaphore. Each of several readers will print the first message before the 20 seconds is up. Only one of several writers will print such a message and, when it releases, another writer will enter the critical section and print the first message.

A wait_queue can be used to implement the delay. Declare a wait queue globally like this:

   wait_queue_head_t queue;
initialize the queue like this:
   init_waitqueue_head(&queue);
and delay for 20 seconds like this:
   wait_event_timeout(queue, 0, 20*HZ);

The wait queue functions are declared in linux/sched.h which also includes linux/kernel.h and linux/rwsem.h, the character device functions are declared in linux/cdev.h, the copy functions are declared in asm/uaccess.h, and unregister_chdev_region is declared in linux/fs.h which also includes the needed wait.h. These includes plus linux/module.h should be sufficient.

 
Usage:
  1. Compile:

       make
    
  2. Install:

       sudo insmod rw_sema
       cat /proc/devices | grep interface
       dmesg -> get the major number
       sudo mknod /dev/interface c major# 0 
       sudo chmod a+w /dev/interface
    
  3. Test:
    Open 3 terminals - then quickly do this, each in a separate terminal window: tryit write "Hello buddy", tryit read, tryit read. Run dmesg to see what happened. If all is well, both reads went into the semaphore and took out the write.

    Open 2 terminals - then quickly do this, each in a separate terminal window: tryit write "Hello Buddy", tryit write "Hello There". If all is well, the writes entered one a time.

  4. Unload:

       sudo rmmod rw_sema
       sudo rm -f /dev/interface