Skip to content

Instantly share code, notes, and snippets.

@razielgn
Created July 2, 2011 12:53
Show Gist options
  • Save razielgn/1060028 to your computer and use it in GitHub Desktop.
Save razielgn/1060028 to your computer and use it in GitHub Desktop.

Sistemi Operativi

Intro

Il sistema operativo

  • Supervisore

    • Visione globale delle risorse
    • Fornisce una virtual machine
  • Gestore risorse

    • Conosce i dettagli
    • Ottimizza e facilita
  • Interfaccia

    • Astrae i dettagli
    • Semplifica (hopefully)
  • Funzioni

    • Gestione CPU & RAM, I/O, processi, file, (G)UI, security

Macchina di Von Neumann

===========================
      bus di sistema
===========================
  |||       |||       |||
  CPU     MEMORIA     I/O

Storia

I generazione ('45 - '55)####

  • OS inesistente o dedicato
  • Sistema meccanico
  • Tutto in linguaggio maccchina
  • Big stuff, single user only
  • Utente = operatore

II generazione ('55 - '65)

  • SO batch
  • Operatore + utente
  • Lettura codice da schede
  • Due macchine per l'I/O, una per la computazione

III generazione ('65 - '85)####

  • 60s
    • OS batch multiprogrammato
    • Miglior uso della CPU (scheduling, interrupts, async I/O)
    • Spooling
  • 70s
    • CPU time-sharing
    • Job swapping
    • Tastiere!
    • MULTICS (multiuser, centralizzato + time-sharing)
    • UNIX (monouser, open!)

IV generazione ('80 - oggi)

  • 80s
    • Computer made personal
    • Proliferazione device I/O
    • Pretty GUI
  • 90s
    • Net OSs
  • 00s
    • Grid + Cloud = Virtualization FTW
  • 10s
    • ???
    • PROFIT
  • Esempi
    • CP/M
    • Windows
      • 95, 98
      • Win2000 e NT
      • XP, Vista, 7
    • Linux
      • Open
      • Distribuzioni abbestia
    • Apple
      • Mac OS [1-9]
      • Mac OS X

Classificazione

  • Terminal vs GUI
  • Mono-user vs Multi-user
  • Mono-tasking vs Multi-tasking

Mainframes

  • Ieri

    • Job non interattivi
    • Elab. batch
    • CPU sottoutilizzata
    • Condivisione CPU
  • Oggi

    • Virtualizzazione delle risorse (CPU, RAM, hard-disks, GPUs) tramite time-sharing

Sistemi paralleli

Distribuzione dello sforzo su più processori

  • Asimmetrico
    • Master-slave
  • Simmetrico
    • Ogni processore esegue una copia dell'OS

Concetti base e architettura

I/O

I/O dai dispositivi al corrispettivo buffer, poi la CPU sposta dal buffer alla memoria

  • Programmato
  • Interrupt
  • DMA
  • Canali

Obiettivi

  • Astrazione
  • Virtualizzazione

Funzioni di un OS

Gestione CPU

  • Creazione, avvio, sospensione e terminazione di processi
  • Schedulazione
  • Sincronizzazione
  • Gestione stalli
  • Comunicazione tra processi

Gestione Memoria

  • Allocazione e deallocazione processi
  • Protezione della memoria

Gestione periferiche

  • Interfaccia omogenea
  • Installazione, conf. e iniz.

Gestione files

  • Supporto filesystems
  • Ecc.

(G)UI

  • API
  • ...

Implementazione di un OS

Ieri asm, oggi C/C++ (o cmq type-safe)

Boot

  1. PowerOn
  2. BIOS
  3. Bootstrap del kernel
  4. ????
  5. PROFIT

SO su hdd o ROM (se embedded)

Gestione interrupt

Lista interrupt in memoria

  1. CPU rileva
  2. Salva il contesto
  3. Recupero codice interruzione
  4. ????
  5. PROFIT
  6. Ripristino contesto

API

Accesso a servizi dell'OS Da asm o c/c++ Parametri passati per

  • Registri
  • Stack
  • Memoria

Struttura di un OS

  • Monolitico
  • Stratificato
  • Microkernel
  • Moduli funzionali
  • VM
  • Client/Server

Monolitico

  • Molti OS commerciali
  • Tutte le procedure compilate in un unica .dll/.so
  • Blocking system calls

Stratificato

  • Suddiviso in layers
  • Layer 0: hardware
  • Layer N: (G)UI
  • Vantaggi:
    • Virtualizzazione
    • Portabilità (meno efficiente)

Microkernel

  • Più funzionalità nei programmi di sistema che nel kernel stesso
  • Facile estensione
  • Maggiore portabilità
  • Calo di prestazioni con più moduli caricati

Modulari

  • Dynamic kernel extensions
  • Come microkernel ma più efficiente (niente messaggi tra moduli)

VM

  • L'hypervisor crea l'illusione di fornire cpu e memoria reali

I processi

Concetto

Job = Processo Processo = programma in esec.

Componenti

  • Codice
  • Dati
    • Stack + Heap
  • Stato
    • PC
    • Stack pointer
    • ...

Processo ~ Funzione che trasforma lo stato iniziale in stato finale

Stati

  • New
  • Running
  • Waiting - I/O, eventi, ecc.
  • Ready
  • Terminated
  • Solo UNIX: Zombie

### PCB ###

  1. Stato
  2. PID
  3. PC
  4. Registri CPU
  5. Limiti memoria
  6. Info I/O
  7. Priorità

Code

  • Job queue
  • Ready queue
  • I/O queue

Schedulazione ###

  • Long-term scheduler - Ordine di secondi, minuti (no time-sharing)
  • Short-term scheduler - Freq.
  • Mid-term scheduler - Swap

Context Switch ###

< 10ms

Esecuzione

  • Synch: padre attende i figli
  • Asynch: padre non attende i figli

Comunicazione tra processi

Cooperazione ##

  • Condivisione info
  • Computazione più veloce
  • Modularità
  • Convenienza

Scambio info = Comunicazione

Coordinamento = Sincronizzazione

IPC ###

Per scambiare info tra processi

  • Veloce
  • Scalabile
  • Semplice
  • Integrato nei linguaggi
  • Affidabile
  • Sicuro

Produttore-consumatore

Buffer condiviso

Memoria condivisa

  • Identificazione dei processi comm.
  • Consistenza degli accessi
  • Richiede una sincronizzazione

Scambio messaggi

  • Memoria non condivisa

  • Contenuto

    • Proc. mittente
    • Proc. dest.
    • Infos
  • Una connessione per coppia (Diretta)

  • Più di una connessione per coppia (Indiretta)

  • Uni/Bidirezionale

  • Coda temporanea

    1. Capacità 0: bloccante
    2. Capacità n: bloccante se piena
    3. Capacità ∞: mai bloccacnte

Comunicazione mediante file

  • File condivisi
  • Pipe
    • Unidirezionali
  • Named pipe
    • Bidirezionali
    • Byte oriented

Comunicazione client/server

  • Socket
    • IP + porta
    • TCP / UDP
  • SOAP
    • HTTP + XML
  • REST
    • Stateless
    • HTTP + XML/JSON
  • RPC
    • Astrae le chiamate
    • Connessione
  • RMI
    • Java shit

Threads

  • Interni ad un processo
  • Spazio di indirizzamento condiviso tra fratelli
  • Contesto
    • Stato (registri, stack, PC)
    • Priorità
    • TID
    • Memoria privata
  • Context switch + veloce
  • Interferenze da gestire

Concorrenza

  • Prog sequenziale
    • Pausabile
    • Deterministico
  • Prog concorrente
    • Flussi cooperanti
    • Blocchi di codice eseguiti contemp.
    • Non deterministico

Modello

  • User-level

    • Soft-threads, esistono solo nell'applicazione

    • Libertà di scheduling

    • PORTABILI YEAH

    • Libs:

      • libpthread
      • win32threads
      • java shit
    • Fails:

      • Se un thread blocca, blocca tutto
      • Contesto SMP: ogni cpu esegue tutti i thread di un solo processo
  • Kernel-level: real threads, switched by the kernel

    • Lo switch grava sul kernel
    • Meno portabile

Molti a uno

Molti thread user-level a un thread kernel-level

  • pthreads

Uno a uno

  • Windows
  • Linux

Molti a molti

Thread pooling?

Problemi

Damn hard to manage

  • Creazione
    • fork(): mysterious face
    • exec(): rimpiazza il processo
  • Cancellazione
    • Async
    • Deferred
  • Gestione segnali
    • Eventi
    • A chi consegno i segnali?
  • Gruppi di thread
    • Pooling!
  • Dati specifici
    • Ogni thread ha la sua copia dei dati
  • Nascita di incosistenze su accessi e modifiche
    • Stato transiente, interferenze
    • Thread-safe se gli accessi sono atomici

Schedulazione della CPU

Obiettivi:

  • Massimizzare l'uso della CPU
  • Fingere un sistema real-time

Esecuzione tipica:

  • Uso CPU
  • Attendi I/O

Breve termine

  • Preemptive (Time sharing)

    • Esempi
      • Esecuzione -> Pronto (interrupt)
      • Attesa -> Pronto (I/O ready)
    • Time slice
    • Pre-rilascio
    • Sync per accesso condiviso
  • Non-preemptive (Multitasking)

    • Esempi
      • Esecuzione -> Attesa (I/O hanging)
      • Termina (SIGINT, SIGKILL, SIGBART, bla bla bla)

Dispatcher

  1. Context switch (sospende il corrente, attiva il seguente)
  2. User-mode
  3. PC settato per runnare il processo

Criteri di schedulazione

  1. Massimizzare l'tilizzo CPU
  2. Massimizzare il throughput
  3. Minimizzare il turnaround time
  4. Minimizzare il tempo di attesa
  5. Minimizzare il tempo di risposta

Algoritmi di schedulazione

  • FCFS
    • Convoy effect
  • SJF
    • Preemptive: se arriva un job più corto interrompe e lo esegue subito
    • Non-preemptive: lascia finire il corrente e poi fa quello nuovo
    • Ottimale, ma ideale: si può solo prevedere la lunghezza dei picchi
  • Priorità
    • Priorità uguale -> FCFS
    • Starvation sui job a bassa priorità
      • Aging
  • RR
    • Alternanza -> FCFS + preemption
    • Time slice (10-100ms)
    • Prestazioni
      • slice grande: FCFS
      • slice piccolo: awesome, ma non troppo piccolo -> overhead due to context switch
  • Coda a più livelli
    • Processi ripartiti in code
    • Ogni coda ha il suo algoritmo
    • Schedulazione tra code!

Schedulazione dei Thread

Se il SO lo supporta sono schedulati i thread, non i processi

Schedulazione multiprocessing

  • Processori omogenei
    • load sharing between them
    • una coda x procio
    • async: master - slave
    • smp: ognuno si autogestisce

Schedulazione realtime

  • hard real-time: forzatura sul tempo dei processi
  • soft real-time: priorità massima su quelli critici

Sincronizzazione dei processi

  • Sezione critica: mutualmente esclusiva nel tempo

  • Locks: variabili flag

  • Semafori: binari o contatori (wait - signal)

  • Problemi

    • Deadlock
    • Starvation

Set istruzioni cpu atomiche

Buffer limitato

  • Semaforo mutex sul buffer
  • Semaforo full a 0
  • Semaforo empty a N

Lettori scrittori

  • Semaforo mutex sul db a 1
  • Counter readerCount a 0
  • Semaforo mutex sul readerCount a 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment