Plánování úloh a procesů v dávkových systémech

• Non-preemtivní plánování: proces si podrží kontrolu nad CPU dokud se jí nevzdá
• Preemtivní - proces lze přerušit během CPU burstu a naplánovat jiný

Bere se ohled na:

• průchodnost (počet úloh dokončených za časovou jednotku)
• průměrnou dobu obrátky (průměrná doba od zadání úlohy do systému do dokončení úlohy)
• využití CPU

Obsah 1 First-Come First-Served (FCFS) 2 Shortest Job First (SJF) 3 Shortest Remaining Time (SRT) 4 Multilevel Feedback

First-Come First-Served (FCFS)

• Někdy používán název FIFO
• Zpracování podle času příchodu úlohy, „kdo dřív přijde, ten dřív mele“
• Nepreemptivní FCFS je nejjednodušší plánovací algoritmus (úloha běží dokud neskončí)
• Je spravedlivý
• Během I/O operací se CPU nevyužívá, ale přesto je blokováno stávajícím procesem

Shortest Job First (SJF)

• Předpoklad, že je předem známá doba vykonávání úlohy
• Nepreemptivní, jedna fronta příchozích úloh, plánovač vybere vždy úlohu s nejkratší dobou běhu
• Nevýhodou je, že na dlouho trvající úlohy se nemusí vůbec dostat

Shortest Remaining Time (SRT)

• Preemptivní varianta SJF
• Plánovač vždy vybere úlohu, jejíž zbývající doba běhu je nejkratší
• Např. právě prováděné úloze to bude trvat 10 min., do systému přijde úloha trvající 1 minutu - systém prováděnou úlohu pozastaví a nechá běžet novou úlohu
• Problém: možnost vyhladovění úloh

Multilevel Feedback

• Je preemptivní
• N rozdílných prioritních úrovní, každá úroveň má svou frontu úloh
• Úloha vstoupí do systému s nejvyšší prioritou
• Na každé prioritní úrovni je stanoveno maximu času CPU, které může úloha na této úrovni obdržet
  • Pokud úloha překročí limit, její priorita se sníží
  • Na nejnižší úrovni může proces běžet neustále nebo může být překročení považováno za chybu
• Procesor obsluhuje nejvyšší neprázdnou frontu
• Výhoda: rozlišuje mezi I/O a CPU úlohami (upřednostňuje I/O)