2012山东专升本操作系统讲义（总）

1、操作系统概述操作系统概述概念定义：管理软件和硬件资源，调度，方便用户，程序集合地位：硬件上的第一层软件，核心系统软件无操作系统基本特征并发性：并发和并行共享性：互斥共享，同时访问虚拟技术：时分复用，空分复用异步性：不可预测主要功能OS结构设计处理机管理功能：进程控制，进程同步，进程通信，调度存储器管理功能：内存分配，内存保护，地址映射，内存扩充设备管理功能：缓冲管理，设备分配，设备处理文件管理功能：存储空间管理，目录管理，读/写管理和保护操作系统与用户接口：用户接口，程序接口模块化结构OS：分解，模块化分层式结构OS微内核结构OS：微内核，面向对象，客户/服务器无结构操作系统发展过程（概念，特

2、点，优缺点）单道批处理系统多道批处理系统：多道程序设计技术分时系统：时间片，响应时间，关键问题，改变方法实时系统：实时控制，实时信息，与分时系统的比较微机操作系统：单用户单任务，单用户多任务，多用户多任务无操作系统：脱机输入/输出方式目标：有效性，方便性，可扩充性，开放性作用：用户接口，资源管理者，对资源的抽象隐藏硬件细节第二章 进程管理 一、进程基本概念进程基本概念进程的概念程序的顺序执行（顺序，封闭，可再现性）并发执行（间断，失去封闭，不可再现）进程的定义前趋图三状态：就绪，阻塞，执行进程控制块，进程的组织（队列，组织方式：链接，索引）进程控制进程控制：创建与终止，阻塞与唤醒，挂起与激活进

3、程通信（高级）共享存储器系统消息传递系统管道系统进程状态与转换五状态：静止就绪，活动就绪，静止阻塞，活动阻塞，执行直接通信间接通信线程概念线程概念：定义、属性线程与进程的区别线程的实现：内核支持线程，用户级线程进程的特征（结构特征，动态性，并发性，独立性，异步性），与程序的区别二、进程同步信号量机制进程同步进程同步的基本概念互斥与同步临界资源临界区信号量及P、V操作定义利用信号量机制实现互斥利用信号量机制解决同步(前趋关系,一般同步)生产者-消费者问题哲学家进餐问题读者-写者问题经典同步问题处理机的调度与死锁一、处理机调度处理机调度调度的基本概念高级调度：作业调度：作业，作业步，作业流，作业控

4、制块低级调度：进程调度中级调度调度队列模型：三种调度基本准则典型调度算法先来先服务调度算法:周转时间,带权周转时间最高优先权优先调度算法时间片轮转调度算法多级反馈队列调度算法面向用户准则：周转时间短、响应时间快、截止时间保证、优先权面向系统准则：系统吞吐量高、处理机利用率好，资源平衡利用一般调度算法分时调度短作业优先调度算法调度的方式非抢占式抢占式高响应比优先调度算法:响应比二、死锁死锁死锁的概念死锁产生的原因：竞争资源，程序推进不当死锁产生的必要条件：互斥，请求和保持，不剥夺，环路等待死锁的检测：资源分配图死锁预防死锁的避免死锁的检测和解除系统安全状态银行家算法死锁的定义处理死锁的方法：预防

5、死锁，避免死锁，检测死锁，解除死锁破坏请求和保持条件：一次性分配破坏不剥夺条件：不满足条件立即剥夺破坏环路等待条件：有序分配两个判断假设分配安全性检查死锁的解除剥夺资源撤消进程第四章 存储器管理内存管理程序的装入与链接程序的装入程序的链接绝对装入方式（逻辑地址，物理地址）可重定位装入方式（重定位）动态运行时装入方式（动态重定位）物理内存管理单一连续分配固定分区分配动态分区分配（分配算法）可重定位分区分配（紧凑）虚拟内存管理管理静态链接方式装入时动态链接方式运行时动态链接方式连续分配方式非连续分配方式基本分页存储管理方式：页表，地址变换，快表基本分段存储管理方式：段表，地址变换段页式存储管理方式

6、请求分段存储管理方式页面分配策略，分配算法虚拟存储器的基本概念：程序局部性原理，虚拟存储器的特征请求分页存储管理方式：请求分页中的硬件支持页面置换算法请求分段中的硬件支持分段的共享与保护最佳置换算法（OPT）（向后看）先进先出置换算法（FIFO）（栈）最近最少使用置换算法（LRU）（向前看）时钟置换算法（CLOCK）（访问位）改进型CLOCK算法第五章 设备管理先来先服务最短寻道时间优先）扫描算法循环扫描算法磁盘的结构：柱面，磁道，扇区；磁盘访问时间构成磁盘调度算法设备管理I/O设备I/O控制方式设备分配与回收设备分配中的数据结构：DCT、SDT、COCT、CHCT设备分配步骤：分配设备、分配

7、控制器、分配通道程序直接控制方式中断控制方式DMA方式通道控制方式缓冲管理单缓冲双缓冲循环缓I/O管理功能：缓冲管理，设备分配，设备处理，虚拟设备，设备独立性设备控制器，通道：字节多路，数组选择，数组多路缓冲的好处假脱机技术（SPOOLing）I/O系统的软件组织中断处理设备驱动程序设备独立性软件设备管理概述信息交换单位：块设备和字符设备使用特性：存储，输入/输出设备共享属性：独占设备、共享设备、虚拟设备传输速率：低速，中速和高速缓冲池磁盘组织与管理第六章 文件管理文 件 管 理文件类型文件操作文件逻辑结构的类型逻辑结构型顺序文件索引文件索引顺序文件文件的逻辑结构文件、记录和数据项文件概念文件

8、外存分配（物理结构）连续分配链接分配（FAT技术）索引分配磁盘管理空闲表法和空闲链表法位示图法文件控制块和索引结点，文件目录和目录文件目录管理目录结构单级目录，两级目录文件共享基于索引结点的共享方式（硬链接）利用符号链实现文件共享（软链接）访问类型树形目录图形目录文件保护访问控制文件逻辑结构的类型逻辑结构型第七章 操作系统接口系统调用系统调用的实现系统调用与一般调用的区别特权指令与非特权指令系统态和用户态系统调用概念操作系统算法总结一、进程(作业)调度算法（p91）先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程

9、一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。 短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。 时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。 优先权调度算法 ：它是从就绪队列

10、中选择一个优先权最高的进程，让其获得处理器并执行。 高响应比优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。 基本概念： 作业周转时间（Ti）完成时间提交时间 作业平均周转时间(T)周转时间/作业个数 作业带权周转时间（Wi）周转时间/运行时间 响应比（等待时间运行时间）/运行时间二、存储器连续分配方式中分区分配算法(p123) 首次适应分配

11、算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。保留了高址部分的大空闲区。 循环首次适应算法：每次分配均从上次分配的位置之后开始查找。 使内存中的空闲区分布得更均匀 最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。 最坏适应分配算法（WF）：将作业申请大小与

12、内存中所有未分配区的大小进行比较，直到找到最大的或等于作业空间的区分配给作业。要求按空闲区大小从大到小的次序组成空闲区链。优先使用大的自由空间，在进行分割后剩余空间还可以被使用。大的自由空间无法保留给需要大空间的作业。三、页面置换算法(p149)最佳置换算法（OPT) ：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。 时钟算法（CLOCK）：选择访问位为0的页面淘汰。四、磁盘调度(p194) 先来先服务（FCFS）：是按请求访问者的先后次

13、序启动磁盘驱动器，而不考虑它们要访问的物理位置 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题，但容易造成进程饥饿现象 扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。五、信号量问题（解题思路）（p53）分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进