Operating Systems ááááºáááº
áá±áž áá¬á! áá»áœááºáá±á¬á·áºá¡ááŒááºá¡á á
áááºáááºá
á¬ážá
áá¬áá±á¬ááºážáá²á· á
á¬áá±áá
áºáá¯ááŒá
áºáá²á· OSTEP áá²á· áá±á¬ááºážáá«ážááœá±ááᯠáá¬áá¬ááŒááºáá¬ážáá²á· á¡áááºážáááºááœá±ááᯠááá·áºá¡á¬áá¯á¶á
áá¯ááºá
á±áá»ááºáá«áááºá á€á¡ááŒá±á¬ááºážá¡áá¬ááẠunix áá²á·ááá¯á·áá±á¬ áááºáááºááŸá¯á
áá
áºáá»á¬ážá áá¯ááºáá±á¬ááºááŸá¯ááᯠá¡áá±á¬áºáá±áž áááºáááºááŸáá¯ááºážááŸáá¯ááºáž ááœá±ážááœá±ážáá¬ážááŒá®ážá ááá¯ááá¯áááºááŸá¬á áá¯ááºáááºážá
ááºáá»á¬ážá á¡áá»áááºááá¬ážááœá²áá°áá»á¬ážá áááºááá¯áá®ááŸáá·áº áá±ááºáá® OS áá
áºáá¯á¡ááŒá
Ạáááºáá®ážáá¬ážááá·áº á¡ááŒá¬ážáá±á¬ á¡áá¬ážáá° á¡á
áááºá¡ááá¯ááºážáá»á¬ážááŸáá·áº á¡áá¯ááºáá¯ááºáá«áááºá áá
á¹á
ááºážá¡á¬ážáá¯á¶ážá áá°áááºážááᯠá€áá±áá¬ááœáẠááŒáá·áºááŸá¯ááá¯ááºáá«áááºá
á€á¡ááŒá±á¬ááºážá¡áá¬á¡ááœáẠáá¬ááºááœá²áááºážááᯠá€áá±áá¬ááœáẠááœá±á·ááá¯ááºáááº-
áá°áááºáž áá°áááºáž áá»áœááºá¯ááºá ááá¯ááºáá±ážááá¯ááºáᬠááá¯ááºáá»á±á¬áá®ááœá±ááŸá¯
á¡ááŒá¬ážá¡á áááºá¡ááá¯ááºážáá»á¬áž-
á¡ááá¯ááºáž 1- áááá«ááºáž á¡ááá¯ááºáž 2- Abstraction- áá¯ááºáááºážá áẠá¡ááá¯ááºáž 3- Process API ááᯠááááºáááºááŒááºážá á¡ááá¯ááºáž 4- á¡á á®á¡á ááºááœá²áá°á¡á¬áž ááááºáááºááŒááºážá á¡ááá¯ááºáž 5- MLFQ á¡á á®á¡á ááºááœá²áá°
áá»áœááºá¯ááºá áá»ááºáááºááœááºáááºáž ááŒáá·áºááŸá¯ááá¯ááºáá«áááºá
á á®á ááºááŒááºáž- á¡ááá·áºáá±á«ááºážá á¯á¶ áá¯á¶á·ááŒááºáá»áẠáááºážá á®
á€áá±á¬ááŒá±á¬ááœá²ááœááºá áá»áœááºá¯ááºááá¯á·ááẠá¡áá»á±á¬áºááŒá¬ážáá¯á¶áž áá»ááºážáááºáááºážáá»á¬ážáá²á០áá
áºáá¯ááᯠáá±á¬áºáá±á¬ááºááŒááºážá ááŒá¿áá¬áá»á¬ážááᯠááœá±ážááœá±ážáá«áááºá
Plan áá¯áá±á«áºáááºá á¡ááá·áºáá±á«ááºážá
á¯á¶ áá¯á¶á·ááŒááºáá»áẠáááºážá
á® (MLFQ)á MLFQ á¡áá»áááºááá¬ážááᯠFernando J. Corbató á០1962 áá¯ááŸá
áºááœáẠá
áááºáá±á¬áºááŒáá²á·áááºá
ááá¯ááºáááºáá±á¬ á¡áá»áááº-áá»áŸáá±ááŒááºážá
áá
Ạ(CTSS)á á€á¡áá¯ááºáá»á¬áž (áá±á¬ááºááá¯ááºážááœáẠáá¯ááºáá±á¬ááºááŸá¯áá»á¬áž á¡áá«á¡áááº
Multics) ááẠTuring Award á¡ááœáẠáá±á¬ááºááá¯ááºážááœáẠá¡áááºá
á¬áááºážáááºááœááºážáá¶áá²á·ááááºá á¡á
á®á¡á
ááºááœá²áá°ááŒá
áºáá²á·áááºá
áá±á¬ááºááá¯ááºážááœáẠááá¯ááá¯áá±á¬ááºážááœááºáá¬áᬠááœá±á·ááŸáááá¯ááºááá·áº á¡ááœááºá¡ááŒááºááᯠáááŸááá²á·áááºá
áá±ááºáá®á
áá
áºá¡áá»áá¯á·á
MLFQ algorithm ááẠá¡ááŒá±áá¶áááºáá±áá±á¬ ááŒá¿áᬠ2 áá¯ááᯠááŒá±ááŸááºážááẠááŒáá¯ážá
á¬ážáááºá
áááá¥á®ážá
áœá¬ááááºáá±á¬ááŒá±á¬ááœá²á áá»áœááºá¯ááºááá¯á· ááœá±ážááœá±ážáá²á·ááá·áºá¡ááá¯ááºážá áááºážá
á®áá°á¡áá»á¬ážá
á¯ááŠážáá±á«ááºážá០á
áááºááá·áºáááºážáááºážááŒáá·áº á¡áá±á¬ááºážáá¯á¶ážááŒá
áºá¡á±á¬áẠááŒá¯áá¯ááºááẠááŒáá¯ážáááºážáááºá
ááá¯áá±á¬ááºážáá±á¬á¡áá¯ááºáá»á¬ážá ááá¯á·áá±á¬áºá OS ááẠဠááá¯á·ááá¯áẠááá¯áá¯ááºáááºážá
ááºááᯠáááºáá»áŸááŒá¬á¡á±á¬áẠáá¯ááºáá±á¬ááºáááºááᯠáááááá±á
SJF, STCF algorithms ááááºáááºááŸá¯á¡ááœááºááá¯á¡ááºáá±á¬á¡ááááá¬á áá¯áááá¡MLFQ ááŒáá¯ážá
á¬ážáááºá
á¡áá¯á¶ážááŒá¯áá°áá»á¬ážá¡ááœáẠá
áá
áºá¡á¬áž áá¯á¶á·ááŒááºááŸá¯ááŒá
áºá
á±ááẠ(á¥ááá¬á ááá¯ááºáá±áá°áá»á¬ážá¡ááœááºá
á¡áá¯ááºááŒá®ážá¡á±á¬ááºá
á±á¬áá·áºáá±á
áẠá
ááááºááᯠá
áá¯ááºááŒáá·áºááŒááºáž) ááŒáá·áº á¡áá»áááºááᯠáá»áŸá±á¬á·áá«á
áá¯á¶á·ááŒááºááŸá¯á áá¶ááá±á¬ááºážá
áœá¬ááŒáá·áºá RR áá²á·ááá¯á· algorithms áá»á¬ážááẠáá¯á¶á·ááŒááºáá»áááºááᯠáá»áŸá±á¬á·áá»áá±ážáá±á¬áºáááºážá
turnaround time metric á¡áá±á«áº ááá¯ážááœá¬ážá
áœá¬ áááºáá±á¬ááºááŸá¯ááŸááááºá ááá¯á·ááŒá±á¬áá·áº áá»áœááºá¯ááºááá¯á·áááŒá¿áá¬- áá®ááá¯ááºážááœá²áááºáž
áá»áœááºá¯ááºááá¯á·áááá¯á¡ááºáá»ááºáá»á¬ážááŸáá·áºááá¯ááºáá®ááá·áºá¡áá»áááºááá¬ážááœá²áááºááŸáá·áºáá
áºáá»áááºáááºážááœááºáá¬áá»áŸááááá«á
áá±áá¯áá»á¡á¬ážááŒáá·áº áá¯ááºáááºážá
ááºá ááá±á¬ááá¬áá á¡á
á®á¡á
ááºááœá²áá°ááẠá¡áá¯ááºáá»á¬ážá áááá±áááá¹ááá¬áá»á¬ážááᯠáááºááá¯á·áá±á·áá¬ááá¯ááºáááºá
áááºážááẠáááºááá·áºá¡áá¬ááᯠá
áááºáá¯ááºáá±á¬ááºááŒá®áž ááá¯ááá¯áá±á¬ááºážááœááºáá±á¬ á¡áá»áááºááá¬ážááœá²áá¯á¶ážááŒááºáá»ááºáá»á¬áž ááŒá¯áá¯ááºááá¯ááºááááºážá
ááŒá¿áá¬áá¡ááŸá
áºáá¬á- ááŒá®ážááŒáá·áºá
á¯á¶áá±á¬á¡ááááá¬áááŸááá² á¡áá¯ááºáá»á¬ážááᯠáááºááá¯á·á
á®á
ááºáááºáááºážá
áá¯á¶á·ááŒááºááŸá¯á¡áá»áááºááᯠáá
áºááŒáá¯ááºáááºáááºáž áá»áŸá±á¬á·áá»ááá¯ááºááá·áº á¡áá»áááºááá¬ážááᯠáááºááá¯á· áá®ááá¯ááºážááœá²áááºáááºážá
á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážáááºáá±á¬ááºáá±á¬á¡áá¯ááºáá»á¬ážá¡ááœááºááŸáá·áºáá
áºáá»áááºáááºážááŸá¬ááááá²ááŸáá·áºáááºááŸá¯á¡áá»áááºááá¯áá»áŸá±á¬á·áá»áááºá
Task execution time ááᯠáááºáá»áœááºážáá«ááá¬ážá
ááŸááºáá»ááº- ááááºááŒá áºáááºáá»á¬ážá០áááºáá°ááŒááºážá
MLFQ áááºážá
á®ááẠáá±á·áá»áá·áºáááºááŒá¬ážáá¬ážááá·áº á
áá
áºá á¡áá±á¬ááºážáá¯á¶áž á¥ááá¬áá
áºáá¯ááŒá
áºáááºá
á¡áá¬áááºááá¯ááŒáá¯áááºááá·áºááŸááºážáááºá¡ááááºááŒá
áºáááºáá»á¬ážá á¡á²áá®ááᯠáá»ááºážáááºáá¬ááœá± áá»á¬ážáá«áááºá
OS ááœááºááœá±á·áááẠ(ááá¯á¡ááá¯ááºážá¡áááºáá»á¬ážá¡áá«á¡ááẠááœááºáá»á°áá¬áááá¹áá¶ááœáẠá¡ááŒá¬ážá¡ááá¯ááºážá¡áááºáá»á¬ážá
áœá¬ááŸááááºá
áá¬á·ááºáá²ááá·áºááŸááºážáá»ááºáá»á¬ážááŸáá·áº ááááºážáááºážááŒááºážááá¯ááºáᬠá¡ááºáááá¯áá®áááºáá»á¬áž)á á¡áá¬ážáá°ááá®ážá
ááºáá»á¬áž
áá¯ááºáááºážáá±á¬ááºáá¬áá»á¬ážááœáẠá¡ááŒá¯á¡áá°á¡ááá·áºáá»á¬ážáá«ááŸáááŒá®áž ááŒáá¯áááºááŸááºážáááá¯ááºááá·áºá¡áá«ááœáẠá¡á
áá»áá¯ážáááºá
ááá¯á·áá±á¬áº ááá·áºááŸááºážáá»ááºáá»á¬ážááẠá¡ááœááºááœááºáá°áá±á¬ááŒá±á¬áá·áº á€áááºážááá¬ááᯠááááá¬ážááá·áºáááºá
ááŸá¬ážááœááºážáá±á¬ áá¯á¶ážááŒááºáá»ááºáá»á¬áž áá»ááŸááºááŒááºážááẠááá¯ááá¯ážáá±á¬ áá¯á¶ážááŒááºáá»ááºáá»á¬áž áá»ááŸááºááẠá
áá
áºá¡á¬áž áŠážáá±á¬ááºááá¯ááºáááº
á¡ááááᬠáá¯á¶ážááááºážáá²á·áá±áááá·áºáááºá
MLFQ- á¡ááŒá±áá¶á ááºážáá»ááºážáá»á¬áž
MLFQ algorithm á á¡ááŒá±áá¶á
ááºážáá»ááºážáá»á¬ážááᯠáá¯á¶ážáááºááŒáá·áºáá«á ဠalgorithm áá¡áá±á¬ááºá¡áááºáá±á¬áºááŸá¯áá»á¬ážá
á¡áá»á¬ážá¡ááŒá¬ážááŸááá«áááºá á¡ááŒá±áá¶áááºážáááºážáá»á¬ážáááºáá°áááºá
áá»áœááºá¯ááºááá¯á·ááá·áºááœááºážá
ááºážá
á¬ážááá·áº á¡áá±á¬ááºá¡áááºáá±á¬áºááŸá¯ááœáẠMLFQ ááœáẠáá»á¬ážá
áœá¬áá«áááºáááºááŒá
áºáááºá
áá®ážááŒá¬ážá
á®áááºážá
á®áá»á¬áž á áá
áºáá¯á
á®ááœáẠááá°áá®áá±á¬ áŠážá
á¬ážáá±ážááŸááá«áááºá á¡áá»áááºáááœá±ážá
áá¯ááºáá±á¬ááºááẠá¡áááºááá·áºááŒá
áºááá·áº á¡áá¯ááºááẠáá°áá®áá±á¬ áááºážá
á®ááá¬ážááœáẠááŸááá±áááºá MLFQ ááẠáŠážá
á¬ážáá±ážáá»á¬ážááᯠá¡áá¯á¶ážááŒá¯áááºá
á¡áá±á¬ááºá¡áááºáá±á¬áºááẠáááºááá·áºáá¬áááºááᯠáá¯ááºáá±á¬ááºááááºááᯠáá¯á¶ážááŒááºáááºá á¥ááá¬á ááŒáá·áºáá¬ážáá±á¬á¡áá¯ááº
áŠážá
á¬ážáá±áž (á¡ááŒáá·áºáá¯á¶ážáŠážá
á¬ážáá±áž áááºážá
á®á០á¡áá¯ááºáá
áºáá¯) ááᯠáááááœáẠá
áááºáá«áááºá
áááºážá
á®áááºá
á¡áá°ážáááŒáá·áº áááºážá
á®áá
áºáá¯ááœáẠá¡áá¯ááºáá
áºáá¯áááºááá¯á ááŒá
áºááá¯ááºáááºá ááá¯á·ááŒá±á¬áá·áºá
áá«ááŒá±á¬áá·áº áá°ááá¯á· ááá¯áá² áŠážá
á¬ážáá±ážáá¯ááºáááºá á€ááá
á¹á
ááœááºááá¹ááá¬ážááá¯á¡áá¯á¶ážááŒá¯áááá·áºáááºá
á¡ááá¯áá« áá¯ááºáááºážáá¬áááºáá»á¬ážááŒá¬ážááœáẠá
áááºááẠá
á®á
ááºááŒááºážá¡ááœáẠRRá
ááá¯á·ááŒá±á¬áá·áº áá»áœááºá¯ááºááá¯á·ááẠMLFQ á¡ááœáẠá¡ááŒá±áá¶á
ááºážáá»ááºáž ááŸá
áºáá¯ááá¯á· áá±á¬ááºááŸáááẠá
- á ááºážáá»ááºáž 1- á¡áááºá áŠážá á¬ážáá±áž(A) > áŠážá á¬ážáá±áž(B)á á¡áá¯áẠA ááẠáá¯ááºáá±á¬ááºááẠ(B áááºááá¯ááºáá«)
- á ááºážáá»ááºáž 2- á¡áááºá áŠážá á¬ážáá±áž(A) = áŠážá á¬ážáá±áž(B)á A&B ááẠRR ááᯠá áááºá¡áá¯á¶ážááŒá¯áá±áá«áááºá
á¡áááºáá«á¡áá»ááºáá»á¬ážá¡áá±á«áºá¡ááŒá±áá¶á MLFQ ááá¯á
á®á
ááºááẠá¡áááá¡áá»ááºáá»á¬ážááŒá
áºáááºá
áŠážá
á¬ážáá±ážááŒá
áºááŒáááºá áá
áºáá¯á
á®ááᯠáá¯á¶áá±áŠážá
á¬ážáá±ážááá·áºá¡á
á¬áž
áá¯ááºáááºážáá¬áááºá MLFQ ááẠáá±á·áá¬ááœá±á·ááŸááá¬ážáá±á¬ á¡áá°á¡áá»áá·áºáá±á«áºáá°áááºá áááºážááŠážá
á¬ážáá±ážááᯠááŒá±á¬ááºážáá²áááºá
á¥ááá¬á¡á¬ážááŒáá·áºá á¡áá¯ááºáá
áºáá¯ááẠáá®ážáá¯ááºááá·áºááœááºážááŸá¯ááá¯á
á±á¬áá·áºááá¯ááºážáá±á
áẠCPU ááœáẠá¡áááºáááŒááºááœááºáá±áá«áá
MLFQ ááẠáá¯ááºáááºážá
ááºááᯠáŠážá
á¬ážáá±áž ááŒáá·áºáá¬ážáá±á
á±áááºááŒá
áºáá±á¬ááŒá±á¬áá·áºá
á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯áá²á· áá¯ááºáááºážá
ááºááœá± áá¯ááºáá±á¬ááºááá·áºáá«áááºá ááá·áºáá»ááºáááºá¡áá±áá²á·ááá¯ááẠá¡áá¯ááºá á¡áááºáááŒááºáá²á·
áá¬áááŒá¬ááŸááºá
áœá¬ CPU ááᯠá¡áá°ážá¡áá±ážáá¬ážááŒá®áž MLFQ ááẠáááºážááᯠá¡ááá·áºááŸááá·áºáá±ážáááºááŒá
áºáááºá
áŠážá
á¬ážáá±ážáá
áºáá¯á ááá¯á·ááŒá±á¬áá·áº MLFQ ááẠáááºážááá¯á·áá¯ááºáá±á¬ááºáá±áá»áááºááœáẠáá¯ááºáááºážá
ááºáá»á¬ážá á¡áá°á¡áá»áá·áºáá»á¬ážááᯠáá±á·áá¬áááºááŒá
áºáááºá
á¡ááŒá¯á¡áá°áá»á¬ážááᯠá¡áá¯á¶ážááŒá¯áá«á
áá
áºáá»áááºáá»áááºááœáẠáááºážá
á®ááŒááºážáá¯á¶á
á¶ááᯠá¥ááá¬áá
áºáá¯ááœá²ááŒáá·áºáá¡á±á¬ááº
á¡áá»áááºáá°ááŒá®ážááẠáá®ááá¯áá»áá¯áž áá
áºáá¯áá¯ááá¬ááŸá¬áá«
á€á¡á
á®á¡á
ááºááœáẠA ááŸáá·áº B áá¯ááºáááºážá
áẠ2 áá¯ááẠá¡ááŒáá·áºáá¯á¶ážáŠážá
á¬ážáá±ážááŒáá·áº áááºážá
á®áá±áááºá áá¯ááºáááºážá
ááº
C ááẠá¡áááºáá±áá¬ááœááºááŸáááŒá®áž áá¯ááºáááºážá
áẠD ááẠáá°áááºážáá¡áá¯á¶ážááœááºááŒá
áºáááºá á¡áááºáá±á¬áºááŒáá«á¡ááá¯ááºáž
MLFQ algorithm ááá±á¬áºááŒáá»ááºá á¡áá»áááºááá¬ážááœá²áá°á á¡ááŒáá·áºáá¯á¶ážá¡áá¯ááºáá»á¬ážááá¯áᬠáá¯ááºáá±á¬ááºáá«áááºá
RR á¡á áŠážá
á¬ážáá±áž á á¡áá¯áẠC á D ááẠá¡áá¯ááºáááŒá
áºáá±á¬á·áá«á
áá¯á¶ááŸááºá¡á¬ážááŒáá·áºá áááºááŒáááºáá±á¬áá»áŸááºáá
áºááŒááºááá¯ááºáá»ááºááẠMLFQ á¡áá¯ááºáá¯ááºáá¯á¶ááᯠá¡ááŒáá·áºá¡á
á¯á¶áá±á¬áºááŒáááºááá¯ááºáá«á
áá¯á¶ááẠá¡áá»áááºááŸáá·áºá¡áá»áŸ ááŒá±á¬ááºážáá²ááœá¬ážáááºááᯠá¡ááá¡áá»áá¬ážáááºááẠá¡áá±ážááŒá®ážáá«áááºá
ááŒáá¯ážá á¬ážááŸá¯ 1- áŠážá á¬ážáá±ážááᯠáááºááá¯ááŒá±á¬ááºážááá²á
á€á¡áá»áááºááœáẠMLFQ ááẠáŠážá
á¬ážáá±ážá¡ááá·áºááᯠáááºááá¯á·ááŒá±á¬ááºážáá²áááºááᯠáááºáá¯á¶ážááŒááºááẠááá¯á¡ááºáááºá
á¡áá¯áẠ(ááá¯á·ááŒá±á¬áá·áº áááºážá
á®áá±ááá·áº á¡áá¯ááºá á¡áá±á¡áá¬áž) ááẠáááºážáááá
ááºáááºážá¡ááœááºážá ááá¯á·
á€á¡ááœááºá áááºááẠá¡áá¯ááºá¡ááœá¬ážá¡áá¬ááᯠááŸááºáá¬ážáá¬ážááẠááá¯á¡ááºáááº- á¡áá»áá¯á·áá±á¬ ááá¬á
ááá¯áá±á¬ááºážáá±á¬á¡áá»áááºáá»á¬ážááŸáá·áºá¡áá° á¡ááŒááºá¡ááŸááºáá¯ááºáá±á¬ááºáá±á¬ áá¯ááºáá±á¬ááºá
áá¬áá»á¬áž (ááá¯á·ááŒá±á¬áá·áº áááŒá¬áá áá¯ááºááœáŸááºáááºá
CPU) ááŸáá·áº CPU ááẠáááºážááá¯á·á á¡áá¯ááºáá¯ááºáá»áááºáá
áºáá»áŸá±á¬ááºáá¯á¶áž á¡áá¯á¶ážááŒá¯ááá·áº ááŸááºáá»á¬ážáá±á¬ á¡áá¯ááºáá»á¬ážá
áœá¬ááᯠáá¯ááºáá±á¬ááºáááºá
ááá¯ááá¯á·áá±á¬á¡áá¯ááºáá»á¬ážá¡ááœáẠáá¯á¶á·ááŒááºáá»áááºááẠá¡áá±ážáááŒá®ážáá«á áá«á០ááẠááááá¯á¶áž ááŒáá¯ážá
á¬ážááá¯ááºááŸá¬áá«á
MLFQ algorithm ááᯠá¡á±á¬ááºáá«á
ááºážáá»ááºážáá»á¬ážááŒáá·áº á¡áá±á¬ááºá¡áááºáá±á¬áºáá«-
- á ááºážáá»ááºáž 3- áá¯ááºáá±á¬ááºá áá¬áá áºáá¯ááẠá áá áºáá²ááá¯á· áááºáá±á¬ááºáá±á¬á¡áá«á áááºážááᯠá¡ááŒáá·áºáá¯á¶ážáááºážá á®ááœáẠááá·áºááœááºážáá¬ážáááºá
- áŠážá á¬ážáá±ážá
- Rule4a- á¡áá¯ááºáá áºáá¯ááẠáááºážá á¡áá»áááºáááºážááá¯ážáá áºáá¯áá¯á¶ážááᯠá¡áá¯á¶ážááŒá¯áá«áá áááºážááᯠá¡áá¯á¶ážááŒá¯áá«á
- áŠážá á¬ážáá±ážááᯠáá»áŸá±á¬á·áá»áá¬ážáááºá
- Rule4b- á¡áá¯ááºáá áºáá¯ááẠáááºážáá¡áá»áááºáááºážááá¯ážááá¯ááºáá¯á¶ážáá® CPU ááᯠáá¯ááºááœáŸááºáá«áá áááºážááẠáááºážá¡á¬áž á¡áá»áááºáá¯ááºááœá¬ážá á±áááºá
- áá°áá®áá±á¬ áŠážá á¬ážáá±ážááŸá¯ááŒáá·áº áááºááŸááá±áá«áááºá
á¥ááᬠ1- áá áºáá¯áááºážáá±á¬ áá±ááŸááºá¡áá¯ááº
á€á¥ááá¬ááœááºáááºááœá±á·ááŒááºááá¯ááºáááºá¡ááá¯ááºážá áááºááœáá·áºááœááºáá¬áááºááá¯á¡ááŒáá·áºáá¯á¶ážááŒáá·áºáááºááŸááºáá¬ážáááºá
áŠážá
á¬ážáá±ážá 10ms á¡áá»áááºáááºážááá¯ážáá
áºáá¯ááŒá®ážáá±á¬ááºá áá¯ááºáááºážá
ááºááᯠáŠážá
á¬ážáá±ážá¡ááá·áºááá¯á· á¡ááá·áºááŸááá·áºáá¬ážáááºá
á¡á
á®á¡á
ááºááœá²áá°á áá±á¬ááºáá
áºááŒááẠáááºážááá¯ážááŒá®ážáá±á¬ááºá áá±á¬ááºáá¯á¶ážááœáẠáá¯ááºáá±á¬ááºá
áá¬ááᯠá¡ááá·áºáá»áŸá±á¬á·áá»ááá¯ááºáá«áááºá
áá»ááºááŸáááá·áºá
áá
áºááœáẠá¡áááá·áºáá¯á¶ážáŠážá
á¬ážáá±ážá
á¥ááᬠ2- ááá¯áá±á¬ááºážáá±á¬ á¡áá¯ááºáá
áºáá¯ááᯠáá±á¬ááºáá°áá²á·áááºá
ááᯠMLFQ ááẠSJF ááᯠáá»ááºážáááºááẠáááºááá¯á·ááŒáá¯ážá
á¬ážáááºááᯠááá°áá¬ááŒáá·áºááŒáá«á
áá¯á·á á¡á²áá®áá²ááŸá¬
á¥ááá¬- á¡áá¯ááºááŸá
áºáá¯- A ááẠáá±ááŸááºáááºááá·áºáá±ááá·áº á¡áá¯ááºáá
áºáá¯ááŒá
áºáááºá
ááá¯áá±á¬ááºážáá±á¬ á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯áá±á¬ á¡áá¯ááºááŒá
áºááá·áº CPU ááŸáá·áº B ááᯠááááºážááá¯ááºááŒááºážá ááá¯áá«á
áá¯á·
á¡áá¯áẠB áá±á¬ááºááŸááá¬áá»áááºááœáẠA ááẠá¡áá»áááºá¡áá±á¬áºááŒá¬á¡á±á¬áẠáá¯ááºáá±á¬ááºáá±ááŒá®ááŒá
áºáááºá
á€ááááºááẠáá¬ááºáááºážáááááºáá»á¬ážááᯠááŒááááºá Task A ááẠáááºááá·áºá¡áá¯ááºááŸáá·áºáá°áááºá
CPU ááá¯á¡áá¯á¶ážááŒá¯á á¡á±á¬ááºááŒá±ááœááºááŸááá²á·áááºá Task B ááẠá¡áá»ááẠT=100 ááŸáá·áº áá±á¬ááºááŸááá¬áááá·áºáááºá
á¡ááŒáá·áºáá¯á¶ážáŠážá
á¬ážáá±ážáááºážá
á®ááœáẠááá·áºááœááºážáá¬ážáááºá ááŒá±ážáá»áááºá ááá¯áá±á¬ááŒá±á¬áá·áºá
áá±á¬ááºáá¯á¶ážáááºážá
á®áááŒá®ážáá® á¡ááŒá®ážáááºáá«áááºá
á€á¥ááá¬ááŸá áááºááẠalgorithm á á¡ááááááºážááá¯ááºááᯠáá¬ážáááºááá·áºáááº- algorithm ááá«áá±á¬ááŒá±á¬áá·áºá
ááŸááºáá»á¬ážáá±á¬á¡áá¯áẠááá¯á·ááá¯áẠááá¯ááá¯áá
áºáá¯ááᯠáááááºá ááá¯á·áá±á¬áẠááá¯áá¬áááºááᯠáŠážá
áœá¬áá¶áá°áááºá
ááá¯ááá¯ááŸáá·áº áááºážááᯠá¡ááŒáá·áºáá¯á¶áž áŠážá
á¬ážáá±ážáááºá ááááºá ááá¯áá±á¬ááºážáá²á· á¡áá¯ááºáá
áºáá¯ááá¯áááºá
áááºážááẠáá»ááºááŒááºá
áœá¬ áá¯ááºáá±á¬ááºááá¯ááºáááºááŒá
áºááŒá®ážá ááá¯á·ááá¯ááºáá«á áááºážááẠááŸááºáá»á¬ážáá±á¬á¡áá¯ááºááŒá
áºáá»áŸáẠááŸá±ážááœá±ážá
áœá¬ ááœá±á·áá»á¬ážáááºááŒá
áºáááºá
áŠážá
á¬ážáá±ážá¡á¬ážááŒáá·áº ááŸááá·áºáá»ááŒá®áž áá°áááẠá¡ááŸááºáááẠááá¯ááºááá¯ááºáá±á¬ ááŸááºáá»á¬ážáá±á¬ á¡áá¯ááºááŒá
áºááŒá±á¬ááºáž áááŒá¬áá® áááºáá±ááŒáááá·áºáááºá
áá¯á¶á·ááŒááºááŸá¯áá
áºáá¯ááá¯á¡ááºáááºá
á¥ááᬠ3- I/O áá±á¬ áááºááá¯áá²á
á¡áᯠI/O á¥ááá¬ááᯠááŒáá·áºáá¡á±á¬ááºá áááºážá¥ááá± 4b ááœááºáá±á¬áºááŒáá¬ážááá·áºá¡ááá¯ááºážá
áá¯ááºáááºážá
ááºáá
áºáá¯ááẠáááºážááááá¯áááºáá¬á¡áá»áááºááᯠá¡ááŒáá·áºá¡áá¡áá¯á¶ážáááŒá¯áá² áááá¯áááºáá¬ááᯠáá¯ááºááœáŸááºáá«áá
ááá¯á·áá±á¬áẠáááºážááẠáá°áá®áá±á¬ áŠážá
á¬ážáá±ážá¡ááá·áºááœáẠááŸááá±áááºá áá®á
ááºážáá»ááºážáá²á· áááºááœááºáá»ááºá áá±á¬áºáá±á¬áºááá¯ážááŸááºážáá«áááºá
- á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯áá±á¬á¡áá¯ááºááẠI/O á¡áá»á¬ážá¡ááŒá¬ážáá¯ááºáá±á¬ááºáá«áá á¥ááá¬á á
á±á¬áá·áºááá¯ááºážááŒááºážá
á¡áá¯á¶ážááŒá¯áá° áá®ážá
ááá ááá¯á·ááá¯áẠáá±á¬ááºá
áºááŸá ááá¯ááá¯á·áá±á¬ á¡áá¯ááºááẠáááá¯áááºáá¬ááᯠááœááºá
á±áááºááŒá
áºáááºá
áá»áá¬ážáá±ážáá±á¬ááŒáááºážáá±á«ááºááŸá±á·ááŸá¬á áá®ááᯠáŠážá
á¬ážáá±ážá¡áá¯ááºáá»áá¯ážááᯠáá»áœááºáá±á¬áºááá¯á· áá»ááºááŸááºááá¬ážáá»ááºáá«áá°ážá
ááá¯á·ááŒá±á¬áá·áº áááºážááẠáá°áá®áá±á¬á¡ááá·áºááœáẠááŸááá±áááºááŒá
áºáááºá
á€á¥ááá¬ááẠalgorithm ááẠááá¯áá²á·ááá¯á·áá±á¬ áá¯ááºáááºážá
ááºáá»á¬ážááŸáá·áº áááºááá¯á·á¡áá¯ááºáá¯ááºáááºááᯠááŒáááẠ- á¡ááŒááºá¡ááŸááºáá¯ááºáá±á¬ááºááá·áºá¡áá¯áẠBá ááá¯ááºáá±á¬ááºáá® CPU ááẠ1ms á¡ááœááºáᬠááá¯á¡ááºáááº
CPU ááᯠáá
áºáá»áááºáá¯á¶áž á¡áá¯á¶ážááŒá¯áá±ááá·áº I/O ááŸáá·áº A ááŸááºáá»á¬ážáá±á¬ á¡áá¯ááºá
MLFQ ááẠáá¯ááºáááºážá
áẠB ááᯠá¡ááŒáá·áºáá¯á¶ážáŠážá
á¬ážáá±ážá¡ááŒá
Ạáááºáááºáá¬ážááŸááá¬ážáááºá
CPU ááá¯áá¯ááºáá«á B ááẠá¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯ááá·áºá¡áá¯ááºááŒá
áºáá«áá á€ááá
á¹á
ááœáẠalgorithm ááẠáá±á¬ááºááŸáááœá¬ážáá«ááŒá®á
áááºážá áááºááœááºáá»ááºááŸá¬ á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯ááá·áº áá¯ááºáááºážáá±á¬ááºáá¬áá»á¬ážááᯠáá»ááºááŒááºá
áœá¬ á
áááºáááºááŒá
áºáááºá
áááºááŸá MLFQ á¡ááºáááá¯áá®áááºááŸáá·áº ááŒá¿áá¬áá»á¬áž
ááááºááá°áá¬áá»á¬ážááœááºá áá»áœááºá¯ááºááá¯á·ááẠMLFQ á á¡ááŒá±áá¶áá¬ážááŸááºážááᯠáááºáá±á¬ááºáá¬ážáá«áááºá ááŒá®ážáá±á¬á· áá°á áááºáá±á¬ááºáááºá
áááºážááẠáááºážáá¡áá¯ááºá¡á¬áž áá±á¬ááºážááœááºáá»áŸáá
áœá¬ áá¯ááºáá±á¬ááºááŒá®áž CPU á¡áá»áááºááᯠáá»áŸáá
áœá¬ ááœá²áá±áá±ážáááºá
ááŸááºáá»á¬ážáá±á¬áá¯ááºáá±á¬ááºá
áá¬áá»á¬ážááŸáá·áº ááá¯áá±á¬ááºážáá±á¬áá¯ááºáá±á¬ááºá
áá¬áá»á¬áž ááá¯á·ááá¯áẠááŒá®ážáá¬ážá
áœá¬áááºáá±á¬ááºá¡áá¯á¶ážááŒá¯áá±á¬ á¡áá¯ááºáá»á¬ážááᯠááœáá·áºááŒá¯ááŒááºážá
áá»ááºááŒááºá
áœá¬áá¯ááºáá±á¬ááºááẠI/O ááá¯á·á áá¶ááá±á¬ááºážá
áœá¬ááŒáá·áºá á€áá»ááºážáááºááŸá¯ááœáẠáá»á¬ážá
áœá¬áá«áááºáá«áááºá
ááŒááºážáááºáá±á¬ááŒá¿áá¬áá»á¬ážá
áááá¥á®ážá
áœá¬, áááºááœááºáá±á«ááºážáá«ážááŸá¯ááŒá¿áá¬: á
áá
áºá¡áá»á¬ážá¡ááŒá¬ážá¡ááŒááºá¡ááŸááºá¡áá»áá¯ážáááºáá±á¬ááºááŸá¯ááŸááááá·áºáááºá
á¡áá¯ááºáá»á¬ážááẠCPU áá¡áá»áááºá¡á¬ážáá¯á¶ážááᯠáá¯á¶ážá
áœá²áááºááŒá
áºááŒá®ážá ááá¯á·ááŒá±á¬áá·áº áá
áºááŒáááºáá»áŸ ááŒá¬áááºááá¯ááºáá±á
ááá¯áá¬áááºááᯠá¡áá±á¬ááºá¡áááºáá±á¬áºááẠá¡ááœáá·áºá¡áááºáž ááááá·áºááẠááá¯ááºáá± (áá°ááá¯á· áááºáá±ááŒáááº)á
áá¯áááá¡áá«ááŒá±á¬áá·áº á
áááºáá»áá²á· áá¯á¶ážá
áœá²áá°ááœá±áᬠáá°ááá¯á·áá²á· áááá¯ááááºááœá±ááᯠáá±ážááá¯ááºáá«áááºá
á¡á
á®á¡á
ááºááŸá°ážááᯠááŸáá·áºá
á¬ážáá«á ááŸáá·áºá
á¬ážááŸá¯ááẠá¡áááºážá¡ááŒááºáá¯ááºááẠáá
áºáá¯áá¯áá¯ááºááŒááºážá áá¯áá¬ááŒá
áºáááºá
áá¯ááºáááºážá
ááºááᯠCPU á¡áá»áááºááá¯áá±ážááá¯ááºááẠá
á®á
ááºáá±ážáááºá algorithm á á¡á²áá«
á¡áááºááœááºáá±á¬áºááŒáá¬ážáá±á¬ ááá¯ááºááá¯ááºááŸá¯áá»á¬ážááẠá¡áá»áááºááŒáááºážáá±á«ááºááᯠáááºááœá±á·áá»áá» ááá¯ááºáá±á¬ááºáá®á
áá»á±á¬áºááŒá®á áááºááẠI/O áá¯ááºáá±á¬ááºáá»ááºááᯠáá¯ááºáá±á¬ááºááẠááá¯á¡ááºááẠ(á¡áá»áá¯á·á¡ááœááºá áááºááá·áºááá¯ááºáááá¯)
ááá¯á·ááŒá±á¬áá·áº CPU ááᯠááœááºá
á±áááºá áá®ááá¯á¡ááŒá¯á¡áá°áá»áá¯ážá áááºážááᯠá¡áá°áá°áá±ááá¯ááºá
á±áááá·áºáááºá
áááºážá
á®ááẠáá°á·áá¬áá¬áá°ááŒá
áºááŒá®áž CPU á¡áá»áááºá ááá¯áá»á¬ážáá±á¬ áá¬ááá¯ááºááŸá¯ááºážááᯠáááºáá¶áááŸááááºá ááŒá®ážááŒá®ááá¯áá»áŸááº
áááºážáááºááŸááºáááºááẠ(á¥ááᬠCPU ááá¯ááá¯ááºáá® window á¡áá»áááºá 99% ááᯠrun)á
ááá¯ááá¯á·áá±á¬á¡áá¯ááºááẠáááá¯áááºáá¬ááᯠááá¯ážááŸááºážá
áœá¬ áááºáá«ážááŒá®ážá¡á¯ááºááá¯ááºáááºá
áá±á¬ááºáá¯á¶ážááœááºá áááá¯ááááºáá
áºáá¯ááẠá¡áá»áááºááŸáá·áºá¡áá»áŸ áááºážáá¡ááŒá¯á¡áá°ááᯠááŒá±á¬ááºážáá²ááá¯ááºáááºá áá±áá±á·
CPU ááá¯á¡áá¯á¶ážááŒá¯áá¬ážáá±á¬ááŒá±á¬áá·áº á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážáááºáá±á¬ááºááŸá¯ááŸáááá¯ááºáá«áááºá áá»áœááºá¯ááºááá¯á·áá¥ááá¬ááœááºá á¡áá¬ážáá°
á¡áá¯ááºáá»á¬ážááẠá¡ááŒá¬ážáá°áá»á¬ážáá²á·ááá¯á· á¡áá»áááºááá¬ážááœá²áá°áá¶á០ááá·áºáá»á±á¬áºáá±á¬ áá¯áááŸá¯ááᯠáááŸááááºááá¯ááºáá«á
(áá°áááºáž) á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯áá±á¬ á¡áá¯ááºáá»á¬ážá
ááááááºááᯠáá±ážááœááºážáá¯ááºáááº- áá±ááºáá®ááá¹áá¬ááœáẠá¡áá»áááºááá¬ážááœá²áá°ááᯠáááºááá¯á·ááá¯ááºááá¯ááºááá¯ááºááááºážá
ááŒáá¯ážá á¬ážááŸá¯ 2- áŠážá á¬ážáá±ážááŸá¯ááᯠááá¯ážááŒáŸáá·áºáá«á
á
ááºážáá»ááºážááœá±ááᯠááŒá±á¬ááºážáá²ááŒá®áž ááŒá¿áá¬ááœá±ááᯠááŸá±á¬ááºááŸá¬ážááá¯ááºááá¬ážááá¯áᬠááŒáá·áºáá¡á±á¬ááº
áááºááœááºááŒááºáž áááºá
ááºáá±áá»á¬á¡á±á¬áẠáá¬áá¯ááºááá¯ááºááá²á
CPU áá¯ááºáá±á¬ááºáá»ááºáá»á¬ážááẠáááºážááá¯á·áá¡áá»ááẠ(áááŒá¬áá«) ááá¯áááŸááááºááŒá
áºáááºá
ááŒá¿áá¬á¡ááœáẠááá¯ážááŸááºážáá±á¬á¡ááŒá±áá
áºáá¯á¡áá±ááŒáá·áº áááºááẠá¡áá«á¡á¬ážáá»á±á¬áºá
áœá¬ á¡ááŒá¶ááŒá¯ááá¯ááºáá«áááºá
á
áá
áºá¡ááœááºážááŸá ááá¯áá²á·ááá¯á·áá±á¬ á¡áá¯ááºáá»á¬ážá¡á¬ážáá¯á¶ážááᯠáŠážá
á¬ážáá±ážáá¯ááºáá±á¬ááºáá«á áááºážáááºážáá»á¬ážá
áœá¬ááŸááá«áááºá
áá«ááá¯á¡á±á¬ááºááŒááºááá¯á·á¡ááœááºá á¥ááá¬áá
áºáá¯á¡áá±áá²á· ááá¯ážááá¯ážááŸááºážááŸááºážáá
áºáá¯áá¯ááᯠá¡áá±á¬ááºá¡áááºáá±á¬áºááŒáá·áºáá¡á±á¬ááº- áá¬áá¬ááŒááºáá«á
á¡áá¯ááºá¡á¬ážáá¯á¶ážááᯠáá
áºááŒáá¯ááºáááºáááºáž á¡ááŒáá·áºáá¯á¶ážáŠážá
á¬ážáá±áž ááŒá
áºáá±á¬ááŒá±á¬áá·áº á
ááºážáá»ááºážá¡áá
áº-
- áááºážá¥ááá±5: á¡áá»áá¯á·áá±á¬áá¬á S ááŒá®ážáá±á¬ááºá á áá áºá¡ááœááºážááŸá áá¯ááºáá±á¬ááºá áá¬á¡á¬ážáá¯á¶ážááᯠá¡ááŒáá·áºáá¯á¶ážáááºážá á®ááá¯á· ááœáŸá²ááŒá±á¬ááºážáá«á
áá»áœááºá¯ááºááá¯á·áá
ááºážáá»ááºážá¡áá
áºááẠááŒá¿áá¬ááŸá
áºáá¯ááᯠáá
áºááŒáá¯ááºáááºáááºáž ááŒá±ááŸááºážáá±ážáááºá áááá áá¯ááºáááºážá
ááºáá»á¬áž
á¡á
á¬ááááºá
á±ááẠá¡á¬ááá¶áá«áááº- á¡ááŒáá·áºáá¯á¶ážáááºážá
á®ááŸá á¡áá¯ááºáá»á¬ážááᯠáá»áŸáá±áá«áááºá
RR algorithm á¡á áááá¯áááºáá¬á¡áá»áááºááẠáá¯ááºáááºážá
ááºáá»á¬ážá¡á¬ážáá¯á¶áž áááºáá¶áááŸááááºááŒá
áºáááºá
áááá¯áááºáá¬á¡áá»áááºá áá¯áááá¡áá»ááºá¡áá±áá²á·ááá¯ááẠá¡áááºááá¯á¶ážáá²á· process áá
áºáá»áá¯á·áá«á
áááá¯áááºáá¬áááºáᬠá¡ááŒááºá¡ááŸááºá¡áá»áá¯ážáááºáá±á¬ááºááŸá¯ááŸááááºá áááºážááẠá¡ááŒáá·áºáá¯á¶ážáááºážá
á®ááœáẠááŸááá±áááºááŒá
áºáááºá
áŠážá
á¬ážáá±ážááŸá¯ááᯠá¡ááŒáá·áºáá¯á¶áž áŠážá
á¬ážáá±ážááᯠáá
áºááŒááẠááá¯ážááŒá®áž áááºáá¶áá«á
á¥ááá¬áá
áºáá¯ááᯠáá¯á¶ážáááºááŒáá·áºáá¡á±á¬ááºá á€á¡ááŒá±á¡áá±ááœááºá áá¯ááºáááºážá
ááºáá
áºáá¯áááºážááᯠá¡áá¯á¶ážááŒá¯á á
ááºážá
á¬ážáá«á
CPU ááŸáá·áº á¡ááŒááºá¡ááŸááºá¡áá»áá¯ážáááºáá±á¬ááºááŸá¯á ááá¯áá±á¬ááºážáá±á¬ áá¯ááºáááºážá
ááºááŸá
áºáá¯á áá¯á¶ááŸá áááºáááºááœááºá ááááºážááááºážááẠáŠážá
á¬ážáá±áž ááŒáŸáá·áºáááºááŒááºážáááŸááá² á¡ááŒá¯á¡áá°ááᯠááŒááááºá ááá¯á·ááŒá±á¬áá·áº á
áá
áºááœáẠá¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯áá±á¬ áá¯ááºáá±á¬ááºá
áá¬ááŸá
áºáá¯áá±á¬ááºááŸáááŒá®ážáá±á¬áẠáá±ááŸááºáá¯ááºáá±á¬ááºáá±á¬á¡áá¯ááºááẠáááºá
ááŒá¯áá¬áááºá áá¬áááºááŸá áá¯á¶ááœááºá 50ms ááá¯ááºážááœáẠáŠážá
á¬ážáá±áž ááá¯ážááŒáŸáá·áºááŸá¯ááᯠáá¯ááºáá±á¬ááºááŒá®áž ááá¯á·ááŒá±á¬áá·áº áá¯ááºáááºážá
ááºá¡á¬ážáá¯á¶ážááᯠáááá¯áááºáá¬á¡áá»áááºáááŸáááẠá¡á¬ááá¶áá¬ážááŒá®áž á¡áá»áááºá¡áá«á¡ááá¯áẠá
áááºáááºááŒá
áºáááºá á€ááá
á¹á
ááœáẠ50ms ááᯠááá°áá¬á¡ááŒá
Ạáá°áááºá ááááºáá±á¬á· á€ááááºážááááºážááẠá¡áááºááẠááá¯ááŒáá·áºáááºá
Periodic rise time S ááᯠáá±á«ááºážááá·áºááá¯ááºáá¬á áááºááŸá¬ážáá«áááºá
áá¯áá¹ááááŸááá±á¬áá±ážááœááºáž- áááºááá·áºáááºááá¯ážááᯠáááºááŸááºááá·áºááááºážá ááŒááºá
áœá¬áá¯áá¬ážááẠáá±á¬ááºážá
áœá¬ áá¶ááá¯ááºáá
á
áá
áºá¡ááºáá»ááºáá®áá¬áá»á¬áž John Ousterhout ááẠá
áá
áºáá»á¬ážááœáẠá¡áá¬ážáá°ááá¬ááá»á¬ážááᯠvoo-doo áᯠáááºááœáŸááºážáá²á·áááºá
áá
áºáááºážáá
áºáá¯á¶á¡á¬ážááŒáá·áº ááŸááºáááºáá±á¬ á¡á±á¬ááºáááºážááá¬ááᯠááá¯á¡ááºáá±á¬ááŒá±á¬áá·áº á¡á
ááºá¡ááŒá²
ááááœá±á·ááŒááºážá áá¶ááá±á¬ááºážá
áœá¬áá²á S ááŸá¬ áá®ááá¯á¡ááá¬ááŸááááºá áááºááá¯ážáááºááŸááºáá¬áááºáž ááŸááááºá
ááŒá®ážáá¬ážáá±á¬á¡áá¯ááºáá»á¬áž áááºáááºá áááá·áºááœááºážáááºá
á¡ááŒááºá¡ááŸááºáá¯á¶á·ááŒááºáá¯ááºáá±á¬ááºááŸá¯áá»á¬ážááẠááá·áºáá»á±á¬áºáá±á¬ CPU á¡áá»áááºááᯠáááŸááááºááá¯ááºáá«á
ááŒáá¯ážá á¬ážááŸá¯ 3: ááá¯ááá¯áá±á¬ááºážááœááºáá±á¬á á¬áááºážááá¯ááº
ááᯠáá»áœááºá¯ááºááá¯á·ááœáẠááŒá±ááŸááºážááẠáá±á¬ááºááẠááŒá¿áá¬áá
áºáᯠááŸááá±áááº- áááºááá¯á·áá»áŸ áááŒá±ááŸááºážááá¯ááºáá«á
áá»áœááºá¯ááºááá¯á·á á¡á
á®á¡á
ááºááœá²áá°ááᯠááŸáá·áºá
á¬ážááœáá·áºááŒá¯áá«áá¬ážá áá®ááŒá
áºááá¯ááºáá»á±áá²á· ááá¬ážáá¶ááœá±áá«á
áááá¯áááºáá¬ááᯠááœáŸááºááá¯ááºááŒááºážááŒáá·áº á¡áá¯ááºáá
áºáá¯ááẠáááºážááŠážá
á¬ážáá±ážááŸá¯ááᯠááááºážáá¬ážááá¯ááºá
á±ááá·áº 4aá 4b á
ááºážáá»ááºážáá»á¬áž
áááºááŸááºáá»áááºááá¯ááºáá¯á¶ážáá®á á¡á²áá«ááᯠáááºááá¯ááŒá±ááŸááºážááá²á
á€ááá
á¹á
ááœáẠááŒá±ááŸááºážáá»ááºááẠáá
áºáá¯á
á®áá±á«áºááœáẠCPU á¡áá»áááºááᯠááá¯ááá¯áá±á¬ááºážááœááºá
áœá¬ ááœááºáá»ááºááŒááºážáᯠáá°áááá¯ááºáááºá
MLFQ á¡ááá·áºá áááá¯ááááºá¡áá¯á¶ážááŒá¯ááá·áºá¡áá»áááºááᯠáá±á·ááœá¬ážááá·áºá¡á
á¬ážá
áááá¯áááºáá¬ááẠáá»áá¬ážáá±ážááá·áº ááŒá¬ážáá¬áá¡ááœááºá áááºááẠáááºážááᯠááááºážáááºážááá·áºáááºá ááŒá®ážáá±á¬ááº
áá¯ááºáááºážá
ááºááẠáááºážá ááœá²áá±áá±ážááá·áºá¡áá»áááºááᯠáá¯ááºáá¯á¶ážááœá¬ážááŒá®á áááºážááᯠáá±á¬ááºáá
áºáá¯ááá¯á· áá»áŸá±á¬á·áá»ááá·áºáááºá
áŠážá
á¬ážáá±ážá¡ááá·áºá ááᯠáá¯ááºáááºážá
ááºááẠáááºážáá¡áá»áááºááᯠáááºááá¯á·áááºáá¯á¶ á¡áá¯á¶ážááŒá¯áááºááᯠá¡áá±ážáááŒá®ážáá«á
áááá¯áááºáᬠááá¯á·ááá¯áẠáá±á«áºááá¯ááŸá¯á¡á
á¯áá
áºáá¯á¡ááŒá
Ạá¡áááºáááŒáẠááœááºáá»ááºááŒááºážá ááá¯á·ááŒá±á¬ááºá·,
áááºážá¥ááá± á ááᯠá¡á±á¬ááºáá«á¡ááá¯ááºáž ááŒááºáááºáá±ážáá¬ážááá·áºááẠá
- áááºážá¥ááá±4: á¡áá¯ááºáá áºáá¯ááẠáááºááŸááááºážá á®ááœáẠáááºážáááœá²áá±áá»áá¬ážáá±ážááá·áºá¡áá»áááºááᯠá¡áá¯á¶ážááŒá¯ááŒá®ážáá±á¬áẠ(CPU ááᯠá¡ááŒáááºáááºáá»áŸááœáŸááºáá±ážáá²á·áááºááŒá áºá á±)á ááá¯áá¯ááºáááºážá áŠážá á¬ážáá±ážááẠáá»á±á¬á·ááœá¬ážááẠ(áááºážááẠáááºážá á®ááŒááºážááᯠá¡á±á¬ááºááá¯á·ááœáŸá±á·áááº)á
á¥ááá¬áá
áºáá¯ááá¯ááŒáá·áºáá¡á±á¬ááºá
»
á¡á
á®á¡á
ááºááœá²áá°áá²á·ááá¯á· ááŸáá·áºá
á¬ážááẠááŒáá¯ážá
á¬ážáá«á áááºááá¯á·ááŒá
áºáááºááᯠáá¯á¶ááœááºááŒáááºá
ááááºá
ááºážáá»ááºáž 4a ááŸáá·áºááá¯áá»áŸáẠ4b ááẠáááºáááºááŸá ááááºááŒá
áºáááºá á¡áá
áºááŸáá·áº
á
ááºážáááºážá ááááºá áá¬áááºááŸá¬ááŸááááºá áá¬ááœááºááŸá¯áááŒá¯áá®á áááºááá·áºáá¯ááºáááºážá
ááºáááᯠáááŒá®ážáá® I/O áá±á«áºááá¯ááá¯ááºáááºá
ááá¯á·ááŒá±á¬áá·áº á¡ááŒá¯á¡áá°ááᯠáááœá²ááŒá¬ážáá² áá¬ááœááºááŸá¯ááᯠááœáá·áºááŒá®ážáá±á¬áẠCPU ááᯠááœáŸááºážááá¯ážáá¬ážáááºá
I/Oá áá°á áááºážá
á®áá±áá±ážáá²á·á¡ááœáẠáááá¯ážááá¬áž áá¯ááºááá¯ááºááŸá¬ ááá¯ááºáá«áá°ážá
CPU á¡áááºážá¡ááŒá
áºáá»á¬ážááá¯ááá°áá«á
MLFQ ááŸáá·áº á¡ááŒá¬ážááŒá¿áá¬áá»á¬ážááᯠááá¯ážáááºá á±ááŒááºážá
á¡áááºáá« ááá¯ážáááºááŸá¯áá»á¬ážááŒáá·áº ááŒá¿áá¬á¡áá
áºáá»á¬áž áá±á«áºáá±á«ááºáá¬áááº- á¡ááá áá
áºáá»ááº
áá±ážááœááºážáá»á¬áž - ááá¯ááá¯á·áá±á¬á¡áá»áááºááá¬ážááá¯áááºááá¯á·ááá·áºáááºáááºáááºážá á¡á²áá«ááœá±á áááºáá±á¬ááºáá»ááá·áºáá²á
áááºážá
á®? áááºážá
á®áá±ááá·áº áááá¯ááááºáááºážááá¯ážá á¡ááœááºá¡á
á¬ážááẠá¡áááºáááºážá áááºááá¯áá²
áááºááœááºáá±á«ááºážáá«ážááŸá¯ááᯠááŸá±á¬ááºááŸá¬ážáááºááŸáá·áº áááá¯ááááºááᯠáááŒá¬áá áŠážá
á¬ážáá±ážáá¯ááºáá±á¬ááºááá·áºáááºá
áááá¯ááááºá á¡ááŒá¯á¡áá°ááŒá±á¬ááºážáá²ááŸá¯ááᯠááá·áºááœááºážá
ááºážá
á¬ážáááºá áá®áá±ážááœááºážááœá±á¡ááœááºáá±á¬á· ááá¯ážááá¯ážááŸááºážááŸááºážáááŸááá«áá°ážá
áá¯á¶á·ááŒááºááŸá¯ááŸáá·áº áááºáá¯ááºáááºááá¯ážáá»á¬ážááŸáá·áº áá±á¬ááºáááºááœá²ááœá²á·á
ááºážááŸá¯ááá¯ááºáᬠá
ááºážáááºááŸá¯áá»á¬ážáá¬ááŒá
áºáááºá
á¡áá»áááºááá¬ážááœá²áá°ááẠáá»á±áááºááœááºáá¬áááºáá»ááºááᯠááŒá
áºáá±á«áºá
á±ááá¯ááºáááºá
á¥ááá¬á¡á¬ážááŒáá·áºá MLFQ á¡áá±á¬ááºá¡áááºáá±á¬áºááŸá¯á¡áá»á¬ážá
á¯ááẠááá·áºá¡á¬áž ááá°áá®áá±á¬áá¬áááºáá±ážááŸá¯áá»á¬ážááᯠááœáá·áºááŒá¯áá±ážáááºá
ááá°áá®áá±á¬áááºážá
á®áá»á¬ážá¡ááœáẠá¡áá»áááºááœááºáá»á¬ážá á¡áá»á¬ážá¡á¬ážááŒáá·áº áŠážá
á¬ážáá±ážáááºážá
á®ááŒááºážáá»á¬áž
ááá¯áá±á¬ááºážáá±á¬áá¬ááá»á¬ážá á€á
á®áááºážáá»á¬ážááẠá¡ááŒááºá¡ááŸááºá¡áá»áá¯ážááŒá¯ááá·áº á¡áá¯ááºáá»á¬ážáá«áááºáááºá
á¡ááœááºá¡áá²áááºááŒá®áž 10 ááá¯á·ááá¯áẠááá¯áááºáááºážáá±á¬ á¡áá¬áá»á¬ážá¡ááŒá¬áž áá°ážááŒá±á¬ááºážááŒááºážá
áá±á«áºá ááá·áºáá»ááºáááºá¡á¬ážááŒáá·áºá áŠážá
á¬ážáá±áž áááºážá
á®ááŒááºážáá»á¬ážááœáẠáá±ááŸááºá¡áá¯á¶ážááŒá¯ááá·áº á¡áá¯ááºáá»á¬áž áá«áááºáá«áááºá
á
á®áá®áá°á á€ááá
á¹á
ááœááºá ááŸááºáá»á¬ážáá±á¬ááŒá¬ážáá¬ááá»á¬ážááẠá¡ááœááºá¡áááºááŒá±ááẠ(100ms)á
á€á¥ááá¬ááœááºá áŠážá
á¬ážáá±ážá¡ááá·áº 2 ááœáẠáá¯ááºáá±á¬ááºáá²á·áá±á¬ á¡áá¯áẠ20 áá¯ááŸááááºá
ms ááᯠ10ms windows ááŒáá·áº ááá¯ááºážááŒá¬ážáá¬ážáááºá á¡áááºáááºážáááºážááœáẠ40ms (20ms áááºážááá¯áž) ááŸáá·áº áŠážá
á¬ážáá±ážáááºážá
á®ááœáẠXNUMXms
áááºážá
á®áá»áááºáááºážááá¯ážááẠ40ms ááŒá
áºáá¬ááŒá®áž á¡áá¯ááºáá»á¬ážááᯠáááºážááá¯á·áá¡áá¯ááºááŒá®ážááŒá±á¬ááºá
á±áááºá
Solaris OS ááœáẠMLFQ ááᯠá¡áá±á¬ááºá¡áááºáá±á¬áºááŒááºážááẠá¡áá»áááºááœá²áá±ááŸá¯ á¡á
á®á¡á
ááºáá»á¬áž á¡áá»áá¯ážá¡á
á¬ážáá
áºáá¯ááŒá
áºáááºá
á¡áá»áááºááá¬ážááœá²áá°ááẠáááºážááᯠáááºááá¯á·áá¯ááºááá·áºáááºááᯠáááááá»áá»áááºááŸááºáá±ážááá·áº ááá¬ážá¡á
á¯á¶ááᯠáá±ážáááá·áºáááºá
áááºážááááá
áºáá»áŸá±á¬ááºáá¯á¶áž áá¯ááºáááºážá
ááºá áŠážá
á¬ážáá±ážá á¡ááœááºá¡á
á¬ážááŒá
áºááá·áºáááºáá»á¬ážááᯠááŒá±á¬ááºážáá²áá«á
ááœá²áá±áááºááŸááºáááá·áº áááºážááá¯ážááŸáá·áº á¡áá¯ááºáŠážá
á¬ážáá±ážáá»á¬ážááᯠáááºáá»áŸááŒá¬ááŒá¬ ááŒáŸáá·áºáááºáááºá á¡á¯ááºáá»á¯ááºáá±ážááŸá°áž
á
áá
áºááẠá€ááá¬ážááŸáá·áº á¡ááŒááºá¡ááŸáẠáá¯á¶á·ááŒááºááá¯ááºááŒá®áž á¡á
á®á¡á
ááºáá±ážááœá²áá°ááᯠááŒá¯áá°á
á±áááºá
ááá°áá«á áá¯á¶ááŸááºá¡á¬ážááŒáá·áºá á€ááá¬ážááœáẠáááºážá
á® áá ááŸáááŒá®áž áááŒááºážááŒááºáž ááá¯ážáá¬áááºá
áááºážááá¯ážá¡ááœááºá¡á
á¬áž 20ms (ááŒáá·áºáá¬ážáá±á¬áŠážá
á¬ážáá±áž) á០áá¬ááááºáž ms (á¡áááá·áºáá¯á¶ážáŠážá
á¬ážáá±áž) ááŸáá·áº
á¡áá¯ááºá¡á¬ážáá¯á¶ážááᯠáá
áºá
áá¹ááá·áºáá»áŸáẠáá
áºááŒááẠááŒáŸáá·áºáááºáá«á
á¡ááŒá¬áž MLFQ á¡áá»áááºááá¬ážááœá²áá°áá»á¬ážááẠááá¬ážáá
áºáᯠááá¯á·ááá¯áẠáá®ážááŒá¬ážáááºááá·áºá¡áá¬ááá¯áá»áŸ ááá¯á¶ážáá«á
á€á¡áááºážááœááºáá±á¬áºááŒáá¬ážáá±á¬ á
ááºážáá»ááºážáá»á¬ážááẠááá·áºáá»ááºáááºá¡áá±ááŸáá·áº áááºážááá¯á·ááẠáŠážá
á¬ážáá±ážáá»á¬ážááᯠá¡áá¯á¶ážááŒá¯á ááœááºáá»ááºáá«áááºá
áááºá¹áá»á¬áá±á¬áºááŒá°áá¬áá»á¬ážá á¥ááá¬á FreeBSD ááŸá á¡áá»áááºááá¬ážááœá²áá°ááẠáá±á¬áºááŒá°áá¬ááᯠá¡áá¯á¶ážááŒá¯áááºá
áá¯ááºáááºážá
ááºáááºáá»áŸá¡áá±á«áºá¡ááŒá±áá¶á áááºááŸááá¯ááºáááºážáŠážá
á¬ážáá±ážááᯠááœááºáá»ááºááŒááºážá
CPU ááá¯áá¯á¶ážáááºá ááá¯á·á¡ááŒááºá CPU á¡áá¯á¶ážááŒá¯ááŸá¯ááẠá¡áá»áááºááŒá¬áá¬áááºááŸáá·áºá¡áá»áŸ ááá¯ááœááºážáá¬áááºá
ááá¯á·ááŒá±á¬áá·áº áŠážá
á¬ážáá±ážááá¯ážááŸá¯ááẠá¡áááºááœááºáá±á¬áºááŒáá¬ážáááºááẠá¡áááºážáááºááœá¬ááŒá¬ážáá«áááºá áá«á¡ááŸááºáá«áá²
decay algorithms áá¯áá±á«áºáááºá áá¬ážááŸááºáž 7.1 á¡á FreeBSD ááẠULE á¡áá»áááºááá¬ážááᯠá¡áá¯á¶ážááŒá¯áááºá
áá±á¬ááºáá¯á¶ážááœááºá á¡á
á®á¡á
ááºáá±ážááœá²áá°á¡áá»á¬ážá¡ááŒá¬ážááœáẠá¡ááŒá¬ážá¡ááºá¹áá«áááºáá»á¬ážááŸááááºá á¥ááᬠáá
áºáá»áá¯á·
á¡áá»áááºááá¬ážááá¬ážáá»á¬ážááẠáááºáááºááŸá¯á
áá
áºááááºáááºááŸá¯á¡ááœáẠááá¯ááá¯ááŒáá·áºáá¬ážáá±á¬á¡ááá·áºáá»á¬ážááᯠááá¯ááŸá±á¬ááºáá¬ážáá±á¬ááŒá±á¬áá·áºááŒá
áºáááºá
ááá¯á·ááŒá±á¬áá·áº áááºááá·áº user process á០á¡ááŒáá·áºáá¯á¶áž áŠážá
á¬ážáá±áž ááááá¯ááºáá«á
á
áá
áºá á¡áá»áá¯á·áá±á¬á
áá
áºáá»á¬ážá ááá·áºá¡á¬áž á¡áá°á¡áá®áá±ážááẠá¡ááŒá¶áá¬ááºáá»á¬ážáá±ážááá¯ááºáááºá
ááŸááºáááºá
áœá¬ áŠážá
á¬ážáá±ážááẠá¡á
á®á¡á
ááºááœá²áá°á á¥ááá¬á¡á¬ážááŒáá·áº command ááᯠá¡áá¯á¶ážááŒá¯ áá±á¬ááºážáá²á·
á¡áá¯ááºáá
áºáá¯á áŠážá
á¬ážáá±ážááŸá¯ááᯠááá¯ážááá¯ááºááẠááá¯á·ááá¯áẠáá»áŸá±á¬á·áá»ááá¯ááºááŒá®áž ááá¯á·ááŒá±á¬áá·áº ááá¯ážááá¯ááºááẠááá¯á·ááá¯áẠáá»áŸá±á¬á·áá»ááá¯ááºáááºá
CPU á¡áá»áááºá¡ááœáẠáááá¯ááááºá á¡ááœáá·áºá¡áááºážáá»á¬ážááᯠáá»áŸá±á¬á·áá»áá«á
MLFQ- á¡áá»ááºážáá»á¯ááº
áá»áœááºá¯ááºááá¯á·ááẠMLFQ áá¯áá±á«áºáá±á¬ á¡á
á®á¡á
ááºááœá²ááŒááºážáááºážáááºážááᯠáá±á¬áºááŒáá¬ážáá«áááºá áá°á·áá¬áááº
áááºáááºááŸá¯áááá¬áá¡á áááá¯á¶ážáá»á¯ááºáá¬ážááẠ- áááºážááœáẠáááºážá
á®ááŒááºážáá»á¬ážá
áœá¬ááŸáááŒá®áž áá¯á¶á·ááŒááºáá»ááºááᯠá¡áá¯á¶ážááŒá¯áááºá
á¡áá¯ááºáá
áºáá¯ááᯠáŠážá
á¬ážáá±ážáááºá
á
ááºážáááºážáá»ááºá áá±á¬ááºáá¯á¶ážáá¯á¶á
á¶ááŸá¬ á¡á±á¬ááºáá«á¡ááá¯ááºážááŒá
áºáá«áááºá
- áááºážá¥ááá±1á¡áááºá áŠážá á¬ážáá±áž(A) > áŠážá á¬ážáá±áž(B)á á¡áá¯áẠA ááẠáá¯ááºáá±á¬ááºááẠ(B ááœáẠááá«ááŸááá«)á
- áááºážá¥ááá±2: á¡áááºá priority(A) = Priority(B)á A&B ááẠRR ááᯠá áááºá¡áá¯á¶ážááŒá¯áá±áá«áááºá
- áááºážá¥ááá±3áá¯ááºáá±á¬ááºá áá¬áá áºáá¯ááẠá áá áºáá²ááá¯á· áááºáá±á¬ááºáá±á¬á¡áá«á áááºážááᯠá¡ááŒáá·áºáá¯á¶áž áŠážá á¬ážáá±ážáááºážá á®ááœáẠááá·áºááœááºážáá¬ážáááºá
- áááºážá¥ááá±4: á¡áá¯ááºáá áºáá¯ááẠáááºááŸááááºážá á®ááœáẠáááºážáááœá²áá±áá»áá¬ážáá±ážááá·áºá¡áá»áááºááᯠá¡áá¯á¶ážááŒá¯ááŒá®ážáá±á¬áẠ(CPU ááᯠá¡ááŒáááºáááºáá»áŸááœáŸááºáá±ážáá²á·áááºááŒá áºá á±)á ááá¯áá¯ááºáááºážá áŠážá á¬ážáá±ážááẠáá»á±á¬á·ááœá¬ážááẠ(áááºážááẠáááºážá á®ááŒááºážááᯠá¡á±á¬ááºááá¯á·ááœáŸá±á·áááº)á
- áááºážá¥ááá±5: á¡áá»áá¯á·áá±á¬áá¬á S ááŒá®ážáá±á¬ááºá á áá áºá¡ááœááºážááŸá áá¯ááºáá±á¬ááºá áá¬á¡á¬ážáá¯á¶ážááᯠá¡ááŒáá·áºáá¯á¶ážáááºážá á®ááá¯á· ááœáŸá²ááŒá±á¬ááºážáá«á
MLFQ ááẠá¡á±á¬ááºáá«á¡ááŒá±á¬ááºážááŒáá»ááºááŒá±á¬áá·áº á
áááºáááºá
á¬ážá
áá¬áá±á¬ááºážááẠ- ááŸáá·áºáááºáááºáá±á¬ ááá¯áá¯ááá»á¬ážááá¯á¡ááºááŒááºážá¡á
á¬áž
á¡áá¯ááºáááá±á¬ááá¬áááá¯ááŒáá¯áááºá algorithm ááẠá¡áá¯ááºááŸáá·áº set áá»á¬ážáá¡ááááºá¡ááŒá¯á¡áá°ááá¯áá±á·áá¬áááºá
áŠážá
á¬ážáá±ážá¡ááá¯ááºá ááá¯á·ááŒá±á¬áá·áº áá°ááẠáá±ážáááºáá±á¬á¡áá¯ááºáá»á¬áž (SJFá STCF) á¡ááœáẠá
áœááºážáá±á¬ááºáááºáááŸááááºááŸáá·áº ááá¯ážáá¬ážá
áœá¬ áá¬ááŸááºáá¯ááºáá±á¬ááºááẠáá¯áá¬ážááá¯ááºááŸá
áºáá¯á¶ážáá±á«áºááœáẠáá
áºááŒáááºáááºážááá¯ááºááẠááŒáá¯ážá
á¬ážáááºá
CPU-loading á¡áá¯ááºáá»á¬ážá ááá¯á·ááŒá±á¬áá·áº BSD ááŸáá·áº áááºážááá¯á·á áááºážáááºáá¬ááŸá¯áá»á¬áž á¡áá«á¡ááẠá
áá
áºáá»á¬ážá
áœá¬á
Solarisá Windowsá Mac ááẠá¡á
á®á¡á
ááºááœá²áá°á¡ááŒá
Ạá¡áá»áá¯á·áá±á¬ algorithm áá¯á¶á
á¶ááᯠá¡áá¯á¶ážááŒá¯áááºá
MLFQ ááᯠá¡ááŒá±áá¶á¡áá»ááºá¡ááŒá
áºá
á¡ááá¯áá±á¬ááºážáá á¹á ááºážáá»á¬áž:
manpages.debian.org/stretch/manpages/sched.7.en.html en.wikipedia.org/wiki/Scheduling_ (ááœááºáá»á°áá¬)pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf chebykin.org/freebsd-process-scheduling
source: www.habr.com