Systemy operacyjne materiaªy ¢wiczeniowe

Studia dzienne PJWSTK

‚WICZENIA XII

Szeregowanie procesów

Stan procesu

• nowy proces wªa±nie utworzony

• aktywny proces wªa±nie wykonywany na procesorze

• oczekuj¡cy proces oczekuje na zaj±cie pewnego zdarzenia

• gotowy proces oczekuje na przydzielenie mocy obliczeniowej procesora

• zako«czony proces wªa±nie zako«czyª dziaªanie

Mo»liwe przej±cia stanów procesu

• nowy 7−→ {gotowy}

• aktywny 7−→ {oczekuj¡cy, gotowy, zako«czony}

• oczekuj¡cy 7−→ {gotowy}

• gotowy 7−→ {aktywny}

• zako«czony 7−→ ∅

Miary efektywno±ci metod szeregowania procesów

• czas przetworzenia ª¡czny czas wszystkich stanów procesu pomi¦dzy stanem nowy a stanem zako«czony (wª¡czaj¡c oba)

• czas gotowo±ci ª¡czny czas wszystkich stanów gotowy procesu pomi¦dzy stanem nowy a stanem zako«czony (wª¡czaj¡c oba)

• czas reakcji ª¡czny czas wszystkich stanów procesu pomi¦dzy stanem nowy a pierwszym stanem aktywny (wyª¡czaj¡c ten ostatni)

Strategia FCFS szeregowania procesów

• skrót od First Come First Serve

• procesy zostaj¡ obsªu»one niewywªaszczeniowo w kolejno±ci zasygnalizowania zapotrzebowania na moc obliczeniow¡ procesora

• zalety

◦ prosta implementacja

◦ niskie narzuty systemowe zwi¡zane z obsªug¡ mechanizmu

• wady

◦ strategia cz¦sto niepoptymalna w sensie ±redniego czasu gotowo±ci 1

c

° Paweª Rembelski

Systemy operacyjne materiaªy ¢wiczeniowe

Studia dzienne PJWSTK

Strategia SJF szeregowania procesów

• skrót od Shortest Job First

• procesy zostaj¡ obsªu»one niewywªaszczeniowo w kolejno±ci aktualnie najkrótszych zada« oczekuj¡cych na moc obliczeniow¡ procesora

• zalety

◦ prosta implementacja (pomijaj¡c problem wyznaczenia oczekiwanego czasu rozwi¡zania zadania)

◦ niskie narzuty systemowe zwi¡zane z obsªug¡ mechanizmu

• wady

◦ strategia cz¦sto niepoptymalna w sensie ±redniego czasu przetwarzania

◦ problem wyznaczenia oczekiwanego czasu wykonania zadania

◦ mo»liwo±¢ zagªodzenia procesu

Strategia SRTF szeregowania procesów

• skrót od Shortest Remaining Time First

• procesy zostaj¡ obsªu»one wywªaszczeniowo w kolejno±ci aktualnie najkrótszych czasów niezb¦dnych do doko«czenia zada«, spo±ród oczekuj¡cych na moc obliczeniow¡ procesora

• zalety

◦ prosta implementacja (pomijaj¡c problem wyznaczenia oczekiwanego czasu rozwi¡zania zadania)

◦ niskie narzuty systemowe zwi¡zane z obsªug¡ mechanizmu

◦ rozwi¡zanie efektywne pod wzgl¦dem minimalizacji ±redniego czasu gotowo±ci

• wady

◦ problem wyznaczenia oczekiwanego czasu wykonania zadania

◦ mo»liwo±¢ zagªodzenia procesu

Strategia RR szeregowania procesów

• skrót od Round Robin

• czas procesora jest podzielony na kwanty dªugo±ci k jednostek czasowych

• procesy otrzymuj¡ wywªaszczeniowo kwanty czasu procesora w kolejno±ci zasygnalizowania zapotrzebowania na moc obliczeniow¡ procesora

• proces przydziaªu kwantów czasu procesora jest cykliczny

• zako«czenie procesu przed wykorzystaniem peªnego kwantu czasu procesora powoduje bezzwªoczne udost¦pnienie procesora dla kolejnego procesu

• zalety

◦ rozwi¡zanie efektywne pod wzgl¦dem minimalizacji ±redniego czasu reakcji

◦ brak mo»liwo±ci zagªodzenia procesu

• wady

◦ strategia cz¦sto niepoptymalna w sensie ±redniego czasu oczekiwania

◦ wysokie narzuty systemowe zwi¡zane z obsªug¡ mechanizmu 2

c

° Paweª Rembelski

Systemy operacyjne materiaªy ¢wiczeniowe

Studia dzienne PJWSTK

Zadanie

Dana jest nast¦puj¡ca lista pi¦ciu procesów wraz z ich czasami przybycia i czasami wykonania proces czas przybycia czas wykonania

P1

0

3

P2

1

5

P3

2

2

P4

7

4

P5

8

1

Dla strategii FCFS, SJF, SRTF oraz RR

• narysuj diagramy ilustruj¡ce wykonanie procesów P1, ..., P5,

• podaj ±rednie czasy przetworzenia, gotowo±ci i reakcji procesów P1, ..., P5.

Zarz¡dzanie pami¦ci¡ zyczn¡ z segmentowaniem

Strategia Best Fit zarz¡dzania pami¦ci¡

• minimalizowana jest strata pami¦ci wynikaj¡ca z przydzielenia danego obszaru

• je»eli istnieje klika obszarów minimalizuj¡cych strat¦ pami¦ci, to wybierany jest obszar pierwszy wzgl¦dem adresu bezwzgl¦dnego

Strategia Worst Fit zarz¡dzania pami¦ci¡

• maksymalizowana jest strata pami¦ci wynikaj¡ca z przydzielenia danego obszaru

• je»eli istnieje klika obszarów maksymalizuj¡cych strat¦ pami¦ci, to wybierany jest obszar pierwszy wzgl¦dem adresu bezwzgl¦dnego

Strategia First Fit zarz¡dzania pami¦ci¡

• poszukiwanie rozpoczyna si¦ od obszaru pocz¡tkowego pami¦ci

• wybierany jest pierwszy wzgl¦dem adresu bezwzgl¦dnego wystarczaj¡cy obszar pami¦ci Strategia Cycle First Fit zarz¡dzania pami¦ci¡

• poszukiwanie rozpoczyna si¦ od obszaru pami¦ci, na którym zako«czono poprzedni¡ operacj¦ przydzielenia pami¦ci

• wybierany jest pierwszy wzgl¦dem adresu bezwzgl¦dnego wystarczaj¡cy obszar pami¦ci Zadanie

Dana jest pami¦¢ skªadaj¡ca si¦ z 10-ciu segmentów jednostkowych. Dla poni»szych »¡da« przydziaªu i zgªosze« zwolnienia pami¦ci prze±led¹ kolejne etapy dziaªania metod Best Fit, Worst Fit, First Fit oraz Cycle First Fit. W razie potrzeby zastosuj optymaln¡ metod¦ kompresji (w dowolnym kierunku) - jaki jest jej ª¡czny koszt mierzony liczb¡ transpozycji segmentów pami¦ci?

nr. »¡dania proces

»¡danie

nr. »¡dania proces

»¡danie

1

P1

przydziel 4

7

P1

zwolnij

2

P2

przydziel 2

8

P3

zwolnij

3

P3

przydziel 1

9

P6

przydziel 1

4

P2

zwolnij

10

P7

przydziel 2

5

P4

przydziel 1

11

P8

przydziel 3

6

P5

przydziel 3

3

c

° Paweª Rembelski

Systemy operacyjne materiaªy ¢wiczeniowe

Studia dzienne PJWSTK

Zast¦powanie stron pami¦ci wirtualnej

Strategia FIFO

• skrót od First In First Out

• zast¦powana jest strona, która w pami¦ci przebywaªa najdªu»ej Strategia Drugiej Szansy

• ka»da strona pami¦ci posiada ag¦ bitow¡

• wczytanie strony do pami¦ci zyczne jest równowa»ne z ustawieniem agi bitowej na warto±¢ 1

• zast¦powane strony wybierane s¡ a» do skutku w kolejno±ci zgodnej ze strategi¡ FIFO

◦ je»eli aga bitowa zast¦powanej strony jest równa 1 to strona ta zostaje przepisana na koniec kolejki, a jej aga kontrolna zostaje ustawiona na 0

◦ je»eli aga bitowa zast¦powanej strony jest równa 0 to strona ta zostaje zast¡piona now¡ stron¡

Strategia LRU

• skrót od Least Recently Used

• zast¦powana jest strona, która nie byªa u»ywana przez najdªu»szy okres Strategia Optymalna

• zast¦powana jest strona, która nie b¦dzie u»ywana przez najdªu»szy okres

• rozwi¡zanie czysto teoretyczne

Zadanie

Zakªadamy, »e pami¦¢ zyczna pewnego urz¡dzenia skªada si¦ z pi¦ciu ramek ponumerowanych od 1

do 5. Ile sygnaªów braku strony zostanie wygenerowanych, je»eli pami¦¢ zyczna urz¡dzenia odbierze nast¦puj¡cy ci¡g odwoªa« do stron

chwila

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

strona

1

2

3

4

2

1

5

6

2

1

2

3

7

6

3

2

4

5

3

6

w przypadku zastosowania strategii

• FIFO,

• Drugiej Szansy,

• LRU,

• Optymalnej?

Przyjmujemy, »e pocz¡tkowo ramki pami¦ci zycznej s¡ puste.

4

c

° Paweª Rembelski