操作系统总结.doc

1
操作系统总结
第一篇：操作系统总结
第一部分概述
一、导论
1.
操作系统做什么
①
冯诺依曼体系结构
②
OS角色：对上：控制程序正确执行，使用方便；对下：资源分配器
③
核心功能：进程管理，内存管理，文件管理，输U调度
1.
基本概念
8
①
CPU区间和I/O区间的概念
②
抢占与非抢占调度的概念（发生在：一个进程从运行切换到等待、运行切换到
就绪、等待切换到就绪、以及终止，1,4非抢占，2,3抢占）
2.
调度准则：CPU利用率（使CPU尽量忙），吞吐量（测量工作的方法），周转时间（从
进程提交到完成的时间），等待时间，响应时间
3.
调度算法
①
先到先服务调度FCFS（非抢占的）
②
最短作业优先调度SJF（抢占，最优算法，难知道下一CPU区间长度，用于长
期调度）
③
最短剩余时间优先调度SRTF（强占式的SJF，适合长期调度）
④
优先级调度（问题：无穷阻塞或饥饿，老化来解决；非抢占方式不用占用CPU
9
切换）
⑤
轮转调度RR（专为分时系统设计，是可抢占的，时间片过大变为FCFS，时间片
过小等待时间段，但是切换频繁）
⑥
多级队列调度（前台与后台的调度算法不同，RR与FCFS）？
⑦
多级反馈队列调度
⑧
实时调度：硬实时（在特定硬件上保证时间），软实时：尽力而为，优先级不变，
没有饥饿现象
4.
算法评估
①
确定性模型甘特图
②
排队模型
N=入*W（N平均队列长度，W为队列的平均等待时间，入为新进程
到达队列的平均到达率）
③
模拟
11
④
实现
四、进程同步
1．
背景：竞争条件：共享内存，共享变量
2．
临界区问题
①
临界区解决方案：进入去，临界区，退出区，剩余区
②
效果：互斥，有空让进，有限等待
③
证明：，，临界区内无进程执行，
那么只有那些不在剩余区内执行的进程可参加选择，，从一个进程做出进入临界区的请求，知道该请求允许为止，其他进程允许进入其临界区的次数有上限。
④
PETERSON算法
3．
信号量：计数信号量，二进制信号量
①
技术信号量用于控制访问：当每个线程需要使用资源时，需要对该信号量执行
11
acquire()操作，当线程释放资源时，需要对该信号执行release()操作。
②
用信号量解决同步问题
4．
管程：管程结构确保一次只有一个进程能在管程内活动
5．
经典同步问题
①
生产者消费者问题
②
读者写者问题
③
哲学家吃饭问题
五、死锁
1.
死锁特征
①
必要条件：互斥，占有并等待，非抢占，循环等待
②
资源分配图：分配图没有环则没有死锁，有环则有死锁；有环则可能有死锁。
12
2.
死锁预防
①
互斥：通常不能通过否定互斥条件来预防死锁：有的资源本身就是非共享的。
②
占有并等待：协议一：每个进程在执行前申请并获得所有资源；协议二，允许
进程在没有资源时才可以申请资源。协议缺点：资源利用率低，可能发生饥饿。
③
非抢占：协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那
么其现在已分配的资源都可被抢占。
④
循环等待：对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请
资源。
3.
死锁避免
①
安全状态:如果系统能按某个顺序为每个进程分配资源并能避免死锁，那么系统
13
状态就是安全的。
②
单实例：资源分配图：申请边，分配边，需求边
③
多实例：银行家算法Available(向量),Max（矩阵）,Allocation（矩阵），Need(矩
阵),
4.
死锁检测
①
单实例：等待图：当且仅当等待图中有一个环时，系统存在死锁
②
多实例：类似银行家算法
5.
死锁恢复
①
进程终止：终止所有死锁进程；一次只终止一个进程，直到取消死锁循环为止
②
资源抢占：问题：选择一个牺牲品；回滚；饥饿
第三部分内存管理
一、内存管理
1.
14
背景
①
地址绑定：编译时（编译时就知道进程将在内存中的驻留地址，那么就可以生
成绝对代码），加载时（生成可重定位的代码），运行时（如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才进行）
②
逻辑地址（CPU所生成的地址）物理地址（内存单元所看到的地址）
③
动态加载（子程序只在调用时加载，优点不用的子程序绝不会被加载）
④
动态链接与共享库（将连接延迟到运行时）
2.
交换（没看）
3.
连续内存分配：单分区，多分区
4.
非连续内存