COMP 3000 2011 Week 6 Notes

Signals & Scheduling

Scheduling

The kernel takes control when an interrupt occurs, either software (e.g. system call) or hardware (e.g. keyboard input).

The main loop of an operating system is:

Application running in user mode
Interrupt
Enter supervisor mode
Jump to interrupt handler
Run interrupt handler
Housekeeping (this role has been greatly minimized over time to minimize scheduling links)
Scheduler ("What next?")
User mode continues with an application

Note that the applications in the first and last steps of the loop may be different depending on what the scheduler decides to do next.

Run Queue

The scheduler mainly deals with the run queue. The run queue is made up of things to schedule--these are processes and threads (execution contexts). In Linux the kernel translates this to task_structs (which are generally very large). The "catch" of the run queue though is it needs to decide what to do very quickly (we used to strive to do this in constant time, but have now moved up to log n time).

A slow scheduler is very undesirable as it would be running all the time and it's purely overhead--there would be no time for anything else. It is getting harder to schedule efficiently now though due to multiple cores. This is because, however many cores we have, we still have to do the same amount of work per core (e.g. if we had 16 cores, we would need to do 16 times the amount of work than if we only had 1 core).

Ready to Run Queue

The ready to run queue is made up of things that are ready to consume CPU cycles. This is relevant since not everything will be "ready to run" (i.e. their state is not ready to run).

Processes and thread states:

Running
Ready: the process is not running, but it could be
Blocked: if you give the process CPU cycles in this state, it would do nothing. The process is waiting for IPC (process thread) or I/O (network, disk, video etc.)

Types of Scheduling

There are several types of scheduling, the majority of these, however, are "best effort" scheduling. The "best effort" schedulers are fairness, priorities and fair share scheduling. Real time scheduling, however, is not based on "best effort", but rather that, it will only do something if it knows it can be done.

Fairness

Scheduling by fairness is only done when there is no other basis for a decision. It means that every process gets an equal share of resources (i.e. "round robin" scheduling). However, we do not want to use fair schedulers since, as the amount of tasks increase, the resources allocated to each task decreases. By using this method of scheduling, when there are too many tasks, every task dies. Due to this, each scheduler has values associated with it (value judgments) which brings us to priority based scheduling.

Priorities

Priority based scheduling is the class system incarnate within a computer--the main question with this type of scheduling is, "Who is more important?" For this type of scheduling, since the kernel itself does the scheduling, the kernel is given the highest priority (i.e. negative priorities are given to kernel tasks). After the kernel, the "next in line" is generally whoever is there unless the system admin decides to manually tweak the priorities.

Fair Share Scheduling

The focus of this type of scheduling is groups of processes. The scheduler will put processes in groups then allocate resources based on the needs of the groups, then allocating resources to individual processes.

Real Time

A real time scheduler is based on predictability, not speed. In contrast to the above "best effort" types of scheduling, real time scheduling will allocate resources in such a way that any promises made will be fulfilled, and if a task can't be fulfilled, no promise is made. In other words, a real time scheduler will not commit to a task unless it knows it can execute the task to a certain standard (i.e. it will either give you a good experience or no experience), whereas the "best effort" schedulers will give it a try, regardless of the quality of the experience.

The core of real time schedulers are resource reservation and deadlines. This type of scheduler is used for systems that, when there is a delay beyond a certain threshold, bad things happen (e.g. missile defense system). In other words, real word observation of time matters.

Soft Real Time vs. Hard Real Time

Hard real time cannot be used with a traditional OS kernel, as it would be too complicated to keep deadlines. Hard real time schedulers give absolute guarantees for deadlines. Soft real time, however, gives a general guarantee for deadlines (i.e. it will mostly reach its deadlines). Soft real time is mainly used in dealing with multimedia (i.e. graphics and sound), bumping these tasks to the front of the run queue.

Signals

Signals are a funny type of legacy IPC method. The CPU must be able to handle a signal at any time. Signals are a service provided by the kernel.