K\u00f6rtiden f\u00f6r varje uppgift \u00e4r k\u00e4nd.<\/li>\n<\/ol>\nSchemal\u00e4ggarens m\u00e4tv\u00e4rden<\/h3>\n \n F\u00f6rutom vissa antaganden om belastningen beh\u00f6vs ocks\u00e5 ett verktyg f\u00f6r att j\u00e4mf\u00f6ra olika schemal\u00e4ggarpolicyer: schemal\u00e4ggarens m\u00e4tv\u00e4rden. En m\u00e4tv\u00e4rde \u00e4r helt enkelt ett m\u00e5tt p\u00e5 n\u00e5got. Det finns ett antal m\u00e4tv\u00e4rden som kan anv\u00e4ndas f\u00f6r att j\u00e4mf\u00f6ra schemal\u00e4ggare.<\/p>\n
Som exempel ska vi anv\u00e4nda en m\u00e4tning som kallas v\u00e4ndtid<\/b> (turnaround time). V\u00e4ndtiden f\u00f6r en uppgift definieras som skillnaden mellan tiden d\u00e5 uppgiften avslutas och tiden d\u00e5 uppgiften anl\u00e4nde till systemet.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Eftersom vi antog att alla uppgifter anl\u00e4nde samtidigt, s\u00e5 \u00e4r Ta=0 och d\u00e4rmed Tt=Tc. Detta v\u00e4rde kommer naturligtvis att \u00e4ndras n\u00e4r vi \u00e4ndrar de ovanst\u00e5ende antagandena.<\/p>\n
En annan m\u00e4tv\u00e4rde \u00e4r r\u00e4ttvisa<\/b> (fairness). Prestanda och r\u00e4ttvisa \u00e4r ofta motstridiga egenskaper inom schemal\u00e4ggning. Till exempel kan en schemal\u00e4ggare optimera prestanda, men p\u00e5 bekostnad av att andra uppgifter f\u00e5r v\u00e4nta, vilket d\u00e4rmed minskar r\u00e4ttvisan.<\/p>\nF\u00d6RST IN F\u00d6RST UT (FIFO)<\/h3>\n
\n Den mest grundl\u00e4ggande algoritmen som vi kan implementera kallas FIFO eller first come (in), first served (out)<\/b>. Denna algoritm har flera f\u00f6rdelar: den \u00e4r mycket enkel att implementera och den passar alla v\u00e5ra antaganden, vilket g\u00f6r att den fungerar ganska bra.<\/p>\n
L\u00e5t oss titta p\u00e5 ett enkelt exempel. Anta att 3 uppgifter st\u00e4llts samtidigt. Men anta att uppgift A kom lite tidigare \u00e4n de andra, s\u00e5 den kommer att st\u00e5 f\u00f6rst i k\u00f6, precis som B i f\u00f6rh\u00e5llande till C. L\u00e5t oss anta att var och en av dem kommer att utf\u00f6ras p\u00e5 10 sekunder. Vad blir d\u00e5 den genomsnittliga tiden f\u00f6r att slutf\u00f6ra dessa uppgifter?<\/p>\n
Det visar sig att olika exekveringstider f\u00f6r uppgifter har en extremt negativ p\u00e5verkan p\u00e5 FIFO-algoritmens produktivitet. Anta att uppgift A kommer att exekveras i 100 sekunder, medan b\u00e5de B och C fortfarande kommer att vara 10 sekunder var.<\/p>\n
karavaneffekten<\/b>, d\u00e4r vissa kortvariga resurskonsumenter st\u00e5r i k\u00f6 efter en tung konsument. Det liknar en k\u00f6 i en livsmedelsbutik, d\u00e4r du st\u00e5r bakom en kund med en full kundvagn. Den b\u00e4sta l\u00f6sningen p\u00e5 problemet \u00e4r att f\u00f6rs\u00f6ka byta kassa eller att slappna av och andas djupt.<\/p>\nKortaste jobb f\u00f6rst<\/h3>\n
\n Finns det n\u00e5got s\u00e4tt att l\u00f6sa en s\u00e5dan situation med tunga processer? Sj\u00e4lvklart. En annan typ av schemal\u00e4ggning kallasKortaste jobb f\u00f6rst<\/b> (SJF). Dess algoritm \u00e4r ocks\u00e5 ganska primitiv \u2014 som namnet antyder, kommer de kortaste uppgifterna att startas f\u00f6rst en efter en.<\/p>\n
50 ist\u00e4llet f\u00f6r 110<\/b>, vilket \u00e4r n\u00e4stan 2 g\u00e5nger b\u00e4ttre.<\/p>\n
S\u00e5ledes, baserat p\u00e5 antagandet att alla uppgifter anl\u00e4nder samtidigt, verkar SJF-algoritmen vara den mest optimala. Men v\u00e5ra antaganden verkar fortfarande inte realistiska. Denna g\u00e5ng \u00e4ndrar vi antagande 2 och f\u00f6rest\u00e4ller oss att uppgifter kan anl\u00e4nda n\u00e4r som helst, snarare \u00e4n alla samtidigt. Vilka problem kan detta leda till?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n F\u00f6r att f\u00f6rb\u00e4ttra situationen sl\u00e4pper vi antagande 3 om att programmet k\u00f6rs och arbetar till dess avslut. Dessutom beh\u00f6ver vi h\u00e5rdvarust\u00f6d och som ni kan gissa, kommer vi att anv\u00e4nda en timer<\/b> f\u00f6r att avbryta en k\u00f6rande uppgift och v\u00e4xla kontexter<\/b>. S\u00e5ledes kan schemal\u00e4ggaren vid ankomsten av uppgifter B, C \u2014 avbryta uppgift A och b\u00f6rja bearbeta uppgifter B och C, och efter deras slutf\u00f6rande forts\u00e4tta k\u00f6ra process A. En s\u00e5dan schemal\u00e4ggare kallas STCF<\/b>eller Preemptive Job First<\/b>.<\/p>\n
Metrik Svarstid (Response Time)<\/h3>\n \n S\u00e5, om vi k\u00e4nner till bearbetningstiden f\u00f6r uppgifterna och att dessa uppgifter bara anv\u00e4nder CPU, skulle STCF vara det b\u00e4sta beslutet. I de tidiga dagarna fungerade dessa algoritmer ganska bra. Men nu tillbringar anv\u00e4ndaren st\u00f6rre delen av sin tid vid terminalen och f\u00f6rv\u00e4ntar ett produktivt interaktivt samspel. S\u00e5 f\u00f6ddes den nya metrik \u2014 svarstid<\/b> (response time).<\/p>\n
Svarstid ber\u00e4knas enligt f\u00f6ljande:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
S\u00e5ledes, i det tidigare exemplet, blir svarstiden: A=0, B=0, C=10 (abg=3,33).<\/p>\n
Och algoritmen STCF \u00e4r faktiskt inte s\u00e5 bra i situationer d\u00e4r tre uppgifter anl\u00e4nder samtidigt - den m\u00e5ste v\u00e4nta tills de sm\u00e5 uppgifterna \u00e4r helt avslutade. S\u00e5ledes \u00e4r algoritmen bra f\u00f6r turnaround-timing, men d\u00e5lig f\u00f6r interaktivitet. T\u00e4nk dig att du sitter vid en terminal och f\u00f6rs\u00f6ker skriva tecken i en redigerare, men du m\u00e5ste v\u00e4nta mer \u00e4n 10 sekunder eftersom en annan uppgift ockuperar processorn. Det \u00e4r inte s\u00e4rskilt trevligt.<\/p>\n
Round Robin<\/h3>\n \n F\u00f6r att l\u00f6sa detta problem har en algoritm utvecklats Round Robin<\/b> (RR). Grundid\u00e9n \u00e4r ganska enkel: ist\u00e4llet f\u00f6r att k\u00f6ra uppgifter tills de \u00e4r helt avslutade, ska vi k\u00f6ra en uppgift under en viss tidsperiod (kallad tidskvant) och sedan v\u00e4xla till en annan uppgift i k\u00f6n. Algoritmen upprepar sitt arbete tills alla uppgifter \u00e4r avslutade. Under tiden m\u00e5ste programmets k\u00f6rtid vara ett multipel av tiden d\u00e5 timern avbryter processen. Till exempel, om timern avbryter processen var tionde millisekund, d\u00e5 b\u00f6r f\u00f6nsterstorleken f\u00f6r processens exekvering vara ett multipel av 10 och vara 10, 20 eller x*10.<\/p>\n
L\u00e5t oss ta ett exempel: Uppgifterna A, B och C anl\u00e4nder samtidigt till systemet och var och en vill k\u00f6ra i 5 sekunder. SJF-algoritmen kommer att utf\u00f6ra varje uppgift till slutet innan den startar en annan. Till skillnad fr\u00e5n detta kommer RR-algoritmen med en k\u00f6rf\u00f6nster p\u00e5 1 sekund att g\u00e5 igenom uppgifterna p\u00e5 f\u00f6ljande s\u00e4tt (se bild 4.3):<\/p>\n
Det genomsnittliga svarstiden f\u00f6r RR-algoritmen (0+1+2)\/3=1, medan f\u00f6r SJF (0+5+10)\/3=5.<\/p>\n
Det \u00e4r rimligt att anta att tidsf\u00f6nstret \u00e4r en mycket viktig parameter f\u00f6r RR; ju mindre det \u00e4r, desto h\u00f6gre \u00e4r responstiden. Dock f\u00e5r man inte g\u00f6ra det f\u00f6r litet, eftersom tiden f\u00f6r kontextbyte ocks\u00e5 kommer att spela sin roll i den \u00f6vergripande prestandan. D\u00e4rf\u00f6r st\u00e4lls tidsf\u00f6nstret in av operativsystemets arkitekt och beror p\u00e5 de uppgifter som planeras att k\u00f6ras. Kontextbyte \u00e4r inte den enda systemoperation som tar tid \u2013 det k\u00f6rda programmet interagerar med m\u00e5nga andra saker, till exempel olika cacher, och vid varje byte m\u00e5ste denna milj\u00f6 sparas och \u00e5terst\u00e4llas, vilket ocks\u00e5 kan ta mycket tid.<\/p>\n
RR \u00e4r en utm\u00e4rkt schemal\u00e4ggare om det endast handlar om responstidsmetrik. Men hur beter sig metrik f\u00f6r uppgiftens oms\u00e4ttningshastighet med denna algoritm? L\u00e5t oss titta p\u00e5 exemplet ovan, d\u00e4r A, B, C = 5s och de kommer in samtidigt. Uppgift A avslutas vid 13, B vid 14, C vid 15s, och den genomsnittliga oms\u00e4ttningstiden blir 14s. D\u00e4rf\u00f6r \u00e4r RR den s\u00e4msta algoritmen f\u00f6r oms\u00e4ttningsmetrik.<\/p>\n
Mer generellt kan man s\u00e4ga att varje algoritm av RR-typ \u00e4r r\u00e4ttvis; den delar CPU-arbetstiden j\u00e4mnt mellan alla processer. Och p\u00e5 s\u00e5 s\u00e4tt st\u00e5r dessa metrikar konstant i konflikt med varandra.<\/p>\n
S\u00e5ledes har vi flera motsatta algoritmer och det kvarst\u00e5r ocks\u00e5 flera antaganden \u2013 att uppgiftens tid \u00e4r k\u00e4nd och att uppgiften endast anv\u00e4nder CPU.<\/p>\n
Blandning med I\/O<\/h3>\n \n F\u00f6rst och fr\u00e4mst ska vi ta bort antagandet 4, att processen bara anv\u00e4nder CPU; det \u00e4r naturligtvis inte s\u00e5, och processerna kan ocks\u00e5 beg\u00e4ra annan h\u00e5rdvara.<\/p>\n
Vid den tidpunkt d\u00e5 en process beg\u00e4r en in- och utmatningsoperation g\u00e5r processen in i ett blockerat tillst\u00e5nd och v\u00e4ntar p\u00e5 att I\/O ska slutf\u00f6ras. Om I\/O skickas till h\u00e5rddisken kan en s\u00e5dan operation ta flera millisekunder eller l\u00e4ngre, och CPU:n kommer vara idle under denna tid. Under denna tid kan schemal\u00e4ggaren anv\u00e4nda CPU:n f\u00f6r en annan process. Den n\u00e4sta beslutsfattning som schemal\u00e4ggaren m\u00e5ste g\u00f6ra \u00e4r n\u00e4r processen kommer att slutf\u00f6ra sin I\/O. N\u00e4r det h\u00e4nder kommer ett avbrott att intr\u00e4ffa, och operativsystemet kommer att \u00f6verf\u00f6ra den process som beg\u00e4rde I\/O till ett redo-tillst\u00e5nd.<\/p>\n
L\u00e5t oss betrakta ett exempel med flera uppgifter. Varje uppgift beh\u00f6ver 50 ms processor tid. Men den f\u00f6rsta kommer att g\u00f6ra ett I\/O-anrop var tionde millisekund (som ocks\u00e5 kommer att k\u00f6ras under 10 ms). Och process B anv\u00e4nder helt enkelt 50 ms processor utan I\/O.<\/p>\n
Oraklet finns inte l\u00e4ngre<\/h3>\n \n L\u00e5t oss nu f\u00f6rs\u00f6ka g\u00f6ra oss av med antagandet att uppgiftens k\u00f6rtid \u00e4r k\u00e4nd. Detta \u00e4r i stort sett det s\u00e4msta och mest orealistiska antagandet p\u00e5 hela listan. Faktiskt vet den genomsnittliga vanliga operativsystemet vanligtvis mycket lite om k\u00f6rtiden f\u00f6r uppgifter, hur skulle vi d\u00e5 bygga en schemal\u00e4ggare utan att veta hur l\u00e4nge en uppgift kommer att k\u00f6ras? Kanske skulle vi kunna anv\u00e4nda vissa principer fr\u00e5n RR f\u00f6r att l\u00f6sa detta problem?<\/p>\n
Resultat<\/h3>\n \n Vi har tittat p\u00e5 grundl\u00e4ggande id\u00e9er om uppgiftsschemal\u00e4ggning och granskat tv\u00e5 familjer av schemal\u00e4ggare. Den f\u00f6rsta k\u00f6r den kortaste uppgiften f\u00f6rst och \u00f6kar d\u00e4rmed genomloppstiden, medan den andra f\u00f6rdelar tiden j\u00e4mnt mellan alla uppgifter, vilket \u00f6kar svarstiden. B\u00e5da algoritmerna \u00e4r d\u00e5liga d\u00e4r de andra familjens algoritmer \u00e4r bra. Vi har ocks\u00e5 sett hur parallell anv\u00e4ndning av CPU och I\/O kan f\u00f6rb\u00e4ttra prestandan, men vi har inte l\u00f6st problemet med operativsystemets clairvoyance. P\u00e5 n\u00e4sta lektion kommer vi att titta p\u00e5 en schemal\u00e4ggare som ser till det n\u00e4rmaste f\u00f6rflutet och f\u00f6rs\u00f6ker f\u00f6ruts\u00e4ga framtiden. Den kallas multi-level feedback queue.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t