Gabatarwa zuwa Tsarukan Ayyuka
Hai Habr! Ina so in kawo muku jerin labarai-fassarar wallafe-wallafe guda ɗaya mai ban sha'awa a ra'ayina - OSTEP. Wannan abu yayi magana sosai game da aikin tsarin aiki-kamar unix, wato, aiki tare da matakai, masu tsarawa daban-daban, ƙwaƙwalwar ajiya, da sauran abubuwa makamantan waɗanda suka haɗa da OS na zamani. Kuna iya ganin asalin duk kayan anan . Da fatan za a lura cewa fassarar an yi ta ne ba da ƙwararru ba (da yardar rai), amma ina fata na riƙe ma'anar gaba ɗaya.
Ana iya samun aikin Lab akan wannan batu a nan:
Sauran sassa:
Hakanan zaka iya duba tashar ta a =)
Gabatarwa ga Mai tsara tsarawa
Asalin matsalar: Yadda ake haɓaka manufofin tsara jadawalin
Yaya ya kamata a tsara tsarin tsare-tsaren tsare-tsare na asali? Menene ya kamata ya zama mahimmin zato? Wadanne ma'auni ne masu mahimmanci? Wadanne dabaru na asali aka yi amfani da su a farkon tsarin kwamfuta?
Hasashen Ayyukan Aiki
Kafin mu tattauna yiwuwar manufofin, bari mu fara yin ƴan sauƙaƙan ra'ayoyin game da hanyoyin da ke gudana a cikin tsarin, waɗanda ake kira tare. nauyin aiki. Ƙayyade nauyin aiki wani muhimmin ɓangare ne na manufofin gine-gine, kuma mafi yawan sanin aikin aiki, mafi kyawun manufofin da za ku iya rubutawa.
Bari mu yi zato masu zuwa game da hanyoyin da ke gudana a cikin tsarin, wani lokaci kuma ana kiran su jobs (ayyuka). Kusan duk waɗannan zato ba gaskiya bane, amma sun zama dole don haɓaka tunani.
- Kowane aiki yana gudanar da adadin lokaci guda,
- Ana saita dukkan ayyuka lokaci guda,
- Aikin da aka ba shi yana aiki har sai an kammala shi.
- Duk ayyuka suna amfani da CPU kawai,
- An san lokacin gudu na kowane aiki.
Ma'aunin Jadawalin
Bugu da ƙari ga wasu zato game da kaya, ana buƙatar wani kayan aiki don kwatanta manufofin tsarawa daban-daban: ma'auni mai tsarawa. Ma'auni shine kawai ma'aunin wani abu. Akwai ma'auni da yawa waɗanda za a iya amfani da su don kwatanta masu tsara jadawalin.
Misali, za mu yi amfani da ma'auni da ake kira lokacin juyawa (lokacin juyawa). An bayyana lokacin juyawa ɗawainiya azaman bambanci tsakanin lokacin kammala aikin da lokacin isowar aiki a cikin tsarin.
Tturnaround=Kammala-Tarival
Tun da mun ɗauka cewa duk ayyuka sun zo a lokaci guda, sannan Ta = 0 kuma haka Tt = Tc. Wannan ƙimar za ta canza a zahiri lokacin da muka canza zato na sama.
Wani ma'auni - adalci (adalci, gaskiya). Yawan aiki da gaskiya sune halaye masu gaba da juna a cikin tsarawa. Misali, mai tsara jadawalin na iya inganta aikin, amma a farashin jiran wasu ayyuka don gudana, don haka rage adalci.
FARKO A FARKO (FIFO)
Mafi mahimmancin algorithm wanda zamu iya aiwatarwa shine ake kira FIFO ko fara shigo (a), fara hidima (fita). Wannan algorithm yana da fa'idodi da yawa: yana da sauƙin aiwatarwa kuma ya dace da duk tunaninmu kuma yana yin aikin sosai.
Bari mu kalli misali mai sauƙi. Bari mu ce an saita ayyuka 3 lokaci guda. Amma bari mu ɗauka cewa aikin A ya zo kadan a baya fiye da sauran, don haka zai bayyana a cikin jerin kisa a baya fiye da sauran, kamar B dangane da C. Bari mu ɗauka cewa za a kashe kowannensu na 10 seconds. Menene matsakaicin lokaci don kammala waɗannan ayyuka a cikin wannan yanayin?
Ta hanyar kirga dabi'u - 10 + 20 + 30 da rarraba ta 3, muna samun matsakaicin lokacin aiwatar da shirin daidai da 20 seconds.
Yanzu bari muyi kokarin canza tunaninmu. Musamman, zato na 1 don haka ba za mu ƙara ɗauka cewa kowane ɗawainiya yana ɗaukar adadin lokaci ɗaya don aiwatarwa ba. Ta yaya FIFO za ta yi wannan lokacin?
Kamar yadda ya fito, lokuta daban-daban na aiwatar da ayyuka suna da mummunar tasiri akan yawan aiki na FIFO algorithm. Bari mu ɗauka cewa aikin A zai ɗauki daƙiƙa 100 don kammalawa, yayin da B da C za su ɗauki daƙiƙa 10 kowanne.
Kamar yadda ake iya gani daga adadi, matsakaicin lokacin tsarin zai kasance (100+110+120)/3=110. Ana kiran wannan tasirin tasirin convoy, lokacin da wasu masu amfani na ɗan gajeren lokaci na albarkatun za su yi layi bayan mabukaci mai nauyi. Kamar layi ne a kantin kayan miya lokacin da akwai abokin ciniki a gabanka da cikakken karusa. Mafi kyawun maganin matsalar shine ƙoƙarin canza rajistar kuɗi ko shakatawa da numfashi mai zurfi.
Gajeren Aiki Na Farko
Shin yana yiwuwa a ko ta yaya warware irin wannan yanayin tare da matakai masu nauyi? Tabbas. Wani nau'in shiri ake kiraGajeren Aiki Na Farko (SJF). Algorithm ɗin sa shima na daɗaɗɗe ne - kamar yadda sunan ke nunawa, za a fara ƙaddamar da mafi guntu ayyuka da farko, ɗaya bayan ɗaya.
A cikin wannan misali, sakamakon gudanar da matakai guda ɗaya zai zama ingantawa a cikin matsakaicin lokacin juyawa na shirin kuma zai kasance daidai. 50 maimakon 110, wanda kusan sau 2 yafi kyau.
Don haka, don zato da aka ba da cewa duk ayyuka sun zo a lokaci guda, SJF algorithm alama shine mafi kyawun algorithm. Duk da haka, zatonmu har yanzu ba su zama na gaske ba. Wannan lokacin muna canza zato 2 kuma wannan lokacin tunanin cewa ayyuka na iya kasancewa a kowane lokaci, kuma ba duka a lokaci ɗaya ba. Wadanne matsaloli ne wannan zai iya haifarwa?
Bari mu yi tunanin cewa aikin A (100c) ya zo da farko kuma ya fara aiwatar da shi. A t=10, ayyuka B da C sun zo, kowannensu zai ɗauki daƙiƙa 10. Don haka matsakaicin lokacin aiwatarwa shine (100+(110-10)+(120-10))3 = 103. Menene mai tsarawa zai iya yi don inganta wannan?
Mafi Gajeren Lokaci don Kammala Farko (STCF)
Domin inganta yanayin, mun bar zato na 3 cewa an ƙaddamar da shirin kuma yana aiki har zuwa ƙarshe. Bugu da ƙari, za mu buƙaci tallafin hardware kuma, kamar yadda kuke tsammani, za mu yi amfani da su saita lokaci don katse wani aiki mai gudana da mahallin sauyawa. Don haka, mai tsara jadawalin zai iya yin wani abu a wannan lokacin ayyuka B, C sun zo - dakatar da aiwatar da aikin A kuma sanya ayyukan B da C cikin sarrafawa kuma, bayan kammala su, ci gaba da aiwatar da tsari A. Ana kiran irin wannan mai tsara jadawalin. STCFko Aiki Na Farko Na Farko.
Sakamakon wannan mai tsarawa zai kasance sakamako mai zuwa: ((120-0)+(20-10)+(30-10))/3=50. Don haka, irin wannan jadawali ya zama mafi kyawu ga ayyukanmu.
Lokacin Amsa Aiki
Don haka, idan mun san lokacin gudu na ayyukan kuma waɗannan ayyukan suna amfani da CPU kawai, STCF zai zama mafi kyawun mafita. Kuma sau ɗaya a farkon lokutan, waɗannan algorithms sunyi aiki sosai. Koyaya, mai amfani yanzu yana ciyar da mafi yawan lokacinta a tashar kuma yana tsammanin ƙwarewar hulɗa mai amfani. Ta haka aka haifi sabon ma'auni - lokacin amsawa (amsa).
An ƙididdige lokacin amsa kamar haka:
Tresponse=Tfirstrun-Tarival
Don haka, don misalin da ya gabata, lokacin amsa zai zama: A=0, B=0, C=10 (abg=3,33).
Kuma ya bayyana cewa STCF algorithm ba shi da kyau sosai a cikin halin da ake ciki inda ayyuka 3 suka zo a lokaci guda - zai jira har sai an kammala ƙananan ayyuka gaba ɗaya. Don haka algorithm yana da kyau ga ma'aunin lokacin juyawa, amma mara kyau ga ma'aunin hulɗa. Ka yi tunanin idan kuna zaune a tashar tashar tana ƙoƙarin rubuta haruffa a cikin edita kuma kuna jira fiye da daƙiƙa 10 saboda wani aiki yana ɗaukar CPU. Ba dadi sosai.
Don haka muna fuskantar wata matsala - ta yaya za mu iya gina na'ura mai tsarawa wanda ke kula da lokacin amsawa?
Zagaye Robin
An ƙirƙiri wani algorithm don magance wannan matsala Zagaye Robin (RR). Babban ra'ayin yana da sauƙi: maimakon gudanar da ayyuka har sai an kammala su, za mu gudanar da aikin na wani ɗan lokaci (wanda ake kira lokaci yanki) sannan mu canza zuwa wani aiki daga jerin gwano. Algorithm yana maimaita aikinsa har sai an kammala duk ayyukan. A wannan yanayin, lokacin gudu na shirin dole ne ya zama maɓalli na lokaci bayan haka mai ƙidayar lokaci zai katse aikin. Misali, idan mai ƙidayar lokaci ya katse tsari kowane x=10ms, to girman taga aiwatar da tsari yakamata ya zama mahara 10 kuma ya zama 10,20 ko x*10.
Bari mu dubi misali: Ayyukan ABC suna zuwa lokaci guda a cikin tsarin kuma kowannensu yana so ya yi gudu na 5 seconds. Algorithm na SJF zai kammala kowane ɗawainiya kafin fara wani. Sabanin haka, RR algorithm tare da taga ƙaddamarwa = 1s zai bi ta ayyukan kamar haka (Fig. 4.3):
(SJF Again (Bad for Response Time)
(Round Robin (Mai Kyau Don Lokacin Amsa)
Matsakaicin lokacin amsawa na RR algorithm shine (0+1+2)/3=1, yayin da SJF (0+5+10)/3=5.
Yana da ma'ana a ɗauka cewa taga lokacin shine ma'auni mai mahimmanci ga RR; ƙarami shine, mafi girman lokacin amsawa. Koyaya, bai kamata ku sanya shi ƙanƙanta ba, tunda lokacin sauya yanayin mahallin shima zai taka rawa a aikin gabaɗaya. Don haka, zaɓin lokacin taga kisa an saita shi ta hanyar ƙirar OS kuma ya dogara da ayyukan da aka shirya aiwatarwa a ciki. Sauyawa mahallin ba shine kawai aikin sabis ɗin da ke ɓata lokaci ba - shirin mai gudana yana aiki akan wasu abubuwa da yawa, alal misali, caches daban-daban, kuma tare da kowane canji ya zama dole don adanawa da dawo da wannan yanayin, wanda kuma zai iya ɗaukar abubuwa da yawa. lokaci.
RR babban mai tsarawa ne idan muna magana ne kawai game da awo lokacin amsawa. Amma ta yaya ma'aunin juyar da aikin zai kasance tare da wannan algorithm? Yi la'akari da misalin da ke sama, lokacin da lokacin aiki na A, B, C = 5s kuma ya zo a lokaci guda. Aiki A zai ƙare a 13, B a 14, C a 15s kuma matsakaicin lokacin juyawa zai zama 14s. Don haka, RR shine mafi munin algorithm don ma'aunin juyawa.
A cikin ƙarin sharuɗɗa na gabaɗaya, kowane nau'in algorithm na nau'in RR daidai ne; yana rarraba lokacin CPU daidai tsakanin duk matakai. Sabili da haka, waɗannan ma'auni suna cin karo da juna akai-akai.
Don haka, muna da algorithms masu bambanta da yawa kuma a lokaci guda har yanzu akwai sauran zato da yawa - cewa an san lokacin aiki kuma aikin yana amfani da CPU kawai.
Haɗuwa da I/O
Da farko, bari mu cire zato 4 cewa tsari yana amfani da CPU kawai; a zahiri, wannan ba haka bane kuma matakai na iya samun dama ga wasu kayan aiki.
Lokacin da kowane tsari ya buƙaci aiki na I/O, tsarin zai shiga cikin yanayin da aka katange, yana jiran I/O ya kammala. Idan an aika I/O zuwa rumbun kwamfutarka, to irin wannan aiki na iya ɗaukar ms da yawa ko ya fi tsayi, kuma processor ɗin zai kasance mara amfani a wannan lokacin. A wannan lokacin, mai tsarawa zai iya mamaye processor tare da kowane tsari. Shawara ta gaba mai tsara jadawalin zai yanke ita ce lokacin da tsarin zai kammala I/O. Lokacin da wannan ya faru, katsewa zai faru kuma OS zai sanya tsarin da ake kira I/O a cikin shirye-shiryen.
Bari mu kalli misalin matsaloli da yawa. Kowannensu yana buƙatar 50ms na lokacin CPU. Koyaya, na farko zai shiga I/O kowane 10ms (wanda kuma za'a aiwatar dashi kowane 10ms). Kuma tsarin B kawai yana amfani da processor 50ms ba tare da I/O ba.
A cikin wannan misali za mu yi amfani da tsarin STCF. Yaya mai tsara tsarin zai kasance idan an ƙaddamar da tsari kamar A akan shi? Zai yi abubuwan da ke biyowa: na farko zai aiwatar da tsarin A gaba ɗaya, sannan aiwatar da B.
Hanyar gargajiya don magance wannan matsala ita ce ɗaukar kowane 10 ms subtask na tsari A matsayin wani aiki dabam. Don haka, lokacin farawa tare da STJF algorithm, zaɓi tsakanin aikin 50 ms da aikin 10 ms a bayyane yake. Bayan haka, lokacin da aikin ƙaramin aiki A ya ƙare, za a ƙaddamar da tsarin B da I/O. Bayan I / O ya kammala, zai zama al'ada don sake fara tsarin 10ms A maimakon tsarin B. Ta wannan hanyar, yana yiwuwa a aiwatar da overlap, inda CPU ke amfani da wani tsari yayin da na farko yana jiran I/O. Kuma a sakamakon haka, tsarin yana da kyau a yi amfani da shi - a lokacin da tsarin hulɗa yana jiran I / O, ana iya aiwatar da wasu matakai akan na'ura.
Oracle babu kuma
Yanzu bari muyi kokarin kawar da tunanin cewa an san lokacin gudanar da aikin. Wannan gabaɗaya shine mafi muni kuma mafi girman zato mara gaskiya akan jerin duka. A zahiri, a cikin matsakaicin OS na yau da kullun, OS da kansa yakan san kadan game da lokacin aiwatar da ayyuka, to ta yaya za ku iya gina na'ura mai tsarawa ba tare da sanin tsawon lokacin da aikin zai ɗauka ba? Wataƙila za mu iya amfani da wasu ƙa'idodin RR don magance wannan matsalar?
Sakamakon
Mun kalli ainihin ra'ayoyin tsara tsarin aiki kuma mun kalli iyalai 2 na masu tsara jadawalin. Na farko yana farawa mafi guntu aiki da farko kuma ta haka yana ƙara lokacin juyawa, yayin da na biyu ya tsage tsakanin dukkan ayyuka daidai, yana ƙara lokacin amsawa. Dukansu algorithms ba su da kyau inda algorithms na sauran iyali ke da kyau. Mun kuma duba yadda daidaitaccen amfani da CPU da I/O zai iya inganta aiki, amma bai warware matsalar ba ta OS clairvoyance. Kuma a darasi na gaba za mu dubi mai tsara shirin da zai duba abubuwan da suka faru a baya kuma ya yi ƙoƙarin yin hasashen abin da zai faru nan gaba. Kuma ana kiran sa jerin gwano na martani masu yawa.
source: www.habr.com