ITF225129 Innføring i operativsystemer

Obligatorisk oppgave 5: Programmering med tråder

I denne oppgaven får du trening i grunnleggende trådprogrammering i Linux, med bruk av C-programbiblioteket pthreads.

Oppgaveteksten består av to deler:

  1. I den første delen gis det en innføring i enkel bruk av pthreads, som inneholder det du trenger å kunne for å løse oppgavene i del 2. Det er også noen enkle øvinger i del 1, som det ikke skal leveres noen besvarelse på.

  2. Den andre delen inneholder programmeringsoppgaver. Det skal leveres besvarelser på oppgavene i form av et tekstdokument med besvarelser, og filer som inneholder C-programmer.

1 POSIX-tråder i Linux: pthreads

Vi skal se på hvordan du kan skrive C-programmer som oppretter en ny tråd, avslutter en tråd, og venter på at en tråd skal fullføre eksekvering. Det gis enkle programeksempler med brukertråder, som følger standarden gitt av POSIX (The Portable Operating System Interface). POSIX er et sett med standarder som definerer et operativsystemuavhengig programmeringsgrensesnitt. Deler av dette grensesnittet implementeres av C-biblioteket pthreads

1.1 Kompilering

Når du programmerer med pthreads, må du si fra til kompilatoren at programmet ditt skal bruke trådbiblioteket. Anta at du har laget et C-program som bruker pthreads, som er lagret i filen mythreads.c i stående katalog. For å kompilere dette og produsere en eksekverbar fil med navn mythreads, kan du gi kommandoen:

gcc -pthread -o mythreads mythreads.c

Husk at manualsystemet i Linux er din beste venn både når du bruker shellet og programmerer i C. For detaljert informasjon om alle funksjonene som tilbys i pthreads, se man pthreads.

1.2 Opprettelse og avslutning av tråder

For å opprette nye tråder i pthreads brukes funksjonen pthread_create(), som er definert slik i headerfilen pthread.h:

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                   void *(*start_routine) (void *), void *arg);

Et kall på pthread_create() vil både lage og starte eksekvering av en ny tråd i prosessen som kaller funksjonen. pthread_create() returnerer verdien 0 (null) hvis opprettelse av tråden gikk bra, ellers returneres en feilkode.

Funksjonen har fire parametre:

  • pthread_t *thread

    Datatypen pthread_t, som er definert i headerfilen pthread.h, brukes til å lagre data om en tråd. Parameteren thread her er en peker til en pthread_t-variabel, som vil inneholde den nye tråden som er opprettet når kallet på pthread_create() returnerer.

  • const pthread_attr_t *attr

    Datatypen pthread_attr_t, som også er definert i headerfilen pthread.h, brukes til å lagre en tråds attributter. Dette er et sett med verdier som brukes til å styre hvordan en tråd skal oppføre seg. Parametern attr er en peker til en slik attributt-variabel. Vi kommer til å la denne parameteren være lik NULL i våre eksempler. pthread_create() vil da lage en ny tråd med standard-innstillinger.

  • void *(*start_routine) (void *)

    Denne parameteren er viktig for å forstå hvordan pthread_create() virker. I C kan man overføre pekere til både variable og til funksjoner, som parametre til en annen funksjon (se læringsmodulen om avansert C-programmering for et annet eksempel). Parameteren start_routine() er her en peker til en funksjon som vi (oftest) har programmert selv — det er dette som angis med syntaksen (*start_routine).

    Når den nye tråden som er laget av pthread_create() starter, vil den begynne med å eksekvere koden som er gitt i den funksjonen som parameteren start_routine() peker til! Der er på denne måten vi styrer hva de enkelte trådene som startes skal utføre: Vi gir pthread_create() en peker til starten på koden (funksjonen) som tråden skal kjøre.

    Returdatatypen til start_routine(), som er angitt foran (*start_routine), ser vi er definert som void *. Dette gjør at vi (ved å anvende typecasting) kan bruke funksjoner med en hvilket som helst datatype i kall på pthread_create().

    Feltet (void *), som kommer etter funksjonspekeren (*start_routine), angir at funksjonen som tråden skal starte i kan ha en eller flere parametre. Disse parametrene angis i den siste parameteren arg i pthread_create.

  • void *arg

    Den siste parameteren til pthread_create() er en peker arg til datatypen void. arg brukes for å angi de faktiske parameterne som tråden skal bruke når den starter funksjonen start_routine(). Hvis funksjonen ikke har noen parametre, skal arg være lik NULL. Vi skal se nedenfor se flere enkle eksempler på hvordan du kan programmere dette.

Følgende figur oppsummerer syntaksen og parametrene til pthread_create():

[figur]

1.3 Tråder og samtidighet/concurrency

Her er et enkelt eksempel på opprettelse av tråder i et C-program:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define N_THREADS 10

void *print_message(void *thread_id)
{
   printf("Tråd %ld starter\n",   (long) thread_id);
   printf("Tråd %ld avslutter\n", (long) thread_id);
   pthread_exit(NULL);
}

int main ()
{
   pthread_t thread;
   long i;
   int ret_val;

   for(i = 0; i < N_THREADS; i++)
   {
      printf("Main oppretter tråd %ld\n", i);
     
      ret_val = pthread_create(&thread, NULL, print_message, (void *) i);
   
      if (ret_val)
      {
	printf("Feil i oppretting av tråd, feilkode %d\n", ret_val);
	exit(-1);
      }
   }
}

Programmet ovenfor gjør følgende:

  • Hovedprogrammet main() oppretter 10 (konstanten N_THREADS) tråder, én i hvert gjennomløp av for-løkken.

  • I hvert kall på pthread_create() lagres den nye tråden som er opprettet i variabelen thread, som er første parameter (thread brukes ikke til noe i dette enkle eksemplet). Den nye tråden blir en "standardtråd", siden attributt-parameteren (andre parameter) settes lik NULL. Neste parameter er funksjonen print_message() (definert ovenfor i koden) som tråden skal starte å eksekvere. Den siste parameteren er "nummeret" på tråden, variabelen i, som gis videre som parameter til print_message(). Denne må type-castes til void *.

  • Hovedprogrammet main() tar vare på returverdien fra pthread_create() i variabelen ret_val, og gir en feilmelding hvis en tråd ikke kunne opprettes.

  • Metoden print_message() gis som parameter til pthread_create() i main(), slik at hver tråd starter med å kjøre denne. print_message() gjør ikke noe annet enn å skrive ut to meldinger (legg merke til at parameteren thread_id må type-castes igjen før utskrift). Metoden kaller også pthread_exit(), som terminerer tråden som kaller den. Dette er egentlig ikke nødvendig, tråden skal uansett bare terminere etter utskrift.

Kompiler og kjør deretter dette programmet selv flere ganger. Du vil da se at utskriften ikke blir den samme hver gang!

Her er f.eks. utskrift fra to ulike kjøringer på min egen Linux-maskin:

Kjøring 1        Kjøring 2 
Main oppretter tråd 0
Main oppretter tråd 1
Tråd 0 starter
Tråd 0 avslutter
Main oppretter tråd 2
Tråd 1 starter
Tråd 1 avslutter
Main oppretter tråd 3
Main oppretter tråd 4
Tråd 2 starter
Tråd 2 avslutter
Tråd 3 starter
Tråd 3 avslutter
Tråd 4 starter
Tråd 4 avslutter
Main oppretter tråd 5
Main oppretter tråd 6
Tråd 5 starter
Tråd 5 avslutter
Main oppretter tråd 7
Tråd 6 starter
Tråd 6 avslutter
Main oppretter tråd 8
Tråd 7 starter
Tråd 7 avslutter
Main oppretter tråd 9
Tråd 8 starter
Tråd 8 avslutter
 
Main oppretter tråd 0
Main oppretter tråd 1
Tråd 0 starter
Tråd 0 avslutter
Main oppretter tråd 2
Tråd 1 starter
Tråd 1 avslutter
Main oppretter tråd 3
Main oppretter tråd 4
Tråd 3 starter
Tråd 3 avslutter
Main oppretter tråd 5
Main oppretter tråd 6
Tråd 4 starter
Tråd 4 avslutter
Main oppretter tråd 7
Tråd 5 starter
Tråd 5 avslutter
Tråd 2 starter
Tråd 2 avslutter
Main oppretter tråd 8
Tråd 7 starter
Tråd 7 avslutter
Tråd 6 starter
Tråd 6 avslutter
Main oppretter tråd 9
Tråd 8 starter
Tråd 8 avslutter

Vi ser her tydelig at rekkefølgen av det som skjer i trådene og i main() er forskjellig mellom de to kjøringene. F.eks. starter tråd 2 først etter at tråd 5 er ferdig i kjøring 2.

Legg også merke til at den siste tråden, tråd 9, ikke får kjørt i noen av de to eksemplene. Dette skjer fordi selve prosessen som trådene tilhører, dvs. prosessen som kjører main(), selv terminerer før den siste tråden kan starte. Når en prosess avsluttes, termineres også alle trådene i prosessen!

Dette betyr at eksekvering av trådene er ikke-deterministisk, dvs. at du ikke vet i hvilken rekkefølge koden vil utføres eller hvordan utskriften vil bli når du bruker tråder. Dette skjer fordi operativsystemet kjører trådene og main() "samtidig" og parallelt med hverandre, med bruk av såkalt time-sharing og scheduling (som vi skal se nærmere på senere i kurset).

Denne samtidigheten (concurrency på engelsk) som vi oppnår i trådprogrammering, betyr at mange operasjoner og beregninger kan utføres parallelt. Det er nettopp derfor vi bruker tråder: Vi kan utnytte "dødtid" på systemet bedre og få beregninger til å gå mye raskere hvis vi har mange CPU-kjerner.

Concurrency/samtidighet skaper også problemer for oss som programmerere. Det gjør oppførselen til trådprogrammer vanskeligere å styre, forstå og feilrette. Vi trenger derfor mekanismer som gjør at vi kan kontrollere trådene. Tråder og prosesser må kunne vente på hverandre (synkroniseres), og de må kunne utveksle data og kommunisere (interprosesskommunikasjon).

1.4 Vente på at en tråd skal fullføre

Som vi så i eksemplet ovenfor (og som beskrevet i manualsiden for pthread_create()), vil en ny tråd bare avsluttes hvis "hovedtråden" som opprettet den selv avsluttes. Dette gjøres selv om den nye, opprettede tråden ikke har fullført koden sin.

Hvis vi ønsker å sikre at hovedtråden venter til den opprettede tråden er fullført før den selv fortsetter, kan vi bruke funksjonen pthread_join(). Funksjonen er definert slik i pthread.h:

int pthread_join(pthread_t thread, void **retval);

Den første parameteren til pthread_join() angir tråden som det skal ventes på. Den andre parameteren kan brukes til å ta vare på returverdi(er) fra tråden, vi vil sette denne lik NULL i våre kodeeksempler. Hvis tråden terminerte normalt vil funksjonen returnere verdien 0 (null), ellers returneres en feilkode.

Nedenfor er et eksempel på bruk av pthread_join(). Vi har her skrevet om programmet gitt ovenfor i avsnitt 1.3, slik at alle trådene som opprettes lagres i en array. Hver gang en ny tråd opprettes og startes, utfører main() umiddelbart etterpå et kall på pthread_join(). main() vil da vente til den nye tråden er ferdig før den går videre med å lage og starte neste tråd:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define N_THREADS 10

void *print_message(void *thread_id)
{
   printf("Tråd %ld starter\n",   (long) thread_id);
   printf("Tråd %ld avslutter\n", (long) thread_id);
   pthread_exit(NULL);
}

int main ()
{
   pthread_t thread[N_THREADS];
   long i;
   int ret_val;

   for(i = 0; i < N_THREADS; i++)
   {
      printf("Main oppretter tråd %ld\n", i);
      ret_val = pthread_create(&thread[i], NULL, print_message, (void *) i);
      if (ret_val)
      {
	printf("Feil i oppretting av tråd, feilkode %d\n", ret_val);
	exit(-1);
      }
      pthread_join(thread[i], NULL);
   }
}

Når vi kjører dette programmet, ser vi at alle de 10 trådene kjøres i rekkefølge og oppfører seg som "vanlige funksjonskall":

Main oppretter tråd 0
Tråd 0 starter
Tråd 0 avslutter
Main oppretter tråd 1
Tråd 1 starter
Tråd 1 avslutter
Main oppretter tråd 2
Tråd 2 starter
Tråd 2 avslutter
Main oppretter tråd 3
Tråd 3 starter
Tråd 3 avslutter
Main oppretter tråd 4
Tråd 4 starter
Tråd 4 avslutter
Main oppretter tråd 5
Tråd 5 starter
Tråd 5 avslutter
Main oppretter tråd 6
Tråd 6 starter
Tråd 6 avslutter
Main oppretter tråd 7
Tråd 7 starter
Tråd 7 avslutter
Main oppretter tråd 8
Tråd 8 starter
Tråd 8 avslutter
Main oppretter tråd 9
Tråd 9 starter
Tråd 9 avslutter

Ut fra dette eksemplet kan det kanskje virke som om tråder er unødvendige — de kompliserer både programmering og eksekvering på en helt annen måte enn vanlige funksjoner. Grunnen til at vi allikevel bruker dem er (som nevnt ovenfor) at de gir utviklere muligheter til å bygge mye mer effektive og fleksible systemer. F.eks. er store databaser og internett-tjenester med mange brukere og mye datatrafikk, helt avhengige av tråder for å fungere. Slike systemer trenger flere og kraftigere mekanismer for trådkontroll enn de få funksjonene i pthreads som vi ser på her.

1.5 Overføring av argumenter til en tråd

Vi har sett at nye tråder lages og startes med kall på pthread_create() som er definert slik i pthread.h:

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                   void *(*start_routine) (void *), void *arg);

Den første parameteren her, thread, vil ved retur fra pthread_create() inneholde selve tråden som startes, mens andre parameter, attr, angir settinger/attributter for tråden. Vi bruker verdien NULL for attr for å opprette en "standardtråd".

Tredje parameter, start_routine(), er en peker til en funksjonen som tråden skal starte i. Det er den siste parameteren, arg, som brukes til å overføre argumenter til denne funksjonen.

Programmet i avsnitt 1.3 ovenfor gir et eksempel på overføring av et argument (eller en verdi) til en tråd som skal startes av pthread_create(). Her er et par eksempler til som kan være nyttige for å løse oppgavene i del 2 nedenfor.

Hvis start_routine() ikke har noen argumenter, settes det siste argumentet i pthread_create() til NULL. Her er et enkelt eksempel: 

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

void *skriv()
{
  printf("Tråd: Cashmere Cat ruler!\n");
}

int main ()
{
   pthread_t tråd;
   pthread_create(&tråd, NULL, skriv, NULL);
   pthread_join(tråd, NULL);
   printf("Main: Helt enig\n");
}

I det neste eksemplet gjør vi referanseoverføring av parameteren til start_routine(), slik at den kan forandre på verdien til en heltallsvariabel: 

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

void *increment(void *void_ptr)
{
   int *int_ptr = (int *) void_ptr;
   *int_ptr += 1;
}

int main ()
{
   pthread_t tråd;
   int tall = 0;
   printf("tall = %d\n", tall);
   
   pthread_create(&tråd, NULL, increment, (void *) &tall);
   
   pthread_join(tråd, NULL);
   printf("tall = %d\n", tall);
}

Kjør programmet for å se at verdien på variabelen tall i main() endres av tråden som kjører funksjonen increment(). Legg spesielt merke til både type-castingen og håndteringen av pekere/parametere i koden ovenfor.

En array/tabell kan også overføres som parameter ved opprettelse av tråder. Her er en utvidelse av eksempelet ovenfor, der tråden nå kaller en funksjon som legger til 1 på alle elementene i en array med heltall:

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

void *increment(void *void_array)
{
  int i, *int_array;
  
  int_array = (int *) void_array;
  
  for (i = 0; i < N; i++)
     int_array[i] += 1;
}

int main ()
{
   pthread_t tråd;
   int i, A[N];
   
   for (int i = 0; i < N; i++)
   {
      A[i] = i + 1;
      printf("%2d ",A[i]);
   }
   printf("\n");
   
   pthread_create(&tråd, NULL, increment, (void *) A);
   
   pthread_join(tråd, NULL);
   for (int i = 0; i < N; i++)
      printf("%2d ",A[i]);
   printf("\n");
}

Hvis du trenger å overføre flere variabler av ulik datatype til en tråd, kan du overføre en peker til en struct som inneholder dataene, som i dette eksemplet: 

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

struct prosess
{
   int nummer; 
   char status;
   float start_tid;
   float CPU_tid;
};

void *skriv(void * V)
{
   struct prosess *P = (struct prosess *) V;
   printf("Nr: %3d  Status: %c  Start: %5.2f  CPU: %5.2f\n",
	   P->nummer, P->status, P->start_tid, P->CPU_tid);
}

int main ()
{
   pthread_t tråd;  
   struct prosess P = {15, 'S', 0.12, 3.14};
   
   pthread_create(&tråd, NULL, skriv, (void *) &P);
   pthread_join(tråd, NULL);
}

1.6 Matrisemultiplikasjon

Matrisemultiplikasjon er et eksempel på en beregning som kan utføres mye raskere med bruk av tråder, hvis du har svært store datamengder og en maskin med mange CPU-kjerner tilgjengelig. Du kan da f.eks. bruke like mange tråder som antall kjerner, og få operativsystemet til å kjøre hver av trådene på sin egen kjerne. Du skal programmere matrisemultiplikasjon med tråder i en av oppgavene nedenfor.

1.6.1 Definisjon

En matrise med størrelse M×N er det samme som en todimensjonal tabell i programmering, med M rader og N kolonner. Her er et eksempel på en 3×3 matrise med heltall:

[figur]

Vi kan multiplisere to matriser A og B med hverandre og beregne produktet AB, hvis antallet kolonner i A er lik antallet rader i B.

Anta at A er en M×N matrise (med M rader og N kolonner) og B er en N×P matrise (med N rader og P kolonner). Vi kan da beregne produktet C=AB. C blir en M×P matrise (med M rader og P kolonner), som vist i formelen nedenfor:

[figur]

Element Cij, dvs. elementet i rad i og kolonne j i C, beregnes ved å multiplisere elementene i rad i i A med elementene i kolonne j i B. Multiplikasjonen gjøres som et såkalt indreprodukt (som også kalles for et prikkprodukt eller skalarprodukt) av to arrayer/tabeller med samme lengde. I et indreprodukt multipliserer vi første element i den ene arrayen med første element i den andre arrayen, andre element i første array med andre element i andre array osv. Alle produktene av to og to elementer på samme indeks legges sammen.

Formelen for å beregne Cij er:

[figur]

Figuren nedenfor viser to 4×4 matriser som multipliseres med hverandre. Produktet blir da også en 4×4 matrise. Elementet i rad 1 og kolonne 1 i produktet (markert med rødt) beregnes ved å multiplisere første rad i første matrise med første kolonne i andre matrise (begge markert med gult).

[figur]

Her er et eksempel på hvordan produktet av en 2×3 og en 3×2 matrise beregnes, med fargekoding av radene og kolonnene:

[figur]

En mer "programmeringsaktig" figur, som viser i detalj hvordan produktet av to 3×3 matriser beregnes, kan du se ved å klikke på denne linken.

For å være sikker på at du forstår hvordan produktet av to matriser beregnes, kan du selv prøve å beregne produktet av disse to 3×3 matrisene ("fasiten" er gitt etter likhetstegnet):

[figur]

1.6.2 Implementasjon

Det er laget et relativt enkelt program som gjør matrisemultiplikasjon og beregner C=AB. Siden det er en del mer kode enn de små eksemplene ovenfor, er programmet ikke inkludert i teksten her. Det kan i stedet lastes ned fra denne linken:

I dette programmet ligger alle dataene om matrisene som skal multipliseres globalt tilgjengelig. Dvs. at matrisene A, B og C, og størrelsen på dem, N, er deklarert utenfor funksjonene og main(). De blir dermed tilgjengelige i hele koden, inkludert alle funksjoner, uten at vi trenger å overføre dataene som parametre. For å få litt enklere kode, antar vi at N maksimalt kan være lik 64.

Programmet matrix.c er bygget opp på denne måten:

  • main() kaller først en funksjon les_AB(), som leser inn verdien på N og deretter alle dataene i to kvadratiske N×N matriser A og B med heltall. Dataene leses fra to filer A.txt og B.txt.

  • Deretter beregnes produktet av de to matrisene A og B, med et kall på en funksjon multipliser_AB(). Resultatet/matriseproduktet lagres i C.

  • Merk at funksjonen multipliser_AB() utfører matrisemultiplikasjonen rad for rad i C.

  • Til slutt skrives resultatet i C ut til en ny fil C.txt.

Last ned programmet matrix.c og de to datafilene A.txt og B.txt (som begge inneholder en 64×64 matrise), kompiler og kjør det selv. Du skal skrive om dette programmet til å bruke tråder i en av oppgavene nedenfor.

2 Oppgaver

Nedenfor er det gitt tre oppgaver som skal besvares både med tekst og med C-kode. Du kan gjerne gjenbruke/kopiere deler av C-programmene fra eksemplene ovenfor i din egen kode.

Oppgave 1

Følgende C-program er gitt: 

#include <pthread.h>
#include <stdio.h>
#define N_THREADS 5

int value = 0; // Global variabel som deles av alle tråder

void *count()
{
  int i;
  
  for (i = 0; i < 100000; i++)
     value++;

  printf("%d ", value);
}

int main ()
{
   int i;
   pthread_t thread[N_THREADS];
   
   for(i = 0; i < N_THREADS; i++)
      pthread_create(&thread[i], NULL, count, NULL);
   
   for(i = 0; i < N_THREADS; i++)
     pthread_join(thread[i], NULL);
   
   printf("\n");
}

  1. Kjør programmet gitt ovenfor flere ganger. Inkluder utskriften fra fem påfølgende kjøringer i besvarelsen din, som et skjermbilde eller ved å gjøre klipp-og-lim av teksten.

    Du vil se at tallene som skrives ut av trådene forandrer seg i hver kjøring. Gi en kort forklaring på hvorfor dette skjer.

    Hele svaret på oppgave 1a skriver du inn i et tekstdokument, f.eks. i Word eller en annen tekstbehandler eller editor. Lagre dokumentet som en PDF-fil med navn oblig_5.pdf

  2. Skriv om koden slik at programmet alltid skriver ut:

    100000 200000 300000 400000 500000

    Programmet skal fortsatt starte 5 tråder fra main(). Det er bare koden i main() som du skal endre litt på, resten av programmet skal være uforandret. Programkoden din skal lagres i en fil med navn oppgave_1_b.c.

Oppgave 2

Hele besvarelsen på oppgave 2 skal skrives inn i det samme tekstdokumentet som brukes i oppgave 1a ovenfor, og lagres som et PDF-dokument med navn oblig_5.pdf.

I oppgave 2 skal vi se hvordan tråder kan gjøre et program raskere og mer effektivt. Eksemplet vi skal ta utgangspunkt i er følgende program som ikke gjør noe "fornuftig", men bare kjører en for-løkke et stort antall ganger:

#include <stdio.h>

#define N 1000000000 // 1 milliard    - 10⁹
#define n 100000000  // 100 millioner - 10⁸

void count()
{
   int i;
   for (i = 0; i < N; i++)
     if (i % n == 0)
       printf(".\n");
}

int main ()
{
  count();
  printf("%d iterations completed!\n", N);
}

Vi ser at main() kaller funksjonen count(), som kjører en løkke der løkkevariabelen i "telles opp" fra 0 til en milliard(!). Hver gang løkken har gått 100 millioner ganger, skrives det ut et punktum.

Kompiler og kjør dette programmet. Du vil da se at dette faktisk tar litt tid å kjøre. Selv med dagens superraske gigahertz-prosessorer, vil en milliard addisjoner og if-tester (og litt til) ta noen sekunder å fullføre.

For å måle effektivitet av et program, kan vi se på hvor lang tid programmet bruker for å løse et problem når størrelsen på problemet (antall data) er veldig stort (dette vil dere lære mye mer om i det utmerkede kurset "Algoritmer og datastrukturer" som alle anbefales å ta). Det finnes mange måter å gjøre dette på. I Linux har vi f.eks. en egen kommando, time, som kan brukes i shellet til å måle tidsforbruket til et program.

For å se tidsforbruket til det lille programmet gitt ovenfor, som vi kan anta ligger ferdig kompilert på den eksekverbare filen oppgave_2_1, kan du gi følgende kommando:

time ./oppgave_2_1

Programmet vil da kjøre som normalt, men etter at det er ferdig vil time skrive ut informasjon om tidsforbruket til programmet. På min egen Linux-maskin kan dette se slik ut etter en kjøring:

real	0m2,238s
user	0m2,233s
sys	0m0,000s

time skriver her ut tre tider:

real:
Dette er den faktiske tiden — drøyt 2.2 sekunder — som har gått fra prosessen startet til den er ferdig, kalles også "wall clock time". Dette inkluderer både tiden prosessen har kjørt i CPU, og tiden den har ventet på f.eks. input eller på å få bruke en CPU som er opptatt av andre prosesser.

user:
Tiden som prosessen har fått kjøre i CPU i user mode, når den eksekverer sin egen kode.

sys:
Tiden som prosessen har kjørt kode i kernel mode, typisk utførelse av systemkall. Summen av user og sys er den totale CPU-tiden som prosessen har brukt. Merk at både user og (spesielt) sys kan være null sekunder i utskriften fra time, selv om prosessen har brukt tid både i user og kernel mode. Dette skjer når kjøretidene er så små/korte at de ikke kan måles.

Tiden som et program bruker for å løse et gitt problem avhenger av hvor rask maskinens hardware er, hvilken kompilator og operativsystem som brukes, og hvor opptatt maskinen er med å utføre andre prosesser som er aktive samtidig med vårt program.

  1. Kompiler programmet gitt ovenfor på studentserveren itstud.hiof.no. Kjør det deretter med time for å måle tidsforbruket når det kjøres på serveren. Inkluder utskriften fra time i besvarelsen.

Programmet nedenfor gjør omtrent det samme som det første programmet i denne oppgaven, men det bruker to tråder som begge "teller" til en halv milliard. Hver tråd kjører samme for-løkke som ovenfor, men løkken går fem hundre millioner ganger i hver tråd. Til sammen utfører altså dette programmet nøyaktig like mange operasjoner som det ovenfor — en millard addisjoner og if-tester i for-løkke:

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

#define N 1000000000 // 1 milliard    - 1o⁹
#define n 100000000  // 100 millioner - 10⁸

void *count()
{
  int i, N2 = N/2;
    
  for (i = 0; i < N2; i++)
    if (i % n == 0)
       printf(".\n");
}

int main ()
{
  pthread_t thread_1, thread_2;
  int i;

  pthread_create(&thread_1, NULL, count, NULL);    
  pthread_create(&thread_2, NULL, count, NULL);    

  pthread_join(thread_1, NULL);
  pthread_join(thread_2, NULL);

  printf("%d iterations completed!\n", N);
}

  1. Kompiler også dette programmet på studentserveren itstud.hiof.no. Husk å bruke opsjonen -pthread til gcc. Kjør deretter programmet med time for å måle tidsforbruket når det kjøres på serveren. Inkluder utskriften fra time i besvarelsen din.

  2. Når jeg kjører programmet med to tråder på min maskin, får jeg typisk denne utskriften fra time:

    real	0m1,057s
user	0m2,100s
sys	0m0,000s

    Hvis vi sammenligner med utskriften ovenfor fra programmet som ikke brukte tråder, ser vi at den virkelige tiden som programmet bruker nå er halvert(!). Dette til tross for at CPU-tiden er omtrent den samme, og selv om begge programmer gjør nøyaktig like mye arbeid (en millard operasjoner av ulike typer).

    Du bør få et lignende resultat når du kjører programmet med tråder på itstud.hiof.no, dette avhenger av hvor mye annet serveren har å gjøre. Gi en forklaring på hvorfor trådprogrammet blir omtrent dobbelt så raskt. Hint: Gi kommandoen:

    lscpu | more

    på itstud.hiof.no, og se hvor mange prosessorer/CPU(s) som serveren har.

Oppgave 3

Skriv om programmet for matrisemultiplikasjon fra avsnitt 1.6 ovenfor, matrix.c, slik at det bruker 4 tråder. Hver tråd skal beregne produktet C=AB for en fjerdedel av radene i matrisen C. Lagre det ferdige programmet ditt på en fil som heter oppgave_3.c

Den enkleste måten å få til dette på, er å la hver tråd starte med å kjøre funksjonen multipliser_AB(). Funksjonen må da skrives om noe, slik at den kan brukes som parameter i pthread_create(). Du trenger å gi funksjonen en parameter, som angir hvilken rad i C den skal starte med å beregne. Du må også sørge for at funksjonen ikke beregner mer enn en fjerdedel av radene i C.

Hovedprogrammet main() må også skrives om, slik at det starter alle de fire trådene og deretter venter til de er ferdige før resultatet skrives ut. Du skal ikke trenge å gjøre noe med koden som leser inn og skriver ut matriser til/fra fil.

Det kreves bare at programmet du skriver virker for 4 tråder og 64x64 matriser, som er størrelsen på de to testfilene A.txt og B.txt som er gitt. Men du kan gjerne skrive et mer generelt program som fungerer for ulike antall tråder og matrisestørrelser.

Hva skal du levere?

Svarene på oppgave 1a og oppgave 2 skal lagres som et PDF-dokument, på en fil med navn oblig_5.pdf. Svarene på oppgave 1b og 3 skal lagres på filer med navn hhv. oppgave_1_b.c og oppgave_3.c. C-koden skal kunne kompileres og skal fungere som beskrevet i oppgavetekstene. Innlevering av besvarelsen din gjøres i Canvas ved å laste opp PDF-filen og de to C-filene.