Scheduling (computing): Difference between revisions

Revision as of 17:44, 30 January 2024

Revision as of 18:12, 30 January 2024

Line 72:

=={{Anchor|SCHEDULER}}Types of operating system schedulers==

{{See also|Network scheduler|I/O scheduling|Jobjob scheduler}}

The scheduler is an operating system module that selects the next jobs to be admitted into the system and the next process to run. Operating systems may feature up to three distinct scheduler types: a ''long-term scheduler'' (also known as an admission scheduler or high-level scheduler), a ''mid-term or medium-term scheduler'', and a ''short-term scheduler''. The names suggest the relative frequency with which their functions are performed.

Line 167:

* To use this policy we should have at least two processes of different priority

===Fixed -priority pre-emptive scheduling===

{{Main|Fixed -priority pre-emptive scheduling}}

The operating system assigns a fixed -priority rank to every process, and the scheduler arranges the processes in the ready queue in order of their priority. Lower-priority processes get interrupted by incoming higher-priority processes.

* Overhead is not minimal, nor is it significant.

* FPPS has no particular advantage in terms of throughput over FIFO scheduling.

Line 184:

* RR scheduling involves extensive overhead, especially with a small time unit.

* Balanced throughput between FCFS/ FIFO and SJF/SRTF, shorter jobs are completed faster than in FIFO and longer processes are completed faster than in SJF.

* Good average response time, waiting time is dependent on number of processes, and not average process length.

* Because of high waiting times, deadlines are rarely met in a pure RR system.

* Starvation can never occur, since no priority is given. Order of time unit allocation is based upon process arrival time, similar to FIFO.

* If Time-Slice is large it becomes FCFS /FIFO or if it is short then it becomes SJF/SRTF.

===Multilevel queue scheduling===

Line 202:

===Scheduling optimization problems===

There are several scheduling problems in which the goal is to decide which job goes to which station at what time, such that the total [[makespan]] is minimized:

* [[Job -shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} identical stations. Each job should be executed on a single machine. This is usually regarded as an online problem.

* [[Open-shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} different stations. Each job should spend some time at each station, in a free order.

* [[Flow-shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} different stations. Each job should spend some time at each station, in a pre-determined order.

Line 291:

===Solaris===

[[Solaris (operating system)|Solaris]] uses a multilevel feedback queue with priorities ranging between 0 and 169. Priorities 0&ndash;59 are reserved for time-shared threads, 60&ndash;99 for system threads, 100&ndash;159 for real-time threads, and 160&ndash;169 for low priority interrupts. Unlike Linux,<ref name="opensolaris-queue"/> when a process is done using its time quantum, it is given a new priority and put back in the queue. Solaris&nbsp;9 introduced two new scheduling classes, namely fixed -priority class and fair share class. The threads with fixed priority have the same priority range as that of the time-sharing class, but their priorities are not dynamically adjusted. The fair scheduling class uses CPU ''shares'' to prioritize threads for scheduling decisions. CPU shares indicate the entitlement to CPU resources. They are allocated to a set of processes, which are collectively known as a project.<ref name="Galvin"/>

===Summary===

Line 358:

==See also==

{{Div col|colwidth=20em}}

* [[Activity selection problem]]

Line 391 ⟶ 390:

==Further reading==

*[httphttps://pages.cs.wisc.edu/~remzi/OSTEP/ Operating Systems: Three Easy Pieces] by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapters: [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf Scheduling: Introduction] [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf Multi-level Feedback Queue] [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-lottery.pdf Proportional-share Scheduling] [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-multi.pdf Multiprocessor Scheduling]

*[http://www.cs.sunysb.edu/~algorith/files/scheduling.shtml Brief discussion of Job Scheduling algorithms]

*[https://web.archive.org/web/20060613130106/http://oreilly.com/catalog/linuxkernel/chapter/ch10.html Understanding the Linux Kernel: Chapter 10 Process Scheduling]

Line 399 ⟶ 398:

*Peter Brucker, Sigrid Knust. Complexity results for scheduling problems [http://www.mathematik.uni-osnabrueck.de/research/OR/class/]

*[http://rtime.felk.cvut.cz/scheduling-toolbox TORSCHE Scheduling Toolbox for Matlab] is a toolbox of scheduling and graph algorithms.

*[httphttps://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6226795 A survey on cellular networks packet scheduling]

*[https://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/43438.pdf Large-scale cluster management at Google with Borg]