02323 操作系统概论
2019-07-10 18:51:57 3 举报AI智能生成
自考 02323 操作系统概论
作者其他创作
大纲/内容
第六章 I/O设备管理
第一节 I/O系统的组成
一、I/O系统的结构
微机I/O系统：又叫总线型I/O系统，CPU与内存之间可以交换信息，但不能与设备直接交换信息。
主机I/O系统：可能采用四级结构，包括主机、通道、控制器和设备，一个通道可以控制多个设备控制器，一个设备控制器也可以控制多个设备。
二、I/O设备的分类
按传输速率分
低速设备：如键盘和鼠标
中速设备：如打印机
高速设备：如磁带机、磁盘机、光盘机
按信息交换的单位分类
块设备：数据存取以数据块为单位，如磁盘。
字符设备：传送字节流，没有使用块结构。如打印机。
按设备的共享属性分类
独占设备：是必须作为临界资源以互斥方式访问的设备。如打印机
共享设备：允许多个进程共同访问的设备，如磁盘
虚拟设备：通过某种虚拟技术把一台物理设备变成若干逻辑设备。
三、设备控制器
设备控制器：是一个可编址设备，是CPU与I/O设备之间的接口，接收I/O的命令并控制设备完成I/O工作。
设备控制器的功能
接收和识别命令
数据交换
设备状态的了解和报告
地址识别
数据缓冲
差错控制
设备控制器的组成
与处理机的接口：数据线、控制线和地址线
与设备的接口：数据、状态、控制信号
I/O逻辑：指令译码器、地址译码器
四、I/O通道
是一种特殊的处理机，适用于大型主机系统控制I/O设备，与控制设备结合，与微机和小型机的设备控制器具有对等的功能。
第二节 I/O控制方式
一、轮询
主机需反复检测设备控制器状态是否忙/闲，使CPU经常处于循环检测状态，浪费CPU
二、中断
CPU发出请求，若I/O设备忙，则阻塞进程，CPU执行其他进程，当设备忙完后向CPU发出信号，CPU重新调度被阻塞进程并开始执行。
三、DMA控制方式
DMA控制器包括了主机与DMA的接口、DMA与设备的接口、I/O控制逻辑三部分
四类寄存器
命令/状态寄存器CR：用于接收CPU发来的控制信息、设备状态
内存地址寄存器MAR：存放数据的内存起始地址，DMA应该把数据放在哪里
数据计数器DC：提示DMA，向CPU发中断信号前要读或写的数据次数
数据寄存器DR：暂存DMA传输中要输入或输出的数据
第三节 缓冲管理
缓冲区：是用来保存两个设备之间或设备与应用程序之间传输数据的内存区域。
一、缓冲的引入
引入缓冲区的原因
处理数据流的生产者与消费者之间的速度差异
协调传输数据大小不一致的设备
二、单缓冲
操作系统提供的最简单的缓冲类型是单缓冲区
三、双缓冲
通过给操作系统指定两个系统缓冲区，性能高，但增加了复杂性
四、循环缓冲
在数据到达和数据离去的速度差别很大的情况下，需要增加缓冲区的数量
五、缓冲池
被广泛应用的一种技术，公共缓冲池中设置多个可供若干进程共享的缓冲区
三种类型：空缓冲区、装满输入数据的缓冲区和装满输出数据的缓冲区
四种工作方式：收容输入、提取输入、收容输出、提取输出
第四节 设备分配
一、设备分配中的数据结构
设备控制表DCT：多台设备的设备控制表构成设备控制集合
控制器控制表COCT：用于记录该控制器的控制器信息表
通道控制表CHCT：为每个通道设备设置一张通道控制表
系统设备表SDT：记录了系统中全部设备的情况
二、设备分配
设备的共享属性：独占设备、共享设备、虚拟设备
设备分配算法
先来先服务
基于优先权的分配算法
设备分配方式
安全分配方式：摒弃了请求和保持的死锁原因
不安全分配方式：分配不安全，可能造成死锁
三、设备独立性
设备独立性：为了提高操作系统的可适应性和可扩展性，在现代操作系统中都毫无例外的实现了设备的独立性，也称为设备无关性。
实现设备独立性的好处
应用程序与物理设备无关，系统增减或变更外围设备时不需要修改应用程序
易于处理输入/输出设备的故障
提高了系统的可靠性，增加了设备分配的灵活性
设备独立软件完成的主要功能
执行所有设备的公有操作
向用户层软件提供统一的接口
四、独占设备的分配程序
分配设备：根据用户请求的设备，查找系统设备表，确定设备的忙闲状态，根据算法进行分配
分配控制器：系统分配了请求的设备，就到该设备的控制表中查找设备的状态，闲就分配，忙就阻塞该进程到该设备的阻塞队列中。
分配通道：根据控制器连接的通道，查找控制表中设备的状态，闲就分配，忙就阻塞该进程在该通道阻塞队列上。
五、SPOOLing技术
在多道程序环境下，利用一道程序来模拟脱机输入时的外围控制机的功能，把低速I/O设备上的数据传送到高速输出磁盘上，再利用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上的外围操作方式。
SPOOLing系统的组成
输入井和输出井
输入缓冲区和输出缓冲区
输入进程SPi和输出进程SPo
SPOOLing系统的特点
提高了I/O速度
将独占设备改造为共享设备
实现了虚拟设备功能
第五节 I/O软件原理
一、设备管理软件的功能
实现I/O设备的独立性
错误处理
异步传输
缓冲管理
设备的分配和释放
实现I/O控制方式
二、中断处理程序
I/O中断处理程序的作用是将发出的I/O请求而被阻塞的进程唤醒。
三、设备驱动程序
设备驱动程序是I/O进程与设备控制器之间的通信程序，其主要任务是接受上层软件发来的抽象的I/O请求，把它们转换成具体需求后，发送给设备控制器，启动设备去执行。
磁盘驱动程序的工作
计算出所请求块的物理地址
检查驱动器电机是否正在运转
检查磁头臂是否定位在正确的柱面
确定需要哪些控制器命令及命令的执行顺序
向设备控制器的设备寄存器中写入命令
I/O完成后，向上层软件传送数据
四、与硬件无关的I/O软件的功能
设备命名：将设备名映射到相应的驱动程序
设备保护：为设备设置合理的访问权限
提供独立于设备的块大小
为块设备和字符设备提供必要的缓冲技术
块设备的存储分配
第六节 磁盘管理
一、磁盘结构
数据的组织和格式：磁盘上存储的物理记录数目是由扇区数、磁道数及磁盘面数所决定
磁盘的每个扇区包括两个字段
标识符字段：利用磁道号、磁头号及扇区号三者来标识一个扇区
数据字段：每个扇区600个字节，其中512个字节用来存放数据
磁盘的类型
固定头磁盘：每条磁道上都有读/写磁头，装在一个刚性臂中，可访问各磁道并读写
移动头磁盘：每个盘面仅配有一个磁头，也装在磁臂中，读写较慢，用于中小型磁盘设备
磁盘的访问时间
寻道时间：把磁臂移动到指定磁道上所经历的时间
旋转延迟时间：将指定扇区移动到磁头下面所经历的时间
传输时间：把数据从磁盘读出或向磁盘写入数据时所经历的时间
二、磁盘调度
先来先服务FCFS：适用于请求磁盘I/O进程数目较少的场合
最短寻道时间优先SSTF：要求访问的磁道与当前磁头所在的磁道距离最近，易出现饥饿现象
扫描算法SCAN：又称电梯算法，磁头由外向里或由里向外循环读取
循环扫描算法CSCAN：能获得较好的寻道时间，防止了饥饿现象，广泛用于磁盘调度
NStepSCAN和FSCAN调度算法
三、提高磁盘I/O速度的方法
提前读：系统根据现在用户请求读的内容，将预计最近不久可能要读的内容一起读入内存
延迟写：对修改过的换出页暂时保留在内存中，直到这些页所在的页框内容将被覆盖时再启动磁盘操作
优化物理块的分布：适当的集中数据在磁盘上存放的位置来减少磁臂的移动距离
虚拟盘：利用内存空间去仿真磁盘，又称RAM盘，可接受所有标准的磁盘操作，但并不是在磁盘上，而是在内存中。
磁盘高速缓存：用来暂存从磁盘中读出的一系列盘块中的信息。
第五章 文件系统
第一节 文件
一、文件命名
文件名支持长达255个字符，有些操作系统区别文件名大小写，有些不区分
用圆点隔开的后面部分称为文件扩展名，表示这个文件的类型
二、文件结构
无结构字节序列文件：也称流式文件，操作系统不知道也不关心文件内容，操作系统见到的就是字节，其含义由使用该文件的程序自行理解。
固定长度记录序列：构成文件的基本单位是具有固定长度的记录，每个记录都有内部结构
树形结构：文件由一棵记录树构成，记录长度不定，按文件的关键字域排序。
三、文件类型
ASCII文件：由多行正文组成，在某些系统中每行用回车符或换行符结束。
二机制文件：具有一定的内部结构，只有使用专门二进制文件编辑器才能打开。
四、文件存取
顺序存取：从文件开始处读取文件中所有记录，不能跳过某些内容
随机存取：可以以任意顺序读取文件中的字节或记录
五、文件属性
保存其他与文件相关的信息，如创建日期、文件大小……
六、文件操作
CREATE：创建文件
DELETE：删除文件
OPEN：打开文件，目的是将文件属性和文件的地址信息装入主存
CLOSE：关闭文件
READ：读取文件
WRITE：写入文件
APPEND：在文件末尾添加数据
SEEK：指定从何处开始取数据
GETATTRIBUTES：获取文件属性
SETATTRIBUTES：修改文件属性
RENAME：修改文件名
第二节 目录
目录是文件系统中实现按名访问文件的重要数据结构。
一、层次目录系统
目录文件的两种常见的结构：属性放在目录项中和放在i结点中
目录结构
单层目录：也被称为根目录，在系统中设置一张线性目录表，表中包括了所有文件的描述信息，优点是设计相对简单。
两级目录：为避免文件名冲突，为每个用户提供一个私有目录，优点是解决了文件重名问题和文件共享问题，缺点是增加了系统的存储开销。
树形目录：把两级目录加以推广，就形成了多级目录。优点是便于文件的分类、层次结构清晰、便于管理和保护，解决了重名问题和查找速度快。缺点是多次访问磁盘会影响速度，结构相对复杂。
二、路径名
绝对路径名：由根目录到文件的路径组成。如/C/A/B
相对路径名：访问的文件在当前目录下。如.指当前目录，..指上级目录
三、目录操作
CREATE：创建目录
DELETE：删除目录
OPENDIR：目录内容可以被读取
CLOSEDIR：关闭目录
READDIR：以标准格式返回打开目录的下一级目录项
RENAME：更换目录名
第三节 文件系统的实现
一、实现文件
连续分配：就是把每个文件作为一连串连续数据块存储在磁盘上。
优点：实现简单、读操作性能好。缺点：磁盘会越来越零碎
使用磁盘链接表的分配：为每个文件构造簇的链接表，每个簇开始的几个字节用于存放下一个簇的簇号，簇的其他部分存放数据，每个文件可以存放在不连续的簇中。
优点：不浪费存储空间、管理简单。缺点：随机存取速度慢
使用内存的链接表分配：将文件所在的磁盘的簇号存放在内存的表中。访问文件时需顺着链接关系查找簇的簇号。缺点：必须把整个表存放在内存中，不适合大容量磁盘
i-结点：为每个文件赋予一个被称为i结点的数据结构，其中列出了文件属性和文件块的磁盘地址。
二、实现目录
CP/M中的目录：是一个微机操作系统，只有一层目录，只有一个目录文件
用户码：记录了文件所有者
文件名：存放文件名
扩展名：标识文件类型
范围：由该域可知某目录项是文件的第几个目录项
块数：文件实际使用的簇的数量
磁盘块号：最后16个域记录了簇号
MS-DOS中的目录：IBM PC系列所采用的文件系统FAT-32
UNIX中的目录：每个目录项只包含一个文件名及其i结点号
三、磁盘空间管理
簇大小：文件系统为文件分配磁盘空间是以簇为单位的，一般簇大小为2的整数次幂
记录空闲块：怎样记录空闲簇
空闲簇链接表：用一些空闲簇存放空闲簇的簇号
位图：用n位位图对应磁盘的n个簇，所需空间少，每个簇用二进制位标识
第四章 内存管理
第一节 存储器的层次结构
存储器的层次结构
L0 CPU寄存器，速度快，容量小，价格高，1个时钟周期内访问
L1 SRAM高速缓存存储器，速度较快，几个时钟周期内访问
L2 DRAMY主存储器，俗称内存，容量较大，50-100个时钟周期内访问
L3 本地磁盘 容量大，速度慢，价格低，2000万个周期内访问
L4 远程二级存储，分布式文件存储系统，WEB系统
局部性原理的表现
时间局部性
某条指令被执行后可能再次被执行
空间局部性
某个单元被访问后，其附近的单元也将被访问
第二节 程序的链接和接入
一、程序的链接
链接程序不属于操作系统的部分，链接分为静态链接和动态链接
静态链接：是在程序运行前，用链接程序将目标模块链接成一个完成的装入模块
程序任务分为对逻辑地址进行修改和变换外部调用符号
动态链接：可将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行
优点是节省内存和外在空间，方便程序开发
二、程序的装入
程序装入方式
绝对装入方式
可重定位装入方式（静态重定位）
物理地址=有效逻辑地址+程序在内存中的起始地址
动态运行时装入（动态重定位）
重定位：程序装入时对目标程序中的指令和数据地址的修改过程
第三节 连续分配存储管理方式
一、单一连续分配
适用于单用户、单任务的操作系统，把内存分为系统区和用户区
常用的方法是设置一个基址寄存器和一个界限寄存器
二、固定分区分配
划分分区的方法
分区大小相等
分区大小不等
支持固定分区分配的数据结构
固定分区的分配过程
寻找大于或等于进程需要且空闲的内存空间，将该空间分配给进程，并将分区状态改为“已占用”
固定分区的回收
进程运行结束后，系统回收进程所占空间，并将分区状态改为“空闲”
三、动态分区分配
动态分区分配：是根据进程的实际需要，为进程分配大小合适的内在区域
动态分区分配的数据结构
空闲分区表
空闲分区链
动态分区分配算法
首次适应算法FF
每次为进程分配内存时，均从链首开始顺序查找，直到找到合适的空间再进行分配
循环首次适应算法NF
每次为进程分配空间时，均从上一次查找的位置开始查找，直到找到合适的空间
优点：空闲区分布均匀、查找开销小；缺点：系统容易缺乏大空闲区
最佳适应算法BF
按大小顺序将空闲分区进行排列形成一个空闲区链
为进程寻找最佳的空闲分区进行分配
优点：避免大材小用，提高内存利用率；缺点：容易留下难以利用的小空闲区
动态分区分配的流程
内存分配流程
内存回收流程
第四节 基本分页存储管理方式
一、分页存储管理的基本原理
离散内存管理方式：把进程离散地存储在内存中物理地址不连续的区域中
离散内存管理方式主要分为
分页存储管理
分段存储管理
段页式存储管理
地址结构
页号P=INT（A/L），例INT（5236/4096）=1
页内偏移量W=MOD（A/L） 例MOD（5236/4096）=1140
页：将一个进程的逻辑地址空间分成若干个大小相等的片
页框：将物理内存空间分成与页大小相同的若干个存储块
分页存储：为进程分配内存时，以页框为单位将进程中的若干页分别装入多个可以不相邻接的页框中
页内碎片：进程的最后一页一般装不满一个页框而形成了不可利用的碎片
页表：是系统为进程建立的数据结构，作用是实现从页号到页框号的映射
二、快表
快表：也称转换后援缓冲TLB，是为了提高CPU访存速度而采用的专用缓存，用来存放最近被访问过的页表项。
三、两级和多级页表
两级页表：将页表再分页，使每个页表分页的大小与内存页框的大小相同，并为它们编号
页目录表：将页表分页分别放入不同的、不一定相邻的页框中，为离散分配的页表再建立一张外层页。
页表的起始地址=进程页所在的页框号×页框大小+页内地址d
减少页表占有内存的方法：将当前所需的页表存放在内存，不需要的存放在外存中
多级页表结构：将外层页表再分若干页，然后为外层页表建立连续存放的索引表
四、反置页表
反置页表：为每一个页框设一个表项，表项中存放进程号和页号，系统只维护一张反置表
反置页表的映射
根据进程号和页号找到页框号
物理地址=页框号×页框大小+页内偏移地址
五、空闲页框的管理
使用位图管理空闲页框
使用空闲页框的链表
第五节 基于分页的虚拟存储系统
虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
虚拟存储技术带来的3点好处
提高内存利用率
提高多道程序度
把逻辑地址空间和物理地址空间分开，使程序员不用关心物理内存的容量对编程的限制
虚拟存储系统的主要特征：离散性、多次性、对换性、虚拟性
一、请求分页中的硬件支持
页表：是支持请求分页系统最重要的数据结构，作用是记录描述页的各种数据
页框号：存放页所在的页框号
状态位P：用来标识页是否在内存中
访问字段A：用于记录页最近被访问的情况
修改位M：用于标识页最近是否被修改过
保护位：用于标识页的访问权限
缺页异常机构：访问内存过程中发现缺页时产生的缺页异常信号
地址变换过程
二、页分配策略
最少页框数：是指能保证进程正常运行所需要的最少页框数。
保证进程正常运行与计算机硬件结构有关，取决于指令的格式、功能和寻址方式
页分配和置换策略
固定分配局部置换、可变分配全局置换、可变分配局部置换
分配算法
平均分配算法
按比例分配算法
考虑优先权的分配算法
三、页调入策略
何时调入页：在进程需要时才将页调入内存
从何处调入页
当系统拥有足够的对换空间时，若发生缺页请求，则从对换区调入页
页调入过程
四、页置换算法
最佳置换算法（性能好，难实现）
该算法将以后不会用或者很长时间不会用的页作为换出页
先进先出页置换算法FIFO（性能差，实现简单）
该算法将进入内存时间最早的页作为换出页
最近最久未使用LRU置换算法
该算法选择最近最久未使用的页作为换出页
LUR算法的实现：寄存器、栈、计数器
其他置换算法
附加引用位算法
简单Clock置换算法
改进型Clock算法
最少使用置换算法
页缓冲算法
五、请求分页系统的性能分析
缺页率对有效访问时间的影响
工作集机制是为了能有效降低缺页率，从而提高访存的时间效率而提出的
抖动产生的原因和预防方法
多道程序度太高，使运行进程的大部分时间都用于进行页的换入、换出，而几乎不能完成任何有效工作的状态称为抖动。
产生抖动的主要原因是系统中进程数量太多，每个进程分配到的页框数太少
预防方法
采取局部置换策略
在CPU调度程序中引入工作集算法
挂起若干进程
第六节 分段存储管理
一、分段机制的引入
引入分段机制的优点是：方便编程、分段共享、分段保护、动态链接，以及存储空间的动态增长
二、分段系统的基本原理
分段：在分段的存储管理方式中，进程的地址空间被划分成若干个段。
段表的每一个表项记录的信息包括段号、段长和段的基址
分段机制的逻辑地址是二维的，由段号和段内地址组成
段表是由操作系统维护的用于支持分段存储管理地址映射的数据结构。
包含段号、段基址和段长
s号段表项在内存中的起始地址=段表起始地址+段号s×段表项长度
分页和分段的主要区别
相同点
分页和分段都属于离散分配方式，都要通过数据结构与硬件的配合来实现逻辑地址到物理地址的映射。
不同点
页是按物理单位划分的，段是按逻辑单位划分的。
页的大小是固定的，段的大小不固定。
分页地址是一维的，而分段的地址是二维的。
采用分段机制比采用分页机制更容易实现信息的共享。
三、段页式存储管理
实现原理：操作系统为每个进程建立一个段表，为进程的每个段建立一个页表，存放某个段的页表起始地址和页表长度。
物理地址=页框号×页框大小+页内偏移W
第七节 Linux的伙伴系统
伙伴算法
第一章 操作系统简介
第一节 什么是操作系统
操作系统OS：是一种复杂的系统软件，是不同程序代码、数据结构、数据初始化文件的集合，可执行。
操作系统的目标
与硬件部分相互作用，为包含在硬件平台上的所有底层可编程部件提供服务
为运行在计算机系统上的应用程序提供执行环境
操作系统的作用
操作系统是用户与硬件之间的接口
操作系统是计算机资源的管理者：管理处理机、内存、设备、文件等
第二节 操作系统的发展
一、无操作系统：第一代计算机（1945年~1955年） 电子管，无内存
二、单道批处理系统
产生：第二代计算机（1955年~1965年） 晶体管 增加存储设备
特点：自动性、顺序性、单道性
三、多道程序系统
多道批处理系统
特点：多道性、无序性、调度性、复杂性
优点：提高CPU、内存和I/O设备的利用率和系统的吞吐量
缺点：平均周转时间长，缺乏交互能力
分时系统
特点：多路性、独立性、及时性、交互性
优点：提供了人机交互的方便性，使多个用户可以通过不同的终端共享主机
分时系统的实现需要解决的问题：及时接收和及时处理（快速响应）
四、微机操作系统：第一个是Intle公司的CP/M系统，这是一个磁盘操作系统
五、实时操作系统：支持实时计算的系统
特点：多路性、独立性、及时性、交互性、可靠性
实时系统比分时系统要求有更高的可靠性
操作系统产品现状
主机操作系统：需具备批处理、事物处理和分时处理三大功能
示例：IBM的OS/360、OS/390
服务器操作系统：运行在网络服务器上，主要提供打印服务、文件服务和Web服务
示例：Liunx、Win Server 200X
微机操作系统：也叫个人机操作系统
嵌入式操作系统：采用易于移植的方式
特点：小巧、实时性、可装卸、代码固化、弱交互性、强稳定性、接口统一、低能耗
第三节 操作系统的特征
并发：是指两个或多个事件在同一时间间隔内发生
共享：是指系统中的资源可供内存中多个并发执行的进程共同使用
互斥共享：是指任意时刻一种资源只能被一个进程访问，当一个进程访问资源时，其他进程必须等待，直到资源被进程访问完毕，释放访问权。
同时共享
虚拟：是指通过某种技术把一个物理实体变成若干逻辑上的对应物
异步性
第四节 操作系统的功能
内存管理
内存分配（静态分配方式和动态分配方式）
内存保护
一是使操作系统内核的空间不会被用户随意访问，以保证系统的安全和稳定
二是确保每道用户程序都在自己的内存空间中运行，互不干扰
地址映射：把程序的逻辑地址转变为物理地址
内存扩充：借用于虚拟存储技术，从逻辑上扩充内存容量，使系统能够向用户提供比物理内存大的存储容量
进程管理
功能：进程的描述与组织、进程控制、进程同步、进程通信及进程调度
设备管理
功能：缓冲管理、设备分配、设备处理、设备独立性和虚拟设备
文件管理
文件存储空间的管理
目录管理，为每个文件建立目录项并对众多目录项进行有效组织
文件的读、写管理和存取控制
提供用户接口
命令接口：分为联机用户接口和脱机用户接口
图形用户接口
程序接口（一般都提供进程控制、文件操作、通信管理、系统维护等系统调用）
第五节 操作系统的体系结构
一、软件体系结构：是一个复杂软件系统的高层结构，为软件系统提供了一个结构、行为和属性的高级抽象，包括系统元素的结构、元素间的相互关系，以及指导元素集成的模式和约束三个方面。
二、操作系统体系结构
简单的监控程序模型
单体结构模型
层次结构模型
客户/服务器模型与微内核结构
动态可扩展结构模型
第六节 指令的执行
指令周期：一个单一指令需要的处理
取指周期
执行周期
第二章 进程管理
第一节 进程的描述
一、程序的并发执行
1.程序的顺序执行
在无操作系统和单道批处理系统中，程序执行只能按程序控制流依次执行
主要特点：顺序性、封闭性、可再现性
2.程序的并发执行
程序的并发执行是指在同一时间间隔内运行多个程序
主要特点：间断性、失去封闭性、不可再现性
二、进程的概念
进程的定义
进程是允许并发执行的程序在某个数据集合上的运行过程
进程是由正文段、用户数据段及进程控制块共同组成的执行环境
进程的特征
并发性：多个进程实体能在一段时间间隔内同时运行
动态性：进程是进程实体的执行过程
独立性：进程是独立运行和资源调度的基本单位
异步性：进程时断进续，执行和暂停都无法预知，呈现一种随机状态
结构特征：进程实体包括用户正文段、用户数据段和进程控制块
进程与程序的区别
程序是静态的，进程是动态的
程序是永久的，进程是暂时存在的
程序与进程的存在实体不同
进程与程序的联系
进程是程序的一次执行，进程总是对应至少一个特定的程序，执行程序的代码
一个程序可以对应多个进程
三、进程控制块
进程控制块：是进程实体的一部分，是操作系统中最重要的数据结构。
进程控制块中的信息
进程标识符信息。用于唯一标识一个进程
处理机状态信息。通常包括通用寄存器、指令计数器、程序状态字PSW和用户栈指针
进程调度信息。进程状态信息、进程优先级和进程调度所需的其他信息
进程控制信息。包括程序和数据的地址、进程同步和通信机制、资源清单
四、进程的状态
就绪态。是进程一旦获得CPU就可以投入运行的状态
执行态。是进程获得CPU正在运行的状态
阻塞态。是进程由于等待资源或某个事件的发生而暂停执行的状态
五、进程的组织
链接方式，把系统中具有相同状态的进程的进程控制块PCB用其中的链接字链接成一个队列
索引方式，根据进程的状态，建立索引表，索引表的每一个表项指向一个PCB物理块
进程队列，把进程控制块用队列组织起来，形成进程队列
第二节 进程的控制
一、进程的创建
用户登录
作业调度
提供服务
应用请求
二、进程的阻塞
请求系统服务
启动某种操作
新数据尚未到达
无新工作可做
三、进程的唤醒
将新进程从阻塞队列中移出
将进程状态由阻塞态改为就绪态
将进程插入就绪队列
四、进程的终止
当进程正常执行完毕，调用终止进程的系统调用，请求操作系统删除该进程
一个进程调用适当的系统调用，终止另外一个进程
第三节 操作系统内核
操作系统的内核有以下功能
支撑功能，包括中断处理、时钟管理和原语操作
资源管理功能，包括进程管理、存储器管理和设备管理
一、中断
什么是中断：是改变处理器执行指令顺序的一种事件
为什么需要中断
使CPU可以与其他设备并行工作，提高CPU的利用率，改善系统性能，支持系统的异步性
中断的类型
同步中断，也称内部中断或异常
导步中断，也称外部中断
引起中断的原因
人为设置中断
程序性事故
硬件故障
I/O设备
外部事件
二、时钟管理
时钟是计算机系统的脉搏，计算机的活动由定时测量来驱动。
计算机中有两个时钟源
实时时钟RTC：也称为CMOS时钟，是一块时钟芯片，靠电池供电，为计算机提供计时标准，是最原始、最底层的数据。
OS时钟：产生于PC主板上的定时/计数芯片，在开机时有效，由操作系统控制。
操作系统的时钟机制
OS时钟管理硬件（可编程间隔定时器PIT）
时钟软件（时钟驱动程序的主要功能）
维护日期和时间
递减当前进程在一个时间片内的剩余执行时间，并检查是否为零，防止进程运行超时
对CPU的使用情况记账
递减报警计数器
三、系统调用
系统调用：是一群预先定义好的模块，它们提供一条管道让应用程序或一般用户能由此得到核心程序的服务。
系统调用与一般函数调用的区别
系统调用运行在系统态，而一般函数运行在用户态
系统调用与一般函数调用的执行过程不同
系统调用要进行“中断处理”，比一般函数调用多了一些系统开销
系统调用的类型
进程控制类系统调用。创建、撤销进程
文件操纵类系统调用。创建文件、删除文件
设备管理类系统调用。请求、释放设备
通信类系统调用。打开、关闭连接，交换信息
第四节 进程同步
一、进程同步的基本概念
进程同步的两个任务
一是对具有资源共享关系的进程，保证诸进程以互斥的方式访问临界资源
二是对具有相互合作关系的进程，保证相互合作的诸进程协调执行
临界资源：必须以互斥方式访问的共享资源。临界区是进程中访问临界资源的那段代码
二、同步机制应遵循的准则：空闲让进、忙则等待、有限等待、让权等待
三、信号量机制
整型信号量机制。整型信号量的值只能通过两个特定的原子操作wait和signal来改变
记录型信号量机制
生产者-消费者问题的描述（利用管程解决）
读者-写者问题
AND型信号量机制
五、管程：是描述共享资源的数据结构和在数据结构上的共享资源管理程序的集合
包括变量的定义、变量的初始化代码以及管理共享资源的过程
管程的说明
管程是可供程序员调用的软件包
每次只有一个进程调用管程执行
管程是一种特殊的编辑语言构件，所以编译器知道它们很特殊，并可以调用与其他过程不同的方法来处理它们。
第五节 进程通信
共享存储器系统
基于共享数据结构的通信方式
基于共享存储区的通信方式
消息传递系统
直接通信方式
间接通信方式
管道通信
管道是连接读写进程的一个特殊文件，也称为管道文件
消息缓冲队列
广泛应用于本地进程之间的通信，消息缓冲区是一个结构型数据结构。
第六节 线程
一、线程的描述
线程：是进程中的一个实体，是被系统独立调度和分派的基本单位，包括程序计数器、一组寄存器和栈。
线程的分类
用户级线程
内核级线程
线程的基本状态
就绪态
运行态
阻塞态
线程与进程的区别
资源和调度。线程是程序执行的基本单位，进程是拥有资源的基本单位
地址空间资源。不同进程的地址空间是互相独立的，而同一进程中的各线程共享同一地址空间。
通信关系。进程之间的通信必须使用操作系统提供的进程间通信机制，而同一进程中的各线程间可以通过直接读写全局变量来通信。
并发性。多个进程和多个线程之间可并发执行，而同一进程中多个线程之间也可以并发执行。
系统开销。相比进程而言，线程在创建、撤销及上下文切换时系统开销很小，且速度更快。
二、线程的控制
线程的创建
用户线程的创建：是通过调用线程库中的实用程序完成的
内核线程的创建：是由内核完成的
线程的终止
引起线程终止的原因：正常结束、异常结束、外界干预
线程的终止过程
线程的调度与切换
用户线程的调度与切换在应用程序内部进行，采用非抢占式和时间片轮转规则
内核线程的调度与切换是由内核以线程为单位进行，需要用户模式和内核模式之间的切换
线程的阻塞与唤醒
引起线程阻塞的事件
请求系统服务
启动某种操作
新数据尚未到达
用户线程的阻塞和唤醒
内核线程的阻塞和唤醒
三、线程的同步
线程同步的机制有原语操作和信号量机制
四、线程通信：是指线程之间的信息交换
第三章 进程调度与死锁
第一节 进程调度的功能与时机
一、进程调度的功能
是由操作系统内核的进程调度程序完成，是按照某种策略和算法从就绪态进程中为当前空闲的CPU选择在其上运行的新进程。
二、进程调度的时机
进程运行结束、进程阻塞、中断返回、优先级更高的进程进来、时间片用完
第二节 进程调度算法
进程调度算法：是指从就绪态进程中选择一个或几个进程为其分配CPU，使其进入执行态的算法。
选择调度方式和算法的准则
周转时间短：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔
响应时间快：是指从用户提交一个请求开始直至系统首次产生响应的时间
截止时间的保证，截止时间是指某个任务必须开始执行的最迟时间
系统吞吐量高，吞吐量是单位时间内完成的作业数
处理机利用率好
调度算法
先来先服务调度算法FCFS
FCFS为从就绪队列的队首选择最先到达就绪队列的进程分配CPU
性能分析：适合长进程，不利于短进程
系统平均周转时间=每个进程周转时间相加/进程数
平均带权周转时间=（周转时间/服务时间）/进程数
短进程优先调度算法SPF
SPF是从就绪队列中选择估计运行时间最短的进程将CPU分配给它
性能分析
优点：有效降低平均等待时间，提高系统吞吐量
缺点：对长进程不利，不能保证紧迫进程及时处理，并不能完全做到短进程优先
优先权调度算法
为每个进程关联一个0~127之间的优先权数字，权值越高，优先权越高
优先权调度算法类型
非抢占式优先权调度算法：进程一旦得到CPU，则该进程会一直执行完成
抢占式优先权调度算法：一旦有更高优先权的进程进入，那么系统会抢占CPU
优先权的类型
静态优先权，优先权在运行期间不会改变
动态优先权，优先权会在运行期间随等待时间的增加而改变
主要问题：无穷阻塞，是指就绪态进程得不到CPU而等待的状态
解决方案：老化技术，逐渐增加在系统中等待时间很长的进程优先权
时间片轮转调度算法RR
时间片轮转调度算法：系统将所有进程按先后顺序排成一个队列，给每次调度的进程分配一个时间片，时间用完后，将进程送到队尾重新排队。
时间片大小的确定
系统对响应时间的要求
就绪队列中进程的数目
系统的处理能力
性能评价：该算法很依赖时间片大小，如果时间片很小，会增加CPU的开销
多级队列调度
将就绪队列分成多个独立队列，根据进程属性，每个队列有自己的调度算法
优点是降低了进程调度的开销，但可能会存在无穷阻塞问题
多级反馈队列调度
将进程根据优先级排列，优先权越高，时间片越短，等待过长的进程采用老化技术
第三节 实时系统中的调度
一、实现实时调度的基本条件
提供必要的调度信息
就绪时间、开始截止时间和完成截止时间
处理时间、资源要求、优先级
系统处理能力强
采用抢占式调度机制
基于时钟中断的抢占式优先调度算法
立即抢占的优先权调度算法
具有快速切换机制
对外部中断的快速响应能力
快速的进程切换能力
二、常用的几种实时调度算法
最早截止时间优先算法EDF
最低松弛度优先算法LLF
第四节 进程切换的步骤
保存包括程序计数器和其他寄存器在内的CPU上下文环境
更新被替换进程的进程控制块
修改进程状态，把执行态改为就绪态或者阻塞态
将被替换进程的进程控制块移到就绪队列或阻塞队列
执行通过进程调度程序选择的新进程，并更新该进程的进程控制块
更新内存管理的数据结构
恢复被调度程序选中的进程的硬件上下文
第五节 多处理器调度
一、多处理器系统的类型MPS
紧密耦合的多处理器系统
通过高速总线或高速交叉开关实现多个处理器之间互连，共享主存储器和I/O设备
松弛耦合的多处理器系统
通过通道或通信线路来实现多台计算机之间互连，有独立的存储器和I/O设备
对称多处理器系统
处理单元的功能和结构相同，处理器系统是对称的
非对称多处理器系统
多种类型的处理单元，功能结构各不相同，只有一个主处理器，多个从处理器
二、多处理器系统中的进程分配方式
对称多处理器系统中的进程分配方式
静态分配
建立一个专门的就绪队列，队列上的每个进程只能在对应的处理器上运行
动态分配
每个进程经过多次调度，每次获得的不一定是同一个处理器
非对称多处理器系统中的进程分配方式
采用主-从式操作系统，操作系统的核心部分驻留在一台主机上，而从机上只运行用户程序，只有主机执行调度程序，所有从机的进程都是由主机分配的。
三、进程（线程）调度方式
自调度：最常用最简单的调度方式之一
优点：易移植，有利于提高CPU的利用率
缺点：瓶颈问题、低效性、线程切换频繁
成组调度：是由系统一组相互合作的进程或线程同时分配到一组处理器上运行，进程或线程与处理器一一对应
优点：减少线程切换，改善系统性能；减少调度开销。
成组调度中的时间分配方式
面向所有的应用程序平均分配处理器时间
面向所有的线程平均分配处理器时间
专用处理器分配
适用于：并发程序多的处理器环境，拥有数十个或数百个处理器的并行系统
优点：加速了应用程序的运行速度；避免了进程切换
缺点：处理器资源严重浪费，如出现阻塞，处理器只能空等，不能分配给其他线程
第六节 死锁
一、产生死锁的原因和必要条件
死锁：由于多个进程竞争共享资源而引起的进程不能向前推进的僵死状态
产生死锁的原因：竞争共享资源且分配资源的顺序不当
产生死锁的必要条件
互斥条件：指一个进程在访问资源的过程中，其他进程不能访问该资源
请求和保持条件：进程已经保持了至少一个资源，又提出新的资源需求，而请求的资源被其他进程占有，但又对保持的资源不放，其他进程也无法使用被占有的资源
不剥夺条件：进程占有的资源不能被剥夺，只能由进程自我释放
环路等待条件：进程之间的资源需求形成了一个环形
二、处理死锁的基本方法
死锁的预防：保证至少其中一个条件不成立
摒弃请求和保持：进程只要有一个资源申请不成功，其他资源也不给它
摒弃不剥夺条件：当进程提出新资源需求不被满足时，必须释放它已占有的资源
摒弃环路等待：对不同类型的资源排序，进程必须按规定申请资源
缺点
限制了新设备的增加
系统为资源分配的序号与进程实际使用资源的不同，造成资源浪费
给用户编程带来了麻烦
死锁的避免：设置系统安全状态
系统安全状态：系统根据进程执行序列进行资源分配，进程序列执行完成后统一回收再分配给下一序列，这样系统就处于安全状态中
三、银行家算法
银行家算法由Dijkstra于1965年提出，为了实现银行家算法，需要数据结构的支持。
基本思想：当一个进程提出资源请求后，系统先进行资源试分配，然后检测本次的试分配是否使系统处于安全状态，若安全则执行分配方案，否则不分配资源。
银行家算法分为两个过程
一是进行资源试分配过程
资源试分配算法
二是对试分配后系统的状态做安全性检测的过程
安全性检测算法
应用情况说明：缺乏实用价值，因进程在运行之前不容易知道其所需资源数且可用资源也可能突然之间变得不可用
四、死锁的检测和解除
何时调用检测算法
死锁可能发生的频率
当死锁发生时受影响的进程数量
资源分配图，该图由一组结点和一组边组成
死锁定理用于检测系统所处的资源分配状态S是否为死锁状态
死锁的解除
进程终止
资源抢占
0 条评论
下一页
