Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Marco Lapegna » 6.Il S.O. Linux – parte prima


Introduzione

Il kernel di Linux è il cuore del piu’ popolare e completo s.o. open source Unix-like.
Il codice sorgente è liberamente disponibile al pubblico Linux per modifiche ed installazione.
Oggi molto diffuso su servers, desktop computers e sistemi embedded

Numerosi vantaggi per gli utenti

  • Economici
  • Di personalizzazione del s.o.
  • Disponibilita’ di molti user groups

RAPIDISSIMA DIFFUSIONE

Storia

Versione 0.1 creata nel 1991 da Linus Torvalds a partire dal s.o. “didattico” Minix e dagli strumenti sw sviluppati da Stallman nel progetto GNU.

Guidati da Torvalds, una comunità di sviluppatori rilascia la versione 1.0 nel 1994

  • Conformità a POSIX;
  • Caratteristiche dei s.o. avanzati (mem. virt., networking, multiprogrammazione,…).

Versione 2.0 nel 1994

  • Supporto SMP;
  • Supporto a vari file system;
  • Tools di amministrazione.

Versione 2.6 nel 2003

  • Architetture a 64 bit;
  • Riscrittura di numerosi moduli del kernel.

Le distribuzioni (qualche centinaio)

Nate per facilitare il processo di installazione e configurazione del sistema, nonché il suo uso.
Di solito includono:

  • Il kernel di Linux
  • Applicazioni di sistema (tools per la sicurezza e la gestione del sistema)
  • Applicazioni utente (compilatori, browser, librerie di office automation,…)
  • Interfacce grafiche

Distribuzioni famose:

  • Red hat
  • Ubuntu
  • Suse
  • Debian
  • Fedora

Interfacce utente

A differenza di Windows e MacOS X, il kernel di Linux non specifica una interfaccia grafica utente (il desktop).
L’accesso standard al sistema è attraverso interfacce “a linea di comando” chiamate shell (Bourne shell, C shell, Bourne again shell).

Le comuni interfacce grafiche fanno parte delle distribuzioni e sono costituite da 3 livelli:

  • Gestione dei file e accesso ai programmi;
  • Posizionamento e aspetto delle finestre;
  • Creazione e manipolazione delle finestre.

Architettura del kernel


Sottosistema per la gestione dei processi

Responsabile per:

  • allocazione del processore ai processi;
  • gestione dei segnali.

Linux non fa differenza tra processi e thread:

  • Processi e thread hanno un’unica rappresentazione e vengono chiamati task;
  • Il PCB prende il nome di task_struct.

Oltre ai task_struct (una per processo) il kernel mantiene una tabella dei processi.
Ogni processo è identificato univocamente da un Process ID.
Un metodo hashing consente un accesso veloce alla tabella dei processi.

Stati di transizione


Creazione dei task

Un task può generare altri tasks mediante la chiamata di sistema clone.
Mediante tale funzione e’ possibile specificare quali risorse (memoria, registri, stack, descrittori di file) far condividere tra task padre e task figlio.

  • Poche risorse → creazione di processi
  • Molte risorse (es. sp. indirizzamento)→ creazione di threads

I task sono le unità di schedulazione da parte del kernel, quindi i threads generati con clone hanno una naturale implementazione uno-uno.

Scheduling dei processi (kernel 2.4)

40 livelli di priorita’: da -19 (la massima) a 20 (la minima).
I task vengono eseguiti secondo l’ordine di priorità.

  • Un array delle priorità conserva i puntatori alle liste dei task con la stessa priorità

Ogni livello gestito in modalità round robin.
Quanto di tempo q variabile a secondo della priorità

  • Time slice piccolo per task a bassa priorità
  • Time slice grande per task a alta priorità

Ogni task è in esecuzione fino a:

  • Esaurimento del quanto di tempo
  • Operazioni di I/O
  • E’ disponibile un task con priorità maggiore

Epoche

  • Per evitare la starvation dei processi il kernel divide il tempo di CPU in Epoche

EPOCA =
Periodo di tempo predefinito (starvation limit) entro cui tutti i processi sono eseguiti almeno una volta

  • All’inizio di ogni epoca viene assegnato un quanto di tempo q ad ogni processo, in funzione della sua priorità e del suo quanto di tempo base Q.
  • Durante un’epoca la CPU può essere assegnata round robin più volte allo stesso processo, fino a quando q non e’ esaurito
  • L’epoca scade quando:
    • la coda dei processi attivi è vuota
    • Scade la starvation limit

Lo stato expired

Alla creazione di un processo si assegna un valore di default q= Q = 200ms.

Quando i processi esauriscono il loro quanto oppure scade la starvation limit tutti i processi passano allo stato expired e non possono essere più schedulati.

All’inizio di una nuova epoca il nuovo quanto di tempo q viene ricalcolato come

q = Q + T/2
(priorita’ maggiore)

Dove T è il tempo non usato nell’epoca precedente (es. erano bloccati per I/O).

Idea alla base

I task possono essere divisi in due classi

  • I/O bound: uso prevalente dei dispositivi di I/O.
    • Tendono a non utilizzare per intero il quanto di tempo a loro assegnato;
    • Sono interattivi.
  • CPU bound: uso prevalente della CPU.
    • Tendono ad usare tutto il quanto di tempo a disposizione;
    • In generale sono poco interattivi.

Ai task interattivi (I/O bound) si cerca di dare una priorità maggiore

Scheduling real time

Oltre allo scheduling a partizione di tempo, Linux gestisce anche la classe di scheduling real time.

I processi sono gestiti o con una coda FIFO senza prelazione o in modalità round-robin.

Per prevenire un utilizzo improprio possono essere creati solo dall’amministratore di sistema.

Gestione della memoria

  • La memoria centrale è divisa in frame di 4 KB o 8 KB
  • Linux può gestire indirizzamenti a:
    • 32 bit → spazio di ind. 4 GB
    • 64 bit → spazio di ind. 2 PB (es. Intel Itanium, ma con 51 bit)
  • Tale spazio di indirizzamento richiede l’uso della memoria virtuale
    • 3 livelli di tabelle delle pagine;
    • 1 livello viene disabilitato per architetture a 32 bit.
  • Lo spazio di indirizzamento virtuale è organizzato in aree di memoria virtuale che raggruppano pagine con caratteristiche omogenee (heap, stack, area testo, …).

Segmentazione paginata

Organizzazione della memoria fisica (IA-32)


Buffer bounce (memoria tampone di rimbalzo)

I dispositivi DMA sono in grado di indirizzare limitate quantita’ di memoria

  1. viene creata una area di memoria transitoria nella zona di memoria DMA (memoria bassa);
  2. le pagine della zona di memoria DMA vengono copiate dal kernel nella zona di memoria alta.

Allocatore di zona

  • Modulo che ha il compito di trovare frame liberi per un processo. Nell’ordine cerca frame liberi ne:
    • Zona di memoria alta;
    • Zona di memoria normale se quella alta è indisponibile;
    • Zona di memoria DMA se quella normale è indisponibile.

I frame liberi sono organizzati in liste di frame adiacenti in numero pari a potenze di 2

Alle liste si accede attraverso un vettore


Esempio


Il “buddy algorithm” (buddy = compagno)

Utilizzato quando il kernel non riesce ad allocare pagine con il precedente meccanismo (es. 3 pagine e assenza di 1 e 2 frame liberi consecutivi).
Crea gruppi di frame in numero uguali a potenza di due,

  • in fase di allocazione divide frame grandi in 2 frame più piccoli (i compagni) fino alla dimensione richiesta (min=4KB)
  • in fase di deallocazione raggruppa 2 frame in frame piu’ grandi
Passi del buddy algorithm  per l’allocazione  di un processo  di 3 KB

Passi del buddy algorithm per l'allocazione di un processo di 3 KB


Allocatore di slab

Tipicamente la dimensione delle pagine in un sistema Linux è di 4 KB
Molte strutture del kernel richiedono molto meno di una pagina.

Rischio di frammentazione

Il kernel conserva alcune pagine (slab) usate come contenitore per struttture dati più piccole di una pagina.


I materiali di supporto della lezione

Silberschatz , Galvin, Gagne – Sistemi Operativi 8a ed. Capitolo 21

Tanenbaum – Moderni sistemi operativi 3a ed. Capitolo 10

Deitel, Deitel, Choffnes - Sistemi operativi 3a ed. Capitolo 16

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion