real-time scheduler

The real-time scheduler (Scheduler/RealTime../ns-2/scheduler.cc) attempts to synchronize the execution of events with real-time. It is currently implemented as a subclass of the list scheduler. The real-time capability in ns is still under development, but is used to introduce an ns simulated network into a real-world topology to experiment with easily-configured network topologies, cross-traffic, etc. This only works for relatively slow network traffic data rates, as the simulator must be able to keep pace with the real-world packet arrival rate, and this synchronization is not presently enforced.

Multi-processor scheduling

*Will consider only shared memory multiprocessor

*Salient features:
-One or more caches: cache affinity is important
-Semaphores/locks typically implemented as spin-locks: preemption during critical sections

thread scheduler


thread scheduler, part of the OS (usually) that is responsible for sharing the available CPUs out between the various threads. How exactly the scheduler works depends on the individual platform, but various modern operating systems (notably Windows and Linux) use largely similar techniques that we'll describe here. We'll also mention some key varitions between the platforms.

Note that we'll continue to talk about a single thread scheduler. On multiprocessor systems, there is generally some kind of scheduler per processor, which then need to be coordinated in some way. (On some systems, switching on different processors is staggered to avoid contention on shared scheduling tables.) Unless otherwise specified, we'll use the term thread scheduler to refer to this overall system of coordinated per-CPU schedulers.

Across platforms, thread scheduling1 tends to be based on at least the following criteria:

****a priority, or in fact usually multiple "priority" settings that we'll discuss below;

****a quantum, or number of allocated timeslices of CPU, which essentially determines the amount of CPU time a thread is allotted before it is forced to yield the CPU to another thread of the same or lower priority (the system will keep track of the remaining quantum at any given time, plus its default quantum, which could depend on thread type and/or system configuration);

****a state, notably "runnable" vs "waiting";

****metrics about the behaviour of threads, such as recent CPU usage or the time since it last ran (i.e. had a share of CPU), or the fact that it has "just received an event it was waiting for".

Most systems use what we might dub priority-based round-robin scheduling to some extent. The general principles are:

****a thread of higher priority (which is a function of base and local priorities) will preempt a thread of lower priority;

****otherwise, threads of equal priority will essentially take turns at getting an allocated slice or quantum of CPU;

****there are a few extra "tweaks" to make things work

CPU SCHEDULING

CPU Scheduling

CPU and I/O Burst Cycle

• The execution of a process consists of a cycle of CPU execution and I/O wait.

A process begins with a CPU burst, followed by an I/O burst, followed by another CPU burst and so on. The last CPU burst will end will a system request to terminate the execution.

• The CPU burst durations vary from process to process and computer to computer.

An I/O bound program has many very short CPU bursts.

A CPU bound program might have a few very long CPU bursts.

Types of Scheduling

The key to the multiprogramming is scheduling. There are four types of scheduling that an OS has to perform. These are:

• Long Term scheduling

>>>The long term scheduling determines which programs are admitted to the system for processing. Thus, it controls the level of multiprogramming.

>>>Once admitted, a job or a user program becomes a process and is added to the queue for the short term scheduling (in some cases added to a queue for medium term scheduling).

>>>Long term scheduling is performed when a new process is created.

>>>The criteria used for long-term scheduling may include first-come-first serve, priority, expected execution time, and I/O requirements.

• Medium-Term Scheduling

>>>The medium-term scheduling is a part of swapping function. This is a decision to add a process to those that are at least partially in main memory and therefore available for execution.

>>>The swapping-in decision is made on the need to manage the degree of multiprogramming and the memory requirements of the swapped-out process.

>>>Short-Term Scheduling

>>>A decision of which ready process to execute next is made in short-term scheduling.

>>>I/O Scheduling

>>>The decision as to which process’s pending I/O requests shall be handled by the available I/O device is made in I/O scheduling.

CPU Scheduler

• Whenever, the CPU becomes idle, the OS must select one of the processes in the ready-queue to be executed.

The selection process is carried out the short-term scheduler or CPU scheduler. The CPU scheduler selects a process from the ready queue and allocates the CPU to that process.

• CPU scheduling decisions may take place when a process:

1.The running process changes from running to waiting state (current CPU burst of that process is over).

2.The running process terminates

3. A waiting process becomes ready (new CPU burst of that process begins)

4. The current process switches from running to ready stat (e.g. because of timer interrupt).

• Scheduling under 1 and 2 is nonpreemptive.

Once a process is in the running state, it will continue until it terminates or blocks itself.

• Scheduling under 1 and 2 is preemptive.

Currently running process may be interrupted and moved to the Ready state by OS.

Allows for better service since any one process cannot monopolize the processor for very long

Dispatcher

• Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:

Switching context

Switching to user mode

Jumping to the proper location in the user program to restart that program

• Dispatch latency – time it takes for the dispatcher to stop one process and start another running.