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, o temps que passa fins que el sistema respon i entrega la primera sortida a l'usuari en el cas d'activitat interactiva); 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.
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 de processos a punt 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.
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 cal 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 cal 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.
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 miniatura|Un grup de fils (les caixes verdes), amb una cua FIFO de tasques en espera (blau) i una cua de tasques completades (groc).|400x400px 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.