| Previous | Table of Contents | Next |
The method used to synchronize the execution of tasks as well as to communicate between tasks is based on Dijkstra’s semaphore.2 In 1968, Dijkstra proposed a primitive function to synchronize the execution of processes in a multiprogramming operating system. Synchronization is the capability of one task to pause and wait until another task has performed an operation. A semaphore provides a mechanism to allow a task to wait.
2E. W. Dijkstra, “The Structure of ‘THE’ Multiprogramming System,” Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341–346.
The original semaphore has a counter and a waiting list. Two operations (instructions) are defined. The V operator increments the value of the counter by one. The P operator tests the value of the counter; if the value is greater than zero, the P operator decrements the value of the counter by one and lets the next instruction in the instruction stream execute. If the counter value is not greater than zero, the P operator waits until the value becomes greater than zero before it completes its operation and allows the next instruction to execute. The waiting comes about when the P operator is executed and the counter is not greater than zero. In this case, the task that executed the P operator waits until some other task increments the counter with a V operator. This allows tasks to be synchronized.
In many situations, it is desirable to exchange some information, or a message, as a part of this synchronization operation. The AS/400 defines a send/receive queue (SRQ) to support synchronization and message passing. An SRQ is a data structure in memory that is used as a “mailbox” for messages sent from one task to another.
When a running task executes a SEND MESSAGE operation, another data structure called a send/receive message (SRM) is enqueued to an SRQ associated with some other task. This SRQ is the mailbox for the other task. The SRM contains the message the running task wishes to send to the other task. When a running task wants to obtain a message from an SRQ (its mailbox), it does so by executing a RECEIVE MESSAGE operation. If no message is available, the task has the option to wait for the message. If the task chooses to wait, the TDE for the running task is dequeued from the TDQ and enqueued to a wait list that is part of each SRQ. The task dispatcher is then invoked to select the highest priority, ready task and make it the running task.
At some later time, another running task executes a SEND MESSAGE operation to the SRQ. If a TDE is waiting for the message, it is dequeued from the SRQ and enqueued on the TDQ in priority sequence. If the newly enqueued TDE has higher priority than the running TDE, the running task is preempted. If more than one TDE is waiting, a bit in the header of the SRQ indicates whether all waiters should be awakened or just the first one.
Any task whose TDE is enqueued to an SRQ is, by definition, in the wait state. Figure 9.3 shows the migration of TDEs and how the state of the task is determined by the location of its TDE.
)
Figure 9.3 Task Dispatching Element Migration
Not shown in the figure are the other data structures that can have TDEs enqueued. One of these is the send/receive counter (SRC). An SRC has no message passing, so it is similar to the original semaphore. SLIC provides operations of SEND COUNT and RECEIVE COUNT to provide synchronization between tasks where no messages need to be exchanged.
Some readers who are familiar with the SNDPGMMSG (Send Program Message) and RCVMSG (Receive Message) commands at OS/400 may be wondering whether they are related to the operations used by the tasking structure in SLIC. The answer is, “Yes, there is a very close relationship.” The exact format of SRMs, SRQs, and SRCs is designed for the tasking functions being performed, but the operations of enqueuing and dequeuing the messages are fundamentally the same throughout the system. SLIC is responsible for providing all these functions.
The discussion in the preceding section assumed only a single processor and, therefore, only one running task. In contrast, a multiprocessor system potentially has many running tasks. The task-dispatching mechanism includes the support for multiprocessors. Although much of this function was included in the original System/38, it was never used in that system. It wasn’t until 1990 that multiprocessing was introduced and first used on the AS/400. Some of that original support for multiprocessing still has not been fully exploited in the AS/400, but it is available for future multiprocessor implementations.
Earlier, we saw that a symmetric multiprocessor (SMP) system allows the operating system to run on any free processor or on all processors simultaneously, sharing the memory among them. This is exactly how n-way processing operates on an AS/400. Any component of the operating system, including the task dispatcher, can run on any or all processors in the system.
The task dispatcher in an n-way system provides automatic workload balancing among the processors without requiring software changes from a single processor design. Because the memory is shared, the task dispatcher running on any processor has access to all the queues, including the TDQ. The effects of the task dispatcher, however, are not limited to the processor on which it runs. The task dispatcher running on one processor can cause a task switch to occur on another processor.
With multiple processors, we have multiple running tasks — one for each processor. Simplistically, we would just dispatch the n top TDEs on the TDQ. These n tasks do have the highest priorities of the ready tasks. But while this simple approach seems to be the best choice, it often isn’t.
Suppose we have two tasks, A and B, executing on processors 1 and 2 in a two-processor system. Suppose further that a waiting task C, with a higher priority than task A but lower than task B, comes out of the wait state. Its TDE will be enqueued on the TDQ just above the TDE for task A. The task dispatcher causes a task switch to occur on processor 1 to make task C a running task. Now suppose task B on processor 2 either completes or goes into a wait state. Task A is the highest priority ready task and should be dispatched on processor 2 — but this may not be the best choice.
| Previous | Table of Contents | Next |
){kind=link}