Schemaläggning på två nivåer
Schemaläggning på två nivåer är en datavetenskaplig term för att beskriva en metod för att mer effektivt utföra processschemaläggning som involverar utbytta processer .
Tänk på det här problemet: Ett system innehåller 50 pågående processer, alla med samma prioritet. Systemets minne kan dock bara hålla 10 processer i minnet samtidigt. Därför kommer det alltid att finnas 40 processer utbytta skrivna på virtuellt minne på hårddisken. Tiden det tar att byta ut och byta i en process är 50 ms respektive.
Med enkel Round-robin-schemaläggning , varje gång en kontextväxling inträffar, skulle en process behöva bytas in (eftersom endast de 10 minst nyligen använda processerna byts in). Att välja slumpmässigt bland processerna skulle minska sannolikheten till 80 % (40/50). Om det inträffar måste uppenbarligen en process också bytas ut. Att byta in och ut ur är kostsamt, och schemaläggaren skulle slösa mycket av sin tid på att göra onödiga byten.
Det är där schemaläggning på två nivåer kommer in i bilden. Den använder två olika schemaläggare, en schemaläggare på lägre nivå som bara kan välja bland de processer i minnet som ska köras. Den schemaläggaren kan vara en Round-robin schemaläggare. Den andra schemaläggaren är schemaläggaren på högre nivå vars enda uppgift är att byta in och byta ut processer från minnet. Den gör sin schemaläggning mycket mer sällan än schemaläggaren på lägre nivå eftersom byte tar så mycket tid.
Sålunda väljer schemaläggaren på högre nivå bland de processer i minnet som har körts under lång tid och byter ut dem. De ersätts med processer på disk som inte har körts på länge. Exakt hur den väljer processer är upp till implementeringen av schemaläggaren på högre nivå. En kompromiss måste göras som involverar följande variabler:
- Svarstid : En process bör inte bytas ut för länge. Då måste någon annan process (eller användaren) vänta onödigt länge. Om denna variabel inte betraktas resurssvält inträffa och en process kanske inte slutförs alls.
- Processens storlek: Större processer måste vara föremål för färre byten än mindre eftersom de tar längre tid att byta. Eftersom de är större kan färre processer dela minnet med processen.
- Prioritet: Ju högre prioritet processen har, desto längre bör den finnas kvar i minnet så att den slutförs snabbare.
- Tanenbaum , Albert Woodhull, Operativsystem: Design och implementering , s.92