It's 7:10AM and the bus has just left Little Compton on it's way to Providence. The bus driver was talkative this morning and I learned a something about how they schedule the bus drivers' vacations, making sure to honor a complex pecking order while preserving safety (make sure that there is a driver for every bus route for every day the route shows up on the bus schedule) and fairness (every driver should eventually get a vacation). Some schemes for scheduling processes in computers (task management) are nearly as complex.

The task-management scheme that I outlined a few days back can be summarized as follows: Processes are grouped by their priority. A process is assigned a priority at the time that it is created but under some circumstances the priority for a process can change (I'll get to this in a minute). The process scheduler (task manager) selects the highest priority group of processes in which at least one process is ready to run. It then proceeds to allocate slices of CPU time to each process in this group using a round-robin allocation scheme until either all of the processes in that group have run to completion or a process in a group at a higher priority becomes ready to run. This simple scheme works pretty well though we'll need to modify it somewhat in order to make sure that all processes eventually get to run (a measure of fairness).

Modern operating systems like Sun Microsystems's Solaris, Apple Macintosh's OS X, Microsoft's XP and Linux distinguish between those threads of control (processes) spawned by the user and those spawned by the operating system to provide basic services. The OS-spawned processes are called kernel threads because the inner-most software components of the OS reside in a core system called the kernel. Many of the threads that perform tasks for the operating system are interrupt driven. For example, the process controlling a disk drive might go to sleep waiting on the disk as it grinds along reading or writing data (disks are glacially slow compared to most modern processors) and then wake up when the disk signals through an interrupt that there is something that the process can do.

Sleeping processes are ignored by the scheduler. A process might put itself to sleep for a specified interval of time when it has nothing to do. Such a process tells the scheduler to set the status of the process to "waiting". It then sets an alarm clock to wake it after the specified interval of time has elapsed. The alarm clock is a digital counter that counts pulses of the system clock; you set the alarm by setting the counter to a number corresponding to the specified interval of time and then let the counter count down to zero by decrementing the counter on each pulse of the system clock. When the counter reaches zero it sends an interrupt to the CPU which causes the scheduler to set the status of the process to "ready to run".

Modern operating system use semaphores (see the July 28, 2002 entry) to sychronize processes and make sure that everything gets done in a timely and efficient manner. Semaphores control access to shared resources and prevent processes from getting hung up waiting for one another in what are called deadlocks. If one process is already using a shared resource, then a second process wanting to use that resource will be able to tell this by checking a semaphore set by the first process; the second process will put itself to sleep with directions to wake it up when the first process is finished using the resource.

After all this talk about the scheduling processes, I'm curious about what sort of processes are running on my laptop as the bus barrels through Barrington along Route 114. I'll run the process-status program, ps, asking for all processes including those of other users (-a) and those that aren't associated with a command console (-x) and pipe the results into the word-count program, wc, asking it to count the number of lines lines (-l) thus giving me some idea of how many processes are currently running on my laptop.

/usr/tld % ps -ax | wc -l
      36 

I also just ran the process-status program with the report usage option (-u) to find out how much of the CPU and memory each process is using. Most of the processes aren't using the CPU at all right now; they're just waiting for some event to trigger an interrupt, e.g., if I tried to use the network, it would trigger an interrupt and wake up the kernel thread responsible for handling network communications. I also noted that some of the processes aren't even currently resident in memory, RAM.

I guess I haven't talk about virtual memory so you may have no idea how a "running" process can exist outside of RAM. (Think of a memory, say your first day in high school or the first time you drove a car, and then think what it might mean to have virtual memory.) The short explanation is that one of the services most operating systems provide is to optimize the use of memory to give the illusion that you have almost unlimited RAM. The OS does this by carefully mapping out a very large virtual address space, significantly larger than the amount of random access memory that you have installed in your machine; at any given time, portions of this large memory are mapped to real RAM, these are the portions that are immediately accessible to the CPU. Those portions of memory currently not mapped to real RAM are moved to RAM (and other portions swapped out) when the need arises, say, when they contain instructions corresponding to a process that has to perform some essential service.

The contents of this virtual address space that currently don't reside in RAM are stored on a part of your disk referred to as swap space. The operating system maintains this illusion of a very large memory by moving instructions and data back and forth between RAM and disk on an as-needed basis. This is yet another example of how the OS provides an abstraction that makes it much simpler for the programmer to write large complex programs.

Of course, there is overhead associated with shuttling instructions and data back and forth between RAM and disk. Reading and writing from disk is substantially slower than reading and writing from RAM. I alluded earlier to the notion of "thrashing" which is what happens with you have too little real memory or RAM and too much in virtual memory and hence stored on disk. In this case, the OS spends much of its time swapping processes and data into and out of physical memory as processes are given their allocations of the CPU.

Imagine that a process running your word-processing program is just pulled off the queue of processes and given a slice of CPU time to run. Just when the relevant parts of the process are moved from disk to RAM and the registers are restored to their state just prior to the last time the process was interrupted, the little slice of time allocated to the process runs out and the process has to relinquish the CPU to the next process awaiting cycles. That's what happens when you have too many processes and too little memory or too slow a processor.

I mentioned earlier that it was possible using the processor scheduling scheme that I outlined at the beginning of this entry to have a process that never gets a slice of the CPU. This can happen when there are always other processes at a higher priority that monopolize the processor's time. There's a story which may or may not be apocryphal about some sysadmins (system administrators - see the entry for July 4, 2002) decommisioning an old computer built by Honeywell and running the MULTICS operating system. Evidently the machine hadn't been shut down for several years. The story tells of a poor orphan process they found marooned on the process queue that had been waiting years for a chance at the CPU but was always outranked by other competing processes with higher priorities.

This can't happen with most modern operating systems as they look out for such processes, periodically raising the priority of low priority processes that haven't had a chance at the CPU and then subsequently lowering their priority once they've had a shot at the CPU. In this way, eventually even the lowest priority process will eventually get a chance to run.

As usual I got side tracked; it's not the first time that I went off on a tangent as a result of something that happened on my morning bus ride. I had wanted to think a little about a study that Jo had described to me concerning some scientists studying the connection between human emotions and facial expressions. It seems that these scientists discovered that if a subject is able to control his facial muscles so that his face takes on a particular facial expression typically associated with a given emotion, e.g., being sad, then in relatively short order the subject will also experience the associated emotion. In what seems like an odd reversal of cause and effect, the outward expression brings on the inward feeling. (The study that Jo read about was described in a story entitled "Annals of Pschology - The Naked Face" by Malcolm Gladwell published in The New Yorker, August 5, 2002, pages 38-49. For a discussion of the original study written by the scientists who did the study see Ekman, P., Levenson, R. W., and Friesen, W. V. (1983). Autonomic nervous system activity distinguishes among emotions. Science, 221, 1208-1210.)

As Jo described the study, I thought about how associations might be implemented in the brain and the possibility of them working in either direction similar to how the constraint propagation system worked that we looked at in the July 12, 2002) entry. It's intriguing to think about how the hardware influences the software in humans and how in building robots you might want to start by building the hardware and the let it guide you in the design of the software rather than the other way around. Start by thinking about what the hardware really "wants" to do, identify its natural harmonic motions, and then design software that takes advantage of these natural predilections. I'm rushing because the bus is rapidly approaching my stop; perhaps I'll return to this at some point in the future.