Algorytmy przydziału PAO:

1. Algorytm bliźniaków (Buddies)

Oparty na podziale pamięci (o długości 2^k) na dwa bliźniacze bloki. Jeden z nich jest dalej połowiony, aż do uzyskania bloku o minimalnej długości spełniającego wymagania zlecenia przydziału.

2. Algorytm leniwych bliźniaków próbuje zarządzać pulą lokalnie wolnych (tych które nie są obok siebie) bloków tak, by wywoływać łączenie tylko wtedy gdy ilość tych bloków przekracza pewną wartość graniczną.

3. Alg. Dwuręcznego zegara jest algorytmem zastępowania stron. Używa bitu „Reference” (odwołania do strony), by sprawdzić do których stron nie ma odwołań. Bit Ref. Jest równy 0, gdy strona jest do zrzucenia, 1-gdy jest odczytywana bądź zapisywana. Algorytm wykorzystuje 2 ręce: Przednią - przechodzi przez listę dostępnych stron i ustawia bit Ref. Na 0. Tylna ręka :] jakiś czas po pierwszej ponownie sprawdza bit Ref.. Jeśli 2 ręka stwierdzi, że bit Ref. Jest 1 to ignoruje stronę, jeśli 0 -umieszcza na liście stron do zrzucenia. Parametry alg - szybkość skanowania, odległość między rękoma.

Algorytmy synchronizacji współbieżnych procesów:

Algorytm bankiera opiera się na następujących obserwacjach. Jeżeli w danym stanie system może doprowadzić do zakończenia wszystkich procesów, to może to również zrobić wykonując i kończąc te procesy w pewnej kolejności, po jednym na raz. Aby móc zakończyć jakiś proces, musimy mieć w systemie tyle wolnych zasobów, żeby zaspokoić jego potrzeby. W najgorszym przypadku ilość potrzebnych zasobów jest równa różnicy między maksymalną zadeklarowaną liczbą potrzebnych zasobów, a ilością aktualnie przydzielonych zasobów. Jednak po zakończeniu procesu w systemie może tylko przybyć wolnych zasobów, gdyż wszystkie zasoby przydzielone procesowi są zwalniane. Tak więc, aby odpowiedzieć na pytanie czy sytuacja jest bezpieczna, musimy stwierdzić, czy istnieje taka kolejność P₁, P₂, ..., P_n, w której możemy wykonywać i kończyć procesy. Ponadto, taką kolejność możemy konstruować w sposób zachłanny - jeżeli istnieje taka kolejność i wolne w danej chwili zasoby wystarczają do zakończenia procesu P, to istnieje również taka kolejność zaczynająca się od P.

Niech n będzie liczbą procesów, a m liczbą rodzajów zasobów (w naszym przypadku m=4). Zakładamy, że są określone następujące cztery tablice:

• wolne - wektor długości m określający ilości wolnych zasobów poszczególnych rodzajów,

• maks - macierz
  określająca zadeklarowane przez poszczególne procesy maksymalne ilości potrzebnych im zasobów,

• przydzielone - macierz
  określająca ilości zasobów przydzielonych poszczególnym procesom,

• potrzebne - macierz
  określająca maksymalne ilości zasobów potrzebnych do zakończenia poszczególnych procesów; tę macierz możemy zawsze wyznaczyć na podstawie wzoru
  .

Dodatkowo zakładamy, że mamy do dyspozycji dwa pomocnicze wektory: pom i zakończone długości odpowiednio m i n. Wektor pom reprezentuje symulowaną ilość wolnych zasobów, a zakończone reprezentuje zbiór procesów, które udało się zakończyć. Algorytm bankiera ma następującą postać:

1	pom := wolne;
2	zakończone := (false, false, ..., false);
3	while istnieje takie i, że:
4	not zakończone[i] and potrzebne[i, j] pom[j]
5	do begin
6	for j := 1 to m do
7	pom[j] := pom[j] + przydzielone[i, j];
8	zakończone[i] := true
9	end;
10	if zakończone = (true, true, ..., true) then
11	system jest w stanie bezpiecznym
12	end
13	system nie jest w stanie bezpiecznym.

Algorytm ten ma złożoność O(n²m).

Algorytm bankiera jest zwykle używany do określenia, czy stan systemu po przydzieleniu zasobów jest bezpieczny.

Planowanie dostępu do dysku

Ekonomiczne wykorzystanie sprzętu jest jednym z wielu zadań systemu operacyjnego. Jeśli chodzi o dyski to jest to troska o szybki dostęp do nich i szybki przesyłanie danych zawartych na nich. Są swa ważne składniki wpływające na czas dostępu do dysku:

1. czas szukania (seek time) - jest to czas potrzebny na przemieszczenie ramienia dysku do pozycji w której głowice znajdują się w cylindrze zawierającym potrzebny sektor

2. opóźnienie obrotowe (rotation latency) - jest to czas potrzebny na obrót dysku do pozycji w której głowica trafia nad potrzebny sektor

Jest jeszcze jeden parametr wpływający na prędkość pracy dysku. Jest to szerokość pasma (bandwidth). Szerokością pasma nazywamy łączną liczbę przesyłanych bajtów, podzieloną przez łączny czas jaki upływa od pierwszego zamówienia na usługę dyskową, do chwili zakończenia ostatniego przesyłania. Planowanie wykonywania dyskowych operacji we-wy może polepszyć zarówno czas dostępu, jak i szerokość pasma.

Każdy proces potrzebujący wykonać operacje we-wy dotyczącą dysku musi odwołać się do systemu operacyjnego. Zamówienie takie zawiera następujące informacje:

1. czy jest to operacja wejścia czy wyjścia

2. dyskowy adres przesyłania

3. adres pamięci dotyczący przesyłania

4. liczbę bajtów do przesłania

Zamówienie można spełnić natychmiast, jeżeli napęd dysku i jego sprzętowy sterownik są gotowe do pracy. W innym przypadku każde nowe zamówienie jest ustawiane w kolejce zamówień. Kolejka dyskowa może mieć po kilka zamówień w systemie wieloprogramowym. Po zakończeniu jednego zamówienia system ma możliwość wyboru zamówienia, które będzie realizowane w następnej kolejności. Wyróżniamy kilka sposobów wyboru zamówień.

Opiszemy teraz metody planowania dostępu do dysków

1. Metoda FCFS

Jest to najprostszy algorytm planowania dostępu do dysku. Zamówienia sa wykonywane w kolejności ich zgłaszania. Skrót FCFS (first-come, first-served) oznacza 'pierwszy zgłoszony - pierwszy obsłużony'. Jest to najbardziej sprawiedliwy z algorytmów jednak nie najszybszy. Załóżmy że kolejka zamówień na operacje we-wy wygląda tak i odnosi się do bloków w cylindrach:

100, 198, 44, 132, 2, 134, 70, 72

a głowica dysku znajduje się początkowo na 65 cylindrze. Głowica najpierw przemieści się do cylindra 100, a następnie w kolejności : 198, 44, 132, 2, 134, 70, a na końcu do cylindra 72. Głowica przechodzi łącznie 703 cylindry. Wadą tego planowania jest gwałtowne wychylanie się głowicy.

2. Metoda SSTF

Skrót SSTF jest skrótem od Shortest-Seek-Time-First, co oznacza -najpierw najkrótszy czas przeszukiwania'. Metoda ta polega na realizacji zamówień w takiej kolejności, aby wielkość liczby cylindrów pomiędzy każdym zamówieniem była jak najmniejsza. Startując od cylindra 65 głowica przechodzi do cylindra 70, gdyż ten leży najbliżej. Następnym cylindrem jest cylinder 72. Z cylindra 72 skaczemy do cylindra 44. Później głowica pobiera dane z cylindrów w następującej kolejności: 2, 100, 132, 134, 198. Głowica łącznie pokonuje 273 cylindry. Jest to ok. 1/3 tej drogi jaką pokonuje głowica w metodzie FCFS. Planowanie tą metodą może jednak powodować tzw. głodzenie (starvation). Spowodowane jest to tym, że zamówienia mogą przychodzić w dowolnym momencie. Powiedzmy że mamy w kolejce do obsłużenia zamówienia dotyczące cylindrów 20 i 190. W czasie obsługiwania zamówienia w cylindrze 14 może nadejść zamówienie dotyczące cylindra będącego bliżej, aniżeli cylinder 190. Zostaje więc obsłużone zamówienie które właśnie przyszło, a zamówienie dotyczące cylindra 190 zostaje przesunięte na koniec. Podczas wykonywania tego zamówienia, może przyjść kolejne będące bliżej aniżeli odległość tego cylindra, obsługiwanego teraz, aniżeli odległość od cylindra 190. W ten sposób cylinder 190 może być w ogóle nie obsłużony.

Algorytm ten, chodź krótszy od algorytmu FCFS, nie jest algorytmem optymalnym.

3. Metoda SCAN

Algorytm SCAN polega na tym, że ramię dysku rozpoczyna przemieszczanie się od jednej krawędzi dysku, do przeciwległej krawędzi. W czasie przemieszczania się ramienia dysku, obsługiwane są zamówienia w kolejności napotkanych, żądanych przez system, cylindrów. Po osiągnięciu przeciwległej krawędzi ramię dysku zmienia kierunek ruchu i zaczyna wracać, obsługując następne zamówienia napotkane po drodze.

Do zaplanowania zamówień w algorytmie SCAN potrzebna nam jest znajomość kierunku ruchu głowicy. Załóżmy że ramię przesuwa się w kierunku cylindra o numerze 0, wtedy kolejność odczytywanych cylindrów będzie następująca: 65, 44, 2, 0, 70, 72, 100, 132, 134, 198. Jeśli w czasie przebiegu głowicy pojawiłoby się zamówienie dotyczące cylindra który będzie za chwilę odwiedzany, zamówienie to zostanie obsłużone prawie natychmiast. Jeśli natomiast zamówienie dotyczy cylindra który niedawno był mijany przez głowicę zamówienie musi poczekać aż głowica dojdzie do końca i powróci do tego miejsca.

Inną nazwą dla algorytmu SCAN jest nazwa: algorytm windy (elevator algorithm), a to dlatego że ramię dysku zachowuje się jak winda. Jeżdżąc góra � dół obsługuje wszystkie zamówienia, tak jakby winda zabierała ludzi.

4. Metoda C-SCAN

Odmianą algorytmu SCAN, jest algorytm C-SCAN (cilcural SCAN). Polega ona na tym, że po osiągnięciu jednej krawędzi dysku głowica wraca do drugiej krawędzi, ale nie wykonuje nic poza tym. Po osiągnięciu tej drugiej krawędzi, głowica przemieszcza się do pierwszej krawędzi, wykonując zlecenia po drodze. Algorytm ten jest zaprojektowany w trosce o bardziej równomierny rozkład czasu czekania na wykonanie zlecenia.

5. Metoda LOOK

Zarówno w planowaniu SCAN jak i C-SCAN głowica przemieszcza się od jednego skrajnego położenia do drugiego skrajnego. Żaden z tych algorytmów jednak w rzeczywistości nie jest tak implementowany. Przeważnie głowica przesuwa się pomiędzy skrajnymi zamówieniami. Gdy osiągnie jedno z nich, natychmiast robi zwrot i idzie w kierunku przeciwnym, nie dochodząc do skrajnego położenia na dysku. Są to algorytmy LOOK i C-LOOK które są poprawionymi odpowiednikami algorytmów SCAN i C-SCAN.

Wybór odpowiedniego algorytmu

Ciężko jest wybrać odpowiedni algorytm dostępu do dysku. Algorytm SSTF jest dość powszechny i wygląda bardzo naturalnie. W systemach z dużą liczbą zamówień, bardziej odpowiednimi algorytmami są algorytmy SCAN i C-SCAN, gdyż nie występuje w nich zjawisko tzw. głodzenia. Można zdefiniować dla konkretnej listy zamówień optymalny porządek, lecz wielkość obliczeń do tego potrzebnych może nie dać się usprawiedliwić uzyskanymi oszczędnościami w stosunku do metod SSTF lub SCAN. Liczba i rodzaj zamówień wpływa w największym stopniu na wydajność każdego algorytmu. Lokalizacja katalogów i bloków indeksowych również jest ważna, gdyż każdy plik przed użyciem musi być otwarty. Natomiast otwarcie pliku wymaga przeszukania struktury katalogowej. Dlatego algorytm planowania dostępu do dysku powinien być pisany jako osobny moduł i w razie potrzeby odpowiednio podmieniany przez system operacyjny. W nowoczesnych dyskach twardych algorytmy planowania są zawarte w sterowniku dysku, gdyż producent sam najlepiej dobiera, jaka metoda jest najlepsza dla dysku jego produkcji. System operacyjny musi jednak nadzorować te algorytmy gdyż np. operacja stronicowania na żądanie ma większy priorytet niż np. operacja we-wy dotycząca aplikacji. Dlatego system operacyjny posiada swoje własne algorytmy które mają zapewnić zarówno optymalną szybkość, jak i bezpieczeństwo danych zawartych na tym dysku.

Algorytmy przydziału procesora:

1) EDD:
Kazde zadanie ma jakas linie krytyczna (czas przed ktorym musi zostac wykonany).
Sortujemy je od tego ktory ma najmniejsza wartosc tej linii do tego o najwiekszej..
Dzieki temu jest najwieksza szansa ze wiekszosc z nich zdazy sie wykonac przed
wyznaczonym czasem.

2) ERT:
Porzadkujemy zadania niemalejaco wzgledem czasu gotowosci (cokolwiek to nie jest).

3) Hodgsona-Moore'a:
Najpierw układamy zadania przez algorytm EDD. Nastepnie sprawdzamy od poczatku
czy ktorys z nich nie przekroczyl linii krytycznej. Jesli tak to wyszukujemy od 1 do tego
zadania wlacznie taki, ktory ma najdluzszy czas wykonania i wyrzucamy go na koniec
listy.

4) Hu:
Liczymy poziomy wszystkich zadan (wydaje mi sie ze tu ustala sie po prostu jakas
zaleznosc miedzy zadaniami, czyli ile zadan musi byc wykonane zanim wybrane moze
zostac rozpoczete.. Mam nadzieje ze Gawiej to sam wypisze;) ). Nastepnie wybieramy te
bez nastepnikow i tworzymy z nich liste, ukladajac je tak zeby te o najwiekszym
poziomie byly na poczatku.. I teraz przydzielamy je po kolei tylu prockom ile mamy.. Po
tym wywalamy z drzewa te ktore przydzielilismy i czyscimy liste. Jezeli dobrze rozumiem
to algorytm ten pozwala na maksymalna optymalizacje w wypadku jezeli jakies procesy
potrzebuja zeby np inny proces cos wczesniej policzyl..

5) LS:
Tutaj po prostu przydzielamy je tak jak sa podane do pierwszego wolnego procka.

6) LPT:
Najpierw ukladamy zadania od najwiekszego czasu wykonywania do najmniejszego, a
potem stosujemy LS.

7) round-robin:
Ten chyba wszyscy powinni rozumiec.. Po prostu procek wykonuje przez chwile czesc
procesu (np jakis watek) przez okreslony czas, a nastepnie przelacza sie na kolejny na
liscie.. Po dojechaniu do konca listy zaczyna od poczatku..

8) SPT:
Algorytm ktory uklada zadania wzgledem czasu wykonywania, czyli najpierw jest ten
ktory najszybciej sie zakonczy, az do tego ktory bedzie dzialal najdluzej..

9) alg. McNaughtona zakłada że proces można podzielić. wrzuca się procesy po koleji na procesor. a kiedy czas wykonania przekroczy linie końcową obcina i przechodzi do nowego procka. nie wiem do czego ma sie to przydać.

Algorytmy kryptograficzne:

Szyfr Playfair

Polega on na zastąpieniu par liter tekstu jawnego inną parą liter. Użyjmy jako słowa-klucza słowa SZYFR. Zatem pierwszą czynnością będzie zapisanie liter alfabetu w kwadracie 5 x 5, zaczynając od słowa kluczowego i łącząc litery I oraz J.

S Z Y F R
A B C D E
G H I/J K L
M N O P Q
T U V W X

Jeżeli postanowisz używać innego słowa-klucza, w którym litery się powtarzają (dotyczy to szczególnie imion, np. MARTYNA), pamiętaj że powtórzenia liter musisz pominąć (w tym przypadku słowem-kluczem będzie MARTYN).

Potem dzielimy tekst, który mamy zamiar zaszyfrować (nazywajmy go tekstem jawnym) na dygramy, czyli pary liter. Każda z par powinna się składać z dwóch różnych od siebie liter. W razie potrzeby możemy w tym celu wstawić np. x. Dodajemy je także na końcu wtedy, gdy tekst nie kończy się pełnym dygramem.

Na przykład:

tekst jawny wikipedia jest najlepsza

tekst jawny jako digramy wi-ki-pe-di-aj-es-tn-aj-le-ps-za

Teraz przystępujemy do właściwego szyfrowania. Pary liter możemy podzielić na trzy grupy:

1. obie litery są w tym samym wierszu

2. obie litery są w tej samej kolumnie

3. pozostałe

Jeśli obie litery są w tym samym wierszu, zastępujemy je sąsiadującymi z nimi literami z prawej strony; na przykład ki zamienia się w LK. Jeżeli jedna z liter znajduje się na samym końcu wiersza, zastępujemy ją pierwszą literą w tym wierszu. Jeśli obie litery znajdują się w tej samej kolumnie, powinny zostać zastąpione przez litery leżące pod nimi; np. le zmienia się w QL. Jeżeli któraś litera znajduje się na końcu kolumny, zastępujemy ją pierwszą literą w kolumnie.

Zupełnie inna jest sytuacja, kiedy każda z liter digramu znajduje się w innym wierszu i innej kolumnie. W takim wypadku, aby zaszyfować pierwszą literę, idziemy wzdłuż wiersza, aż dotrzemy do kolumny, która zawiera drugą literę. Litera na skrzyżowaniu wiersza z kolumną zastępuje pierwszą literę. W celu zaszyfrowania drugiej z liter, szukamy wzdłuż wiersza kolumny, w której znajduje się pierwsza litera. Znak ze skrzyżowania reprezentuje drugą literę. Zaszyfrowany tekst przykładowy brzmi zatem:

tekst jawny jako digramy wi ki pe di aj es tn aj le ps za

tekst zaszyfrowany (kryptogram) VK LK QD CK CG AR UM CG QL MF SB

Adresat znający słowo-klucz, może odczytać wiadomość odwracając opisaną procedurę.

Szyfr polialfabetyczny - uogólnienie szyfru monoalfabetycznego na większą liczbę przekształceń.

Szyfr taki składa się z n przekształceń, takich że pierwszą literę szyfrujemy pierwszym przekształceniem, drugą drugim itd., po czym powtarzamy przekształcenia od początku począwszy od litery n+1. Szyfry polialfabetyczne maja współcześnie wyłącznie historyczne znaczenie.

Przykładem szyfru polialfabetycznego jest szyfr Vigenere'a.

Szyfry homofoniczne

Szyfry homofoniczne odwzorowują każdy znak a_i alfabetu jawnego A na zestaw elementów tekstu zaszyfrowanego, zwanych homofonami. W ten sposób odwzorowanie tekstu jawnego na zaszyfrowany można określić jako funkcję:

f:A→B

gdzie B jest alfabetem szyfrującym, składającym się z podzbiorów b_i, będących zbiorami homofonów odpowiadających a_i.

Tekst jawny M=m₁, m₂ ... podlega szyfrowaniu jako b=c₁, c₂, ... gdzie znak c_i wybierany jest losowo ze zbioru homofonów f(m_i).

Przykład:

Litera

S 34 41 56 83

M 22 53 65 90

O 44 76

L 09 27 40 59

N 10 11 28 54 70 80

I 33 91

K 20 29 45 64 78

Tekst jawny: S M O L N I K

Tekst zaszyfrowany: 41 53 76 27 11 91 29

Lub: 34 90 44 59 10 33 78

Szyfry homofoniczne mogą być dużo trudniejsze do złamania niż zwykłe szyfry podstawieniowe, szczególnie w przypadkach, gdy liczba homofonów przydzielonych literze jest proporcjonalna do względnej częstości jej występowania. Oczywiście im więcej homofonów przydzielimy literom, tym silniejszy tworzymy szyfr.

Większość szyfrów można złamać, gdy posiadamy odpowiednio dużą ilość tekstu zaszyfrowanego. Wynika to z faktu, że istnieje tylko jeden klucz K, którego użycie do odszyfrowania daje w wyniku zrozumiały tekst jawny. Istnieje jednak możliwość stworzenia szyfru homofonicznego wyższego stopnia, dla którego kryptogram można zdeszyfrować na więcej niż jeden sensowny tekst.

Szyfry monoalfabetyczne

Szyfry monoalfabetyczne zamieniają każdy znak uporządkowanego alfabetu jawnego na odpowiedni znak uporządkowanego alfabetu szyfru. Bardzo często alfabet szyfru powstaje z alfabetu jawnego przez prostą zamianę kolejności znaków w alfabecie jawnym (permutacja). Jeśli alfabet jawny ma postać a₁, a₂, ..., a_N-1, wtedy alfabet szyfru ma postać f(a₁),f(a₂), ...,f(a_N-1), przy czym f jest odwzorowaniem wzajemnie jednoznacznym (bijekcją). Kluczem jest alfabet szyfru lub funkcja f.

Przykład:

Alfabet jawny: A B C D E F G H I J K L M N O P R S T U W X Y Z

Alfabet szyfru: D E F G H I J K L M N O P R S T U W X Y Z A B C

Tekst jawny: A D A M S M O L N I K

Tekst zaszyfrowany: D G D P W P S O R L N

Powyższy przykład jest szczególnym przypadkiem szyfru podstawieniowego, gdyż szyfr powstał na �śalfabecie przesuniętym" zwanym też szyfrem Cezara. Funkcja f ma wtedy postać:

f(a) = (a+k) mod N

gdzie:

N - długość alfabetu,

k - przesunięcie w prawo,

a - pozycja litery w alfabecie.

Innym przypadkiem szyfru podstawieniowego jest szyfr oparty na mnożeniach zwany przerzedzonym. Funkcja f ma postać:

f(a) = (s*k) mod N

przy czym k oraz N są liczbami względnie pierwszymi. Jeśli k i N nie są liczbami względnie pierwszymi, to wielu literom tekstu jawnego będzie odpowiadać ta sama litera tekstu zaszyfrowanego.

Te dwie metody można połączyć i otrzymamy wtedy szyfr afiniczny.

f(a) = (a * k₁ + k₀) mod N

gdzie:

k₀ - przesunięcie w prawo,

k₁ - współczynnik przerzedzenia.

Ogólny wzór przekształcenia wyższego rzędu otrzymuje się z przekształceń wielomianowych stopnia t:

f(a) = (a ^t*k _t+ a ^(t-1)*k_(t-1)+ ...a* k₁+ k₀ ) mod N.

---