OS: Exercise 3: Processes and threads

You can do this exercise in any size group you wish. Don't worry if you find some of the questions difficult to answer, since they may be intended to initiate a discussion rather than have a single correct answer.

There might also be more questions than you have time to answer, but do as many as you can.

Preparations

Before this exercise, you should (ideally) have:

Uppgift 1

Man brukar säga att en viktig skillnad mellan trådar och processer i många vanliga operativsystem är att varje process har sin egen minnesrymd, medan flera trådar kan dela på samma minnesrymd. En annan skillnad är att operativsystemkärnan alltid måste känna till alla processer, men det kan hända att det finns trådar som operativsystemkärnan inte vet om. Förklara varför detta är olika för processer och trådar!

Uppgift 2

En process kan befinna sig i olika tillstånd, som "ny", "redo", "körande", "färdig" och "väntar". Rita upp ett tillståndsdiagram för hur processens tillstånd kan ändras, med de händelser som kan göra att det ändras.

Uppgift 3

Operativsystemkärnan innehåller att antal köer som processerna placeras i. Vilka är det? Hur hänger köerna ihop med de olika tillstånden från uppgiften ovan?

Uppgift 4

Processkontrollblocket (PCB) eller task-structen har bland annat plats för innehållet i processorns register. Varför det? Registerinnehållet finns väl i registren?

Uppgift 5

Några olika scheduleringsalgoritmer ("schemaläggningsalgoritmer"): Vad innebär de? Vilken är bäst? Och vad menar vi med "bäst"?

Uppgift 6

Varje process har sin egen minnesrymd, och flera trådar kan dela på den minnesrymden. Processens minne delas ibland upp i olika delar: Alla trådarna i en process kan dela på samma textsegment, statiska data och heap, men det behövs en stack per tråd. Varför är det så?

Uppgift 7

Här är programmet nothreads.c, som fyller arrayen data med 'x', och därefter kontrollerar att den verkligen innehåller 'x'. 

// nothreads.c

#include <stdio.h>

#define KILO 1024
#define MEGA (KILO*KILO) // 1048576
#define GIGA (KILO*KILO*KILO) // 1073741824

char data[GIGA];

int main(void) {
    // Fill with a billion 'x'
    for (int i = 0; i < GIGA; ++i)
        data[i] = 'x';
    // Check
    for (int i = 0; i < GIGA; ++i)
        if (data[i] != 'x')
            printf("Wrong!\n");
}

Här är programmet threads-1.c, som gör samma sak, men när det fyller arrayen delar det upp arbetet på två trådar: 

// threads-1.c

#include <stdio.h>
#include <pthread.h>

#define KILO 1024
#define MEGA (KILO*KILO) // 1048576
#define GIGA (KILO*KILO*KILO) // 1073741824

char data[GIGA];

void *thread_body_1(void *arg) {
    for (int i = 0; i < GIGA / 2; ++i)
        data[i] = 'x';
    return NULL;
}

void *thread_body_2(void *arg) {
    for (int i = GIGA / 2; i < GIGA; ++i)
        data[i] = 'x';
    return NULL;
}

int main(void) {
    // Fill with a billion 'x', in two threads
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread_body_1, NULL);
    pthread_create(&thread2, NULL, thread_body_2, NULL);
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    
    // Check
    for (int i = 0; i < GIGA; ++i)
        if (data[i] != 'x')
            printf("Wrong!\n");
}

I programmet threads-2.c har vi ändrat ordningen på några av satserna i main-funktionen, så den ser ut så här: 

int main(void) {
    // Fill with a billion 'x', in two threads
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread_body_1, NULL);
    pthread_join(thread1, NULL);
    pthread_create(&thread2, NULL, thread_body_2, NULL);
    pthread_join(thread2, NULL);
    
    // Check
    for (int i = 0; i < GIGA; ++i)
        if (data[i] != 'x')
            printf("Wrong!\n");
}

Slutligen finns programmet threads-3.c, där anropen till pthread_join saknas, så main-funktionen ser ut så här: 

int main(void) {
    // Fill with a billion 'x', in two threads
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread_body_1, NULL);
    pthread_create(&thread2, NULL, thread_body_2, NULL);
    
    // Check
    for (int i = 0; i < GIGA; ++i)
        if (data[i] != 'x')
            printf("Wrong!\n");
}

Vi provkör de fyra olika programmen, och mäter körtiden. Fungerar allihop? Hur lång tid kan vi förvänta oss att de tar att köra?

Uppgift 8

Vi provar också programmet threads-4.c: 

// threads-4.c

#include <stdio.h>
#include <pthread.h>

#define KILO 1024
#define MEGA (KILO*KILO) // 1048576
#define GIGA (KILO*KILO*KILO) // 1073741824

char data[GIGA];

void *thread_body_1(void *arg) {
    for (int i = 0; i < GIGA; i += 2)
        data[i] = 'x';
    return NULL;
}

void *thread_body_2(void *arg) {
    for (int i = 1; i < GIGA; i += 2)
        data[i] = 'x';
    return NULL;
}

int main(void) {
    // Fill with a billion 'x', in two threads
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread_body_1, NULL);
    pthread_create(&thread2, NULL, thread_body_2, NULL);
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    
    // Check
    for (int i = 0; i < GIGA; ++i)
        if (data[i] != 'x')
            printf("Wrong!\n");
}

Fungerar det? Kan vi gissa något om körtiden?

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), May 4, 2022