Planificador de tasques

En informàtica, el planificador (en anglès, scheduler), és un component funcional molt important dels sistemes operatius multitasca i multiprocés i essencial en els sistemes operatius en temps real. El planificador assigna treball als recursos del sistema. El treball poden ser elements virtual com processos, fils d'execució o flux de dades, el treball és planificat i assignat a recursos hardware com per exemple processadors, enllaços de telecomunicacions, targetes d'expansió.

El planificador porta a terme la planificació l'activitat. Els planificadors usualment estan implementats per mantenir ocupats tots els recursos de l'ordinador (com en el balanç de càrrega), permeten que múltiples usuaris comparteixen els recursos del sistema de manera efectiva o per obtenir una qualitat de servei objectiva. La planificació és una part fonamental per la informàtica i una part intrínseca del model d'execució en un sistema informàtic. El concepte de planificació fa possible l'existència de sistemes multitasca amb una sola unitat de processament (CPU).

Objectius

Un planificador pot centrar-se en un o diversos objectius, com per exemple: maximitzar el throughput (la quantitat de treball completat per unitat de temps); minimitzar el temps d'espera (el temps des que el treball està llest per executar-se fins que comença la seva execució); minimitzar la latència o el temps de resposta (temps des que el treball està preparat fins que finalitza en el cas d'execució per lots,^[1]^[2]^[3] o temps que passa fins que el sistema respon i entrega la primera sortida a l'usuari en el cas d'activitat interactiva);^[4] o maximitzar la equitat (temps de CPU igual per a cada procés, o més generalment, temps apropiat segons la prioritat i la càrrega de treball per a cada procés). A la pràctica, aquests objectius habitualment entren en conflicte els uns amb els altres (per exemple rendiment en contra latència), per tant un planificador s'implementarà segons les qüestions comentades anteriorment, les necessitats i objectius dels usuaris.

En entorns en temps real, com els sistemes encastats pel control automàtic en la indústria (per exemple, robòtica), el planificador també ha de garantir que els processos s'executin en un temps acotat, això és vital per mantenir estable el sistema. Les tasques planificades també es poden distribuir a dispositius remots mitjançant una xarxa i administrar-se a través d'un back-end administratiu.

Tipus de planificadors del sistema operatiu

El planificador és un mòdul del sistema operatiu que selecciona els pròxims treballs que s'admetran en el sistema i el següent procés a executar. Els sistemes operatius poden presentar tres tipus diferents de planificadors: un planificador a llarg termini (també conegut com a planificador d'admissió o planificador d'alt nivell), un planificador a mitjà termini i un planificador de curt termini. Els noms succeeixen la freqüència relativa amb la qual realitzen les seves funcions.

Planificador de processos

El planificador de processos és una part del sistema operatiu que decideix quin procés s'executa en un determinat moment. Generalment, té la capacitat de parar un procés en execució, moure’l al final de la cua d'execució i iniciar un nou procés; a aquest planificador se'l coneix com a planificador preventiu, al contrari és un planificador cooperatiu.^[5]

Planificació a llarg termini

El planificador de llarg termini, o planificador d'admissió, decideix quins treballs o procesos s'admetran a la cua del sistema (memòria principal); és a dir, quan s'intentarà executar un programa, el planificador a llarg termini autoritza o retrasa l'admissió al conjunt de processos que s'estan executant actualment. Per la qual cosa, aquest planificador dicta quins processos s'executaran en un sistema i el grau de concurrència que s'admet en un determinat moment, si molts o pocs processos s'executen simultàniament i com la divisió entre la E/S intensiva i els processos que fan un ús intensiu de la CPU. El planificador de llarg termini és el responsable de controlar el grau de multiprogramació.

En general, la majoria de processos es poden descriure com a enllaços d'E/S o enllaçats amb CPU. Un procés vinculat a E/S és aquell que passa més temps fent E/S que del que gasta fent càlculs. En canvi, un procés lligat a la CPU genera rarament sol·licituds d'E/S, utilitzant més del seu temps fent càlculs.És important que un planificador a llarg termini seleccioni una bona combinació de processos vinculats a E/S i amb CPU. Si tots els processos estan vinculats a E / S, la cua llesta gairebé sempre serà buida i el planificador a curt termini no tindrà gaire a fer. D'altra banda, si tots els processos estan vinculats a la CPU, la cua d'espera d'E/S gairebé sempre serà buida, els dispositius es quedaran sense utilitzar i, de nou, el sistema es desequilibra. El sistema amb el millor rendiment tindrà, doncs, una combinació de processos vinculats a la CPU i E/S. En els sistemes operatius moderns, això s'utilitza per assegurar-se que els processos en temps real tinguin suficient temps de CPU per acabar les tasques.^[6]

La programació a llarg termini també és important en sistemes a gran escala com ara sistemes de processament per lots, clústers d'ordinadors, supercomputadors i granges de renderització.Per exemple, en sistemes concurrents, sovint es requereix la planificació dels processos interactius per evitar que es bloquegin per haver-se d'esperar els uns als altres. En aquests casos, el programari de planificació de treballs amb propòsits especials s'utilitza normalment per ajudar aquestes funcions, a més de qualsevol suport subjacent de planificació d'admissions en el sistema operatiu.

Planificació a mitjà termini

El planificador a mitjà termini elimina temporalment els processos de la memòria principal i els col·loca a la memòria secundària (com ara un disc dur) o viceversa, que comunament es sol anomenar "swapping out" o "swapping in" (no confondre amb "paging out” o “paging in”). El planificador a mitjà termini pot decidir canviar un procés per l'altre que fa temps que no està actiu, o un procés que té una prioritat baixa, o un procés que té moltes fallades de pàgina o un procés que ocupa una gran quantitat de memòria per alliberar la memòria principal per a altres processos, reactivant el procés més endavant quan hi hagi més memòria disponible o quan el procés s'ha desbloquejat i ja no espera cap recurs. [Stallings, 396] [Stallings, 370]

En molts sistemes actuals (els que admeten mapeig de l'espai d'adreces virtuals a l'emmagatzematge secundari que no sigui el fitxer swap), el planificador a mitjà termini pot exercir el paper del planificador a llarg termini, tractant els binaris com a “processos intercanviats” durant la seva execució. D'aquesta manera, quan es requereix un segment del binari es pot canviar a demanda o bé fent servir la tècnica “lazy loaded”. [Stallings, 394]

Planificació a curt termini

El planificador a curt termini (també conegut com a planificador de la CPU) decideix quin dels processos està en estat “ready” i que es troben a memoria es vol executar (assignant una CPU) després de rebre una interrupció del rellotge, una interrupció d'E/S, una trucada del sistema operatiu o qualsevol altra forma de senyal. Així, el planificador a curt termini pren les decisions de planificació molt més sovint que les planificadores a llarg termini o a mitjà termini. Una decisió de planificació haurà de prendre’s com a mínim després de cada període determinat de temps, i aquestes són molt curtes. Aquest planificador pot ser preventiu, implicant que és capaç d'eliminar els processos forçadament d'una CPU quan decideix assignar aquesta CPU a un altre procés, o no preventiu(també conegut com a "voluntari" o "co-operatiu"), en què el planificador no pot "forçar" els processos fora de la CPU.

Un planificador preventiu es basa en un temporitzador d'intervals programable que invoca un controlador d'interrupció que s'executa en mode kernel i implementa la funció de planificació.

Despatxador

Un altre component que participa en la funció de planificació de la CPU és el despatxador, que és el mòdul que dona el control de la CPU al procés seleccionat pel planificador a curt termini. Rep el control en mode kernel com a resultat d'una interrupció o una trucada del sistema. Les funcions d'un despatxador són les següents:

Canvi de context, en els quals el despatxador guarda l'estat (també conegut com a context) del procés o thread que abans s'estava executant; el despatxador llavors carrega l'estat inicial o prèviament desat del nou procés.
Canvi al mode d'usuari.
Saltant a la ubicació adequada al programa d'usuari per reiniciar aquest programa indicat pel seu nou estat

El despatxador ha de ser el més ràpid possible, ja que s'invoca durant cada canvi de procés. Durant els canvis de context, el processador està pràcticament en estat “idle” durant una fracció de temps, per la qual cosa s'han d'evitar els canvis de context innecessaris. El temps que triga el despatxador a aturar un procés i iniciar-ne un altre es coneix com a latència de despatx.^[6]^:155

Tipus de planificacions

Les disciplines de programació són algoritmes utilitzats per distribuir recursos entre les parts que els sol·liciten de forma simultània i asíncrona. Les disciplines de programació s'utilitzen en encaminadors (per gestionar el trànsit de paquets), així com en sistemes operatius (per compartir el temps de CPU entre fils d'execució i processos), unitats de disc (programació d'E / S), impressores (cua d'impressió), la majoria dels sistemes integrats, etc.

Els principals propòsits d'algorismes de planificació són minimitzar la inanició de recursos i garantir l'equitat entre les parts que utilitzen els recursos. La planificació tracta el problema de decidir a quina de les sol·licituds pendents es destinarán recursos. Hi ha molts algoritmes de planificació diferents. En aquesta secció, en presentem diversos.

A les xarxes d'informàtica amb transmissió de paquetes i altres multiplexions estadístiques, la noció d'un algoritme de planificació s'utilitza com a alternativa a la cola de les paquetes de dades per ordre d'arribada.

Els algorismes de programació del millor esforç són més simples, com l'operació per torns, la cola equitativa (un algoritme de programació equitativa màxim-mínim), la programació proporcionalment equitativa i el rendiment màxim. Si s'ofereix una qualitat de servei diferenciada o garantida, en contraposició a les comunicacions amb millor esforç, es pot utilitzar una cua justa ponderada.

First come, first served

Article principal: FIFO

First in, first out (FIFO), també conegut com a First come, first served (FCFS), és el algorisme de planificador de tasques més senzill. El FIFO ordena els el processos en l'orde que han arribat a la cua de llestos. S'utilitza molt en cues de tasques, com per exemple en la de la il·lustració de la secció.

Atès que els canvis de context només succeeix al finalitzar el procés i no es necessita una reorganització de la cua del procés, la sobrecàrrega de la planificació és mínima.
El rendiment pot ser baix, a causa que els processos llarg poden acaparar la CPU, el fet que fa que el processos curts esperen molt de temps (això es coneix com l'efecte convoy).
No produeix inanició de la CPU, perquè cada procés té l'oportunitat d'executar-se després d'un cert temps.
El turnaround, el temps d'espera i el temps de resposta depenen de l'ordre d'arribada dels processos i pot ser alt per les mateixes raons citades amb anterioritat.
No hi ha prioritzacions, per tant el sistema té problemes per conèixer quan finalitzaran els processos.
La falta de priorització implica que cada vegada que un procés es completa, no hi ha inanició. En un entorn on alguns processos poden no completar-se, la inanició es pot donar.
Està basat en cues.

Planificador amb prioritats

Article principal: Earliest deadline first scheduling

Vegeu també: Deadline-monotonic scheduling

Earliest Deadline First (EDF) també conegut com “menys temps per finalitzar” és un algoritme de planificació dinàmic utilitzat en sistemes operatius en temps real per introduir processos a una cua de prioritats. Quan succeeix un esdeveniment del planificador (finalitza una tasca, una nova tasca és alliberada, etc.), es busca a la cua el procés que està més pròxim a acabar la seva execució, aquest serà el següent a ser planificat per la seva execució.

Temps restant més curt primer

Article principal: Shortest remaining time

Similar a Shortest Job First (SJF). Amb aquesta estratègia el planificador organitza els processos amb l'estimació més baixa de processament per ser el següent a la cua. Això requereix tenir informació o estimacions sobre el temps que necessita un procés per completar-se.

Si un procés amb un temps d'execució més baix arriba mentre s'està executant un altre procés, el procés en execució s'interromp (conegut com a “preemption”), dividint aquest procés en dos blocs per a computar per separat. Això crea un excés de sobrecàrrega a causa del canvi de context addicional. El planificador ha de situar cada procés entrant a un lloc específic de la cua, creant també sobrecarrega addicional.
Aquest algorisme està dissenyat per aconseguir la màxima taxa de transferència efectiva (Throughtput) a la majoria d'escenaris.
El temps d'espera i de resposta augmenten a mesura que augmenten els requisits computacionals del procés. Com que el temps de resposta es basa en el temps d'espera i de processament, els processos més llargs es veuen afectats. Malgrat això el temps d'espera total és menor que en FIFO, ja que cap procés ha d'esperar a la finalització del procés més llarg.
No es presta atenció significativa a quan el programa ha d'acabar la seva execució, el programador només pot intentar fer processos amb execucions tan curtes com sigui possible.
La inanició és possible, especialment en un sistema molt ocupat amb molts processos petits executant-se.
Per utilitzar aquesta política hauríem de tenir dos processos amb prioritats diferents.

Planificació preventiva de prioritat fixa

Article principal: Fixed priority pre-emptive scheduling

El sistema operatiu assigna un rang de prioritat fixa a cada procés, i el planificador organitza els processos a la cua per entrar a execució en ordre segons aquesta prioritat. Els processos amb una prioritat més baixa s'interrompeix si arriba un procés amb una prioritat més alta.

La feina afegida no és mínima, però tampoc significativa.
La quantitat de processos finalitzats per unitat de temps no és millor que a la planificació FIFO.
Si la quantitat de rangs és limitada, és com si tinguéssim un conjunt de cues FIFO, una per a cada rang de prioritat. Els processos de menys prioritat només es planifiquen quan les cues de més prioritat estan buides.
El temps d'espera i de resposta depenen de la prioritat del procés. Els processos amb prioritat més alta tenen un temps d'espera i resposta més petits.
Els processos amb deadlines es poden assolir donant una prioritat més alta a aquests processos.
La inanició dels processos amb prioritat més baixa és possible amb un alt nombre de processos d'alta prioritat a les cues d'execució de la CPU.

Planificació Round Robin

Article principal: Round-robin scheduling

El planificador assigna una unitat fixa de temps per procés, i va rotant entre ells. si el procés finalitza dins d'aquesta unitat de temps acaba, si no, és replanifica després de donar una oportunitat a la resta de processos.

La planificació round robin suposa una gran despesa extra de rendiment, especialment si la unitat de temps configurada és petita.
Hi ha una finalització de treballs per unitat de temps balancejat entre FCFS/FIFO i SJF/SRTF. Els processos curts es completen més ràpidament que a la planificació FIFO, i els més llargs acaben més ràpid que a SJF.
Té una bona mitja respecte al temps de resposta, el temps d'espera depèn de la quantitat de processos, i no de la mida mitjana que tinguin els processos.
A causa dels alts temps d'espera, deadlines succeeixen rarament en un sistema Round Robin.
No existeix la inanició, ja que no es dona prioritat als processos. L'ordre en l'assignació d'unitats de temps es basa en el temps d'arribada del procés de forma similar a FIFO.
Si la unitat de temps és gran l'algorisme es converteix en un FCFS/FIFO i si es fa petit es converteix en un SJF/SRTF.

Planificació Multinivell

Article principal: Multilevel queue

Aquest tipus de planificació s'utilitza en situacions on els processos poden ser fàcilment agrupats en diferents grups. Per exemple, una divisió es podria fer entre processos de primer pla (interactius) i processos en segon pla (per lots). Aquests dos tipus de processos tenen diferents temps de resposta i per tant han de tenir diferents necessitats de planificació. És molt útil per a problemes de memòria compartida.

Planificació Work-conserving

Article principal: Work-conserving scheduler

Aquest planificador intenta tenir sempre ocupats els recursos planificats, si hi ha treballs llests per ser planificats. En contrapartida, un no conservatiu és un planificador, en alguns casos, pot deixar inactius els recursos programats encara que hi hagin treballs llests per ser planificats.

Planificació manual

Un mètode comú en sistemes encastats és planificar els treballs manualment. Això es pot fer per exemple de forma multiplexada en el temps. A vegades el kernel es divideix en tres o més parts: Planificació manual, planificació de nivell preventiu i planificació d'interrupció. Sovint els mètodes per planificar treballs són propietaris.

No té problemes d'inanició de recursos
Previsibilitat molt alta, permet la implementació de sistemes en temps real.
No hi ha gaire feina extra a realitzar.
Pot no ser òptim per a moltes aplicacions.
L'efectivitat és completament depenent de la implementació.

Problemes d'optimització de la planificació

Hi ha diversos problemes a l'hora de planificar on l'objectiu és decidir quin treball va a quina màquina en quin moment, de forma que es minimitzi el temps total que passa d'ençà que comença fins que finalitza el treball (makespan)

Job shop scheduling - Hi ha N treballs i M màquines idèntiques. Cada treball hauria de ser executat a una única màquina. Això generalment és considerat com un problema en línia.
Open-shop scheduling - Hi ha N treballs i M màquines diferents. Cada treball hauria de gastar temps a cada màquina, en ordre lliure.
Flow shop scheduling - Hi ha N treballs i M màquines diferents. Cada treball hauria de gastar temps a cada màquina, en un ordre predeterminat.

Triant un algorisme de planificació

Quan es dissenya un Sistema Operatiu (SO), un programador hauria de considerar quin algorisme de planificació donarà el millor rendiment segons l'ús que se li doni al sistema. No hi ha un algoritme de planificació que sigui millor que els altres, i molts SO utilitzen combinacions o extensions dels algoritmes de planificació que s'han vist amb anterioritat.

Per exemple, Windows NT/XP/Vista utilitza multilevel feedback queue, una combinació de planificació preventiva de prioritat fixa, round-robin, i FIFO. En aquest sistema, els fils poden incrementar o disminuir la seva prioritat depenent si estan llests (serviced already), o si han estat esperant per molt temps.

Cada nivell de prioritat està representat per la seva pròpia cua, on s'utilitza round robin a les cues d'alta priroitat i FIFO a les cues de baixa prioritat. En aquest sentit, el temps de resposta és més curt per la majoria de fils, i els fils curts però crítics finalitzen molt de pressa. Com que els fils només poden fer servir una unitat de temps de round robin a les cues d'alta prioritat, la inanició pot ser un problema pels fils d'alta prioritat que siguin llargs en execució.

Implementacions de planificadors de processos de sistemes operatius

L'algoritme usat pot ser de complexitat molt variada, des de algorismes senzills com un Round-Robin fins a altres que tenen en compte prioritat.

OS/360 i successors

IBM OS/360 estava disponible en tres planificadors diferents. Les diferències eren tals que les variants sovint es consideraven tres sistemes operatius diferents: L'opció Planificador seqüencial únic, també coneguda com a Programa de Control Primari (PCP) proporcionava l'execució seqüencial d'un sol flux de treballs. L'opció Planificador seqüencial múltiple, coneguda com a Multiprogramació amb un nombre Fixat de Tasques (MFT) proporcionava l'execució de diversos treballs concurrents. L'execució es regia per una prioritat que tenia un valor predeterminat per a cada flux o es podia sol·licitar per separat per a cada treball. La versió II de MFT va afegir subtasques (fils), que s'executaven amb una prioritat en funció de la tasca principal. Cada flux de treball defineix la quantitat màxima de memòria que podria fer servir qualsevol tasca d'aquest flux. L'opció Planificador de prioritat múltiple, o Multiprogramació amb un nombre Variable de Tasques (MVT), van incloure subtasques des del primer moment; cada treball demanava la prioritat i la memòria que requeria abans de l'execució. Les versions posteriors d'emmagatzematge virtual de MVS van afegir una funció de Gestor de càrrega de treball al planificador, que programa recursos de processador segons un esquema elaborat definit per la instal·lació.

Windows

Els sistemes MS-DOS i Microsoft Windows molt primerencs no eren multitasca i, per tant, no disposaven d'un planificador. Windows 3.1x utilitzava un planificador no preventiu, és a dir, que no va interrompre els programes. Va confiar en el programa per acabar o dir-li al sistema operatiu que no necessitava el processador perquè pogués passar a un altre procés. Això s'anomena generalment multitasca cooperativa. Windows 95 va introduir un rudimentari planificador preventiu; tanmateix, per al suport llegat va optar per deixar que les aplicacions de 16 bits funcionessin sense cap tipus de premissió.^[7]

Els sistemes operatius basats en Windows NT utilitzen una cua de comentaris de diversos nivells. Es defineixen 32 nivells de prioritat, de 0 a 31, i les prioritats de 0 a 15 són les prioritats "normals" i les prioritats 16 a 31 són prioritats en temps real suaus, que requereixen privilegis per assignar. 0 està reservat per al sistema operatiu. Els usuaris poden seleccionar 5 d'aquestes prioritats per assignar-les a una aplicació en execució des de l'aplicació de Task Manager o mitjançant API de gestió de fils. El nucli pot canviar el nivell de prioritat d'un fil en funció del seu ús d'E / S i CPU i de si és interactiu (és a dir, accepta i respon a les entrades dels humans), augmentant la prioritat de processos interactius i d'E / S i reduint el de processos enllaçats amb CPU, per augmentar la resposta de les aplicacions interactives.^[8] El planificador es va modificar a Windows Vista per utilitzar el registre comptador de cicles dels processadors moderns per fer un seguiment exacte de quants cicles de CPU ha executat un fil, en comptes d'utilitzar una rutina d'interrupció del temporitzador.^[9] Vista també utilitza un planificador de prioritats per a la cua d'E / S per tal que els desfragmentadors de disc i altres programes d'aquest tipus no interfereixin amb les operacions de primer pla.^[10]

Mac OS clàssic i macOS

Mac OS 9 utilitza la planificació cooperativa per a fils, on un procés controla diversos fils cooperatius i també proporciona una planificació preventiva per a tasques de multiprocessament. El nucli planifica tasques de multiprocessament mitjançant un algorisme de planificació preventiu. Tots els processos del Gestor de processos s'executen dins d'una tasca especial de multiprocessament, anomenada "blue task". Aquests processos es planifiquen de forma cooperativa, utilitzant un algorisme de planificació de Round-Robin; un procés cedeix el control del processador a un altre procés cridant explícitament a una funció de bloqueig com WaitNextEvent. Cada procés té la seva pròpia còpia del Gestor de fils que programa els fils d'aquest procés de forma cooperativa; un fil cedeix el control del processador a un altre fil cridant a YieldToAnyThread o a YieldToThread.^[11]

macOS utilitza una cua de retroalimentació multinivell, amb quatre bandes de prioritat per als fils: normal, d'alta prioritat del sistema, només mode del nucli i temps real.^[12] Els fils es programen de forma preventiva; macOS també admet fils programats de forma cooperativa en la seva implementació del Gestor de fils a Carbon.^[11]

AIX

A la versió 4 d'AIX hi ha tres valors possibles per a la política de programació de fils:

First In, First Out (FIFO): Un cop programat un fil amb aquesta política, s'executa fins que no sigui bloquejat, cedeix voluntàriament el control de la CPU o bé un fil de prioritat més alta es pot enviar. Només els fils de prioritat fixa poden tenir una política de programació FIFO.
Round Robin (RR): Aquest és similar al esquema de planificació AIX en la versió 3 basat en franges de temps de 10ms. Quan un fil RR té el control al final de la porció de temps, es mou al final de la cua dels fils despatxables de la seva prioritat. Només els fils de prioritat fixa poden tenir una política de programació de Round Robin.
ALTRES: Aquesta política la defineix POSIX1003.4a com a definida per la implementació. A la versió 4 d'AIX, aquesta política es defineix que és equivalent a RR, excepte que s'aplica als fils amb prioritat no fixa. La recalculació del valor de prioritat del fil en curs a cada interrupció del rellotge significa que un fil pot perdre el control perquè el seu valor prioritari ha augmentat per sobre del d'un altre fil enviable. Aquest és el comportament de la versió 3 d'AIX. Els fils són d'interès principal per a les aplicacions que actualment consten de diversos processos asíncrons. Aquestes aplicacions poden imposar una càrrega més lleugera al sistema si es converteixen en una estructura multifil.

L'AIX 5 implementa les següents polítiques de programació: FIFO, Round Robin i un Round Robin just. La política FIFO té tres implementacions diferents: FIFO, FIFO2 i FIFO3. La política de Round Robin s'anomena SCHED_RR a AIX, i la Round Robin just s'anomena SCHED_OTHER.^[13]

Linux

Linux 2.4

A Linux 2.4, es va utilitzar un planificador O(n) amb una cua de retroalimentació multinivell amb nivells de prioritat que van de 0 a 140; De 0 a 99 es reserven per a tasques en temps real i de 100 a 140 es consideren nivells de tasques nice. Per a tasques en temps real, el quàntum de temps per commutar els processos era d'aproximadament 200ms, i per a les tasques nice aproximadament de 10 ms. El planificador recorría la cua d'execució de tots els processos en estat Ready, deixant que els processos de màxima prioritat passessin primer i s'executessin per les seves franges de temps, un cop acabat el quantum de temps assignat es col·locaven en la cua de tasques caducades.

Quan la cua activa està buida, la cua caducada es converteix en la cua activa i viceversa.

Tanmateix, algunes distribucions Linux de l'empresa com SUSE Linux Enterprise Server van substituir aquest planificador per un backport del planificador O(1) al nucli Linux 2.4 utilitzat per la distribució.

Linux 2.6.0 to Linux 2.6.22

A les versions 2.6.0 a 2.6.22, el nucli feia servir un planificador O(1) desenvolupat per Ingo Molnár i molts d'altres desenvolupadors del nucli durant la fase de desenvolupament del Linux 2.5. Con Kolivas va desenvolupar conjunts de pegats que milloraven la interactivitat amb aquest planificador o, fins i tot, el va substituir pels seus propis planificadors.

Des de Linux 2.6.23

L'aportació de Con Kolivas, la més important, la seva implementació de "Planificació justa" anomenat "Rotating Staircase Deadline", va inspirar Ingo Molnár a desenvolupar el Planificador completament just com a reemplaçament del planificador O(1) anterior. Molnár va acreditar a Kolivas en l'anunci de la seva implementació.^[14] CFS és la primera implementació d'un planificador de processos just àmpliament utilitzat en un sistemes operatius de propòsit general.^[15]

El Planificador completament just (CFS) utilitza un algorisme de planificació clàssic ben estudiat anomenat fair queuing inventat originalment per a xarxes de paquets. Anteriorment fair queuing s'havia aplicat a la planificació de CPU sota el nom de planificació estricta. El planificador CFS té una complexitat de planificació d'O (log N), on N és el nombre de tasques en la cua d'execució. La selecció d'una tasca es pot fer en temps constant, però la reinserció d'una tasca després d'executar-la necessita operacions O (log N), i això és perquè la cua d'execució s'implementa com un arbre negre vermell.

El Brain Fuck Scheduler (BFS), també creat per Con Kolivas, és una alternativa a la CFS.

FreeBSD

FreeBSD utilitza una cua de retroalimentació multinivell amb prioritats d'entre 0 i 255. Els nivells de 0 a 63 estan reservats per a les interrupcions, de 64 a 127 per a la meitat superior del nucli, de 128 a 159 per a fils d'execució d'usuaris en temps real, de 160 a 223 per a fils d'execució d'usuaris que comparteixen el temps i de 224 a 255 per a fils d'execució d'usuaris inactius.

NetBSD

NetBSD utilitza una cua de retroalimentació multinivell amb prioritats que van des de 0 a 235. De 0 a 63 està reservat per als fils d'execució compartits en temps (predeterminats, política SCHED_OTHER), de 64 a 95 per als fils d'execució d'usuari que van entrar a l'espai del nucli, de 96 a 128 per als fils d'execució del nucli, de 128 a 191 per als fils d'execució en temps real dels usuaris (polítiques SCHED_FIFO i SCHED_RR) i de 192 a 223 per a interrupcions del programari.

Solaris

Solaris utilitza una cua de retroalimentació multinivell amb prioritats d'entre 0 i 169. Les prioritats de 0 a 59 es reserven per a fils d'execució compartits en temps, de 60 à 99 per a fils d'execució de sistema, de 100 a 159 per a fils d'execució en temps real i de 160 a 169 per a interrupcions de baixa prioritat. A diferència de Linux,^[16] quan un procés durant la seva execució agota el seu quàntum de temps, se li assigna una nova prioritat i es torna a col·locar a la cua. Solaris 9 va introduir dues classes de planificació noves, la classe de prioritat fixa i la classe de quota justa. Els fils d'execució amb la prioritat fixa tenen el mateix rang de prioritats que el de la classe de temps compartit, però les seves prioritats no s'ajusten dinàmicament. La classe de planificació justa utilitza les accions de CPU per prioritzar els fils d'execució per a les decisions de planificació.

Les accions de CPU indiquen el dret als recursos de la CPU que es poden fer servir per un conjunt de processos, que es coneixen col·lectivament com a projecte.^[6]

Resum


Sistema Operatiu	Preferencia	Algoritme
Amiga OS	Sí	Planificació round-robin amb prioritats
FreeBSD	Sí	Cua de retroalimentació multinivell
Linux kernel abans del 2.6.0	Sí	Cua de retroalimentació multinivell
Linux kernel 2.6.0–2.6.23	Sí	planificador O(1)
Linux kernel després del 2.6.23	Sí	El Planificador completament just
Mac OS clàssic pre-9	No	Planificador cooperatiu
Mac OS 9	Parcial	Planificador preventiu per a tasques de MP i cooperatiu per a processos i threads
macOS	Sí	Cua de retroalimentació multinivell
NetBSD	Sí	Cua de retroalimentació multinivell
Solaris	Sí	Cua de retroalimentació multinivell
Windows 3.1x	No	Planificador cooperatiu
Windows 95, 98, Me	Parcial	Planificador preventiu per a processos de 32 bits i cooperatiu per a processos de 16 bits
Windows NT (inclòs 2000, XP, Vista, 7, and Server)	Sí	Cua de retroalimentació multinivell

Vegeu també

Notes

↑ C. L., Liu; James W., Layland «Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment». Journal of the ACM. ACM, 20, 1, 1-1973, pàg. 46–61. DOI: 10.1145/321738.321743. «We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.»
↑ Kleinrock, Leonard. Queueing Systems, Vol. 2: Computer Applications. Wiley-Interscience, 1976, p. 171. ISBN 047149111X. «For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.»
↑ Feitelson, Dror G. Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press, 2015. ISBN 9781107078239 [Consulta: 17 octubre 2015]. «if we denote the time that a job waits in the queue by t_w, and the time it actually runs by t_r, then the response time is r = t_w + t_r.»
↑ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg. Operating System Concepts. 9. Wiley Publishing, 2012, p. 187. ISBN 978-0470128725. «In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.»
↑ Paul Krzyzanowski. «Process Scheduling: Who gets to run next?», 19-02-2014. [Consulta: 11 gener 2015].
↑ ^6,0 ^6,1 ^6,2 Operating System Concepts. 9. John Wiley & Sons, Inc., 2013. ISBN 978-1-118-06333-0.
↑ Early Windows a Wayback Machine (archive index)
↑ Sriram Krishnan. «A Tale of Two Schedulers Windows NT and Windows CE». Arxivat de l'original el 22 juliol 2012.
↑ «Windows Administration: Inside the Windows Vista Kernel: Part 1», 14-11-2016. [Consulta: 9 desembre 2016].
↑ [1]
↑ ^11,0 ^11,1 «Technical Note TN2028: Threading Architectures». [Consulta: 15 gener 2019].
↑ «Mach Scheduling and Thread Interfaces». [Consulta: 15 gener 2019].
↑ [2] Arxivat 2011-08-11 a Wayback Machine.
↑ «[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]». [Consulta: 13 abril 2007].
↑ ; Dan Baumberger; Scott Hahn«Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin». [Consulta: 9 desembre 2016].
↑ «Comparison of Solaris, Linux, and FreeBSD Kernels». Arxivat de l'original el 7 agost 2008.

Referències

Błażewicz, Jacek; Ecker, K.H.; Pesch, E.; Schmidt, G.; Weglarz, J. Scheduling computer and manufacturing processes. 2. Berlin [u.a.]: Springer, 2001. ISBN 3-540-41931-4.
Stallings, William. Operating Systems Internals and Design Principles (fourth edition). Prentice Hall, 2004. ISBN 0-13-031999-6.
Information on the Linux 2.6 O(1)-scheduler

[liu1973-1] C. L., Liu; James W., Layland «Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment». Journal of the ACM. ACM, 20, 1, 1-1973, pàg. 46–61. DOI: 10.1145/321738.321743. «We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.»

[kleinrock1976-2] Kleinrock, Leonard. Queueing Systems, Vol. 2: Computer Applications. Wiley-Interscience, 1976, p. 171. ISBN 047149111X. «For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.»

[feitelson2014-3] Feitelson, Dror G. Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press, 2015. ISBN 9781107078239 [Consulta: 17 octubre 2015]. «if we denote the time that a job waits in the queue by t_w, and the time it actually runs by t_r, then the response time is r = t_w + t_r.»

[silberschatz2012-4] Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg. Operating System Concepts. 9. Wiley Publishing, 2012, p. 187. ISBN 978-0470128725. «In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.»

[5] Paul Krzyzanowski. «Process Scheduling: Who gets to run next?», 19-02-2014. [Consulta: 11 gener 2015].

[galvin-6] 6,0 ^6,1 ^6,2 Operating System Concepts. 9. John Wiley & Sons, Inc., 2013. ISBN 978-1-118-06333-0.

[7] Early Windows a Wayback Machine (archive index)

[8] Sriram Krishnan. «A Tale of Two Schedulers Windows NT and Windows CE». Arxivat de l'original el 22 juliol 2012.

[9] «Windows Administration: Inside the Windows Vista Kernel: Part 1», 14-11-2016. [Consulta: 9 desembre 2016].

[10] [1]

[appletn2028-11] 11,0 ^11,1 «Technical Note TN2028: Threading Architectures». [Consulta: 15 gener 2019].

[12] «Mach Scheduling and Thread Interfaces». [Consulta: 15 gener 2019].

[13] [2] Arxivat 2011-08-11 a Wayback Machine.

[14] «[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]». [Consulta: 13 abril 2007].

[dwrr-15] ; Dan Baumberger; Scott Hahn«Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin». [Consulta: 9 desembre 2016].

[opensolaris-queue2-16] «Comparison of Solaris, Linux, and FreeBSD Kernels». Arxivat de l'original el 7 agost 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]