Agenda

• Announcements
• Dining Philosophers
• How to Write Programs
• Unix Systems Programming

Announcements

Classical Problems of Synchronization

Dining Philsophers

• Five philosophers alternate thinking and eating
• Need 2 forks to do so (eating spaghetti), one from each side
• keep both forks until done eating, then replace both

Since fork is the name of a C function, we'll use a different (and possibly more appropriate) analogy of chopsticks. The philosophers needs two chopsticks to eat rice.

• Shared data:

  semaphore chopstick[5];
  chopstick[0..4]=1;
  

• Philosopher i:

  while (1) {
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
  
     /* eat */
  
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
  
     /* think */
  
  }
  

This solution may deadlock. One way to reduce the chances of deadlock might be to think first, since each might think for a different amount of time.

Another possibility:

Each philosopher

1. Picks up their left chopstick
2. Checks to see if the right chopstick is in use
3. If so, the philosopher puts down their left chopstick, and starts over at 1.
4. Otherwise, the philosopher eats.

Does this work?

No! It livelocks. Consider this: all could pick up their left chopstick, look right, put down the left, and repeat indefinitely.

How to solve this? Must either

1. introduce an asymmetry, or
2. limit the number of concurrently hungry philosophers to n-1.

Here's one that includes an asymmetry, by having odd numbered philosophers pick up to the right first. The code for philosopher i and problem size n.

void philosopher() {
  think;
  if (odd(i)) {
    wait(chopstick[(i+1) % n]);
    wait(chopstick[i]);
  }
  else {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % n]);
  }
  eat;
  if (odd(i)) {
    signal(chopstick[(i+1) % n]);
    signal(chopstick[i]);
  }
  else {
    signal(chopstick[i]);
    signal(chopstick[(i+1) % n]);
  }
}

How to Write Programs

Design your program first! Implement it incrementally!! Computers are fast. Compiling doesn't take long. Compile and test often! Construct your Makefile first - it's there to help you! Document as you go!

Unix Systems Programming

You need to use a number of Unix system calls to implement Project 2. We have seen a few of these:

getpid() - get current process ID

getppid() - get parent's process ID

fork() - duplicate process. Child is a copy of the parent - in execution at the same point, the statement after the return from fork().

The return value indicates if you are child or parent. 0 is child, >0 means parent, -1 means failure (limit reached, permission denied)

Example:

pid=fork();
if (pid) {
  parent stuff;
}
else {
  child stuff;
}

exit() - terminate a process. If it's a child, it waits for its parent to accept its return code. If this doesn't happen, the child is called a "zombie" process.

To avoid this - call wait() from the parent - parent stops and waits for the child to terminate (call exit()). returns PID of child, and in its argument, the status includes the value the child passed to exit(). Be careful not to confuse this wait() with the wait() operation on semaphores!

Running a new program - exec calls

fork() lets you have two copies of a process - the same process. To create processes that do other stuff, the fork() is followed by one of these "exec" calls:

execl() - exec process with list of arguments

execv() - exec process with args specified in an array

execlp() - list, but search path for the program.

execvp() - array, but search path for the program.

Example:

#include <stdio.h>
#include <unistd.h>

int main() {

  printf("This program will magically become ls -l\n");
  execlp("ls", "ls", "-l", NULL);
  printf("So this line never executes...\n");
  return 0;
}

Signals

Unix processes can communicate by sending each other signals.

Type kill -l at your favorite Unix prompt to see the names of the signals it supports.

kill -SIGNAL pid will send signal SIGNAL to a process pid:

-> sleep 60&
[1] 96132
-> kill -TERM %1
[1]+  Terminated              sleep 60
-> sleep 60&
[1] 96133
-> kill -STOP %1
[1]+  Stopped                 sleep 60
-> kill -CONT %1
-> jobs
[1]+  Running                 sleep 60 &
-> 
[1]+  Done                    sleep 60
-> 

Two system calls are used to send and catch signals:

signal() - replace default handler. Lets you "trap" many signals and handle them appropriately.

Be careful not to confuse this signal() with the signal() operation on semaphores!

Example: A compute-bound process that "wakes up" every 5 seconds to report on its progress. [sigalrm-example.c]

We can ignore a signal completely by setting its handler to SIG_IGN, and restore the default handler with SIG_DFL.

Enhanced example: [sigalrm-example2.c]

A process can also send signals with kill(). Don't let the name fool you, you can send any signal with kill(), not just SIGKILL.