-------------------------------------------------------------------- Progetti del corso di Laboratorio di Sistemi Operativi. -------------------------------------------------------------------- Ogni studente deve scegliere 1 progetto dall'elenco e svilupparlo. Una volta scelto il progetto ogni studente DEVE contattare il docente per concordare l'assegnazione e i dettagli di sviluppo. NOTA BENE: progetti auto-assegnati non saranno valutati. I progetti sono individuali e se scegliete di scrivere programmi concorrenti, e' possibile svolgere il progetto in coppia. Il tempo previsto per la stesura del progetto, implementazione e documentazione e' di 50 ore circa. Vedere le modalita' di consegna nel file requisiti.txt nella stessa pagina web. Ci sono DUE categorie di progetti: shell scripting e system programming C/C++. Per i dettagli non specificati, si lascia la liberta' di scelta progettuale, debitamente documentata. -------------------------------------------------------------------- Progetto 1: mini crawler / analizzatore pagine Realizzare uno script bash che scarichi in modo ricorsivo l'home page di un url fornito come parametro e nelle pagine puntate dalla pagina. Si stabilisca una soglia (es. 1000 pagine) per terminare la ricerca. (Usare wget SENZA le opzioni ricorsive) A questo punto scrivere uno script che collezioni le parole (non tag html) per compilare una statistica sulle parole piu' frequenti. Lo script quindi dara' in output un elenco di parole con il conteggio delle loro occorrenze in tutte le pagine. -------------------------------------------------------------------- Progetto 2: shell encoding Estensione shell minimale vista a lezione, che supporti pipe (|), esecuzione condizionata (&&), redirezioni in out err, secondo la sintassi bash. Supporto per la history, che deve essere salvata e letta in un file .myhistory. -------------------------------------------------------------------- Progetto 3: directory compare Scrivere uno script bash che confronti ricorsivamente il contenuto di due directories. Lo script mostra quali files in posizioni corrispondenti sono diversi in data e/o dimensione. Per questi files lo script offre all'utente di sincronizzare il contenuto in modo automatico, tenendo la versione piu' aggiornata. NB: due files sono corrispondenti se si trovano nello stesso sottopercorso a partire dalle due directories di riferimento -------------------------------------------------------------------- Progetto 4: briscola Non puo' mancare il gioco preferito dagli studenti. Implementare un programma composto da server (1 processo che gestisce il gioco) e 2 o 4 clients (i giocatori). Il server garantisce il regolare svolgimento del gioco secondo le regole della briscola e conta in automatico i punti. Il server invia le informazioni sulle mani e distribuisce le carte ai clients. I clients visualizzano all'utente il gioco corrente (in formato testo!) e rinviano al server le decisioni prese dal giocatore. Lo scambio di informazione e sincronizzazione *deve* essere gestito con IPC (mem condivisa, messaggi e/o semafori). Si assume che i vari utenti facciano ssh sulla stessa macchina (didattica.sci.unipr.it). -------------------------------------------------------------------- Progetto 5: scheduler Si implementi un simulatore di tecniche di scheduling. Il simulatore e' composto da un generatore di processi (tramite fork) e un gestore degli stati dei processi. Il simulatore sincronizza la dinamica dei processi controllando lo spostamento dei processi tra i vari stati. I processi creati, anche se fittizi, gireranno realmente sulla CPU e la loro alternanza deve essere regolata da tecniche di sincronizzazione. Un processo puo' fare 2 cose: usare la CPU per un tempo casuale o fare richieste I/O che durano un tempo casuale. Alla creazione del processo, si decide preventivamente la struttura del processo ovvero quante alternanze tra uso CPU e I/O waiting si genereranno e la durata di ciascuna di esse. Si implementi la tecnica di scheduling FCFS ed almeno un'altra a vostra scelta. Ogni coda di processi contiene i pid dei processi. Usare una qualunque tecnica di comunicazione e sincronizzazione per sospendere e riattivare i processi. Infine si richiede al simulatore una statistica sull'uso CPU e sui vari tempi di attesa, completamento ecc. -------------------------------------------------------------------- Progetto 6: gestore memoria virtuale (2 o 3 studenti) Implementare un gestore di memoria virtuale in cui un processo rappresenta la memoria virtuale e altri processi fanno richieste di allocazione e uso del proprio spazio di indirizzi. I processi sono sincronizzati tramite IPC e il gestore della memoria implementa un algoritmo per la scelta del candidato vittima, un sistema per la assegnazione dinamica del numero di frame per processo e ovviamente la tlb (implementata come semplice array). Ogni processo puo' chiedere nuovo spazio logico (pagine) e fare accessi al suo spazio di indirizzamento (in modo piu' o meno casuale). Ogni richiesta viene passata al gestore della memoria, che si preoccupa di gestire i page faults. La granularita' delle operazioni e' la pagina (non ci interessano gli offset all'interno delle pagine). Inoltre implementare un sistema di statistica che riporti l'uso della memoria virtuale (page faults ecc). -------------------------------------------------------------------- Progetto 6.5: statistiche sulle tecniche di gestione memoria (1/2 studenti) Implementare un gestore di memoria che usa allocazione contigua a partizionamento variabile. Ogni processo (reale) richiede al gestore (un altro processo) la quantita' di memoria necessaria. Ogni processo avra' un unico ciclo di elaborazione casuale, dopodiche' chiedera' la deallocazione. Creare un generatore di processi (x esempio con fork) che stabilisce dimensione e durata di ciascuno dei figli. Se un processo non puo' essere soddisfatto, si accoda in attesa che il gestore fornisca la memoria necessaria. Il gestore della memoria utilizza una tecnica per la gestione dello spazio libero e mostra le statistiche sulla deframmentazione. -------------------------------------------------------------------- Progetto 7: Prede e predatori http://it.wikipedia.org/wiki/Equazioni_di_Lotka-Volterra Immaginiamo un recinto (80x25 pixel) in cui inizialmente ci sono N prede ed M predatori. Ogni entita' (implementata come processo linux) conosce la propria posizione nel recinto. Il sistema evolve con le seguenti regole: 1) ogni processo, dopo una attesa casuale (tra 0.1 e 2 secondi), si muove in un pixel adiacente del recinto. 2) due prede (o predatori) non possono occupare la stessa casella (serve sincronizzazione) 3) se una preda occupa la stessa casella di un predatore, viene mangiata (e il processo preda sparisce) 4) se due prede (o predatori) si trovano in caselle adiacenti, i due generano una nuova preda (o predatore) che viene collocato in una casella libera adiacente 5) ogni entita' termina la sua esistenza dopo un numero predeterminato di passi (es. 1000) Creare un processo per la visualizzazione (testuale) dell'evoluzione e vedere se ci sono dei valori iniziali che permettono di mantenere una situazione stabile. Usare gli IPC per realizzare il progetto. -------------------------------------------------------------------- Progetto 8: Schema multithread per load balancing Un task complesso puo' essere descritto da un insieme di sotto attivita' piu' o meno complesse. Non si conosce la durata di sottoattivita', quindi non e' possibile preparare uno schema ottimale di pianificazione (vedi knapsack etc). Ogni attivita' e' rappresentata come un array di celle boolean; Se la cella false = da eseguire, true = eseguito. In un ambiente multi thread, ogni thread elaborare una sotto attivita' (settando a true una cella) con una velocita' casuale di elaborazione (es. 5 secondi per cella, 2 secondi un'altra cella etc). Utilizziamo una gestione centralizzata del balancing, ovvero c'e' un altro thread che coordina i lavori. Il gestore puo' assegnare un sottoinsieme di celle (es. dalla cella 20 a 45) ad un thread ed essere notificato dell'avvenuta terminazione dell' elaborazione. Il load balancing avviene quando un thread ha terminato il suo lavoro e chiede al gestore nuovo lavoro se ne e' rimasto di non assegnato. Di fondamentale importanza e' l'implementazione della prelazione: quando tutte le celle sono assegnate, e' necessario requisire del lavoro a qualcuno. In questo caso il gestore puo' fare preemption sulla parte di lavoro assegnato a qualcuno ma ancora non svolto e ri-assegnarlo al richiedente (cosi' tutti lavorano). Inizialmente tutti i thread worker richiedono lavoro, e il gestore inizia a soddisfare le assegnazioni (per esempio si danno 10 celle a tutti i richiedenti). Aggiungere un thread di visualizzazione testuale dello stato dei lavori (es. ogni cella completata e' visualizzata con il codice del thread che la ha elaborata). -------------------------------------------------------------------- Progetto 9: chat Si programmi una applicazione per fare chat testuali. La struttura e' client server. Il processo server attende le richieste di connessione dai clients. I processi clients si collegano al server e eseguono una delle seguenti operazioni: -invio messaggio a tutti i clients connessi (broadcast) - invio messaggio ad uno specifico client - richiesta elenco clients collegati. Ogni client visualizza a stout i messaggi ricevuti. Utilizzare IPC e NON usare socket! -------------------------------------------------------------------- Progetto X: scegliete voi Avete la possibilita' di proporre il vostro progetto, da discutere con il docente per la sua approvazione. I temi devono essere legati all'implementazione di un aspetto teorico visto a lezione, o richiedere l'implementazione tramite una tecnica o metodologia vista a laboratorio.