-
Notifications
You must be signed in to change notification settings - Fork 1
/
Klausurvorbereitung.html
592 lines (357 loc) · 15 KB
/
Klausurvorbereitung.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<link rel="stylesheet" href="style.css" />
</head>
<title>Betriebssysteme und Sicherheit Prüfungsvorbereitung</title>
<!-- MARKDOWN ......................... -->
<xmp theme="superhero" style="display:none;">
# Sicherheit
##Safety und Security:
###Safety:
* Schutz vor Schäden durch Fehlfunktionen von IT-Systemen
* technisches Versagen: Alterung, Stromausfall
* Menschliches Versagen: Dummheit, Fahrlässigkeit, mangelnde Ausbildung
* höhere Gewalt: Feuer, Blitzschlag, Erdbeben
→ Schutz vor einem IT-System, bedroht durch Fehler, Ausfälle
###Security:
* Schutz vor Schäden durch zielgerichtete Angriffe auf IT-Systeme
* Wirtschaftsspionage, Betrug, Erpressung, Vandalismus
→ Schutz des IT-Systems, bedroht durch strategische Angreifer
##Bedrohung
* Abstrakt: mögliche Ereignisse/Aktionen, die zu einer Verletzung eines oder mehrerer Sicherheitsziele führt
* Instanziierung einer Bedrohung ist ein **Angriff**
###Ziele der IT-Sicherheit → *CIA*
* Vertraulichkeit (**C**onfidentiality)
- Übertragene und gespeicherte Daten dürfen nur legitimierten Empfängern zugänglich sein
- Vertraulichkeit der Identität wird als Anonymität bezeichnet
* Integrität (**I**ntegrity)
- Veränderungen an Daten müssen erkannt werden
- (Identifikation des Absenders)
* Verfügbarkeit (**A**vailability)
- Informationen und Dienste sollen berechtigten Nutzern in angemessener Frist zugänglich sein
Ebenfalls:
* Zurechenbarkeit (Accountability)
- verantwortliche Partei für eine Operation soll identifizierbar sein
* Kontrollierter Zugriff (Controlled Access)
- nur autorisierte Parteien sollen in der Lage sein, auf Dienste oder Informationen zuzugreifen
### Bedrohungen
* Maskerade
* Informationsverlust
* Autorisierungsverletzung
* Zerstörung/Modifikation von Information
* Fälschung von Information
* Abstreiten von Ereignissen
* Sabotage
### Sicherheitsdienste
* Authentifizierung
* Integritätsschutz
* Vertraulichkeitsschutz
* Zugangskontrolle
* Nicht-Abstreitbarkeit
### Sicherheitsanforderungen
* Methodische Identifikation und Spezifikation der Sicherheitseigenschaften von IT-Systemen
#### Bedrohungsanalyse:
* Identifikation der möglichen Angriffsziele / Angreifer / Angriffsmethoden und -techniken
→ Erstellung eines Bedrohungskatalogs mit Inhalt:
* Identifikation der Angriffsziele
* Identifikation potentieller Angreifer
* Angriffsmethoden und -techniken
* Schadenspotential
__Angriffsziele:__
* Informationsgewinn (Spionage, Kontrolle kritischen Wissens)
* Modifikation von Daten (Sabotage)
__Angreifer:__
* professionelle Organisationen
* ehemalige und aktive Mitarbeiter
* politische Gegner
__Angriffsmethoden und-techniken:__
* Ausnutzung technischer und menschlicher Schwachstellen
__Schadenspotential:__
* Verlust der Kontrolle über kritisches Wissen (Risikotechnologien)
* wirtschaftliche Schäden (Vertragsstrafen, Produktkopien)
* Reputationsschäden
------------------------------------------------------------------------------------------------------
# Threads
**"fair"**:
* jeder Thread erhält “angemessenen” Anteil CPU-Zeit
* kein Thread darf CPU für sich allein beanspruchen
* Wohlverhalten von Threads darf bei der Implementierung von Threads keine Voraussetzung sein
#### Definition Thread
* sequentielles Programm
* parallel arbeitend zu anderen Threads
* von einem Betriebssystem zur Verfügung gestellt
#### Zustände
* Aktiv
- Thread wird gerade auf der CPU ausgeführt
* Blockiert
- Thread wartet auf ein Ereignis um weiterarbeiten zu können
* Bereit
- nicht aktiv aber auch nicht blockiert
##### Mögliche Übergänge
* Aktiv --> Blockiert
- Fehlende Betriebsmittel o.Ä.
- Warten auf Botschaft oder Zwischenergebnis
* Aktiv --> Bereit
- z.B. Rechenzeit zu Ende
* Blockiert --> Bereit
- Betriebsmittel stehen zur Verfügung
* Bereit --> Aktiv
- Es wird zu dem Thread gewechselt
#### Betriebsmittel eines Threads
* Kern-Stack
* CPU State
* Thread-Zustand
* Verweis auf Adressraum
* Scheduling-Attribute
* --> TCB (Thread Control Block)
#### Ablauf von switch_to(Ziel-Thread)
```xsl
store_CPU_State(); //in den TCP der im Stack liegt
TCBTAB[Aktueller-Thread].StackPointer = StackPointer; //Speichern der Daten in TCB Tabelle
Aktueller-Thread = Ziel-Thread; // Thread switch
SP = TCBTAB[Aktueller-Thread].StackPointer;
load_CPU_State(); // laden aus dem TCP aus dem Stack
```
## Kritischer Abschnitt
Den Programmteil, in dem auf gemeinsamen Speicher gearbeitet wird, nennt man Kritischer Abschnitt (KA). Wettläufe um den Speicher nennt man Race Condition
**Anforderungen**:
* keine zwei Threadsdürfen sich zur selben Zeit im selben KA befinden.
* -> Wechselseitiger Ausschluss (**SICHERHEIT**)
* Jeder Thread, der einen kritischen Abschnitt betreten möchte, muss ihn auch irgendwann betreten können. (**LEBENDIGKEIT**)
* Es dürfen keine Annahmen über die Anzahl, Reihenfolge oder relativen Geschwindigkeiten der Threads gemacht werden
### Lösungsansätze
#### Implementierung mittels Interruptsperrre (Unterbrechungssperre) //FOLIE 70
**Vorteil**:
* einfach
* effizient
**Nachteil**:
* Nicht im User-Mode
* manche KA sind zu lang
* funktioniert nicht auf Mulitprozessor-Systemen
**Konsequenz**:
* wird nur in BS für 1 CPU Rechner genutzt und da nur im BS-Kern.
#### Implementierung mit HW Unterstützung // FOLIE 73
**Vorteil**:
* funktioniert im MP-Fall
* es können mehrere KA so implementiert werden
**Nachteil**:
* busy waiting
* hohe Busbelastung
* ein Thread kann verhungern
* nicht für Threads auf demselben Prozessor
**Konsequenz**:
* geeignet nur für Kurze KA bei kleiner CPU-Anzahl
#### Lösung nach Peterson //FOLIE 79-82
**Vorteile**:
* funktioniert im MP Fall
* es können mehrere KA so implementiert werden
* keine HW Unterstützung nötig
**Nachteile**:
* busy waiting
* hohe Busbelastung
* (vielleicht nur für 2 Threads?!)
#### Semaphore
```
class SemaphoreT {
public:
SemaphoreT(int howMany);
//Konstruktor
void down();
//P: passeren = betreten
void up();
//V: verlaten = verlassen
}
```
> A mutex is used for mutual exclusion. A region of code that begins with a call to acquire a mutex, and ends with a call to release the same mutex, can only have one thread in the code at a time.
> A semaphore is used for flow control, to restrict the number of threads executing a block of code that begins with a call to acquire the semaphore, and ends with a call to release the semaphore.
oder
> A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section.
> A semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore).
* z = Counter Zählvariable
* q = Warteschlange
Initialisierung:
* z := Anfangswert (max. Anzahl von Threads, die KA gleichzeitig betreten dürfen)
* q := leer
* P: prüft ob z ≤ 0 --> wenn ja, blockieren --> wenn nein, in kritischen Abschnitt gehen und z := z - 1
* V: setzt z := z + 1, wenn q nicht leer --> freisetzen (wake up)
Semantik z:
* z > 0 : Anzahl Threads, die KA noch betreten können
* z = 0 : KA gesperrt für weitere Threads
* z < 0 : nicht möglich bei dieser Implementierung
**Vorteile**:
* kein busy-waiting
* einfache Nutzung
**Nachteile**:
* Gefahr von Programmierfehlern (Bsp. V() vergessen)
* Restriktionen: setzt Betriebssystem-Unterstützung voraus
* warten auf einen von mehreren Semaphoren nicht möglich
-------------------------------------------------------------------------------------------
# Verklemmungen
Eine Menge von Prozessen heißt verklemmt, wenn jeder Prozess dieser Menge auf ein
Ereignis wartet, das nur von einem anderen Prozess dieser Menge ausgelöst
werden kann.
## Charakterisierende Bedingungen
**Notwendig ist einzeln jede der Bedingungen**:
1. gegenseitiger Ausschluss bei Benutzung von BM
2. Nachfordern von BM (hold and Wait)
3. keine Verdrängung (Entzug der BM) möglich
4. zyklische Wartesituation
* Hinreichend ist:
- (1) AND (2) AND (3) AND (4)
## Gegenmaßnahmen:
* Gegenseitiger Ausschluss (Mutual Exclucion)
- z.B. Spooling -> nur ein Prozess (Daemon) erhält BM
* Nachfordern
- Postulat: alle BM müssen bei Start angefordert werden
- Freigabe aller BM bei Neuforderung
- Problem: Dynamik, BM-Auslastung
* Nicht-Verdrängbarkeit
- bei logischen Betriebsmitteln (Transaktionen)
* Zyklische Wartebedingung
- sorgfältige Betriebsmittelzuteilung (BMZ)
## sorgfältige BMZ
* Postulat:
- Anforderung der BM in festgelegter Reihenfolge
* zahlreiche Einzelsitiationen in Betriebssystemen
## Bank-Algorithmus für 1 Betriebsmittel-Typ
* Gegeben:
- Prozesssystem P
- maximale Anzahl G von BM-Exemplaren
- maximale Anzahl KP von BM-Exemplaren, die Prozess P<sub>i</sub> ∈P im Laufe seiner Existenz benötigt mit KP ≤ G
* Zustand
- Vektor der momentan den Prozessen zugeteilten BM-Exemplare
Ein Zustand heißt *sicher*, wenn
* keine Verklemmung vorliegt
* es eine Reihenfolge der Erfüllung aller Anforderungen gibt, ohne dass eine Verklemmung auftritt
Andernfalls heißt der Zustand *unsicher*.
Idee des Bank-Algorithmus:
Zuteilung nur vornehmen, wenn Nachfolgezustand immer noch sicher ist, andernfalls muss Prozess warten.
* Probleme:
- Komplexität: O(2n) n: Anzahl der Prozessen
- Mehrere BM-Typen: mehrere "Währungen"
- Basis: maximale Anzahl genutzter BM-Exemplare, Kenntnis, Eintreten dierser Situation
- Blockierdauer nicht kalkulierbar
## Entdecken und Beseitigen
Symptom:
Operation dauert wesentlich länger als erwartet, z.B. TIMEOUT als
zusätzlicher Parameter blockierender Operationen:
Diagnose:
Feststellen ob zyklische Wartebedingung vorliegt
Therapie:
* Verdrängung von Betriebsmitteln
* Entfernen von Prozessen
* Zurücksetzen
- regelmäßiges Erstellen von Rücksetzpunkten
- Zurücksetzen vor die verursachende BM-Anforderung
- Außenwelt-Problem
- Transaktionen
Falls das vermeiden zu aufwendig ist, müssen Verklemmungen erkannt und behoben werden können.
----------------------------------------------------------------------------------------
# Quantitative Methoden
**Problem: Erfüllen von QoS-Anforderungen mit zeit- bzw. größenbeschränkten Ressourcen**
## Scheduling
#### Begriff
Vorgehensweise zur **Einplanung** von Aufgaben, die durch ein aktives Betriebsmittel zu bearbeiten sind
**Entscheidungsstrategien** legen die Reihenfolge fest, in der sich Prozesse
um den Prozessor bewerben bzw. in der sie aus einer Warteschlange
ausgewählt werden.
Aufgabe der Schedulingtheorie ist es solche Strategien zu entwickeln und zu bewerten
#### Ziele
* hohe Prozessorauslastung η / U
* größtmöglicher Durchsatz D
* minimale Gesamtbearbeitungszeit t<sub>g</sub>
und
* geringe durchschnittliche Verweilzeit t̄<sub>v</sub>
* minimale Antwortzeit
* garantierte Reaktionszeit
! Diese beiden Gruppen sind nicht vereinbar
* Gerechtigkeit
#### Einordnung und Abgrenzung
* Ablaufpalnung (Teilgebiet der Operationsforschung)
* Prozessauswahl (System-S.) - Prozessorzuteilung (Dispatching)
* Strategie - Algorithmus - Implementation
#### Ablaufplan (Schedule)
zeitabhängige Zuordnung von Prozessen zu Prozessoren
#### Klassifikationsgesichtspunkte
* Ein-/Mehrprozessorsysteme
* Bearbeitung ohne/mit Prozessorentzug
* Deterministische/probabilistische Modelle
* Echtzeitbedingungen
#### Modellannahmen
Gegeben:
* J = \{J<sub>1</sub> , ... , J<sub>n</sub>\} - Menge von Jobs
* R ⊆ J × J - Präzedenzrelation
* t: J → ℝ<sup>+</sup> - Abbildung, wobei t(J<sub>i</sub> =: t<sub>i</sub>)
#### Deterministische Modelle
* Vorgangsknotennetz:
- Knoten stellen die Prozesse da. Es wird die Ausführzeit drangeschrieben.
Knoten können mehrere Ausgehende Pfeile und mehrere Eingehende Pfeile haben
* Vorgangspfeilnetz
- Pfeile stellen die Prozesse da. Es wird die Ausführzeit drangeschrieben.
Pfeile können mehrere Inputs haben, dürfen aber nur einen Output haben.
Um Vorgangsknotennetz zu Vorgangspfeilnetz zu überführen sind Scheinvorgänge
nötig.
#### Scheduling in 1-Prozessor-Systemen ohne Entzug
#### Scheduling in 1-Prozessor-Systemen mit Entzug
#### Scheduling in Mehrprozessor-Systemen
* *m* identische Prozessoren. Enumeration: Aufwand O (e<sup>jobanzahl</sup>)
* **Optimalitätskriterium t<sub>g</sub> → Min!**
- R bel.: polynomialer Algorithmus nur für m = 2, t<sub>i</sub> = const. bekannt
- R = ∅:
+ m = 1 trivial
+ m > 1: Approximation
+ **LPT** "Largest Processing Time"
* **Optimalitätskriterium t̄<sub>v</sub> → Min!**
- R = ∅: SPT ist optimal (sonst NP-vollständig)
## Echtzeit-Scheduling
#### Grundbegriffe
* **Job** (Planungseinheit für Scheduling)
- e = Ausführungszeit, Bearbeitungszeit (execution time)
- r = Freigabezeit, Bereitzeit (release time)
- d = Zeitschranke, Frist (deadline)
* **Task** (Menge "zusammengehörender" Jobs)
- Speziell: **Jobnetz** oder **periodische Tasks**
* **Deadline**
- hart / weich
* **Schedule**
- zeitliche Zuordnung von Jobs zu Prozessoren
- gültig: Zuordnung verletzt keine der gegeben Bedingungen (valid)
- ausführbar: alle Zeitschranken werden eingehalten (feasible)
* **Scheduling**
- Einplanung: Vorgehen (Algorithmus), das bei gegebener Taskbeschreibung einen Ablaufplan bestimmt
- Prozessor-Zuordnung: Auswahl eines Jobs durch Scheduler des Systems
* **Einplanbarkeit**
- Taskmenge einplanbar (schedulable, feasible) bei einem Scheduling-
Algorithmus, wenn der Algorithmus einen ausführbaren Ablaufplan erzeugt
* **Admission** (Zulassung)
- Verfahren, das die Einplanbarkeit einer Taskmenge entscheidet
* **Optimalität** bzgl. Einplanbarkeit
- eines Scheduling-Verfahrens in einer Klasse C von Verfahren:
- erzeugt für jede Tasktmenge T einen ausführbaren Ablaufplan, sofern T
überhaupt mit einem Verfahren aus C eingeplant werden kann
#### Modellannahmen Echtzeit-Scheduling
jede Task T<sub>i</sub> ist persiodische Folge von Jobs mit der Peropde p<sub>i</sub>
p<sub>i</sub> ist zugleich Zeitschranke. Die Bearbeitungszeit e<sub>i</sub> ist konstant
Prozessor ist entziehbar
Task sind von einander unabhängig
#### Verfahren
**RMS** "Rate Monotonic Scheduling"
statische Taskpriorität proportional zu Ankunftsrate
EDF "Earliest Deadline First"
**Optimalitätseigenschaft**
RMS ist optimal in der Klasse aller statischen, EDF in der Klasse aller
(dynamischen) Scheduling-Algorithmen (in Einprozessor-Systemen für
unabhängige, verdrängbare Tasks)
**Existenz eines Ablaufplans**:
</xmp>
<!-- MARKDOWN ......................... -->
<script src="strapdown.js"></script>
</html>