Svar: Ett avbrott innebär att processorn slutar köra den maskinkod som den höll på med, sparar undan alla maskintillstånd som kommer att behöva återställas efter avbrottet, och hoppar till en särskild avbrottsrutin. På en del processorer är systemanrop implementerade med hjälp av avbrott. Systemanropet innebär att någon instruktion som kräver särskilda priviligier, kanske en särskild instruktion avsedd för just detta ändamål, exekveras av en vanlig användarprocess, och då sker ett mjukvaruavbrott, så att exekveringen fortsätter i operativsystemkärnans kod. Eftersom OS-kärnans kod är lagrad i minne som endast OS-kärnan har rättighet att modifiera och exekvera, kanske till och med fast minne (ROM eller PROM) som inte alls kan ändras, har OS-kärnan kontroll över vad som kan göras i systemanropet.
b) Långt efter att systemanropet gjorts kan det förekomma fler interrupt, som en del av arbetet som utförs av systemanropet. Beskriv hur det kan gå till!
Svar: Moderna operativsystem är interrupt-drivna. Externa enheter som hårddiskar och nätverksenheter är mycket långsamma jämfört med processorn, och operationer på dem (som läsning och skrivning) tar mycket lång tid jämfört med den takt som processorn arbetar i. I stället för att operativsystemkärnans gång på gång ser efter om en uppgift (till exempel läsning från en hårddisk) är klar, så kallad pollning, använder man avbrott. Operativsystemkärnan som kör på processorn bara startar läsningen eller vad det nu är för extern process det gäller, och sen får den externa hårdvaran arbeta vidare utan inblandning av processorn. När operationen är färdig signalerar den externa hårdvaran till processorn med ett avbrott, och då kan processorn i sin avbrottsrutin ta hand om resultatet från den externa operationen.
a) Vad används den till?
Svar: Den lagrar all information som operativsystemet har om en process, dvs en körande instans av ett program.
b) Vad innehåller den?
Svar: Uppgifter om processens namn (typiskt ett nummer), ägare, prioriteter, uppgifter om processens virtuella minne, processens öppna filer, aktuellt tillstånd (körande, redo att köra, eller väntar på något). Om processen inte är körande finns också undansparat maskintillstånd, så OS-kärnan kan köra igång processen igen.
c) Task-structen förekommer i flera olika köer i operativsystemkärnan. Vad är det för köer, och vad används de till?
Svar: En kö med processer som är redo att köra, så fort det finns en ledig processor. En "kö" med de processer som är igång och kör just nu. En kö för varje extern enhet, till exempel ett sekundärminne eller en timer, som processer kan vänta på.
a) Hur stor är en minnessida ("page")? Visa hur du räknat.
Svar: 2048 minnesplatser. Med 11 bitar kan man lagra 211 = 2048 olika binära tal, så det är så många olika minnesplatser man kan adressera inom en minnessida.
b) Fysiska ramar ("frames") kommer att vara lika stora som minnessidorna. Förklara varför!
Svar: Innehållet på en minnessida (page) är egentligen data, och man lagrar den i en ram (frame). Därför bör de vara lika stora. Minessidan måste förstås få plats i ramen, så ramen måste vara minst lika stor som sidan, och det finns ingen anledning att göra ramen större än minnessidan, för då blir det bara oanvänd plats i den.
c) På den här processorn har fysiska adresser fler bitar än virtuella adresser. Är det något konstigt med det? Vad innebär det?
Svar: Det är inget konstigt, men ovanligt numera på vanliga datorer, och innebär att det fysiska minnet kan vara större än det virtuella minnet. Om man utnyttjar hela den fysiska adressrymden, dvs datorn är bestyckad med så mycket fysiskt minne som går med hänsyn till de fysiska adresserna, så kan upp till 16 olika processer som utnyttjar hela sin virtuella minnesrymd vara inladdade i fysiskt minne samtidigt.
d) Hur mycket plats (i byte) tar page-tabellen för en process? Gör rimliga antaganden, redovisa dem, och förklara hur du räknat!
Svar: Sidnummer är 22 bitar, dvs den virtuella minnesrymden består av 222 = 4194304 minnessidor (pages). Det behövs alltså, om man inte använder några trick för att "klumpa ihop" en del av minnessidorna till större, 4194304 platser i page-tabellen. Hur många olika ramar (frames) finns i datorn? När man tar bort offseten på 11 bitar från den fysiska adressens 37 bitar, återstår 26 bitar för ramnumret. Vi behöver minst 26 bitar för att lagra ett ramnummer, och för att det åtminstone ska bli hela 8-bitarsbytes använder vi 32 bitar, dvs 4 byte. Alltså tar hela page-tabellen 4 * 4194304 byte, dvs 16777216 byte (16 megabyte).
e) Den virtuella minnessidan nummer 2 (binärt: 10) lagras i fysisk frame nummer 0 (binärt: 0). På vilken fysisk minnesplats finns den virtuella adressen 4097 (binärt 1000000000001)?
Svar: 1
Den virtuella adressen är uppdelad i de 11 lägsta bitarna som är offset, och resten av bitarna som är sidnummer, dvs (binärt) 10 och 00000000001. Sidnumret 10 binärt motsvarar 2 decimalt, och minnessida 2 (decimalt) lagrades ju i frame 0 (decimalt). 0 (decimalt) = 0 (binärt). Den fysiska adressen blir alltså (binärt) 0 sammanfogat med 00000000001, dvs 000000000001 (binärt) = 1 (binärt) = 1 (decimalt).
...
a) Vi kör programmet, men variabelns värde blir inte alls två miljoner, utan 1028606. Vad beror det på att det blir fel värde?
Svar: De två trådarna uppdaterar samma variabel, utan lås eller annan synkronisering, och därför blir resultatet fel. När ett program ska ändra värdet på en variabel, som i ++data i det här programmet, måste processorn först hämta variabelns värde från primärminnet till ett register i processorn, utföra beräkningen i processorn, och därefter skriva tillbaka värdet till variabelns plats i primärminnet. Med flera trådar kan det till exempel bli så att tråd 1 hämtar värdet 17 från variabeln, placerar det i ett register, utför beräkningen och får det nya värdet 18, men innan tråd 1 hinner skriva tillbaka värdet till variabeln så har tråd 2 hunnit hämta det gamla värdet, 17. Tråd 1 skriver det nya värdet 18 till variabeln, och nu utför tråd 2 sin beräkning på det värde (17) den hämtade, får resultatet 18, och skriver tillbaka det till variabeln. Efter två försök att öka variabelns värde har det alltså bara ökat med ett.
b) Vi flyttar om raderna i main-funktionen så den ser ut enligt nedan. Vad blir variabelns värde nu, och vad beror det på?
...
Svar: Nu blir värdet rätt, dvs två miljoner. Vi kör en tråd i taget: huvudtråden, dvs den vanliga tråden i programmet som kör main-funktionen, startar tråd 1 med pthread_create, och väntar därefter med pthread_join på att den ska köra klart, innan den startar tråd 2 med nästa pthread_create.
c) Kan man gissa något om hur körtiden för threads-2 kommer att bli, jämfört med threads-1? Vad beror det på? (Vi talar om den så kallade "väggklocketiden", som är den verkliga tid som det tog att köra programmen, och som man till exempel skulle kunna mäta genom att titta på en väggklocka).
Svar: Om vi har flera (lediga) processorkärnor kan man gissa att threads-1, med två parallella trådar, blir ungefär dubbelt så snabbt som threads-2, som inte har någon parallellitet. Om vi har bara har en processorkärna tillgänglig, kan man gissa att båda programmen tar ungefär lika lång tid att köra, eftersom det ändå inte kan bli någon parallellitet.
Men, som vi lärt oss på labbarna, kan det krävas synkronisering på hårdvarunivån mellan trådar, till exempel för att upprätthålla cache-koherens, och därför kan det mycket väl bli så att det mer parallella programmet threads-1 blir mycket långsammare än det icke-parallella threads-2.
d) Vi har glömt hur man skrev för att använda pthread-paketets lås, så vi försöker göra ett lås själva, så programmet ser ut enligt nedan. Fungerar låset? Kommer variabelns värde att bli två miljoner nu? Förklara!
....
Svar: Nej, det här försöket att göra ett lås fungerar inte. Efter loopen som väntar på att låset ska bli ledigt, och innan låsningen genom att sätta variabeln locked till ett, kan en annan tråd hinna emellan och ta låset, så att mer än en tråd tror att den har låset.
e) Visa hur man gör låsningen på rätt sätt, med pthread-paketets lås.
Svar: Programmet threads-4.c:
// threads-4.c
#include <stdio.h>
#include <pthread.h>
volatile long long data = 0;
pthread_mutex_t lock;
void *thread_body(void *arg) {
for (int i = 0; i < 1000*1000; ++i) {
pthread_mutex_lock(&lock);
++data;
pthread_mutex_unlock(&lock);
}
return NULL;
}
int main(void) {
pthread_t thread1, thread2;
pthread_mutex_init(&lock, NULL);
pthread_create(&thread1, NULL, thread_body, NULL);
pthread_create(&thread2, NULL, thread_body, NULL);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
pthread_mutex_destroy(&lock);
printf("Result: data = %lld\n", data);
}
|
...
När vi provkör programmen mäter vi upp dessa körtider:
| Program | Körtid |
|---|---|
| create-garbage-1 | 6.253 s |
| create-garbage-2 | 0.019 s |
| create-garbage-3 | 0.013 s |
| create-garbage-4 | 0.018 s |
| create-garbage-5 | 0.005 s |
a) Varför är create-garbage-1 så väldigt långsamt? Förklara!
Svar: create-garbage-1 skriver bara en enda byte (char) åt gången med systemanropet write, så det gör väldigt många (10485760 stycken) systemanrop. Systemanrop är långsamma, jämfört med till exempel ett vanligt funktionsanrop, eftersom det måste lämna över till operativsystemkärnan och byta exekveringsmod från user mode till kernel mode (och sen tillbaka).
b) Kan man förklara körtiderna för programmen create-garbage-2, create-garbage-3 och create-garbage-4?
Svar: create-garbage-2 skriver 1024 byte åt gången, och gör 10240 systemanrop till write. Därför är det rimligt att create-garbage-2 är mycket snabbare än create-garbage-1, som gjorde 10485760 write-anrop.
create-garbage-3 skriver 10240 byte åt gången, och gör 1024 systemanrop till write. Därför är det rimligt att create-garbage-3 blir snabbare än create-garbage-2.
create-garbage-4 skriver hela datamängden, 10485760 byte, på en gång, och gör alltså bara ett enda systemanrop till write. Man skulle kunna gissa att create-garbage-4 därför blir ännu snabbare än create-garbage-3, men i stället ser vi att det blir långsammare. Men det är inte bara systemanrop som tar tid när man kör ett program, utan även vanligt arbete i user mode. Här måste programmet fylla hela bufferten med 'x', och det kanske tar så lång tid att skriva dessa 10485760 byte med data att vi inte vinner något på att ha färre systemanrop. Det är i alla fall en möjlig förklaring. En annan förklaring kan bero på detaljerna i hur write är implementerat inuti kärnan, till exempel hur buffertar allokeras och kopieras.
c) Kan man säga något om hur många processorkärnor som datorn vi provkörde på har? Vad, och varför?
Svar: Ja, när vi delar upp programmet i tio trådar blir det snabbare än någon av de icke-trådade versionerna, så det förefaller som om en del arbete görs parallellt. Därför måste det finnas mer än en processorkärna, och förmodligen också minst tre (eller två med hyperthreading), eftersom det flertrådade programmet blir mer än dubbelt så snabbt som något av de enkeltrådade. (Men vi har inget enkeltrådat program som gör just tio write-anrop, och det hade varit intressant att jämföra med det.)
d) Ett program kan vara flertrådat, men man talar också om flertrådade operativsystemkärnor. Kan man säga något om ifall operativsystemkärnan på datorn som vi provkörde på är flertrådad? Vad, och varför?
Svar: Ja, systemanropen verkar ju gå snabbare när man gör flera parallellt, och det tyder på att de utförs parallellt även i kärnan. Om operativsystemkärnan var enkeltrådad skulle de olika systemanropen behöva vänta, för bara en tråd i taget kan utföra arbete i kärnan.