Fondamenti di informatica

Chiamate di sistema

Le chiamate di sistema (system call) sono funzioni fornite all'utente dal kernel, un componente centrale del sistema operativo.

Un programma scritto in linguaggio C può invocare, oltre alle funzioni della libreria standard, anche chiamate di sistema (che dipendono e sono variabili a seconda del sistema operativo in uso).

Quando viene invocata una chiamata di sistema, viene generata un'interruzione software, lo stato del programma chiamante viene salvato, e il controllo è trasferito al kernel del sistema operativo, che invoca una routine di gestione dell'interruzione (eseguendo le operazioni relative alla chiamata di sistema invocata). Quando tali operazioni sono completate, il controllo viene restituito al programma chiamante, ripristinandone lo stato.

Ad esempio, le chiamate di sistema open(), read(), write() e close() permettono di aprire, leggere, scrivere e chiudere un file, rispettivamente, e sono invocate dalle

risolvono. Si noti che un algoritmo è un concetto astratto, mentre la sua implementazione richiede l'applicazione dei costrutti del relativo linguaggio di programmazione in uso.

La struttura dati è un metodo di organizzazione dati che consente di gestire i dati elaborati dal programma che implementa l'algoritmo.

Ciascun linguaggio di programmazione offre strumenti, più o meno sofisticati, per definire strutture dati, ovvero aggregare dati di tipo omogeneo o eterogeneo. In questo contesto introduciamo i concetti di struttura dati e algoritmo all'interno del linguaggio di programmazione C.

LISTE

Una lista è una successione finita di valori di un tipo. L'informazione che questo codifica consiste di due componenti:

1. Multi-insieme dei valori: codifica un insieme nel quale lo stesso elemento "può comparire più volte".
2. L3: 1-->2--> 3--> 2: il concetto di multi-insieme permette che uno stesso elemento può

comparire più volte all'interno di una lista, ma assume due significati diversi (un medesimo valore dà un'informazione differente a seconda della sua relazione d'ordine)

2. Relazione di ordine tra i valori stessi

In questo senso {1, 5, 2} è una lista diversa da {1, 2, 5}

La lista è qualificata, non solo dai valori che rappresenta, ma anche dalle OPERAZIONI che vi si possono eseguire all'interno. Tali operazioni sono:

• INSERIMENTO: aggiunge un nuovo valore alla lista. In diverse varianti dell'operazione, il valore può essere inserito in testa, in coda, o in una posizione intermedia determinata da un qualche criterio di posizionamento (ad esempio nella creazione di una lista ordinata).
• CANCELLAZIONE: rimuove un elemento dalla lista. Anche in questo caso, diverse varianti operano sulla testa, la cosa, oppure su un elemento determinato in base ad un qualche criterio o possono restituire il valore che era memorizzato

sull'elemento che è stato cancellato- VISITA: applica un trattamento comune a tutti gli elementi della lista. Una visita può comunemente stampare i valori della lista, calcolarne la somma o identificarne il massimo ecc..- RICERCA: determina se la lista contiene un elemento qualificato da una condizione sul valore. Tipicamente restituisce vero/falso, ma può anche restituire l'indirizzo o comunque la posizione dell'elemento cercato nel caso in cui questo sia presente.- INIZIALIZZAZIONE: non ha un significato proprio nell'elaborazione dell'informazione. È un metodo che non corrisponde ad alcuna operazione, se non quella di inizializzare la particolare rappresentazione concreta della lista. Una lista può essere rappresentata in:

1. Forma SEQUENZIALE= i valori della lista sono rappresentati su un vettore e il loro ordine è codificato in maniera IMPLICITA dalla posizione nel vettore
2. Forma COLLEGATA= la relazione d'ordine

è codificata in modo ESPLICITO, associando ciascun valore ad uninformazione che permette di identificare il successore. Di questa forma esistono due ulteriori varianti che sidifferenziano a seconda che l’informazione sul successore sia codificata usando gli indici di un vettore o ipuntatori a un insieme di variabili.

Le differenze tra le due attengono sostanzialmente al modo con cui è rappresentata la relazione d’ordine tra gli elementi della lista.

➔ LISTA IN FORMA SEQUENZIALE

In prima approssimazione, una rappresentazione in forma sequenziale può essere ottenuta codificando i valori della lista su un array associato a una variabile che indica il numero di elementi rappresentati.

Ciò permette di eseguire efficientemente le operazioni di inserimento ed estrazione in coda, la visita e la ricerca.

È però problematica la realizzazione di un inserimento o un’estrazione in testa che richiedono una catena di copie di complessità

• se head==tail la lista è vuota
• altrimenti la locazione head contiene la testa, tail-1 contiene la coda e i valori della lista sono memorizzati nel loro ordine nel segmento compreso tra gli indici da head (incluso) a tail (escluso)
• la lista è considerata piena quando head== tail + 1, anche se in tale condizione una locazione è in effetti vuota. Se anche quella locazione venisse riempita risulterebbe head== tail, rendendo non distinguibile le condizioni di lista piena e lista vuota. Quindi una lista viene considerata piena anche se una locazione risulta vuota.

hannol'effetto contrario sull'indice tail. Combinando le diverse operazioni il segmento occupato dalla lista ruota nel buffer, allungandosi in senso antiorario/orario per gli inserimenti in testa/coda e accorciandosi in senso orario/antiorario per le cancellazioni in testa/coda. Lo schema concettuale è CONCRETAMENTE IMPLEMENTATO su un array lineare applicando agli indici head e tail un' algebra a modulo pari alla dimensione dell'array, mediante l'operatore % del linguaggio C. In questa ottica, molte delle condizioni che si possono incontrare nelle implementazioni delle operazioni relative alle liste rappresentate in forma sequenziale, vedono l'utilizzo dell'operatore % e della relativa algebra a modulo (utilizzo dell'aritmetica modulare detta anche aritmetica dell'orologio). Ad esempio la condizione (tail+1)%size==head stabilisce che il buffer non può accettare un ulteriore elemento e la lista è considerata piena.

VEDI

ESEMPI (L16 pag. 5-9)

- Inizializzazione

- Inserimento in coda: Tail= (tail+1) % size

- Inserimento in testa: head= (head+ size -1)%size

In generale (SIA PER HEAD SIA PER TAIL):

INCREMENTO: (P + 1) % size

DECREMENTO: (P + size -1) % size

- Visita: In questo caso potrebbe essere passata la lista piuttosto che il suo indirizzo (i.e., il prototipo della funzione potrebbe avere la forma void visit(struct list);) visto che l'operazione non modifica il valore di alcun membro della struttura. Nella implementazione, si è invece passato l'indirizzo per ragioni di efficienza, in modo da ridurre il numero dei parametri copiati sullo stack di sistema.

- Ricerca

NUMERO ELEMENTI LISTE SEQUENZIALI: (tail + size -head)%size

LIMITI della struttura dati in forma sequenziale:

- la lista in forma sequenziale è inadeguata laddove siano richieste operazioni di inserimento o cancellazione in posizione intermedia (tali operazioni possono in effetti essere implementate, ma richiedono una catena

costante l'elemento in posizione mediana. VEDI ES DA COMPITO (l16 pag. 10-11)➔ LISTA IN FORMA COLLEGATA CON ARRAY E INDICI

La rappresentazione collegata con arrays e indici memorizza ancora i valori su un buffer ma virtualizza la relazione di sequenza dei valori.

Il buffer è un array di records, ciascuno dei quali contiene un valore e l'indice del record del buffer che contiene il successivo valore della lista.

L'elemento di coda ha nell'indice un valore illegale che non corrisponde ad alcun record nel buffer; tipicamente il valore illegale è la dimensione del buffer stesso.

I records non usati sono anche essi concatenati attraverso gli indici in maniera da formare una lista dei records disponibili.

Nella struttura di lista si possono osservare le seguenti informazioni:

• int size: la dimensione dell'array
• int first: l'indice dell'elemento dell'array che contiene il primo valore della lista
• int free: l'indice di un

L'elemento libero dell'array a partire dal quale sono concatenati tutti gli elementi è li.