Introduktion till operativsystem

Hej Habr! Jag skulle vilja uppmärksamma dig på en serie artiklar-översättningar av en intressant litteratur enligt min mening - OSTEP. Detta material diskuterar ganska djupt arbetet med unix-liknande operativsystem, nämligen arbete med processer, olika schemaläggare, minne och andra liknande komponenter som utgör ett modernt operativsystem. Du kan se originalet av allt material här här. Observera att översättningen gjordes oprofessionellt (ganska fritt), men jag hoppas att jag behöll den allmänna innebörden.

Labbarbete i detta ämne finns här:

Övriga delar:

Du kan också kolla in min kanal på telegram =)

Introduktion till Schemaläggare

Kärnan i problemet: Hur man utvecklar en schemaläggarpolicy
Hur ska de underliggande schemaläggarens policyramar utformas? Vilka bör vara de viktigaste antagandena? Vilka mått är viktiga? Vilka grundläggande tekniker användes i tidiga datorsystem?

Arbetsbelastningsantaganden

Innan vi diskuterar möjliga policyer, låt oss först göra några förenklade avvikelser om processerna som körs i systemet, som tillsammans kallas arbetsbelastning. Att definiera arbetsbelastningen är en kritisk del av byggnadspolicyer, och ju mer du vet om arbetsbelastningen, desto bättre policy kan du skriva.

Låt oss göra följande antaganden om de processer som körs i systemet, ibland även kallat jobb (uppgifter). Nästan alla dessa antaganden är inte realistiska, utan nödvändiga för tankeutveckling.

Varje uppgift körs under samma tid,
Alla uppgifter ställs in samtidigt,
Den tilldelade uppgiften fungerar tills den är slutförd,
Alla uppgifter använder endast CPU,
Körtiden för varje uppgift är känd.

Schemaläggare

Förutom vissa antaganden om belastningen behövs ett annat verktyg för att jämföra olika schemaläggningsprinciper: schemaläggarmått. Ett mått är bara ett mått på något. Det finns ett antal mätvärden som kan användas för att jämföra schemaläggare.

Till exempel kommer vi att använda ett mått som heter handläggningstid (omläggningstid). Uppgiftens omloppstid definieras som skillnaden mellan uppgiftens slutförandetid och uppgiftens ankomsttid i systemet.

Tturnaround=Tavslut-Tarrival

Eftersom vi antog att alla uppgifter kom samtidigt, då Ta=0 och därmed Tt=Tc. Detta värde kommer naturligtvis att ändras när vi ändrar ovanstående antaganden.

Ett annat mått - rättvisa (ärlighet, ärlighet). Produktivitet och rättvisa är ofta motsatta egenskaper i planeringen. Till exempel kan schemaläggaren optimera prestanda, men till priset av att vänta på att andra uppgifter ska köras, vilket minskar rättvisan.

FÖRST IN FÖRST UT (FIFO)

Den mest grundläggande algoritmen som vi kan implementera kallas FIFO eller först till kvarn (in), först till kvarn (ut). Denna algoritm har flera fördelar: den är väldigt lätt att implementera och den passar alla våra antaganden och gör jobbet ganska bra.

Låt oss titta på ett enkelt exempel. Låt oss säga att 3 uppgifter ställdes samtidigt. Men låt oss anta att uppgift A kom lite tidigare än alla andra, så den kommer att dyka upp i exekveringslistan tidigare än de andra, precis som B i förhållande till C. Låt oss anta att var och en av dem kommer att utföras i 10 sekunder. Vad blir den genomsnittliga tiden för att slutföra dessa uppgifter i det här fallet?

Genom att räkna värdena - 10+20+30 och dividera med 3 får vi den genomsnittliga programexekveringstiden lika med 20 sekunder.
Låt oss nu försöka ändra våra antaganden. I synnerhet antagande 1 och därmed kommer vi inte längre att anta att varje uppgift tar lika lång tid att utföra. Hur kommer FIFO att prestera den här gången?

Som det visar sig har olika körningstider en extremt negativ inverkan på FIFO-algoritmens produktivitet. Låt oss anta att uppgift A kommer att ta 100 sekunder att slutföra, medan B och C fortfarande tar 10 sekunder vardera.

Som framgår av figuren blir medeltiden för systemet (100+110+120)/3=110. Denna effekt kallas konvojeffekt, när vissa korttidskonsumenter av en resurs kommer att köa efter en storkonsument. Det är som i kö vid mataffären när det står en kund framför dig med full vagn. Den bästa lösningen på problemet är att försöka byta kassaapparat eller koppla av och andas djupt.

Kortaste jobbet först

Är det möjligt att på något sätt lösa en liknande situation med tunga processer? Säkert. En annan typ av planering kallasKortaste jobbet först (SJF). Dess algoritm är också ganska primitiv - som namnet antyder kommer de kortaste uppgifterna att lanseras först, en efter en.

I det här exemplet kommer resultatet av att köra samma processer att vara en förbättring av den genomsnittliga programomloppstiden och den kommer att vara lika med 50 istället för 110, vilket är nästan 2 gånger bättre.

För det givna antagandet att alla uppgifter anländer samtidigt, verkar SJF-algoritmen vara den mest optimala algoritmen. Våra antaganden verkar dock fortfarande inte realistiska. Den här gången ändrar vi antagande 2 och den här gången föreställer vi oss att uppgifter kan vara närvarande när som helst och inte alla samtidigt. Vilka problem kan detta leda till?

Låt oss föreställa oss att uppgift A (100c) kommer först och börjar utföras. Vid t=10 anländer uppgifterna B och C, som var och en tar 10 sekunder. Så den genomsnittliga exekveringstiden är (100+(110-10)+(120-10))3 = 103. Vad kan schemaläggaren göra för att förbättra detta?

Kortaste tid till slutförande först (STCF)

För att förbättra situationen utelämnar vi antagande 3 om att programmet är lanserat och körs tills det är klart. Dessutom kommer vi att behöva hårdvarustöd och, som du kanske gissar, kommer vi att använda timer för att avbryta en pågående uppgift och kontextbyte. Sålunda kan schemaläggaren göra något i det ögonblick som uppgifter B, C anländer - sluta utföra uppgift A och sätta uppgifter B och C i bearbetning och, efter att de är slutförda, fortsätta att utföra process A. En sådan schemaläggare kallas STCFeller Förebyggande jobb först.

Resultatet av denna planerare blir följande resultat: ((120-0)+(20-10)+(30-10))/3=50. Därmed blir en sådan schemaläggare ännu mer optimal för våra uppgifter.

Metrisk svarstid

Således, om vi vet körtiden för uppgifterna och att dessa uppgifter endast använder CPU, kommer STCF att vara den bästa lösningen. Och en gång i de tidiga tiderna fungerade dessa algoritmer ganska bra. Men användaren tillbringar nu större delen av sin tid vid terminalen och förväntar sig en produktiv interaktiv upplevelse. Så föddes ett nytt mått - respons tid (svar).

Svarstiden beräknas enligt följande:

Tresponse=Tfirstrun−Tarrival

Således, för det föregående exemplet, kommer svarstiden att vara: A=0, B=0, C=10 (abg=3,33).

Och det visar sig att STCF-algoritmen inte är så bra i en situation där 3 uppgifter kommer samtidigt - den får vänta tills de små uppgifterna är helt klara. Så algoritmen är bra för omloppstidsmåttet, men dåligt för interaktivitetsmåttet. Föreställ dig om du satt vid en terminal och försökte skriva tecken i en editor och fick vänta mer än 10 sekunder eftersom någon annan uppgift tog upp CPU:n. Det är inte särskilt trevligt.

Så vi står inför ett annat problem - hur kan vi bygga en schemaläggare som är känslig för svarstid?

LISTA MED NAMNEN I CIRKEL

En algoritm utvecklades för att lösa detta problem LISTA MED NAMNEN I CIRKEL (RR). Grundidén är ganska enkel: istället för att köra uppgifter tills de är slutförda kommer vi att köra uppgiften under en viss tidsperiod (kallas en tidsdel) och sedan byta till en annan uppgift från kön. Algoritmen upprepar sitt arbete tills alla uppgifter är slutförda. I detta fall måste körtiden för programmet vara en multipel av tiden efter vilken timern kommer att avbryta processen. Till exempel, om en timer avbryter en process varje x=10 ms, bör storleken på processexekveringsfönstret vara en multipel av 10 och vara 10,20 eller x*10.

Låt oss titta på ett exempel: ABC-uppgifter kommer samtidigt in i systemet och var och en av dem vill köra i 5 sekunder. SJF-algoritmen kommer att slutföra varje uppgift innan en annan påbörjas. Däremot kommer RR-algoritmen med ett startfönster = 1s att gå igenom uppgifterna enligt följande (Fig. 4.3):

(SJF igen (dåligt för svarstid)

(Round Robin (bra för svarstid)

Den genomsnittliga svarstiden för RR-algoritmen är (0+1+2)/3=1, medan för SJF (0+5+10)/3=5.

Det är logiskt att anta att tidsfönstret är en mycket viktig parameter för RR, ju mindre det är, desto högre svarstid. Du bör dock inte göra den för liten, eftersom kontextbytetid också kommer att spela en roll för den övergripande prestandan. Således ställs valet av exekveringsfönstertid in av OS-arkitekten och beror på de uppgifter som är planerade att utföras i den. Att byta kontext är inte den enda tjänsteoperationen som slösar tid - det pågående programmet fungerar på en massa andra saker, till exempel olika cacher, och med varje switch är det nödvändigt att spara och återställa denna miljö, vilket också kan ta en hel del tid.

RR är en bra schemaläggare om vi bara pratade om svarstidsmåttet. Men hur kommer uppgiftens omloppstidsmått att bete sig med denna algoritm? Betrakta exemplet ovan, när drifttiden för A, B, C = 5s och anländer samtidigt. Uppgift A kommer att sluta vid 13, B vid 14, C vid 15s och den genomsnittliga omloppstiden kommer att vara 14s. Således är RR den sämsta algoritmen för omsättningsmåttet.

I mer allmänna termer är vilken RR-typ algoritm som helst rättvis, den delar CPU-tiden lika mellan alla processer. Och därför kommer dessa mätvärden ständigt i konflikt med varandra.

Vi har alltså flera kontrasterande algoritmer och samtidigt finns det fortfarande flera antaganden kvar - att uppgiftstiden är känd och att uppgiften bara använder CPU.

Blandning med I/O

Först av allt, låt oss ta bort antagande 4 att processen bara använder CPU; Naturligtvis är detta inte fallet och processer kan komma åt annan utrustning.

I samma ögonblick som någon process begär en I/O-operation går processen in i blockerat tillstånd och väntar på att I/O ska slutföras. Om I/O skickas till hårddisken kan en sådan operation ta upp till flera ms eller längre, och processorn kommer att vara inaktiv för närvarande. Under denna tid kan schemaläggaren ockupera processorn med vilken annan process som helst. Nästa beslut som schemaläggaren måste fatta är när processen ska slutföra sin I/O. När detta händer kommer ett avbrott att inträffa och operativsystemet kommer att sätta processen som anropade I/O i redoläge.

Låt oss titta på ett exempel på flera uppgifter. Var och en av dem kräver 50ms CPU-tid. Den första kommer dock att komma åt I/O var 10:e ms (som också kommer att exekveras var 10:e ms). Och process B använder helt enkelt en 50ms processor utan I/O.

I det här exemplet kommer vi att använda STCF-schemaläggaren. Hur kommer schemaläggaren att bete sig om en process som A startas på den? Han kommer att göra följande: först kommer han att helt utarbeta process A och sedan process B.

Den traditionella metoden för att lösa detta problem är att behandla varje 10 ms deluppgift i process A som en separat uppgift. När man börjar med STJF-algoritmen är valet mellan en uppgift på 50 ms och en uppgift på 10 ms uppenbart. Sedan, när deluppgift A är klar, kommer process B och I/O att startas. Efter att I/O är klar kommer det att vara vanligt att starta 10ms process A igen istället för process B. På detta sätt är det möjligt att implementera överlappning, där CPU:n används av en annan process medan den första väntar på I/O. Och som ett resultat utnyttjas systemet bättre - i det ögonblick då interaktiva processer väntar på I/O kan andra processer exekveras på processorn.

Oraklet finns inte längre

Låt oss nu försöka bli av med antagandet att löptiden för uppgiften är känd. Detta är i allmänhet det sämsta och mest orealistiska antagandet på hela listan. Faktum är att i det genomsnittliga vanliga operativsystemet, vet själva operativsystemet vanligtvis väldigt lite om exekveringstiden för uppgifter, så hur kan du då bygga en schemaläggare utan att veta hur lång tid uppgiften kommer att ta att utföra? Kanske kan vi använda några RR-principer för att lösa detta problem?

Totalt

Vi tittade på de grundläggande idéerna för uppgiftsschemaläggning och tittade på 2 familjer av schemaläggare. Den första startar den kortaste uppgiften först och ökar därmed handläggningstiden, medan den andra slits mellan alla uppgifter lika mycket, vilket ökar svarstiden. Båda algoritmerna är dåliga där den andra familjens algoritmer är bra. Vi tittade också på hur parallell användning av CPU och I/O kan förbättra prestandan, men löste inte problemet med OS clairvoyance. Och i nästa lektion ska vi titta på en planerare som ser in i det omedelbara förflutna och försöker förutsäga framtiden. Och det kallas återkopplingskö på flera nivåer.

Källa: will.com

Operativsystem: Tre enkla delar. Del 4: Introduktion till schemaläggaren (översättning)