Introducció

Un sistema operatiu és un programa que gestiona el maquinari d’un ordinador, proporciona una base per a d’altres programes i fa d’intermediari entre l’usuari de l’ordinador i el maquinari (fent així el seu ús més fàcil, eficient i segur).

El primer sistema operatiu va ser creat el 1956 per General Motors, per a un mainframe d’IBM. Per a més informació: History of Operating Systems, per Ayman Moumina (versió PDF).

Crides a sistema

El diagrama d’una crida a sistema és el següent:

Mode d’usuari (User Mode) Mode privilegiat
Programa Llibreria del llenguatge Llibreria del sistema Trap (crida al sistema) Codi del sistema operatiu
printf() write() x86: INT 0x…

El sistema disposa d’un vector anomenat Interrupt Descriptor Table (IDT) que determina la funció a invocar per a cada crida al sistema (o excepció per maquinari).

Processos

  • Un procés és la unitat bàsica d’assignació de recursos i té com a mínim un fil.
  • Un fil (també flux o thread) és la unitat bàsica de planificació per a l’execució d’instruccions.

Per defecte, els processos no comparteixen recursos (memòria, descriptors de fitxers ni fils) entre ells. Algunes de les seves propietats són el PID (identificador del procés) i en UNIX l’UID (usuari propietari) i el GID (grup propietari). En sistemes Linux també poden tenir personalitat, el qual permet canviar el comportament d’algunes crides a sistema per motius de compatibilitat.

Al llarg de la seva vida un procés passa per diferents estats. En termes generals, aquests es poden representar amb el següent graf:

El Process Control Block (PCB) emmagatzema la informació relativa a un procés, com ara els identificadors ja mencionats, l’estat, el PC, el contingut dels registres l’últim cop que ha estat interromput, informació per a la gestió de memòria, la llista de fitxers oberts, estadístiques que el sistema operatiu consideri rellevants, procés pare i fills, així com altres dades (prioritat del procés, restriccions de memòria o fitxers, etc). Aquesta estructura de dades (anomenada task_struct, en Linux) és generada quan es crea el procés i no s’allibera fins que el procés mor i el seu pare (o, si aquest no existeix, l’init) el recull.

El sistema operatiu inclou funcions de comptabilitat (accounting) i cada «tick» (equivalent a un determinat nombre de cicles de rellotge) s’encarrega de decidir quin ha de ser el procés actiu.

Alguns serveis relacionats amb els processos (Linux)

pid_t fork(); Crea un procés fill que és una còpia idèntica del pare, però que n’és independent. (En sistemes Linux, només hereta un dels fils).
void exit(int status); Converteix el procés en zombie i li assigna el codi d’eixida indicat.
pid_t wait(int *status); Espera que un dels processos fills acabi i retorna el seu PID. Si status no és NULL, li assigna el codi d’eixida del fill.
int execlp(char *path, …); Substitueix l’executable del procés actual (és a dir, muta el procés). Aquesta crida només retorna en cas d’error.
Exemple: execlp(“/bin/ls”, “ls”, “-l”, NULL)
Veure també: clone, threads.

Optimitzacions
Una possible optimització per millorar l’eficiència d’un fork és el copy-on-write (COW), que consisteix en no duplicar la memòria del procés fins que un dels dos la vulgui modificar (així és especialment útil, per exemple, quan es clona un procés per mutar-lo tot seguit, ja que llavors s’evita del tot haver de copiar-ne la memòria).

Fils (threads)

Els fils són més ràpids de crear i destruir que processos sencers, i comparteixen memòria i descriptors de fitxers.

Per treballar amb ells utilitzem la API de fils de POSIX. Aquesta ens deixa manipular fils d’usuari que poden estar mapejats sobre fils del sistema (kernel threads) de forma molts-a-un, un-a-un o un-a-molts.

En el sistema Linux cada fil del sistema és identificat per un identificador LWP (Light-Weight Process), el qual ens permet enviar-li senyal. Això no és així amb d’altres sistemes operatius (per exemple, algunes versions de Solaris), els quals només permeten adreçar senyals a processos sencers.

Problemes amb la concurrència

En un programa multi-thread amb recursos compartits entre els diferents fils podem trobar-nos amb problemes (per exemple, si dos fils accedeixen a la mateixa variable alhora). Poden produir-se errors molt difícils d’identificar (race conditions).

La solució als problemes de concurrència és l’ús de Mutex (exclusió mútua o locks) per protegir les seccions crítiques del codi. Es poden implementar amb espera activa (busy waiting) o bé adormint el fil. Al implementar aquestes mesures cal evitar el problema de l’abraçada mortal (deadlock).

L’API de POSIX ens proporciona les següents funcions útils:

  • pthread_mutex_trylock: intenta reservar un recurs i retorna indicant si ho ha aconseguit o no.
  • pthread_mutex_lock: reserva un recurs (esperant que estigui lliure, si cal).
  • pthread_mutex_unlock: allibera un recurs prèviament reservat.

Planificació

Hem mencionat abans que cada tick el sistema operatiu s’encarrega de decidir quin procés s’ha d’executar: aquesta tasca la fa el planificador (scheduler). Realment, però, aquest es divideix en varis components:

  • Planificador a llarg termini (Long-term scheduler / Job Scheduler): gestiona la cua de «ready» (llista de processos residents en la memòria principal i a punt per executar-se).
  • Planificador a curt termini (Short-term scheduler / CPU Scheduler): selecciona els processos / fils que s’executen en cada moment.

El planificador a curt termini es pot executar de forma «preemptiva» (preemptive), si el nucli obliga a parar al fil, o «no preemptiva» si és el fil qui abandona la CPU (perquè fa una crida bloquejant -una operació d’entrada/sortida, una espera, etc.- o acaba). Quan el canvi és «preemptiu» hi ha un canvi d’estat de «running» a «ready».

Polítiques de planificació

Algunes estratègies segons les quals es pot dur a terme la planificació:

  • First-Come, First-Served (FCFS o FIFO)
    És la més senzilla de totes: s’executa el primer programa que estigui a punt, fins que aquest torni a cedir el control al sistema operatiu. Veiem que es tracta d’una política no «preemptiva».
  • Round Robin (RR)
    Cada procès té la CPU durant un temps prefixat (quantum) o fins que es bloqueja (per ex., inicia una operació d’entrada/sortida o una espera).

En la pràctica s’acostuma a utilitzar un model híbrid de varies estratègies i pot ser que s’utilitzin les estadístiques proporcionades pel sistema de comptabilitat (accounting).

A més, molts sistemes permeten que l’administrador estableixi prioriats diferents a certs processos. En aquest cas, però, cal evitar problemes com el de starvation (que un procés tingui tan baixa prioritat que no arribi a executar-se mai).

El planificador a mig termini (medium-term scheduler)

Quan s’executen moltes aplicacions concurrents (o bé, algunes aplicacions especialment pesades), pot ser que no càpiguen totes les instruccions i dades dels programes en la memòria RAM. Quan aquest és el cas, molts sistemes operatius moderns són capaços de moure part de la memòria que no s’estigui utilitzant al disc dur (operació que es coneix com a swap out; la destinació al disc pot ser tant un fitxer especial -Windows- com una partició d’intercanvi -UNIX-) per a fer lloc per a més dades. Quan les dades mogudes tornen a ser necessàries (perquè és el torn d’executar-se d’un programa que les necessita), aquestes es tornen a copiar a la memòria, movent algunes altres dades al disc si és necessari.

Si hi ha massa processos actius, pot arribar-se a una situació de sobrepaginació, on el sistema estigui més temps intercanviant dades de programa entre la memòria i el disc que executant els programes en sí. Per evitar això, s’introdueix el planificador a mig termini, el qual s’encarrega de controlar la quantitat de processos que s’executen simultàniament (posant en pausa alguns processos de la cua de «ready»).

Memòria

Podem parlar d’adreces físiques (reals) i d’adreces lògiques. Un component hardware, la unitat de gestió de memòria (Memory Management Unit, MMU) s’encarrega de fer la traducció, vigilar que un programa no es surti del seu espai de memòria, etc. La memòria d’un mateix programa és pot separar en diferents seccions: codi, heap (no executable), pila (stack;  no executable), etc.

Assignació de memòria

  • Paginació
    La memòria es divideix en marcs (frames) d’una mida preestablerta (per exemple, 4KiB), cadascun dels quals pot acollir una pàgina.
    La paginació presenta un problema de fragmentació interna, ja que quan la quantitat de memòria requerida per un programa no és múltiple de la mida de pàgina, es desaprofitarà part d’un marc.
  • Segmentació
    Amb el sistema de segmentació la memòria es reserva un segment de memòria per a cada secció del programa (instruccions, pila, heap, etc). Així la memòria es divideix de forma lògica i cada segment de memòria pot tenir assignats uns permisos diferents (per exemple, si el seu contingut és executable com a instruccions o no). Per accedir a memòria segmentada s’utilitzen adreces compostes per un identificador del segment i un desplaçament (nombre de bytes -quan l’adreçament de memòria és a nivell de byte– a sumar a l’adreça inicial del segment).
    La memòria corresponent a un segment ha de ser contigua, de manera que en aquest cas tenim un problema de fragmentació externa: quan entre dos segments queda un espai de memòria buit, aquest no pot ser utilitzat si és més petit que les seccions dels programes.

Per reduir els problemes del sistema de segmentació, a la pràctica s’acostuma a utilitzar una combinació de tots dos, la segmentació paginada, on els segments de memòria que es troben dividits en pàgines. Així la memòria té l’estructura lògica de la segmentació però amb la fragmentació interna de la paginació (la qual aprofita millor la memòria).

Unitat de gestió de memòria (MMU)

Ja hem comentat breument que la MMU s’ocupa de traduir les adreces lògiques (tal com les veuen els programes) a adreces físiques. També s’encarrega d’evitar l’accés a memòria aliena al programa que s’està executant i, quan l’assignació fa ús d’un sistema de segmentació, de fer respectar altres possibles restriccions.

Amb aquesta finalitat, el sistema operatiu disposa d’una taula de pàgines. En la majoria de sistemes moderns, la MMU també disposa d’una unitat de memòria cau (cache) anomenada TLB (translation lookaside buffer).

Quan un programa accedeix a memòria, es cerca la traducció de l’adreça virtual que proporcioni al TLB. Si la traducció es troba a la memòria cau (TLB hit), retorna l’adreça física i l’accés a memòria pot continuar. En canvi, si no hi és (TLB miss), es passa a cercar la traducció a la taula de pàgines. La taula de pàgines inclou, juntament a l’adreça virtual i l’adreça física, un bit de validació que indica si l’adreça física és vàlida o si el contingut cercat ha estat mogut a l’espai d’intercanvi (és una pàgina no resident); si és el darrer cas, es produeix una excepció i es notifica al sistema operatiu perquè carregui les dades i actualitzi la taula de pàgines. Un cop s’ha trobat una adreça vàlida a la taula de pàgines, aquesta es grava a la TLB i es repeteix l’accés a memòria.

En sistemes de 32 bits i amb una mida de pàgina de 4KiB, hi poden haver 2^20 pàgines (2^32 bytes / 4 KiB), el qual requereix una taula de pàgines de 4MiB. Per reduir la mida de la taula de pàgines es pot implementar una taula de pàgines multi-nivell (directori de pàgines -> taula de pàgines).

Memòria dinàmica (heap)

Quan un programa no sap quanta memòria necessitarà en temps de compilació, pot reservar memòria de forma dinàmica en temps d’execució. En sistemes Linux, això es fa amb la crida a sistema brk (en C: brk i sbrk).

La llibreria estàndard del llenguatge C ofereix un seguit de funcions de més alt nivell que s’encarreguen de gestionar aquest tipus de crides de forma més eficient (reserven espai per avançat per reduir el nombre de crides a sistema, re-aprofiten l’espai anteriorment alliberat, etc). Es tracta de les funcions malloc i free.

Bibliografia

Veure també…