Omlaboration 2: Schedulering

Introduktion

Denna laboration har som syfte att ge en inblick i hur fördelning av CPU-tid kan göras. Eftersom institutionen inte har möjlighet att tillhandahålla hårdvara till alla studenter, i form av personliga datorer som man kan manipulera på en hårdvarunära nivå, blir laborationen mer av en simulering. Tanken är att uppgiften ska ge en inblick i hur en, något förenklad, preemptive schedulerare kan fungera.

Regler och förordningar

Laborationen lämnas in för bedömning till någon av handledarna. För att laborationen ska godkännas (G) krävs att programmet fungerar korrekt samt en utförlig rapport som analyserar och dokumenterar lösningen. I övrigt gäller att mindre oklarheter (K) medför muntlig förklaring eller kommentar. Felaktigheter eller brister i rapport eller program (O) medför ny inlämning av korrigerad rapport eller program. Om "fusk" eller liknande upptäcks, kommer lämpliga åtgärder att vidtas och laborationen kommer att betraktas som underkänd (U).

Problemspecifikation

Din uppgift i denna laboration är att, i C eller C++, implementera ett program som schedulerar fiktiva program, vars format beskrivs senare. Scheduleraren ska vara preemptive, d.v.s. med jämna mellanrum ska det program som för närvarande körs avbrytas och ett nytt program väljs ut bland de som finns tillgängliga.

Format på program som ska scheduleras

De program som ska scheduleras är inga riktiga program, utan endast textfiler med följande format:

Rad 1 innehåller antalet instruktioner i filen

 

Rad 2 innehåller prioriteten för detta program, (1..100)

 

Övriga rader innehåller ett heltal/rad som utgör en instruktion. Antalet rader bestäms av filens första rad. Varje instruktion är alltid ett positivt tal som är mindre än det totala antalet instruktioner

Nedan visas ett litet exempel på hur ett fiktivt program kan tänkas se ut.

   10
   4
   7
   5
   8
   2
   9
   4
   6
   5
   7
   8

Hur exekveras de fiktiva programmen?

Den klart mest berättigade frågan i detta skede är hur dessa program ska exekveras. Exekveringen är egentligen mycket primitiv, men från ett operativsystems synvinkel är ofta själva exekveringen ganska elementär, eftersom mycket sköts av hårdvaran.

Exekveringen av ett program sker enligt följande:

1. Börja med den första instruktionen
2. Om aktuell instruktion är 0 har programmet kört klart
3. I annat fall:
   1. Lägg till värdet av aktuell instruktion till den totala summan av exekverade instruktioner
   2. Räkna ned aktuell instruktion ett steg
   3. Sätt nästa aktuella instruktion till den instruktion vars index är aktuell instruktions nya värde
4. Upprepa från punkt 2

Som man kan se ska scheduleraren summera instruktionerna för varje program. När ett program har kört klart ska scheduleraren skriva lite information om exekveringen på standard output, vars format beskrivs senare.

Hur vet scheduleraren vilka program den ska köra?

För att få ett system som är någorlunda realistiskt måste naturligtvis scheduleraren kunna instrueras till att exekvera olika program. I denna laboration ska detta lösas med att scheduleraren vid kontextbyten kontrollerar om det finns indata på dess standard input. Om det finns indata ska scheduleraren läsa denna data, som ska bestå av sökvägar till de filer som ska köras (en sökväg/rad). Om flera rader anlänt till standard input ska scheduleraren läsa samtliga dessa och beakta till kommande scheduleringar.

Utdata från scheduleraren

I det normala fallet ska scheduleraren endast, för varje färdigt program, skriva ut antalet exekverade instruktioner, ett tabulatortecken, slutsumman för programmet, ett tabulatortecken samt sökvägen till programmet (och en radbrytning naturligtvis).

Förutom denna utdata ska scheduleraren kunna kompileras till ett debugläge med make debug. I detta debugläge ska, förutom den ordinarie utskriften, följande skrivas ut:

• Vid schedulering ska en utskrift enligt Scheduling 7 tasks göras då scheduleringen ska inledas (förutsatt att det finns just 7 jobb att välja mellan)
• Då ett jobb valts av scheduleraren ska utskriften Chose ./program förutsatt att det valda programmets sökväg angivits som ./program
• Då ett jobb blir avbrutet ska utskriften Interrupted ./program göras

Ni ska även ha stöd för ett läge som genererar ännu mer utskrifter, som ska erhållas med make verbose. I detta läge ska scheduleraren, förutom de utskrifter som genereras i debugläge, för varje instruktion som exekveras göra utskrifter enligt följande format:

• Högerjusterat med bredd 8 skrivs vilken instruktion i ordningen aktuell instruktion är (alltså hur många instruktioner har exekverats före + 1)
• Högerjusterat med bredd 8 skrivs ut vilket index aktuell instruktion har
• Högerjusterat med bredd 8 skrivs ut vilket värde aktuell instruktion har
• Radbrytning

En del av utdata från en körning i verbose-läge skulle kunna se ut enligt:

Scheduling 1 tasks
Chose ./program1
       1       0       29
       2      28       78
       3      77       81
...
    1043      86       29
Interrupted ./program1
Scheduling 1 tasks
Chose ./program1
    1044      28       17
...
    1809      40       65
1810    100377  ./program1

Schedulering och prioritet

Varje program har en given prioritetsnivå. Vid schedulering väljs det program som har störst vikt. Denna vikt ska bestämmas utifrån prioritet och väntetid. Då ett program kommer in i systemet är vikten 0. Vid schedulering ökar alla programs vikt med motsvarande programs prioritet. När det program med störst vikt valts sätts dess vikt till 0 och den börjar exekvera. Detta innebär att program som får vänta får högre prioritet för varje schedulering som görs.

Tips

• Skriv ett litet enkelt program som genererar fiktiva program
• Kolla upp finkänsliga timers, t.ex. setitimer(2) eller ualarm(3c)

Redovisning

Godkänd senast den 29:e augusti är en exekverbar schedulerare vars namn är cpusched. Samtliga filer som ingår i lösningen ska ligga i katalogen edu/os/omlab2 på ditt Unix-konto. Filer som matchar *.[ch]*, d.v.s. alla filer vars namn innehåller .c eller .h kommer att antas vara källkod som ingår i din lösning. Förutom källkoden ska även en fungerande Makefile finnas tillgänglig. Denna makefile ska kompilera din lösning och med argumenten debug respektive verbose kompilera din lösning i de två debuglägen som beskrivits tidigare.

Dessutom ska senast vid samma tidpunkt en välskriven rapport, som noggrannt beskriver din lösning, blivit godkänd.

För kännedom