Agenda

• Announcements
  • Computer Science Colloquium Friday 2:30, Michael Rosenstein of MIT on robitics.
  • Lab 2 studies due Friday 4 PM.
  • Lab 3 out. Don't worry, it's not too long. It's so short, that it's due on Tuesday.
  • We now have a FreeBSD 5 machine available for our use: lebedinskaja.cs.williams.edu
• More on CPU scheduling
  • What about systems with multiple CPUs?
    • processor affinity
    • load balancing
  • Examples
    • From the text: Solaris, Win XP, Linux
    • From McKusick and Neville-Neil: FreeBSD 5.x
• Cooperating Processes
  • Bounded buffer problem
  • Race conditions

Examples

• 4.4BSD scheduler, see methods: swi_sched(), resetpriority(), setrunnable(), wakeup(), roundrobin(), and schedcpu(), many defined in /sys/kern/kern_synch.c
• Bounded-Buffer Producer/Consumer leaving an empty slot:
  • Shared data

    int buffer[n];
    int in=0;
    int out=0;
    

  • Producer process

    while (1) {
      ...
      produce item;
      ...
      while (((in+1)%n) == out); /* busy wait */
      buffer[in]=item;
      in=(in+1)%n;
    }
    

  • Consumer process

    while (1) {
      while (in==out); /* busy wait */
      item=buffer[out];
      out=(out+1)%n;
      ...
      consume item;
      ...
    }
    

• Bounded-Buffer Producer/Consumer using a shared counter:
  • Shared data

    int buffer[n];
    int in=0;
    int out=0;
    int counter=0;
    

  • Producer process

    while (1) {
      ...
      produce item;
      ...
      while (counter==n); /* busy wait */
      buffer[in]=item;
      in=(in+1)%n;
      counter=counter+1;
    }
    

  • Consumer process

    while (1) {
      while (counter==0); /* busy wait */
      item=buffer[out];
      out=(out+1)%n;
      counter=counter-1;
      ...
      consume item;
      ...
    }
    

• prodcons-shmem