Návrat na detail prednášky / Stiahnuť prednášku / Univerzita Komenského / Fakulta matematiky, fyziky a informatiky / Princípy PC

Poznamky (poznamky_full.doc)

Úvod do operačných systémov

Úrovne počítača

Operačný systém

1. jeho služby : otváranie, zatváranie, vytváranie súborov, procesov, posielanie dát, kreslenie, ....
2. 4 zákl. časti – správa procesov, pamäte, I/O zariadení, súborov
3. proces = bežiaci program
4. stavová informácia zahŕňa premenné & históriu volania procedúr pre otvorené súbory v konkrétnom čase
5. správa súborov – abstrakcia sektorov na súbory
6. vzniká ako rozšírenie strojového kódu s novými inštrukciami pre zjednodušenie práce s I/O zariadeniami
7. MS-DOS – 2-rozmerné pole znakov na adresu <=> Windows – virtualizácia – spúšťa aj DOS programy

Vyšší programovací jazyk

1. nie je viazaný na konkrétny HW
2. prekladá do strojového kódu, volá knižnice //v niektorých možno použiť priamo assembler
3. aplikačné programy

Programovacie jazyky

najskôr málo zrozumiteľné pre používateľov, bližšie procesoru => nové jazyky boli kvôli HW prekladané do viac userfriendly jazykov

vrstvenie jazykov

kompilácia

kompilácia

interpreter

INTERPRETER

1. vstupom je program v danom jazyku – výstupom je konkrétny výsledok – vykonanie programu
2. HW interpreter = číslicové obvody = interpreter mikroprogramu
3. I diagram

KOPILÁTOR – prekladá, vstup aj výstup je konkrétny jazyk, T diagram

Interpreter        HW interpterer        Kompilátor

Kompilácia pascalu v pascale

Vývoj programovacích jazykov

1.  1951  M. V. Wilkes – pridal k počítaču mikroprogram medzi číslicové obvody a strojový kód => zjednodušenie, väčšia flexibilita, zlacnenie, spomalenie

1. n-bitový procesor = n-bitová dátová zbernica, aritmetika, registre // slovo = n bitov
2. predný panel 1k-bit PC s 2 registrami, 8-ková sústava => HW rieši programátor
3. zárodok OS – knižnice na prácu s I/O zariadeniami
4. zloženie:

vyšší programovací jazyk – Fortran (IBM) //formula translation

assembler

zárodok OS – podpora behu

HW

1. mid 50’s - počítač využíva jeden človek, viac manuálna obsluha – výmena diernych štítkov

Pascal             P-Kód                Pascal    P-Kód                        

       Pascal     Pascal     P-Kód  Pascal

                              Pascal             P-Kód

                                                       CDC

                              Pascal        

                              -človek-           CDC

P-Kód

CDC

6600

       P-Kód                          P-Kód

      Fortran   Fortran       CDC   CDC

                                CDC

                      CDC

2. dierne štítky

1. 80 stĺpcov / 12 dierok – 1 riadok = 80 znakov
2. 1 štítok = 1 riadok programu
3. BATCH processing // dávkové spracovanie
4. JCL – job control language
5. príklad programu

                 *JOB  meno    => jazyk OS

                *FORTRAN

                       ~ ~ ~ ~      => vyšší programovací jazyk

      ~ ~ ~ ~

                        *END

                        *RUN

                       ~ ~ ~ ~ dáta     => jazyk programu

      ~ ~ ~ ~ dáta

                        *RUN

                       ~ ~ ~ ~

      ~ ~ ~ ~

*END

1. rozdiel medzi HW a SW nie je jasný, vlastnosti v rôznych vrstvách nie sú jednoznačne dané k vrstve // HW a SW sú logicky ekvivalentné

História počítačov a OS

0. Prehistória (stroje)

17. stor.

1. Pascal – Pascalína (1641) – sčítanie šesťmiestnych čísel
2. Gotfried Wilhelm Leibniz (1647) – počítací stroj stupňovými valcami pre 4 základné aritmetické operácie, zaoberá sa aj dvojkovou reprezentáciou čísel

19. stor.

3. Charles Babbage

– „Different Engine“ (1822) – opakované výpočty 1 polynómu / diferenčná metóda

– „Analytical Engine“ (1838) – vstup aj výstup – predchodcovia diernych štítkov; 4 časti: pamäť, procesor, I/O

20. stor.

1. Konrad Zuse – elektromechanická kalkulačka – obsahuje relé, zobrazenia v binárnej sústave
2. 1943 angličan Turinn – počítač Colosus (tajný) – dešifrovanie nemeckých správ
3. 1944: Howard H. Aiken – Mark 1 – prvý americký počítač

1. Generácia

1945 – 55

1. 1946: P. Eckert a J. W. Mauchly – ENIAC – prvý čisto elektronický počítač z elektrónok a relé
2. Von Neuman (1946 – 1952)  – EDSAC

2. model počítača s uloženým programom => program = forma dát, inštruk.
3. základná schéma počítača // procesor, pamäť, zbernica, I/O

3. okolo 1950 sa objavujú dierne štítky
4.  všetko sálové počítače

2. Generácia

1955 – 65

1. objavuje sa transistor (1956)
2. počítače sa dostávajú do veľkých firiem
3. rozvoj OS – BATCH system
4. binárna aritmetika
5. použitie počítačov – vedecko-technické výpočty a ekonomické výpočty (hromadné spracovanie dát)
6. BCD – rýchlejšie I/O operácie //4 bity = 1 cifra
7. čítanie z diernych štítkov, zápis na magnetické pásky
8. stále sálové počítače – filozofia: počítač je drahý – treba ho urobiť tak, aby stále počítal, max. využitie

3. Generácia

1965 – 80

1.  integrované obvody
2.  stále sálové počítače – multiprocessing / multiprogramming
3.  IBM 360 – OS 360, IBM 370
4.  ZSSR kópia (menej spoľahlivá) – J SEP – EC 1020, 1050  // J SEP = jednotný systém
5.  time sharing – komunikácia s úlohou cez terminál
6.  multics (na prelome 60-70’s) – projekt, kde jeden počítač obsluhuje tisíce terminálov, minul sa vývoju

Minipočítač

4. nová kategória počítačov
5. nepotrebuje výpočtové stredisko
6. monoprograming (žiaden multiprogramming)
7. Dec PDP 1, Dec PDP 7, Dec PDP 11
8. ZSSR kópia – SMEP CM, SM (systém malých elektronických počítačov)
9. operačný systém unics – protipól multicsu, väčšina kódu v jaz. C //unix

4. Generácia

7.  mikroprocesor – processor počítača integrovaný do 1 čipu, unifikácia procesorov
8. 1971 intel 4004
9. mikropočítač – pre jedného užívateľa
10. sieťové OS
11.  CP/M – INTEL 8080

                DOS – diskový OS, základný I/O systém

                BIOS – (?) podprogr. na výpis znaku na obraz, prečítaný sektor z diskety

1.  1987 INTEL 8086; 1980 INTEL 8088 – 16 bitové
2.  8-palcové diskety, max 1MB, 5 ¼ palcové diskety
3.  1981 IBM PC – procesor 8086/88, zverejnené všetky, popisy zbernice
4.  1983/4 – IBM PC AT 80286

IBM PS2 – personal system 2 (neujal sa)

IBM OS/2

1.  mikropočítač – rôznorodé programy pre rôzne počítače – posudzovanie noriem PC – nie noriem programov ako v minulosti

Úroveň konvenčného počítača

//programovací jazyk – strojový kód – špecifický pre procesor intel, kompatibilita na tejto úrovni s 8386

procesor intel pentium

register = pamäťové miesto v procesore //32 bit procesor => 32 bitový adresový priestor

//286 – 16kbit procesor, 24 bit adresová zbernica, 8086 – 16kbit procesor, 20 bit adresová zbernica

2 byte = WORD, 4B = DWORD, 8B = QWORD

znamienkové operácie

2. príklad rozdelenia čísel na znamienk. a neznam.

mod 5                0 1 2   3  4         //2 + 4 = 1, 2 + 3 = 0, 1 + 4 = 0  4 = -1, 3 = -2

                        0 1 2 -2 -1

3.  násobenie -1

256 = 1 0000 0000

 +5       0000 0101

         0 1111 1011

 –5  1111 1011 + 0000 0001 = 1111 1011

4.  všetky operácie - +, –, *, / zložené zo sčítania a násobenia –1
5. 1 byte – čísla 0..255 bez znamienka – so znamienkom čísla od –128 po +127 //podobne pri word, dword, qword

čísla

1. single: 4B
2. double: 8B
3. extended: 10B
4. real = double
5. real 48 //nezodpovedá ničomu na úrovni procesora – pomalšia aritmetika

Vývoj operácií / procesory

1. 8080 – len +
2. 8086 – bez reálnych čísel
3. 8086 + 8087 – reálne čísla z koprocesoru pre reálne čísla
4. 286 a 287
5. 386 a 387
6. 486 – integrovaný koprocesor, násobenie bez koprocesoru

FPV – aritmetická jednotka pre reálne čísla (+,-,*,/,log,....)

celé čísla v Pascale

neznamienkové        1B = = BYTE

2B = = WORD

4B = = LONGWORD

znamienkové                1B = = SHORTINT

                        2B = = SMALLINT

                        4B = = LONGINT

                        8B = = INT 64

                                INTEGER – generický, celé čísla so znamienkom

                                CARDINAL – kladné čísla

1. kvôli riziku pretečenia a kvôli výstupu je nutné zadať, či je operácia znamienková/ neznam., nerovnosť 2 čísel, násobenie
2. Porovnávanie 2 čísel – kompilácia na int 64

4B = = smerník / adresa; uložený / daný + nasledovné 3 adresy

LITTLE ENDIAN (intel)  najmenší bit v najväčšej adrese

BIG ENDIAN (motorola v mac, IBM 360)  najmenší bit v najmenšej adrese

problém v komunikácii viacerých procesorov  sieťové protokoly

Registre

1.  staré PC – 1 akumulátor (register) a pamäte – – neskôr viac registrov
2.  intel – rôzne typy registrov
3.  ľavá skupina registra – zameniteľná
4.  8 x 32 bit registre – – väčšinou rovnocenné / operácie výlučne na daný register
5.  8086 – AX, BX, CX, DX, SI, DI, BP, SP
6.  8 bit operand – – AH,AL, BH, ... DL
7.  16 bit operand – – AX, BX, ....
8. 6 x 16 segmentových registrov
9. 8086 = 16 bit dát + 20 bit adresové zbernice

SP = stack pointer

smerník na vrch zásobníka

na začiatku ukazuje do zásobníka / vrch prázdny

volania podprogramov

EIP – ukazuje na miesto, kde sa vykonáva program

CS = kódový segment

segmentový register, ukazuje na začiatok programu

všetky adresy budú relatívne k CS

ES = extra segment

môže pracovať s dátami, ktoré sú od seba ďalej ako 64kB

DS         1 3 D 2 0

adresa     A 3 7 0   posunutie o 4  // 1 D E 9  0 – skutočná 20bit adresa

1.  ofset = posunutie
2.  segmenty musia začínať na číslach deliteľných 16
3.   Win 3.1 – 16 bit  Pentium – segmenty – reálny režim
4.  chránený režim – segment a ofsetová časť, ale nesčítavajú sa priamo
5.  segmentové registre majú stále význam  32 bit Win – všetky adresy 32 bit, ukázané len v rámci segmentu, každý proces = 1 segment  zjednorozmernenie

Register EFLAGS

1.  register príznakov
2.  32 bitov
3.  obsahuje vedľajšie výsledky aritmetických operácií, nastavenia procesora, prepínače

CF

ZF

OF

SF

IF

CF = = carry flag – v beznamienkových operáciách – – pretečenie; prenos o mínus n-bit

ZF = = zero flag (ak výsledok = 0)

OF = = pretečenie znamienkovo – zlý výsledok

SF = = znamienkový bit

IF = = prerušenie = mechanizmus ako môže reagovať na komunikáciu v reálnom čase, napr. vstup z klávesnice; nevykonáva ďalšiu inštrukciu, ale podprogram a vráti sa asynchrónne prerušenie; zakázanie – 0 = IF, potvrdenie – 1 = IF

12 – 13 bit = IOPL – oprávnenie 0, 1, 2, 3 – I/O operácia vykonaná len s oprávnením väčším než je dané

Procesor Pentium

1. 32 bitový – fyzický adresový priestor = 46 B
2. adresa = SELECTOR//segment + OFFSET
3. reálny režim – adresovanie                SEGMENTOR_0 0 0 0

                                                __ OFFSET___

                                                ///////////////////////////////// spolu 20 bit

1.  CS: [1305] – určenie segmentu 1305ho bytu v časti pamäte, obsah registra sa použije ako selektor
2.  2-rozmerné adresovanie v chránenom režime zachováva 2 časti adresy

                selector            offset  

                _____3 2 1 0 | ___1 3 5 0__

3.  selector – vyberá TAB – globálna GDT / lokálna LDT = = pole popisovačov segmentov
4.  register GDTL – začiatok GDT, LDTL – začiatok LDT
5.  selector = jeden zo 6 určených registrov
6.  v CS – selector je program, ktorý sa práve vykonáva
7.  CS: EIP – vykonáva inštrukciu
8.  SS: ESP – vrchol zásobníka
9.  DS – dátový segment
10.  v každom deskriptore je bit p – – p=1 / p=0 – nie je v pamäti segmentu, nájde na disku, zmení údaje na 1, pokračuje

Flat memory model

1.  jednorozmerný
2.  OS nastavuje segmentový register, každý program sa pohybuje vo svojom segmente a má 64 B virtuálnej pamäte – OS vie o existujúcich častiach pamäte
3.  pamäť procesoru je 1 segment – adresovanie len offsetom, adresovanie 46 B
4.  nespojité časti

Inštrukcie procesoru Pentium

MOV

MOV EAX, 1  prenesie zdroj. operand do cieľového

        OPERANDY – register, priama hodnota, adresa do pamäte, v pamäti zväčša 1 operand

MOV [2806], EBX – na pozíciu 2806 – 2809 uloží 4B z EBX – nemožno ukladať pozíciu na pozíciu!! //[..]

MOV EAX, [3200]          priradenie, [3200] = offset (priama adresa) do virtuálnej pamäte

MOV [2806], EAX         

MOV EAX, [EBX] – uloží obsah EBX na adresu v EAX

MOV [EAX],[EBX] – vloží obsah EBX do obsahu EAX

polia, recordy, smerníky nemožno adresovať priamo

x: array[1..10] of integer         //40B

adr (x[i]) = adr (x) + (i-1)*4

x[i] := 25                        

  MOV EAX, [20500]

MOV [        ], 25 = MOV [10000 + (EAX-1)*4], 25 = MOV [10000 + EAX*4 – 4], 25 =

MOV [9996 + EAX*4], 25        

najzložitejšie adresovanie

MOV [EAX + EBX*4 + 20000]

MOV EAX, EDX

ADD EAX, EBX

ADD EAX, 1

INC EAX

INC [EAX + 5000]  ZLEE  INC DWORD PTR [EAX + 5000]

ADD [2305], EBX

operandy – 1, 2, 4 byte – nemožno krížiť rôzne veľkosti operandov

x: DB 4 – vynechá 4B + premenuje na x

MOV EAX, X        [3205]

oblasť, v ktorej je program a oblasť v ktorej sú premenné – – VPY, ASM, OS, SK

ADD, SUB, SBB, ADC                        //VŠETKO NA PAPIERI

ADD EBX, EDX

ADC EAX, ECX  + prenos z predošlej operácie, nastaví CF

MUL [3210]  treba nastaviť dĺžku

DIV, IDIV – hlási chybu pri delení nulou – – pretečený výsledok

Vetvenie programu

nepodmienený skok JMP @1

podmienené skoky

i: integer;

while i<10 do

   i:=i+1;

@2: MOV EAX, I

   CMP EAX, 10

   JGE @1

   INC I

   JMP @2

   @1:

KONZOLOVÁ APLIKÁCIA

var x,i: integer;

begin

 x:=1;

 i:=1;

 while x<4 do begin

   i:=2*I;

   x:=x+1;

 end;

end;

//zbehne 3x, i=2³

ODD(x) – true pre nepárne čísla // najnižší bit = 1

ROTÁCIE

ROL EAX,1

function Pocet1(x: cardinal):byte;

asm

 push ebx

 mov ebx,x

 @2: rol ebx,1

     jnc @1

     inc a1

 @1: loop @2

 pop ebx

end;

**********************************

AND AL,7 = = AL:=AL AND 7 //MASKA

MOV AL,0

TEST EAX,127

JZ @1

MOV AL,1

@1:

 program sko49 na 1 ak 7 najnižších bitov EAX = 0, tak AL = 1

127: 00000001111111

************************************

TYPE BIT4 = 0..15

FUNCTION ZLOZ2(A,B: BIT4):BYTE

begin

 Result:=A*16+B;

end;

MOV AL,[A]

SHL AL,4  pretečie do CF – SAR

OR AL,[B]

********************************

PUSH EAX

PUSH [X]

EBX a EDX musia mať rovnakú hodnotu ako na začiatku

********************************

Function POLET1(x: cardinal):byte;

ASM

 PUSH EBX

 MOV EBX,EAX

 MOV AL,0

 MOV ECX,32

@2: SHR RBX,1

   JMC @1

   INC AL

@1: LOOP @2

 POP EBX

END;

//program ráta počet 1 v čísle

 MOV EDX,EAX

 MOV AL,0

@2: SHR EDX,1

   JMC @1

   INC AL

@1 LOOP @2

*********************************

Function PALINDROM(x: byte):Boolean;

IF AL<>BL THEN

 AL:=0

ELSE

 AL:=1;

 RESULT:=AL=BL

ASM

PUSH ECX

OBRAT

CMP AL, BL

JE @1

MOV AL,0

JMP @2

@1 MOV AL,1

@2 POP ECX

END;

Function OBRAT(x: byte):byte;

ASM

 PUSH EBI

 MOV BL,AL

 MOV ELX,8

@1 SHR BL,1

 LCL AL,1

 LOOP @1

 POP EBX

END;

Plánovanie ROUND ROBIN = každý program dostane rovnaký objem času, opak – PRIORITNÉ PLÁNOVANIE

Správa procesov v preemptívnom OS

Princíp: plánovač procesov – dostáva sa „k slovu“ keď časovač spôsobí prerušenie

Podmienky na reálne plánovanie

1. efektívnosť (čo najvyššia)
2. férovosť //subjektívne hodnotenie
3. čas odozvy – čo najmenší
4. doba obrátky – čo najmenšia
5. priepustnosť – čo najvyššia

Prioritné plánovanie

priorita:

1. terminal kvantum
2. I/O
3. short kvantum
4. long kvantum

2 priority

1. statická – musí sa meniť explicitne, počiatočná priorita
2. dynamická – podľa nej sa plánuje, pravidlá zmien priorít s časom – zmenšuje sa s časom stráveným v stave bežiacom

CIEĽ – rozlíšiť úlohy

typy úloh:

1. veľké kvantá, menej často
2. častejšie, menšie kvantá

História

bolo nutné k úlohe zadať aj čas, koľko bude trvať

A – 8  &  B, C, D – 4

ak idú v poradí A B C D – priemerný čas obrátky je 8 + 12 + 16 + 20 / 4, čiže 14 //program D má čas 20 aj keď sa vykonával len 4 a čaká 16

ak idú v poradí B C D A – priemerný čas je 11 //čaká sa menej

 shortest job – vyberie sa najlepšia priemerná doba obrátky úloh zadaných v čase 0

životný cyklus interaktívnej aplikácie – stavy bežiaci a čakajúci

Policy driven

uprednostňujú sa procesy, ktoré minuli najmenej času a majú najnižší možný termín

 dvojúrovňové plánovanie

Komunikácia medzi procesmi //typy procesov

1. ak je proces samostatný nie je viazaný na ostatné a je si vedomý, že beží spolu s inými, ale aktívne nevyužíva  
2. proces komunikujúci

Race condition // časová závislosť

nastáva vtedy keď výsledok 2 a viac procesov sa líši v závislosti od poradia, v akom boli plánované.

Rovnaký kód – rôzne výsledky kvôli poradiu  problém v dátovej štruktúre.

Pravidlo konzistencie zdieľaných údajov – race condition – prerušenie behu programu na nekonzistentnom mieste – kritická sekcia – úsek programu, ktorý pracuje so zdieľanými dátami a to tak, že na začiatku a konci úseku sú dáta konzistentné a v strede úseku nie

riešenie problému časovej závislosti: Mutual exception // vzájomné vylúčenie

Mutual exception // vzájomné vylúčenie

Podmienky pre dobré riešenie vzájomného vylúčenia

1. keď sa žiadne dva procesy sa neocitnú vo svojej kritickej sekcii naraz
2. nepredpokladáme nič o vzájomnej rýchlosti ani o počte procesov
3. žiaden proces nesmie brániť ostatným procesom dostať sa do svojej kritickej sekcie, pokiaľ v nej práve nie je
4. férovosť – žiaden proces nebude „dlho“ čakať na vstup do kritickej sekcie
5. základný predpoklad všetkých riešení – kritická sekcia sa vykoná v konečnom (krátkom) čase

Typy riešení

1. s aktívnym čakaním – busy waiting

1. spotrebúva sa čas, testuje sa podmienka, ktorá sa nemôže počas behu zmeniť
2. náročné na čas procesora

2. s podporou OS

1. proces je v stave čakajúci, bežia ostatné procesy – daný proces čaká na udalosť od nich

1.  busy waiting

Zamykacie premenné

zámok: boolean – while cyklus – kým zamknuté, tak sa vykonáva

var front: array[0..n] of string

   N:integer = 0;

   Zamknute: boolen=false;

Procedure pridaj (meno:string);

Begin

while zamknute do begin

  front[n]:= meno;

  n:= n+1;

  zamknute:=false;

 end;

End;

zamykacie premenné NIE SÚ riešením !!!

Striktné striedanie

spĺňa základnú podmienku, z ostatným nespĺňa jednu  treba vedieť, koľko je procesov

var front: array[0..n] of string

   N:integer = 0;

   Narade: integer = 1;

Procedure pridaj (meno:string);

Begin

repeat until narade = 1               repeat until narade = 2            CMP narade,1

  front[n]:= meno;                ~~                                 JNE @1

  n:= n+1;                               ~~

  narade:=2;                       narade:=1;  

 end;

ak sa zakážu prerušenia – plánovač sa nedostane k slovu

 ASM CLI END;

CLI zakáže prerušenie

povolí to Win 98  Win XP – pokus o vykonanie privilegovanej inštrukcie, ktorú môže robiť len jadro OS

    ASM STI END;

     môže vážne narušiť systém

   bežná používaná metóda pri programovaní driverov – keď vznikne prerušenie – odovzdá sa program – zakážu sa prerušenia

Nedeliteľné „testuj a zamkni“

@1:TSL OTVORENE, EAX        //inštrukcia z IBM 360 – prenesie pamäťové miesto/register do registra a vynuluje

CMP EAX,1                   môžem prerušiť viem testovať či bolo otvoren

var front: array[0..n] of string

   N:integer = 0;

   Otvorene: boolen=true;

Procedure pridaj (meno:string);

ASM                                              

SHR OTVORENE,1           prenesie carry  

JNC @1;

front[n]:= meno;

End;

OTOVORENE:= TRUE;                                 Aktívne čakanie

Petersonove riešenie – potrebuje vedieť, koľko procesov

2. s podporou OS

Systém SLEEP & WAKE UP

if not otvorene then sleep

otvorene:= false;

...

...

wakeup(2) //druhý proces

druhý proces -- wakeup(1), ak 1 nespí nič sa nestane

môže sa stať, že sa wakeup stratí a program odíde do kritickej sekcie, wakeup sa znovu nevykoná  

zase nefunguje, nie je to správne riešenie

Binárny semafor – E. W. Dijskstra, 1965

typ s dvoma stavmi – 0 a 1 a operáciami DOWN a UP

*..., čaká na UP semafor, jeden z programov sa uvoľní, skončí a dá UP – uvoľní sa ďalší

Ak nečaká =>1

Ak niekto čaká - 1 čakajúci sa znení na pripravený, bod zostane na 0, končí to na 1 – keď prešli všetky programy krit. sekciami

otvorene: semafor; //1 z procesov ho inicializuje

DOWN semafor;

...

UP semafor

semafor je kombináciou sleep/wakeupu a zámkov, stále sa používa

Všeobecný semafor

ľubovoľné stavy >= 0, tiež procedúry DOWN a UP,

CONST MAX = 100;

var m:integer;

voľné = N, obsadené = 0 : vseobecny semafor

DOWN VOLNE;

DOWN OTVORENE;

 front[n]:= meno;                PRODUCENT

 N:=N+1 mod MAX;

UP OTVORENE;

procedure zober(var m:string);

begin

 DOWN OBSADENE;

 DOWN OTVORENE;

 MENO:= FRONT(M);                KONZUMENT

 M:= (M+1) MOD MAX;

 UP OTVORENE;

 UP VOLNE;

end;

                 Cyklický front – riešenie úloh typu producent – konzument

Monitory (Hoare, Hansen) – v praxi stačia semafory, //lock a unlock v Delphi pri Canvase

DeadLock // uviaznutie

(väčš.) chyba programátora

 množina procesov uviazla vtedy, keď každý proces z tejto množiny čaká na udalosť, ktorú môže spôsobiť len iný proces z tej istej množiny //2 procesy sa navzájom blokujú  

**************************************************************************************

Komunikácia medzi procesmi

Posielanie správ

        send (adresát, správa)        //správa = pole bytov

                možnosti – či chce odosieľateľ čakať na prijatie alebo nie

        receive (odosieľateľ, var správa)

1. v niektorých verziách nemusí byť určitý
2. pri správe aj voľby – flagy ...či chcem čakať a pod.

win control – posiela správy, ktoré príjmajú okná

sendmessage (handle, správa, wparam, lparam)

postmessage (handle, správa, wparam, lparam)

každé okno má procedúru pre prijatie správy – jej telom je case – spracovanie podľa typu správy

wm.keydown – ak je stlač. kláves

pipe – v unixe

RPC – remote procedure call

1. pokus zakryť komunikáciu medzi procesmi
2. programátor napíše 1 aplikáciu, v prídavnej informácii je popis procesov, ktoré sa skladajú z procedúr A, B, C, D – A,B = proces P1 a C,D = proc P2
3. systém: program (obsahuje proc al moduly)  RPC (predkompilátor, prekompiluje volania procedúr na posielanie správ)  2 zdrojáky, 2 procesy

Klasické problémy / úlohy

Dining Philosophers // problém obedujúcich filozofov

máme n filozofov na konferencií, ktorý fungujú v dvoch režimoch – buď filozof rozmýšľa alebo je, najesť sa musí, ale trvá to konečnú (krátku) dobu

jedlo sa je 2 vidličkami, filozofovia sedia pri okrúhlom stole a počet vidličiek zodpovedá počtu filozofov

vidličky sú teda zdieľaný nástroj

riešenie:

každá vidlička má binárny semafor a filozofi procedúry uchop_vidličky(n) a uvoľni

uchop_vidličky(n..)

 čakaj(ľavá)

 čakaj(pravá)

 zober(pravá, n)

Protokol Eternet

1 vodič

spätná odozva – keď je vysielanie zinterferované, treba prestať

Správa procesov vo Windows

        32bit Win – preemptívne plánovanie

Delphi – Processes and Threads                                         //pozri delphi help

1. processes
2. thread – vlákno, ... , zahŕňa info o vykonaní, momentálny stav registrov a zásobníka
3. fiber = thread, ktorý neplánuje, má stav
4. priority class
5. priority level
6. base priority
7. priority boosts

1. slúži na zlepšenie času odozvy, pre interaktívne thready
2. dočasné zvýšenie priority bežných procesov (0-15) na vyššiu ako BG procesy
3. postupne sa mu priorita znižuje až na pôvodnú
4. po skončení čaká

1. priority inversion – vedie k stavu podobnému deadlocku
2. win 9x – aktívne detekuje a boostuje procesy
3. win NT – náhodne zvyšuje prioritu ready threadom

Synchronizačné mechanizmy vo Windows

synchronizačné objekty:

        mutax – binárny semafor (mutual exclusion)

        semaphore – všeob. semafor

        timer

        event – oproti semaforu môže vyvolať viac „reagujúcich naraz“, je binárny

Pr:  M:=CreateMutex();

    ...

    ...

    WaitForSingleObject(n,infinite);

    ...        

    ...

    Release Mutex(M);

    closehandle(M);

tieto objekty maj[ meno yn8me v celom syst0me

objekt Critical Section Object – funguje len v rámci jedného

Pr:  var ks: TCriticalSection

    InitializeCriticalSection(ks);

    DeleteCriticalSection(ks);

    EnterCriticalSection(ks);

    LeaveCriticalSection(ks);

Správa pamäte

funkcie

2. udržať informáciu o voľnej, použitej, ... pamäti
3. prideľovať / uvoľňovať pamäť procesom
4. ochrana pamäte procesu
5. umožniť zdieľanie pamäte procesmi        //nie je možné v 32bit Win – thready zdieľajú pamäť, segmentovanie
6.  vytvárať a udržiavať virtuálnu pamäť procesov

Jednoduchá správa pamäte

– operácie pridelenia a uvoľnenie každej jednej časti pamäte

        GETMEM (smerník – netypový, n bytov)        //N-bitový fyzický adresný priestor        

        FREEMEM (smerník, n bytov)

        new (p) – smerník na typ vyššie definovaný

Pascal – postupne získava časti pamäte z OS, ktoré delí na menšie časti – pascalovské dáta

Metódy správy pamäte sa používajú nie len v OS, ale aj v knižniciach vyšších progr. jazykov, tam možno metódy doprogramovať.

Problém Externá fragmentácia

spôsobujú ju malé diery v lineárnej pamäti vznikajúce pri prideľovaní a uvoľňovaní  vznikajú voľné segmenty medzi obsadenými úsekmi

Riešenie

čistý obraz pamäte – súbory .com

– bežné programovanie cez segmenty (DS, SS, CS) – – v pôvodných 16bit proc. – program .com <= 64B

Relokácia

1. pri prekladaní program nevie, kam do pamäte bude nahraný
2. pri zavádzaní alebo hocikedy použitím .com
3. súbor .exe – obsahuje dvojakú informáciu – kód progr. a informáciu o tom, kde sú adresy (relatívne k zač. bloku)
4. .exe súbor je ľahko relokovaný pri zavádzaní
5. OS: CS 360 MFT
6. Ochrana

1. IBM 360 – 16 x 2kB častí
2. pamäť sa dá rozdeliť na 2kB bloky, ku každému sa pridelia 4b mimo adresného priestoru  zámok, kód
3. zámok sa mení počas behu programu
4. pri adresovaní stroj. kód kontroluje kľúče a zámky – porovnanie zámku s kľúčovým registrom

1. Tvar vykonateľného programu obsahuje funkciu na relokáciu pamäte

teda:  riešenie fragmentácie – – kompaktácia => relokácia

Algoritmy správy pamäte

Bitová mapa

2. 1 bit pre každé najmenšie prideliteľné miesto – – 0 voľné / 1 obsadené
3. 16B – minimálny prideliteľný úsek
4. GETMEM (P, 256)        // 256/16 = 16 – algoritmus musí hľadať 16 núl za sebou
5. FREEMEM (P, 512)
6. nevýhoda: – pomocná dát. štruktúra zaberá pamäť

                        – kvôli efektivite treba určiť prideliteľný úsek (16B)

Spájaný zoznam

záznam = record

  obsadený: boolean;

  veľkosť: cardinal;

  adresa: pointer;

  ďalší, predošlý: ^záznam;

end;

1. spájanie pamäťových blokov – zlúčim prvky zoznamu a nastavím mu veľkosť súčtu veľkostí
2. uvoľnenie pamäte = zrušenie a presmerníkovanie
3. výhoda: rýchlosť – vyreťazenie trvá rovnako dlho bez ohľadu na veľkosť blokov
4. nevýhoda: nevieme koľko bude naša štruktúra zaberať – zaberá miesto podľa počtu voľných vs. obsadených blokov

Modifikovaný spájaný zoznam

1. ukladá sa len dĺžka bloku, netreba smerník na ďalšieho
2. info sa ukladá rovno do pamäte – P, pointer na čítané miesto ( GETMEM(P) ) sa nastaví až za info
3. info aj na konci – o obsadení a veľkosti // kvôli spojeniu s predošlými blokmi
4. ak niekto žiada menej ako 4B – pridelí sa viac miesta // kvôli fragmentácii

Spôsoby nájdenia voľného úseku

First Fit – použije sa prvý voľný priestor s >= veľkosťou

Best Fit – hľadá sa priestor presne takej veľkosti, akú treba alebo o niečo väčší

        – problém: zaručene zanedbáva malé nepoužiteľné zvyšky

Worst Fit – všetko ukladá do najväčšieho priestoru //teoretický spôsob

Circular First Fit – hľadá od miesta, kde sa naposledy prideľovalo

                  – obmedzí hľadanie v malých kúskoch na začiatku a vo veľkých na konci

Past Fit – más svoje „obľúbené“ dĺžky, napríklad: správa pamäte vyšš. progr. jazyka  

Virtuálna pamäť

1. riešenie ochrany
2. spočiatku používaná kvôli cene pamätí – simulácia väčšej než reálnej
3. 2 prístupy: segmentovanie a stránkovanie

1. Segmentovanie

1. rôzne veľkosti segmentov, 2-rozmerná pamäť, adresovanie systémom segment–offset
2. GetMem – vytvorí segment (z N1, N2 –> N3)
3. v OS podporujúcom segmentovanie možno žiadať o zmeny veľkosti segmentov
4. tabuľka segmentov
5. výnimka typu výpadok segmentu

1. posledná inštrukcia sa vykoná znova, medzitým sa potrebný segment nahrá z disku a upraví tabuľku so segmentami a offsetmi
2. stroj. kód musí mať konkrétnu podporu pre túto operáciu

2. Stránkovanie

1. vychádza z 1-rozmernej pamäte – mapuje do 1-rozmernej

- - - - tu má byť akýsi obrázok...ale ja to už proste nezvládam kresliť, nexeee sa mi :-P - - - - -

2. fyzický priestor (0..M) rozdelíme na rámce napr. 4kB  adr. konca
3. virtuálny adresný priestor rozdelíme na stránky
4. v adrese sa zmení číslo stránky na číslo rámca
5. výnimka: ak adresa nie je v pamäti – prenos z disku – odznova
6. bežný programátor nemusí vedieť o stránkovaní
7. Algoritmy hľadania obete

Algoritmy hľadania obete

1. obeť = stránka, ktorú rámec pošle preč z fyzického adr. priestoru, aby mohol urobiť priestor pre aktuálne adresovanie
2. snaha minimalizovať počet výmen a výpadkov
3. optimálny algoritmus – – najlepšia obeť by bola taká, čo sa nikdy nebude adresovať; ak taká nie je, tak je to stránka, čo sa bude adresovať najneskôr
4. každý z algoritmov sa snaží k optimalizácii priblížiť

NRU – not recently used

1. stránka nebola v blízkej minulosti použitá
2. podpora v procesore / stroj. kóde – 1bit v tabuľke T
3. A /acces bit/ – keď procesor použije riadok tabuľky – nastaví A bit na 1.

Na začiatku nastaví OS tabuľku na 0 a cyklicky nuluje tie stránky, kde A bit na 1  

a boli použité v poslednom „kvante“

1. ďalší pomocný bit D /dirty bit/ - ukazuje, či bolo do stránky zapísané od momentu jej načítania do pamäte – ak nebolo, tak je na disku // ušetrí sa 1 operácia

      FIFO – first in first out

        stránka, ktorá je tam najdlhšie, druhá šanca

     LRU – Least Recently Used         //najdávnejšie použitý

Podpora virtuálnej pamäte v procesoroch Intel Pentium

8086/88 //16bit – žiadna podpora

80286 //16 bit – reálny a chránený režim (segmentovanie – segment 64kB)

80386 //32 bit – reálny režim

                 – chránený režim – 32b segmentovanie – segment 4GB

                – stránkovanie – režim virtuálnej 86ky – adresovanie ako  v reálnom režime                                 8086ky – DOS aplikácie pod Windows

Segmentovanie (jeho podpora v 386+)                 //obr. 5.2, 5.3

RPL – 00 – najvyššia ochrana, napr. OS

       – 11 – bežné procesy

Ti (?) – 0 – GDT //Global descriptor table

            1 – LDT //Local descriptor table

Báza segmentu 32b – – 4GB

LIMIT – B / 4k-bytové jednotky

G – berie sa limit v násobkoch 4kB //??

AVL – available to user // to OS

Prístupové práva                //obr 5.4, 5.6, 5.8

Segmenty

1.  údajové

              práva – bit p //je v pamäti?

                bity DPL – ochrana segmentu

                bity 43/ 1,0 – data segment, 1,1 – inštr. segment, 0,x – sys. segment

                bit A – access bit

                bit ED = 0  – normálny data segment             4GB                            4GB

                           = 1  – zásobník nejakého procesu

                bit W = 0 – read only segment               LiM                              LiM                        

                                                                       0                                   0

                                                        ED0                        ED1

segmentovanie sa dá dobre využiť pri zdieľaní pamäte, 1 segment môže byť použitý vo viacerých virtuálnych adresných priestoroch

2.  inštrukčné                        

                  LDT alebo GDT

                bit R – či sa dá čítať

                zefektívnenie segmentovania

                        časti: báza | limit                 

                        ak sú v selektore samé nuly – odkazuje na nil

3. systémový //napr. LOT

Systémový riadiaci register CRO                        //obr. 5.12

PE ak =1 – chránený režim / =0 reálny režim

PG stránkovanie – ON / OFF – lineárna pamäť – fyzická pamäť

31        22        11        0

4kB

     str. adresár        stránková                Fyz. pamäť

                tabuľka

8kB stránok

*************************************************************************************

Správa zariadení

HW – vstupno/výstupné zariadenia

typy:

Blokovo orientované

 s priamym prístupom

napr. disk („vonkajšia pamäť“) – obsahuje adresovateľné bloky

Znakovo orientované

 Sekvenčné

napr. znaková tlačiareň

Radič (controller) zariadenia

        procesor         pamäť            radič                

Prístupy

4. špeciálnymi I/O inštrukciami
5. mapovaním registrov radičov I/O zariadení do pamäte
6. DMA prístup

                – Direct Memory Access – procesor povie radičom, čo majú robiť, zatiaľ môže robiť                                 niečo iné, nemusí dáta čítať z registrov po bytoch

                – bez účasti procesora – hodnoty sa na začiatku zapíšu do radiča

7.  použitie po prerušení – preruší prácu, ak je úloha hotová
8.  rolling (spytovanie sa) – v cykle sa pýta, či je úloha hotová

Software správy zariadení

1. sprístupnenie funkcií I/O zariadení (čo najviac) strojovo nezávislým spôsobom; tak, aby to nebolo veľmi závislé od zariadenia – cez volania OS, ktoré majú zakrývať druhy, vlastnosti zariadení
2. pomenovanie zariadení
3. spracovanie chýb – nehlási chyby rovno systému, nie sú fatálne, takže ich najprv, čo najviac, rieši sám daný SW (opakovaním, ....)
4.  prezentovanie asynchrónnych I/O operácií synchrónnym spôsobom (užívateľskému programu) – proces, ktorý funkciu vyvolá je počas behu v stave čakania, kým sa úloha neskončí
5. prideľovanie zariadení procesom        //blokovo orentované zariadenia možno zdieľať / serializovať znakovo orientované sa prideľujú (čakanie a pridelenie) na exkluzívne použitie
6. ochrana zariadení (nie každý proces môže pracovať so všetkými zariadeniami)

1. preruš. podprogramy
2. ovládače/drivery
3. strojovo nezávislý SW
4. užívateľský I/O SW

Ovládač (driver)

1. je strojovo nezávislý, dostáva relatívne jasný príkaz
2. ak je rýchly, netreba prerušenie
3. ak používa radič, musí sa dať do stavu čakajúci – čaká na radič, ak ten skončí – prerušenie podprogr. – berie dáta z radiča –  driver sa odblokuje až keď je všetko zapísané
4. ak je chybový kód – preruš. podprogr. sa snaží opraviť – následne aj driver, ak ide chyba ďalej aj za užívateľský SW  výnimka, spracovanie chyby procesom
5. zakrýva všetko strojovo závislé – snaha o čo najmenej strojovo závislé podanie

Preruš. podprogramy – čo najkratšie, možno v nich urobiť najviac chýb

Strojovo nezávislý SW

1. jednotný SW interface pre drivery
2. pomenovanie zariadení nezávislé od zariadenia – mapovanie zariadenia do jeho drivera
3. strojovo nezávislé bloky – ukladanie údajov do buffera – cieľ: veľkosť zapisovaného bloku nezávislá od zariadenia
4. Buffering – vyrovnávacia pamäť, zbieranie dát

                //driver môže mať fixný počet bufferov mimo správy pamäte

1. prideľovanie (pomenovaných) zariadení
2. hlásenie chýb        //z vyšších úrovní – pretvorených do unifikovaných chybových správ

Užívateľský I/O SW

1. knižnice vyššieho programovacieho jazyka, nie je súčasťou OS

        // vyš. progr. jazyky – nezávislé od OS – knižnice podľa OS

                var i:integer;

                writeln(tlac,i);

                 volanie podprogramu z knižnice prevedie z jazyka pascalu do pojmu OS – zavolá službu OS

2. virtuálne zariadenia (zbieranie výstupu do súboru, až ten ide do I/O)

DeadLock v správe zariadení

        A        B        orientovaný cyklus na orient. grafe

                chyba nastáva nezávisle na programátoroch

        Z         S         podmienky pre vznik deadlocku (Hoffman a spol.)        

1. zariadenie môže byť pridelené najviac 1 procesu
2. proces vlastniaci zariadenia môže žiadať o ďalšie
3. neexistuje preempcia (odoberanie nasilu) v správe zariadení – zariadenie pridelené procesu, až kým ho neuvoľní
4. v orientovanom grafe sa nachádza orientovaný cyklus procesov a zariadení

Správa súborov

pohľad používateľa:

3. sekvenčný prístup – napr. (?) File v Delphi
4. priamy prístup – veta pevnej alebo premenlivej dĺžky
5. operácie na súboroch

                open(handle,...) F := open(meno, spôsob))

                read(f, x, dĺžka, č. vety)

                write

                close(f)

1. operácie na adresároch

                vytvorenie, zrušenie, premenovanie súboru/adresára

                nastavenie atribútov – ochrana súborov (prístupové práva), „vlastné“ atribúty

úlohy správy súborov

1. vytvárať a udržiavať súbory
2. ochrana súborov
3. zdieľanie súborov

Implementácia – pohľad tvorcu

Lin. adr. priestor  strom   ….                  //no jo...tu uz aj Frankiemu dochádzajú invenčné poznámky

Štruktúra súborov „FileSystem“                

( FAT, NTFS )

1. FAT – file allocation table
2. cluster = alokačný blok – 0 = voľný, iné číslo – pseudospájaný zoznam
3. priestor na súbory
4. koreňový adresár
5. boot sector

master boot

record                        partitions                        extended partition

MBR                                                MBR                   MBR        

                                        aktívna partícia

                        boot sector

**************************************************************************************

made by kik © 2005

THANKS TO:         Ettelie,         Frank