English web site
TDDI81 Processprogrammering och operativsystem
Hemuppgift
Case study: Pintos
Detta är information rörande det som i schemat benämns "hemuppgift" under vecka 8. En kodstudielab ni gör på egen tid. Detta är preliminär information. Frågor och kommentarer mottages fram till Onsdag vecka 7. Deadline för inlämning den 25/2 kl 23:59. Rapporten skickas som pdf till examinator.
- Instruktioner och uppgifter
- ACM:s rapportmall (doc) (Känner du till andra? Hör av dig!)
Gruppindelning
Grupper skall helst bestå av 4 aktiva medlemmar. Om man inte får kontakt med alla medlemmer gäller följande. Grupp med färre än 4 aktiva medlemmar får byta en inaktiv medlem mot en aktiv medlem i grupp med 5 aktiva medlemmar. Detta måste ske i sådan tid att alla påverkade är överens. Båda grupperna måste ha samma uppgift. Medlemmer man inte fått kontakt med, eller som inte bidrar till arbetet skall inte räknas med i gruppen. Är man fortfarande för få löser gruppen uppgiften ändå. Alla gruppförändringar skall meddelas examinator via e-post.
Resultat
Varje inlämnad rapport finns länkad nedan. Generellt gäller att de flesta behöver flera ytterligare omgångar korrekturläsning för att få fullgott språk. Det gäller även att figurer i flera fall behöver mycket utförligare förklaring i text.
Jag har läst och kommenterat vad jag inte riktigt håller med om eller tycker behöver förtydligas. Det betyder inte att jag hittat alla missuppfattningar, men många. Överlag ser det ut som alla grupper fått nya insikter, och på så sätt uppnått målet med uppgiften.
Som kommentar här skriver jag vad som är bra samt något förtydligande av saker som kanske missuppfattats. Avsikten är att identifiera vad som kan vara läsvärt för andra utan att sprida missuppfattningar. Det gäller dock ändå att läsa kritiskt. Delar som inte är kommenterade som bra är att betrakta som opålitliga i studiehänseende (även om de till stor del kan vara ok). Jag har fetstilat lite "highlights", det som nog är av mest intresse att läsa.
Processer och trådar: Deadline 25/2
- rassi149,andda584,patot329,jondo466,tonma951
Bra i sin helhet, med några kommentarer: Efter "fork" kan parent och child inte kommunicera, child kan bara läsa data som parent skapat innan "fork" eftersom child blir en helt egen klon av parent, med egna resurser (minne, öppna filer). Huruvida Pintos i ursprungsläge är 1-1 eller 1-N kan diskuteras då dessa avser multitrådade processer och Pintos bara har enkeltrådade processer. Vad gäller process_activate hanterar den endast "pagetable" vid processbyte. I övrigt utförst state save och restore av intr_entry och intr_exit, samt vid trådbyte switch_threads. Er avslutande TCB skall bara ha stack och CPU context, samt vilken PCB den tillhör, det är allt som behövs för att återställa trådens exekvering. - nikbl918,freha424,jakda117,matle481
Bra genomgång av PCB. Stack, PC, Register utlokaliseras till en TCB per tråd vid flertrådning. Det är process_execute som startar en ny process, medan thread_create mycket riktigt skapar en kernel-tråd. - alela025,andda458,aleol874,idaen752
PCB och TCB väl beskrivet. PCB håller resurser som är gemensamma för alla processens trådar medan varje TCB håller reda på var i exekveringen dess tråd är. Multithreading-avsnittet på rätt spår. Pintos har faktiskt vänteköer även om det bara ingick att identifiera readykön. En ny tråd startar mycket riktigt som blocked, men flyttas omedelbart till ready-kön via thread_unblock. Det ni kallar "interrupt-simulering" används för att få tråden att växla till user-mode. - maros968,karas932,freni297,nicno731
Figur 1 visar Pintos köer och funktioner för förflyttning mellan dem på ett bra tydligt sätt. intr_frame har inget med PCB att göra, det representerar user-trådens sparade state vid systemanrop. "Hantering av flera processer" och framåt är bra, dock gäller att Pintos är multitrådat i kernel med enkeltrådade processer. Funktionen fork() klonar alltid en hel process, d.v.s. en ny process skapas - men ibland klonas inte alla trådar som körde när fork anropades. Bra referenshantering. - sonph955,vikal046,vikol799,satpa411,adala894
Figur 1 är bra, figuren saknar thread_create för state "New". Bra diskussion om trådhantering. Även i övrigt mestadels OK, men det bör framförallt poängteras att en kerneltråd i Pintos inte nödvändigtvis behöver vara en process (t.ex. idle-thread), samt att PCB alltid är data om en process lagrat i kernel. - linfo609,karvo020,thoel741,salad517
Även här bra (men lite annorlunda) figur över kösystemet. Det bör poängteras att en ny process alltid får sitt eget minne som andra processer inte har tillgång till, inte ens förälderprocessen. Systemanropet "fork" är i UNIX det som skapar en ny process (child) genom att klona processen som körs (parent). - casne493,parso500,marbe393,jacho391
Överlag OK men behöver korrekturläsas. Har korrekt identifierat hur vänteköer hanteras i Pintos! Det är process_execute som drar igång en kerneltråd för en ny process. Kerneltråden kör start_process för att läsa in processen. Avslutande PCB lämnar mig med frågetecken. - sebbj070,johsc157,johsu917,marpe589,adahe965
Första två sidorna OK med lite förtydliganden av en del saker. PCB håller reda på information (resurser) gemensam för alla trådar inom processen (som ni säger: status, ID, minne, öppna filer). Thread_create skapar en ny tråd, inte thread_start. Trådar håller endast reda på exekveringsstate (stack och register), öppna filer delas med resten av de trådar som har samma PCB. Systemanropet "wait" har ni missuppfattat. - marhe414,sebto088,timan976,joncr042,joakv409
Figur 1 gillas. Överlag korrekt information. Förtydlignden: intr_frame är en beskrivning av det som sparas vid avbrott, detta kan tolkas som user-trådens CPU-context. Kerneltrådens TCB är den stack och stackpekare som återfinns i struct thread. TCB är ibland en del av PCB, framförallt då processer är enkeltrådade. Processer skapas med process_execute med hjälp av start_process. En kerneltråd avdelas att exekvera processen. I UNIX används traditionellt fork+exec för att göra samma jobb.
Öppna filer och filsystem: Deadline 25/2
- jonka918,pelma710,andli288
Bra i sin helhet. Bilden behöver beskrivning. Saknar information om länkar och kataloger. Ett "inte" för mycket på sidan 2, kolumn 2, rad 4. Samt några andra smärre korrekturfel. - sebko269,jakha102,robgu573,johhj583
Överlag bra. Förtydliganden: inode_disk innehåller numret på första datasektorn. open_cnt anger hur många gånger den inoden öppnats. Partitionering och contigous allocation utesluter inte varandra. Stycket om länkar är fel. Figuren bör visa att det finns en open file table (i mitten) per process. De små tabellerna i figuren ingår ej i OS. - theal187,marfa222,freli055,frevi615
Överlag bra. Figur 1 behöver förklaring. Figur 2 har 5 block ledigt i rad. Saknar info om länkar. Utbyggnad för indexed allocation bör lagra sitt index i den outnyttjade delen av nuvarande inode_disk. inode_disk lagrar bland annat filstorlek som bara bör finnas på en plats. - filan750,torkv393,glewe258,jeslu580
Korrekturläs fem gånger till. Bra beskrivning av external fragmentation. Bra om linked allocation. Nämner tree-structured directory. Allokeringsmetod för pages, referens 11, har bara med internminneshantering (RAM) att göra. Inget med disk och filer. Detaljerad referenshantering. - johng862,matal092,eriti930,mirha348
Överlag ok men med några oklarheter. WAFL? Bild på sida två behöver förklaras. Bra bild på combined scheme indexed allocation. - sepmi077,hamni509,perde191,albek446
Figur 1 behöver förklaras. Bra stycke katalog och filsystem. Bra om hårda länkar. Mjuka länkar är helt enkelt en fil som lagrar ett filnamn. Den behöver liksom kataloger en speciell filtyp för att automatiskt tolkas korrekt vi öppning. Inga referenser. - johli348,tobni236,erijo979,johwa457
Bra om hårda länkar. System-wide open file table manipuleras närmast av inode_open och inode_close. Många nämner att blockpekarna tar mycket plats i linked allocation. De tar lika mycket plats i indexed allocation. Typiskt behövs 4 byte per 4kB block. Det är en liten overhead som får ses som acceptabel för att slippa external fragmentation. - mican614,erivi070,simjo952,johsa893
Förklarar figur 1! Dela upp texten i kortare stycken. Tar upp bra exempel på internal och external fragmentation, men utan att sätta namn på det. - andyd643,henfo939,davro272,ponli933
Överlag ok. Förtydliganden: Huruvida external fragmentation uppstår beror på allokeringsmetod. Ny inode_disk bör ha 125 block pointers istället för det 125 oanvända positionerna. Hela structen skall vara exakt ett diskblock. Figur 1 med tabellerna är inte rätt. - henri407,linis160
Överlag ok. Följer inte mall. Riktigt detaljerad och korrekt figur.
Processer och trådar: "Rätt" svar i korthet
PCB motsvaras av "struct thread". Här finns pagedir som tilldelar processen minne och per-process open file list som håller reda på alla öppnade filer. Eftersom endast en tråd per process finns lagras även trådinformation här. Processens schemaläggningsprioritet lagras här. PCB håller reda på de resurser som är gemensamma för hela processen (alla dess trådar).
TCB motsvaras av "struct thread". Här finns kernelstack som i sin tur lagrar cpu-context vid trådbyten och avbrott. Det finns ett ID för att identifiera tråden. TCB motsvarar den information som behöver sparas medan andra trådar exekverar, så tråden till slut kan fortsätta där den avbröts.
Process och kerneltråd är i Pintos samma sak. De kerneltråd-states som finns i Pintos är Running, Ready, Blocked och Dying. I Pintos finns dubbellänkade ready_list för ready-kön och varje orsak att vänta på något har en egen dubbellänkad lista som väntekö, oftast som del i en semaphore (överkurs). thread_create placerar en ny kerneltråd på ready_list, thread_yield flyttar körande kerneltråd till ready_list, thread_block flyttar körande kerneltråd ut ur kösystemet (någon annan förutsätts ha lagrat tråden på en relevant väntekö), thread_unblock flyttar in en kerneltråd till ready_list, och schedule väljer en kerneltråd att exekvera från ready_list. thread_current ger trådinformation (TCB, PCB) för den kerneltråd/process som kör.
Pintos använder FCFS-Round-Robin men 4 ticks quanta.
Ett UNIX-system skapar en ny process genom systemanropet fork. Den process som körs klonas, inklusive alla resurser den har öppna i OS (PCB: minne, filer, och i variaerande grad trådar). Den som anropar fork blir förälder och den nya processen blir barn. Barnet kan inte komma åt eller kommunicera med föräldern då de finns i separata processer med skyddat minne. Enda kommunikationsvägen är via systemanrop OS tillhandahåller. Speciellt kan föräldern (frivilligt) be om barnets exit-status (värdet barnet ger till systemanropet exit) via systemanropet wait. Både förälder och barn kommer köra samma program. För att ersätta en process med ett nytt program kan systemanropet exec användas. I Pintos utför process_execute en kombinerad fork+exec för att direkt skapa en ny process som exekverar ett eget program, utan att först klona processen som kör.
Ett vanligt trådbibliotek i UNIX är POSIX threads (pthreads) med stöd för create, cancel, detach, join och exit. Pintos har endast tillgång till kerneltrådar via thread_create, thread_sleep, thread_yield och thread_exit.
I Pintos schemalägger process_execute en ny kerneltråd (inkl. TCB). Den nya tråden exekverar funktionen start_process som läser in programmet från fil, initierar PCB och skapar processens (user-trådens) stack samt startar processen genom att börja exekvera main i user-mode.
För att ge möjlighet till usertrådar 1-1 mappade till kerneltrådar bör struct thread delas upp i en PCB (pagedir, öppna filer, trådlista, mm) som är gemensam, och en TCB (stack, context, PCB-pekare) för varje tråd i processen. För att skapa en ny usertråd utförs ett systemanrop som skapar en ny kerneltråd som delar PCB med körande kernel-tråd. Kerneltråden skapar (likt start_process) en user-mode stack och börjar exekvera begärd kod i user-mode.
Filer och filsystem: "Rätt" svar i korthet
FCB motsvaras i Pintos av struct inode (i RAM) och inode_disk (på disk). Viktiga data i FCB är startblock, filstorlek och filtyp (katalog, länk, fil).
System-wide table motsvaras av inode_list och manipuleras av inode_open, inode_reopen och inode_close. Dessa funktioner ser tillsammans till att en inode endast finns i en instans i listan, öppnas en inode som redan är öppen ökas bara open_count i struct inode. Tabellen behövs för att effektivisera filåtkomst och skydda mot samtidig access och borttagning. Per-process table behövs för att veta vilka filer en process har öppen (så de kan stängas vid avslut) och hålla reda på läs/skrivposition för varje öppning. Alla tabeller lagras i RAM då de byggs upp på nytt vid varje körning.
Pintos har en förenklad inode utan ägare tidstämplar och rättigheter.
I litteraturen står om bitmap med en bit per diskblock, länkad struktur där varje ledigt block pekar ut nästa, och en variant som kortar ned listan genom att lagra en lista på lediga block i varje länksteg. Pintos använder en bitmap.
Pintos använder contigous allocation vilket ger upphov till external fragmentation men effektiv random access. Alternativ ett är linked allocation utan external fragmentation på bekostnad av ineffektiv random access. Även lite extra overhead för pekare. Alternativ två är indexed allocation utan external fragmentation på bekostnad av högre internal fragmentation (i indexblock) samt "begränsad" filstorlek. Extra overhead för pekare är samma som för linked allocation. Alla metoder har viss internal fragmentation genom att filens sista datablock inte alltid fylls.
Boken beskriver kataloger i en, två eller flera nivåer. Antingen linjär tabell eller hashtabell i varje nivå. Pintos använder endast en rotkatalog med max 16 filer i en linjär lista. Filnamn har begränsad längd. Filer kan inte ha samma namn och sökning är inte speciellt effektiv när katalogen växer.
En fil som skall tas bort öppnas först. Därefter tas den bort ur katalogindexet så den inte kan öppnas på nytt. I steg tre markeras den öppna filen som borttagen varpå den stängs. Om inodens open_count vid stängning är noll indikerar det att ingen annan har filen öppen och filens datablock markeras som lediga. Det går alltså att använda en borttagen fil utan problem. Den försvinner först vid sista stängning.
Pintos inode_disk lagrar redan startblock och filstorlek i ett diskblock. Den plats som är över i blocket kan användas för indexpekare till filens block. Totalt ryms 125 blockpekare i inode_disk oanvända utrymme. X av dem vara direkta, Y kan vara indirekta och Z dubbelt indirekta för att stödja större filer. Funktionerna inode_create, inode_read_at och inode_write_at behöver uppdateras med den nya allokeringsmetoden. För att komma åt byteposition X behövs block N=X/BLOCKSIZE. För att komma åt block N läses pekare N från de direkta blocken om N < X, block (N-X) från de indirekta om (N-X)<(Y*Pointers_Per_Block) eller annars från de dubbelt indirekta.
För att stödja hårda länkar behövs en länkräknare i inode_disk. Den räknas upp när en hård länk skapas och ned när inoden tas bort. Blir länkräknaren noll skall filen tas bort och datablocken markeras som lediga i freemap. För att stödja mjuka länkar och kataloger måste filtypen lagras i inode_disk. Anger filtypen vid öppning en mjuk länk läses ett filnamn från filen och det filnamnet öppnas istället (om filen finns). Anger filtypen en katalog tolkas filinnehållet som en lista på flera inodes.
Sidansvarig: Klas Arvidsson
Senast uppdaterad: 2013-03-03
