PSS (F2008) Miniprojekt

Det overordnede formål med miniprojektet er at designe og implementere et kørende flertrådet program med ikke-triviel synkronisering.

• Afleveringsfrist Fredag den 30. maj 2008 kl. 13:00 i René Rydhof Hansens dueslag i klynge 1 eller på kontor 1.2.36.
• Opgaven forventes at have et omfang svarende til tre øvelses/forelæsnings moduler (ca. 6 timer).
• Opgaven er individuel og skal besvares individuelt.
• Opgavebesvarelsen består af et kørende program, en kort rapport der beskriver de væsentligste aspekter ved projektet, en læsevenlig udskrift af programmet med navn, sidetal, filnavn og linienumre på alle sider samt output fra en eksempelkørsel.
• Opgavebesvarelsen evalueres af kursusholder og hjælplærer.
• Der må ikke benyttes busy waiting.
• For alle løsninger skal der argumenteres for at løsningen er deadlockfri.
• Da formålet med opgaven er at få erfaring med synkronisering og flertrådede programmer, gives der relativt få point for anvendelse af (unødvendigt) avancerede datastrukturer, GUI'er og unødig funktionalitet.
• Programmet skal implementeres i enten C#, Java eller C.
• Miniprojektbeskrivelserne er relativt udetaljerede og overlader derfor en hel del ansvar og beslutninger til den enkelte studerende mht. ambitionsniveau, tidspres osv.
• Der vil være hjælpelærer i den normale opgaveregningstid.
• Under hele projektet kan der naturligvis stilles spørgsmål enten på mail eller personligt på kontor 1.2.36.

Miniprojekt 1: Kalender

Projektet handler om en kalender der kan tilgås af flere brugere. Kalenderen er defineret i termer af tidsreserveringsenheder, kaldet slots, der f.eks. dækker en time. Reservationer kan spænde over flere slots. Et slot indeholder relevant information, f.eks., en kort beskrivelse, et bruger ID og status (ledig, mulig aftale, bekræftet aftale, aflysning osv.).

Projektet skal som minimum opfylde følgende:

• Det skal være muligt at aflæse et givet slot.
• Det skal være muligt at udskrive et opdateret øjebliksbillede af kalenderen.
• All brugere skal kunne tilføje reservationer.
• Det skal være muligt for kalenderejeren (en bruger i systemet) at se kalenderen kontinuerligt, dvs. skærmbilledet skal opdateres hver gang kalenderen opdateres.
• Det skal være muligt for flere brugere at opnå samtidig læse-adgang.
• Global eksklusiv lås på hele kalenderen må ikke benyttes. Låsning bør foregå på slot-niveau.
• Brugere simuleres som selvstændige tråde der aflæser kalenderen, opretter reservation eller sover. Eventuelt kan brugere også slette reservationer.

Miniprojekt 2: Disk-schedulering

I dette projekt skal der implementeres en disk scheduler der varetager den overordnede kontrol med disken, en "disk simulator"-process samt et antal brugerprocesser der ønsker adgang til at læse/skrive på disken.

Et request består læse- eller skrive-adgang til et givet cylinder/spor på disken. Brugerprocesser opnår adgang ved at tilføje et request til en request-liste der kontrolleres og analyseres af disk-scheduleren. Disk-scheduleren skal minimere tilgangstiden til disken ved at minimere flytning af diskens læse/skrive-hovede. Endvidere skal disk-scheduleren sørge for, at udsultning undgås. Dette kan gøres ved at benytte SCAN algoritmen der (1) servicerer alle requests til det aktive spor inden hovedet flyttes og (2) flytter hovedet i een retning sålænge der er requests for spor i den retning.

I projektet skal de ovennævnte processer implementeres, procedurer til læsning/skrivning samt synkronisering mellem brugerprocesser, scheduler og disk-processen således at:

• Der er mutex på request-listen og andre delte variable
• Et request blokerer den kaldende process indtil
  1. læsehovedet står over det ønskede spor
  2. det er processens tur til at tilgå sporet (i tilfælde af flere processer der ønsker adgangtil samme spor serviceres disse i ankomstrækkefølge)
• Processen bevarer retten til at tilgå et spor indtil den frigiver det.
• Scheduleren blokerer hvis der ikke er requests der skal serviceres
• Scheduleren blokerer når disk armen bevæges.

Miniprojekt 3: Hukommelsesallokering

Der skal implementeres rutiner til hukommelsesallokering samt et antal brugerprocesser der allokerer, reallokerer og deallokerer hukommelse. Følgende krav skal være opfyldt:

• Allokatoren skal blokere kaldende processer hvis der ikke er hukommelse nok til at imødekomme ønsket eller ved fare for deadlock.
• Når hukommelse frigives skal eventuelt blokerede processer vækkes.
• Der skal indgå eksplicit deadlockhåndtering f.eks. i form af Banker's algorithm eller anvendelse af "detection and recovery".

Detaljeret opgaveforslag fra Morten Kühnrich kan ses her og templates kan findes her.

[PSS home]