Så bestämmer operativsystemet vilken app som får CPU-tid

Din dator kör just nu troligtvis dussintals processer samtidigt, webbläsaren, musikspelaren, operativsystemets egna bakgrundstjänster och mycket mer. Men din processor har ett begränsat antal kärnor och kan egentligen bara utföra ett begränsat antal saker i exakt samma ögonblick. Ändå upplever du allt som flytande och parallellt. Det är ingen illusion, utan resultatet av ett av operativsystemets mest centrala ansvarsområden: schemaläggning. Varje bråkdel av en sekund fattar operativsystemet beslut om vilken process som får köra, hur länge och vad som händer när tiden är slut.

Vad en process är och varför den behöver vänta

För att förstå schemaläggning behöver man först förstå vad operativsystemet faktiskt hanterar. När du startar ett program skapar operativsystemet en process, en självständig instans av programmet med sitt eget minnesutrymme, sina egna resurser och sitt eget tillstånd. En process är alltså inte samma sak som ett program. Du kan ha flera processer av samma program körandes samtidigt, och ett enda program kan internt skapa flera processer som samarbetar.

Processtillstånd och varför de finns

En process befinner sig alltid i ett av flera möjliga tillstånd. De tre grundläggande är körande, redo och väntande. En körande process använder just nu CPU-tid aktivt. En redo process är beredd att köra men väntar på att få tillgång till processorn. En väntande process kan inte köra just nu oavsett om processorn är ledig, för att den väntar på något externt, till exempel att en fil ska läsas från disk eller att ett nätverkssvar ska anlända.

Det är distinktionen mellan redo och väntande som är central. En process som väntar på disk-io blockerar inte processorn, den ställer sig bara åt sidan och ber operativsystemet väcka den när det den väntar på har inträffat. Det frigör processorn för andra processer under väntetiden.

Kontextbyte: kostnaden för att byta process

När operativsystemet bestämmer sig för att byta från en process till en annan måste det spara exakt det tillstånd den körande processen befann sig i, så att den kan återupptas exakt där den avbröts nästa gång den får CPU-tid. Det inkluderar innehållet i processorns register, programräknaren som pekar på nästa instruktion och annan relevant information. Det här kallas ett kontextbyte.

Kontextbyten är inte gratis. De tar tid, vanligtvis i storleksordningen några mikrosekunder, och de rensar ofta delar av processorns interna cacheminne vilket kan leda till prestandaförsämringar efteråt. Operativsystemet måste därför balansera mellan att byta process tillräckligt ofta för att alla processer ska få rimlig responstid och att byta så sällan att kontextbytenas overhead inte dominerar.

Schemaläggaren som fattar besluten

Den del av operativsystemet som hanterar dessa beslut kallas schemaläggaren. Den körs med mycket hög prioritet och aktiveras regelbundet, ofta hundratals gånger per sekund, för att avgöra vilken process som ska få köra härnäst. Schemaläggaren har tillgång till information om alla processer i systemet, deras tillstånd, hur länge de senast körde och vilken prioritet de har tilldelats. Baserat på den informationen och den algoritm den implementerar väljer den nästa process att köra och ger den ett tidskvantum, en begränsad tid under vilken den får använda processorn innan schemaläggaren aktiveras igen.

Schemaläggningsalgoritmer: Olika sätt att fördela tid

Det finns inte en enda universell lösning på problemet med hur CPU-tid ska fördelas. Olika användningsfall ställer olika krav, och därför har många olika schemaläggningsalgoritmer utvecklats under datorhistoriens gång. Moderna operativsystem använder ofta hybrider av flera principer.

De enklaste modellerna som grund

Den enklaste tänkbara schemaläggningsalgoritmen är first come, first served. Processer körs i den ordning de anländer till schemaläggaren och får köra klart innan nästa process tar vid. Det är enkelt att förstå och implementera men har uppenbara problem i praktiken. En långvarig process kan blockera alla andra under lång tid, vilket ger dålig responstid för interaktiva användare.

Round robin är ett steg upp i komplexitet och är grundprincipen bakom många moderna schemaläggare. Varje process i kön med redo processer tilldelas ett tidskvantum och får köra under den tiden. När kvantum löper ut avbryts processen och ställs sist i kön, varefter nästa process i kön får sitt kvantum. Det ger en jämn fördelning och garanterar att ingen process behöver vänta längre än ett helt varv runt kön.

Prioritetsbaserad schemaläggning

Round robin i sin renaste form behandlar alla processer lika, vilket inte är optimalt. En tangentbordsinmatning behöver hanteras på millisekunder för att användaren ska uppleva systemet som responsivt, medan en bakgrundsprocess som komprimerar filer kan vänta utan att någon märker det. Prioritetsbaserad schemaläggning löser det genom att tilldela processer olika prioritetsnivåer och alltid välja den redo process med högst prioritet.

Problemet med ren prioritetsbaserad schemaläggning är svält, på engelska starvation. En process med låg prioritet kan i teorin vänta i all evighet om det alltid finns processer med högre prioritet i kön. Lösningen kallas aging: processer som väntat länge får gradvis ökad prioritet tills de till slut hamnar tillräckligt högt för att schemaläggas.

Multilevel feedback queue: Den moderna hybridlösningen

De flesta moderna operativsystem, inklusive Windows, Linux och macOS, använder varianter av en algoritm kallad multilevel feedback queue. Grundidén är att ha flera köer med olika prioritetsnivåer och olika tidskvanta, och att låta processer röra sig mellan köerna baserat på deras beteende.

En ny process börjar i en kö med hög prioritet och kort tidskvantum. Om den använder hela sitt kvantum utan att avbrytas av en vänteopereration klassas den som CPU-intensiv och flyttas ned till en kö med lägre prioritet men längre kvantum. En process som ofta avbryts för att den väntar på inmatning eller nätverk klassas som interaktiv och behåller eller återfår hög prioritet. Systemet lär sig alltså automatiskt hur processer beter sig och schemaläger dem därefter, utan att operativsystemet behöver veta på förhand vad varje process gör.

Prioriteringar, avbrott och vad som kan stjäla CPU-tid

Schemaläggningsalgoritmen är kärnan i hur CPU-tid fördelas, men det finns ytterligare mekanismer som påverkar vilken process som faktiskt körs vid ett givet tillfälle. Hårdvaruavbrott, realtidskrav och operativsystemets egna behov kan alla förändra bilden på ett sätt som inte alltid är synligt för vanliga processer.

Hårdvaruavbrott och deras företräde

När hårdvara behöver uppmärksamhet, till exempel att ett nätverkskort har tagit emot data, att en tangent trycks ned eller att en timer löper ut, skickar hårdvaran ett avbrott till processorn. Processorn avbryter omedelbart det den håller på med, sparar sitt tillstånd och kör den avbrottshanterare som operativsystemet registrerat för den typen av avbrott.

Avbrottshanterare körs med mycket hög prioritet och så kort tid som möjligt. Deras uppgift är att ta hand om det mest akuta, till exempel att kopiera inkommande nätverksdata till en buffert, och sedan väcka den process som väntar på den datan så att schemaläggaren kan ge den CPU-tid vid nästa tillfälle. Det är den mekanismen som gör att ett klick på en knapp i ett program upplevs som omedelbart, även om systemet är belastat.

Realtidsprocesser och deras speciella ställning

Vissa system har processer med strikta tidskrav där en fördröjning inte bara är irriterande utan faktiskt felaktig. Det kan handla om ljud- och videouppspelning, industriell styrutrustning eller medicinska instrument. För sådana processer räcker vanlig prioritetsbaserad schemaläggning inte, eftersom den inte ger några garantier för när en process faktiskt körs.

Realtidsschemaläggning löser det genom att ge vissa processer garanterade tidsramar. Linux implementerar det via schemaläggningspolicyer som SCHED_FIFO och SCHED_RR, som ger realtidsprocesser absolut företräde framför vanliga processer. En realtidsprocess som är redo att köra avbryter alltid en vanlig process, oavsett vad den gör.

Hur användaren och programmeraren påverkar prioriteten

Även om operativsystemet automatiskt justerar prioriteter finns möjligheten att påverka dem manuellt. På Linux och macOS används kommandot nice för att starta en process med lägre prioritet än normalt, eller renice för att justera prioriteten på en redan körande process. Skalan går från minus 20, högsta prioritet, till plus 19, lägsta prioritet. Normala processer startar på 0, och att sätta ett positivt nice-värde är ett sätt att tala om för operativsystemet att en process är ett bakgrundsjobb som inte behöver hög prioritet.

På Windows finns motsvarande funktionalitet via processhanteraren eller via API-anrop i koden. En väldesignad applikation sätter själv sin prioritet baserat på vad den gör:

• Bakgrundstjänster och schemalagda jobb körs med låg prioritet
• Vanliga applikationer körs med normal prioritet
• Ljudmotorer och realtidskomponenter begär förhöjd prioritet
• Kritiska systemtjänster körs med högsta möjliga prioritet

Det är ett samspel mellan operativsystemets automatik och de medvetna val som systemadministratörer och programmerare gör, och tillsammans formar de det som för användaren upplevs som ett system där allt flödar smidigt och parallellt.