C语言

指针

指针的读取规则：

教程：http://unixwiz.net/techtips/reading-cdecl.html

[] 数组和 ()函数从左向右读取，* 和 & 从右向左读取

go right when you can, go left when you must

long **foo[7];
// 是一个二级指针的数组,表示7个二级指针   **foo -> *foo -> long
unsigned long int **x();
// 表示函数， 函数返回值是 unsiged long int**
char *(*(**foo [][8])())[];
// foo is ... char
//   *foo[] => go rihgt => foo is a array ... char
//   *foo[8] => go right => foo is a array of array of 8
//   **foo  => go left => foo is a array of array of 8 pointer to pointer
//   *foo() => go right => foo is a array of array of 8 pointer to pointer to function returning ... char
// char *(*foo)[]; => go left => returning pointer to
// *foo[] go right => returning pointer to array of pointer to char

操作系统

Einfürung

操作系统的任务
操作系统怎么完成这些任务
操作系统怎么限制用户的使用

计算系统定义(Rechensystem)

计算系统是开放的，动态的，技术的系统

计算系统可以

存储
处理详细
交流通信

开发系统

开发系统有组件构成

组件之间的连接成为依赖(Abängigkeiten)

有给外部开发的接口

接口

接口可以有不同的视角来看

从外面：黑盒视角 Black-Box-Sicht

组件的总结
从里面：白盒视角 White-Box-Sicht

子系统划分

动态的系统

一些性质可以用来描述一个系统的状态。这些性质是随着时间变化的。性质的变化就是系统状态的变化。而状态的变化就描述了系统的行为。系统通过主动的元件（CPU）和被动的元件（内存）。主动的元件的行为会改变系统状态。被动元件帮助主动元件行为

技术的系统

计算系统是用硬件和软件实现的。下图展示了操作系统在计算系统的位置

操作系统定义

操作系统本身是一个程序。他控制和监管系统程序和应用程序。他给引用程序提供了一个和硬件交互的接口。

这些接口可以是读写操作，存取操作

操作系统任务

抽象化 Abstraktion

简化，分配抽象的原件和共同的接口。比如文件

资源管理

操控检查程序的执行

影响操作系统发展的因素

硬件技术
数据计算的传递
新的应用场景

操控种类

批处理 Stapelverarbeitung
交互操控 Transaktionsbetrieb
窗口操控 Dialogbetrieb
实时处理 Echtzeitbetrieb

操作系统种类

服务器操作系统 Server-Betriebssystem
- SuperMUC, MPI
- Dedizierte BS für Datenzentren
服务器和桌面操作系统Server- und Desktop-Betriebssystem
- Linux, Windows, MacOS
移动系统 Mobile Betriebssystem
- Android, IOS
嵌入式系统 Eingebettete Betriebssystem
- QNX, L4, PikeOS, TinyOS, RTOS, RIOT

基础概念

资源和它的分类
进程是抽象化的处理器
文件是抽象化的存储器
操作系统模式
系统调用

资源的分类

使用次数 Anzahl der Nutzung
- 只能用一次，可以用多次
并行 Paralllelität
- 可以并行
持续性 Dauerhaftigkeit
- 可打断，不可打断
中心资源 Zentrale Ressouren
- 处理器，内存
边缘资源 Periphere Ressourcen
- 存储单元

进程

一个进程是一个执行的程序

线性进程和并行进程

线性进程是控制流程，和指令计数器
多线程进程是有很多控制流程，每个线程都有子集的指令计数器和寄存器，每个线程都用自己单独的栈

文件和文件系统

比如这样的结构

操作系统模式 Betriebssystem-Modi

用户模式 Benutzermodus (User Mode)

不能直接接触硬件

不能运行有权限的指令

只能读取虚拟地址

系统模式 Systemmodus(Kernel Mode)

有权限的模式：可以执行所有命令

直接控制硬件

系统调用

它提供与硬件交互的接口

比如 open, close, read, write , mkdir, rmdir, link

操作系统架构

单片机系统 Monolithisches System

比如 Unix/Linux

它完全在 Kernel Mode 上
有高的运行优先度

Mikrokerne

比如 L4, PikeOS, Mach, QNX, MINIX

系统编程

系统编程就是写系统程序

进程和进程管理

进程在栈中

比如

进程的状态

add 添加一个新的进程
assign 分配CPU资源
block 由于输入输出或者协同的调用，线程在等待
resign 线程重新回到ready状态
retire当前计算的进程终止
swap out 当前的线程转移到硬盘上
swap in 当前线程从硬盘上转移过来

多线程的原因

Overhead
Performance

进程的实现

Process Control Block

操作系统的任务

生成进程
结束进程
分配CPU
调度CPU

进程调度策略

First-Come First-Served

先到先得策略

Shortest-Jobs-First

最短的先

Round Robin

维护一个按index排序的队列，然后循环队列每个干一点。

多线程系统和同步

Sequetielle und Parallele Programme

一个程序实现一个算法，一个程序是一系列的指令

Sequentielle Programmausführung

程序的结果是确定的。相同的程序出相同的结果
多线程程序运行

一个程序分成多个执行的序列

有许多的CPU和核心共同跑程序

程序的结果不是确定的

Interaktion 交互

同时运行的程序可以相互交互

Kausale Beziehungen

比如信号灯和行人的交互
Kommunikation

相同计算系统或者不同计算系统的处理器交换信息
Koordinierung

比如 Clinet- Server
Konkurrenz

多个进程使用同一个资源

描述一个多线程的活动

我们可以用不同的抽象层面描述

Modell- Ebene

关注行动和依赖关系
Programmiersprachen-Ebene

线程。fork, join, send, recv, lock, unlock 等等
Betriebssystem-Ebene

程序使用的自己的地址，进程的线程共享一个地址空间

描述活动的行为

Aktion动作

比如C指令，及其指令
Ereignisse 事件

可以产生影响的单位

多线程系统的特征

确定性 Determiniertheit

相同的条件产生相同的结果
Störungsfreiheit

并行的进程之间互不影响
Wechselseitiger Ausschluss exklusiv nutzbarerer Ressourcen

对于一个相同的点，最多只有一个进程访问同一个资源
Verklemmungsfreiheit 死锁

相互循环等待，无法继续
Kein Verhungern

不存在无限推迟运行的进程

同步

Race Codition:

竞争冒险（race hazard）又名竞态条件、竞争条件（race condition），它旨在描述一个系统或者进程的输出依赖于不受控制的事件出现顺序或者出现时机。此词源自于两个信号试着彼此竞争，来影响谁先输出。

举例来说，如果计算机中的两个进程同时试图修改一个共享内存的内容，在没有并发控制的情况下，最后的结果依赖于两个进程的执行顺序与时机。而且如果发生了并发访问冲突，则最后的结果是不正确的。

至少2个进程读写同一个资源，结果取决于进程执行的顺序

Kritischer Abschnitt

临界区段（Critical section）指的是一个访问共享资源（例如：共享设备或是共享存储器）的程序片段，而这些共享资源又无法同时被多个线程访问的特性。

当有线程进入临界区段时，其他线程或是行程必须等待（例如：bounded waiting 等待法），有一些同步的机制必须在临界区段的进入点与离开点实现，以确保这些共享资源是被异或的使用，例如：semaphore。

在临界区段里，很多进程同时访问一个资源，

线程必须协调来避免竞争条件

进入临界区段的步骤

执行非临界区段的代码
进入临界区段
执行临界区段的指令
离开临界区段

Wechselseitiger Ausschluss互斥锁（Mutex）

实现互斥锁的要求

临界区段不可以进行交换
实现不可以依赖于进程的执行顺序
实现不可以依赖于进程的运行时间
进程不允许无休止的干扰其他进程进入临界区段

Automare Maschinenbefehle

TLS (Test-and-Set Lock)

enter_crit_region:
    tsl rax, [lock] ; Copy lock to rx
    ; and set lock to 1
    cmp rax, $0 ; Was lock zero?
    jne enter_crit_region ; Busy-Waiting
    ret ; Process can enter
    
leave_crit_region:
    mov [lock], $0 ; Reset lock to 0
    ret

Semaphore 信号量

信号量（英语：semaphore）又称为信号标，是一个同步对象，用于保持在0至指定最大值之间的一个计数值。当线程完成一次对该semaphore对象的等待（wait）时，该计数值减一；当线程完成一次对semaphore对象的释放（release）时，计数值加一。当计数值为0，则线程等待该semaphore对象不再能成功直至该semaphore对象变成signaled状态。semaphore对象的计数值大于0，为signaled状态；计数值等于0，为nonsignaled状态.

Mutex

二进制的信号量

定义：• Ein Mutex ist ein binäres Semaphor, mit s ∊ {0; 1}

Monitore 管程

管程 (英语：Monitors，也称为监视器) 是一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。这些共享资源一般是硬件或一群变量。管程实现了在一个时间点，最多只有一个线程在执行管程的某个子程序。与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。

Verhungern

Es gibt keine Prozesse, deren Ausführung unendlich lange aufgeschoben wird, obwohl sie nicht in einem Deadlock sind

Deadlocks

定义

Zyklische Wartesituation zwischen mehreren Prozessen: jeder dieser Prozesse wartet auf ein Ereignis, das nur ein anderer Prozess aus dieser Menge verursachen kann

出现死锁的条件（4个同时满足）

Exklusiv nutzbare Ressource 互斥

资源只能同时分配给一个行程，无法多个行程共享。
Belegen und Anfordern 持有和等待

进程占用资源，然后取找其他资源了
Nicht Entziehbar 禁止抢占

系统资源不能被强制从一个进程中退出。
Zyklische Wartebedingung 循环等待

一系列进程互相持有其他进程所需要的资源

Bankier-Algorithmus

并发系统建模

动作结构

定义

$E^*$ 事件的集合
$A$ 动作的集合

三元组 $p=(E, \le, \alpha)$ 是进程 $p$ 的动作结构，若满足

对于事件集合满足 $E \subseteq E^*$
$\le$ 是在 $E$ 上的 partielle Ordnung
映射 $\alpha:E\rightarrow A$ 是动作标记
$\alpha$ 把每个事件和动作一一对应

进程的性质

在一个进程里，每个事件是唯一的
可能存在不同的事件有相同的动作
对于一个进程 $p=(E, \le, \alpha)$ ，我们说两个事件 $e_1,e_2 \in E$ 是并发的，若
- $\neg(e 1 \leq e 2 \lor e 2 \leq e 1)$
一个进程是有限的，若事件集合有限
一个进程是序列的sequentiell, 若关系 $\le$ 是一个线性关系

动作间的因果关系

真因果关系

$e$ 是 $d$ 的原因，若 $d$ 没有 $e$ 永不发生
时间关系

$e$ 的结束在 $d$ 的开始之前

因果关系可以推出时间关系
系统限制

$e$ 不允许与 $d$ 并发运行

序列化

通过序列化可以简化并发过程

我们可以通过拓扑排序来序列化。

状态自动机

佩特里网 Petri-Netze

它是一个除了 Aktionsstruktur 图形化建模的另一种选择数

定义

它是一个三元组 $(S,T,F)$ ,

$S$ 是位置 Stelle(用圆形表示) , 它可以表示被动单元如存储单元
$T$ 是传递 Transition(用方形表示)，它可以表示动态单元如进程
S 和 T 没有交集
$F$ 是 Flussrelation , $\mathrm{F} \subseteq(\mathrm{S} \times \mathrm{T}) \cup(\mathrm{T} \times \mathrm{S})$
$F$ 在图上面用有向箭头表示
对于一个节点$x \in (S \cup T)$来说
- Vorbereich: $\cdot x=\{y \mid y F x\}$ 是前驱
- Nachbereich: $x^{\bullet}=\{y \mid x F y\}$ 是后继

比如下面这个就是一个Petri-Netze

改善

佩特里网可以一步步简化

Transition 可以简化成一个黑盒
总的结构保持不变
里面的结构可以还有Stelle 和 Transition

佩特里网的动态表现

定义：标记网Markiertes Netz,Stellen-Transitonsnetz

给定一个佩特里网 $(S,T,F)$

一个 Stelle 的 Kapazität 是一个映射 $c: S\rightarrow \mathrm{IN} \cup \{\infin\}$ 如果没有默认标记为 $\infin$
一个边的重量 Gewichtung 是映射 $\mathrm{w}: \mathrm{F} \rightarrow \mathrm{IN} \cup\{0\}$ 如果没有默认标记为 $1$

一个 Stellen-Transitionsnetz 是一个以自然数标记的网络: $M: S \rightarrow N$

自然数标记的 Stellen 是这个网络的状态
必须满足 $\forall s \in S ,M(s) \leq c(s)$
一个标记也可以说是一个 Token

一个条件/布尔网络也可以 $M: S \rightarrow IB$

定义：开关条件

给定一个佩特里网 $(S,T,F)$ , 函数 $c,w$ 和开始标记 $M_0$

状态转移在打开一个 Transiton 后开始
Transition 的打开时间在这个模型中忽略不计

一个 Transition $t \in T$ 可以打开，若

$s t $ 满足 $\mathrm{M}(\mathrm{s}) \geq \mathrm{w}((\mathrm{s}, \mathrm{t}))$

$\forall s \in t \cdot$ 满足 $\mathrm{M}(\mathrm{s}) \leq \mathrm{c}(\mathrm{s})-\mathrm{w}((\mathrm{t}, \mathrm{s}))$

开启之后，状态的变化后的 $M'$ 是

$s t t $ 满足 $\mathrm{M}^{\prime}(\mathrm{s})=\mathrm{M}(\mathrm{s})-\mathrm{w}((\mathrm{s}, \mathrm{t}))$

$s' tt $ 满足 $\mathrm{M}^{\prime}(\mathrm{s'})=\mathrm{M}(\mathrm{s'})-\mathrm{w}((\mathrm{t}, \mathrm{s'}))$

$s'' t t $ 满足 $\mathrm{M}^{\prime}\left(\mathrm{s}^{\prime \prime}\right)=\mathrm{M}\left(\mathrm{s}^{\prime \prime}\right)-\mathrm{w}\left(\left(\mathrm{s}^{\prime \prime}, \mathrm{t}\right)\right)+\mathrm{w}\left(\left(\mathrm{t}, \mathrm{s}^{\prime \prime}\right)\right)$

其他的满足 $\mathrm{M}^{\prime}(\mathrm{s})=\mathrm{M}(\mathrm{s})$

建模系统性质

子系统 Nebenläufige Systeme

例子：4个活动 $t1,...,t4$ ，

$t1$ 结束后，开始 $t2,t3$

s在 $t2,t3$ 结束后才能开始 $t4$

非确定性

下面的那个标记不一定会走哪一边

可到达性 Erreichbarkeit

一个网络可以从一个状态到达另一个状态吗

定义：Erreichbarkeit

给定一个佩特里网 $(S,T,F)$ 和一个标记 $M$

一个有限的序列 $\rho=t_{1}, t_{2}, \ldots, t_{n}$ 是 $M$ 的激活序列，那么 \[ M_{0} \stackrel{t_{1}}{\longrightarrow} M_{1} \stackrel{t_{2}}{\longrightarrow} \ldots \stackrel{t_{n}}{\longrightarrow} M_{n}, \text { also } M_{0} \stackrel{\rho}{\longrightarrow} M_{n} \] $M'$ 是从 $M$ 可以到大的，若存在一个从 $M$ 到 $M'$ 的序列

活跃性 Lebendigkeit

定义 : Lebendigkeit

给定一个佩特里网 $(S,T,F)$ 和一个开始状态 $M_0$

这个网络是活跃的，若对于每个可到达的 $M$ ，并且对于每个Transition $t \in T$ 存在一个 $M'$ 使得，从 $M$ 可到达，并且 $t$ 是可以传递的

定义：Verklemmung

给定一个佩特里网 $(S,T,F)$ 和一个开始状态 $M_0$

从 $M_0$ 出发的一个可到达的状态 $M$ 是一个完全死锁，若它没有可以打开的 Transition

局部死锁 lokale Verklemmung

从 $M_0$ 出发可以到大的 $M$ 是局部死锁，若存在 $t\in T$ , 使得没有 $M$ 以及 $M$的后续状态 $M'$ 可以让 $t$ 继续传递

公平 Fairness

对于一个Transiton $t$ 是不公平 unfair 的，若 $t$ 可以无限次transitionsbereit

饥饿 Verhungern

一个 $t$ 是饥饿的，若存在一个无穷序列，其中 $t$ 没有出现过

进程通信 IPC

通信的带宽

窄带通道 Schmalbandige Kanäle

携带少量信息，事件，需要同步和打断

比如Linux的信号

宽带通道 Breitbandige Kanäle

携带大量信息

隐式通信

在共同的操作媒介上的隐式通信

Vorteil: Einfach und schnell, da kein Kopieren zwischen Adressräumen

例如：存储器，寄存器，文件

显示通信

发送信息

如: send, recv 函数

同步和异步

进程间的耦合度 Kopplungsgrad

同步：两个进程间在信息传递的时候同步，阻塞。

异步：结合发送和收取，非阻塞。

异步通知 Asynchrone Meldung

发送端把消息发送给操作系统的消息处，然后接收者接收消息。如果没有消息，那么接收端会阻塞。其中发送端不会等待接收端接收到消息，发送端非阻塞。

同步通知 Synchrone Meldung

发送选发送消息后，会阻塞并且等待接收端确认收到消息。

同步和异步的优缺点

Vorteile von asynchronem Senden:

Nützlich für Echtzeitanwendungen, wenn sendender Prozess nicht blockiert werden darf
Ermöglicht parallele Abarbeitung durch Sender und Empfänger
Anwendbar zum Signalisieren von Ereignissen

Nachteile

Verwaltungsoverhead im Betriebssystem (Puffer für Nachrichten)
Behandlung von Fehlern schwieriger
Keine direkte Benachrichtigung des Senders möglich
Paketverlust (durch volle Puffer, insbesondere bei Netzkommunikation)
Wiederholung von Paketen

存储管理

Von-Neumann-Flaschenhals

Der Von-Neumann-Flaschenhals bezeichnet die zunehmende Diskrepanz der Geschwindigkeiten von Prozessor und Hauptspeicher.

Dem Problem begegnet man üblicher Weise durch Einführung einer Speicherhierarchie.

要求

理想世界

内存无限大，无限快
现实

高速的内存很贵
结果

大量的数据存储在较慢的硬盘里

处理数据，先加载到内存中

内存资源很少
其他问题

处理器一直在进步，但是内存读取时间没有

存储器层次

地址空间概念

管理物理存储器

所有程序有对物理存储器的全部的存取权限
问题
- 每个程序可能会占用整个内存
- 程序可能会让在内存中的操作系统瘫痪
- 程序会互相干扰
解决办法：抽象化物理内存
- 引入地址空间的概念
- 进程可以读取的虚拟的存储单元
- 每个进程有独立的地址空间

通过操作系统管理地址空间

内存的物理地址空间
- 从0开始的带编号的字节
- 一个字节的位置(物理地址) 描述了它在物理上的内存地址
进程的逻辑地址空间
- 可以访问的存储集合
- 用虚拟地址来描述它在逻辑地址空间的位置
- 在一个4GB大小的逻辑地址空间使用大小为32bit的地址
内存映射
- 从逻辑地址空间映射到物理地址空间

直接寻址

每个虚拟地址对应一个物理地址

比如：8080, Z80, 6502

多个程序可以在这里运行
选择1：交换
- 在每个时间点只允许1个程序运行
- 如果要运行其他程序，那么先把当前的运行状态保存到硬盘里
- 很慢
选择2：重定位
- 程序在不同的位置加载
- 加载的时候需要再计算物理地址的位置
- 代价昂贵
- 程序会相互影响

基地址寻址Basis-Adressierung

每个进程有个基地址
在进程开始时，基地址会加载到 Basisregister 里
地址计算
- 物理地址=逻辑地址+基地址
优点：
- 操作系统可以可以移动在内存中的程序 relocation
- 多个进程可以同时在内存中
缺点：需要很多加法操作，代价昂贵

段寻址 Segmentadressierung

把地址空间分成不同长度的逻辑线段
- 比如进程有： Stack- , Daten-, Code-Segment
线段化的使用
- 不同线段有不同权限
段寻址：每个段都需要
- 一个段开始地址，对应基地址
- 段的长度
CPU有一个Segmentregister

段寻址：交换Swapping

有时候内存会满
进程会暂时放在硬盘上
如果有空间了还会放回来

如果程序增长会怎么样

空余内存分配

空闲内存管理的数据结构
- Bitmap
- 链表
空闲存储区域管理的策略
- First Fit，Next Fit，Best Fit，Worst-Fit
- Buddy算法

数据结构：Bitmap

把内存分为相同大小的块
改内存占用了则为1，空闲则为0

问题：选择块的大小
- 块太小：需要的Bitmap很大
- 块太大：浪费内存的风险
Bitmap的有点

简单快速的读取速度
缺点

若进程P要k个主内存块，那么久需要k个连在一起的内存块. 那么就需要线性查找的时间。

链表

给定若干长度为b的内存块
操作系统维护一个存放连接内存块的链表
每个区域要么是有个进程P，要么空闲F
每个列表的格子包含
- 该区域的开始地址
- 区域长度
- 指向下一个格子的指针

优点

弹性的内存分配
缺点

线性查找，没有固定管理结构，会动态增长
优化方案
- 分离出占用和空闲两个链表
- 对大小排序
- 用树结构管理

占用策略Belegungstrategien

内存释放和空闲区域的合并
- 使用双向链表简化链表管理
- 优点：对起始地址排序

问题：不能合并空闲区域
后果：内存随时间肢解
需要高效的内存占用策略

First-Fit

从链表的开始寻找空闲区域
- 第一个空闲区域被占用
- 不需要的空间会加入到空闲列表
优点

简单，快速找到一个合适的空闲区域

Next-Fit

一种First-Fit
- 从上次占用区域开始寻找空闲区域

Best-Fit和Worst-Fit

Best-Fit

完全查找链表的空闲区域，最少的零头被占用
Worst-Fit

完全查找链表的空闲区域，最大的零头被占用

Buddy算法

管理内存大小为 $2^k$ 的块，其中 $l \le k \le u$
$2^l$ 最小的可被占用的内存块
$2^u$ 最大的可被占用的内存块
通常来说 $2^u$ 是整个可以占用的内存

内存占用

开始有一个长度为 $2^u$ 大小的连续区域
系统为长度为$2^i$的块管理一个空闲链表
开始只有一个链表，管理大小为 $2^u$ 的块
占用大小为 $s$ 区域的要求
- 若 $2^{u-1}<s\le 2^u$
  
  那么那么整个空闲的 $2^u$ 大小的块被占用，并且从空闲链表中移除
- 否则
  
  这个块会从$2^u$ 的空闲链表中移除，并且分成2个大小为$2^{u-1}$ 的块。如果大小合适 $2^{u-2}<s\le2^{u-1}$ 那么就停止，否则继续分解，知道最小的块被找到

评价

非常快速实现，有效率的查找
零头最多是一半的块
融合很快速

分段Fragmentierung

内部分段

在块状分配内存是需要
外部分段

虚拟存储Virtueller Speicher

问题

虚拟进程地址空间会比现有的物理内存的大小大

手动分配虚拟地址很麻烦

操作系统应该自己解决这个问题
解决方案：虚拟内存管理Paging

分页Paging

虚拟地址空间被分成很多页
内存是分成很多物理框架的Kacheln
操作系统的任务是把分页映射到物理框架上

分页表

管理从分页到框架的映射

操作系统为每一个程序管理一个分页表

交换进程的时候，新的程序分页表的开始地址会加载到CPU的分页表寄存器Sitentabellenregister里
页错误

在调用一个没有框架的虚拟地址
嵌入页

若所有框架都被占用，那么页必须被更换

计算地址映射

虚拟地址 $v=(s,w)$ ，s是分页表的编号，w是偏移量

物理地址 $p=(k,w)$，k是框架的编号

例如下面是一个例子

16Bit虚拟地址空间，4K的分页表大小。这说明地址空间被分成16页，需要4Bit表示分页编号，12bit表示4096Byte的偏移量

MMU内存管理单元

Memory Management Unit是硬件的一部分，用于计算地址。

地址映射很非时间，用缓存来解决

TLB

Translation Lookaside Buffer

从分页映射到内存的缓存，先在TLB查找，如果找不到，再到映射表里面找

分页错误

当Pbit没有被设置
硬件出错
出错后运行Page-Fault-Handlers

查找过程

FIFO策略

每次弹出最老的那一页。这样就没办法考虑“经常性使用的变量”

文件系统

文件系统的要求

Speicherplatz für (sehr) große Datenmengen bereitstellen
Datenverlust vermeiden
Nebenläufigen Zugriff auf Daten ermöglichen

文件

Dateien als zu verwaltende Einheiten

Dateien können von unterschiedlichen Prozessen genutzt werden
Dateien müssen benannt werden: bei ihrer Erzeugung erhält eine Datei einen Namen

文件类型

普通文件 Dateien (engl. regular files) enthalten Benutzerdaten
- Textdatei, Binärdateien
Verzeichnisse
字符特殊文件 Character Special Files

用于串行IO设备
块特殊文件 Block Special Files

磁盘类文件

文件访问

Sequential access
- Geeignet für Magnetbänder als Speichermedium, aber unflexibel
Random-access
- Random-access ist essentiell unter anderem in Datenbanksystemen • Der lseek Systemcall unter UNIX erlaubt es, die aktuelle Position in der Datei zu spezifizieren • Beispiel: lseek (fd, 10, SEEK_SET);

文件属性

文件操作

Erzeugen und Löschen einer Datei

Open: Vor einem Zugriff auf eine Datei muss diese geöffnet werden • Damit lädt das BS die Dateiattribute und andere Infos in den Hauptspeicher, für eine schnelle Bearbeitung wichtig • Open liefert einen Datei-Deskriptor als Ausgabe, das ist ein kleiner Integerwert
Unlink: entfernt eine Datei

Nachfolgende Zugriffe auf die Datei unter Nutzung des Deskriptors.

Close: Angabe des Datei-Deskriptors, Freigabe von internen Datenstrukturen, manche BS erlauben nur eine festgelegte Zahl von offenen Dateien pro Prozess
Read: Angabe der gewünschten Daten und Angabe eines Puffers, in den die Daten geschrieben werden sollen.
Write: Schreiben von Daten an der aktuellen Position Daten werden ggf. überschrieben
Seek: Positionieren des Datei-Zeigers auf eine spezifische Position (ab der gelesen oder geschrieben werden soll)

文件夹

Single-Level Verzeichnisstrukturen

Hierarchische Verzeichnisstrukturen

路径名

绝对路径 Absolute Pfadnamen
相对路径 Relative Pfadnamen

文件系统的实现

文件系统布局

磁盘被划分为分区Partitionen 磁盘的0区是主引导记录Master Boot Record (MBR)

MBR 的结尾是分区表。在计算机被引导时候，MBR先确定活动分区，入去引导块，并执行。引导块中的程序将装载该分区中的操作系统。

文件的实现

连续分配 Contiguous Allocation

把每个文件作为一连串的数据存储到磁盘上 Vorteile: • Einfache Implementierung • Speichern der Adresse des ersten Blocks und Anzahl der Blöcke pro Datei • Lesen ist sehr performant • Nur eine Positionierungs-Operation für den Schreib/Lesekopf notwendig, um die gesamte Datei von der Platte einzulesen • Nachteile • (Externe) Fragmentierung • Mit der Zeit entstehen “Löcher” von freien Speicherbereichen • Defragmentierung des Speichers ist sehr zeitaufwendig

链表分配 Linked List Allocation

为每个文件创建磁盘块链表。每个块的第一个字作为指向下一个块的指针，块的其他部分存放数据

Vorteile • Es geht kein Speicherplatz verloren • bis auf interne Fragmentierung im letzten Block • Nachteile • Niedrige Performance bei Random-Access • Um Block n zu finden, müssen die ersten n−1 Blöcke gelesen werden • Festplattenzugriff ist sehr langsam. • Größe des verfügbaren Speichers in einem Block keine 2er-Potenz • Zeiger auf den nächsten Block nimmt Platz im Block ein • Operationen nutzen i.d.R. Blockgrößen als Parameter • zum Lesen eines Bereichs, der eine Blockgröße umfasst, müssen 2 Blöcke geladen werden

Linked List Allocation mit File Allocation Table (FAT)

采用内存中的表进行链表分配：去除每个磁盘块的指针字，把他们放在内存的一个表中。这样的表格叫文件分配表 File Allocation Table (FAT)

i节点（i-node）

给每个文件富裕一个称为i节点的数据结构，其中列出了文件属性和文件块的磁盘地址。给定i节点，就能找到文件的所有块。

Vorteile • Ein i-node muss nur für eine geöffnete Datei in den Speicher geladen werden • Speicherbedarf proportional zur Anzahl von Dateien, die gleichzeitig geöffnet sein dürfen (nicht zur Festplattenkapazität) • Nachteile • Jeder i-node enthält eine feste Anzahl an Blockadressen: begrenzt max. Dateigröße • Umgehung: Der letzte i-node Eintrag zeigt auf einen Block mit weiteren Blockadressen

存储的Einträge

• Typ (FIFO, Character device, Directory, Block device, Regular file, Symbolic link, Socket), • Besitzer (User und Gruppe), • Dateirechte, • verschiedene Timestamps (created, accessed, modified), • Anzahl der Hardlinks die auf den Inode verweisen, • Anzahl der Blöcke, • verschiedene Flags, • Adressen der referenzierten Blöcke (Single-, Double-, Triple-Indirection)

目录的实现

目录的任务：Pfadname auflösen, Datei auf der Festplatte finden

Verzeichniseintrag

Verzeichnisse bestehen aus einer Menge von Verzeichniseinträgen • Beispiel: /home/eva, /home/heinz, /home/karl • Verzeichnis /home enthält 3 Dateien, mit jeweils einem Eintrag in /home

不同的维护操作

把文件属性直接放在目录项中Direkt im Verzeichniseintrag

Annahme, dass Dateinamen eine kurze (maximale) Länge haben • Wie können wir längere Dateinamen mit variabler Länge verwalten? • Dateinamenlänge limitieren • z.B. auf 255 Zeichen • Nicht alle Dateinamen sind gleich lang • Verschwendung von Speicherplatz

In den i-nodes • Verzeichniseintrag besteht nur aus dem Dateinamen und einer i-node Nummer.

erzeichniseinträge mit Referenzen zum Heap, der die Datei-Namen speichert • Vorteil: Keine Fragmentierung beim Löschen von Dateien. Ein neuer Eintrag wird immer an die Stelle des gelöschten Eintrags passen • Problem • Suchen von Dateien in Verzeichnissen mit vielen Einträgen ist langsam

共享文件

C的文件同时出现在B的目录下，这样的练习叫链接 link，这样文件系统是一个有向无环图。 Zwei Ansätze

Hard Links • Verzeichnisse verweisen auf i-nodes • i-nodes beschreiben die Dateien • Weitere Verweise auf i-nodes z ulassen • Keine Unterscheidung zwischen 1. und n. Link • i-nodes erhalten Reference Counts • Zeigt an, wann die Datenstruktur freigegeben warden kann • Erklärt den Namen des Systemcalls zum Löschen unter UNIX: unlink()

删除时的i-node：

Der Linkzähler wird um eins dekrementiert. Falls er danach auf 0 steht, wird die Datei tatsächlich gelöscht.

Symbolic Links • Erzeugen einer besonderen Datei mit Verweis auf die verlinkte Datei durch Angabe des Pfadnamens (je nach Länge in i-Node oder Datenblock)

删除时的i-node：

nichts passiert

Journaling-Dateisysteme

日志结构文件系统 (Log-structured File System, LFS)

虚拟文件系统VFS

把多种文件系统统一成一个有序的结构。

VFS stellt einheitliche (POSIX) Schnittstelle zur Verfügung • open, read, write, lseek usw.

文件系统优化

Buffer Cache缓冲区告诉缓存

虚拟化

虚拟化的要求

Equivalence / Fidelity • Betriebssysteme und Anwendungen funktionieren ohne Änderungen • Ggf. minimale Änderungen / Ergänzungen am Gast-BS • Verhalten sich genauso wie auf einem nativen System
Resource Control / Safety (Isolation) • Hypervisor muss in Kontrolle sein • Hypervisor schützt Ressourcen vor und Gast-BS gegeneinander
Efficiency / Performance • Die meisten Instruktionen müssen ohne Intervention des Virtualisierungssystems ausgeführt werden • Virtualisierungssystem fügt eine weitere Software-Schicht hinzu (Overhead)

系统虚拟机

Virtual Machine Monitor (VMM) – Hypervisor

System Virtual Machines

Virtual Machine Monitor (VMM) – Hypervisor – bietet eine Laufzeitumgebung für Betriebssysteme

Typ 1 Hypervisor: Direkt auf der Hardware ausgeführt z.B. Xen, Hyper-V, VMware ESX
Typ 2 Hypervisor: Verwendet Dienste des Host-BS z.B. KVM, VirtualBox, VMware Workstation

Ein Typ I Hypervisor läuft direkt auf der Hardware, wobei ein Typ II Hypervisor als Teil des Betriebssystems ausgeführt wird.

原因

Emulation • Betriebssysteme können auf verschiedenen ISAs ausgeführt werden • Debuggen von BS in Virtuellen Maschinen ist oft bequemer als auf der echten Hardware („Bare-Metal“) • ISA-Design: eine ISA ist einfacher in SW zu implementieren als in HW
Isolation • Verschiedene BS laufen isoliert in einer VM auf der gleichen HW • Sandboxing von Gast-Betriebssystemen • Ein kompromittiertes Gast-BS kann weder den Zustand weiterer VMs auf dem System noch den Hypervisor selbst manipulieren
Sicherheit • Security-Mechanismen im BS können durch Malware umgangen oder ausgeschaltet werden • Hypervisor ist leichter zu sichern (kleiner, höhere Privilegien) • Sicherheitsmechanismen für Gast-BS können im Hypervisor plaziert werden
Ressourcennutzung • Hardware-Ressourcen können besser (flexibler) ausgeschöpft werden

CPU-虚拟化

Paravirtualization

在VM中修改的操作系统,

Gast VM 和 BS 合作
Binary Translation
Hardware-assisted Virtualization
Privileged Instructions
Sensitive Instructions
Innocuous Instructions

Hohe Komplexität im Hypervisor → Binary Translation,

Dedizierte Geräte Treiber kommunizieren mit dem Hypervisor durch sog.

Hypercalls → Para Virtualization,

Benutzung von Intel VT-x, AMD-V, etc. → Hardware-assisted Virtualization,

Kooperation zwischen dem BS in der Gast VM und dem Hypervisor → Para Virtualization,

Hypervisor interpretiert/emuliert (Teile des) Binärcode(s) der Gast-VM in Software → Binary Translation,

Modifiziertes Betriebssystem in VM → Para Virtualization

内存虚拟化

Betriebssystem hat normalerweise uneingeschränkte Kontrolle über den physischen Speicher • Verwalten virtuellen Speicher für Prozesse • Seitentabellen zur Abbildung auf den physischen Speicher
Durch Virtualisierung konkurrieren plötzlich mehrere BS • Hypervisor ist die übergeordnete Instanz

Shadow Page Tables (SPT)

影子页表(shadow page table)

Second Level Address Translation (SLAT)

I/O-Virtualisierung

Full Virtualization/Emulation • Hypervisor multiplext oder emuliert virtuelle I/O-Geräte in Software • Gast-I/O-Anfragen vom Hypervisor abgefangen und an das I/O-Gerät geleitet • Vorteile • Gemultiplexte I/O-Geräte sind effizient • Transparentes Geräte-Management • Probleme • Hohe Komplexität in Software • Hypervisor benötigt Treiber für viele I/O-Geräte • Falls Geräte emuliert werden müssen, so entsteht ein hoher Overhead
Paravirtualization • Verwendet eine Split-Driver-Architektur • Backend-Treiber: Dedizierte privilegierte VM greift direkt auf Geräte zu • Frontend-Treiber in Gast-VMs kommuniziert mit dem Backend-Treiber • Vorteile • Geringer Overhead • Im Vergleich zu Full Virtualization leichter zu implementieren • Adaption für Gast-BS: z.B. neue Geräte mittels bestehender Treiber anbieten • Probleme • Benötigt Modifikationen/Treiber im Gast-Betriebssystem

Container

Namespaces

Bieten per Namespace eine isolierte Sicht auf globale Ressourcen (Prozesse, Netzwerk, Mount-Points, etc.).

Control Groups

Systemressourcen werden für Prozessgruppen allokiert/limitiert und überwacht.

SECCOMP

Secure Computing Mode(SECCOMP) Systemressourcen werden für Prozessgruppen allokiert/limitiert und überwacht.

考试复习

Betriebsmodi

Benutzermodus 用户模式 Ausführung von Benutzer Prozessen kein direkter Zugriff auf Hardware kein oder nur lesender Zugriff auf Systemcode oder Dateien
Systemmodus 系统模式 Ausführung des Betriebssystemkerns Ausführung von privilegierten Befehlen

Systemaufruf系统调用

在Benutzermodi 不会直接系统调用函数而是通过和Systembibilothek连接，调用的。系统调用会导致，从用户模式转化到系统模式系统调用是通过TRAP指令(SysCall)来实现的

Systemcalls bieten dem Benutzermodus die Möglichkeit z.B. auf die Hardware zugreifen zu können.

Eine Anwendung ruft im Benutzermodus eine Bibliotheksfunktion auf (z.B. printf).Bibliotheksfunktion ruft den Systemcall auf. Der Systemcall unterbricht den Prozess und wechselt in den Systemmodus, in dem er ausgeführt wird. Nachdem der Systemcall beendet ist wird der Prozess im Usermodus weiter ausgeführt.

所有systemcall的列表：

https://blog.csdn.net/wukery/article/details/79295567

读取文件最后200byte

• open: Öffnen der Datei. • seek|lseek: Setzen der Position auf die relative Länge - 200 Byte. • read: Lesen des Inhalts der Datei in einen Puffer. • printf: Ausgeben der Datei auf die Standardausgabe. • close: Schließen der Datei.

内存分配

局部变量在Stack里，malloc的再堆里，地址指针的大小是和计算机的位数一样（64bit就是8Byte的指针）

POSIX函数

Pipe

Eine Pipe ist ein unidirektionaler Kommunikationskanal und hat damit immer ein lesendes und ein schreibendes Ende.

• socket: Öffnen eines neuen Sockets. X • connect: Verbinden des Sockets zu einem Server. X • bind: Binden des Sockets an einen Port. X • listen: Warten auf eine neue eingehende Verbindung. X • accept: Offen der eingehenden Verbindung als eigener File Deskriptor. X • close: Schließen der Datei.

例如：

• Server: socket, bind, listen, accept, close (pro Client Socket), close (Server Socket) • Client: socket, connect, close

内存分配

Problem direkter Adressierung des physischen Arbeitsspeichers

Jedes Programm belegt potentiell den gesamten Hauptspeicher
Maximal ein Prozess pro Zeiteinheit im Speicher
Programme können das ebenfalls im Speicher befindliche Betriebssystem unbrauchbar machen
Der Adressraum eines Prozesses ist beschränkt durch die Größe des physischen Speichers

Adressierungen

• Direkter Adressierung: Jede logische Adresse entspricht ihrer physischen Adresse. • Basisadressierung: Die Berechnung der physischen Adresse erfolgt beim Addieren der logischen und der Basisadresse. • Seitenadressierung: Das Betriebssystem verwaltet eine Seitentabelle, die virtuelle Adressen auf physische Adressen abbildet.

Fragmentierung

Fragmentierung handelt es sich um Speicherbereiche, die nicht mehr verwendet werden können. • Interne Fragmentierung: Ungenutzte Bereiche eines Blocks (wenn Dateigröße << Blockgröße) • Externe Fragmentierung: Dateien werden wenn möglich in aufeinanderfolgenden Blöcken gespeichert. Wenn nur noch einzelne Blöcke und keine langen Bereiche zusammenhängender freier Blöcke vorhanden sind, spricht man von externer Fragmentierung.

• Interne Fragmentierung: Verkleinerung der Blockgröße. • Externe Fragmentierung: Neuordnung (Defragmentierung) der fragmentierten Blöcke.

Belay-Anomalie

Die Belady-Anomalie kann beim FIFO-SeitenersetzungsverfahrenXauftreten. Sie beschreibt, dass das Erhöhen der Kachelzahl in einem Rechensystem zu mehr SeitenfehlernXführen kann (anstatt intuitiv zu weniger).

多线程系统

PCB

Der Scheduler wählt gemäß seiner Schedulingstrategie einen Prozess aus der Liste der rechenwilligen Prozesse, der als nächstes die CPU zugewiesen bekommen soll.

• Der Dispatcher ist für den eigentlichen Kontextwechsel zuständig. • Z.B. Bei preemptive Scheduling-Strategien, entzieht der Dispatcher dem rechnenden Prozess die CPU und weist sie dem nächsten, vom Scheduler ausgewählten Prozess zu. • Der PCB enthält alle für diese Aufgaben relevanten Informationen und Datenstrukturen

Datenstrukturen beim Prozesskontrollblock (PCB) für einen Prozesswechsel benötigt werden

• Run Queue:Verwaltet Prozesse, die sich im Zustand rechenwillig befinden. Der Scheduler entscheidet, welcher dieser Prozesse als nächstes die CPU bekommen soll. • Wait Queue:Verwaltet Prozesse, die blockiert bzw. im Zustand wartend sind. Der Dispatcher legt blockierende Prozesse in die Wait Queue.

Schedulingverfahren

• Batch-Systeme: – FCFS (non-preemptive), SJF (non-preemptive), SRTN • Interaktive Systeme: – Round-Robin (preemptive), Priority Scheduling (preemptive) • Echtzeit Systeme:
– EDF (preemptive/non-preemptive) – RMS (non-preemptive)

Preemptive Scheduling : Prozesse können vom Scheduler unterbrochen werden (SRTN ) • Non-Preemptive Scheduling : Der aktuell ausführende Prozess wird so lange ausgeführt bis er (i) terminiert oder (ii) blockiert (SJF ).

SRTN Scheduling ist die unterbrechbare Variante von SJFX. Das Problem an SRTN ist, dass man die Rechenzeit der Prozesse im Voraus kennen muss . Dies ist in der Praxis nicht immer möglich

Kontextwechseln

• Die Aufgabe wird vom Dispatcher übernommen. Dieser entzieht dem rechnenden Prozess die CPU und teilt sie einem rechenbereitem Prozess zu. • Ändern des Zustands des rechnenden Prozesses zu wartend oder rechenbereit. • Sichern des PCB (TCB) des alten Prozesses • Laden des PCB des neuen Prozesses • Ändern des Zustands des neuen, rechenbereiten, Prozesses zu rechnend.

Thread und Prozesse

Prozesse besitzen einen eigenen (virtuellen) Adressraum.

Threads führen den Programmcode aus und teilen sich die Ressourcen (den Adressraum) eines Prozesses

Um Race Conditions zu vermeiden müssen Threads eines Prozesses synchronisiert werden

PID

Jeder Prozess hat eine eindeutige Prozess ID (PID) die den Prozess identifiziert.X • Jeder Prozess (bis auf Init) besitzt einen Vaterprozess. Diese Zuordnung wird in der Parent PID (PPID) verwaltetX. • Jeder Prozess inkl. Kinder formen eine Prozessgruppe (PGID)

Zombie und Waise

• Waisen: Der Kindprozess verwaist, wenn der Vaterprozess sich beendet, bevor der Kindprozess seine Ausführung beenden kann . • Zombies: Wenn sich der Kindprozess vor dem Vaterprozess beendet und der Vater nicht auf das Ende des Kindprozesses wartet, so wird der Kindprozess zu einem Zombie . • Dämonen sind Waisen-Prozesse.

Prozesskomunikation

• Signal: Benachrichtigungsmechanismus, der den Kontrollfluss eines Prozesses zu beliebigen Zeitpunkten unterbrechen kann. XEs wird ein Signal bei der Eingabe von Strg-c generiert und an den Laufenden Prozess gesendet. X • Pipe: Einseitiger Nachrichtenkanal. XZwei Pipes sind notwendig für bidirektionale Kommunikation (eine zum Schreiben, eine zum Lesen). Programme können sequenziel Daten verarbeiten, z.B. grep | sed | sort | uniq -c. X • Socket: Breitbandiger bidirektionaler Kommunikationskanal. XVerwendung u.a. für TCP/IP Verbindungen und höhere Protokolle.

死锁 Deadlock

Bei Deadlocks sind Prozesse blockiert, da sie auf Ressourcen warten, die zugleich von anderen Prozessen blockiert werden

Prevention und Avoidance

• Deadlock Prevention: Dafür sorgen, dass eine der vier Deadlock Bedingungen nicht erfüllt ist (die Bedingungen müssen nicht genannt werden sondern nur schreiben dass es sie gibt) • Deadlock Avoidance: Das Betriebssystem prüft dynamisch, ob eine Ressourcen-Anforderung erfolgen kann oder nicht (gegebenenfalls werden Ressourcen zurückgehalten, bis das der Fall ist).

Bedingungen für Auftreten

• Mutual Exclusion: XDie gemeinsam genutzten Ressourcen sind nur exklusiv nutzbar, d.h. eine Ressource ist entweder verfügbar oder genau einem Prozess zugeordnet.X • Hold-and-Wait: XProzesse, die bereits Ressourcen zugeteilt haben, belegen diese Ressourcen, auch wenn sie noch weitere Ressourcen anfordern.X • No-Preemption: XZugeteilte Ressourcen können einem Prozess nicht entzogen werden,d.h. die Ressourcennutzung ist nicht unterbrechbar.X • Circular Wait: XEs gibt eine zyklische Kette von min. zwei Prozessen, die jeweils auf eine Ressource warten, die vom nächsten Prozess in der Kette belegt ist.

活锁 Livelock

Prozesse geben freiwillig belegte Ressourcen ab, sobald sie merken, dass sie die nächste Ressource nicht belegen können. Sie blockieren nicht, sondern versuchen wieder die erforderlichen Ressourcen zu belegen. Obwohl beide Prozesse weiterhin ausgeführt werden, machen sie keinen Fortschritt

不同处

• Bei Deadlocks sind Prozesse blockiert, da sie zirkulär auf Ressourcen warten; • bei einem Livelock sind Prozesse blockiert, da sie zirkular auf exklusiv vergebene, nicht präemptive Ressourcen warten

Starvation

Starvation: Ein Prozess kann verhungern, wenn seine Ressourcenanfrage nie erfüllt wird, da stets andere (höher priorisierte) Prozesse Vorrang haben.

Singale

Zur Interprozesskommunikation

Das Signal kann ignoriert oder behandelt werden, sonst wird der Prozess terminiert.

syscalls:

singal, kill

Dateisystem

Unix Dateitypen

• Dateien (engl. regular files) beinhalten Benutzerinformationen. Man unterscheidet zwischen ASCII- und Binär-Dateien. • Verzeichnisse (engl. directories) sind Systemdateien zur Verwaltung des Dateisystems. Sie enthalten Verweise auf andere Dateien und Verzeichnisse und ermöglichen somit eine hierarchische Verwaltung. • Character Special und Block Special Files Xsind Gerätedateien für zeichen- und blockorientierte I/O Geräte. • Named Pipes Xsind unidirektionale Kommunikationskanäle. • Sockets Xsind bidirektionale Kommunikationskanäle.

Dateitypen erkennen

• Spezielle Magicnumbers können den Dateitypen repräsentieren.X • Unterschiedliche Dateiendungen (File Extensions)X, können vom Betriebssystem erkannt und interpretiert werden. (Somit erkennt das Betriebssystem zu welchem Programm die zu öffnende Datei gehört).

Inodes

Der Name einer Datei ist in den Daten des Inodes gespeichert, der das Verzeichnis darstellt, in dem die Datei referenziert wird.Dies liegt daran, dass eine Datei als Hardlink in mehreren Verzeichnissen mit unterschiedlichen Namen verlinkt sein kann.

speicherte Eintrag

Syscalls

ls

Verzeichnis öffnen; alle Einträge sukzessive lesen und die Dateinamen ausgeben , Verzeichnis schließen. opendir() , readdir() , closedir() – ggf. rewinddir()

FAT

Verwaltung als Linked List in einer Tabelle.

Man braucht einen Eintrag pro Block -> FAT wird groß

Hardlink und softlink

• Bei Hardlinks wird eine Datei I-Node aus mehreren Verzeichnis I-Nodes referenziert. X • Ein Softlink ist eine dedizierte I-Node, die den Pfad der Referenzierten Datei angibt.

Ein und Ausgabe

Arten von Geräten设备文件类型

设备文件分为字符设备(Block Device)和块设备(Character Device),这两种设备的本质区别在于他们是否可以被随机访问。典型的字符设备(不能随机读取)有:键盘、串口，典型的块设备(random access)有：硬盘，SSD，CD-ROM等。 ### DMA-Controller 直接存储器存储（Direct Memory Access）。

没有DMA时磁盘如何读:控制器从磁盘驱动器串行地、一位一位地读取一个块（或一个扇区），直到将整块信息放入控制器的内部缓冲区中。接着，计算校验合，以保证没有读错误发生，然后控制器产生一个中断。当操作系统开始运行时，它重复地从控制器的缓冲区一次一个字节或一个字地读取该块的信息，并将其存入内存中。

使用DMA时：

1、CPU通过设置DMA的寄存器对它进行编程，所以DMA控制器知道将什么数据传送到什么地方（图中第一步）。DMA控制器向磁盘控制器发出一个命令，通知它从磁盘读取到其内部的缓冲区中，并对其校验和检验。如果磁盘控制器的缓冲区中的数据是有效的，那么DMA就可以开始了。Programmiert DMA-Register

2、DMA控制器通过在总线上发出一个读请求到磁盘控制器而发起DMA传送。Disk-Controller muss Daten in Puffer bereitstellen

3、写到内存是另一个标准总线周期 DMA-Controller iniiert die Übertragung von Disk in RAM

4、当写操作完成时，磁盘控制器在总线上发出一个应答信号到DMA控制器。 Disk-Controller meldet (Ack) Beendigung der Übertragung

Datenaustausch mit einem Gerät

• Programmed I/O : CPU kopiert und wartet synchron darauf, dass das Gerät die jeweiligen Aktionen ausführt. • Interrupts : CPU initiiert das Lesen/Schreiben eines Datum, und das Gerät meldet asynchron, sobald die Aktion abgeschlossen wurde.(CPU kann in der Zwischenzeit was anderes tun, kopiert aber noch selbst.) • DMA : CPU konfiguriert DMA-Controller, der interagiert mit dem Gerät, stößt den Transfer an; Abschluss signalisiert ein Interrupt.

IO软件层次(Struktur eines E/A-Systems)

Hardware(硬件)

Interrupt-Handler(中断处理程序)

Device Drivers(设备驱动程序)

Device-independent operating system software(与设备无关的操作系统软件)

User-level I/O software(用户级IO软件)

RAID-Systeme

Raid: Redundant Array of Inexpensive (Independent) Disks(独立硬盘冗余阵列，简称磁盘阵列)

利用虚拟化存储技术把多个硬盘组合起来，成为一个或多个硬盘阵列组，目的为提升性能或资料冗余。

时钟

时钟的任务：

• Tageszeit und Datum verwalten(维护日时间)

• Prozesse unterbrechen und umschalten (Scheduling)（防止进程超时运行）

• Rechenzeitverbrauch eines Prozesses messen （对CPU使用情况进行记账）

• Zeitschaltuhren den Anwendungen zur Verfügung stellen （处理用户进程提出的alarm系统调用）

• Funktionsfähigkeitsüberwachung (watchdog timer) （为系统本身的各个部分提供监视定时器）

• Profiling, Monitoring, Statistik（完成概要剖析、监视和统计信息收集）

SoftTimer

• Soft-Timers reduzieren die Anzahl von InterruptsX, die sonst durch Hardware Timer erzeugt werden würden.X • Bevor das Betriebssystem den Kernel Mode verlässt, überprüft es ob einer der Soft-Timers abgelaufen ist. Falls ja, so wird das zugehörige Event behandelt.

终端

Line Descipline(行规范) • Zeilenweise Verarbeitung • Zeilen editieren • Echo-Funktion

Cooked Mode(Canonical Mode)(规范模式):

zeilenorientiert

Echo, Editieren (Backspace) usw.

Sicherheit 安全

目标

• Prüfung der Korrektheit der Identität der Akteure: Authentizität (engl. authenticity) 数据真实性

• Schutz der Daten gegen Manipulation: Daten-Integrität (engl. integrity) 数据完整性

• Schutz vor unberechtigten Zugriffen, Vertraulichkeit (engl. confidentiality) 数据保密性

• Nicht-Abstreitbarkeit von durchgeführten Aktionen (engl. non-repudiation) ->Verwandt: Accountability 问责制

• Gewährleistung der Verfügbarkeit (engl. availability) von IT-Diensten 系统可用性

Sicherheitskern (Trusted Computing Base)可信计算基

• Großteil der Hardware (außer E/A-Geräte, die die Sicherheit nicht beeinflussen) 大多数硬件

• Teile des Kerns oder der ganze Kern 操作系统核心的一部分

• Im Kern: Prozesswechsel, Speicherverwaltung und Teile des E/A-Management

• Alle Programme mit Superuser-Rechten (z.B: setuid-root-Programme) 所有掌握超级用户权限的用户程序

• TCB sollte so klein wie möglich gestaltet werden, um verifizierbar zu bleiben

Kryptographie(密码学)

Verschlüsselung

Symmetrische Kryptographie(加解密用同一密钥）

Asymmetrische Kryptographie(加解密用不同密钥) ist aufwendig

两者结合使用效率最高

Hashfunktion哈希函数

HMAC（Message Authentication Codes）消息认证码

是一种确认完整性并进行认证的技术

消息认证码的输入包括任意长度的消息和一个发送者与接收者之间的共享密钥。输出固定长度的数据，输出的数据就是 MAC 值。（关键：完整性和认证）

Digitale Signatur数字签名

Basiert auf asymmetrischer Kryptographie

Zertifikate证书

Authentifizierung认证

当人们试图登录系统时，大多数用户登陆的方法基于下列三个方面考虑：

Wissen: z.B. password, PIN, Krypto-Schlüssel 用户已知的信息
Besitz: z.B. Smartcard, USB Token, SIM Karte 用户已有的信息
Person (Biometrie): z.B. Fingerabdruck, Retina 用户是谁

Zugriffskontrolle

Speicherschutz (Robustheit)

Secure Boot

Angriffsmethoden

Buffer-Overflow

解决办法：

Stack Canaries

werden vom Compiler zwischen der Return Adresse und lokalen Variablen auf dem Stack einer Funktion eingefügt. Das Betriebssystem überprüft die Integrität des Stack
Data Execution Prevention(DEP) Der Stack wird vom Betriebssystem durch das NX-Bit (XN) als non-executable markiert und verhindert somit die Ausführung vom einem potenziell
Address Space Layout Randomization (ASLR)

randomisiert die Adresse des Stacks und erschwert dem Angreifer diesen zu finden.

Salt-Wert

• Das Passwort wird nicht im Klartext gespeichert; Eine kryptografische Hashfunktion ist nicht umkehrbar • Der Salt-Wert verhindert, dass gleiche Passworte unterschiedlicher Nutzer den gleichen Hashwert haben. • Salt verhindert, dass ein Angreifer Hashwerte für alle gängigen Passwörter vorberechnen kann (Rainbow Tables). Das ist zu aufwändig.

DEP

• Grundidee ist, dass kein Speicher gleichzeitig als ausführbar und schreibbar markiert ist. Damit kann kein neuer Code ins bestehende System eingeführt werden. • CPU-Feature NX-bit (No-eXecute) ermöglicht es, Seiten als nicht ausführbar zu markieren; Zusätzlich sollten ausführbare Seiten nicht schreibbar sein. • Durch DEP können Code-Reuse-Angriffe können nicht verhindert werden, da der Angreifer bereits vorhandenen Code in Speicher nutzt.

SETUID

• SETUID-Programme werden im Kontext der Benutzer-ID des Besitzers der Datei ausgeführt, nicht mit der des aufrufenden Nutzers. • Bugs in SETUID-Programmen ermöglichen die Komprommitierung des Besitzer-Accounts der Binary. (Privilege Escalation.) • /bin/passwd benötigt Lese- und Schreibzugriff auf die Datei /etc/shadow, welche nur von root gelesen/geschrieben werden darf.Das SETUID-Bit erlaubt es daher in diesem Kontext, dass ein Nutzer sein eigenes Passwort ändern kann.

Linker Loader

Relocation

Bibliotheksfunktionen: Load-Time-Relocation • Statische Funktionen gehören zu keiner Relocation-Klasse. Sie werden vom Assembler direkt aufgelöst. • Nicht-Statische Funktionen: Link-Time-Relocation