Maszyna RAM (random access machine – maszyna o dostępie swobodnym) jest abstrakcyjnym modelem maszyny obliczeniowej wykorzystywanym współcześnie przede wszystkim w celach dydaktycznych. Rozwiązywanie zadań na tej maszynie ćwiczy zarówno logiczne myślenie jak i jest świetnym wprowadzeniem do programowania w Asemblerze (aczkolwiek nie tylko).

Klasyczna Maszyna RAM rozpoznaje zestaw instrukcji, nazywany kodem RAM, podobny do asemblera współczesnych procesorów, co daje możliwość jej programowania tak, jakby programowało się prawdziwy komputer, ale w prostszy sposób, ukazujący istotę niskopoziomowego programowania

Jak wygląda maszyna RAM?

Maszyna RAM zbudowana jest z:
- nieograniczonej pamięci RAM
- pamięci stałej, w której przechowywany jest program
- taśmy wejściowej,
- taśmy wyjściowej,
- układów pomocniczych.

Jej dokładny wygląd nie jest sprecyzowany, pokuszę się jednak o własną interpretację graficzną:

Taśma wejściowa i taśma wyjściowa, to dwie potencjalnie nieskończone taśmy zawierające dane wejściowe i wyjściowe. Są one podzielone na komórki w których mogą znajdować się dane w postaci nieujemnych liczb naturalnych. Z taśmy wyjściowej dane można tylko odczytywać, natomiast na taśmie wyjściowej dane te można jedynie zapisywać. Po każdej operacji odczytania/zapisania głowica w taśmie wejściowej/wyjściowej przesuwana jest o jedną pozycję w prawo. W taśmie wyjściowej na początku działania programu wszystkie komórki są puste. PAMIĘTAJ! Nie można dowolnie sterować przesuwaniem głowicy na obu taśmach (ruch głowicy wykonywany jest tylko przy okazji użycie rozkazu READ lub WRITE).

Pamięć RAM składa się z nieograniczonej liczby rejestrów r. Rejestr jest nazywany akumulatorem, wszelkie obliczenia wykonywane są właśnie w nim.

Program zawiera ciąg poleceń maszyny RAM. Każda komórka programu składa się z trzech części:

- etykieta jest swego rodzaju adresem wiersza (potrzebnym w przypadku skoków, o tym za chwilę) – nie jest wymagana przy każdej instrukcji,
- operacja jest rozkazem programu wykonywane na adresie,
- adres – adres akumulatora, wartość liczbowa bądź nazwa etykiety.

Rozkazy obsługi taśmy wejściowej i taśmy wyjściowej:

W rozpatrywanym przeze mnie modelu maszyny RAM rozróżniać będziemy 12 rozkazów.

- READ a - wczytuje wartość komórki (nad którą znajduje się głowica) do rejestru a oraz przesuwa głowicę o jedną w prawo,
- WRITE a - zapisuje  w komórce (nad którą znajduje się głowica) wartość z rejestru a oraz przesuwa głowicę o jedną w prawo.

Rozkazy operacji na komórkach pamięci RAM:

- LOAD a – ładuje do akumulatora (rejestr ) wartość a. Po co ładować wartość rejestru do akumulatora? Po to, by wykonać na nim inne operacje matematyczne bądź instrukcje skoków.
- STORE a – zapisuje wartość akumulatora do rejestru a.

Operacje matematyczne:

- ADD a – do wartości w akumulatorze (rejest ) dodaje wartość a,
- SUB a – od wartości w akumulatorze odejmuje wartość a,
- MULT a – mnoży wartość w akumulatorze przez wartość a,
- DIV a – dzieli całkowicie wartość z akumulatora przez a.

Wyniki wszystkich operacji matematycznych zapisywane są w akumulatorze.
Dzielenie całkowite oznacza tyle, że jeżeli wynik działania daję liczbę z ułamkiem, to ułamek ten jest zwyczajnie odcinany. np. Działanie 5/2 daje wynik 2.

Operacje skoków:

- JUMP b dokonuje skoku to fragmentu programu oznaczonego etykietą b,
- JGTZ b porównuje liczbę znajdującą się w akumulatorze do zera. Gdy wynik jest różny od zera dokonuje skoku do etykiety b, gdy zaś wynik jest równy zero wykonuje kolejną instrukcję.
- JMPZ b, sytuacja odwrotna. Skok do etykiety b dokonywany jest, gdy wartość w akumulatorze jest równa zero. W przeciwnym wypadku wykonywana jest następna w kolejce instrukcja.
- HALT – zatrzymuje działanie programu jednocześnie go kończąc.

Oczywiście operacji może być znacznie więcej, jednak w przyjętym przeze mnie modelu posługiwać się będziemy wyłącznie powyższymi rozkazami.

Wartości operacji:

Rozróżniamy trzy sposoby zapisu wartości rozkazu:
- a - wartość w rejestrze a,
np. SUB 6 – odejmuje od wartości w akumulatorze wartość rejestru 6,
- =a – wartość a,
np. SUB =6 – odejmuje od wartości przechowywanej w akumulatorze liczbę 6,
- ^a – wartość w rejestrze którego adres przechowywany jest w rejestrze a,
np. SUB ^6 – odejmuje od wartości przechowywanej w akumulatorze wartość rejestru o numerze przechowywanym w rejestrze 6.

Wiem, że może to się wydać na razie abstrakcją, ale gdy przejdziemy do prostych programów programowanie maszyny RAM powinno być już bardziej zrozumiałe.

Złożoność czasowa i pamięciowa:

W maszynie RAM złożoność czasowa równoważna jest z ilością wykonanych operacji. Natomiast złożoność pamięciowa równa jest liczbie wykorzystanych rejestrów pamięci RAM (łącznie z akumulatorem).

Emulator maszyny RAM to program komputerowy, który naśladuje działanie maszyny RAM. Dzięki niemu możliwe jest pisanie rzeczywistych programów dla maszyny i ich uruchamianie. Emulator maszyny został wzbogacony o procesor - mózg maszyny, który odpowiada za rozpoznawanie i wykonywanie rozkazów, na kształt procesora w rzeczywistym komputerze. Ta koncepcja zgadza się z modelem rzeczywistego komputera. Jest lepiej sądzić, że właśnie procesor jest jednostką wykonującą rozkazy, niż myśleć ogólnie, iż to maszyna wykonuje rozkazy.

Doprecyzowane zostało również działanie taśm i głowic czytających/piszących - głowicę na taśmie wejściowej można przesuwać przy pomocy myszy. Taśma zawiera przyciski do przesuwania zarówno głowicy jak i samej zawartości taśmy w obie strony. Dzięki temu nie trzeba za każdym razem zmieniać danych wejściowych dla programu - wystarczy wpisać wiele danych na taśmę (lub wczytać je z pliku), a następnie, przed uruchomieniem programu, przesunąć głowicę nad wybraną komórkę taśmy, od której ma się rozpocząć czytanie.

Aby można było obserwować, jak wykonywany jest program na maszynie RAM, emulator posiada suwak, za pomocą którego można dostosować prędkość wykonywania programu - prędkość można regulować w trakcie wykonywania programu oraz gdy program jest zatrzymany. Jeśli obserwowanie działania jest dla programisty nieistotne, a interesujący jest tylko wynik działania, maszynę można uruchomić w trybie szybkim - wówczas instrukcje kodu RAM wykonywane są błyskawicznie (tzn. możliwie najszybciej).

Program dla maszyny RAM można wykonywać również krokowo, instrukcja po instrukcji, oraz spauzować i wznowić jego działanie, gdy jest uruchomiony, a także przejść z trybu krokowego na wykonanie ciągłe i odwrotnie. Emulator maszyny ma również opcję ustawiania punktów kontrolnych w kodzie RAM, dwojakiego rodzaju - bezwarunkowych i warunkowych.