• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Formelsamling

2^x * 2^y = 2^x+y

Uppgift 1 (5 p)

a) Rita ett diagram som visar de olika tillstånden och övergångarna mellan dem.

b) Operativsystemkärnan innehåller en del datastrukturer som är relaterade till processerna och deras tillstånd. Vilka datastrukturer är det?

Uppgift 2 (3 p)

Uppgift 3 (4 p)

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"?

Uppgift 4 (3 p)

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!

Uppgift 5 (3 p)

Uppgift 6 (5 p)

#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?

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å?

Uppgift 7 (3 p)

#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!

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!

Uppgift 8 (4 p)

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.