METODY OBSŁUGI ZAKLESZCZEŃ

-Zapobieganie zakleszczeniom

Wzajemne wykluczanie
Przetrzymywanie i oczekiwanie
Brak wywłaszczania
Czekanie cykliczne

-Unikanie zakleszczeń (warunki do porstania zakleszczeń prawdziwe, ale badamy za każdym razem czy system bezpieczny przed każdym żądaniem)

Algorytm grafu przydziału zasobów

-Zanim proces P(i) rozpocznie działanie, wszystkie jego krawędzie deklaracji muszą pojawić się w grafie przydziału zasobów.

-Zamówienie może być spełnione tylko wtedy, gdy zamiana krawędzi zamówienia P(i) —> Z(j) na krawędź przydziału Z(j) —> P(i), nie spowoduje utworzenia cyklu w grafie przydziału zasobów.

-Sprawdzenie bezpieczeństwa polega na użyciu algorytmu wykrywania cyklu w tym grafie (brak cyklu=stan bezpieczny)

Algorytm bankiera

-używany gdy każdy typ zasobu ma wiele egzemplarzy

-proces wchodząc deklaruje max. ilość egzem. typu zasobu

-rodzaje zasobów=niewymienialne waluty;procesy=klienci;bank=system;wolne zasoby=kasa banku;przydzielone zasoby=kasa pożyczona;max.ilości zasobów=limity kredytów

-Wykrywanie zakleszczeń i odtwarzanie

ZŁOŻONOŚĆ OBLICZENIOWA: ilość zasobów niezbędnych do wykonania algorytmu (zależy od rozmiaru i uporządkowania danych wejściowych|Nie architektura)

Złożoność zasobowa (pamięciowa) - jej mirą jest ilość zużytej pamięci

Złożoność czasowa - jej miarą jest liczba operacji podstawowych w zależności od rozmiaru wejścia.

Notacja „wielke O”
O(g(n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ≤ f (n) ≤ c · g(n) dla wszystkich n ≥ n0}

Algorytm o czasie wykonania F(N) ma złożoność [liniową|kwadratową], jeśli:

Złożoność rz [N|N^2] ozn. symbolem F(N) = [O(N)|O(N^2)]

JĘZYK P. - zbiór zasad określających, kiedy ciąg symboli tworzy program oraz jakie obliczenia opisuje. Pozwala on na precyzyjny zapis algorytmów oraz innych zadań, jakie komputer ma wykonać.
- wysoki lvl - rozbudowana składnia czytelna dla prog. (C++, Java) - niski lvl (asemblery) - posługują się składnią zbliżoną do elementarnych operacji procesora i adresów symbolicznych reprezentujących jego rejestry; łatwo przekształcalne do kodu maszynowego

- kompilowane, gotowe do wykonywania przez system operacyjny (C++)

- interpretowane, wykonywane przez interpretery (matlab, php, ruby, perl)

NOTACJA NADMIAROWA - Wartość binarna słowa kodowego jest równa kodowanej liczbie

pomniejszonej o pewną stałą zwaną nadmiarem.

TRYBY ADRESOWANIA - sposób określenia miejsca przechowywania argumentów rozkazu(Kod Rozkazu=Kod Operacji+Arg R)

- natychmiastowe-ArgR w KR->musi być znany w momencie pisania programu (+)nie trzeba się odnosić do pamięci (-)mały rozmiar pola w rozkazie
- bezpośrednie-w KR adres komórki pamięci gdzie jest ArgR (+)nie wymaga obliczeń (-)nieprzenaszalność programu i znaczne ograniczenie przestrzeni adresowej
- rejestrowe - w KR odniesienie do rejestru gdzie ArgR (+/-)rejestrów mało → szybko pobiera
- pośrednie-w KR odniesienie do rejestru gdzie adres ArgR w pamięci (+)duża przestrzeń adresowa (-)wolniej
- indeksowe z przemieszczeniem-adres

ArgR w pamięci to suma zawartości rejestru i przemieszczenia określonych w KR

CYKL ROZKAZOWY PROCESORA

Pobierania:

1. Adresowanie: podanie zawartości licznika rozkazów PC na magistralę adresową (Wartość licznika rozkazów-> Szynę adresową-> Pobranie adresu rozkazu -> Pamięć)

2. Odczyt zaadresowanej komórki pamięci do rejestru rozkazów (Pamięć-> Szyna danych-> rejestr rozkazów)

3. Zwiększenie licznika rozkazów o jeden (następny rozkaz)

Wykonania:

4.Rejestr rozkazków-> dekoder-> wynik wykonania rozkazu (np. sygnał sterujący)
PROBLEM NP:Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność. ||NP jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga
Problem NP-zupełny - problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym (→jeśli potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP.||1^st NPC = SAT(p spełnialności formuł zadaniowych) ||RSA

CECHY POPRAWNOŚCI ALGORYTMU:
- skończoność - wykonuje się w skończonej liczbie kroków
- określoność - operacje i ich porządek wykonywania są ściśle określone, brak miejsca na dowolną interpretację
- ogólność - algorytm nie ogranicza się do jednego szczególnego przypadku, ale odnosi do pewnej klasy zadań
- efektywność -algorytm prowadzi do rozwiązania jak najprostszą drogą
- kompletność - uwzględnia wszystkie przypadki, realizuje algorytm zgodnie z instrukcjami przewidzianymi na każdy przypadek
- jednoznaczność - niezależność działania programu od momentu jego wykonania, innych programów działających w systemie oraz od sprzętu

METODY SYNCHRONIZACJI PROCESÓW:
Przyczyny, dla których konieczna jest synchronizacja procesów:
- problem sekcji krytycznej - procesy współdzielą pewną strukturę danych;
- problem producenta-konsumenta - wyniki działania jednego procesu stanowią dane dla innego procesu; Prod dodaje do bufora (max n), Kon wyjmuje |mają nie czekać-semafor
- problem pięciu filozofów - procesy korzystają z pewnej wspólnej puli zasobów.
Środki synchronizacji procesów:
Semafory- wiele procesów chce 1 zasób; EZ|dostęP: czekaj (when wartsem>0 wartsem++) i sygnalizuj (wartsem++), Semafory binarne (muteksy) wartsem={0,1}
Regiony -shared zmienna współdzielona przez kilka procesów, natomiast instrukcja “region zmienna when B do operacja”

Gdy proces chce wejść do sekcji krytycznej, liczymy bool B:true(S wykonana) false(opóźnianie aż B=true czyli inny proces nie przebywa w regionie)
Monitory w przetwarzaniu współbieżnym obiekt, który może być bezpiecznie używany przez kilka wątków. Metody monitora chronione przez muteksy-> w danym momencie z metody korzysta max1 wątek. Prostsza budowa obiektów, brek implementacji skomplikowanych wykluczeń.

ZWIĘKSZENIE EFEKTYWNOŚCI PROCESORA:
Pobieranie instrukcji z rejestru instrukcji (IR) do

dalszego przetwarzania odbywa się z różna prędkością w zależności od:

- trybu adresowania,

- liczby argumentów,

- czasu dostępu do pamięci,

- czasu wykonania instrukcji

- obciążenie szyny danych.
Rejestr instrukcji → wielopozycyjny bufr z kolejką instrukcji

- pobranie instrukcji(Pam)

- dekodowanie instrukcji(Dek)

- obliczenie adresu argumentów

- pobranie argumentów(Pam)

- wykonanie instrukcji (ALU)

- zapamiętanie wyników(Pam)
MASZYNA TURINGA

- jednostka sterująca- odczyt/zapis symboli za pomocą głowicy (~procesor)

- obustronnie infty taśma z symbolami ze skończonego zb.

- skończony zestaw stanów [w tym (start)(halt)].

DMT {Q,S,d,q0,F} Q-zb stanów sterowania|S-alfabet (zbiór symboli) taśmy|d-funkcja przejścia|q0-pocz stan ster|F-zb końcowych stanów ster

InstrukcjaDMT (S0, qi, Sz, qj, L/R)|S0-symbol odczytany|qi-bieżący stan ukł ster|Sz-symbol do przypisania|qj-nowy stan ukł|L/R-ruch głowicy

NDTM-dla tych samych S0,qi inne cz. operacyjne

ARCHITEKTURA VON NEUMANNA:

-pamięć komp (dane+instrukcje) każda komórka ma adres

-jednostka sterująca(pobieranie danych+ instr z pamięci i sekwencyjne przetwarzanie)

-ALU (basic operacje artmet na binarnych)

-Input/Output

System komputerowy:

- skończona i funkcjonalna pełna lista rozkazów

-możliwość wprowadzenia prog do sys przez urządzenia zew i jego przechowywanie w pamięci w sposób identyczny jak danych

- dane i instrukcje jednakowo dostępne dla jednostki centralnej

- informacja w CPU przetwarzana dzięki sekwencyjnemu odczytywaniu instrukcji z pamięci komputera i wykonywaniu ich w procesorze

Cykl wykonywania: c pobrania, c wykonania

---