In the Mach operating system, an application or a task consist of several threads. A thread is the smallest independent unit of execution and scheduling in Mach. In the Mach operating system, all the processors of a multiprocessor are grouped in disjoint sets, called processor sets.

The processes in a processor set are assigned a subset of threads for execution. These executions are priority scheduling to execute the threads assigned to their processor set. Threads can have priority ranging from 0 to 31, where 0 and 31 are the lowest and the highest priorities respectively.

Each processor set has an array of 32 ready queues. one queue to store ready threads of each priority. When threads with priority 1 becomes ready it is appended to ith queue. In addition, every processor has a local ready queue that consists of the threads that must be executed only by the processor. Clearly, it is two level priority scheduling, all the threads in the local queue have priority over all the threads in the global queue and there are also priorities inside each of these two queues.

When a processor becomes idle, it selects a thread for execution in the following manner. If the local ready queue of the processor is nonempty, it selects the highest priority thread for execution. Otherwise, it selects the highest priority thread from the global ready queues for execution. If both the queue (local and global) is empty, the processor executes a special idle thread until a thread becomes ready.

When a thread runs out of its time-slice at a processor. It is preempted only if an equal or higher priority ready thread is present. Otherwise, the thread receives another time-slice at the processor. The length of the time-slice is variable and depends upon a number of ready threads. The highest the number of ready threads, the shorter the time-slice

Hints in the MACH Operating system

The scheduler in the MAC OS uses the concepts of hints to effectively schedule a process or task that are believed to communicate with each other. A user may have application specific information that may help the operating system make intelligent scheduling decisions. A hint is an information in coded form, which is supplied by the user at the time of task submission to the system. Hints essentially help modulate priority and determine the timing of the execution of threads such that communication and synchronization are efficiently made between the threads.

Scheduling information specific to an application (such as senders and receivers of messages, processes synchronizing through a rendezvous, etc.) can be advantageously used to effectively carry out communication and synchronization among threads. Sometimes a hint can be a mere guess and sometimes it can be known accurately, depending on the deterministic nature of an application.

The MAC OS supports two classes

Discouragement Hints:

A discouragement hint allows a scheduler to delay execution of a task. It indicates that the current thread should not be run at present. Discouragement hint can be soft, strong or absolute. A mild hint suggests that the thread should relinquish the processor to some other thread if possible. A strong hint suggests that the thread should not only relinquish the processor but that it should also suppress it’s priority temporarily. An absolute hint blocks a thread for a specific period.

Discouragement hints can be effectively used to schedule threads in an application. E.g. Discouragement hints can be used to optimize the performance of an application that performs synchronization through shared variables. When one thread holds the lock on a shared variable, other threads that are competing for the same lock can reduce the wastage of resources by delaying their execution using discouragement hints.

Handsoff Hints:

The Handsoff scheduling indicates that a specific thread should be run instead of the currently executing thread. A handsoff hint “Hands off” the processor to the specific thread, bypassing the scheduler. Handsoff scheduling may designate a thread within the same task or within a different task that should run next.

One excellent of handsoff hints is the priority inversion problem, where a low priority thread holds a resource that is needed by high priority threads. In such situations, high priority thread can hand processor off to the low priority thread. For example, a thread that is waiting for a semaphore to open should hand off processor to the thread that holds semaphore.