Planificació de Processos i Fils en Sistemes Operatius

Canvis de Procés vs. Canvi de Context

Canvi de procés: Sempre que el SO agafa el control cedit pel procés en execució.

• Interrupció: Externa a la instrucció en execució.
  • Interrupció de rellotge.
  • Interrupció d'E/S.
  • Falla de memòria: la paraula no és present en memòria principal.
• Excepció (Trap): Interrupció deguda al propi procés.
  • Exemple: intent d'accés no autoritzat a un fitxer.
  • Depenent de l'error es canvia de procés o es continua l'execució.
• Crida al supervisor: El programa d'usuari requereix l'execució d'una rutina pròpia del sistema operatiu (per exemple, obrir un fitxer).
  • El procés passa a l'estat bloquejat.

Canvi de context: (Recordar el tractament d'interrupcions).

Tasques necessàries per a un canvi de procés (PCB#1 a PCB#2):

1. Salvar el context del processador (PC i altres registres).
2. Actualitzar el PCB#1: canviar estat del procés, perquè es modifica l'estat i la informació comptable.
3. Transferir PCB#1 a la cua pertinent.
4. Seleccionar el nou procés (PCB#2) d'acord amb l'algorisme de planificació utilitzat pel sistema operatiu.
5. Actualitzar PCB#2: modificar estat a execució.
6. Actualitzar les estructures de dades de gestió de memòria.
7. Restaurar el context del processador d'acord amb PCB#2.

És evident que un canvi de procés requereix més esforç que un canvi de context.

Processos i Fils d'Execució

Procés pesat (tradicional): procés amb un fil.

• Cada procés conté un sol fil.
• Cada procés té el seu propi PC, pila, espai d'adreces, etc.
• L'única relació entre els processos s'origina mitjançant les funcions d'intercomunicació.

Tasca (Procés nou): unitat d'assignació de recursos.

• Pot tenir més d'un fil.
• Tots els fils comparteixen els mateixos recursos: espai d'adreces, variables globals, fitxers, processos fills, etc.
• Cada fil es comporta com un miniprocés: s'executa seqüencialment, té el seu propi PC, pila i conjunt de registres.
• Comparteix la CPU i existeix una planificació de fils.
• Poden crear nous fils i crides al sistema.
• Poden presentar els mateixos estats que un procés: execució, preparat, bloquejat.

Recursos Reutilitzables en Sèrie

Escassetat de recursos: El nombre de recursos és inferior al nombre de processos que competeixen per ells.

Recurs reutilitzable en sèrie: Recurs que només pot ser assignat a un procés en cada instant.

• Exemples: impressores, CPU, etc.

Planificació de recursos: El SO ha d'establir una política d'assignació dels recursos reutilitzables en sèrie als processos.

Planificador

Element del sistema operatiu que determina a quin procés se li assigna un determinat recurs en cada instant de temps d'acord amb alguna política. Si el recurs a assignar és el processador es distingeixen:

• Planificador a Llarg Termini

  • Controla el grau de multiprogramació: conjunt de processos residents simultàniament en memòria i executables concurrentment.
  • Selecciona processos de la cua on esperen els que s'han de carregar en memòria.
  • Només s'executa cada vegada que finalitza un procés.

• Planificador a Curt Termini

  • Selecciona un procés de la cua de preparats i l'assigna a la CPU.
  • S'executa molt sovint: cada canvi de procés.

Processos Lligats a CPU o a E/S

Un procés lligat a CPU és aquell que inverteix la major part del temps en la realització de càlculs i requereix poques operacions d'E/S. Un procés lligat a E/S inverteix més temps en operacions d'E/S que en càlculs a la CPU. Serà funció del planificador a llarg termini seleccionar una combinació adequada d'ambdós tipus de processos.

Criteris de Planificació

Per poder comparar els diferents algorismes de planificació caldrà establir uns criteris de planificació:

• Utilització del recurs: Temps de recurs ocupat / Temps total.
• Productivitat o rendiment: Nombre de treballs finalitzats / Temps total.
• Temps de retorn: Temps d'execució d'un procés. Instant de sortida - Instant d'entrada = T_CPU + T_E/S + T_CUA.
• Temps d'espera: Temps a la cua de preparats.
• Temps de resposta: Temps des que es realitza una petició fins que s'inicia la resposta.
• Equitat: Mesura del tractament igualitari dels processos.
  • Inanició: grau extrem, no obté mai el recurs.

Optimització dels Criteris de Planificació

Alguns dels criteris anteriors són contraposats, per tant, no podran optimitzar-se tots ells simultàniament. Cada sistema presenta les seves prioritats:

• Sistemes per lots: Maximitzar utilització i rendiment, minimitzar el temps de retorn i d'espera.
• Sistemes interactius: Proporcionar equitat i un temps de resposta raonable i predictible.

La multiprogramació pretén millorar els criteris d'utilització i productivitat en front de l'execució seqüencial. Els algorismes de planificació tenen com a objectiu millorar alguns dels criteris anteriors en els sistemes multiprogramats.

Planificació per Torn d'Arribada (FCFS)

El recurs (CPU) és assignat als diferents processos en el mateix ordre que aquests el sol·liciten. No apropiatiu: el procés amb la CPU assignada la conserva fins que desitja alliberar-la, quan acaba o quan espera algun esdeveniment.

• Avantatges:
  • Fàcil d'implementar.
• Inconvenients:
  • No optimitza el temps d'espera, que passa a ser molt variable en funció de l'ordre d'arribada i de la durada dels intervals de CPU.
  • Els processos llargs endarrereixen els curts.
  • No és adequat per a sistemes interactius.
  • Per ser apropiatiu, un procés (per lots) pot provocar temps d'espera llargs als usuaris interactius.

Prioritat al Més Curt (SJF: Shortest Job First)

S'associa a cada treball el temps del següent interval de CPU. S'assigna la CPU al treball amb inferior temps associat. No apropiatiu: el procés amb la CPU assignada la conserva fins que desitja alliberar-la, quan acaba o quan espera algun esdeveniment.

• Inconvenients:
  • Pot provocar inanició en els processos llargs.
  • No sempre resol el problema dels processos curts.
  • Els temps de resposta continuen essent molt variables.

Prioritat al que Menys Temps Resta (SRTF)

Shortest Remaining Time First. La CPU és assignada al procés que menys necessita per acabar la ràfega de CPU actual. És la variant apropiativa de SJF: si arriba un procés amb una ràfega de CPU pendent inferior a la que resta al procés actualment en execució, aquest és expulsat i el nou procés obté la CPU.

• Avantatges:
  • SRTF optimitza la mitjana del temps d'espera.
• Inconvenients:
  • És difícil predir la durada del següent interval de CPU.
  • És de difícil implementació en els planificadors a curt termini.
  • En un sistema per lots el propi usuari pot aportar la informació en iniciar el treball.
  • Possibilitat d'inanició: els treballs amb intervals de CPU curts passen davant dels d'intervals llargs.