Mašina sa slučajnim pristupom

U računarskim naukama, mašina sa slučajnim pristupom (RAM) je apstraktna mašina u opštoj klasi registarskih mašina. Veoma je slična brojačkoj mašini ali ima dodatnu sposobnost "indirektnog adresiranja" svojih registara. Kao i u brojačkoj mašini, instrukcije se u RAM-u nalaze u delovima konačnog stanja mašine, što predstavlja tzv. Hardvard arhitekturu.

Ekvivalent univerzalnoj Turingovoj mašini - kod koje se i program i podaci čuvaju u registrima - naziva se mašina skladišta programa sa slučajnim pristupom ili RASP. Ovo je primer takozvane fon Nojmanove arhitekture i najbliža je opštoj ideji računara. Zajedno sa Turingovom mašinom i modelima brojačke mašine, RAM i RASP se koriste za analizu računske kompleksnosti. Van Emde Boas je 1990. godine nazvao ove modele kao i pokazivačku mašinu modelima "sekvencijalne mašine", kako bi ih razlikovao od modela "mašina sa paralelnim slučajnim pristupom".

Uvod u model

Koncept mašine sa slučajnim pristupom počinje sa najjednostavnijim modelom, takozvanim modelom brojačke mašine. Međutim, dve osobine ga razlikuju od brojačke mašine. Prva je indirektno adresiranje, a druga čini da model teži ka više konvencionalnim kompjuterima baziranim na akumulatoru, koji imaju jedan ili više pomoćnih registara, od kojih se najpoznatiji naziva "akumulator".

Formalna definicija

Mašina sa slučajnim pristupom je apstraktni model računske mašine identična brojačkoj mašini sa više registara, pri čemu ima i indirektno adresiranje. Po nahođenju instrukcije iz tabele mašine, mašine uzima registarsku adresu cilja ili direktno iz same instrukcije ili indirektno iz sadržaja, npr. brojevi, oznake, pokazivača registra specificiranog u instrukciji.

Po definiciji: registar je lokacija za adresom i sadržajem. Adresa predstavlja jedinstveni lokator ekvivalentan prirodnom broju, a sadržaj je prirodni broj. Zbog preciznosti koristićemo kvazi -formalni simbolizam od Bulov-Burdžis-Džefrija 2002. godine da specificiramo registar, njegov sadržaj i operaciju nad registrom: [r] znači "sadržaj registra na adresi r". Oznaka "r" u ovom slučaju je promenljiva koja može biti prirodni broj, slovo ili ime.→ znači "kopiraj" ili "zameni", ali bez brisanja same vrednosti u izvoru.

Primer: [3] +1 → 3 znači "sadržaj izvornog registra sa adresom "3", plus 1, se stavlja u odredišni registar sa adresom "3". U ovom slučaju i izvor i destinacija su isto mesto. Ako je [3]=37, sadržaj registra 3 je broj "37", dakle 37+1=38 će biti stavljeno u registar 3.

Primer: [3]→ 5 znači "sadržaj izvornog registra sa adresom "3" se stavlja u odredišni registar sa adresom "5". Ako je [3]=38, sadržaji registra 3 je broj 38, tako da će ova operacija biti stavljena u registar 5. Sadržaj registra 3 se ne menja ovom operacijom, tako da sadržaj registra [3] ostaje 38.

Definicija: direktna instrukcija je ona koja u samoj instrukciji specificira adresu izvornog ili odredišnog registra čiji će sadržaji biti predmet instrukcije. Indirektna instrukcija je ona kao specificira "pokazivački registar", čiji je sadržaj adresa ciljnog registra. Ciljni registar može biti izvor ili odredište. Registar može indirektno sam sebe da adresira.

Definicija: Sadržaj izvornog registra se koristi od strane instrukcije. Adresa izvornog registra može biti određena direktno samom instrukcijom ili indirektno pokazivačkim registrom specificiranim instrukcijom.

Definicija: sadržaj pokazivačkog registra je adresa "ciljnog" registra.

Definicija: Sadržaj pokazivačkog registra pokazuje na ciljni registar - "cilj" mogu biti izvorni ili odredišni registar.

Definicija: odredišni registar predstavlja mesto gde instrukcija skladišti svoj rezultat. Adresa izvornog registra može biti specificirana ili direktno instrukcijom ili indirektno pokazivačkim registrom specificiranim u instrukciji. Jedan registar može istovremeno biti i izvorni i odredišni.

Model brojačke mašine

Melzak je 1961. godine napravio jednostavnu vizualizaciju brojačke mašine: njegovi registri su rupe u kojima se nalaze kamenčići. Po instrukciji, u i iz ovih rupa "kompjuter" (čovek ili mašina) dodaje ili uklanja kamenčić. Minski i Hopkrof-Ulman dodaju vizualizaciju Turingove mašine sa više traka u kojoj trake sa krajem na levoj strani čiine "registre". Registarska mašina poseduje kolekciju diskretnih i jedinstveno označenih lokacija nazvanih "registri". Ovi registri mogu da skladište samo prirodne brojeve ( nulu i pozitivne cele brojeve).

Bazni slučaj 1: model najsličniji vizualizaciji Minskog (1961): INC - inkrementirati sadržaj registra r, DEC - dekrementirati sadržaj registra r, IF - ako je sadržaj registra r 0 THEN - onda idi na instrukciju Iz ELSE - nastavi na sledeću instrukciju)

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
INCrement	INC ( r )	[r] +1 → r	[IR] +1 → IR
DECrement	DEC ( r )	[r] -1 → r	[IR] +1 → IR
Jump if Zero	JZ ( r, z )	none	IF [r1] = 0 THEN z → IR ELSE [IR] +1 → IR
Halt	H	none	[IR] → IR

Bazni slučaj 2: model "naslednik" - INC - inkrementirati sadržaj registra r, CLeaRv - obriši sadržaj registra r, IF ako je sadržaj registra rj jednak sadržaju registra rk THEN - onda pređi na instrukciju Iz ELSE pređi na narednu instrukciju.

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
CLeaR	CLR ( r )	0 → r	[IR] +1 → IR
INCrement	INC ( r )	[r] +1 → r	[IR] +1 → IR
Jump if Equal	JE (r1, r2, z)	none	IF [r1] = [r2] THEN z → IR ELSE [IR] +1 → IR
Halt	H	none	[IR] → IR

Bazni slučaj 3: korišćen od strane Elgot-Robinsona (1964) u njihovom istraživanju ograničenih i neograničenih RASP - model naslednik sa instrukcijom COPY umesto CLEAR: INC - inkrementirati sadržaj registra r, COPY - kopirati sadržaj registra rj u registar rk, IF - ako je sadržaj registra rj jednak sadržaju registra rk onda pređi na instrukciju Iz ELSE pređi na narednu instrukciju.

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
COPY	COPY (r1, r2)	r1 → r2	[IR] +1 → IR
INCrement	INC ( r )	[r] +1 → r	[IR] +1 → IR
Jump if Equal	JE (r1, r2, z)	none	IF [r1] = [r2] THEN z → IR ELSE [IR] +1 → IR
Halt	H	none	[IR] → IR

Spoljašnje veze