egzaminProf Flashcards
Maszyna Turinga - budowa, sposób działania, programowanie
Maszyna Turinga składa się z trzech podstawowych komponentów: głowicy czytajaco-zapisujacej, nieskończenie długiej taśmy podzielonej na komórki oraz bloku sterowania, który realizuje instrukcje. Głowica odczytuje symbol z taśmy i wykonuje odpowiednią instrukcję, zapisując ewentualnie nowy symbol na taśmie. Instrukcje mogą obejmować takie działania jak przeniesienie głowicy do lewej lub prawej strony taśmy, zmiana symbolu na taśmie lub wykonanie pewnej operacji matematycznej
Działanie maszyny Turinga polega na realizacji programu opisanego przez tzw. tablice charakterystyczna. Wspomniana tablica zawiera zestaw rozkazów, składających się z trzech elementów:
znaku, który należy umieścić na taśmie, kierunku określającego przemieszczenie głowicy i stanu, w którym maszyna powinna się znaleźć po wykonaniu rozkazu.
Należy zauważyć, ze maszyna jest świadoma tego, jaki znak znajduje się pod głowica, toteż rozkaz w danym stanie jest zależny od odczytanej wartości
Programowanie polega na wypełnieniu tablicy charakterystycznej maszyny Turinga. W kolumnach tablicy znajdują się kolejne stany maszyny, rozkazy w komórkach zależne są od wiersza, który odpowiada danemu symbolowi, ze zbioru dopuszczalnych symboli
Maszyna W – budowa i działanie
Maszyna W to przykład komputera o architekturze von Neumanna, cecha charakterystyczna takiego urządzenia jest brak podziału między pamięcią programu a pamięcią danych. Oznacza to podobny system kodowania danych i instrukcji, a co za tym idzie, możliwość ich nadpisywania w trakcie działania programu.
Pojedynczy rozkaz polega na realizacji wielu sygnałów, które wpływają na zachowanie bloków funkcyjnych maszyny W.
Każdy rozkaz zaczyna się od sekwencji: czyt, wys, wei, il, która powoduje odczytanie kolejnego rozkazu z pamięci, wprowadzenie go do bloku I oraz inkrementację licznika. Rozkaz powinien zakonczyc sie sekwencja: wyad, wea, która powoduje wprowadzenie adresu kolejnego rozkazu do bufora adresowego pamięci operacyjnej.
Jeden rozkaz może składać się z wielu taktów, należy zaznaczyć, że w danym takcie tylko raz można skorzystać z magistrali adresowej i magistrali danych. Oznacza to, że po wprowadzeniu danych do jednostki arytmetyczno-logicznej, wynik mozna wyprowadzic na magistrale dopiero w kolejnym takcie.
Maszyna W składa się z
Magistrali adresowej, Magistrali słowa, jednostki arytmetyczno logicznej, pamięci operacyjnej, licznika rozkazów, rejestru instrukcji, układu sterowania(pobieranie rozkazów z pamięci), urządzeń wejścia wyjścia
Język asemblera, asemblacja i generacja binarnego kodu wynikowego
Języki asemblera (zwyczajowo asemblery) to rodzina języków programowania niskiego poziomu, których jedno polecenie odpowiada zasadniczo jednemu rozkazowi procesora. Języki te powstały na bazie języków maszynowych danego procesora poprzez zastąpienie kodów operacji ich mnemonikami. Dzięki stosowaniu kilkuliterowych skrótów poleceń zrozumiałych dla człowieka pozwala to z jednej strony na tworzenie oprogramowania, z drugiej strony bezpośrednia odpowiedniość mnemoników oraz kodu maszynowego umożliwia zachowanie wysokiego stopnia kontroli programisty nad działaniem procesora. Składnia języka asemblera zależy od architektury procesora, ale i używanego asemblera, jednak zwykle autorzy asemblerów dla danego procesora trzymają się oznaczeń danych przez producenta.
Asemblacja kodu to proces, w którym mnemoniki wraz z operandami, a także etykiety i inne elementy programu napisanego w języku asemblera, są tłumaczone bezpośrednio na odpowiadające im wartości. Każda instrukcja odnosi się do pewnego numeru, ten zaś pozwala na jej zidentyfikowanie i podjęcie odpowiednich działań np. wykonanie dodawania. Binarny kod wynikowy składa się z zer i jedynek, jednakże najczęściej jest reprezentowany
w formie heksadecymalnej. W przypadku mikroprocesorów 16-bitowych o zredukowanym zestawie instrukcji (np. Microchip RISC), kod operacji składa się z: 6 bitów operacji i 10 bitów adresowania itp. W przypadku maszyny W moznaby przyjac model, w którym w pamięci operacyjnej dostępne są wartości 16-bitowe (pojedyncze słowa). Przyjmując, że maksymalnie można wykorzystać 8 instrukcji procesora, 4 bity zostaną poświęcone na kod mnemoniki, zas 12 (2 · 6) bitów na dwa operandy odwołujące się do pamięci operacyjnej. Oznacza to, że pamięć ma pojemność 2×64B.
Pojęcie zasobów systemu oraz wzajemnej blokady i metody ochrony przed blokadą wzajemną
Jako zasoby systemu można interpretować zbiór elementów, z których system może skorzystać. W przypadku systemu komputerowego mogą to być peryferia, urządzenia bezpośrednio związane z procesorem jak pamięć lub obiekty wirtualne np. tabele w systemie bazodanowym.
Blokada wzajemna, nazywana również zakleszczeniem (ang. deadlock), polega na warunkowym dostępie do zasobów przez dwa systemy, gdzie każdy z nich jest w posiadaniu jednego z zasobów.
Przykładowo: system A posiada zasób z1 i potrzebuje zasobu z2, aby go zwolnić, natomiast system B posiada zasób z2 i potrzebuje zasobu z1, aby zwolnić z2. Powoduje to, że systemy wzajemnie oczekują na zwolnienie dzielonych przez siebie zasobów i nie wykonują
powierzonych zadań.
Do blokady wzajemnej może dojść, gdy spełnione są cztery warunki:
1. Co najmniej jeden z zasobów w systemie nie może być współdzielony,
2. Istnieją zadania, które wymagają posiadania jednego zasobu i pobrania kolejnego,
3. Zasób może zostać zwolniony tylko przez posiadacza,
4. Zadania wzajemnie na siebie oczekują (z1 na z2, …, zn na z1).
Podstawowa metoda ochrony przed blokada wzajemna jest zastosowanie odpowiedniej kolejności alokowania zasobów. Zasoby mogą być kontrolowane za pomocą specjalnych zmiennych zwanych semaforami. Semafor moze byc binarny lub zliczający, za procedury kontrolujące semafory uznaje się funkcje zwiększająca V (s) (ang. vacate) i zmniejszająca semafor P(s) (ang. procure).
Inne sposoby rozwiązywania blokady wzajemnej polegają na zastosowaniu hierarchii – bardziej znaczący proces wymusza zasoby od procesów mniej znaczących – lub arbitralnym zakończeniu zadania.
System M/M/1
M/M/1 - system kolejkowy, w którym rozkład czasu pomiędzy kolejnymi zgłoszeniami do systemu oraz rozkład czasu obsługi pojedynczego zgłoszenia są rozkładami wykładniczymi, istnieje jedno stanowisko obsługi i nieskończenie długa kolejka.
Na powyższy model składają się:
1. źródło zgłoszeń – emituje zgłoszenia i przesyła je do wykonania systemowi. Wyróżnia się dwa rodzaje źródeł:
a) źródło n wymiarowe – zawiera ściśle określoną liczbę zadań – po wyemitowaniu n zgłoszeń źródło nie generuje kolejnych (prawdopodobieństwo wygenerowania kolejnego zgłoszenia wynosi 0)
b) źródło nieskończenie wymiarowe – liczba wygenerowanych zgłoszeń nie zmienia prawdopodobieństwa pojawienia się kolejnego zgłoszenia (najczęściej spotykane)
- kolejka – uporządkowany ciąg zgłoszeń czekających na obsługę. Z każdą kolejką związany jest regulamin, który decyduje o kolejności wyboru zgłoszeń do obsługi
a) regulamin naturalny – o kolejności obsługi decyduje kolejność przybycia
b) regulamin priorytetowy - kolejność obsługi zależy od priorytetu zgłoszenia - stanowisko obsługi – charakteryzowane jest zmienną losową określającą czas obsługi jednego klienta.
System M/M/1 zbudowany jest z nieskończonego źródła, kolejki o nieograniczonej pojemności i regulaminie naturalnym oraz pojedynczego stanowiska o wykładniczym czasie obsługi.
