a) Rita ett diagram som visar de olika tillstånden och övergångarna mellan dem.
Svar:
|
Kursboken av Silberschatz et al (10:e upplagan)
innehåller det här tillståndsdiagrammet:
|
b) Operativsystemkärnan innehåller en del datastrukturer som är relaterade till processerna och deras tillstånd. Vilka datastrukturer är det?
Svar:
|
I första hand PCB (process control block), även kallad task-struct,
som innehåller information om en process:
vilken användare som äger processen,
dess prioritet,
med mera.
De olika processernas PCB:er samlas i ett antal köer,
som ungefär motsvarar de olika tillstånden som processen kan befinna sig i.
Det finns en ready-kö med processer som är redo att köra,
men som just nu inte har fått en tillgänglig processorkärna att köra på.
Det finns en running-kö
(som brukar kallas för "kö" även om det inte precis är en kö)
med den eller de processer som just nu finns på en processorkärna
och är igång och kör.
Det finns också flera olika waiting-köer,
med processer som inte kan köra
eftersom de väntar på att att något ska inträffa.
Det kan vara att hårdvara som en buss eller ett sekundärminne blir ledig,
att en timer ska lösa ut, eller att ett lås ska bli ledigt, eller liknande.
Man kan också titta på den här bilden från kursboken med köer:
|
Svar:
|
Ja, trådar har också dessa tillstånd, och de kan schemaläggas på samma sätt.
Så kallade kernel threads schemaläggas av OS-kärnan,
vilket bland annat innebär att flera sådana trådar i samma process kan köras parallellt på olika processorkärnor.
En skillnad mellan trådar och processer
är att det finns så kallade user threads,
som OS-kärnan inte känner till,
och som schemaläggs av trådbiblioteket utan inblandning av OS-kärnan.
Om en process innehåller flera user threads schemaläggser OS-kärnan bara processens huvudtråd,
och kärnan känner inte till, och kan inte påverka, att den huvudtråden byter mellan att köra olika user threads.
En kommentar: Ibland används ordet "trådar" som en förkortning för det antal trådar som en processor kan köra parallellt. Till exempel kan man säga att en processor med fyra kärnor och multthreading "har åtta trådar". Det är förstås inte sådana "trådar" som avses här, för de är hårdvara och schemaläggs inte av operativsystemet, utan operativsystemet schemalägger trådar och processer på dem. |
Svar:
| Att bestämma när de olika processerna (och trådarna) ska få köra på processorn. Det kan innebära att välja vilken av flera körklara processer (i ready-kön i uppgift 1) som ska få köra, och flytta den från den kön till running, och att starta körningen på en processorkärna. Även att, om det finns väntande trådar i ready-kön, avbryta körningen av en körande tråd och flytta den till ready-kön. |
b) Beskriv två olika algoritmer för schemaläggning, och jämför dem. Vilken av dem är bäst, och vad menar man egentligen med "bäst"?
Svar:
Kursboken tar upp ett antal olika algoritmer för schemaläggning:
First-Come, First-Served är den enklase algoritmen, och innebär att processerna körs i den ordning de anländer. Man använder en enkel FIFO-kö, startar processerna i ordning, och varje process körs tills den är färdig eller (brukar man mena) "med I/O yield", dvs tills den inte längre kan köra på processorn eftersom den väntar på I/O. Algoritmen är alltså inte preemptive, dvs operativsystemet stoppar aldrig en process som kör på processorn och flyttar den till ready-kön. Shortest-Job-First kräver att schemaläggaren vet, eller i alla fall kan uppskatta, hur länge varje process behöver köra på processorn innan den antingen är färdig eller behöver vänta på I/O. Man ordnar processerna i en prioritetskö, med processer med kortare tid först, och kör den kortaste först. Den här algoritmen är inte heller preemptive. (Det finns en preemptive-version av Shortest-Job-First, Shortest-Remaining-Time-First.) Eftersom ingen av algoritmerna är preemptive, och alltså ingen av dem någonsin avbryter en process som kör på processorn och byter till en annan, blir det inga onödiga kontextswitchar. Bägge algoritmerna utnyttjar processorn maximalt, och i ett maximalt belastat system (som alltid har minst en process som kan köra på processorn) är utnyttjandet av processorn 100%. Om man med "bäst" menar utnyttjande av processorn, är båda lika bra. Om man med "bäst" i stället menar väntetider, är First-Come, First-Served förstås en katastrof, i synnerhet på ett interaktivt system där en användare sitter och försöker ge kommandon till datorn och få svar, och om man har en enkärning processor eller i alla fall få processorkärnor i förhållande till antalet processer. En process som kör länge på processorn kommer att köra klart, och alla andra får vänta. Exempelvis skulle programmet thread-performance-test från labb 2, som startar flera trådar, fyller upp alla processorkärnorna, och sedan bara räknar i en loop, köra klart innan något annat kunde hända på datorn. Jag kan flytta musen och skriva på tangentbordet, och klockan som visas på skärmen vill flytta fram sekundvisaren, men datorn kommer inte att reagera på något av detta innan thread-performance-test kört klart. Vi bör också nämna att i en del sammanhang har man realtidskrav, dvs att uppgifter måste utföras inom en viss tid. Det kan vara ett styrsystem i en självkörande bil, där bilen måste reagera på att vägen svänger innan bilen kört ner i diket. Ingen av de två nämnda algoritmerna är lämplig, eftersom en långvarig process kan ockupera processorn hur länge som helst, långt efter att bilen kört ner i diket.
|
Men är inte hela idén med virtuellt minne att man ska kunna använda mer minne än vad som finns fysiskt i datorn? Hur blir det då när adressrymderna är lika stora? Förklara!
Svar:
|
Dels är det inte säkert att hela den fysiska adressrymden faktiskt motsvaras
av fysiskt minne. Exempelvis är fysiska minnesadresser i den vanliga
x86-64-arkitekturen 52 bitar, men det är nog ganska få datorer
som faktiskt har 252 byte, dvs drygt 4 miljoner gigabyte,
fysiskt minne.
Dessutom är "hela idén med virtuellt minne" inte alls att man ska kunna använda mer minne än vad som finns fysiskt i datorn, utan virtuellt minne innebär bara att programmen arbetar med virtuella adresser som måste översättas till fysiska adresser för att hitta var i det fysiska minnet som data är lagrat. Att använda mer minne än vad som finns fysiskt i datorn underlättas av virtuellt minne, eftersom man ganska enkelt kan flytta runt ett körande programs data både i det fysiska minnet och även ut på någon form av sekundärminne. Dessutom kan det finnas flera olika processer, som var och en har sin egen virtuella adressrymd, och då blir ju faktiskt den sammanlagda mängden virtuellt minne mer än vad som fysiskt kan adresseras i datorn. |
Svar:
|
I-noden innehåller data om en fil i filträdet.
En fil kan vara en normal fil med data eller körbar kod,
men den kan också vara en filkatalog ("directory")
eller en "speciell" fil ("special file").
Speciella filer kan representera en fysisk enhet (exempelvis en hårddiskenhet),
eller fungera som ett gränssnitt mot operativsystemet
(exempelvis /proc-filsystemet).
I-noden innehåller data om filen, som vilken användare som är filens ägare, vilka rättigheter (att läsa, skriva och exekvera filen) olika användare har, filens storlek, tid för senaste ändring, och referenser till var filens data är lagrade. I-noden innehåller inte filens namn. Filnamn lagras i filkatalogerna. Flera olika namn, i en eller flera olika filkataloger, kan hänvisa till samma fil, dvs samma i-nod. I-noden innehåller också antalet hårda länkar, dvs antalet förekomster i filkataloger av denna fil. När det antalet går ner till noll kan i-noden och filens data tas bort. |
#include <stdio.h>
#include <unistd.h>
int a = 0;
void f(int b) {
b = b + 1;
printf("a = %d, b = %d\n", a, b);
}
int main(void) {
int c = 0;
if (fork() == 0) {
a = a + 1;
c = c + 1;
printf("child: a = %d, c = %d\n", a, c);
f(5);
}
else {
a = a + 2;
c = c + 2;
printf("parent: a = %d, c = %d\n", a, c);
f(7);
}
fork();
printf("finished: a = %d, c = %d\n", a, c);
}
|
a) Vad skrivs ut när programmet körs?
Svar:
Så här kan utskriften bli:
parent: a = 2, c = 2 a = 2, b = 8 child: a = 1, c = 1 a = 1, b = 6 finished: a = 2, c = 2 finished: a = 2, c = 2 finished: a = 1, c = 1 finished: a = 1, c = 1 |
b) Kan det bli olika utskrifter från gång till gång? Vad kan i så fall bli olika, och vad beror det på?
Svar:
| Ja, det kan bli olika utskrifter. Varje process som startas har sitt eget minne, så raderna som skrivs ut kommer alltid att vara likadana. Däremot kan de komma i olika ordning eftersom det är fyra olika processer som körs, utan synkronisering mellan dem. Det finns vissa begränsningar i hur olika det kan bli, och exempelvis kommer raden parent: a = 2, c = 2 alltid att skrivas ut före raden a = 2, b = 8, eftersom de utskrifterna sker efter varandra i samma process. Men som ett annat exempel kan raderna parent: a = 2, c = 2 och child: a = 1, c = 1 komma i vilken ordning som helst, eftersom barnprocessen och föräldraprocessen från det första fork-anropet inte har någon synkronisering efter fork-anropet. |
#include <stdio.h>
#include <pthread.h>
volatile int g = 0;
void *thread_body(void *arg) {
for (int i = 0; i < 1000000; ++i) {
++g;
}
return NULL;
}
int main(void) {
printf("How many threads do you want? ");
int nr_threads;
scanf("%d", &nr_threads);
printf("Starting %d threads...\n", nr_threads);
pthread_t threads[nr_threads];
for (int i = 0; i < nr_threads; ++i)
pthread_create(&threads[i], NULL, thread_body, NULL);
printf("%d threads have been started.\n", nr_threads);
printf("Waiting for them to finish...\n");
for (int i = 0; i < nr_threads; ++i)
pthread_join(threads[i], NULL);
printf("All %d threads have finished.\n", nr_threads);
printf("The value of g is %d.\n", g);
}
|
Vi provkör programmet och matar in att vi vill köra 100 trådar. Provkörning:
How many threads do you want? 100 Starting 100 threads... 100 threads have been started. Waiting for them to finish... All 100 threads have finished. The value of g is 2452039. |
Vi provkör programmet en gång till, men nu vill vi bara köra en enda tråd. Provkörning:
How many threads do you want? 1 Starting 1 threads... 1 threads have been started. Waiting for them to finish... All 1 threads have finished. The value of g is 1000000. |
a) Kan man förvänta sig att den första provkörningen, med hundra trådar, alltid ger samma värde på variabeln g? Förklara!
Svar:
| Nej. Flera olika trådar uppdaterar samma variabel, utan något lås eller annan synkronisering. Beräkningar, som att öka en variabels värde, kan inte göras direkt i minnet, utan innehållet i variabeln måste först hämtas till ett register i processorn. Ett exempel på vad som kan hända är att en tråd A hämtar värdet på variabeln g, låt oss säga 17, från den plats i minnet där variabeln är lagrad, till ett processorregister, och ökar det med ett, till 18. Innan A hinner skriva tillbaka det nya värdet till g hinner emellertid en annan tråd B hämta värdet 17. Även tråd B ökar det hämtade värdet med ett, till 18, och skriver tillbaka resultatet till g. Därefter skriver även tråd A tillbaka sitt nya värde 18 till g. Nu har vi försökt öka 17 med ett två gånger, och det borde förstås bli 19, men det har bara blivit 18. |
b) Kan man förvänta sig att den andra provkörningen, med en tråd, alltid ger samma värde på variabeln g? Förklara!
Svar:
| Ja, det ger alltid samma svar, 1000000. Här är det bara en tråd som ändrar innehållet i variabeln g, så det kan inte bli några problem med samtidighet. |
När vi provkör trådprogrammet från uppgiften ovan med en enda tråd, som vi gjorde, visar det sig att det tar 0,001 sekunder på en dator med den processorn.
Vi provkör tråd-programmet en gång till på samma dator, men nu med 100 trådar. Ungefär hur lång tid kan man gissa att det kommer att ta? Förklara hur du tänkt, och vad som spelar in för körtiden.
Svar:
|
En första gissning är förstås att det tar lika lång tid med 100 trådar som med en enda,
eftersom den här processorn kan köra alla 100 trådarna parallellt,
och det finns inga lås i programmet som gör att trådarna kan behöva vänta på varandra.
Men det är inte gratis att starta en tråd. Det tar lite tid, bland annat för att allokera plats för trådens stack. En del av detta kan kanske göras parallellt, men inte allt. Om det ska gå att köra trådarna parallellt på olika processorkärnor måste OS-kärnan känna till dem, så det behövs minst ett systemanrop för att starta tråden. Det är inte frågan om sekunder för att starta en tråd, kanske inte ens millisekunder, men det tog bara 0,001 sekunder att köra en enda tråd, och om varje tråd tar 0,00001 sekunder att starta blir det totalt 0,001 sekunder, och då har vi fördubblat tiden för programmet. Ytterligare ett problem är att trådarna arbetar med samma plats i minnet, variabeln g. Även trådar som körs på varsin processorkärna kan behöva dela på minnet och minnesbussen. Om de olika processorkärnorna har cache kan processorkärnorna behöva kommunicera på hårdvarunivån, om att de cachade värdena inte längre stämmer. Vi såg ju i labben med monstervärlden att ett flertrådat program kanske inte alls går fortare än ett enkeltrådat program som utför samma arbete, trots att flera processorkärnor arbetar parallellt, utan tvärtom mycket långsammare. |
