Assignment 12, due Nov. 22

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

1. Background: Consider the buddy system implementation distributed in the skeleton solution to MP6, along with the mymalloc code that converts between the malloc()/free() API and the requirements of the buddy system.

   a) A design choice was made here, to have the free-list index passed to the buddy system interface routines instead of passing the size of the desired block. This makes mymalloc() do extra work computing the log₂ of the block size. Does this lead to an overall savings in computational effort, or does it merely move work from buddyalloc() to mymalloc(). Explain. (0.5 points)

   b) In buddyfree() the code contains a loop searching the free list. Why wasn't the loop written like this?

   /* search for budy in free list */
   b = freelists[i];
   for (;;) { /* loop exit by break */
          if (b == NULL) {
   
                 /* put p at start of list */
                 *(void **)p = freelists[i];
                 freelists[i] = p;
   
                 /* quit loop */
                 break;
          }
          if (((intptr_t)p) == (((intptr_t)b) ^ (1 << i))) {
   
                 ... etc ...
   
                 /* free result of merger */
                 buddyfree( p, i + 1 );
                 break;
          }
          /* walk down list */
          b = *(void **)b;
   }
   

   (0.5 points)

2. Background: Consider these alternative ways to link two UNIX processes where one process produces data that is consumed by the other:
   • The processes each use mmap() to map a shared disk file into their address spaces, and then they build a FIFO bounded-buffer queue in that shared virtual memory, using a pair of named semaphores that they connect to using sem_open() to track the amount of data and free space in the queue.

   • The parent process uses mmap() to map an anonymous block of shared memory for the queue and its two semaphores, uses sem_init() to initialize the semaphores, and then calls fork() to create the other process that will communicate through this queue.

   • One process uses write() to enqueue data items on the queue while the other uses read() to dequeue. The buffer sizes used by both of the above must match the size of the objects being pushed through the queue. The shell that was used to launch both processes is responsible for connecting them with a pipe, created using pipe().

   a) Which of these options give (or gives) the programmer control over the size of the bounded buffer. (0.5 points)

   b) Which of these options has the potential to be more efficient, in terms of the number of system calls required to move the data? Explain. (Count only calls used to move data after the initial communication channel has been set up.) (0.5 points)

3. Background: The Unix kernel was largely developed before semaphores were invented, and the semaphore services in the Unix kernel were added as afterthoughts. Many important Unix utilities such as sendmail were developed before before these afterthoughts were added. Named pipes are also an afterthought; in the original Unix, for two processes to communicate through a pipe, that pipe must have been created by an ancestor that forked to run the two in parallel.

   Classical Unix did, however, have the following services that are relevant here:

   • pause()
   • setitimer()
   • open( fname, O_EXCL | O_CREAT | O_RDWR , S_IRWXU )
   • unlink( fname )

   Classical Unix applications (still, to this day) use what are called lock files for critical section synchronization. A lock is considered to be claimed (indicating that a process is in the associated critical seciton) if the lock file exists. Busy waiting is used to enter critical sections, with the CPU demand reduced by throttling back the polling rate using timers.

   a) Write a C function called delay1() that causes the calling process to wait one second. The only kernel calls required are mentioned above. (0.4 points)

   b) Give a fragment of C code to enter a critical seciton guarded by the lock file /usr/mail/lock -- your code should cally your delay1 routine each time it polls the lock. The only kernel calls required are mentioned above. (0.4 points)

   c) Give a fragment of C code to exit the critical seciton guarded by the lock file /usr/mail/lock. The only kernel calls required are mentioned above. (0.2 points)