Computer Science 432
Operating Systems

Lecture 06: CPU Scheduling 3: Multiprocessors, Linux 2.6, FreeBSD ULE. Cooperating Processes, Bounded Buffer Problem
Date: September 26, 2006

Announcements
- Mike will not hold "official" TA hours this week, but you should feel free to contact him with questions on the simulator lab.
- Get your Unix groups and Subversion repositories.
CPU scheduling wrapup
- What about systems with multiple CPUs?
  - scaling
  - locking issues
  - processor affinity
  - load balancing
- Examples
  - From the text: Solaris, Win XP, Linux
  - Linux 2.6 O(1) scheduler
  - From McKusick and Neville-Neil: FreeBSD 5.x ULE scheduler
Cooperating Processes
- Bounded buffer problem
- Race conditions

There is no lecture assignment to submit for Thursday. Work on those simulations!

The readings for next time are SG&G Sections 3.4.1 and 6.1-6.3.

4.4BSD scheduler, see methods: resetpriority(), setrunnable(), wakeup(), roundrobin(), and schedcpu(), many defined in /sys/kern/kern_synch.c
ULE scheduler, see /sys/kern/sched_ule.c on any FreeBSD lab system running FreeBSD 5.x.

Bounded-Buffer Producer/Consumer leaving an empty slot:

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;
  ...
}