Multiprocessor Scheduling

In computer science, multiprocessor scheduling is an NP-Complete optimization problem. The problem statement is: "Given a set J of jobs where job j_i has length l_i and a number of processors m_i, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.

• Will consider only shared memory multiprocessor

Real Time Scheduling

A multitasking operating system intended for real-time applications. Such applications include embedded systems (programmable thermostats, household appliance controllers), industrial robots, spacecraft, industrial control (see SCADA), and scientific research equipment.
A RTOS facilitates the creation of a real-time system, but does not guarantee the final result will be real-time; this requires correct development of the software. An RTOS does not necessarily have high throughput; rather, an RTOS provides facilities which, if used properly, guarantee deadlines can be met generally or deterministically (known as soft or hard real-time, respectively). An RTOS will typically use specialized scheduling algorithms in order to provide the real-time developer with the tools necessary to produce deterministic behavior in the final system. An RTOS is valued more for how quickly and/or predictably it can respond to a particular event than for the amount of work it can perform over a given period of time. Key factors in an RTOS are therefore a minimal interrupt latency and a minimal thread switching latency.
An early example of a large-scale real-time operating system was Transaction Processing Facility developed by American Airlines and IBM for the Sabre Airline Reservations System.

Real-Time Review

• Real time is not just “real fast”
  Real time means that correctness of result depends on both functional correctness and time that the result is delivered
  
• Soft real time
  Utility degrades with distance from deadline
  
• Hard real time
  System fails if deadline window is missed
  
• Firm real time
  Result has no utility outside deadline window, but system can withstand a few missed results

Type of Real-Time Scheduling

• Dynamic vs. Static
  Dynamic schedule computed at run-time based on tasks really executing
  Static schedule done at compile time for all possible tasks
  
• Preemptive permits one task to preempt another one of lower priority
  

• Thread Scheduling

The thread of a parent process forks a child process. The child process inherits the scheduling policy and priority of the parent process. As with the parent thread, it is the child thread whose scheduling policy and priority will be used.

The following figure illustates the flow of creation.

Figure 1-35 Inheritance of Scheduling policy and priority

• Each thread in a process is independently scheduled.
  
• Each thread contains its own scheduling policy and priority
  
• Thread scheduling policies and priorities may be assigned before a thread is created (in the threads attributes object) or set dynamically while a thread is running.
  
• Each thread may be bound directly to a CPU.
  
• Each thread may be suspended (and later resumed) by any thread within the process.

The following scheduling attributes may be set in the threads attribute object. The newly created thread will contain these scheduling attributes:

• contentionscope
  PTHREAD_SCOPE_SYSTEM specifies a bound (1 x 1, kernel-spacel) thread. When a bound thread is created, both a user thread and a kernel-scheduled entity are created.
  PTHREAD_SCOPE_PROCESS will specify an unbound (M x N, combination user- and kernel-space) thread. (Note, HP-UX release 10.30 does not support unbound threads.)
  
• inheritsched
  PTHREAD_INHERIT_SCHED specifies that the created thread will inherit its scheduling values from the creating thread, instead of from the threads attribute object.
  PTHREAD_EXPLICIT_SCHED specifies that the created thread will get its scheduling values from the threads attribute object.
  
• schedpolicy
  The scheduling policy of the newly created thread
  
• schedparam
  The scheduling parameter (priority) of the newly created thread.

Different CPU Scheduling Algorithms

• Treats ready queue as FIFO.

• Simple, but typically long/varying waiting time.

Shortest Job First (SJF)

• Give CPU to the process with the shortest next burst

• If equal, use FCFS

• Better name: shortest next cpu burst first

Round-Robin (RR)

• FCFS with Preemption

• Time quantum (or time slice)

• Ready Queue treated as circular queue

Shortest Remaining Time (SRT)

• Preemptive version of shortest process next policy

• Must estimate processing time