操作系统复习.docx
《操作系统复习.docx》由会员分享，可在线阅读，更多相关《操作系统复习.docx（34页珍藏版）》请在冰点文库上搜索。
操作系统复习
第二章
顺序执行与并发执行
v程序顺序执行指的是在有多个程序需要执行的情况下，处理器严格按照某一顺序按序执行，每次只执行一个程序。
其实质是单道程序系统。
v特点:
顺序性、资源封闭性、可再现性
v不足：
资源效率低下
v前趋图定义
v有向无循环图
v表示方式：
v
（1）p1--->p2
v
（2）--->={（p1,p2）|p1必须在p2开始前完成}
v节点表示：
一条语句，一个程序段，一进程。
v多道程序设计
٭同一时刻内存中存放了多个作业，处理器交替运行不同的作业。
提高了系统的效率，尤其是资源利用率。
٭特点
▪多道
▪宏观上并行
▪微观上串行
٭问题
▪系统管理复杂化
v程序并发执行带来的新特征
٭资源共享性；
٭间断性
程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。
٭失去封闭性
程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。
这样，某程序在执行时，必然会受到其它程序的影响。
例如，当处理机这一资源已被某个程序占有时，另一程序必须等待。
٭不可再现性
程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。
v结论：
٭程序的并发执行使得程序的执行情况不可预见，其结果不再唯一，成为一个动态的过程。
而程序是一个静态的概念，不再能切实反映程序执行的各种特征（独立性、并发性、动态性）。
进程的三种基本状态及其转换
v进程的三种基本状态：
就绪状态、执行状态、阻塞状态
五状态进程模型
v内存资源紧张
v无就绪进程，处理机空闲：
I/O的速度比处理机慢得多，可能出现全部进程阻塞等待I/O
解决方法
v采用对换技术：
换出一部分进程到外存，以腾出内存空间
v采用虚拟存储技术：
每个进程只能装入一部分程序和数据（存储管理部分）
v将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外存，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的数据和程序，换入内存。
进程被交换到外存，状态变为挂起状态
v进程挂起的原因
٭进程全部阻塞，处理机空闲。
٭系统负荷过重，内存空间紧张。
٭操作系统需要。
٭终端用户请求。
٭父进程请求。
v进程状态的转换
٭就绪就绪/挂起
٭阻塞阻塞/挂起
٭就绪/挂起就绪
٭阻塞/挂起阻塞
引入进程原因:
为了使程序在多道程序环境下能并发执行并能对并发执行的程序加以控制和描述从而在操作系统中引入了进程概念。
进程的定义:
进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。
它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。
进程的组成:
进程是由程序、数据集合、进程控制块（PCB）3部分组成，统称为进程映像。
PCB的功能:
提供进程的各种信息，以便操作系统控制和管理进程。
所谓创建进程，实质上是创建进程实体中的PCB；而撤消进程，实质上是撤消进程的PCB。
PCB的组织方式:
1）单一队列
所有进程的PCB通过链表组织成为一个单一队列，适用于进程数目不多的系统。
如：
Windows操作系统。
2）多级队列（链接方式）
这是把具有同一状态的PCB，链接成一个队列。
这样，可以形成就绪队列、若干个阻塞队列等。
对其中的就绪队列常按进程优先级的高低排列，把优先级高的进程的PCB排在队列前面。
此外，也可根据阻塞原因的不同而把处于阻塞状态的进程的PCB排成等待I/O操作完成的队列和等待分配内存的队列等。
3）表格结构（索引方式）
系统根据所有进程的状态建立几张索引表。
例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。
在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。
进程与程序的区别和联系:
（1）程序是静态的，进程是动态的。
程序是有序代码的集合；进程是程序的一次执行。
（2）进程是暂时的，程序的永久的。
进程是一个变化的过程，有生命周期，暂时存在，程序没有生命周期，可长久保存。
（3）进程还是操作系统资源分配和调度的基本单位，程序没有此功能。
（4）进程与程序的对应关系。
通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
（5）进程与程序的结构不同。
进程的控制:
操作系统对进程的控制包括进程的创建与撤销、挂起与激活、阻塞与唤醒以及进程切换等操作，这些操作通过操作系统内核中的一组原语实现。
引入线程原因:
为了描述和实现多个程序的并发执行，以改善资源利用率及提高系统的吞吐量。
进程与线程的联系:
线程是进程的一个实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。
线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源，但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发。
线程的调度:
同一进程中的多个线程之间进行切换时，不会引起进程的切换。
但是，当一个进程中的线程切换到另一进程中的线程时，将会引起进程的切换。
进程调度
调度类型（长程调度、中程调度、短程调度）:
1、长程调度（高级调度，作业调度）
▪将外存作业调入内存，创建PCB等，插入就绪队列。
▪一般用于批处理系统，分/实时系统一般直接入内存，无此环节。
٭调度特性
▪接纳作业数（内存驻留数）
太多―――>周转时间T长
太少―――>系统效率低
▪接纳策略：
即采用何种调度算法：
FCFS、短作业优先等
v2、中程调度（中级）
为提高系统吞吐量和内存利用率而引入的从内存外存对换功能（换出时，进程为挂起状态）
v3、短程调度（进程调度，低级调度）
v决定就绪队列中的哪个进程将获得处理机。
v短程调度运行频率最高。
v现代操作系统几乎都具有短程调度功能。
v运行频率：
短>中>长。
常见调度算法（FCFS、短作业优先，响应比高者优先、时间片轮转、多级反馈调度）:
v1.先来先服务（FCFS）调度算法（非剥夺）
٭特点：
简单，有利于运行时间较长的进程（或长作业即CPU繁忙性作业）
v2.短进程（作业）进程优先调度算法（非剥夺）
٭提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）
٭特点：
对运行时间较长的进程（长作业）不利，有可能得不到服务（饥饿）
٭估计时间不易确定
3.时间片轮转调度算法
٭时间片大小的确定：
太大：
退化为FCFS；太小：
系统开销过大
٭系统对响应时间的要求；T=nq
٭就绪队列中进程的数目；
٭系统的处理能力：
（应保证一个时间片处理完常用命令）
٭常用于分时系统及事务处理系统，合理的时间片大小将带来满意的响应时间。
٭通常，合理的时间片指，能让80%左右的进程在一个时间片内完成。
٭对于短的，计算性的进程较有利。
٭不适合于批处理系统的进程调度。
٭不利于I/O型的进程。
4.响应比高者优先：
R=（w+s）/s=w/s+1
٭将进程的等待时间和执行时间纳入优先级的计算。
R=（w+s）/s=1+w/s（其中w为等待时间，s为执行时间）
٭
（1）短作业RP大。
٭
（2）s（要求服务时间）相同的进程间相当于FCFS。
٭（3）长作业等待一段时间仍能得到服务。
5.反馈调度算法
应设置多个就绪队列，并为各个队列赋予不同的优先级。
第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。
该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。
例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
v特点：
长、短进程兼顾，有较好的响应时间
٭
（1）短进程一次完成；
٭
（2）中型进程周转时间不长；
٭（3）长进程不会长期不处理。
四种基本的实时调度算法:
vA.基于时间片轮转调度算法秒级
vB.基于优先级非剥夺调度算法秒~毫秒级
vC.基于优先级的剥夺点调度毫秒级
vD.立即剥夺调度毫秒~微秒级
进程并发控制：
互斥与同步
几种互斥与同步解决方法:
v软件方法
v硬件方法
v信号量方法
v管程方法
v消息传递方法
互斥条件:
空闲让进、忙则等待、有限等待、让权等待
临界区:
不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。
人们把在每个进程中访问临界资源的那段代码称为临界区。
若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。
当进程需要使用临界资源，必须获得临界区的使用权。
在进入临界区之前要判断是否有进程在临界区内，如果有则阻塞自己，如果没有，进程进入临界区，并且设置临界区使用标志，阻止其他进程进入临界区，使用完毕，还需修改临界区标志。
信号量:
v信号量方法能实现进程互斥与同步，而不必“忙等”。
v两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以“向前推进”的信号（被唤醒）。
v相应地，将实现信号灯作用的变量称为信号量，可定义为记录型变量，其中一个域为整形，另一个域为队列，其元素为等待该信号量的阻塞进程。
v工程实际证明，利用信号量方法实现进程互斥是高效的，一直被广泛采用。
wait（）、signal（）:
用wait（s）和signal（s）实现同步与互斥。
s.count初值表示系统中某类资源的数目。
进程进入临界区之前，首先执行wait（s）原语，若s.count<0,则进程调用block（）阻塞原语，将自己阻塞，并插入到s.queue队列排队。
所以如果s.count<0，|s.count|表该信号量链表中已阻塞进程的数目。
当其它进程执行了signal（s）原语，若s.count<=0，说明阻塞队列中还有被阻塞的进程，则调用wakeup（）唤醒原语，把s.queue中第一进程修改为就绪状态，送就绪队列，准备执行临界区代码。
互斥信号量:
v互斥信号量用于申请或释放资源的使用权，常初始化为1。
资源信号量:
v资源信号量用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数。
vwait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己；
vsignal操作用于释放资源（或归还资源使用权），进程执行signal原语，有责任唤醒一个阻塞进程。
信号量的物理意义:
（1）若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数，亦即等于s所代表的实际使用的物理资源个数。
（2）若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待进程的个数，亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数。
（3）通常P操作意味着请求一个资源，V操作意味着释放一个资源。
在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作。
进程同步互斥基本概念:
进程同步是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。
进程间的直接制约关系来源于他们之间的合作。
进程互斥也是进程之间的间接制约关系。
当一个进程进入临界区使用临界资源时，另一个进程必须等待。
只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。
生产者/消费者问题:
生产者/消费者必须同步:
生产者不能向满缓冲区写数据，消费者不能从空缓冲区取数据，即生产者与消费者必须同步。
生产者/消费者必须互斥:
生产者和消费者必须互斥进入缓冲区，即，某时刻只允许一个进程（生产者或消费者）访问缓冲区，生产者必须互斥消费者和其它任何生产者。
读者/写者问题
v多个进程访问一个共享数据区，如果数据库、文件、内存区及一组寄存器等的数据问题建立了一个通用模型，其中若干读进程只能读数据，若干写进程只能写数据。
v多个进程同时读一条数据可以的，但如果一个进程正在更新数据时，则所有其他进程都不能访问（读或写）该记录。
v允许多个读者进程可以同时读数据；
v不允许多个写者进程同时写数据，即只能互斥写数据；
v若有写者进程正在写数据，则不允许读者进程读数据。
v严格互斥任何读者和写者进程，可以保证数据更新操作的正确性。
v但是，对于若干读者进程被严格互斥严重影响了系统效率。
显然应该让多个读者同时读数据。
v如果一个写者进程正在修改数据，别的写者和读者都不能访问该数据。
读者优先
v当一个读者正在读数据时，另一个读者也需要读数据，应该允许第二个读者进入，同理第三个及随后更多的读者都被允许进入。
v现在假设一个写者到来，由于写操作时排他的，所以它不能访问数据，需要阻塞等待。
如果一直都有新的读者陆续到来，写者的写操作将被严重推迟。
v该方法称为“读者优先”。
即，一旦有读者正在读数据，允许多个读者同时进入读数据，只有当全部读者退出，才允许写者进入写数据。
写者优先
v为了防止“读者优先”可能导致写者饥饿，可以考虑写者优先。
v当共享数据区被读者占用时，后续紧邻到达的读者可以继续进入，若这时有一个写者到达且阻塞等待，则写者后面到来的若干读者全部阻塞等待。
v也就是说，只要有一个写者申请写数据，则不再允许新的读者进入读数据，这样，写者只需等待先于它到来的读者完成其读数据任务，而不用等待其后到来的读者。
v这种方法解决了写者饥饿问题，但降低了并发程度，使系统的性能降低。
哲学家进餐问题
进程间通过信箱进行消息传递
v直接寻址（直接通信）方式：
点到点的发送
Send（destination,message）；
Receive（source,message）；
v间接寻址（间接通信）方式：
以信箱为媒介进行传递
Send（mailbox,message）；
Receive（mailbox,message）；
v采用“不阻塞发送，阻塞接收”方式。
v多个并发执行的发送进程和接收进程共享一个邮箱mutex，它被初始化为一个无内容的“空”消息。
v如果一个进程希望进入临界区，首先必须申请从mutex邮箱中接收一条消息。
若邮箱为“空”，则该进程阻塞（接收）；若进程收到邮箱中的一条消息，则进入临界区，执行完毕以后，退出临界区，并将该消息发送回邮箱mutex中。
什么是死锁:
多个进程运行过程中因争夺资源而造成的一种僵局，无外力作用，它们都无法向前推进。
死锁产生的四个必要条件:
v1.互斥：
竞争的资源一次只能被一个进程使用。
v2.占有且等待：
当一个进程占有一些资源，同时又申请新的资源，如果新资源申请失败，进程将占有资源且阻塞等待。
v3.非剥夺：
进程已占有的资源不能被其它进程强行剥夺。
v4.循环等待：
在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有一些资源，同时又申请环形请求链中下一个进程所占有的资源。
解决死锁的方法:
v1.预防死锁：
破坏4个条件之一；有效，使资源利用率低。
v2.避免死锁：
防止进入不安全态。
v3.检测与解除死锁：
检测到死锁再清除。
利用银行家算法避免死锁:
死锁的检测与解除:
死锁定理:
v若能消去资源分配图中所有节点的连接边，使全部节点都成为孤立节点，则称该图是可以完全简化图；若不能使该图完全简化，则称该图是不可完全简化图。
v当且仅当系统某状态S所对应的资源分配图是不可完全简化的，则S是死锁状态。
该充分条件称为死锁定量。
死锁检测算法:
解除死锁:
v撤销死锁进程。
该方法是目前操作系统中解除死锁的常用方法。
v把死锁进程恢复到前一个检查点，重新执行每个进程。
v按照某种原则逐个选择死锁进程进行撤销，直到解除系统死锁。
v按照某种原则逐个剥夺进程资源，直到解除死锁。
v最小代价原则
٭已花费处理机的时间最少的进程。
٭已产生输出最少的进程；
٭估计未执行部分最多的进程；
٭已获得资源量最少的进程。
٭优先级最低的进程。
中断：
指当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。
即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。
原语：
指由若干个机器指令构成的完成某种特定功能的一段程序，具有不可分割性；即原语的执行必须是连续的，在执行过程中不允许被中断。
响应时间：
响应时间是指从终端用户发出一条命令开始，到系统处理完这条命令并做出回答为止或开始处理先显示指示信息所需的最大时间间隔
周转时间:
从作业被提交给系统开始， 到作业完成为止这段时间间隔。
优先权:
系统吞吐量:
就是吸纳和流出的总和量。
响应比:
临界资源:
一次仅允许一个进程访问的资源
安全状态:
第三章
程序的3种装入方式
三种装入方式：
绝对装入方式、可重定位装入方式、运行时重定位方式
v绝对装入：
٭编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。
٭绝对地址的产生：
（1）由编译器完成，
（2）由程序员编程完成。
v可重定位装入方式:
٭目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。
٭由装入程序将装入模块装入内存后，装入模块中程序所访问的所有逻辑地址与实际装入内存的物理地址不同，必须进行地址映射，将逻辑地址转换为物理地址。
٭静态重定位技术：
地址映射在程序装入时进行，以后不再更改程序地址。
v运行时重定位:
٭在程序运行时动态进行程序的地址转换。
٭硬件的支持，即重定位寄存器，用于保存程序的在内存中的起始地址。
٭能保证进程的可移动性，有效的提高内存的使用效率。
٭运行时重定位有利于多道程序环境下，进程的换进/换出及实现紧凑技术。
程序的3种链接方式
v1）、静态链接:
在程序装入之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。
v2）、装入时动态链接:
这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。
٭a.便于修改和更新
٭b.便于实现对目标模块的共享
v3）、运行时动态链接:
这是指对某些目标模块的链接，是在程序执行中需要该（目标）模块时，才对它进行的链接。
逻辑地址:
由程序产生的与段相关的偏移地址部分
物理地址:
出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址
重定位:
把程序的逻辑地址空间变换成内存中的实际物理地址空间的过程
固定分区方式
v特点：
将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。
有n个分区，则可同时装入n个作业/任务。
v一、分区大小：
٭相等:
当程序太小时，会造成内存空间的浪费。
当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。
٭不相等：
可把内存区划含有多个较小的分区、适量的中等分区及少量的大分区。
不相等利用率更高。
v二、内存分配：
٭为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表。
v三、特点：
٭简单，有内部碎片（内零头）
动态分区方式（分配算法，回收算法，紧凑）
v一、分区组织
٭1．空闲分区表：
在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。
٭2．空闲分区链：
为了实现对空闲分区的分配和链接，设置前向指针和后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链。
v二、分区分配
٭1．首次适应算法FF。
v每次都从头开始，寻找第一个满足需求的空闲分区。
v特点：
找到第一个大小满足的分区，划分。
有碎片（外零头），低址内存使用频繁。
٭2．循环首次适应算法。
v与1类似，从上次找到的空闲分区的下一个开始查找。
v特点：
空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。
٭3．最佳适应算法
v分区按大小递增排序；分区释放时需插入到适当位置。
v特点：
产生无法利用的小碎片。
v三、分区回收
当进程运行完毕释放内存时，需合并相邻的空闲分区，形成大的分区，称为合并技术。
٭
（1）上邻空闲区：
合并，改大小
٭
（2）下邻空闲区：
合并，改大小，首址。
٭（3）上、下邻空闲区：
合并，改大小。
٭（4）不邻接，则建立一新表项。
紧凑:
٭通过作业移动将原来分散的小分区拼接成一个大分区。
٭作业的移动需重定位。
是动态（因作业已经装入）
离散分配方式（分页存储管理，分段存储管理，段页式存储管理）
٭分页存储管理
▪将一个进程的逻辑地址空间分成若干个大小相等的页面，把内存空间分成与页面相同大小的若干个存储块，称为页框，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的页框中。
٭分段存储管理
▪作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。
每个段都有自己的名字。
每个段都从0开始编址，并采用一段连续的地址空间。
段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。
٭段页存储管理
▪是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。
分页存储管理方式地址变换机构和过程（含具有快表的情况）
v完成：
逻辑页号——物理页框号的映射，由页表完成。
v一、基本地址变换机构：
٭越界保护
٭每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。
具有快表的地址变换机构
v不具有快表，则需两次访问内存。
٭
（1）访页表
٭
（2）得到绝对地址内容
v有快表，速度提高。
v快表贵，不能太多。
虚拟存储技术
为什么要引入:
٭
（1）有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行。
٭
（2）有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。
特征:
v1．离散性：
٭部分装入（若连续则不可能提供虚存），无法支持大作业小内存运行。
v2．局部性：
局部装入，多次装入。
v3．对换性：
٭对换性是指允许在作业运行过程中换进、换出。
٭换进和换出能够有效提高内存利用率。
v4．虚拟性：
٭虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远远大于实际容量。
٭虚拟性是以多次性和对换性为基础的。
实现虚拟存储的关键技术:
请求分页系统（请求分页的页表机构、缺页中断机构、地址变换机构）
请求分段系统（请求分段的段表机构、缺段中断机构、地址变换机构）
请求分页系统的基本原理:
v建立在基本分页基础上，支持虚拟存储器功能，增加了请求调页和页面置换功能。
٭每次调入和换出的基本单位都是长度固定的页面。
比
升级会员 