21

Operaˇ cn´ı syst´ emy

´ Uvod do Operaˇ cn´ıch Syst´ em˚ u Petr Krajˇca

Katedra informatiky Univerzita Palack´eho v Olomouci

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

1 / 21

Organizaˇcn´ı informace email: [email protected] konzultaˇcn´ı hodiny stˇreda 15:00 – 16:00 p´atek 10:00 – 11:00

www: http://phoenix.inf.upol.cz/~krajca/ slidy budou k dispozici online

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

2 / 21

Pr˚ ubˇeh v´yuky pˇredn´aˇsky u ´koly souvisej´ıc´ı s prob´ıranou t´ematikou nen´ı potˇreba vyˇreˇsit zadan´e u ´koly (urˇcen´e k pochopen´ı prob´ıran´e l´atky) samostudium; do pˇr´ıˇstˇe: Keprt A. Operaˇcn´ı syst´emy. 2008. Kapitoly 1–5.3.5, tj. strany 9–48. Keprt A. Assembler. 2008. Kapitoly 1–5.1, tj. strany 6–53.

skripta jsou na webu katedry (sekce studium) dotazy a konzultace

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

3 / 21

Literatura Keprt A. Operaˇcn´ı syst´emy. 2008 Keprt A. Assembler. 2008 Silberschatz A., Galvin P.B., Gagne G. Operating System Concepts, 7th Edition. John Wiley & sons, 2005. ISBN 0-471-69466-5. Tanenbaum A.S. Modern Operating Systems, 2nd ed. Prentice-Hall, 2001. ISBN 0-13-031358-0. Stallings, W. Operating System Internals and Design Principles, Fifth Edition. Prentice Hall, 2004. ISBN 0-13-127837-1. Solomon D.A., Russinovich M. E. Windows Internals: Covering Windows Server 2008 and Windows Vista. Microsoft Press, 2009. ISBN 0735625301. Jel´ınek L. J´adro syst´emu Linux: kompletn´ı pr˚ uvodce program´atora. Brno, Computer Press, 2008.

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

4 / 21

Architektura poˇc´ıtaˇce John von Neumannova architektura CPU (ALU, ˇradiˇ c) pamˇet’ spoleˇ cn´ a pro program i data (vs. harvardsk´a architektura) vstup/v´ystup sbˇernice (ˇr´ıd´ıc´ı, adresn´ı, datov´a) instrukce procesoru jsou zpracov´av´any v ˇradˇe za sebou (nen´ı-li uvedeno jinak) OS jako abstrakce HW vyv´ıjet software na m´ıru jednoho HW n´aroˇcn´e/neefektivn´ı (obvykle); hardware je neuvˇeˇritelnˇe sloˇzit´y operaˇcn´ı syst´em + jazyky vyˇsˇs´ı u ´rovnˇe poskytuj´ı potˇrebnou abstrakci operaˇcn´ı syst´em – rozhran´ı mezi HW a SW v koneˇcn´em d˚ usledku nˇekolik u ´rovn´ı abstrakce

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

5 / 21

Operaˇcn´ı syst´em Vrstvy poˇ c. syst´ emu 1

hardware

2

operaˇcn´ı syst´em (OS)

3

standardn´ı knihovna (libc, CRT)

4

syst´emov´e n´astroje

5

aplikace hranice mezi posledn´ımi tˇremi vrstvami nemus´ı b´yt ostr´e operaˇcn´ı syst´em zajiˇst’uje spr´avu zdroj˚ u (sd´ılen´y pˇr´ıstup k pamˇeti, zaˇr´ızen´ım, . . . ) z ˇcasov´ych d˚ uvodu se omez´ıme jen na OS pro PC, kter´e jsou zaloˇzen´e na architektuˇre Intel x86

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

6 / 21

CPU (1/2) Obecn´ a struktura CPU Aritmeticko-logick´a jednotka (ALU) – prov´ad´ı v´ypoˇcty ˇr´ıd´ıc´ı jednotka – ˇr´ıd´ı chod CPU registry – slouˇz´ı k uchov´an´ı pr´avˇe zpracov´avan´ych dat (n´asobnˇe rychlejˇs´ı pˇr´ıstup neˇz do pamˇeti); speci´aln´ı registry obsluhuj´ıc´ı chod CPU: IP (instruction pointer), FLAGS, IR (instruction register), SP (stack pointer) Instrukˇ cn´ı sada (ISA) sada instrukc´ı ovl´adaj´ıc´ı procesor (specifick´a pro dan´y CPU/rodinu CPU) instrukce a jejich operandy jsou reprezentov´any jako ˇc´ısla =⇒ strojov´y k´od kaˇzd´a instrukce m´a obvykle 0 aˇz 3 operandy (m˚ uˇze to b´yt registr, konstanta nebo m´ısto v pamˇeti) pro snazˇs´ı porozumˇen´ı se instrukce CPU zapisuj´ı v jazyce symbolick´ych adres (assembleru)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

7 / 21

V´ypoˇcet faktori´alu: Intel x86

00000000 0: 8b 4: b8 9: 83 c: 0f 12: f7 14: 83 17: e9 1c: c3

<main>: 4c 24 04 01 00 00 00 f9 00 8e 0a 00 00 00 e9 e9 01 ed ff ff ff

Petr Krajˇ ca (UP)

mov mov cmp jle imul sub jmp ret

ecx,DWORD PTR [esp+0x4] eax,0x1 ecx,0x0 1c <main+0x1c> ecx ecx,0x1 9 <main+0x9>

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

8 / 21

V´ypoˇcet faktori´alu: Sparc V8 00000000 <main>: 0: 9d e3 bf 4: a0 10 20 8: 80 a6 00 c: 04 80 00 10: 01 00 00 14: a0 5c 00 18: b0 26 20 1c: 10 bf ff 20: 01 00 00 24: b0 10 00 28: 81 c7 e0 2c: 81 e8 20

Petr Krajˇ ca (UP)

88 01 00 06 00 18 01 fb 00 10 08 00

save %sp, -120, %sp mov 1, %l0 cmp %i0, %g0 ble 24 <main+0x24> nop smul %l0, %i0, %l0 dec %i0 b 8 <main+0x8> nop mov %l0, %i0 ret restore

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

9 / 21

CPU (2/2) instrukce jsou zpracov´av´any v nˇekolika kroc´ıch: 1

naˇcten´ı instrukce do CPU (Fetch)

2

dek´odov´an´ı instrukce (Decode)

3

v´ypoˇcet adres operand˚ u

4

pˇresun operand˚ u do CPU

5

proveden´ı operace (Execute)

6

uloˇzen´ı v´ysledku (Write-back) pipelining – umoˇzn ˇuje zv´yˇsit efektivitu CPU je potˇreba zajistit spr´avn´e poˇrad´ı operac´ı procesor m˚ uˇze m´ıt v´ıc jednotek napˇr. pro v´ypoˇcty (FPU, ALU) probl´em s podm´ınˇen´ymi skoky (branch prediction)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

10 / 21

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

11 / 21

Intel x86: Registry (1/2) registry jsou 32bitov´e obecnˇe pouˇziteln´e (i kdyˇz existuj´ı urˇcit´e konvence, jak by se mˇeli pouˇz´ıvat) EAX (Accumulator) – stˇradaˇc pro n´asoben´ı a dˇelen´ı, vstupnˇe-v´ystupn´ı operace EBX (Base) – nepˇr´ım´a adresace pamˇeti ECX (Counter) – poˇcitadlo pˇri cyklech, posuvech a rotac´ıch EDX (Data)

kaˇzd´y registr m´a svou spodn´ı 16bitovou ˇc´ast reprezentovanou jako regist AX, BX, CX, DX tyto 16 bitov´e registr lze rozdˇelit na dvˇe 8bitov´e ˇc´asti reprezentovan´e jako AH, AL, BH, BL, . . .

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

12 / 21

Intel x86: Registry (2/2) Dalˇs´ı registry EDI (Destination Index) – adresa c´ıle ESI (Source Index) – adresa zdroje EBP (Base Pointer) – adresace parametr˚ u funkc´ı a lok´aln´ıch promˇenn´ych ESP (Stack Pointer) – ukazatel na vrchol z´asobn´ıku (adresa vrcholu z´asobn´ıku) EIP (Instruction Pointer) – ukazatel na aktu´aln´ı m´ısto v programu, adresa instrukce n´asleduj´ıc´ı za pr´avˇe prov´adˇenou instrukc´ı, nen´ı moˇzn´e jej pˇr´ımo mˇenit (jen patˇriˇcn´ymi instrukcemi) EF(LAGS) – pˇr´ıznaky nastaven´e pr´avˇe probˇehlou instrukc´ı spodn´ıch 16 bit˚ u tˇechto registr˚ u lze adresovat pomoc´ı registr˚ u DI, SI, BP, SP, IP, F(LAGS); dalˇs´ı dˇelen´ı nen´ı moˇzn´e ESI a EDI jde pouˇz´ıvat jako obecnˇe pouˇziteln´e zmˇeny v registrech EBP, ESP by mˇely b´yt uv´aˇzen´e Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

13 / 21

Intel x86: Operace (1/2) operandy instrukc´ı mohou b´yt r – registry m – pamˇet’ i – hodnoty

pamˇet lze v jedn´e instrukci adresovat pouze jednou MOV r/m, r/m/i ADD r/m, r/m/i SUB r/m, r/m/i NEG r/m MUL r/m IMUL r, r/m IMUL r, r/m, i

; ; ; ; ; ; ;

op1 := op2 op1 := op1 + op2 op1 := op1 - op2 op1 := - op1 EDX:EAX := EAX * op1 op1 := op1 * op2 op1 := op1 * op2 * op3

OR r/m, r/m/i AND r/m, r/m/i XOR r/m, r/m/i NOT r/m

; ; ; ;

op1 op1 op1 op1

Petr Krajˇ ca (UP)

:= := := :=

op1 | op2 op1 & op2 op1 ^ op2 ~op1 KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

14 / 21

Pˇr´ıklady ; do registru EAX ulozi obsah EBX mov eax, ebx ; prevrati spodnich 16 bitu v registru ECX xor ecx, 0x0000ffff ; pricte k registru cx hodnotu registru si add cx, si ; takto nejde -- nesedi velikosti registru add ecx, si ; vyneguje obsah registru edx neg edx

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

15 / 21

Intel x86: Operace (2/2) SHL SAL SHR SAR ROL ROR

r/m, r/m, r/m, r/m, r/m, r/m,

INC r/m DEC r/m

i i i i i i

; ; ; ; ; ;

op1 := op1 := op1 := op1 := rotace rotace

op1 << op2 (bez znam´ enkov´ a operace) op1 << op2 (znam´ enkov´ a operace) op1 >> op2 (bez znam´ enkov´ a operace) op1 >> op2 (znam´ enkov´ a operace) bit˚ u doleva bit˚ u doprava

; op1 := op1 + 1 ; op1 := op1 - 1

m´ısto okamˇzit´e hodnoty (konstanty) lze pouˇz´ıt registr CL jednotliv´e operace nastavuj´ı hodnoty jednotliv´ych bit˚ u v registru EF mj. obsahuje pˇr´ıznaky SF (sign flag) – podle toho jestli v´ysledek je kladn´y nebo z´aporn´y ZF (zero flag) – v´ysledek byl nula CF (carry flag) – pokud pˇri operaci doˇslo k pˇrenosu mezi ˇr´ady OF (overflow flag) – pˇr´ıznak pˇreteˇcen´ı Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

16 / 21

Intel x86: Bˇeh programu, podm´ınˇen´e skoky a porovn´an´ı program zpracov´av´a jednu instrukci za druhou (pokud nen´ı uvedeno jinak) =⇒ skok nepodm´ınˇen´y skok operace JMP r/m/i – ekvivalent GOTO (pouˇzit´ı pˇri implementaci smyˇcek)

nen´ı pˇr´ıtomn´a operace ekvivalentn´ı if podm´ınˇen´y skok je operace ve tvaru Jcc, provede skok na m´ısto v programu, pokud jsou nastaveny pˇr´ısluˇsn´e pˇr´ıznaky napˇr. JZ i (provede skok, pokud v´ysledek pˇredchoz´ı operace byl nula) srovn´an´ı ˇc´ısel jako rozd´ıl (operace CMP r/m, r/m/i, je jako SUB, ale neprov´ad´ı pˇriˇrazen´ı JE skok pˇri rovnosti, JNE, pˇri nerovnosti skoky po porovn´an´ı znam´enkov´ych ˇc´ısel JG (>), JGE (≥), JL (<), JLE (≤) skoky po porovn´an´ı bezznam´enkov´ych ˇc´ısel JA (>), JAE (≥), JB (<), JBE (≤)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

17 / 21

Pˇr´ıklad

; porovnej eax s hodnotou 10 cmp eax, 10 ; pokud je eax vetsi nez 10 ; provede skok na adresu foo jg foo ... ; jinak pokracuje timto kodem ... foo: ...

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

18 / 21

Adresace pamˇeti pˇr´ım´a adresa – ukazuje na m´ısto v pamˇeti nepˇr´ım´a adresa – pˇred pˇreˇcten´ım hodnoty se vypoˇc´ıt´a z hodnot registr˚ u podle vzorce: adresa = posunuti + baze + index × f actor posunut´ı je konstanta b´aze a index jsou registry factor je ˇc´ıslo 1, 2, 4, nebo 8 kteroukoliv ˇc´ast vzorce lze vypustit v assembleru se ˇcten´ı/z´apis do pamˇeti zapisuje pomoc´ı [ ... ] mov eax, [ebx + 10] mov [eax + esi * 2 + 100], bx je dobr´e doplnit velikost zapisovan´ych dat mov eax, dword ptr [ebx + 10] mov word ptr [eax + esi * 2 + 100], bx mov word ptr [eax + esi * 2 + 100], 42 !!! pˇri pˇr´ıstupu k promˇenn´ym ve VS (jsou adresy doplnˇeny automaticky) Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

19 / 21

Vztah adresace pamˇeti procesoru a jazyka C 1

2

3

Dereference mov eax, dword ptr [ebx] ;; eax := *ebx Pole short a[] = malloc(sizeof(short) * 10); _asm { mov ebx, a mov ax, [ebx + esi * 2] ;; ax := a[esi] } Strukturovan´ e hodnoty struct foo { int x; int y; int z[10]; }; struct foo * a = malloc(sizeof(struct foo)); _asm { mov ebx, a mov [ebx], ecx ;; a->x := ecx mov [ebx + 4], ecx ;; a->y := ecx mov [ebx + esi * 4 + 8], ecx ;; a->z[esi] := ecx } Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

20 / 21

CISC a RISC Complex Instruction Set Computer x86 m´a architekturu CISC sloˇzitˇejˇs´ı instrukce (dovedou v´ıc vˇec´ı, adresovat pamˇet’, atd.), n´aroˇcn´e na zpracov´an´ı snazˇs´ı tvoˇrit program (je kratˇs´ı) menˇs´ı poˇcet registr˚ u, instrukce nejsou ortogon´aln´ı Reduced Instruction Set Computer vˇetˇs´ı poˇcet registr˚ u, jednoduch´e instrukce, schopn´e zajistit stejnou funkcionalitu samostatn´e instrukce pro pˇr´ıstup k pamˇeti jedna instrukce dˇel´a v´ıc vˇec´ı pˇr´ıklady pro SPARC (vyuˇz´ıv´a registr g0, kter´y je vˇzdy nula) subcc %r1, %r2, %r3 subcc %r1, %r2, %g0 or %g0, 123, %r1 Petr Krajˇ ca (UP)

; r3 := r1 - r2 ; g0 := r1 - r2 ; r1 := g0 | 123

(cmp r1, r2) (mov r1, 123)

KMI/YOS: Pˇredn´ aˇska I.

10. 10. 2014

21 / 21