Schedulazione CPU: Tipi e Algoritmi

Certo, ecco le note di studio sul testo fornito:

Teoria dei Sistemi Operativi

• Un sistema operativo è un insieme di programmi essenziali per la gestione delle risorse hardware del computer.
• Funge da tramite tra gli applicativi utente e l'hardware, decidendo come allocare le risorse richieste.
• Il kernel è il programma sempre in esecuzione all'interno del sistema operativo.

Sistemi Mainframe

• I sistemi mainframe, utilizzati per applicazioni commerciali e scientifiche, si dividono in:
• Sistemi a lotti: l'utente manda un "job" all'operatore che lo esegue sulla macchina e consegna il risultato quando pronto.
• Sistemi multiprogrammati: mantengono più job in memoria per evitare che la CPU rimanga inattiva durante le operazioni di I/O.
• Sistemi time-sharing: assegnano ad ogni processo utente una porzione di tempo per l'uso della CPU, dando l'impressione all'utente di un sistema dedicato.

Sistemi Desktop

• Sistemi desktop: ottimizzano uso della CPU, comodità e velocità di risposta, gestendo anche la protezione dei file in reti.

Sistemi Multiprocessore

• Sistemi multiprocessore (paralleli o strettamente accoppiati): usano più processori che comunicano e condividono risorse.
• Vantaggi: quantità maggiore di output, economia di scala e aumento dell'affidabilità.
• Tipi: simmetrico (SMP), dove ogni processore esegue una copia del S.O., e asimmetrico, con un processore master che gestisce il lavoro degli altri.

Sistemi Distribuiti

• Sistemi distribuiti (con "processori lascamente accoppiati"): costituiti da reti di computer che non condividono memoria e clock; richiedono una connessione di rete.
• Si dividono in sistemi client-server (server con collo di bottiglia) e peer-to-peer (più efficienti).

Sistemi Cluster

• I sistemi cluster sono computer collegati tramite LAN che condividono la memoria di massa, offrendo affidabilità tramite ridondanza e monitoraggio.
• Si dividono in cluster simmetrici (macchine che si controllano a vicenda) e asimmetrici (una macchina esegue operazioni e l'altra esegue il controllo).

Sistemi Real-Time

• Sistemi real-time: completano le operazioni in tempi prefissati, importanti in determinate operazioni.
• Si dividono in: hard real-time (compiti critici completati nei tempi stabiliti, mischiabile con memorie volatili e di sola lettura) e soft real-time (massima priorità ai processi critici senza tempo massimo di completamento,mischiabile con i S.O. general pourpose).

Sistemi Palmari

• Sistemi palmari: utilizzati in dispositivi portatili di ridotte dimensioni gestendo hardware poco efficiente per ottimizzare l'uso della batteria.

Computer Embedded

• Computer embedded: usano sistemi operativi real-time con hardware e prestazioni limitate e interfaccia limitata.

Funzionamento del Computer

• CPU e periferiche di I/O concorrono per l'accesso alla memoria.
• Programma di bootstrap: avvia e inizializza il sistema, caricando il kernel del S.O.
• Sistemi operativi moderni sono interrupt driven, con eventi segnalati tramite interrupt hardware o software.

Vettori Interrupt

• Il vettore degli interrupt contiene gli indirizzi delle routine di gestione dell'interrupt (interrupt handler).
• Polling: scansione dei dispositivi per verificare richieste di interrupt (spreca tempo di CPU).

Struttura dell'I/O

• Ogni controller di dispositivo I/O ha buffer e registri speciali.
• Operazioni I/O possono essere sync (bloccano il processo) o async (non bloccano il processo).

Device Status Table

• La Device Status Table indica, per ogni dispositivo, il tipo, l'indirizzo e lo stato attuale.

DMA

• Molti dispositivi I/O ad alta velocità usano il DMA (Direct Memory Access) per trasferire dati senza intervento della CPU.

Struttura della Memoria

• La memoria centrale RAM ospita i programmi in esecuzione.
• La memoria secondaria (disco magnetico) memorizza in maniera permanente dati e programmi.

I/O Memory Mapped

• Blocchi di indirizzi della memoria che puntano ai registri del controller del dispositivo (porte I/O).

Disco Magnetico

• Diviso in tracce circolari e settori.
• Tempo di trasferimento dati: dipende dal tasso di trasferimento e dal tempo di posizionamento (seek + latenza).

Drive o Lettore di Dischi

• Collegato a un computer tramite cavi chiamati I/O bus (EIDE, ATA, SCSI).

Coerenza Della Cache

• Problema risolto via hardware per garantire che cache e registri CPU abbiano la stessa versione dei dati.

Protezioni Hardware

• Sistemi operativi multiprogrammati devono assicurare che un programma errato non influenzi gli altri.
• Modalità di funzionamento: utente (bit di modalità = 1) e supervisore (bit di modalità = 0).
• Istruzioni privilegiate eseguibili solo in modalità supervisore.

Chiamate di Sistema

• Un processo chiede al S.O. l'esecuzione di istruzioni privilegiate tramite chiamate di sistema. Un hardware genera una trap nel caso di parametri illegali, in modo da fornire un messaggio di errore (es. accesso a locazioni della memoria di altri processi, con istruzioni privilegiate).

Registro Base o Registro Limite

• Per proteggere i programmi l'uno dall'altro sono definiti range di indirizzi legali di un programma.

Timer

• Il Timer impedisce ad un programma di trattenere la CPU per un tempo infinito o serve per il time sharing usando in modo appropriato il time slice.

Processo

• Il processo ha bisogno di determinate risorse per eseguire e vanno alloccate durante la creazione o l'esecuzione. E può essere a singolo flusso di attività/a più flussi di esecuzione (multithreaded). I processi associati allo stesso programma sono codici separati e sezioni di dati differenti ad accesso sicuro.
• Va deciso ogni utente come e se può accedere a i dati/programmi.

Memoria Secondaria

• Il file system permette di salvare dati e programma e va definito come utilizzarlo o accedervi. Usata quindi come sorgente o destinazione del processo in esecuzione.
• L'utente impartisce degli ordini tramite istruzioni di controllo, tramite shell ed è sempre lì ad attendere comandi. Di tipo grafica o a caratteri, con oggetti eseguibili, precostituiti o batch (svolte in gruppo). Si compilava, fornisce librerie di supporto e vari funzioni per i compilatori.

Passare Parametri al S.O.

• Si può fare tramite:
• Nei registri
• In un blocco
• Stack

Struttura S.O. (Architettura)

• Diviso in piccole parti per faciliarne le modifiche: a struttura semplice (minima gerarchia ES: Ms-Dos), o monolitica (Unix), o a strati (Os/2), o a microkemel (So Mach), ibrida (Mac Os X). Struttura modulare (Solaris, Linux, Mac Os X , Unix) usa programmazioni orientate ad oggetti, con interfacce protette/definite, come se fosse a strati.

Macchina Virtuale

• Hardware a kernel trattati come blocco, con CPU schedulata. Con vantaggi di protezione risorse (condivise via software da minidisk), e per lo sviluppo dei S.O. per via del tempo di sviluppo per via delle interruzioni del sistema e il tempo di sviluppo.
• Vanno definiti subito obiettivi, hardware e tipi di S.O..

Obiettivi

• User-friendly
• Affidabile
• Veloce
• Scalabile
• Affidabile,flessibile, efficiente
• Soggette a specifiche non soggette a stand.

Microkernel

• Implementano primitive indipendenti dalla politica aggiungendo meccanismi o appositi modelli.

Windows

• Politica e meccanismi fusi in un unico sistema per un rafforzamento globale.

Linguaggi di programmazione

• Scrivere con C e C++ agevolato.

Generazione S.O.

• Sysgen (esegue in modo appropriato il S.O. su tal macchina), info hardware, CPU, memoria, dispositivi disponibili, e che funge automaticamente sul tipo di macchina.

Boot.

• Procedura di avvio del computer.

Caricatore Bootstrap / MBR

• Recupera il bootstrap porgram dal disco.

Processo

• Programma in esecuzione che passa per stati in un periodo di tempo.
• Ogni CPU può eseguirne solo uno mentre il processo può essere eseguito su più CPU.

Submit

• Viene quando S.O. idintifica le risorse.

Hold

• Qunado S.O. ordina le richieste.

Macroscheduling

• Si definisce ordine di ingresso delle richeste. Process Scheduler (in memoria): Definisce le richieste, fa riferimento il Process Control block (in esecuzione) e lo aggiorna volta x volta.

MicroScheduling

• Esegue operazione in modo non agevolato se bisogna aspettare operazione in arrivo,
• A quel punto si salva il Process Control block e si mette il in attesa finita l'operazione può passare a running che viene liberato dopo l'uso.

Long-Term Scheduling

• Controlla il livello di multi programmazione.

Short-Term Scheduling

• Sceglie il processo da eseguire assegnando la CPU.

Medium Termin Scheduling

• Si riprende l'esecuzione quando lo swap è terminato.

Creazione processo:

• Il proceso padre crea un processo figlio, e l'operazione si ripete.

Operazioni figli

• Possono usare le stesse risorse del padre. Condivide lo spazio oppure carica un nuovo programma.

Chiamate di sistema

Fork() Padre crea il figlio con un copia dello spazio indirizzamento, puàò andare in esecuzione con una exec(). Il padre si può mettere in pausa con wait(). Con exit() l'operazione viene terminata ma l'utente può vederlo finchè non lo elimina manualmente. In un gestore di memoria, va usato il garbage collector per non avere in memoria le risorse anche se terminato il thread, altrimenti riduce le prestazione della macchina.

Processi cooperanti

• Si scambiano informazioni su cui si gestisce quindi l'accesso.

Produttore/Consumatore

• Paradigma per processi cooperanti, i due processi si scambiano informazioni con apposito buffer. Ci sono buffer illimitati e limititati, consumatore aspetta che siano vuoti e produrre se pieno.

Comunicazioni tra processi

• Tramiti Inter Process Communication scmabio di messaggi (Send/receive).

Comunicazioni Dirette

• Schema simmetrico (sia mittente che destinatario sanno l'altro nome). Schema asimmetrico lo sanno i mittenti (send()), i destinatari con una variabile con riceve.

Indirette

• Tramite mailbox.

Socket

• Estremi di comunicazione usati in reti. LoopBack : 127.0.0.1 usato dal computer per riferirsi a se stesso.

Remote Procedure Call

• Consente di inserire dei processi grazie all'uso messaggi di protocollo standard (invia a demone RPC, con valori in formato XDA (external data rappresention) ad architettura remota. Se non arriva conferma client esegue l'ordinamento per intero o solo 1 volta.

Remote Method Invocation

• Permette thread per connettere oggetti remoti a computer connessi alla rete.

Thread

• Consente ad i programmi di compiere un'operazione per volta creando processi figli onerosi, vantaggi:
  • Economia -Condivisione delle risorse.

Kernel Gestiti direttente

• Si assegna a thread kernel a chiamate bloccanti, upcall è la procedura gestita col gestore upcall a carico del sistema.

API

• Standard Posix (API fatte usando questa specifica con Linux, Solaris, Windows).

Schedulatore CPU

• Non preemptivate-> lo stato va da Wait, Run, Terminated in modo volontario
• Preemtivate-> Se da run a ready o da wait la CPU si può arrestare, anche involontariamente, e può lasciare condivisione dati, portando a incosistenza.

Dispatcher

• Dà il controllo della CPU a schedulatore.

Criterio diSchedulazione( Algoritmi )

• FCFS First Come First Served (Tempo lungo medio, ogni ciclo ha razione di tempo di CPU ad intervalli regolari)
• SJF ShorterJobFirst o SRTF Sost Short Remaining Time First (Priorita')
• Round Robin (con priorità, può portare a starvation)

CODA a più LIvelli

• Interattività o Background. Puàò cambiare coda, evitando che i processi restino nelle code a bassa priorità' alzando in coda per evitare La Starvation (il quanto varia in base al contesto); si definiscono il numero di code, il metodo e il momento.

Schedulazione Threads

• PCS in competizione del thread, SCS competizione del sistema (Modello Uno a Uno usa SCO. SCS spesso è basato su una priorità definita da programmatore).

Processi Cominicazioone

Paradigma Producttore Consumatore

• Aggiungiamo un buffer per maggiori elementi e la sua relazione con l'aiuto del contatore, dove quest'ultimo ha un valore in base All'ordine delle azioni (il produttore esegue registri, aspetta condizione, etc.), cosa succede se contatore e risorsa condivisa è mutua esclusione. A tal proposito i Thread manipulano le informazioni e non ce ne sono molte.

Condizioni

• Mutua esclusione e se lo esegue qualcun altro non può esser fatto il processo, i
• Progresso,
• Attessa LImitattta,
• Soluzioni Software(complesse e efficaci) Il Software Bakery attribuisce numero progressivo per farli accedere, ma in molti sono eseguiti ad alta frequenza e ne causa problematiche pesanti. Soluzione-> disabilitazzione dell'interruttore.

Loking

• Semaforo iniziliazzionne tramite unlock; e se non esegue l'operazione correttata ripercuote sull 'intero codice e si usa istruzioni atomiche. Va usata blocco e rilascio che fa passare a Wait e riprende l'attività, con attesa attiva, tramite release; il codice e più' breve ma l'attesa e costante. Gli stalli con il codice vanno evitati facendo procedere in modo logico. L'imput più che non è lo schema applicato correttamente.

Monitor

• Costrutto in cui di linguaggio ad alto livello presenta operazioni definite con mutua esclusione, wait e singola per implementarare (block con relase).. DEADlock in cui un processo non puo' essere eseguito per via si stalli (per es con 2 dischi P1 e P2 lo usano a Test se serve l'altra, causando STallo -> non si possono gestire le risorse).

Requisiti necessari in Deadlock

• mutua esclusione
• possesso attenta
• Nessun rellascio anticipato -Attesa circolare
• Si può escludere quello che è possibile .

Deadlock.

Esamininare le richieste in modo continuo e esclude la richiesta

Detect and Recover

• Si rileva, e si recupera con allgoritmi specific per individuare qual è.

Memoria

In memoria le linee delle risorse devono andarci in modo coerente ed è importante che i dati combacino e non facciano "bordello". Compillatore unisce indirizzi in posissioni fisiche e logiche con tabelle aggiornate in tempo. Si conettte su 3 livellli:

• Compillazione,
• Caricamento,
• Esecuzione Gli iindirizzi sonno riallocatti da il sistema centrale, dove se c'è bisogno si aggiorna tutto di nuovo. L'iindrizzizzo lògico viene generato dalla cpu, quelle fisiche dalle aree fisiche assegnate. L'mmU trasmorma virtuale in fisica sfruttando supporto hardwware. Limite di range che non può essere alterato.

###Carricamento Dinamico Il loader carica solo le parti necessarie al programma, mentre il resto solo al momento. Più veloce ma funzionamneto piu lento, con il tutto in una tabella ad esso allocata per non avere errori. Permittennedo di rialloca in fase di esecuzione e caricando il codice ad eseguiire, se necessario. Va usato anche overlay che permette di far trapassare l’Utente. Puòò fare quindi una swapp, si usa il medium scheduling (attutata da mmU con trasferimento dati) o uno più lento.

Tecniche per la compillazzione

• Overlay
• Compillazione Contiqua , si inserice nella code e si inserisse il processo intero. Se le code sonno piene, si può usare partizioni multiple multiple. Non si può spostare
• ALLOcazzione Dinamicanna si può essere allocata a a più livelli come :
• FIRST Fit se il processo va ad alloccare più e piu code
• Best Fit se s'assegna il codice a piccolii pezzi. Se si usa la compattazione, non si può manomettere da lì.

Paginnazionne

Si divide la memoria fisica (frame) e lògica (paggine) nell’area di codice. Allore ha una traduzzione da tabella che permette lalloccaggio dove con la TLB si velocizza questa tabella, poi ci possono essere BIt per convalidare se il processo è corretto o meno. Puìò non essere utile negli indirizzzzi.

Si può operare in tabelle separate invertitte e per un miglioramentto della TLB la gestione avviene se è fatta da software nel

Esplora i concetti fondamentali della schedulazione della CPU, inclusi gli approcci preemptive e non-preemptive. Approfondisci gli algoritmi di schedulazione e il ruolo del dispatcher nel cambio di contesto. Comprendi l'impatto della schedulazione sulla consistenza dei dati e i protocolli di condivisione nei sistemi.