IT-Programmet, Tema 1 i termin 4:

TTIT61 Processprogrammering och Operativ System

/Concurrent Programming and Operating Systems/

---

Den C/C++ som behövs för Nachos

Följande är en liten introduktion till C och i viss liten mån C++, författad för studenter som skall laborera med Nachos och som har en bakgrund i Java. Introduktionen är på intet sätt komplett, eller ens fullt detaljerad i de delar som beskrivs.

Innehåll

• Enkla datatyper, globala och lokala variabler
• Sammansatta datatyper
• Referenser, pekare och adresser
• Arrayer och pekare
• Strängar
• C++-klasser, metoder och annat
  
• New och Delete - att allokera eller inte allokera
• Spårutskrifter, macron och debugger
• Avslutningsvis...
  

Enkla datatyper, globala och lokala variabler

Ett C-program består i princip av tre saker:

• deklarationer av datatyper
• definition av de globala variabler ett program skall innehålla
• defintion av de funktioner programmet innehåller

En av funktionerna måste heta main för att det skall bli ett program, och det är den som kommer att köras när programmet startar. Följande är ett exempel på ett komplett litet program:

  #include <stdio.h>   /* Inkludera deklarationer för bl.a. printf */
  int a;               /* Definiera en global heltalsvariabel a    */
  int b = 0;           /* definiera en till, med initialt värde 0  */

  void main() {              /* En 'funktion' som inte returnerar något (void) */ 
    printf("Hello world\n"); /* ...men som skriver ut en textrad               */
  }

Globala variabler skall betraktas som oinitialiserade (dvs har inget kännt värde) om vi inte som med b explicit anger ett initialt värde. Nu brukar kompilatorn se till att de blir 0 ändå - och det är bra för det mesta.

Funktionen main skall (på ett Unix-system) egentligen vara av typen int och returnera ett värde som anger programets "exit-status", där konventionen säger att 0 som returnvärde betyder att allt gick bra, övriga heltal anger någon form av felkod. Programmet ovan gör inte det, och vi får en varning av kompilatorn när vi skriver

  gcc hithere.c -o hithere

...för att kompilera filen hithere.c och döpa det körbara programmet till hithere.

De viktigaste enkla inbyggda datatyper som finns i C (och då räknar vi inte alla de vi kan hitta i diverse bibliotek av tillbehör till språket) är:

• char - en 8-bitars byte som (normal) innehåller ett ascII-tecken
  
• short int, int, long int - olika representationer av heltal
  
• float, double - olika stora reella tal
  

Normalt är variabler av heltalstyp och flyttalstyp kodade så att både negativa och possitiva värden kan lagras. Om en variabel innehåller t.ex. det största heltalet som kan representeras och vi adderar 1, så kommer den därefter att innehålla det minsta värdet (dvs dets största negativa värdet) som samma datatyp kan representera. I vissa situationer har vi dock inget behov av de negativa värdena, och vill då istället kunna handskas med dubbelt så stora possitiva värden. Detta kan vi åstadkomma med tillägget unsigned i variabeldeklarationen:

 unsigned int a = 0;

I många system motsvaras en char av en unsigned short - men se upp, det gäller inte alltid. Det går dock alltid bra att skriva nedanstående (emedan det omvända kan leda till att du förlorar information):

 char a = 'A';
 unsigned short b = 66;
 b = a;                  /* a = b blir bra så länge b < 256  */

Vi kan även definiera nya enkla datatyper för att representera en ändlig (och vanligen liten) mängd alternativ, som t.ex. hur vi kryssar i en tippsrad eller vilken dag i veckan det är:

 enum tippsRad {ett, kryss, tvo, ettkryss, krysstvo, etttvo, helgardering};
 enum veckodag {mondag, tisdag, onsdag, torsdag, fredag, lordag, sondag);

Normalt kommer kompilatorn att representera dessa värden med heltalen 0 t.o.m. (i dessa exempel) 6, men vi kan själva ange vilken representation vi vill ha (så länge vi håller oss till heltal):

 enum tippsRad {ett=1, kryss=2, tvo=4, ettkryss=3, krysstvo=6, etttvo=5, helgardering=7};

...för med en sådan representation så kan vi ju använda bit-visa and och or funktioner för att jämföra med ett facit. Dessa värden kan även betraktas som programkonstanter och kan användas i deklarationer av t.ex. arrayer.

Vi deklarerar variabler av enum typ med hjälp av det namn vi angett:

 veckodag idag = tisdag;

I C fanns ursprungligen ingen datatyp för att representera sant och falsk - man valde heltalet 0 som falskt och alla andra heltal som sant. Med C++ kom dock en datatyp kallad bool med värden true och false. Den motsvaras av deklarationen:

 enum bool {false = 0, true = 1};

I de program där ni ser TRUE och FALSE användas (med stora bokstäver) finns det troligtvis någonstans en macro-definition som gör att alla dessa byts ut mot 1 respektive 0 som ett första steg i kompileringsprocessen.

Än idag gäller att 0 alltid tolkas som falskt om vi betraktar det som ett boolskt värde - något vi återkommer till när vi pratar om arrayer och strängar senare.

Sammansatta datatyper

I C finns två typer av sammansatta datatyper (dvs de består av mer än en del):

• struct - vi grupperar ett antal data av olika typ och vill behandla dem som en enhet - det finns speciell syntax och speciella reserverade ord för detta. Jämför med en klass i Java, fast där du endast kan ha publika medlemsvariabler (inga metoder, inga privata delar och inga statiska delar).
  
• array - vi vill hålla i många element av samma typ - som i Java så används speciell syntax men inga nya reserverade ord. Dock, i C är en array väldigt rudimentär jämfört med javas objekt som själv vet hur många element den rymmer etc. Arrayer behandlas separat senare.

Vi kan nu deklarera en ny datatyp enligt följande:

 typedef struct {
   int x;
   int y;
 } position;

...och därefter använda den i vårt program:

 void main() {
    position p1;

    p1.x = 10;
    p1.y =  p1.x + 5;
    printf("Positionen är <%i,%i>\n", p1.x, p1.y);
 }

När vi kör detta program skrivs följande rad ut på skärmen:

  Positionen är <10,15>

Som synes måste vi själva formattera utskriften av varje del, det finns inget inbyggt stöd för att skriva ut en hel struct. Man får läsa på om hur man formatterar olika datatyper med hjälp av printf och dess kusiner fprintf och sprintf i t.ex. de man-sidor dom finns på varje Unix-system.

Med C++ kom även ett nytt sätt att hantera in- och ut-matning. Utskriften ovan kan nu även genereras med C++ raden:

  #include <iostream>
  cout << "Positionene är <" p1.x << "," << p1.y << ">" << eoln;

Referenser, pekare och addresser

När vi anropar en funktion i C så kopieras alltid data in till funktionen. Och har vi ett returvärde så kopieras returvärdet tillbaka ut ur funktionen. Fördelen är att vi tryggt kan anropa en funktion med ett beräknat värde eller en konstant eller en variabel (dvs värdet av variabeln) utan att vara rädda för att funktionen av misstag kan ändra detta värde för oss. Nackdelen är att om det är stora data (t.ex. en mycket stor struct) så tar det kanske onödig tid att kopiera den vid varje anrop. Eftersom vi endast kan returnera data av enkla datatyper så kan vi aldrig returnera structar eller arrayer från en funktion. Och när vi kommer till C++ objektinstanser så är det sällan så att vi villkopiera dem - även om många gör det ibland ändå (av misstag).

Men om vi vill ändra på värdena i de variabler vi anroper funktionen med? Hur skriver vi funktionen swap som byter plats på värdena i två variabler?

 int x = 10, y = 20;

 void swap(int a, int b) {    /* en funktion som tar två heltal som argument */
    int tmp = a;
    a = b;
    b = tmp;
 }

 /* Inne i main:  */
 swap(x, y);                  /* ...detta blir inte det vi vill! */

Lösningen är att inte kopiera in värdet på variablerna på vars värden vi vill byta plats, utan istället kopiera in adresserna till var dessa variabler finns i minnet, och sedan använda dessa adresser för att hämta och byta plats på värdena:

 int x = 10, y = 20;

 void swap(int *ap, int *bp) {  /* en funktion som tar två adresser (eller pekare) */
    int tmp = *ap;              /* till heltalsvariabler som argument.             */
    *ap = *bp;                  /* Vi måste plasera en * framför namnet för att    */
    *bp = tmp;                  /* komma åt det som adresseras/pekas på            */
 }

 /* Inne i main:  */
 swap(&x, &y);                  /* Med & skickar vi in adresserna till variablerna, */
                                /* och då blir det som vi vill!                     */

När vi (som i exemplet ovan) deklarerar heltalsvariablerna x och y, skapas det alltså av kompilatorn plats i minnet för dessa heltal. men vi kan välja att enbart deklarera variabler som kan hålla adresser till minnesplatser, minnesplatser vari heltal skall lagras:

 int *xp, *yp;

Vi kan inte använda dessa variabler - dom innehåller bara motsvarigheten till adressen 0 - inte heltalet 0. I traditionell C var vi nu tvungna att manuellt be om (dvs skriva egen kod för att få) mer minne, precis så mycket så att ett heltal skulle få plats:

 xp = (int*)malloc(sizeof(int));  /* Allokera minne för ett heltal, spara adressen i variabeln xp. */
 *xp = 5;                         /* I platsen som xp pekar på, lagra talet 5.                     */

Uttrycket (int*) används för att för kompilatorn markera att adressen gäller en plats för ett heltal, och inte "adress till något okänt" som void* betyder - vilket är returtypen på malloc. Om vi nu använder en C- och C++-kompilator kan vi istället skriva

 *xp = new int(5);                /* ...nästan precis som i Java!  */

När vi nu har våra två addressvariabler (pekarvariabler) xp och yp kan (och skall) vi direkt skriva:

 swap(xp, yp);

Det som sagts här ovan gäller alla enkla typer och alla som är baserad på konstruktionen struct (och objektsinstanser, men det återkommer vi till). Med arrayer fungerar det på ett annat sätt.

Arrayer och pekare

På motsvarande sätt som i Java kan vi deklarera variabler av en viss bastyp:

 int a[100];                        /* Plats för 100 heltal    */
 float b[10];                       /* Plats för 10 reella tal */
 char line[80];                     /* Plats för 80 tecken     */
 char tmp[] = "En temporär sträng"; /* Plats för 19 tecken!!   */
 int *a[5];                         /* Plats för 5 pekare till heltal */

Dom enda datatyper som ofta och vanligen blir så stora att det blir märkbart slött att kopiera dom in till varje funktion är arrayerna - vi kan ju med lätthet säga att vi skall ha en array med plats för 10000 heltal - och det tar lite plats och därmed tid att kopiera. Sannolikt därför har man i C valt att inte låta kompilatorn direkt skapa utrymme för hela arrayen och låta t.ex. variabeln a markera detta utrymme. Nix - man låter istället kompilatorn skapa en plats för en pekare (adressen) till en annan plats som skapast för hela datamängden - och sedan låter man kompilatorn fixa till detta överallt där vi använder arrayen i vårt program. Följande rader ger alltså samma resultat, vi skapar en array med plats för 100 heltal:

 int a[100];
 int *a = (int*)malloc(100*sizeof(int));
 int a[] = new int[100];                  /* Bara om kompilatorn även klarar C++ */

En funktion som skall ta två arrayer som argument (och kopiera från den ena till den andra) skriver vi därefter på ett av följande sätt:

void arrCopy(int a[], int b[], int len) { for(int i=0; i<len; i++) { b[i] = a[i]; } } Alternativ A

void arrCopy(int *a, int *b, int len) { for(int i=0; i<len; i++) { *(b+i) = *(a+i); } } Alternativ B

void arrCopy(int *a, int *b, int len) { for(int i=0; i<len; i++) { *b++ = *a++; } } Alternativ C

I alternativ A använder vi array-syntax och allt blir tydligt och klart. I alternativ B skriver vi det som kompilatorn översätter alternativ A till - dvs vi vet att a inehåller adressen till ett (eller flera) heltal, och att i en array så placeras alla elementen ut i sekvens efter varandra i minnet vilket betyder att första talet ligger direkt där a pekar, andra talet ligger "ett snäpp längre fram"... dvs (a+1) skall alltså bli addressen till andra elementet i arrayen a. Att detta fungerar beror på att C-kompilatorn alltid adderar med storleken på det element som pekas ut. Därför är det viktigt att vi typar pekarna - det blir ju skillnad om vi har char*+1 eller float*+1 eftersom dessa typer tar så olika stor plats. Detta brukar kallas pekararitmetik och är rätt speciellt för C.

I alternativ C har vi den kod som en spelprogrammerare eller annan person som räknar varje slösad CPU-cykel som ett nederlag skulle skriva. För varför skall vi hela tiden plocka fram ett i och addera till ett fast a eller b - vi kan ju låta dessa pekare/addresser succesivt stegas upp genom arrayerna - det blir nog två assemblerinstruktioner mindre inne i for-loopen! ...kanske? Vi skall dock strax se hur detta kan effektiviseras ytterligare!

VARNING NR.1

Det är nu dags för en varning. Vad händer om vi i for-looparna ovan kontrollerar mot i<=len istället för som det står nu? Jo, vi kommer att även pilla på en plats i minnet som ligger efter det sista elementet i repektive array. Vi har inget skyddsnät som "vet" hur stor arrayen är, var den börjar och slutar och att vi håller oss däremellan. Många C-kompilatorer kan fås att generea sådan extrakod för att utföra sådana kontroller - men då måste man explicit säga till att sådant skall kontrolleras.

Strängar

En teckensträng som "kalle" är i C (och C++) inget annat än en array med plats för sex stycken tecken - inte fem! Kompilatorn lägger nämligen alltid till ett sjätte tecken, och detta 'tecken' är alltid talet 0.  Vi kan få in  det själva genom att skriva:

 char *str = "två\0 strängar" ;

Här har vi, med hjälp av tecknet '\', angett att vi vill stoppa in teckenkoden 0 och inte ascII-koden för skrivtecknet '0'. Som en konvention så tolkas alltid '\t' som ett tab-tecken, '\n' som ett radslutstecken osv (det finns ytterligare några sådana).

Varför avsluta med en nolla? Jo, det betyder ju även 'falskt', och allt som inte är 0 är ju 'sant'. Om vår arraykopieringsfunktion i alternativ C ovan vore till för strängar skulle vi alltså kunna skippa argumentet len och titta på när strängen är slut:

 void strCopy(char *str1, char *str2) {
  while(*str2++ = *str1++);
}

Att på detta sätt lita på att det står ett speciellt värde i slutet av datamängden gör att vi kan spara in någon operation i varje varv i loopen vilket för stora data sparar märkbart med tid. I detta fall slipper vi räkna upp ett i hela tiden, och vi använder retur-värdet av tilldelningen för att styra while-loopen. Den markör vi placerar sist i datamängden kalls för sentinell, och tekniken att sätta ut sådana används flitigt i effektiva sorteringsalgoritmer och liknande.

Och nej, det saknas ingen kod i exemplet ovan. Det som händer är att först hämtas värdet som str1 pekar på, sedan räknas pekaren upp. Därefter tilldelas platsen som str2 pekar på det nyss beräknade värdet. Sen räknas pekaren str2 upp ett steg. Och hela tilldelningsuttrycket returnerar det värde som tilldelades - vilket om det var 0 får while-loopen att stanna.

VARNING NR.2

I den alternativa lösningen så är det fortfarande bara längden på första strängen som det tas hänsyn till. Om mottagarsträngen egntligen inte har plats för alla tecknen och användaren av denna förväntar sig att den skall innehålla  t.ex. max 10 tecken, så litar ju denna användare på att det står ett '\0' på plats nummer 11. Och det kan vi ju ha förstört med vår kopieringsfunktion. Någonstans på en helt annan plats i ert program kommer detta fel troligen att ställa till med problem....

Knappa t.ex. in följande program och se vad det skriver ut:

#include <stdio.h>
char buff1[] = "Fun";
char buff2[] = "World Is Not Big Enoug";

char* strCopy(char *s1, char *s2) {
  while(*s2++ = *s1++);
  return s2;
}

void main() {
  printf("%s %s\n", strCopy("Hello - The", buff1), buff2);
}

Visst, det är exterm-fult och fel att använda en konstantsträng (som buff1) som en teckenbuffert och sedan ändra dess innehåll. Men det illustrerar problemet -  om man skriver som man skall (dvs char buff1[4];) så uppstår inte problemet i just detta program och vi har ingen aning om var i minnet vi skrev över...

Måste jag använda pekararitmetik?

Om  ni nu skall skriva en funktion som kopierar tecken från en strängbuffert till en annan, så kommer den troligen att vara deklarerad som:

  void moveChars(char *s1, char *s2);   /* Copy chars from s1 to s2 */

...eller som:

  char* moveChars(char *s1, char *s2);  /* Copy chars from s1 to s2, return s2 */

I det senare fallet förväntas även att s2 (som ju är en pekare/adress/referens!) returneras av funktionen, vilket är användbart ibland.

När ni nu skall skriva definitionen för denna funktion så kan ni välja array-syntaxen istället - det var ju ekvivalenta uttryckssät:

  void moveChars(char s1[], char s2[]) {
     int i=0;
     while(s1[i]) {     /* Vi delar upp vårt uttryck och testar här explicit... */
        s2[i] = s1[i];  /* ...och här kopierar vi endast...                     */
        i++;            /* ...och här räknar vi upp. Totalt sett mer läsbart!   */
     }
  }

...och ni kan arbeta med index och slipper fundera på om *s1++ betyder (*s1)++ eller *(s1++) och liknande struligheter.

C++ -- Klasser, metoder och annat

Vid införandet av C++ bestämde man sig för att utöka (inte någonstans ändra) syntaxen för C. De gammla structarna finns kvar, men är detsamma som klassdefinitioner med bara publika medlemsvariabler. Dessutom kan man nu stoppa in metoder i en struct - de kommer alla att vara publika.

Men, man har även lagt till det reserverade ordet class för att deklarera klasser - för er Java-hackers borde det kännas igen eftersom Java har skapats som en uppstädad och förbättrad variant av C++.

Ni finner en lite utförligare snabbgenomgång av hur klasser deklareras (och används) här. Att använda dem ser ut som i Java; men fungerar bara nästan som i Java (där vi nästan alltid arbetar med referenser, dvs pekare). I C/C++ fungerar det som med structar:

  MyThing m;
  MyThing *mp = new MyThing();

I första fallet får vi alltså en variabel m som verkligen innehåller en hel instans av klassen MyThing. Men se upp! Om ni anropar en funktion eller metod med denna som argument så kopieras den och ni får en ny instans inne i funktionen/metoden! På nästa rad som ser så Java-lik ut (om det inte vore för '*') så får vi en pekare till en MyThing instans. Och vi kan naturligtvis med olika konstruktorer skapa den på olika sätt med parametrar etc.

Om vi nu vill komma åt data (medlemsvariabler) och metoder i instansen m, så skriver vi:

  m.width = 5;                 /* Pilla på en publik instansvariabel */
  m.computeSomething("now");   /* Anropa en metod i objektet         */

När vi har en pekare till objektet måste vi dereferera (följa pekaren) innan själva metoden/variabeln kan kommas åt (precis som om vi hade en pekare till en struct):

  (*mp).width = 5;
  (*mp).computeSomething("later");

Att parenteserna behövs har att göra med att prioriteten på operatorerna egentligen är skapad för att göra något annat än det vi vill just nu. Men då detta är en vanlig användning finns en alternativ syntax:

  mp->width = 5;
  mp->computeSomething("nice");

New och Delete - att allokera eller inte allokera...

Från tid till annan behöver man någon mellanvariabel med en storlek man inte känner till i förväg. Då kan man skapa den i runtime (dvs under körning) och sedan se till att den slängs bort direkt efteråt igen (när vi inte längre behöver den):

   void doSomething(int size) {
1      char *tmp1 = new char[1024];   // Oftast onödig, använd rad 2 istället
2      char tmp2[1024];
3      char *tmp3 = new char[size];
4      MyStuff *tmp4 = new MyStuff(); // Oftast onödig, använd rad 5 istället
5      MyStuff tmp5;
       ...

På rad 1 skapar vi en array med en fast storlek. Men vi skapar den på ett sådant sätt att vi själva måste ta bort den mha följande rad:

       delete[] tmp1;

Har vi använt [] när vi skapade en sak med new, så måste vi göra det när vi tar bort objektet också! Glömmer vi att ta bort den, eller
tar bort den på fel sätt kan de mest mystiska fel uppstå senare i programmet. Eftersom storleken på vår variabel är känd i förväg kan vi dock oftast skriva som på rad 2 istället, och slipper då problemet med delete.
På rad 2 så låter vi variablen skapas automatisk i vår procedur, och utrymmet för den kommer också att försvinna automatiskt när vi lämnar proceduren (eller metoden). Mycket användbart för alla temporära data med fast storlek, om de inte är väldigt stora förståss...

På rad 3 har vi inget val - vi känner inte till storleken i förväg. Glöm inte att anropa delete på rätt sätt!

Rad 5 är en variant på rad 2, vi skapar ett objekt på plats. Det kräver dock att det finns en konstruktor utan argument som kan användas. Vill man initiera något mer så får man stoppa in en metod för detta och anropa den i början på proceduren:

        tmp5.init("initiala data");

Rad 4 behövs alltså bara i undantagsfall, och måste senare åtföljas av ett anrop till delete:

        delete tmp2;

...vilket ni slipper om ni skriver som på rad 5.

Spårutskrifter, macron och debugger

Det är ofta lurigt att felsöka ett program om man inte vet vad som händer. Ett sätt att ta reda på det är att på olika ställen i programmet skriva ut små meddelanden. Om vi håller oss till vanlig C så använder man t.ex. printf() för att skriva ut saker:

      printf("En sträng med argumentplatser som %d och %s och ett radslut:\n", 47, "procent-s");

Första argumentet är en vanlig textsträng, men i den kan man ha symboler (oftast en bokstav med ett % framför) som skall bytas ut mot andra värden som heltal, flyttal, andra strängar etc. Värdena hämtas från argumenten som kommer efter textsträngen, i exemplet ovan först heltalet 47 och därefter en annan sträng. Radslut måste man stoppa in själv. Resultatet blir:

      En sträng med argumentplatser som 47 och procent-s och ett radslut:

I man-sidan för ett Unix-system kan man för printf() läsa mer om alla formatsymboler, men %d för heltal och %s för strängar är de ni behöver mest. Man kan även ange att utskriften skall ske med tex minst 6 tecken, då skriver man %6d och får alla talen högerjusterade med så många blanktecken före att det blir en utskrift om totalt minnst 6 skrivtecken (själva talet kan ju behöva mer än 6 tecken!).

 I C++ kan vi använda allt från C men dessutom skriva ut till terminalen (strömen cout) med hjälp av operatorn << på följande sätt:

      cout << "en sträng" <<  integerVariable << 56,6 << eol;

Hur gör vi om vi vill stänga av utskrifterna under en demo och bara ha dom på när vi felsöker? Svaret är att i C (och C++) kan vi utnytja den pre-processor som tolkar alla #-kommandon i kodfilerna till detta. Om vi t.ex. skriver följande rad i början av en fil:

      #define TRACE1(msg)    printf("Inside file XXX: %s\n", msg)

...så kan vi använda detta macro i vår kod:

      blabla();
      TRACE1("mellan bla och blä");
      bläblä();

...och pre-processorn kommer automatiskt att expandera macrot (ersätta det med den text vi skrev i definitionen) och kompilatorn kommer egentligen att  kompilera följande kod:

      blabla();
      printf("Inside file XXX: %s\n", "mellan bla och blä");
      bläblä();

En onödig omväg kan tyckas, men vad händer om vi i början av filen sedan ändrar så att det står:

      // #define TRACE1(msg)    printf("Inside file XXX: %s\n", msg)
      #define TRACE1(msg)

Jo, då (vid nästa kompilering) byts ju alla våra anrop till TRACE ut mot en tom rad! Och vi slipper alla utskrifter!

Ett varningens ord bara, ni kan ju vilja köra en debugger på Nachos-koden. Debuggern ser ju inte macron (det ni skrivit), den ser det som har blivit när alla macron ersats med riktig kod. Har man knepiga macron kan det bli knepigt attse vad koden gör...

Avslutningsvis...

Så - det var allt för nu. I Nachos-labbarna kommer ni med största sanolikhet inte att själva skapa nya klasser, det är bra nog om ni använder de befintliga på rätt sätt. Därför avslutas denna guide här - kommer du/ni/vi på att något mer borde stå här - tveka inte att lämna synpunkter och bidrag till kursledningen.

Peter Loborg, Linköping 2004.