Scheduling (computing)

A process scheduler ( scheduler = scheduler; schedule for the English "Schedule" ) is an arbitration logic that governs the temporal execution of multiple processes in operating systems. Process scheduler can roughly in interrupting ( preemptively ) and non-disruptive ( non pre-emptive, also called cooperative) distributed. Not interrupting Scheduler leave a process after the CPU has been allocated to him once, run until this releases it of your own accord, or until it blocks. Share Breaking the CPU scheduler from the beginning only for a certain period of time and to withdraw from the process then this again. Furthermore, a distinction between " work- conserving " and "non- work- conserving " strategies is possible. A scheduler strategy is working "work- conserving " when switching between processes takes only a negligible time. One can distinguish different systems, into which each have different demands on the scheduler:

In batch systems, the scheduler looks very simple from: Incoming jobs are put into a queue and every time a job is processed, the next from the queue to it ( queue manager ) comes.

Interactive systems have different requirements: The user values ​​short response time. If he, for example, in a text editor makes a keyboard input, the text should appear immediately.

In real-time systems there are for each job a time limit up to which the task must be completed.

Typical desktop PCs are interactive systems that sometimes processes can run as so-called background processes with lower priority.

Objectives

The allocation of the CPU to the process should be the best possible, although different objectives can be pursued (depending on the system running ):

Generally

  • Fairness: No process should have to wait unreasonably long, while another is preferred.
  • Balance: The processes should be allocated in a way the CPU that other resources such as disk, network interface, inter alia, are busy.
  • Compliance with system rules

Batch processing systems

  • CPU Utilization: The CPU should be busy at all times. It should not happen that the CPU is idle, just because a process is waiting for data from the hard disk.
  • Throughput: The number of completed tasks per unit of time should be maximized. This results in a strategy similar to the load, but viewed over the actual result.
  • Short turnaround time ( cycle time ), the time elapsing from the arrival of a process up to its full completion should be minimized.

Interactive Systems ( Dialogue Systems )

  • Fast Response Times: The user ( or other systems ) waiting times should be minimized. Processes that require interaction with the user, thus should be preferred over those that can take place in the background.
  • Proportionality: The response times of various processes should meet the user's expectations. , Processes (such as the closing of an application ), as viewed by the user simple, this should also be carried out quickly.

Real-Time Systems

  • Comply with deadlines
  • Predictability Important for multimedia applications ( otherwise eg deterioration in sound quality threatened ) or safety-critical applications such as control units for airbags, Cruise control in motor vehicles, or automatic pilots for aircraft.

Strategies

The biggest problem of the scheduler is the fact that the resources needed for each process are not known in advance. There was therefore generally not create optimal planning, but the scheduler must react dynamically to changing requirements. It may be used (depending on the scheduler) different allocation strategies. Among other things:

  • First In - First Out ( FIFO), First -Come First-Served ( FCFS ): This all processes are handled in the order they are received. A reallocation of processes takes place only when the current process starts to wait or its execution is terminated. This strategy achieves a good load with respect to the CPU, but not with respect to resources that may require a longer time for a request, such as Ein-/Ausgabe or mass storage. For multi-user systems, the strategy beyond is very useful, since individual users so if necessary (ie, for complex processes of other users ) ruled out for a long time.
  • Shortest Job Next ( SJN ), Shortest Job First ( SJF ), Shortest Processing Time ( SPT): a further method, which is not suitable for multi-user systems. It can be used in cases where the computation time required for individual tasks from empirical values ​​can be well predicted. A disadvantage is that large processes may never get assigned to the CPU when jump the queue always shorter jobs. Can processes be interrupted so that a process change is performed when a newly arrived process a shorter execution time than the currently running process, this is called Shortest - Remaining- Time ( SRT) or Shortest - Remaining- Processing -Time ( SRPT ).
  • Earliest Due Date ( EDD): In this strategy, the processes are executed first, which have the smallest deadline. Prerequisite for this are static deadlines and simultaneous arrival of independent tasks. This non-disruptive method is ideal to minimize the maximum lateness. If processes can be interrupted is called a date -dependent scheduling, planning periods or after the Earliest Deadline First ( EDF ). This strategy is mainly found in real-time systems, since it is thereby possible to guarantee a defined response time for certain processes.
  • Priority Scheduling: In this strategy, each process is assigned a priority. The processing is then carried out in order of priority. Rate Monotonic Scheduling ( RMS): The priority is calculated from the period length (processes with shorter periods have higher priority).
  • Deadline Monotonic Scheduling ( DMS): The priority is calculated from the relative deadline (processes with larger deadlines have higher priority).
  • You can also give several processes have the same priority, they are executed in the input sequence, or alternated with a subordinate time slicing within the same priority (for example, multilevel feedback queue scheduling or Shortest Elapsed Time ( SET) )
  • The priorities can also be dynamic, where the priority of a process increases with time, so that low priority processes will eventually be edited and not constantly displaced by higher-priority processes.
  • Round robin, time slice method: A process, the CPU for a certain ( short ) period of time will be allocated. Thereafter, the process is again queued in the back of the queue. If the individual periods vary in size, it is called Weighted Round Robin ( WRR )

Scheduling method

Arbiter (electronics) Response time (technology) Fair-Share-Scheduling Andrew S. Tanenbaum
663365
de