Ebben az oktatóanyagban a CPU folyamatütemezési algoritmusainak egy fontos fogalmát fogjuk megtanulni. A fontos fogalom neve: First Come First Serve. Ez az az alapvető algoritmus, amelyet minden diáknak meg kell tanulnia, hogy megértse a CPU folyamatütemezési algoritmusok alapjait.
Az „Előbb jön elsőként” szolgáltatás megnyitja az utat más algoritmusok megértéséhez. Ennek az algoritmusnak számos hátránya lehet. De ezek a hátrányok nagyon új és hatékony algoritmusokat hoztak létre. Ezért a mi felelősségünk, hogy megismerjük a CPU folyamatütemezési algoritmusait.
Fontos rövidítések
- CPU - - - > Központi feldolgozó egység
- FCFS - - - > Első érkezési tálalás
- AT - - - > Érkezési idő
- BT - - - > Burst Time
- WT - - - > Várakozási idő
- TAT - - - > Fordulási idő
- CT - - - > Befejezési idő
- FIFO - - - > First In First Out
Aki kapja, marja
A CPU ütemezési algoritmus, röviden FCFS, a CPU folyamatütemezési algoritmus első algoritmusa. A First Come First Serve algoritmusban azt tesszük, hogy lehetővé tesszük a folyamat lineáris végrehajtását.
Ez azt jelenti, hogy amelyik folyamat lép be először a készenléti sorba, az először kerül végrehajtásra. Ez azt mutatja, hogy a First Come First Serve Algorithmus az First In First Out (FIFO) elvet követi.
int karakterlánchoz java-ban
Az „Elsőként jön először kiszolgálás” algoritmus végrehajtható megelőző és nem megelőző módon. Mielőtt belemennénk a példákba, értsük meg, mi az a megelőző és nem megelőző megközelítés a CPU folyamatütemezésében.
Megelőző megközelítés
A megelőző folyamatütemezés ezen példájában az operációs rendszer előre meghatározott időtartamra osztja ki az erőforrásokat egy folyamat számára. A folyamat az erőforrások lefoglalása során futó állapotból kész állapotba vagy várakozási állapotból kész állapotba vált át. Ez a váltás azért történik, mert a CPU más folyamatok elsőbbségét rendelheti hozzá, és a jelenleg aktív folyamatot helyettesítheti a magasabb prioritású folyamattal.
Nem megelőző megközelítés
A nem megelőző folyamatütemezés ebben az esetben az erőforrás nem vonható ki a folyamatból, amíg a folyamat le nem fejeződött. Amikor egy futó folyamat befejeződik, és átáll a várakozási állapotba, az erőforrások átváltásra kerülnek.
Konvoj effektus az érkezési sorrendben (FCFS)
A Convoy Effect egy olyan jelenség, amely a First Come First Serve (FCFS) elnevezésű ütemezési algoritmusban fordul elő. Az „Előbb jön először kiszolgálás” ütemezési algoritmus nem megelőző módon történik.
A nem megelőző mód azt jelenti, hogy ha egy folyamat vagy feladat végrehajtása elindul, akkor az operációs rendszernek be kell fejeznie a folyamatot vagy feladatot. Amíg a folyamat vagy job nulla nem lesz, az új vagy a következő folyamat vagy job nem kezdi el a végrehajtását. A Non Preemptive Scheduling definíciója az operációs rendszer szempontjából azt jelenti, hogy a központi feldolgozó egység (CPU) teljesen dedikált lesz a folyamat vagy job végéig, amelyet először kezdenek el, és az új folyamat vagy job csak a régebbi folyamat befejezése után kerül végrehajtásra. munka.
Előfordulhat néhány eset, ami miatt a központi feldolgozó egység (CPU) túl sok időt fordít rá. Ennek az az oka, hogy az „Előbb jön az első kiszolgálás” ütemezési algoritmus nem megelőző megközelítésben a folyamatok vagy a feladatok soros sorrendben kerülnek kiválasztásra. Emiatt a rövidebb munkák vagy folyamatok a nagyobb folyamatok vagy jobok mögött túl sok időt vesz igénybe a végrehajtása. Emiatt a Várakozási Idő, az átfutási idő, a Befejezési idő nagyon magas.
Tehát itt, mivel az első folyamat nagy, vagy a befejezési idő túl hosszú, akkor ez a Konvoj effektus az „Előbb jön először kiszolgálás” algoritmusban bekövetkezik.
Tegyük fel, hogy a Hosszabb Munka befejezése végtelen ideig tart. Ezután a fennmaradó folyamatoknak ugyanazt a végtelen időt kell várniuk. A Hosszabb Munka által létrehozott konvoj effektusnak köszönhetően a várakozási folyamatok éhezése nagyon gyorsan megnő. Ez az FCFS CPU folyamatütemezés legnagyobb hátránya.
Az FCFS CPU folyamatütemezés jellemzői
Az FCFS CPU folyamatütemezés jellemzői a következők:
- A megvalósítás egyszerű.
- Használat közben nem okoz ok-okozati összefüggést
- Nem preemptív és megelőző stratégiát alkalmaz.
- Az egyes eljárásokat a beérkezésük sorrendjében futtatja.
- Az érkezési idő az eljárások kiválasztási kritériuma.
Az FCFS CPU folyamatütemezés előnyei
Az FCFS CPU folyamatütemezés előnyei a következők:
médiaátvitel
- A folyamatok kiosztásához a First In First Out sort használja.
- Az FCFS CPU ütemezési folyamat egyszerű és könnyen megvalósítható.
- Az FCFS-helyzetben a megelőző ütemezésben nincs esély a folyamat kiéhezésére.
- Mivel nem veszik figyelembe a folyamat prioritását, ez egy méltányos algoritmus.
Az FCFS CPU folyamatütemezés hátrányai
Az FCFS CPU folyamatütemezés hátrányai a következők:
- Az FCFS CPU ütemezési algoritmusnak hosszú várakozási ideje van
- Az FCFS CPU ütemezése előnyben részesíti a CPU-t a bemeneti vagy kimeneti műveletekkel szemben
- Az FCFS-ben fennáll a Convoy Effect előfordulásának esélye
- Mivel az FCFS nagyon egyszerű, gyakran nem túl hatékony. A meghosszabbított várakozási idő ezzel együtt jár. Minden más rendelés tétlen marad, ha a CPU egy időigényes rendelés feldolgozásával van elfoglalva.
Problémák a CPU ütemezési algoritmussal
Példa
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Nem megelőző megközelítés
Most oldjuk meg ezt a problémát az „Előbb jön először kiszolgálás” nevű ütemezési algoritmus segítségével, nem megelőző megközelítésben.
A fenti 1. példa Gantt-diagramja a következő:
Fordulási idő = Befejezési idő – érkezési idő
Várakozási idő = átfutási idő – sorozatfelvételi idő
A fenti kérdés megoldása 1. példa
| Igen nem | Folyamatazonosító | Érkezési idő | Burst Time | Befejezési idő | Átfutási idő | Várakozási idő | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | tizenegy | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | tizenegy |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | ÉS | 2 | 3 | huszonegy | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | húsz | 18 |
Az átlagos befejezési idő:
Átlagos CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Átlagos CT = 97/6
Átlagos CT = 16,16667
Az átlagos várakozási idő:
Átlagos WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Átlagos WT = 66/6
Átlagos WT = 11
"kőműves képlete"
Az átlagos átfutási idő:
Átlagos TAT = ( 9 + 11 + 13 + 17 + 19 + 20 ) / 6
Átlagos TAT = 89/6
Átlagos TAT = 14,83334
Pete Davidson nemzetiségű
Így oldható meg az FCFS a Non Pre Emptive Approach-ban.
Most pedig értsük meg, hogyan lehet ezeket megoldani a megelőző megközelítésben
Megelőző megközelítés
Most oldjuk meg ezt a problémát a „First Come First Serve” nevű ütemezési algoritmus segítségével, megelőző megközelítésben.
A megelőző megközelítésben az elérhető legjobb eljárást keressük
A fenti 1. példa Gantt-diagramja a következő:
| Igen nem | Folyamatazonosító | Érkezési idő | Burst Time | Befejezési idő | Átfutási idő | Várakozási idő | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 23 | 23 | 14 |
| 2 | P 2 | B | 1 | 3 | 8 | 7 | 4 |
| 3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | D | 1 | 4 | tizenöt | 14 | 10 |
| 5 | P 5 | ÉS | 2 | 3 | tizenegy | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| következő → ← előz Az ébresztési jelek elvesztésének problémájának elkerülése érdekében Dijkstra olyan megközelítést javasolt, amely magában foglalja az összes ébresztő hívás tárolását. Dijkstra kijelenti, hogy a gyártó ahelyett, hogy közvetlenül a fogyasztónak adná az ébresztést, eltárolhatja az ébresztést egy változóban. Bármelyik fogyasztó elolvashatja, amikor csak szüksége van rá. A szemafor azok a változók, amelyek a termelőtől a fogyasztóhoz továbbított teljes ébresztő hívást tárolják. Ez egy olyan változó, amelyen kernel módban automatikusan megtörténik az olvasás, módosítás és frissítés. A szemafor nem valósítható meg felhasználói módban, mert versenyfeltételek mindig felmerülhetnek, amikor két vagy több folyamat egyszerre próbálja elérni a változót. Mindig szüksége van az operációs rendszer támogatására a megvalósításhoz. A helyzet igénye szerint a Semaphore két kategóriába sorolható.
Mindegyiket részletesen megbeszéljük. |