Platformăde e-learning și curriculăe-content pentru...

Platformă de e-learning și curriculă e-content pentru învățământul superior tehnic

� Sisteme de operare

13. Planificarea proceselor

2


SO – Sisteme de operare. Planificarea proceselor

Suport curs

OSC

� Capitolul 5 – CPU Scheduling

MOS

� Capitolul 2 – Processes and Threads

�Secțiunea 5 – Scheduling

3



Cuprins

� Spațiul de adresă al unui proces

� Tipuri/criterii/algoritmi de planificare

� Planificare pentru sisteme batch

� Planificare pentru sisteme interactive

� Planificare pentru sisteme real-time

� Planificarea execuției în Windows

� Planificarea execuției în Linux

4



Spațiul de adresă al unui proces

� Zona de date

�.data - variabile globale inițializate cu valori nenule

�.bss - variabile globale neinițializate sau inițializate cu zero

�.rodata - read-only(constante)

� Heap

�regiune dinamică

�controlată de programator

� Stiva

�regiune dinamică

�controlată de compilator

5



Stiva

int a(int b, int c){

int d=3;

int e=4;

int f=5;

int g=6;

return b+c+d+e+f+g;

}

int main(){

return a(1,2);

}

6



Stiva(2)

main:

pushl %ebp

movl %esp, %ebp

subl $8, %esp

movl $2, 4(%esp)

movl $1, (%esp)

call a

leave

ret

Vechiul Frame pointer

2

1

Adresa de return

7



Stiva(3)

a:

pushl %ebp

movl %esp, %ebp

subl $16, %esp

movl $3, -4(%ebp)

movl $4, -8(%ebp)

movl $5, -12(%ebp)

movl $6, -16(%ebp)

movl 12(%ebp), %eax

movl 8(%ebp), %edx

leal %edx(%eax), %eax

add -4(%ebp), %eax

add -8(%ebp), %eax

add -12(%ebp), %eax

add -16(%ebp), %eax

leave

ret

Vechiul frame pointer

2

1

Adresa de return

Vechiul frame pointer

6

5

4

3

8



Recapitulare – stările unui proces

• READY – gata de execuție• RUNNING – rulează• WAITING – așteaptă încheierea unei operații de I/E

9



Planificarea proceselor

� (CPU/Process) Scheduling

�alocarea proceselor pe procesor/procesoare

� Suportul pentru multitasking

� Scheduler

�subsistem al SO

�algoritmi de planificare

10



Comportarea proceselor

11



Comportarea proceselor

(a) procese CPU-bound(b) procese IO-bound

12



De ce planificarea execuției?

� Eficiență – optimizare acces la procesor

�un proces este executat până când așteaptă un eveniment blocant sau îi expiră cuanta

�SO (scheduler-ul) alege alt proces pentru execuție (planifică) după un procedeu (algoritm de planificare)

� Interactivitate și corectitudine (fairness)

�procesele pot fi întrerupte pentru rularea altor procese cu prioritate mai mare

�toate procesele au șanse egale de obținere a a procesorului

•în cazul planificării cu priorități, unele procese sunt „mai egale”

13



Tipuri de planificare a execuției

� Cooperativă

�se face planificare doar atunci când procesul se blochează, se termină sau cedează de bună voie procesorul

� Preemptivă

�procesele rulează un interval maxim de timp (cuantă)

�procesul este suspendat și se planifică altul

�este necesară o întrerupere de ceas

14



Când se apelează planificatorul?

� Crearea unui proces

� Terminarea unui proces

� Blocarea unui proces

�operații de I/E

�operații de sincronizare cu alte procese

� Terminarea unei operații de I/E

� Expirarea cuantei de timp alocate unui proces

� Existența unui proces cu prioritate mai mare

15



În ce constă planificarea execuției?

� Selecția unui proces/thread pentru rulare

�algoritm de selecție

�se parcurge coada READY [1]

�coada poate fi arbore, heap, listă, cozi multiple

� Schimbarea de context [2]

�se salvează contextul procesului curent

�se încarcă procesul selectat

16



Criterii de planificare (2)

� Timpul de așteptare

�cât timp se așteaptă în coada READY

� Timpul de răspuns

�timpul scurs de la crearea unui proces până la începerea execuției, sau

�cât durează o tranziție WAITING->RUNNING

� Echitate/corectitudine (fairness)

�procesele cu aceeași prioritate trebuie tratate similar

17



Criterii de planificare

� Criterii de selecție a procesului [3]

� Utilizarea procesorului

�gradul de “ocupare” a procesorului

� Productivitate (throughput)

�câte procese sunt încheiate în unitatea de timp

� Turnaround time

�timpul scurs de la crearea unui proces până la terminarea lui

18



Criterii de planificare (3)

� Algoritmii de planificare urmăresc

�maximizarea utilizării procesorului

�maximizarea productivității

�minimizarea turnaround time

�minimizarea timpului de așteptare

�minimizarea timpului de răspuns (interactivitate)

19



Notații

� TT – turnaround time

� TTM – turnaround time mediu

� J1, J2, ..., J# - jobul 1, 2, ..., # (batch)

� P1, P2, ..., P# - procesul 1, 2, ..., #

20



Planificare pentru sisteme batch

� Criterii importante

�throughput

�turnaround time

�utilizarea procesorului

� Algoritmi de planificare

�First-Come, First-Served

�Shortest Job First

�Shortest remaining time next

�Planificarea pe trei niveluri

21



First-Come, First-Served

� Planificare în ordinea intrării în sistem

� Un proces care cere procesorul este trecut într-o coadă de așteptare

� Procesele care se blochează sunt trecute la sfârșitul cozii

� + ușor de înțeles și implementat

� - procesele CPU-bound încetinesc procesele I/O-bound (efectul de convoi)

� - timp mediu de așteptare destul de mare

22



Exemplu FCFS

� J1, J2, J3

� Joburile intră simultan în sistem

� Timpii de execuție: 24, 3, 3

� FCFS: ordinea J1, J2, J3

�TT(J1) = 24; TT(J2) = 27; TT(J3) = 30

�TTM = (24 + 27 + 30) / 3 = 27

� Alt algoritm: ordinea J2, J3, J1

�TT(J1) = 30; TT(J2) = 3; TT(J3) = 6

�TTM = (30 + 3 + 6) / 3 = 13

23



Shortest Job First

� Problemă?

�trebuie cunoscută durata de execuție a unui job

� Planificarea în ordinea duratei de execuție

24



Exemplificare SJF

� J1, J2, J3, J4

� Job-urile intră simultan în sistem

� Timpii de execuție: 12, 20, 8, 4

� FCFS: J1, J2, J3, J4

�TT(J1) = 12; TT(J2) = 32; TT(J3) = 40; TT(J4) = 44

�TTM = (12 + 32 + 40 + 44) / 4 = 32

� SJF: J4, J3, J1, J2

�TT(J4) = 4; TT(J3) = 12; TT(J1) = 24; TT(J2) = 44

�TTM = (4 + 12 + 24 + 44) / 4 = 21

25



Shortest remaining time first

� Trebuie cunoscut timpul de execuție a jobului

� Versiune preemptivă a algoritmului SJF

�când un nou job este submis pentru execuție

�... și timpul de execuție al acestuia este mai mic decât timpul rămas din execuția jobului curent

�=> jobul curent este suspendat și noul job este executat

26



Exemplificare SRTF

� J1, J2, J3, J4

� Timpii de intrăre în sistem: 0, 1, 2, 3

� Timpii de execuție: 8, 4, 9, 5

� SRTF: J1(0:1), J2(1:5), J4(5:10), J1(10:17), J3(17:26)

�TT(J1) = 17; TT(J2) = 4; TT(J3) = 24; TT(J4) = 7

�TTM = (17 + 4 + 24 + 7) / 4 = 13

� SJF: J1(0:8), J2(8:12),J4(12:17),J3(17:26)

�TT(J1) = 8; TT(J2) = 11; TT(J3) = 24; TT(J4) = 14

�TTM = (8 + 11 + 24 + 14) / 4 = 14.25

27



Planificarea pentru sisteme interactive


�timpul de răspuns

�satisfacția utilizatorului

� Algoritmi de planificare

�Round-Robin

�Clase de priorități

�Shortest process next

28



Round-Robin

� FCFS preemptiv

� Cuantă de timp de rulare a programului

� La expirarea cuantei de timp procesul este preemptat

�se apelează planificatorul

�se alege alt proces (a cărui cuantă nu a expirat)

29



Round-Robin (2)

� Cum trebuie să fie cuanta de timp? (mare/mică)

� Cuantă de timp mare (secunde, sute de ms)

�productivitate ridicată

�timp de așteptare mare

�interactivitate scăzută

� Cuantă de timp mică (4-10 ms)

�interactivitatea ridicată

�timp comparabil cu o schimbare de context

�utilizare ineficientă a procesorului

30


SO – Sisteme de operare. Planificarea proceselor07.03.2011 - 13.03.2011

Planificare cu priorități

� Dezavantaj Round-Robin

�toate procesele sunt „egale”

� Abordare planificare cu priorități

�unele procese sunt „mai egale” decât altele

� Utilizatori importanți/mai puțin importanți

� Există procese mai importante/prioritare

31



Planificarea cu priorități (2)

� Prioritățile pot fi

�statice

•se cunoaște de la început care procese vor fi prioritare

�dinamice

•procesele I/O-bound sunt, în general, prioritare celor CPU-bound

32




33




[3]

34



Algoritmi cu multiple cozi

� Procesele sunt păstrate în mai multe cozi

� Fiecare coadă are asociată o prioritate

� Se rulează mai întâi procesele din coada cu prioritatea cea mai mare

� Un proces poate migra dintr-o coadă în altă coadă <--- algoritmi cu multiple cozi și feedback

35



Planificare pentru sisteme real-time


�îndeplinirea operațiilor în timp limitat

�predictibilitatea

� Sisteme real-time

�hard real-time

•rezervarea resurselor

•nu se folosește swapping sau memorie virtuală

�soft real-time

•procesele critice au prioritate maximă

•pot cauza întârzieri mari celorlalte procese

36



Shortest process next

� Adaptare a SJF pentru sisteme interactive

� Problemă

�nu se cunoaște timpul de execuție

� Soluție

�estimare pe baza comportamentului anterior

�se estimează o durată T0

�procesul durează T1

�estimarea pentru următoarea cuantă va fi a * T1 + (1-a) * T0

�a – estimarea se uită sau nu repede

�tehnică de estimare de tip aging

37



Planificare pentru sisteme real-time (2)

� Planificare real-time în sistemele time-sharing

�trebuie să existe un planificator bazat pe priorități

�procesele real-time trebuie să ruleze cu prioritate maximă

�planificatorul nu trebuie să decrementeze prioritatea proceselor real-time când acestea rulează

�planificatorul nu trebuie să întrerupă procesele real-time

�schimbarea de context trebuie să dureze puțin

38



Latența unei schimbări de context

� Sumă de timpi

� Salvarea contextului curent

� Încărcarea noului context

� Așteptarea terminării unui apel de sistem

�se pot introduce puncte de preemptare în apelurile de sistem cu durată mare

�kernel preemptiv

� Probleme de priority inversion [4]

�priority inheritance

39



Latența unei schimbări de context (2)

40



Planificarea execuției pe Windows

� Algoritm de planificare preemptivă bazat pe priorități

� Subsistemul de planificare se cheamă dispatcher

� O schemă de priorități pe 32 de niveluri

�0 – prioritate sistem

�1-15 – clasă variabilă de priorități

�16-30 – clasă real-time

� Nucleu preemptiv

41



Apelarea dispatcher-ului

� Un thread se blochează și cedează controlul procesorului

� Este întrerupt de un thread cu prioritate mai mare

�un thread cu prioritate mai mare iese din starea BLOCKED

�unui thread i-a fost schimbată prioritatea

� Unui thread îi expiră cuanta de timp

42



Algoritmul de planificare

� Este selectat procesul cu prioritatea cea mai mare

�fiecare prioritate are asociată o coadă

�procese din fiecare coadă sunt procese în starea READY

� Procesele din aceeași coadă sunt planificate asemănător cu Round-Robin

43



Priority boosting

� Unui proces îi este crescută pentru scurt timp prioritatea

� Situații

�la încheierea unei operații de I/E

�după așteptarea la un obiect de sincronizare

�după ce un proces din foreground a așteptat o operație blocantă

�thread-urile GUI sunt trezite

�un thread nu a rulat în ultima perioadă

44



Priority boosting (2)

� Creșterea priorității este temporară

�procesul rulează o singură cuantă de timp

�se decrementează prioritatea și se rulează încă o coadă de timp

�se continuă până când se ajunge la prioritatea de bază

� Prioritatea de bază este crescută, dar nu mai mult de 15

� La așteptarea I/E prioritatea este crescută în funcție de dispozitiv

45



Planificarea execuției în Linux

� Planificator preemptiv, time-sharing cu suport pentru procese real-time

� Kernel preemptiv de la versiunea 2.6

� Planificatorul gestionează 4 clase de procese [5]

�real-time FCFS

�real-time RR

�interactive

�Batch

46



Planificarea proceselor interactive

� 2.6 – 2.6.23 – O(1) scheduler

� Liste de procese pentru fiecare prioritate

� Două cozi de astfel de liste

�coada activă: procesele care nu și-au consumat cuanta

�coada expirată: procesele care și-au consumat cuanta

� Procesele sunt pedepsite (micșorarea priorității)

�dacă se folosește mai mult timp de procesor decât este disponibil

�se scade prioritatea dinamică proporțional cu cea statică

�se ține cont de istoria procesului

� Operațiile de extragere/inserare în cozi se efectuează în O(1)

47



CFS

� Completely Fair Scheduler [6]

� 2.6.23 – prezent

� Time-ordered red-black tree

� Virtual runtime

�fiecare proces are un timp „virtual” de execuție

�cel mai din stânga proces are timpul virtual cel mai mic – va fi următorul planificat

�planificare: t_virtual_curent – t_virtual_stanga > threshold

� Operații în O(log n)

48



Planificarea proceselor real-time

� Conform cu POSIX.1b

� FCFS

�procesele au doar prioritate statică, mai mare decât prioritatea proceselor time-sharing

�este ales procesul cu prioritatea cea mai mare

�un proces din această clasă va fi înlocuit doar dacă efectuează o operație blocantă

� RR

�la fel ca FCFS, dar un proces va fi preemptat dacă își consumă cuanta de timp

49



Planificarea proceselor real-time (2)

� Procesele sunt planificate într-o manieră RR

� Cuanta de timp este mai mare decât pentru procesele interactive

� Procesele cu prioritate statică minimă sunt considerate procese batch

Platformăde e-learning și curriculăe-content pentru...

Documents

Transcript of Platformăde e-learning și curriculăe-content pentru...