[WARNINGS] link-id not found - [fmiosacomparativestudypartikernellandchapter1bootup|1 link-id not found - [fmiosacomparativestudypartikernellandchapter3scheduling|3 link-id not found - [fmiosacomparativestudypartikernellandchapter5memorymanagement|5 link-id not found - [fmiosacomparativestudypartikernellandchapter7deadlocks|7 link-id not found - [fmiosacomparativestudypartiiuserlandchapter8iolayers|8 link-id not found - [fmiosacomparativestudypartiiuserlandchapter10environmentlayer|10
Intro (I 1 2 3 4 5 6 7) (II 8 9 10 11) (D) (C) (B
I)
h1. Chapter 6: Multiple Processors
(_"Foolproof systems don't take into account the ingenuity of fools." — Gene Brown. _)
Just when you thought it all sounded so easy, things start to get complex when you add multiple processors.
As computational tasks become larger, more complex, and more numerous, the demand for more computing power arises. With this, and the engineering limits of today, using more processors, or machines to do these tasks cooperatively is a common solution.
h2. 1. Multiprocessor O/S Configurations
On a multiprocessor machine, all of the processors share the same resources, such as memory and I/O devices. How these CPUs are managed varies according to the system's design. However, these methods fall under three general categories:
h4. 1. Each CPU Has Its Own O/S
This is perhaps the simplest of the three. Every CPU is running its own copy of the O/S with the memory divided among them. Therefore, each processor has its own execution table, process/thread table, memory manager, syscall handlers, etc. Although this successfully distributes tasks to multiple processors, there are some problems. First of all, if the process load for each CPU is unbalanced, then one CPU could be idle while another is working hard. This is a serious efficiency problem that could easily prevent the user from taking advantage of the multiprocessor system. Although memory could be dynamically assigned to different CPUs (in the case that one CPU has to handle some memory-intensive processes, for example), it is hard to do this during run time because pages cannot be shared between processors.
h4. 2. Master-Slave
This model puts the O/S, and all its tables, onto one master CPU and distributes processes to the other slave CPUs. This allows for shared memory and better balance of process load on the processors. However, as the number of slave CPUs grows, the demand on the master grows and it will eventually become a bottleneck.
h4. 3. Symmetric Multiprocessors (SMP)
With this model, there is also only one O/S and a common, shared memory. However, there is no bottleneck or process unbalance. All of the tables and other kernel info are shared. Also, each CPU may run in the kernel as well as in user space. As a CPU gets ready for a new process, it calls the common scheduler routines to assign it a new process from the common process tree. However, with all of this sharing of kernel structures, other problems arise. This leads into the next section.
h2. 2. Synchronizing CPUs and Lockouts
Let's assume a basic situation on an SMP machine where two CPUs want to call on the scheduler to assign them each a new thread to execute. Since executing a line of code is only a matter of changing the instruction pointer within the CPU and reading (only) from memory, executing shared memory can occur without any problems. However, when writing to shared memory, a type of synchronization is needed.
h3. Mutexes
Any kernel must provide methods for processes to have mutual exclusion (abbreviated to mutex), which means only one process is allowed access to a shared memory or service at a time. Mutexes are also intended to prevent race conditions that can happen in processes' critical region (Section 42)
h4. Semaphores
The primary tool for providing mutexes takes advantage of atomic actions. As mentioned in Chapter 4, an atomic action is a sequence of actions that cannot be interrupted. Semaphores are based off of the atomic actions @up()@ and @down()@. These commands increment and decrement a given counter (called the semaphore). If the semaphore is 0 then the @down()@ can't decrement anymore, so the thread calling it is blocked. It's not until an @up()@ is called on the same semaphore (thus incrementing it from 0 to 1) that the blocked thread is allowed to proceed (wakes up). Therefore, a process would start off their critical region with a @down( foo )@ and end it with an @up( foo )@.
h4. Spinlocks
Spinlocks are also used to lock out other processes from a shared resource. The concept behind these is that there is a common variable that keeps track of whether it is safe to enter the critical region. When a process on one processor is accessing this shared resource, the common variable is set, stating that the resource is occupied, thereby locking it. Therefore, when another process, from another processor, tries to access that same resource, it notices that the resource is locked. As that process waits for the lock to be released it loops, or spins, until the lock is released. This isn't always the best solution because the processor, for the second process, is kept unnecessarily busy looping while waiting for the resource. However, because of their simplicity, they are ideal for locking out short pieces of code that do not keep other processes waiting for long.
Commands in the scheduler are some of the functions that utilize a mutex. Although multiple processes (on multiple CPUs) are allowed to simultaneously execute the run-next function in the scheduler (since execution is a read-only action), they will eventually lock (or block) when they get to the part where they have to access the process table; this is the scheduler's critical region. Therefore, the first CPU to enter the critical region gets the lock while the other one must wait.
Some kernels handle mutual exclusion by locking the entire kernel and all its data. This isn't always the best option since some syscalls won't be using the same read/write data. For example, the IPC would not be accessing the process table. This is where sectional spinlocks come into place. These are locks that you place only on certain parts of the kernel data. For instance, there are locks for the page tables, IPC data structures, etc.
Locks, however, should still be used sparingly. In order to implement atomic instructions, some processors (such as the x86) lock the bus. This becomes a problem the more locks there are since every single mutex operation will lock the bus, hiccuping all the other CPUs (since the bus is what carries addresses and data, etc.).
One other possible problem that you must take into consideration is how to handle interrupts while locking within a critical region. These can cause major deadlocks, which are discussed in Chapter 7 Deadlocks.
h2. 3. Scheduling
There are three basic categories for multiprocessor scheduling.
h4. 1. Time Sharing
This isn't so much a modification as it is an inherent quality of the SMP model. With this, the run-tree is shared among all of the CPUs. Although this has its timesharing and load-balancing advantages, it can slow down with many processors. Every time a process accesses the scheduler to request a new process, the process table is locked. This could easily cause back ups with the more processors that are added to the machine: if there are 128 processors and 50 of them are waiting in line for a new process then that's a waste of processing resources!
Something to consider when writing a timesharing scheduler is a CPU's cache. Every CPU has its own cache, which is very close, fast, private, and easily accessible memory (i.e. no bus) that the CPU uses to store temporary data (holding recently used pages, etc). With this in mind, if processor 1 was running process A, then if it runs process A again soon there's a good chance that A's data is still in that processor's cache, thus improving performance. Therefore, implementing this will improve the efficiency of Time-Sharing scheduling. One possible method of implementation is using a type of two-level scheduling algorithm. With this, the top level consists of a CPU, and the lower level consists of all of the processes attached to that CPU. So, whenever a process is created, it is assigned to a CPU.
h4. 2. Space Sharing
Let's assume that a process has a group of threads and they're executed all at once. It is safe to say that these threads will probably have reasons to talk to one another, so having them run at the same time is a fairly intuitive jump. The space sharing takes these related threads and assigns one to each CPU. If a thread on one CPU blocks, then the CPU stops, or idles, until its thread is awakened. If its thread terminates, then the CPU is released to the pool of available processors that the scheduler can then assign to another group of related threads. The obvious drawback to this is the abundance of CPU idle time. Also, although many threads can run at once, the number of CPUs limits the number of simultaneous processes.
h4. 3. Gang Scheduling
This method aims to combine Time and Space sharing. Groups of related threads are run at the same time, each on a different CPU. Every group of threads, typically grouped by process, is given a set quantum which all of those threads are required to adhere to. If a thread blocks, its CPU idles until the end of the quantum. By keeping the timeslices uniform, the threads that are likely to talk to one another will stay in-sync and be running simultaneously. At the end of every timeslice a scheduling decision is made and the next-up group of threads is run.
h2. 4. O/S Comparisons
Below are some descriptions of methods of managing mulitprocessors used by various operating systems.
h3. Linux
Once again, this monolithic kernel takes radical performance hits trying to implement a particular functionality. Linux does use the SMP model. However, since the kernel has all of the drivers and services built into it, then there are a large number of locks that must be managed.
Linux also allows context switching when holding a lock. This is very deadlock-prone and requires special and complex programming to make up for it.
Because of all of the deadlock compensations as well as the shear amount of locks, Linux does not handle SMP well on machines with 16 or more processors.
h3. FMI/OS
FMI/OS took a lot of its ideas from Plan9 on this topic, as well. It uses the SMP model with the timesharing scheduling algorithm. Because of its fixed-time, O(1) scheduling, the possible scheduler bottleneck problem with numerous processors is solved easily.
Another interesting trait of FMI/OS's scheduling is its inherent affinity. When a thread blocks when sending a message to a server, the server is sent to the front of the list at its priority level, and so the odds of it being run next on that CPU are high. Also, if the server were to run, it gets the rest of the client's quantum on that CPU, a well as its own.
Other compensations FMI/OS makes for handling multiprocessor conditions are covered in the next chapter, Chapter 7 Deadlocks
(c)2006 Dimitri Hammond