Footnotes

... uniksowy.¹

Zgodnie z lansowaną w polskiej literaturze konwencją, nazwa systemu Linux jest pisana w mianowniku przez x (tj. Linux), natomiast w pozostałych przypadkach użyto formy spolszczonej, np. Linuksa, Linuksie, itd. Zasada ta dotyczy także nazwy Unix.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uniksowy.²

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uniksowy.³

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uniksowy.⁴

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uniksowy.⁵

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... operacyjnej ^1.1

W pamięci operacyjnej musi być przechowywany zawsze co najmniej blok kontrolny procesu, natomiast część lub całość zawartości jego przestrzeni adresowej może zostać usunięta na urządzenie wymiany.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... operacyjnej ^2.1

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...idle.^2.2

Zob. serwer http://www.linuxhq.com/

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... uśpienia.^2.3

W [1] dodany jest jeszcze czas, jaki proces spędza w oczekiwaniu na załadowanie do pamięci, jednak czas ten dotyczy algorytmu szeregowania długoterminowego, którego tutaj nie rozpatruje się. Zob. rozdział 1.1.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... priorytet.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... priorytet.^4.1

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... priorytet.^5.1

W klasycznym Uniksie jest odwrotnie -- niższe wartości oznaczają wyższy priorytet. Wartości priorytetów od 0 do 49 są przeznaczone dla procesów w trybie jądra, a od 50 do 119 dla procesów w trybie użytkownika. Wartość upri jest z zakresu od -20 dla procesów o najwyższym priorytecie do 19 dla procesów o najniższym priorytecie. Opis został "`przeskalowany'', aby można było łatwiej porównywać opisy z rozdziałów 2.1-2.4.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... sposób.^5.2

Nagradzane są tylko procesy śpiące.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... procesów:^5.3

W Linuksie proces budzony musi mieć priorytet o 3 większy niż proces bieżący, aby nastąpiło przeszeregowanie. Uzasadnione jest to tym, że wybieranie procesu oraz przełączanie kontekstu są operacjami czasochłonnymi.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... plików.^5.4

Oznacza to, że na poziomie, na którym odbywały się zmiany (niezależnym od systemu plików) nie można dobrze odróżnić danych przychodzących z myszki od danych czytanych z pliku na dysku.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 1 sek.^9.1

Czyli co 1 s wywołuje się funkcję pokazywaną przez zmienną ts_tick.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... procesora,^9.2

Moduły zostały zaprojektowane tak, aby można było je także implementować dla architektur SMP. W pracy właściwość ta nie była używana.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...procfs ^9.3

procfs to system plików, który udostępnia m. in. dane o jądrze poprzez pliki specjalne. Z procfs korzysta np. program top, który wyświetla bieżące statystyki systemu.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...procfs.^10.1

Zob. przyp. na str.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... demony ^10.2

Procesy systemowe o specjalnych uprawnieniach.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... $1\ \mathrm{takt} = 1/100\ \mathrm{s}$ .^10.3

Z dobrą dokładnością. Z lektury treści jądra wynika, że 1 takt Linuksa to 10⁴ taktów fizycznego zegara tykającego 10⁶+20 (a nie 10⁶) razy na sekundę. Błąd wynosi zatem teoretycznie około $-0.00002\%$ . W praktyce niedokładności fizycznego zegara są dużo większe.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...procfs.^11.1

Zob. przyp. na str.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... demony ^11.2

Procesy systemowe o specjalnych uprawnieniach.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... $1\ \mathrm{takt} = 1/100\ \mathrm{s}$ .^11.3

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... gotowości ^11.4

Czas, który proces spędził w kolejce procesów gotowych oczekując na przydzielenie procesora.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... spełniona.^11.5

W przeprowadzonych testach miało to miejsce tylko w kilku przypadkach na kilkanaście tysięcy prób.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... procesora.^13.1

Parametry w tabelach dobrane są tak, aby nie nastąpiło zagłodzenie. Każdy proces dostanie w końcu procesor, ale w tym przypadku procesy działające w tle dostają jeden kwant czasu (10 taktów) co kilka sekund, więc prawie nie działają.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... procesora.^13.2

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ramek ^14.1

Ramka to kawałek pamięci fizycznej o ustalonym rozmiarze, np. na x86 ramki mają 4KB.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... LRU;^14.2

Ang. least recently used -- najmniej ostatnio używany.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ramek ^15.1

Ramka to kawałek pamięci fizycznej o ustalonym rozmiarze, np. na x86 ramki mają 4KB.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... LRU;^15.2

Ang. least recently used -- najmniej ostatnio używany.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... sprzęt.^15.3

Na przykład procesory x86 mają 4 poziomy uprzywilejowania, a Linux korzysta tylko z dwóch: najwyższego i najniższego.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... fizyczne.^15.4

Istnieją od tej reguły wyjątki -- na przykład mechanizm pamięci dzielonej pozwala kilku procesom współdzielić tą samą część pamięci operacyjnej komputera.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... procesów.^15.5

To jest tablice translacji adresów w trybie jądra są wspólne dla wszystkich procesów.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... użytkownika.^15.6

W istocie sprawdzenie samego adresu może w niektórych architekturach odbywać się sprzętowo, ale np. w x86 nie można sprawdzić praw dostępu do obszaru pamięci.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... końcowych.^15.7

Potrzebną operacją jest także znalezienie kolejnego elementu, stąd uporządkowanie list.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... obszarów.^15.8

Do 1GB przestrzeni wirtualnej można np. zamapować 4-kilobajtowe kawałki pliku, co daje około 256000 obszarów.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... danych ^16.1

Tak, aby dominował czas wyszukiwania obszaru pamięci, a nie czas potrzebny na fizyczne skopiowanie danych.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... procesu.^16.2

Informację tę można było przechowywać także w strukturze mm_struct (gromadzącej dane o przestrzeni adresowej procesu), gdyż żaden badany tu program nie współdzielił przestrzeni adresowej z innymi procesami.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... mm_struct^16.3

Struktura ta opisuje przestrzeń adresową procesu w trybie użytkownika. Zawiera m. in. wskaźnik na korzeń drzewa AVL.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... pierwszego.^16.4

Uzasadnia się to tym, że pierwsze uruchomienie aplikacji może, choć nie musi, wiązać się z większym narzutem systemowym, np. wczytaniem kodu programu z dysku do pamięci operacyjnej. Kolejne uruchomienia dają zwykle nieco krótszy czas wykonania, gdyż kod programu znajduje się już w pamięci operacyjnej.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... znikoma ^16.5

W porównaniu z liczbą wywołań potrzebną do stwierdzenia różnicy czasu wykonania. Zob. dalej.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...tex2html_verb_mark ^16.6

Program map nie wywołuje funkcji find_vma() bezpośrednio, ale pośrednio poprzez próbę pobrania danych z obszaru w swojej przestrzeni adresowej.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... starych,^16.7

Spośród dziesięciu, które każdy program ma przydzielone standardowo.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... deterministycznie.^16.8

Winę za to ponosi najprawdopodobniej kod standardowej biblioteki języka C lub powłoka systemowa (program bash): nowy proces używa przez krótki czas kodu powłoki zanim wywoła funkcję systemową execv i tym samym przejdzie do wykonania kodu właściwego programu.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... $5\cdot 10^8$ węzłów ^16.9

Różnica dla lin-avl i lin-lst, por. tab. 8.2.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... szybsze ^16.10

Czytaj: program map wykonuje się szybciej w tym jądrze.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... aplikacji.^16.11

Model nieco wyolbrzymiony. Żadna aplikacja nie powoduje tylu wołań funkcji find_vma() w tak krótkim przedziale czasu.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... komputera.^16.12

Co nie ominęło także autora niniejszej pracy.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Tomek Blaszczyk
1999-05-21