Operativsystem MN1/distans VT2001

Översikt över föreläsningarna

Detta är en mycket kortfattad översikt över föreläsningarna. Nedan finns också OH-bilder och en liten liten ordlista.

Introduktion
- Vad är ett operativsystem?
  - mellan hårdvara och programvara
  - gör datorn lättare att använda genom abstraktion
  - effektiviserar, ökar säkerheten
- Varför ska ni lära er om operativsystem?
- Historisk bakgrund till olika delar och abstraktioner i ett OS
  - batch, spool, multiprogrammering, timesharing
  - jobb, overhead, jobb-schedulering och CPU-schedulering
- OS-abstraktioner
  - processer, minne, datalagring, interaktion, tid, säkerhet
- Olika typer av OS
  - batch, interaktivt, realtid (hård/mjuk), inbyggda, parallella, distribuerade, centraliserade
Processer
- De olika delarna i en process: PCB
- Processtatus, övergång mellan olika
- Köer: jobb-kö, ready-kö, wait-kö(er)
- När sker ett processbyte? Och hur? (context switch)
- Scheduleringskriterier
- Scheduleringsalgoritmer
  - FCFS, SJF, SRTF, Priority, Round Robin
  - preemption, CPU-skur (burst), IO-skur, Gantt-diagram
  - Multi-Level Queue, Multi-Level Feedback Queue
  - Fler-processor-system; priority inversion
- Threads (lättviktsprocesser, LWP)
Samverkade processer (se också OH-bilder)
- Oberoende kontra samverkande processer
- Orsaker till process-samverkan
- Meddelande-skickande kommunikation
  - länkar och deras implementation
  - direkt kommunikation (symmetrisk/asymmetrisk)
  - indirekt kommunikation
  - buffring
- Kommunikation genom delat minne
  - Producent-konsument-problemet (bounded buffer)
  - Critical Section problem
    - definition, processtruktur
    - krav på lösning
    - antaganden en lösning kan göra
    - enkla algoritmer för 2 processer
    - Bakery-algoritmen
- Hårdvarustöd för processkommunikation
  - Slå av interrupts
  - Speciella atomära instruktioner: test-and-set och swap
  - CS-algoritmer med test-and-set resp. swap
  - busy-wait ("ivriga" loopar) bör undvikas
- Semaforer
  - wait (eller P - proberen (testa)) och signal (eller V - verhogen (öka))
  - Enkel CS-algoritm med "mutex-semafor" (initialvärde 1)
  - Semaforer för synkronisering
  - Räknande semaforer - övning på Producent-Konsument
  - Gör semafor-operationerna atomära
  - Binära semaforer (3 kan implementera en räknande)
  - Problem (t.ex. baklås) fortfarande möjliga (mer senare)
- Högre abstraktionsnivåer
  - Conditional Critical Regions
  - Monitorer
    - med condition-variabler och wait/signal
    - vad händer vid signal?
Baklås (se också OH-bilder)
- En eller flera instanser av samma resurstyp
- Request, use, release (begäran, användning, släpp)
- Resursallokeringsgrafer
- Nödvändiga villkor för baklås
- Baklåshantering
  1. Deadlock prevention eller avoidance
  2. Deadlock detection och recovery
  3. Ignorera baklås
- Undvikande av villkors uppfyllande
- Säkert tillstånd, säker sekvens
- Banker's algorithm med varianter
- Wait-for-grafer
- Kombinationer av metoder
Minneshantering
- Hur hamnar ett program i minnet?
- Var översätts logiska adresser till fysiska?
- Swapping, statisk/dynamisk relokering
- Multiprogrammering, partitioner
- Minnesallokering: first/best/worst fit, Buddy-metoden
- Intern/extern fragmentering, kompaktering
Paging
- Ramar och sidor (frames/pages), sidtabeller, ramtabeller
- Adressöversättning
- Implementering, cache, TLB (notera threads och deras cache-fördel)
- Fler-nivå-paging
- Valid/invalid-bit, minnesskyddsbitar
- Sid-delning
- Logisk adressrymd kontra fysisk; kontinuitet
Segmentering
- Logisk adressrymd icke-kontinuerlig
- Adressering, adressöverättning
- Fördelar och problem
- Kombination med paging
Virtuellt minne
- Demand paging
- Sidfel, sidfelshantering
- Krav på arkitekturen
- Prestanda och swap space
- Sidutbyte (page replacement)
  - Dirty-bit
  - Referenssträngar, sidfelsdiagram
  - antal ramar kontra sidfelsfrekvens
  - Algoritmer:
    - FIFO-algoritmen, Beladys anomali, stack-algoritmer
    - OPT/MIN-algoritmen (optimal, med minimalt antal sidfel)
    - LRU: Least Recently Used
    - Referensbit(ar)
    - second-chance
    - enhanced second-chance
    - Least Frequently Used
    - Most Frequently Used
  - Trick för att ytterligare minska PF-tiden:
    - pool med lediga ramar
    - håll reda på vilka sidor som låg i lediga ramar
    - spara modifierade sidor när IO är idle
    - pre-paging
- Ramallokering
  - max/min antal ramar till en process
  - globalt/lokalt utbyte
  - thrashing
  - lokalitet och lokaler
  - working-set-modellen
  - page-fault-frequency-metoden
Filer, kataloger (se OH-bilder)
I/O, diskar, diskschedulering (se OH-bilder)
Filsystem-implementation (se OH-bilder)
Datasäkerhet och skydd
- Problem och hot
  - Instabilitet
  - Förvanskning och förstöring
  - otillåten tillgång till data och resurser
    - vanliga begrepp och tekniker
      - brute force, bakdörrar, trojanska hästar,
      - covert channels, virus, maskar
- Egenskaper att eftersträva
  - sekretess, autenticitet/äkthet, integritet, icke-förnekbarhet
- Policy & mekanism
  - policy: vad vi vill åstadkomma (ex: "need-to-know", minsta möjliga rättigheter)
  - mekanism: hur det kan åstadkommas (verktyg för att uppfylla en policy)
- Mekanismer
  - Fysiskt skydd
  - Kryptologi
    - symmetrisk kryptering
      - en delad, hemlig nyckel
      - exempel DES: snabb men kort nyckel
    - asymmetrisk kryptering
      - nyckelpar: en privat och en publik nyckel, varandras inverser
      - exempel RSA: bygger på stora primtal och svårigheten att faktorisera stora tal (ca 200 siffror, 1024 bitar)
      - kan åstadkomma både sekretess och autenticitet
  - Direkt åtkomstkontroll (ex. minnesskydd, filskydd)
    - obligatorisk resp. frivillig åtkomstkontroll
    - Ringskydd
    - Accessmatris-modellen
      - användes för
        
        Specifikation av policy
        
        Specifikation av mekanismer
      - Implementation
        
        Access control lists (ACL)
        
        Capability lists (CL)
  - Informationsflödeskontroll
    - Hur får information flöda?
    - Modeller
      - Bell-LaPadula: no read up, no write down
      - Denning: mer flexibel
- Klassificering
  - TCSEC: Trusted Computer Security Evaluation Criteria
  - Krav på policy, accountability, assurance, documentation
  - Klasser: D < C1 < C2 < B1 < B2 < B3 < A1 < A2

Overhead-bilder

Här finns, i Postscript-format, en del av de overhead-bilder jag visat och delat ut kopior av.

Processer, critical section, semaforer etc (komprimerad)
Baklåshantering (komprimerad)
Filsystem, I/O, diskschedulering (7M) (komprimerad, 0.7M)

Liten ordlista

Utdrag ur Esseltes Stora Engelsk-Svenska ordbok.

overhead

.... II ...; ~ costs (expenses, charges) se overheads; ...

overheads s plur

allmäna (generella) omkostnader, fasta utgifter

pre-empt

tr
1. 1. förvärva genom [utövande av sin] förköpsrätt
  2. hävda sin förköpsrätt
2. i förväg lägga beslag på (tillägna sig); upptinga
3. Am. (hist) slå sig ner på statsägd mark för att erhålla förköpsrätten
itr kortsp. [av]ge ett spärrbud (stoppbud)

pre-emption s

förköp; [utövande av sin] förköpsrätt

pre-emptive a

förköps-; ~ right
1. förköpsrätt
2. hand. teckningsrätt
kortsp. ~ bid spärrbud, stoppbud
förebyggande, föregripande [ a ~ air strike (flygräd) ]; avskräckande
[ his claim ] will gain ~ authority... kommer att få särskilt stor betydelse (väga mycket tungt)

Senast ändrad: Mon, 08-Jan-2001 14:34 CET