Protsessi plaanimise algorütmid

OS - Scheduling algorithms

We'll discuss four major scheduling algorithms here which are following

• First Come First Serve FCFS Scheduling
• Shortest-Job-First SJF Scheduling
• Priority Scheduling
• Round RobinRR Scheduling
• Multilevel Queue Scheduling

First Come First Serve FCFS

• Jobs are executed on first come, first serve basis.
• Easy to understand and implement.
• Poor in performance as average wait time is high.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Average Wait Time: 0+4+6+13 / 4 = 5.55

Shortest Job First SJF

• Best approach to minimize waiting time.
• Impossible to implement
• Processer should know in advance how much time process will take.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	3 - 0 = 3
P1	0 - 0 = 0
P2	16 - 2 = 14
P3	8 - 3 = 5

Average Wait Time: 3+0+14+5 / 4 = 5.50

Priority Based Scheduling

• Each process is assigned a priority. Process with highest priority is to be executed first and so on.
• Processes with same priority are executed on first come first serve basis.
• Priority can be decided based on memory requirements, time requirements or any other resource requirement.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	9 - 0 = 9
P1	6 - 1 = 5
P2	14 - 2 = 12
P3	0 - 0 = 0

Average Wait Time: 9+5+12+0 / 4 = 6.5

Round Robin Scheduling

• Each process is provided a fix time to execute called quantum.
• Once a process is executed for given time period. Process is preempted and other process executes for given time period.
• Context switching is used to save states of preempted processes.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	0−0 + 12−3 = 9
P1	3−1 = 2
P2	6−2 + 14−9 + 20−17 = 12
P3	9−3 + 17−12 = 11

Average Wait Time: 9+2+12+11 / 4 = 8.5

Multi Queue Scheduling

• Multiple queues are maintained for processes.
• Each queue can have its own scheduling algorithms.
• Priorities are assigned to each queue.

Protsessi plaanimine

Definitsioon - Protsessi planeermine on protsessi haldaja tegevus, mis haldab jooksvate protsesside eemaldamist CPUst ja mõne teise protsessi valimine kindla strateegia põhjal.
Plaanimise järjekorrad - Viitab järjekorrale protsessis või seadmes. Kui protsess siseneb süsteemi, siis protsess pannakse töö järjekorda. See järjekord koosneb kõikidest protsessidest süsteemis. OS omab ka teisi järjekordi nagu seadmejärjekord. Seadmejärjekord on järjekord, mitu protsessi ootavad kindlat I/O seadet. Igal seadmel on oma seamdejärjekord.

This figure shows the queuing diagram of process scheduling.

• Queue is represented by rectangular box.
• The circles represent the resources that serve the queues.
• The arrows indicate the process flow in the system.
  
  
  
  Queues are of two types
  
• Ready queue
• Device queue
    newly arrived process is put in the ready queue. Processes waits in ready queue for allocating the CPU. Once the CPU is assigned to a process, then that process will execute. While executing the process, any one of the following events can occur.
  
  • The process could issue an I/O request and then it would be placed in an I/O queue.
  • The process could create new sub process and will wait for its termination.
  • The process could be removed forcibly from the CPU, as a result of interrupt and put back in the ready queue.

  Two State Process Model

  -Running
  When new process is created by Operating System that process enters into the system as in the running state.
  -Not Running
  Processes that are not running are kept in queue, waiting for their turn to execute. Each entry in the queue is a pointer to a particular process. Queue is implemented by using linked list. Use of dispatcher is as follows. When a process is interrupted, that process is transferred in the waiting queue. If the process has completed or aborted, the process is discarded. In either case, the dispatcher then selects a process from the queue to execute
  

  Schedulers

  Schedulers are special system softwares which handles process scheduling in various ways.Their main task is to select the jobs to be submitted into the system and to decide which process to run. Schedulers are of three types
  
• Long Term Scheduler
• Short Term Scheduler
• Medium Term Scheduler

• Long Term Scheduler

  It is also called job scheduler. Long term scheduler determines which programs are admitted to the system for processing. Job scheduler selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduling. The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.
  On some systems, the long term scheduler may not be available or minimal. Time-sharing operating systems have no long term scheduler. When process changes the state from new to ready, then there is use of long term scheduler.
  

  Short Term Scheduler

  It is also called CPU scheduler. Main objective is increasing system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects process among the processes that are ready to execute and allocates CPU to one of them.
  Short term scheduler also known as dispatcher, execute most frequently and makes the fine grained decision of which process to execute next. Short term scheduler is faster than long term scheduler.
  

  Medium Term Scheduler

  Medium term scheduling is part of the swapping. It removes the processes from the memory. It reduces the degree of multiprogramming. The medium term scheduler is in-charge of handling the swapped out-processes.
  
  

  Schedulerite võrdlus

  

Konteksti vahetus

A context switch is the mechanism to store and restore the state or context of a CPU in Process Control block so that a process execution can be resumed from the same point at a later time. Using this technique a context switcher enables multiple processes to share a single CPU. Context switching is an essential part of a multitasking operating system features.
When the scheduler switches the CPU from executing one process to execute another, the context switcher saves the content of all processor registers for the process being removed from the CPU, in its process descriptor. The context of a process is represented in the process control block of a process.
Context switch time is pure overhead. Context switching can significantly affect performance as modern computers have a lot of general and status registers to be saved. Content switching times are highly dependent on hardware support. Context switch requires ( n + m ) bxK time units to save the state of the processor with n general registers, assuming b are the store operations are required to save n and m registers of two process control blocks and each store instruction requires K time units.

Some hardware systems employ two or more sets of processor registers to reduce the amount of context switching time. When the process is switched, the following information is stored.

• Program Counter
• Scheduling Information
• Base and limit register value
• Currently used register
• Changed State
• I/O State
• Accounting

Protsess

OS'i ülesanne on protsesside haldus ehk OS peab jagama protsessidele ressursse, võimaldama protsessidel vahetada informatsiooni teiste protsessidega ja võimaldama sünkroniseerimist protsesside seas. Protsess on kasutajarakenduse töötav koopia ja protsesside haldamiseks ning neile ressursside jagamiseks peab OS haldama iga protsessi jaoks andmestruktuuri, mis kirjeldab protsessi identiteeti, staatust, seotud ressursse, jne, et rakendada kontrolli protsessi üle. Protsessi iseloomustavad järgmised omadused:

• Identifikaator: unikaalne number, mis eristab protsessi teistest protsessidest
• Staatus: näitab protsessi jooksvat seisundit (näiteks käivitatud)
• Prioriteet: prioriteet võrreldes teiste protsessidega
• Programmiloendur: järgmise käsu aadress, mis tuleb käivitada
• Mälulokaator: mäluaadressid programmi koodi ja andmete asukohta
• Kontekstandmed: protsessori registrite seis protsessi käivitamisel
• S/V staatuse info: info täitmisel S/V päringutest, protsessiga seotud S/V seadmed, protsessi poolt avatud failide loetelu, jne.
• Aruandlusinfo: kasutatud protsessori aeg, ajapiirangud, jne.

Seda infot talletatakse andmestruktuuris, mida nimetatakse protsessi juhtplokiks (Process Control Block), mida haldab OS. Protsessi juhtplokk sisaldab piisavalt infot, et protsessi saab vajadusel katkestada ja hiljem jätkata, nagu oleks vahepeal juhtunud katkestus. Kui protsess katkestatakse siis jooksvad väärtused nagu programmiloendur ja protsessori registrite seis salvestatakse vastavates protsessi juhtploki väljades ja protsessi seisund muudetakse täitmisel (Execution) staatusest kas blokeerituks (Blocked) või täitmiseks valmis (Ready) staatusesse.

Joonis - Protsesside staatuse ümberlülitumise võimalused (Allikas: Learning Materials for Information Technology Professionals (EUCIP-Mat))

• Täitmiseks valmis staatus tähendab, et protsess on ajastatud tööjärjekorda ja ootab protsessoriressursi vabanemist, et oma tööga edasi minna
• Täitmisel protsess kasutab parajasti talle määratud protsessoriressurssi.
• Blokeeritud seisu seatakse süsteemikutse käivitanud protsess, mis ootab mingi S/V operatsiooni täitmist oma töö jätkamiseks. 

Selgitav video protsessi töötamise kohta inglise keeles. 1.osa

Kui kernel suutis mingi asja tööle panna, siis tema jaoks on midagi eraldatud

roheline: virtuaal mälu

Operatsiooni süsteemid:

Koode operatsiooni süsteemi kohta:

 Kernel:

Operatsioonisüsteem (Operating System edaspidi OS) vahendab arvutikasutaja suhtlust arvuti riistvaraga. OS'i eesmärk on muuta arvuti kasutamine mugavaks, võimaldades käivitada kasutajarakendusi ja aidates lahendada veaolukordi. Rakendustarkvara - erinevad rakendusprogrammid, mis pakuvad kasutajale vajalikku funktsionaalsust tööülesannetetäitmiseks arvutil.

Joonis 2-1. Arvuti riist- ja tarkvarakomponendid(Allikas: Learning Materials for Information Technology Professionals (EUCIP-Mat))

Joonis 2‑2. Rakendustele riistvararessursside jagamine(Allikas: Learning Materials for Information Technology Professionals (EUCIP-Mat))
OS vahendab rakendusprogrammide pöördumist riistvarakomponentide poole läbi spetsiaalsete liideste. See võimaldab rakendustele juurdepääsu süsteemi riistvararessurssidele jättes OS'i hooleks riistvara poole pöördumise spetsiifika,riistvararessursside halduse ning konfliktide välistamise. Tüüpilise personaalarvuti OS'i funktsioonid on:

• Kasutajakeskkond seadmetega töötamisel
• Automaatne sisend-väljund (edaspidi S/V)seadmetekonfimine
• Rakenduste liides seadmete poole pöördumiseks
• Keskkond rakenduste loomiseks
• Ressursi (CPU, RAM, failisüsteem, jne) jagaja
• Arvutivõrgu toetus (protokollid, veebilehitseja)
• Turvavahendid (autentimine, tulemüür, failisüsteemi ACL, krüpteerimine, installi- ja kasutuspiirangute konfimine tavakasutajatele).

KaasaegseteOS'ide arendusel tehakse tööd, et toetada uuemat riistvara, uusi rakendusi ja kaitsta OS'i turvaohtude eest. Riistvarakomponentide osas on arengut suunanud multiprotsessorsüsteemide kiire areng, kõrged taktsagedused, massmäluseadmete suurenenud andmemahud. Rakenduste osas on OS'i arengu mõjutajateks multimeediarakendused, internet ja võrgundus, klient/server lahendused ja virtualiseerimine.Nende väljakutsete mõjul tehakse OS'ide arendamiseks tööd järgmistes kategooriates:

• Mikrokernel-arhitektuur(Microkernel architecture) - kompaktne kernel, mida toetavad eraldi lisakomponendid
• Hargtöötlus (Multithreading) - võimaldab protsessi käivitamise jagada lõimedeks, mida saab käivitada paralleelselt
• Sümmeetriline multitöötlussüsteem (Symmetric multiprocessing) - protsessorid jagavad sama põhimälu ja S/V moodulit ning võivad käivitada võrdselt kõiki protsesse.
• Objekt-orienteeritud disain - võimaldab lisada laiendusi kompaktselekernelile, kohandada OS'i ja lihtsustab jagatud tööriistade arendamist.
• Hüperviisor (Hypervisor) - virtualiseerimise haldur, mis paigaldub õhukese tarkvara kihina riistvara ja kerneli vahele ning võimaldab ära kasutada riistvaralise virtualiseerimise toetuse ja hallata nii mitmeid erinevaid operatsioonisüsteeme samas füüsilises masinas.

Operatsioonisüsteemipõhikomponendid on kokku võetud ainulaadsesse programmi, mida nimetatakse kerneliks ehk tuumaks. Kernel võib olla ehitatud kas suure monoliitse arhitektuuriga (monolithic architecture), mille puhul kernel sisaldab kõike vajaliku OS'i funktsioneerimiseks ja sealhulgas plaanuri, failisüsteemi, võrgunduse, seadmedraiverid, mäluhalduse jne. Mikrokernel-arhitektuuri puhul on kernelis ainult kõige põhilisemad funktsioonid nagu protsesside plaanur, protsessidevaheline kommunikatsioon, katkestuste ja erandite töötlus ja mitmeprotsessorsüsteemi sünkroniseerimine. Ka sisaldab mikrokernel alamprotseduure ja baasobjekte, mida kernelit ümbritsevad ja kernelirežiimis töötavad komponendid saavad kasutada.Microsoft Windows OS'id on modulaarsed ja kasutavadmikrokernel-arhitektuurile sarnast lähenemist. Linux OS kasutab monoliitse kerneliga arhitektuuri. Windowsi kerneli ümber on koondatud muud kernelirežiimis töötavad komponendid, mis pakuvad kõiki OS'i teenuseid nagu mälu haldus, protsessi ja lõimede haldus, turvalisus, S/V, võrgundus, protsesside vaheline kommunikatsioon ja graafilise kasutajaliidese funktsioonid. Kernelirežiimis töötavad ka seadmete draiverid, mis muundavad S/Vfunktsioonide käske spetsiifilisteks riistvaraseadmete S/V päringuteks. Kernelirežiimis töötavad komponendid peavad olema väga hästi testitud ja draiverid OS'iga ühilduvad, sest häired nende töös muudavad ebastabiilseks kogu OS'i.
Selleks, et kaitsta OS'i kasutajarakenduste eest on OS'is kasutusel erinevad protsessori režiimid kernelile ehk kernelirežiim (Kernel Mode või Supervisor Mode) ja kasutajarakendustele ehk kasutajarežiim (User Mode). Kasutajarakendused töötavad kasutajarežiimis ja OS'irakendused (süsteemi teenused ja seadmete draiverid) töötavad kernelirežiimis. Selles režiimis rakendused jagavad ühtset virtuaalset aadressiruumi. Kernelirežiim käivitatakse protsessori privilegeeritud käivitusrežiimis, mis tagab juurdepääsu kõigile protsessori käskudele ja kogu süsteemimälule. Erinevate töörežiimide rakendamine võimaldab välistada, et vigane kasutajarakendus ohustaks süsteemi kui terviku stabiilsust.

Protsessi juhtplokk

Pointer - Muutuja, mis viitab ühele mälu aadressile.

Process termination

There are many reasons for process termination:

• Batch job issues halt instruction
• User logs off
• Process executes a service request to terminate
• Error and fault conditions
• Normal completion
• Time limit exceeded
• Memory unavailable
• Bounds violation; for example: attempted access of (non-existent) 11th element of a 10-element array
• Protection error; for example: attempted write to read-only file
• Arithmetic error; for example: attempted division by zero
• Time overrun; for example: process waited longer than a specified maximum for an event
• I/O failure - sisend seadme rike
• Invalid instruction; for example: when a process tries to execute data (text)
• Privileged instruction
• Data misuse
• Operating system intervention; for example: to resolve a deadlock - ummik nt, täisummik (nagu walking deadis ummikud, aint läbipääsmatud)
• Parent terminates so child processes terminate (cascading termination) - Vanem protsessi hävimisel hävinevad ka laps protsessid
• Parent request - vanema nõue
• Fatal error - fataalne jama, viga mis põhjustab programmi sulgemise

 Kui tahate eesti keelset, siis lugemine omal vastutusel: protsessi lõpetamine

On palju põhjusi protsessi lõpetamine:

     Partii töö küsimused peatada juhendamine
     Kasutaja logib välja
     Protsessi käivitab teenuse taotluse lõpetada
     Viga ja veaolukorrad
     Tavaline lõpetamist
     Tähtaeg ületatud
     Mälu puuduvad
     Piire rikkudes; Näiteks: püüdsid juurdepääsu (olematu) 11. osa 10-element massiivi
     Kaitse viga; Näiteks: üritanud kirjutada ainult lugemiseks faili
     Aritmeetiline viga; Näiteks: püüdsid jagamist nulliga
     Aeg ületatud; näiteks: protsess oodanud kauem kui määratud maksimaalne sündmuse jaoks
     I / O rike
     Vale juhendamine; Näiteks: kui protsess püüab täita andmeid (tekst)
     Eesõigus juhendamine
     andmed väärkasutuse
     Operatsioonisüsteem sekkumist; Näiteks: lahendada ummikusse
     Parent lõpevad nii lapse protsessid lõpetada (CSS lõpetamine)
     Parent taotluse
     Fatal error   #googletõlgi

Protsesside loomine

Operatsioonisüsteemid vajan viise, kuidas luua protsesse. Väga lihtne süsteem on konstrueeritud kasutamiseks ainult ühe taotluse kohta (nt kontrolleri mikrolaine ahi), siis võib olla võimalik, et kõik protsessid, mis kunagi on vaja olla kohal, kui süsteem kerkib. In üldotstarbeline süsteemid aga mingil moel on vaja luua ja lõpetatakse protsessid nagu vaja töötamise ajal.
Seal on neli peamist sündmused, mis põhjustavad protsessi tuleb luua:

     Süsteemi ettekanne.
     Täitmine protsessi loomise süsteemi kõne töötama protsessi.
    Kasutaja taotlusel, et luua uus protsess.
     Algatamine partii tööd.

Kui operatsioonisüsteemi alglaadimisel, tavaliselt mitmeid protsesse on loodud. Mõned neist on esiplaanil protsesse, mis suhtleb (inimese) kasutaja ja töö tegemiseks neile. Teised on taust protsessid, mis ei ole seotud konkreetse kasutaja, vaid selle asemel on mõned spetsiifilist funktsiooni. Näiteks üks taust protsess võib olla projekteeritud sissetulevatele e-kirju, magab suurema osa päevast, kuid äkki springing elu, kui sissetuleva e-mail saabub. Teine taust protsess võib olla projekteeritud Saabunud taotluse veebilehti majutatud masin, ärkamine, kui taotlus saabub teenindada, et taotluse.

Protsesside loomine UNIX ja Linux on teinud läbi kahvli () või kloon () süsteem nõuab. On mitmeid etappe protsessi loomist.Esimene samm on kinnitamise kas vanem protsess on piisavalt luba luua protsess. Pärast edukat kinnitamine, vanema protsessi kopeeritakse peaaegu täielikult, muutustega ainult unikaalne protsess id, vanem protsessi ning kasutaja ruumi. Iga uus protsess saab oma kasutaja ruumi.
#googletõlge #ärapahaneole