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 =)

Planering: Feedbackkö på flera nivåer

I den här föreläsningen kommer vi att prata om problemen med att utveckla ett av de mest kända tillvägagångssätten
planering, som kallas Feedbackkö på flera nivåer (MLFQ). MLFQ-schemaläggaren beskrevs första gången 1962 av Fernando J. Corbató i ett system som heter
Kompatibelt tidsdelningssystem (CTSS). Dessa verk (inklusive senare arbete på
Multics) nominerades därefter till Turing Award. Planeraren var
förbättrades därefter och fick det utseende som redan finns i
några moderna system.

MLFQ-algoritmen försöker lösa två grundläggande överlappande problem.
Först, försöker den optimera omloppstiden, som, som vi diskuterade i föregående föreläsning, är optimerad av metoden att börja i början av kön mest
korta uppgifter. Men operativsystemet vet inte hur länge en viss process kommer att köra, och detta
nödvändig kunskap för driften av SJF, STCF-algoritmerna. Andra, MLFQ försöker
gör systemet responsivt för användare (till exempel för de som sitter och
stirra på skärmen i väntan på att uppgiften ska slutföras) och på så sätt minimera tiden
svar. Tyvärr förbättrar algoritmer som RR svarstiden, men extremt
har en dålig inverkan på handläggningstidsmåttet. Därav vårt problem: Hur man designar
en schemaläggare som kommer att uppfylla våra krav utan att veta något om
processens karaktär i allmänhet? Hur kan schemaläggaren lära sig egenskaperna hos uppgifter,
som den lanserar och därmed fatta bättre planeringsbeslut?

Kärnan i problemet: Hur man planerar inställningen av uppgifter utan perfekt kunskap?
Hur man designar en schemaläggare som samtidigt minimerar svarstiden
för interaktiva uppgifter och samtidigt minimerar handläggningstiden utan att veta
kunskap om uppgiftens genomförandetid?

Obs: vi lär oss av tidigare händelser

MLFQ-kön är ett utmärkt exempel på ett system som lär sig av
tidigare händelser för att förutsäga framtiden. Liknande tillvägagångssätt är ofta
finns i OS (Och många andra grenar av datavetenskap, inklusive grenar
hårdvaruförutsägelser och cachningsalgoritmer). Liknande resor
utlöses när uppgifter har beteendefaser och är därmed förutsägbara.
Du bör dock vara försiktig med denna teknik eftersom förutsägelser är mycket enkla
kan visa sig vara felaktiga och leda till att systemet tar sämre beslut än
skulle vara utan kunskap alls.

MLFQ: Grundläggande regler

Låt oss titta på de grundläggande reglerna för MLFQ-algoritmen. Och även om implementeringar av denna algoritm
Det finns flera, de grundläggande tillvägagångssätten är likartade.
I implementeringen vi kommer att titta på kommer MLFQ att ha flera
separata köer, som var och en har olika prioritet. När som helst,
en uppgift redo att utföras finns i en kö. MLFQ använder prioriteringar,
att bestämma vilken uppgift som ska köras för utförande, d.v.s. uppgift med högre
prioritet (uppgift från kön med högst prioritet) kommer att startas först
kö.
Naturligtvis kan det finnas mer än en uppgift i en given kö, så
så de kommer att ha samma prioritet. I det här fallet kommer mekanismen att användas
RR för att schemalägga en körning bland dessa uppgifter.
Så vi kommer fram till två grundläggande regler för MLFQ:

Regel 1: Om prioritet(A) > Prioritet(B) kommer uppgift A att startas (B kommer inte)
Regel 2: Om prioritet(A) = Prioritet(B), startas A&B med RR

Baserat på ovanstående, nyckelelementen för att planera MLFQ
är prioriteringar. Istället för att ge en fast prioritet till var och en
uppgift ändrar MLFQ sin prioritet beroende på det observerade beteendet.
Till exempel, om en uppgift ständigt kastar arbete på processorn medan den väntar på tangentbordsinmatning,
MLFQ kommer att hålla processprioritet hög eftersom det är så
en interaktiv process ska fungera. Om, tvärtom, uppgiften är ständigt och
använder CPU mycket under en lång period, kommer MLFQ att sänka den
en prioritet. Således kommer MLFQ att studera beteendet hos processer medan de körs
och använda beteenden.
Låt oss rita ett exempel på hur köerna kan se ut någon gång
tid och då får du något sånt här:

I detta schema är 2 processer A och B i högsta prioritetskön. Bearbeta
C är någonstans i mitten, och process D är i slutet av kön. Enligt ovanstående
Enligt beskrivningarna av MLFQ-algoritmen kommer schemaläggaren att utföra uppgifter endast med den högsta
prioritet enligt RR, och arbetsuppgifter C, D kommer att vara arbetslösa.
Naturligtvis kommer en statisk ögonblicksbild inte att ge en fullständig bild av hur MLFQ fungerar.
Det är viktigt att förstå exakt hur bilden förändras över tid.

Försök 1: Hur man ändrar prioritet

Vid det här laget måste du bestämma hur MLFQ ska ändra prioritetsnivån
uppgifter (och därmed uppgiftens position i kön) när den fortskrider genom sin livscykel. För
detta är nödvändigt för att komma ihåg arbetsflödet: en viss mängd
interaktiva uppgifter med korta körtider (och därmed frekventa släpp
CPU) och flera långvariga uppgifter som använder processorn hela sin arbetstid, medan
Svarstiden är inte viktig för sådana uppgifter. Och på så sätt kan du göra ditt första försök
implementera MLFQ-algoritmen med följande regler:

Regel 3: När en uppgift kommer in i systemet placeras den i kön med högst
prioritet.
Regel 4a: Om en uppgift använder hela det tidsfönster som tilldelats den, då
prioritet minskas.
Regel 4b: Om en uppgift släpper CPU:n innan dess tidsfönster löper ut, då
förblir med samma prioritet.

Exempel 1: Enstaka långvarig uppgift

Som framgår av detta exempel är antagningsuppgiften satt med den högsta
prioritet. Efter ett tidsfönster på 10 ms degraderas processen i prioritet
planerare. Efter nästa tidsfönster degraderas uppgiften slutligen till
lägsta prioritet i systemet, där det finns kvar.

Exempel 2: Levererade en kort uppgift

Låt oss nu se ett exempel på hur MLFQ kommer att försöka närma sig SJF. I den
till exempel två uppgifter: A, som är en långvarig uppgift konstant
upptar CPU och B, vilket är en kort interaktiv uppgift. Anta
att A redan hade arbetat en tid när uppgift B kom.

Denna graf visar resultatet av scenariot. Uppgift A, som vilken uppgift som helst,
CPU-användningen var i botten. Uppgift B kommer att anlända vid tidpunkten T=100 och kommer
placeras i högsta prioritetskön. Eftersom dess drifttid är kort alltså
den kommer att slutföras innan den når den sista kön.

Från detta exempel bör algoritmens huvudmål förstås: eftersom algoritmen inte gör det
vet om en uppgift är lång eller kort, då antar han först och främst att uppgiften
kort och ger den högsta prioritet. Om det här är en riktigt kort uppgift, alltså
det kommer att slutföras snabbt, annars kommer det att gå långsamt om det är en lång uppgift
prioritet ner och kommer snart att bevisa att hon verkligen är en lång uppgift som inte gör det
kräver ett svar.

Exempel 3: Hur är det med I/O?

Låt oss nu titta på ett I/O-exempel. Som framgår av regel 4b,
om en process släpper processorn utan att använda all dess processortid,
då förblir den på samma prioritetsnivå. Avsikten med denna regel är ganska enkel
- om det interaktiva jobbet utför många I/O-operationer, till exempel att vänta
från användartangenten eller musen, kommer en sådan uppgift att frigöra processorn
före det tilldelade fönstret. Vi skulle inte vilja sänka prioritet för en sådan uppgift,
och därmed kommer den att förbli på samma nivå.

Det här exemplet visar hur algoritmen kommer att fungera med sådana processer - interaktivt jobb B, som bara behöver CPU i 1 ms innan det körs
I/O-process och långvarigt jobb A, som ägnar all sin tid åt att använda processorn.
MLFQ håller process B på högsta prioritet eftersom den fortsätter
släpp processorn. Om B är en interaktiv uppgift, har algoritmen uppnåtts
Ditt mål är att köra interaktiva uppgifter snabbt.

Problem med den nuvarande MLFQ-algoritmen

I de tidigare exemplen byggde vi en grundläggande version av MLFQ. Och det verkar som att han
gör sitt jobb bra och ärligt och fördelar CPU-tiden rättvist mellan dem
långa uppgifter och tillåter korta eller stora uppgifter
arbeta med I/O snabbt. Tyvärr innehåller detta tillvägagångssätt flera
allvarliga problem.
Först, problemet med hunger: om systemet har många interaktiva
uppgifter, då kommer de att förbruka all processortid och därmed inte en enda på länge
uppgiften kommer inte att kunna utföras (de svälter).

Andra, kunde smarta användare skriva sina program så att
lura schemaläggaren. Bedrägeri ligger i att göra något för att tvinga
Schemaläggaren ger processen mer CPU-tid. Algoritmen det
som beskrivs ovan är ganska sårbar för liknande attacker: innan tidsfönstret är praktiskt taget
avslutat måste du utföra en I/O-operation (för vissa, oavsett vilken fil)
och därmed frigöra processorn. Sådant beteende kommer att tillåta dig att förbli i samma sak
själva kön och återigen få en större andel av CPU-tiden. Om du gör
detta är korrekt (exekvera till exempel 99 % av fönstertiden innan du släpper processorn),
en sådan uppgift kan helt enkelt monopolisera processorn.

Slutligen kan ett program ändra sitt beteende över tid. De uppgifterna
som använde processorn kan bli interaktiv. I vårt exempel, liknande
uppgifter kommer inte att få den behandling de förtjänar från schemaläggaren som andra skulle göra
(inledande) interaktiva uppgifter.

Fråga till publiken: vilka attacker mot schemaläggaren skulle kunna utföras i den moderna världen?

Försök 2: Ökad prioritet

Låt oss försöka ändra reglerna och se om vi kan undvika problem med
fasta. Vad kan vi göra för att säkerställa att relaterade
CPU-uppgifter kommer att få sin tid (även om inte lång).
Som en enkel lösning på problemet kan du föreslå med jämna mellanrum
prioritera alla sådana uppgifter i systemet. Det finns många sätt
För att uppnå detta, låt oss försöka implementera något enkelt som ett exempel: översätt
alla uppgifter ges omedelbart högsta prioritet, därav den nya regeln:

Rule5: Efter en viss period S, flytta alla uppgifter i systemet till den högsta kön.

Vår nya regel löser två problem samtidigt. Först, processerna
kommer garanterat inte att svälta: uppgifter som har högsta prioritet kommer att delas upp
CPU-tid enligt RR-algoritmen och därmed alla processer kommer att ta emot
CPU-tid. För det andra, om någon process som tidigare använts
endast processorn blir interaktiv, den förblir i kön med den högsta
prioritet efter att ha fått en engångsökning av prioritet till den högsta.
Låt oss titta på ett exempel. I det här scenariot, överväg en process som använder

CPU och två interaktiva, korta processer. Till vänster i figuren visar figuren beteendet utan prioriterad befordran, och därmed börjar den långvariga uppgiften svälta efter att två interaktiva uppgifter kommit in i systemet. I figuren till höger utförs en prioritetsökning var 50:e ms och därmed är alla processer garanterade att få CPU-tid och kommer att startas med jämna mellanrum. 50ms i det här fallet tas som ett exempel, i verkligheten är detta nummer något högre.
Uppenbarligen, att lägga till den periodiska ökningstiden S leder till
en logisk fråga: vilket värde ska ställas in? En av de hedrade
systemingenjörer John Ousterhout kallade sådana kvantiteter i system som voo-doo
konstant, eftersom de på något sätt krävde svart magi för korrekt
ställer ut. Och tyvärr har S en sådan doft. Om du ställer in värdet också
stora - långa uppgifter kommer att börja svälta. Och om du ställer in värdet för lågt,
Interaktiva uppgifter kommer inte att få korrekt CPU-tid.

Försök 3: Bättre bokföring

Nu har vi ett annat problem att lösa: hur inte
låta vår schemaläggare luras? Människorna att skylla på denna möjlighet är
reglerna 4a, 4b, som tillåter ett jobb att behålla prioritet, vilket frigör processorn
innan den utsatta tiden går ut. Hur ska man hantera detta?
Lösningen i detta fall kan betraktas som en bättre redovisning av CPU-tid på varje
MLFQ nivå. Istället för att glömma tiden programmet använde
processor för den tilldelade perioden, bör den beaktas och sparas. Efter
processen har förbrukat sin tilldelade tid bör den flyttas ned till nästa
prioritetsnivå. Nu spelar det ingen roll hur processen kommer att använda sin tid - hur
ständigt beräkna på processorn eller som ett antal samtal. Således,
regel 4 bör skrivas om till följande form:

Rule4: Efter att en uppgift har förbrukat sin tilldelade tid i den aktuella kön (oavsett hur många gånger den frigjorde processorn), sänks prioritet för den uppgiften (den flyttas ner i kön).

Låt oss titta på ett exempel:
»

Bilden visar vad som händer om du försöker lura schemaläggaren, som
om det var med de tidigare reglerna 4a, 4b skulle resultatet till vänster erhållas. Gott nytt
regeln är resultatet till höger. Innan skyddet kan vilken process som helst anropa I/O innan den är klar och
dominerar alltså CPU:n, efter att ha aktiverat skydd, oavsett beteende
I/O kommer han fortfarande att flytta ner i kön och kommer därmed inte att kunna oärligt
ta över CPU-resurser.

Förbättra MLFQ och andra problem

Med ovanstående förbättringar kommer nya problem: ett av de största
Frågor - hur parametriserar man en sådan schemaläggare? De där. Hur mycket ska det vara
köer? Vad ska storleken på programfönstret vara i kön? Hur
Programprioritet bör ofta ökas för att undvika svält och
ta hänsyn till förändringen i programmets beteende? Det finns inget enkelt svar på dessa frågor
svar och endast experiment med laster och efterföljande konfiguration
planerare kan leda till en tillfredsställande balans.

Till exempel tillåter de flesta MLFQ-implementeringar dig att tilldela olika
tidsintervall för olika köer. Högprioriterade köer vanligtvis
korta intervaller föreskrivs. Dessa köer består av interaktiva uppgifter,
växla mellan vilket är ganska känsligt och bör ta 10 eller mindre
Fröken. Däremot består lågprioriterade köer av långvariga uppgifter som använder
CPU. Och i det här fallet passar långa tidsintervall väldigt bra (100ms).

I det här exemplet finns det 2 uppgifter som fungerade i högprioritetskö 20
ms, uppdelat i 10ms fönster. 40 ms i mellankö (20 ms fönster) och i låg prioritet
Kötidsfönstret blev 40ms där uppgifterna avslutade sitt arbete.

Solaris OS-implementeringen av MLFQ är en klass av tidsdelningsschemaläggare.
Planeraren kommer att tillhandahålla en uppsättning tabeller som definierar exakt som den ska
prioriteringen av processen förändras under dess livstid, vad bör vara storleken
tilldelat fönster och hur ofta du behöver höja uppgiftens prioriteringar. Administratör
system kan interagera med den här tabellen och få schemaläggaren att fungera
annorlunda. Som standard har denna tabell 60 köer med en gradvis ökning
fönsterstorlek från 20 ms (hög prioritet) till flera hundra ms (låg prioritet), och
också med en boost av alla uppgifter en gång per sekund.

Andra MLFQ-planerare använder inte en tabell eller något specifikt
regler som beskrivs i denna föreläsning, tvärtom, de beräknar prioriteringar med hjälp av
matematiska formler. Till exempel använder FreeBSD-schemaläggaren en formel för
beräkna aktuell prioritet för en uppgift baserat på hur lång processen är
använd CPU. Dessutom avtar CPU-användningen med tiden, och så
Alltså sker en ökad prioritet något annorlunda än vad som beskrivits ovan. Detta är sant
kallas förfallsalgoritmer. Sedan version 7.1 har FreeBSD använt ULE-schemaläggaren.

Slutligen har många schemaläggare andra funktioner. Till exempel några
schemaläggare reserverar de högsta nivåerna för driften av operativsystemet och därmed
Således kan ingen användarprocess få högsta prioritet i
systemet. Vissa system låter dig ge råd för att hjälpa
planeraren kan prioritera korrekt. Till exempel genom att använda kommandot trevligt
du kan öka eller minska en uppgifts prioritet och därmed öka eller
minska programmets chanser att använda CPU-tid.

MLFQ: Sammanfattning

Vi har beskrivit en planeringsmetod som kallas MLFQ. Hans namn
innesluten i driftprincipen - den har flera köer och använder feedback
för att bestämma uppgiftens prioritet.
Den slutliga formen av reglerna kommer att vara följande:

Rule1: Om prioritet(A) > Prioritet(B) kommer uppgift A att startas (B kommer inte)
Rule2: Om prioritet(A) = Prioritet(B), startas A&B med RR
Rule3: När en uppgift kommer in i systemet placeras den i högsta prioritetskön.
Rule4: Efter att en uppgift har förbrukat sin tilldelade tid i den aktuella kön (oavsett hur många gånger den frigjorde processorn), sänks prioritet för den uppgiften (den flyttas ner i kön).
Rule5: Efter en viss period S, flytta alla uppgifter i systemet till den högsta kön.

MLFQ är intressant av följande anledning - istället för att kräva kunskap om
uppgiftens karaktär i förväg studerar algoritmen det tidigare beteendet för uppgiften och uppsättningarna
prioriteringar i enlighet med detta. Således försöker han sitta på två stolar samtidigt - för att uppnå produktivitet för små uppgifter (SJF, STCF) och för att ärligt springa långt,
CPU-laddningsjobb. Därför har många system, inklusive BSD och deras derivat,
Solaris, Windows, Mac använder någon form av algoritm som schemaläggare
MLFQ som baslinje.