Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

FIT > IOS > Flashcards

IOS Flashcards

1
Q

Deadlock

A

rozumíme situaci, kdy
každý proces z určité množiny je pozastaven a čeká na uvolnění zdroje s výlučným (omezeným)
přístupem vlastněného nějakým procesem z dané množiny, který jediný může tento zdroj uvolnit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Obecna defenice Deadlocku

A

Uváznutí jako situaci, kdy každý proces z množiny procesů je pozastaven a čeká na
událost, která by mohla nastat pouze tehdy, pokud by mohl pokračovat nějaký proces z dané
množiny

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

COFFMANOVY PODMÍNKY UVÁZNUTÍ

A
  1. Vzájemné vyloučení při používání prostředků
  2. Vlastnění alespoň jednoho zdroje, pozastavení a čekání na další
  3. Prostředky vrací proces, který je vlastní a to až po jejich využití
  4. Cyklická závislost na sebe čekajích procesů
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

PREVENCE UVÁZNUTÍ

A
  1. Nepoužívat sdílené prostředky, nebo používat takové sdílené prostředky, které umožňují
    skutečně součastný sdílený přístup a u kterých není nutné vzájemné vyloučení procesů
  2. Proces může o prostředky žádat pouze v případě, že žádné nevlastní
  3. Pokud proces požádá o prostředky, které momentalně nemůže získat, je pozastaven, jsou mu
    odebrány všechny prostředky a proces je zrušen, a nebo čeká do doby než mu mohou být ony
    prostředky přiděleny.
  4. Prostředky jsou číslovány a je možné je získat pouze od nejnižších čísel k nejvyšším, nebo v
    jiném pořadí, které vylučuje vznik cyklické závislosti procesů
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

VYHÝBÁNÍ SE UVÁZNUTÍ

A

Procesy předem deklarují určité informace o tom jakým způsobem budou využívat zdroje, v
nejjednoduším případě se jedná a maximální počet součastně požadovaných zdrojů jednotlivých
typů.
Předem známé informace o možných požadavcích jednotlivých procesů a o aktuálním stavu
přidělování se využijí k rozhodování o tom, které požadavky mohou být uspokojeny, a které si na
své uspokojení musí počkat, cílem je zamezit tomu aby nemohla vzniknout cyklická závislost na
sebe čekajících procesů i v nejhorší možné situaci, která by v budoucnu mohla vniknout při
deklarovaném chování procesů.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Výpadky stránek

A
  1. Proběhne kontrola, zda proces neodkazuje mimo přidělený adresový prostor
  2. Alokace rámce
    • Pokud je nějaký rámec volný, použije se
    • Vybereme vhodnou stránku s přiděleným rámcem (victim page), stránku odložíme na swap
    • Použijeme vzniklý volný rámec
  3. Inicializace stránky po alokaci závislá na předchozím stavu stránky
    • První odkaz na stránku
    • Stránka byla v minulosti uvolněna z FAP
  4. Úprava tabulky stránek
    • Namapování zpřístupňěné stránky na přidělený rámec
  5. Proces připraven na opakování instrukce která výpadek způsobila ( je ve stavu “připravený”)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

FIFO algoritm vyberu

A

Algoritmus FIFO (first in first out) odstraňuje stránku, která byla zavedena do paměti před nejdelší
dobou a doposud nebyla odstraňena.
Lze využít v kombinaci s odložením oběti na nějaká prostor a v případě špatného výběru se oběť
obnoví a vybere se jinak.
Výhody : Jednoduchá implementace
Nevýhody : Může odstranit starou, ale stále používanou stránku

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

LRU

A

Algoritmus LRU odkládá nejdéle nepoužitou stránku, používá se aproximace LRU
Výhody : Velmi dobrá aproximace hypotetického ideálního algoritmu
Nevýhody : Někdy se uvádí problém s cyklickými průchody rozsáhlími poli, problematická
implementace (vyžadující výraznou HW podporu - označování stránek časovým razítkem
posledního přístupu, či uržování zásobníku stránek, kde je vrcholem naposledy použitá stránka)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Aproximace LRU (2 druhy)

A

Aproximace pomocí omezené historie
• Refefenční bit je nastaven s každým přístupem, jádlo si vezme omezenou historii tohoto bitu pro jednotlivé stránky, periodicky posouvá obsah historie doprava
• Na nejlevější pozici se ukládá aktuální hodnota referenčího bitu a vynuluje ho, oběť je vybrána
jako stránka s nejnižší číselnou hodnotou historie
Aproximace “druhá šance”
• Stránky v kruhovém seznamu, postupuje a nuluje se refenční bit, odstraní se stránka která
referenční bit 0 už má
• Často používaný algoritmus též označovaný jako clock algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

DEFINICE OPERAČNÍHO SYSTÉMU

A

kolekce programů která vytváří spojující vrstvu mezi

hardwarem počítače ( ten může být buď fyzický nebo virtualizovaný ) a uživateli a jejich aplikacemi

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

CÍLE OS

A
  1. Maximální využití zdrojů ( zejména dříve kdy byl velmi drahý hardware a levná pracovní síla)
  2. Snadnost použití ( zejména dnes, kdy je levný hardware a drahá pracovní síla )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

ROLE OS

A
  1. Správce protředků ( dovoluje bezpečné a efektivní sdílení prostředků )
  2. Tvůrce virtuálního počítače ( Poskytuje standartní rozhraní, poskytuje abstrakce )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

JÁDRO

A
  • Nejnižší správa prostředku a tvorba prostředí pro zbytek OS a uživatelské aplikace ( nejnižší anejzákladnější část OS )
  • Zavádí se jako první a běží po celou dobu běhu hardware
  • Navazuje přímo na hardware ( který může být i virtualizovaný )
  • Obvykle běží v privilegovaném režimu
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

MIKROJÁDRA

A

Minimalizují rozsah jádra a nabízí jednoduché rozhraní s jednoduchými abstrakcemi a malým
počtem služeb )
• Většína služeb monolitického jádra implementována formou serverů mimo režim jádra
Výhody :
• Flexibilita ( spouštění, zastavování serverů.. )
• Bezpečnost ( útok na server neovládne celé jádro )
Nevýhody : Vyšší režie ( nižší efektivita )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

NEPREEMPITVNÍ PLÁNOVÁNÍ

A

Ke zmeně běžícího procesu může dojít pouze tehdy, pokud to běžící proces umožní předáním
řízení jádru ( žádá o službu typicky I/O operaci, končí nebo se sám vzdává procesoru )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

PREEMPTIVNÍ PLÁNOVÁNÍ

A

Ke změně běžícího procesu může dojít i bez nápomoci přepnutí kontextu a to na základě
přerušení ( typicky od časovače, ale může se jednat i o jiné přerušení )

17
Q

FCFS ( First come, first served )

A

• Procesy čekají ve FIFO frontě
• Nepreemptivní - proces se jádra musí vzdát sám
• Pokud se proces ve svém průběhu vzdá procesoru, předá řízení a jde na konec fronty
( procesor se přiděluje procesu na začátku fronty )

18
Q

Round-robin

A

• Preemptivní obdoba FCFS
• Pracuje podobně jako FCFS, ale navíc má každý proces přiděleno časové kvantum po jehož
vypršení je mu odebrán procesor a jde na konec fronty

19
Q

SJF ( Shortest job first)

A

o Přiděluje procesor procesu, který požaduje nejkratší dobu pro své další
provádění na procesoru bez I/O operací
o Nepreemptivní algoritmus
o Minimalizuje průměrnou dobu čekání, zvyšuje propustnost systému
o Nutno znát dopředu dobu běhu procesu na procesoru nebo mít možnost tuto
dobu rozumně odhadnout na základě předchozího chování
o Používá se ve specializovaných systémech
o Hrozí stárnutí (hladovění) procesů mající dlouhé výpočetní fáze

20
Q

Víceúrovňové plánování

A
  • Procesy jsou rozděleny do různých skupin ( typicky podle priorit, typu .. )
  • V rámci každé skupiny může být použit jiný plánovací algoritmus
  • Hrozí zde hladovění procesů s nízkou prioritou
21
Q

Víceúrovňové plánování se zpětnou vazbou

A

• Víceúrovňové plánování se skupinami procesů rozdělených dle priorit
• Nový proces je zařazen do fronty s nejvyšší prioritou a postupně klesá, do nižších prioritních
front a nakonec plánován round-robin na nejnížší úrovni
• Modifikace kdy je zařazen na základě statické priority, postupně podle dynamické klesá pokud
bere hodně času nebo stoupá pokud šeká na mnoho I/O operací
• Cílem je zajistim rychlou reakci interaktivních procesů

22
Q

Plánovač v Linuxu verze 2.6

A

• Priority procesů 1-99 pro procesy reálného času plánované FCFS nebo round-robin
• Priorita 0 pro bežné procesy plánované CFS plánovačem
• V rámci úrovně 0 se dále používají podúrovně v rozmezí -20 (nejvyšší) az 19 (nejnižší) nastavené
uživatelem

23
Q

CFS ( Completely Fair Scheduler)

A

1) Snaží se explicitně každému procesu poskytnout odpovídající procento strojového času (dle jejich priorit)
2) Vede si u každého procesu údaj o tom, kolik (virtuálního) procesorového času strávil.
3) Navíc si vede údaj o minimálním stráveném procesorovém čase, který dává nově připraveným procesům.
4) Procesy udržuje ve vyhledávací stromové struktuře podlevyu žitého procesorového času.
5) Vybírá jednoduše proces s nejmenším stráveným časem.
6) Procesy nechává běžet po dobu časového kvanta spočteného na základě priorit a pak je zařadí zpět do plánovacího stromu.
7) Obsahuje podporu pro skupinové plánování: Může rozdělovat čas spravedlivě pro procesy spuštěné z různých terminálů

24
Q

PROBLÉM INVERZE PRIORIT

A
  • Nízkoprioritní proces si naalokuje nějaký zdroj, více prioritní procesy ho předbíhají a nemůže dokončit práci s tímto zdrojem
  • Časem tento zdroj mohou potřebovat více prioritní procesy, jsou nutně zablokovány a musí čekat na nízko prioritní proces
  • Pokud jsou v systému středně prioritní procesy, které nepotřebují daný zdroj budou nadále předbíhat nízkoprioritní proces
  • Tímto způsobem uvedené středně a nízkoprioritní procesy získávají efektivně vyšší prioritu
25
Q

ŘEŠENÍ INVERZE PRIORIT A KOMPLIKACE PLÁNOVÁNÍ

A

1)Priority ceiling : procesy v kritické sekci dostávají nejvyšší prioritu
2)Priority inheritance : proces v kritické sekci, který blokuje výše prioritní proces dostává (dědí)
prioritu čekajícího procesu s nejvyšší prioritou
3)Zákaz přerušení po dobu běhu v kritické sekci : proces získá v podstatě vyšší prioritu než všichni
ostatní

1) Víceprocesorové systémy : nutnost vyvažovat výko, respektivě obsah casche procesorů
2) Hard real-time-systémy : nutnost zajistit garantovanou odezvu

26
Q

Plánovač diskových operací

A

Pořádí bloků čtených/zapisovaných na disk má na starosti plánovač diskových operací
Přenos z / na disk je řízen řadičem disku příméno přístupu do paměti ( DMA )
O ukončení či chybách operace informuje řadič procesor ( jádro ) pomocí přerušení
• Přicházejí požadavky na čtení/zápis a ty jsou ukládány do vyrovnávací paměti a jejich pořadí je případně měněno tak, aby se minimalizovala režie diskových operací
• Plánovač také může sdružovat operace, odkádat operace v naději, že bude možné je později propojit, impementovat časové omezení na provedení operací, impelementovat priority
operací ..

27
Q

Výtahový algoritmus a dalsi algoritmy

A

Pohybuje hlavičkami od středu k okraji ploten a zpět a vyřizuje požadavky v pořadí
odpovídajících pozici a směru hlaviček
1) Circular SCAN
• Vyřizuje požadavky vždy při pohybu jedním směrem - rovnoměrnější doba obsluhy
2) LOOK
• Pohybuje se jen v mezích danými aktuálními požadavky - nižší průměrná doba přístupu

28
Q

Žurnálování

A

Žurnál slouží k ukládání modifikovaných metadat ( data o datech ) před jejich zápisem na disk
Cílem žournálování je zajistit atomicitidu diskových operací ( buď operace proběhnou celé nebo vůbec )
Souborové systémy se žournálem : ext3, ext4, ufs, XFS, JFS, NTFS ..
Data se obvykle nežurnálují, důvodem je velká režie
Žurnál umožňuje rychlejší a spolehlivější náhrat do konzistentního stavu po chybách

29
Q

Implementace na základě dokončení transakcí (REDO):

A
  • Sekvence operací se uloží do žurnálu mezi značky označující začátek a konec transakce.
  • Poté se dílčí operace provádí na disku.
  • Uspějí-li všechny dílčí operace, transakce se ze žurnálu uvolní.
  • Při selhání se dokončí všechny transakce, které jsou v žurnálu.
30
Q

Implementace na základě anulace transakcí (UNDO):

A
  • Záznam dílčích operací do žurnálu a na disk se prokládá.
  • Proběhne-li celá transakce, ze žurnálu se uvolní.
  • Při chybě se eliminují nedokončené transakce.
31
Q

Copy-on-write

A

1) nejprve zapisuje nová data/metadata na disk, pak je zpřístupní:
2) Změny provádí hierarchicky v souladu s hierarchickým popisem obsahu disku (jde o vyhledávací,
nikoli adresovací strom).
3)Vytvoří kopii měněného uzlu -> upraví ji -> vytvoří kopii
uzlu nadřazeného -> upraví ji tak, aby ukazovala na uzel vytvořený v předchozím kroku.
4) Na nejvyšší úrovni se udržuje několik verzí kořenového záznamu se zabezpečovacím kódem a časovými razítky.
5) Nabízí bázi pro implementaci: snímků souborového systému a klonů SS – vznikají částečně sdílené stromové
struktury popisující různé verze obsahu SS

32
Q

ČASOVĚ ZÁVISLÁ CHYBA (RACE CONDITION)

A

Data race (časově závislá chyba nad daty) – dva přístupy ke zdroji s výlučným přístupem ze dvou procesů bez synchronizace, alespoň jeden přístup je pro zápis

33
Q

Kritická sekce:

A

• Sdílenými kritickými sekcemi daných procesů rozumíme ty úseky jejichž řídící program přistupuje ke sdíleným zdrojům, jehož provádění jedním procesem vylučuje
současné provádění ostatními procesy.
• Problém kritické sekce rozumíme problém zajištění korektní synchronizace procesů na množině sdílených kritických sekcí, což zahrnuje:
1) Vzájemné vyloučení – nanejvýš jeden (někdy víc) proces je v daném okamžiku v dané množině sdílených KS.
2) Dostupnost KS:
▪ Je-li KS volná, proces nemůže neomezeně čekat na přístup do ní.
▪ Je zapotřebí se vyhnout:
• Uváznutí
• Blokování
• Stárnutí

34
Q

Problémy vznikající v kritické sekci:

A
  • Data race (časově závislá chyba nad daty) – dva přístupy ke zdroji s výlučným přístupem ze dvou procesů bez synchronizace, alespoň jeden přístup je pro zápis
  • Blokování (blocking) při přístupu do KS – situace, kdy proces, jenž žádá o vstup do kritické sekce, musí čekat, přestože je kritická sekce volná a ani žádný další proces o ni nežádá.
  • Stárnutí (aneb hladovění) – situace, kdy proces čeká na podmínku, která nemusí nastat. V případě kritické sekce je umožnění vstupu do ní.
35
Q

Alokační blok, Diskový sektor, Extent

A

Diskový sektor: nejmenší jednotka, kterou disk umožňuje načíst/zapsat
Alokační blok: skupina pevného počtu sektorů, typicky 2^N pro nějaké N, následujících logicky (tj. v souboru) i fyzicky (tj. na disku) za sebou, která je nejmenší jednotkou diskového prostoru se kterou umí OS (FS) pracovat. (nejmenší jednotka, kterou umožňuje OS načíst/zapsat)
● Extent - posloupnosti proměnného počtu bloků jdoucích za sebou logicky v souboru a uložených
fyzicky za sebou na disku. Zrychlují práci s velkými soubory(menší indexovací struktury, menší objem metadat), naopak pro malé soubory to může znamenat zbytečně velkou režii

36
Q

Překlad logické adresy na fyzickou přes 2-úrovňovou tabulku stránek

A

● LA se rozloží na prefix p sestávající z odkazu p1 do adresáře stránek a z odkazu p2 do konkrétní tabulky stránek. Tedy p=p1.p2
● Test zda TLB obsahuje dvojici (p,f), vyhledává se asociativně dle p (je možné částečně asociativní vyhledání), je-li položka (p,f) nalezena, je výsledná adresa (f,d).
● Přístup k položce na indexu p1 v adresáři stránek, který je v RAM na adrese uložené ve speciálním registru MMU (u intelu CR3)
● Má-li výše uvedená položka nastaven příznak neplatnosti, nastává výpadek v adresáři stránek
● Není-li tomu tak, pak se z uvedené položky získá bázová adresa dílčí tabulky stránek rovněž uložené v RAM. Použije se položka s indexem p2 této tabulky.
● Obsahuje-li položka na indexu p2 v dílčí tabulce stránek příznak neplatnosti, nastává výpadek stránky. Jinak se z položky zmíněné výše získá číslo rámce f a výsledná adresa je (f,d)

37
Q

NTFS, odlišnosti různě dlouhých souborů, 3 varianty reprezentace a
adresovaní.

A

● MFT (Master File Table)
○ alespoň jeden řádek pro každý soubor
○ malé soubory jsou celé uložené v MFT (i s obsahem)
○ střední – na řádku příslušeného souboru uložené odkazy na extenty
○ velké – přes 2 řádky jsou odkazy na pomocné odkazy, ve kterých jsou uložené odkazy na
extenty (adresování podobné jako u B+ stromů)
● Extent
○ posloupnoust proměnného počtu alokačních bloků logicky jdoucích za sebou v souboru a
uložených fyzicky na disku
● podpora žurnálování (REDO+UNDO)

38
Q

Účel a princip dvou-úrovňové obsluhy přerušení

A

● minimalizace délky zákazu přerušení
● 1. úroveň:
○ zajišťuje minimální obsluhu HW, plánování běhu 2 úrovně
○ může být vyloučeno/zamaskováno přerušení
● 2. úroveň:
○ postupně dokončuje obsluhu zaznamenaných přerušení
○ nemusí zakazovat přerušení - vzájemné vyloučení se dá řešit běžnými synchronizačními
prostředky

39
Q

Problematika přepisu dat u SSD

A

● Nutnost načíst blok do vyrovnávací paměti, změnit, na disku vymazat, zapsat zpět a to celý, byť se mění jen 1 stránka
● Řešení (lépe řečeno minimalizace problému):
1) Použití více stránek, než je oficiální kapacita
2) Příkaz TRIM - umožňuje souborovému systému sdělit SSD, které stránky nejsou používány a lze je opět považovat za prázdné
3) Samostatné uvolňování stránek v rámci SSD

FIT (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions