Uke 15 - PowerShell, Java-tråder og synkronisering, deadlock, internminne og konkurransefinale!

Oppgaver til mandag 7. - fredag 11. apr

Aller først denne uken noen flere PowerShell-oppgaver. Dette er noen oppgaver som virkelig viser hvor powerful PowerShell er. De fleste av oppgavene (som ikke er for Windows-spesifikke) kan gjøres med pwsh-shellet på OS-VM. Men husk da å bruke Get-Process og ikke ps samt Get-ChildItem og ikke ls. Hvis du er i tvil, bruk Get-Command ls og tilsvarende hvis du lurer på hvilken commandlet eller kommando som egentilig kjøres. Deretter noen oppgaver der dere dere skal fikse en race condition i et Java tråd-program og gjøre det tråd-sikkert. Så noen utfordringer i form av mer teoretiske oppgaver om mutex-algoritmer. Helt til slutt er det den tiende og siste finaleomgangen i OS-konkurransen! Etter påske blir det premieutdeling under siste forelesning.

PowerShell-oppgavene kan løses ved å bruke pwsh-shellet på os-VMene. Dette shellet er også det samme som dere vil kunne bruke på eksamen.

Det er ikke flere obligatoriske innleveringer, så betrakt oppgaver som er merket (Oblig) som de oppgavene det er viktigst å få med seg i forbredelsene til eksamen.

(Oblig) Lag en PowerShell one-liner som teller opp summen av antall bytes for filene med extension .ps1 i mappen du står i og legger verdien i variabelen $sum (som kan antas å være lik 0 før kommandoen kjøres). (Hint: lov å bruke semikolon slik at resultatet kan skrives ut til slutt). Hvis du ikke klarer å løse oppgaven, spør Sikt-ChatGPT om hjelp.
(Oblig) Skriv en PowerShell oneliner som finner alle filer i mapper og undermapper som har filendelse .ps1.
Skriv et PowerShell script som skriver ut en liste med full path til de ti største filene på C:\ (dvs inkludert alle undermapper).
Lag et PowerShell script som gir en sorter liste med de 25 største filene på C: med mappe-navn, mappe og størrelse i bytes.
(Oblig) Bruk PowerShell til å finne ut hvilken ukedag 17. mai 1814 var.
Skriv et PowerShell-script eller oneliner som lister alle prosesser som kjører nå og som har blitt startet de siste femti minuttene. Og kun med kollonnene for id, ProcessName og StartTime.
(Oblig) Ta utgangspunkt i java-programmet NosynchThread.java fra avsnitt 11.12 i forelesningsnotatene. I java kan man sikre seg mot at en felles variabel ikke blir oppdatert av to threads samtidig ved å lage en kodeblokk
```
synchronized(objekt)
   {
   // Her kan bare en thread av gangen kjøre kode; kritisk avsnitt 
   }
```
Endre java-programmet over ved å først lage
```
    public static Object lock = new Object(); // Et lock-objekt 
```
Og deretter bruke synchronized rundt de kritiske avsnittene i koden til å serialisere NosynchThread.java slik at resultatet blir riktig. Tar programmet lengre tid å kjøre nå? Isåfall: hvorfor? Gjør det noen forskjell om du starter java med taskset -c 0?

Ukens nøtt nr. 1: Vi tar igjen utgangspunkt i NosynchThread.java fra forelesningene der det ble vist at den felles static int variabel Saldo ikke ble synkronisert og at resultatene dermed ble forskjellig fra gang til gang på grunn av en race conditon. Det følgende er et litt anderledes forsøk sammenlignet med ekesempelet i forrige oppgave, på å synkronisere trådene ved å lage synchronized-metoder for å oppdatere saldo:

// Kompileres med javac SynchThreadS.java // Run: java SynchThreadS import java.lang.Thread; class SaldoThreadS extends Thread { static int MAX = 10000000; static int count = 0; public static int saldo; int id,mil; SaldoThreadS(int millisek) { count++; id = count; mil = millisek; } public void run() { try { sleep (mil); } catch (Exception e) { } System.out.println("Thread nr. "+ id +", priority " + getPriority() + " starts"); updateSaldo(); } private synchronized void upSaldo() { saldo++; } private synchronized void downSaldo() { saldo--; } private void updateSaldo() { int i; if(id == 1) { for(i = 1;i < MAX;i++) { upSaldo(); } } else { for(i = 1;i < MAX;i++) { downSaldo(); } } System.out.println("Thread nr. " + id + " finished. Saldo: " + saldo); } } class SynchThreadInt extends Thread { public static void main (String args[]) { int i; System.out.println("Starts two threads!"); SaldoThreadS s1 = new SaldoThreadS(1000); s1.start(); SaldoThreadS s2 = new SaldoThreadS(1000); s2.start(); try{s1.join();} catch (InterruptedException e){} try{s2.join();} catch (InterruptedException e){} System.out.println("Final total saldo: " +SaldoThreadS.saldo); } }

Prøv å kompilere og kjøre denne koden. Det kan være den må kjøres 5-10 ganger eller eventuelt antall runder i løkken må endres, for å se om den likevel ikke er synkronisert. Hvis det viser seg at denne synkroniseringen ikke virker, hva er galt? Hvis du er i tvil om løsningen på problemet, spør Sikt-ChatGPT og prøve å vurdere om svaret er riktig; om mulig ved å teste.

Ukens nøtt nr. 2: De følgende tre oppgavene er av litt mer teoretisk art og en utfordring for de ivrigste. Vi skal se at det ikke er så enkelt å lage en software-løsning for en mutex-algoritme. Andre forsøk på å lage en mutex-algoritme etter det ikke helt tilstrekkelige forsøket fra forelesningen ser slik ut:
```
static int turn = 0; // Felles variabel = 0 eller 1
GetMutex(int t)
   {
   while(turn != t) {}
   }

ReleaseMutex(int t)
   {
   turn = 1-t;
   }
```
For to prosesser med t = 0,1 (pid). Prosess 0 gjør
```
GetMutex(0)
// Kritisk avsnitt
ReleaseMutex(0)
```
og prosess 1 gjør
```
GetMutex(1)
// Kritisk avsnitt
ReleaseMutex(1)
```
turn: hvem sin tur? turn = 0 -> prosess 0 sin tur. Vil dette sikre at gjensidig utelukkelse (mutal exclusion) er oppfylt? I såfall, er det noe annent som gjør algoritmen ubrukelig?

Ukens nøtt nr. 3: Forsøk 3 på software mutex-algoritme:

static boolean[] flag = new boolean[2]; // Begge false i utgangspunktet
GetMutex(int t)
   {
   int other;
   other = 1 - t;
   flag[t] = true; // Ønsker å gå inn i kritisk avsnitt
   while (flag[other] == true){}
   }
 
ReleaseMutex(int t)
   {
   flag[t] = false;
   }

Sikrer den at prosessene 0 og 1 aldri kommer samtidig inn i kritisk avsnitt? Hvis algoritmen gjør det, hva er det som likevel gjør den ubrukelig?

Ukens nøtt nr. 4: Peterson-algoritmen(se Tanenbaum) er en meget elegant softwareløsning av mutex-problemet. Det fantes løsninger før den ble funnet i 1981, men de var meget kompliserte. Den er en blanding av forsøk 2 og 3 og ser slik ut:
```
static boolean[] flag = new boolean[2]; // Begge false i utgangspunktet
static int turn = 0;

GetMutex(int t)
   {
   int other;
   other = 1 - t;
   flag[t] = true; // Ønsker å gå inn i kritisk avsnitt
   turn = other;   // Viktig
   while (flag[other] == true && turn == other){}
   }

ReleaseMutex(int t)
   {
   flag[t] = false;
   }
```
Overbevis deg selv om hvordan og hvorfor den alltid virker, uansett når en Contex Switch intreffer.
Problem 2.22 i Tanenbaum. Virker Petersons mutex-løsning når prosess-schedulingen er preemptive? Hva om den er ikke-preemptive?

(Oblig) Ta igjen utganspunkt i NosynchThread.java. Anta nå at vi lager to lock-objekter:

public static Object lock1 = new Object();
public static Object lock2 = new Object();

og at trådene skal utføre følgende kode

         if(id == 1)
            {
	    for(i = 1;i < MAX;i++) 
		synchronized(lock1)
		   {
		   saldo1++;
		   synchronized(lock2)
		      {
		      saldo2++;
		      }
		   }
	    }
         else
            {
	    for(i = 1;i < MAX;i++) 
		synchronized(lock2)
		   {
		   saldo2--;
		   synchronized(lock1)
		      {
		      saldo1--;
		      }
		   }
            }

der tråd nr. 2 skal utføre det tilsvarende, men i motsatt rekkefølge (først saldo2, så saldo1). Endre programmet og kjør det. Hva slags situasjon har programmet ditt kommet opp i nå? Gjør Java noe for å hjelpe programet ut av denne situasjonen?

(Oblig) Hva er forskjellen på en fysisk adresse og en virtuell adresse?
(Problem 1.12 i Tanenbaum): Tenk deg en datamaskin som har cache, internminne (RAM) og disk, og et operativsystem som bruker virtuelt minne. Anta at det tar 2 nanosekunder (ns) å hente en byte fra cache, 10 ns å hente en byte fra RAM, og 10 ms (millisekunder) å hente en byte fra disken. Hvis cache hit-rate er 95% internminne hit-rate (etter en cache miss) er 99%, hvor lang tid tar det da i gjennomsnitt å hente en byte på dette systemet?
(Oblig) Bruk page-tabellen i avsnitt 13.11 i forelesningsnotatene, Figure 3-10 i Tanenbaum. Gi den fysiske adressen som korresponderer til følgende virtuelle adresser: a) 500) 18010) 46512
(Oblig) CPU utfører en x86-instruksjon som henter en byte fra RAM og legger den i et register. Vil CPU-cache kunne involveres når denne instruksjonen utføres?
(Oblig) CPU utfører en x86-instruksjon som sammenligner tallene i to registere. Vil CPU-cache kunne involveres når denne instruksjonen utføres?
(Oblig) En liten CPU bruker 10-bits registere til å adressere en byte i internminnet. Hvor stort er da det virtuelle adresserommet som kan adresseres med disse 10-bit adressene?
(Oblig) Det virtuelle adresserommet for alle prosesser på det samme systemet er delt inn i sider (pages) med en sidestørrelse på 128 bytes. Hvor mange sider utgjør det virtuelle adresserommet til en prosess?
(Oblig) Denne oppgaven er den siste og idag er det dermed finale hvor det avgjøres hvem som blir de tre beste. Etter påske blir det premieutdeling med premier til de tre beste! Denne ukens oppgave kan egentlig løses på en hvilken som helst server som kjører docker og for eksempel på s-serveren eller på os-serveren. Du skal laste ned fra repositoriet haugerud/steg på Dockerhub en versjon av steg-containeren som har samme tag/versjonsnummer som din s-gruppe. For eksempel versjonsnummer s68 om du har s-nummer 68 på s-serveren. Se mer om hvordan man laster ned containere i avsnitt 9.2 Dockerhub i forelesningsnotatene. Deretter skal du starte denne containeren som er en nginx webserver. Når du kobler deg til denne webserveren vil index.html inneholde et bilde og noen hint om hvordan du kan finne en 10-tegns kode med tilfeldige tegn som viser at du har løst oppgaven. Koden er på en helt spesiell måte gjemt inne i bildet som webserveren viser og navnet på repositoriet er et hint om hva denne metoden kalles. På gruppens os-server er det med apt-get installert et program som må brukes for å kunne løse denne vanskelige oppgaven. Du må også finne en pass-phrase for å kunne komme helt i mål, men all info du trenger finnes på webserveren.
For å sjekke at du har funnet rette streng, skriv inn koden på siden os.php uke 15 og du får beskjed om du har skrevet riktig. I tilegg blir du da med på siste runde i konkurransen om å finne denne koden fortest mulig!