概论

操作系统分类

手工操作
单道批处理：串行执行作业
多道批处理：宏观并行运行，微观串行运行。内存管理、内存保护、CPU调度、进程通信
分时系统：CTSS、MULTICS、UNIX 通道技术：用于控制IO设备和内存间数据传输，有专用IO处理器，启动后独立于CPU 中断：CPU收到外部中断信号后，停下来处理中断事件，完成后回到断点继续工作
实时系统实时性：对请求严格时间范围内做出反应可靠性：高度可靠实时过程控制：工业、军事控制。实时通信处理：电信、银行、飞机订票
嵌入式操作系统 VxWork、嵌入式Linux、uC/OS-II、Windows CE、PalmOS
PC DOS系列、Windows系列、Unix系列
分布式操作系统计算机连接在一起，以获得极高运算能力（云计算）和广泛的数据共享（云储存）。实现处理上的分布，功能和任务的分布。

OS需要的硬件特性

受保护的指令

访问硬件资源、访问IO设备、对内存管理状态操作（页表、段表、TLB）、某些特殊状态位的设置、停机指令
管态：特权态、系统态、内核态
目态：普通态、用户态
PSW，包括CPU的状态码、条件码和中断屏蔽码，判断是系统程序or用户程序
管态->目态：设置PSW实现
目态->管态：系统调用。

系统调用

CPU执行访管指令，引起访管中断
处理器保存断点程序上下文环境（PSW、PC和其他寄存器），CPU切换到管态
中断处理程序调用相应的系统服务
中断处理结束后，恢复中断程序的上下文环境，CPU恢复目态继续执行

内存保护

基址寄存器+边界寄存器

中断机制

由于某事件发生改变了CPU上指令执行顺序
CPU暂停，保留现场，转去执行相应程序。执行完毕后返回断点继续
同步中断：CPU执行指令时由CPU控制单元发出的中断，也叫“异常”
- CPU检测到的异常 Fault、Trap、Abort。如算术溢出、除0、用户态使用特权指令
- 程序设定的异常即程序员通过int、int3指令发出的请求中断（软中断），实现系统调用
异步中断：其他硬件设备在任意时刻发出的中断，每个中断有一个0-255整数（中断向量）表示
- 可屏蔽中断：即IO中断，当外部设备或通道操作正常结束或发生错误产生的，如打印机完成或缺纸、读磁盘时驱动器无磁盘等
- 不可屏蔽中断由掉电、存储器校验错误等硬件故障引起的硬件中断

IO系统

时钟

分时系统中时间片轮转
实时系统中输出正确时间信号给实时控制设备
记录用户和系统所需的绝对时间

死锁问题

条件

互斥
请求和保持条件
不可抢占条件
环路等待条件

对策

无为而治
死锁检测和解除
- 检测算法
  - 单资源：检测封闭环路
  - 多资源：不断找既不阻塞又非独立的进程节点，消去请求和分配。若所有孤立则无死锁
- 解除算法
  - 剥夺资源（危害取决于资源性质）
  - 进程回退（定期备份不同时刻进程状态，死锁后回退，不野蛮但存储和计算代价高）
  - 撤销进程（一直撤销进程直到解除）
动态避免
- 安全检查：银行家算法:如果安全就分配。但无用：不知道请求矩阵，进程个数不确定，资源个数不确定
死锁预防
- 破坏互斥条件：允许多个进程使用同个资源（假脱机打印），不普适
- 破坏请求和保持条件：只允许一次请求所有资源:不知道需要多少、效率低。若申请时先释放所有可能饿死
- 破坏环路等待条件：资源编号，按序申请。可避免死锁，但存在无法获取到全部资源的风险

存储管理

单道程序存储管理

内存分为系统区和用户区。应用程序装入用户区，和OS共享内存。结束后被新程序覆盖。
简单开销小易于管理，适合单用户单任务。但只能运行一个程序，内存效率不高，程序bug会破坏OS，地址空间有限。

分区存储管理

又把用户区划分若干分区，每个进程一个分区

固定分区存储管理

分区大小、位置、个数不变。多小分区适量中等少量大。输入队列处理多个进程内存分配表：分区号+地址+长度+状态+进程名字内存分配：先放入输入队列，然后最先匹配、最佳匹配等。回收简单内存利用率不高，内碎片多。总数固定不灵活。地址大小有限。

可变分区存储管理

从空闲区划分内存给他，结束后释放
避免内碎片，提高内存利用率。但有外碎片，且回收、分配、管理更复杂
分区链表：占05-空53-占86-...
分配方法
- 最先匹配法：碰到第一个足够的，一分为二
- 下次匹配法：记录当前位置（头指针移动）
- 最佳匹配法：大小最接近的，外碎片难以利用
- 最坏匹配法：找最大的
- 内存回收：trivial

页式存储管理

划分为物理页框，逻辑页面，不必连续
页表：系统为每个进程建立一个页表，给出逻辑页面号和物理页面号的对应
物理页面表：系统内设立。位示图描述物理页框分配情况。256个物理页面可用8个32位的字
- 分配：检查是否还有N个空闲。若有则申请一个长度为N的页表，并把地址填入PCB。分配N个物理页框，编号填入页表，修改位示图，加N
- 回收：根据编号计算位示图位置，写0，减N
页号=地址/大小，偏移=地址%大小
页表保存在内核中，有PTBR指示基址，PTLR指示大小
每次访问内存需要两次访问用TLB缓存常用页表项
没有外碎片，内碎片大小平均半页。程序不必连续存放，便于管理。但程序必须全部装入内存，每个进程都需维护页表

段式存储管理

单个地址空间不利于存储保护和存储共享
以段为单位进行分配
段表：系统为每个进程建立段表，存储的段号对应的起始地址和长度
划分模块，可以分别编写、编译、保护、共享，无内碎片。但有外碎片，程序需全装如内存

段页式存储管理

先分段，然后分页。内存划分按段式，以页面为单位分配
段表：记录了每个段的页表起始地址和段长（而非段的起始地址）
页表：每个段有一个，一个进程可能有多个。

虚拟存储技术(TLB,Cache)

局部性原理：顺序执行、循环结构、数组操作
虚拟页式：只装程序部分页面。可发出缺页中断请求换页。使用后备存储和后备页面
页表表项：逻辑页号、物理页号、驻留位、保护位、修改位、访问位
缺页中断：若有空闲物理页面则分配，否则替换一个，然后继续运行。若修改过则写回
置换算法
- 最优页面置换（OPT）（不现实）
- （最近）最久未使用（LRU）（开销大，缺乏硬件支持）
- 最不常用（LFU）设置访问计数器，淘汰最小
- 先进先出（FIFO）选择驻留时间最长的，性能较差
- 时钟页面置换（Clock）若被访问后置1，缺页后指针旋转，0则淘汰1则置0
举例：不同输入下系统策略的比较
- LRU=FIFO 123412341234
- LRU>FIFO 123124252
- FIFO>LRU 123142314
- LRU>Clock 123213414

工作集和驻留集

工作集：进程当前使用的逻辑页面集合，W(t,delta)，t为时刻，delta为容量（从t往前找delta个）
驻留集：实际驻留在内存的逻辑页面集合
固定分配：驻留集大小固定，各进程平均分配or按比例分配。采用局部页面置换，但分配难以确定。少则抖动大则浪费
可变分配：全局页面置换，各并发进程竞争使用物理页面。性能好但开销大。
缺页率算法：根据缺页次数/内存访问次数（或缺页平均时间间隔倒数）调整这和置换算法、分配物理页面数、页面大小和程序编制方法（比如循环ij和ji）有关。
页表结构
- 多级页表：32位，4K，则20位逻辑页面号，12位页内偏移地址。前10位以及页表，接下来二级页表
- 反置页表：根据物理页面号组织页表，作为索引。常用Hash
缺段中断：内存够则装入，不够则紧缩或者淘汰一些段（虚拟段式存储）
32bitwindows：内核中每个段有一个VAD，描述逻辑地址范围、是否共享、是否继承、保护属性

进程管理

进程

进程=代码+数据+寄存器+堆栈+系统资源
进程的特性：动态性、独立性、并发性
运行->阻塞：等待输入运行->就绪：切换了进程就绪->运行被选择阻塞->就绪等待发生
系统为每个进程维护一个PCB。操作系统维护运行、就绪、阻塞队列

线程

线程：并发执行，可以共享地址。进程=线程+资源平台。
代码、数据、文件共享，栈、程序计数器和寄存器私有（线程优先级）。
进程是资源分配的单位，线程是CPU调度单位。

进程间通信

低级：只传送状态和整数。高级：任意数量信号量、信号、共享内存、消息传递分为直接（套接字）和间接通信、管道

进程互斥

临界区：完成访问共享内存、文件的程序
临界资源：需要互斥访问的共享资源
互斥访问
- 任何两个进程不能同时进入临界区
- 不能事先假定CPU个数和运行速度
- 进程运行在临界区外不能妨碍其他进程进入
- 任何一个进程进入的要求在有限时间得到满足

基于关闭中断

进入临界区后关闭所有中断（用来更新内部变量、链表）
有可能临界区大量计算；不适用用户进程(忘记开启中断)；不适用于多CPU

基于繁忙等待：

方法1：while(lock);lock=1;do;lock=0类似图书馆借书，但可能出现lock的竞争
方法2：强制轮转while(turn!=0);do;turn=1另一个对偶。保证只有一个进程，但违反第三个条件。
方法3：Peterson方法调用enter和leave判断是否安全。

1
2
3

void enter(int process)
{other=1-process;interested[process]=1;turn=other;while(turn==other && interested[other]==true);}
void leave(int process){interested[process]=0;}

繁忙等待浪费CPU，且低优先级在临界区，高优先级也想进入会死锁
解决：无法进入后应该sleep，退出后应该wakeup别人。
信号量：操作系统维护。用户进程只能初始化和PV原语。A先VPB后

进程调度

何时调度：1.新进程2.进程结束3.进程阻塞4.IO完成5.时间中断。不可抢占调度1-3发生。可抢占1-5发生
批处理：不可抢占交互式：必须抢占实时系统：可抢占
周转时间T=E-S。平均周转时间。平均带权周转时间：W=Sigma(T/r) / N, r是实际
等待时间：位于就绪队列时间响应时间：请求到相应的时间
吞吐量：单位时间完成作业数。CPU利用率、设备均衡利用（搭配）
调度算法
- FIFO/FCFS按作业到达次序
- SJF预计执行时间，先完成短的
- RR就绪进程按FCFS排成队列。轮流执行时间片。公平有保证。Q小花销大，q大退化成FCFS。通常20-50ms
- 优先级算法：SJF把需要用时作为优先级。
- 静态优先级：低优先级可能饥饿
- 动态优先级：可根据运行时间和等待时间调整优先级防止饥饿。
- 可以不同优先级别分组，然后级别间优先级算法，同级别内时间片轮转。
- 有锁的话可能出现优先级反转
- 多级反馈队列算法：引入多个就绪队列，根据进程性质、类型分为若干子队列有不同优先级。前台交互式进程RR，后台批处理FCFS等。根据进程的运行反馈信息调整队列。
- 新进程优先级高。若时间片未用完升级，否则降级。高优先级低时间片。IO繁忙的高优先级，CPU繁忙的低优先级减少调度次数。

IO

IO管理

机械部分（设备本身）+电子部分（设备控制器（芯片）or适配器（印刷电路卡），完成设备和主机通讯）

IO通信

IO独立编址控制器每一个寄存器分配唯一port
内存映像编址把寄存器映射为内存地址编程方便，但无cache，需要判断IOor内存
混合编址寄存器-独立，缓冲区-内存

IO控制

程序循环检测方式（轮询、繁忙等待）程序(驱动)不断检测IO状态（就绪or完成），CPU控制IO 浪费太多CPU
中断驱动方式 IO完成后，控制器通过bus向中断控制器发出信号，如果接受，就将设备编号放在地址线并令CPU中断。CPU根据编号访问中断向量表，取出中断程序地址然后执行，最后向中断控制器发出确认信号
1. CPU向设备控制器发出命令，启动读操作
2. 设备控制器控制IO设备完成读操作，把数据保存在寄存器或缓冲区，中断CPU
3. CPU把数据读入内存
直接内存访问方式 DMA访问系统总线，代替CPU指挥IO和内存间数据传送有寄存器如内存地址寄存器、字节计数器、多个控制寄存器（指出端口地址、数据传送方向、传送单位、字节数）
1. CPU对DMA控制器编程，告诉他把什么数据传送到内存什么地方，并向磁盘控制器发出命令，让它去磁盘驱动器读入所需的数据块，保存到内部缓冲区，并验证数据正确性。
2. DMA控制器通过总线向磁盘控制器发出读操作，并把写入的内存地址打在Bus上
3. 磁盘控制器取出一个字节，按地址写入内存
4. 磁盘控制器向DMA发送确认信号，DMA吧内存+1，计数器-1
5. DMA向CPU发送中断，告诉数据已完成

IO接口

设备独立性用户无需制定特定的设备类型
统一命名所有文件和设备采用相同的命名规则：路径名
阻塞和非阻塞IO 进程启动系统调用后，是立即返回还是阻塞起来

设备驱动和中断处理

方案1 用户—系统调用—设备驱动—IO（驱动阻塞）—中断信号—中断例程接管CPU唤醒驱动只适用于互斥访问设备
方案2 请求队列 IO请求的提交和实现分离。上层函数管理请求队列，底层函数负责硬件完成IO 用户—内核—上层函数—提交请求，阻塞—底层取出请求—完成请求可以优化IO请求（如数据块重组）

设备独立的IO软件

给上层应用统一接口
给驱动程序统一接口
提供设备无关的数据块大小
缓冲技术

用户空间的IO软件

库函数 write、read，把参数传给系统调用，后者完成实际IO
Spooling技术多道系统中处理独占设备的方法。Virtual IO

磁盘

扇区为最小寻址和存取单位，先移动磁头定位柱面，选中磁头等待扇区到达
低级格式化：标出磁道和扇区，扇区=相位编码+数据+纠错码
分区：划分为若干逻辑分区，每个分区可视为独立磁盘。第0扇区存放boot和分区表（起始扇区和大小）
高级格式化：对每个逻辑扇区，生成引导块、空闲存储管理结构、根目录和空白文件系统

磁盘调度

柱面定位时间+旋转延迟时间+数据传送时间

10000rpm，300扇区，512字节，读150kb，柱面平均6.9ms，旋转平均旋转时间一半（3ms），数据传输17微秒
300个连续扇区：6.9+3+6=15.9
随机300个：(6.9+3+0.017)*300
一般柱面定位时间最久

调度算法

FCFS先来先服务，简单公平但效率不高
SSTF最短定位时间优先：性能好但两侧柱面有可能饥饿
电梯算法：上界是柱面总数两倍

文件系统

文件

命名：文件名.扩展名
结构：无结构的字节流序列，以块为单位，包含若干个扇区
分类：普通文件(ASCII、二进制文件)、目录文件
属性：保护信息、创建者、只读、隐藏、系统、时间(创建、访问、修改)、长度

文件系统的布局

低格为若干个分区，主磁盘的0扇区为MBR，MBR结尾是一个分区表，记录每个分区的起始扇区和大小。

文件的物理结构

FCB是OS管理文件的结构，存放文件所有管理信息，文件存在的标志 FCB包含文件的类型、长度、所有者、访问权限、创建、访问、修改时间、物理块信息

连续结构容易实现、访问速度快、有外碎片、难以动态增长用于早期、DVD
链表结构指针存在块内，顺序访问而不适合随机访问，速度慢，文件内容不对齐
带FAT的链表分离指针和文件数据，只需一次外存访问 表项的宽度=XX(物理块编号的位数) FAT表项个数=物理块个数 FAT大小=个数*宽度 FAT容量=个数*块
索引结构每个文件都有I结点存在FCB，逻辑快与物理块映射，只装载正在用的节点进内存

目录项：直接法=文件名+FCB，间接法=文件名+FCB地址。给定名字返回FCB 每个目录项32字节，文件名(8+3)，属性1字节，创建时间日期各2字节，起始物理块编号2字节，长度4字节
外存：目录结构、FCB
内存：系统文件表（计数+FCB）、进程文件表（打开方式+读写指针+系统表指针）
- 文件组织成索引文件，磁盘块512byte，文件10+1+1+1，每个地址2字节
- 一个文件最多 10+2⁸⁺²16+2^24 个文件页

空闲空间管理

位图法 16G硬盘物理块1KB。则有16M bit=2M byte=2048物理块
链表法空闲物理块上有指针
索引法拿物理块存放空闲物理块编号，自身不分配

操作系统与安全

计算机安全的三个目标

数据的私密性
数据的完整性
系统的可用性

数据加密

私钥加密：加密解密都是秘密，两者简单对应。简单安全，但密钥传送有问题
公钥加密：加密密钥无法推算解密密钥。二者互反。无需传密钥
数字签名：MD5,SHA

用户认证

基于用户名密码的认证：易于理解实现，输入保护攻击：穷举法猜测用户名和密码。多线程回避次数限制
基于用户所拥有的东西（塑料卡片、磁条卡、芯片卡）
基于用户自身生物特征（指纹、声纹、视网膜、笔记）

系统内部攻击：

特洛伊木马(Trojan Horse)：无害程序内嵌破坏代码，用户“自愿”运行
登陆欺骗(Login Spoofing)：运行自己的login程序，盗窃用户名和密码，钓鱼网站
逻辑炸弹(Logic Bomb)：员工植入代码。若在岗则定期输入密码，辞退则引爆，破坏文件
后门(Trap Door)：系统中嵌入代码能绕开正常检查
缓冲区移除(Buffer Overflow)：攻击C语言缺少数组边界检查

外部攻击

病毒

一段代码附着在宿主程序复制传播，可感染可执行程序、内存、引导扇区、驱动、宏。
可执行程序病毒：动静太大容易察觉，重复感染，文件修改时间和大小，变覆盖为寄生
常驻内存病毒：躲在两段，修改中断，运行在内核态，感染系统调用。需内存冷启动，bios放电清理，然后用光驱、软驱启动，杀毒。
宏病毒：文档嵌入，文档操作（打开、关闭、激活）时可能激活

蠕虫：躲在内存，传播但不更改系统，通过网络传播

(1)程序是静态的，而进程是动态的；(2)程序是永久的，进程是短暂的；(3)程序的组成是代码，进程由程序、数据和进程控制块组成；(4)一个程序可以对应多个进程，通过调用关系，一个进程也可以包括多个程序；(5)进程可以生成其他进程，而程序不能生成新的程序。(5分)

【Note】 操作系统笔记

概论