Planificació de Processos i Sincronització en SO

Torn circular (RR: Round Robin)

A cada procés s'assigna una quantitat de temps de CPU (quàntum), normalment petita, 10 - 100 ms. Si el procés consumeix el quàntum és expulsat de la CPU i passa a la cua de preparats. Si hi ha n processos, cadascun obté un 1/n del temps de CPU en intervals de, com a màxim, q unitats.

Valor del quàntum

• q gran: degenera en un algorisme FCFS
• q petit: q sempre ha de superar el temps de canvi de procés, altrament la sobrecàrrega introduïda és molt gran

Propietats del torn circular

• Equitatiu
• Temps d'espera màxim limitat a (n-1)*q
• Temps de retorn mitjà variable amb el quàntum de temps

Planificació amb classes de prioritat

Els processos es classifiquen per classes (interactius, per lots, ...). A cada classe s'assigna una prioritat. Existeix una cua de processos preparats per a cada classe.

S'utilitzen varis algorismes:

• Algorisme de planificació de classe: planifica cada cua
• Algorisme de planificació inter-classes: planifica la selecció de cues. Per exemple:

Prioritats estàtiques: el procés seleccionat és el prioritari de la cua no buida de la classe més prioritària. Pot provocar inanició.

Quotes de temps: Cada cua té assignada una quota d'utilització de la CPU.

Mobilitat entre classes

Possibilitat de canviar de classe d'acord a un mètode de promoció i un mètode de degradació.

Per exemple:

• Processos amb temps d'espera acumulat elevat són promocionats.
• Processos amb elevada utilització de la CPU són degradats.

Selecció de l'algorisme de planificació

Selecció de criteris (ús CPU, temps de resposta, ...). Avaluar l'adaptació, per a cada sistema, dels diferents algorismes als criteris seleccionats.

Mètodes d'avaluació

• Avaluació analítica: atesa una caracterització de la càrrega del sistema, construir una fórmula matemàtica pel rendiment de cada algorisme.
  • Model Determinista
  • Model de cues
• Simulacions: desenvolupar un model, programar-lo, executar-lo i mesurar els resultats.

Solucions software

Avantatges

• No necessiten la intervenció del S.O.
• Ni la introducció de noves instruccions màquina.

Inconvenients

• Els processos consumeixen temps de CPU quan esperen (busy waiting)
• Complexes, sobretot quan s'han de coordinar múltiples processos
• Molt susceptibles de sofrir errors que a més resulten difícils de detectar

Deshabilitació d'interrupcions

Quan un procés executa la seva secció crítica ho fa en mode d'interrupcions no permeses.

• DI: Deshabilitar interrupcions
• EI: Habilitar interrupcions

Limitacions

• Limita la capacitat del processador d'intercanviar processos i per tant pot implicar una degradació de les prestacions
• Només serveix per una estructura monoprocessador.

Instruccions màquina especials

Instruccions especials que permeten la realització de dues accions (lectura/escriptura, escriptura-comprovació...) de manera atòmica, és a dir dins el mateix cicle d'instrucció. S'utilitza en estructures multiprocessador a on els processos comparteixen l'accés a una memòria comuna.

Avantatges

• Aplicable a múltiples processos
• Simple i fàcil de verificar
• Es pot utilitzar per suportar múltiples seccions crítiques (cada secció crítica amb la seva pròpia variable)

Inconvenients

• Els processos consumeixen temps de CPU quan esperen (busy waiting)
• Es pot produir inanició (depèn del mecanisme de selecció utilitzat)
• Es pot produir interbloqueig

Semàfors

Dos o més processos poden cooperar utilitzant senyals simples, de manera que un procés pot ser obligat a aturar-se a un lloc determinat fins que rep una senyal concreta. Aquestes senyals són de fet un tipus de variables especials anomenades semàfors. Tipus abstracte de dades que pren valors enters i sobre el que hi ha definides dues operacions atòmiques: P( ) i V( ). Té associats: un comptador i una cua de processos (suspesos davant del semàfor).

Monitors

Definició

Un monitor és un mòdul software amb un o més procediments, una seqüència d'inicialització, i dades locals.

Característiques

• Les dades locals només són accessibles per les rutines del monitor
• Un procés entra en el monitor quan fa una cridada a una de les seves rutines
• Només un procés es pot executar en el monitor a la vegada; qualsevol altre procés que també hagi cridat una rutina del monitor és suspès fins que el monitor està lliure.
• Utilitza dues variables de condició cwait(c) i csignal(c) per la sincronització de processos accessibles només des del monitor.

Intercanvi de missatges

Té lloc quan els processos són capaços d'interaccionar entre ells i s'utilitzen per comunicar informació i per la sincronització. L'intercanvi de missatges es pot utilitzar a qualsevol tipus d'entorn (mono i multiprocessador). El mínim conjunt de primitives necessàries són:

• enviar (destinació, missatge)
• rebre (font, missatge)

Sincronització per missatges

Hi ha tres combinacions possibles:

1. El procés que envia el missatge i el procés que ha de rebre el missatge es bloquegen fins que el missatge s'ha enviat (rendez vous). Permet una sincronització acurada entre dos processos.
2. Només el procés que espera el missatge es bloqueja fins que el rep, mentre que el procés que ha enviat el missatge pot continuar. És la configuració més utilitzada.
3. Ni l'emissor ni el receptor del missatge es bloquegen

Adreçament

• Directe: la primitiva enviar inclou un identificador específic del procés destinació. En el cas de la primitiva rebre una possibilitat és designar explícitament el procés font i l'altra a través d'una assignació implícita (el procés no coneix la font del missatge i per tant establirà el valor de la variable font una vegada que hagi rebut el missatge)
• Indirecte: els missatges no són enviats directament de l'emissor al receptor sinó que s'utilitzen unes estructures de dades (cues de missatges) anomenades bústies (mailbox).