操作系统原理课堂笔记.docx

第六章设备管理
一、输入输出操作（要求达到“识记”层次）
1、什么是输入输出操作：主存储器与外围设备之间的信息传送操作称为输入输出操作。
2、对于存储型设备，输入输出操作的信息传输单位为“块”。对输入输出型设备，输入输出操作的信息传输单位为“字符”
二、独占设备和共享设备（识记）
1、独占设备是指每次只能供一个作业执行期间单独使用的设备。如输入机、磁带机、打印机等
2、共享设备是指允许几个作业执行期间可同时使用的设备。
3、共享设备的“同时使用”的含义是指多个作业可以交替启动共享设备，当一个用业正在使用设备时其他作业暂不能使用，即每一时刻仍只有一个作业占用，但当一个作业正在使用设备时其他作业就可使用
三、独占设备的分配（领会）
1、独占设备的绝对号与相对号
这和绝对地址/相对地址的概念类似。绝对号就是将每一台设备确定一个编号（相当于一个绝对地址）。相对号就是为了用户程序的方便而设的，在用户请求使用时，采用“设备类-相对号”来提出使用设备要求。由系统建立绝对号与“设备类-相对号”之间的关系，就能正确启用设备了。
2、设备的指定方式　　 　　
1）指定绝对号：这种方式由作业直接指定绝对号对应的设备。系统只能把这个设备分配给他，如果该设备正由其他作业使用则申请不能得到满足。
绝对号就好象给每个人取一个不同的名字。上司的工作计划中有一条：十点钟叫张三去买菜。如果张三有空，就得张三去买
2）指定设备类、相对号：这种方式在申请设备时不指定具体哪台设备，只说明要某类设备多少台，这样可以由系统灵活分配。
设备类-相对号呢，就好比是一个部门，部门中有一些工作人员，上司的工作计划就只写成：十点叫买菜部找个人去买罗卜。这时就由“系统”来看看买菜部是否有人空闲，只要本部有人闲着能干活的，不管张三李四都可以去干。这样，对于上司来说，不用去记谁谁的名字，只要指定某部门，要多少人就是了，他的用人策略和具体的哪个人无关。这就是“设备独立性”
3）设备独立性：采用“设备类、相对号”方式使用设备时，用户编程就不必指定特定设备，在程序中由“设备类、相对号”定义逻辑设备。程序执行时由系统根据用户指定的逻辑设备转换成与其对应的具体物理设备。所以，用户编程时使用的设备与实际使用哪台设备无关，这就是“设备独立性”
4）如何实现独占性设备分配：对于独占性设备，系统采用“静态分配”的策略，就是当一个作业所需使用的独占设备能得到满足时，该作业才能被装入主存储器执行。
在操作系统中，设置“设备分配表”来记录计算机系统所配置的独占设备类型、台数和分配情况等。设备分配表由“设备类表”和“设备表”两部分组成。通过查表和修改表的操作完成设备分配工作。
四、磁盘的驱动调度（领会）
1、磁盘的结构（动画）2、访问磁盘的操作时间（动画）
3、磁盘的驱动调度：在多道程序设计系统中，同时有多个访问者请求磁盘操作，此时系统采用一定的调度策略来决定各等待访问者的执行次序，所以系统决定等待磁盘访问者的执行次序的工作就是磁盘的“驱动调度”
4、对磁盘进行驱动调度的目的：尽可能的降低多个访问者执行输入输出操作的总时间，增加单位时间内的输入输出操作次数，有利于系统效率的提高。
5、磁盘调度分为移臂调度和旋转调度。根据访问者指定的柱面位置来决定执行次序的调度称“移臂调度”；当移动臂定位后，如有多个访问者等待访问该柱面时，根据延迟时间来决定执行次序的调度称为“旋转调度”。
6、移臂调度算法包括以下四种：
1）先来先服务算法；
2）最短寻找时间优先调度算法；
3）电梯调度算法；
4）单向扫描调度算法。
以上几种算法要能够区分，如给你一个访问序列和访问条件，应能根据各种算法做出调度后的访问序列。
7、信息的优化分布：知道信息在磁盘上排列不一定是按顺序最优，对于一些能预知处理要求的信息采用优化分页可以缩短输入输出操作时间，提高系统效率
五、外围设备的启动(识记）
　　要想提高效率就要大胆放权，让下属对事负责而不是对人负责。
　CPU是很忙的，如果所有的事情都自己做，做得再好也不一定好，如果有人能帮他处理一些事情，他就可以腾出时间来做更多的事。通道就是中层干部，发挥他们的作用就能提高效率。
1、通道（channel）：计算机系统中能够独立完成输入输出操作的硬件装置，也称为“输入输出处理机”。
CPU并不直接操作外围设备，他连接通道（I/O处理机），通道连接设备控制器，设备控制器连接设备。CPU只需把“I/O"设备启动，并给出相关的操作要求。然后就由通道来处理输入输出事宜，做完后报告CPU。
} 2、通道命令和通道程序：
通道命令（CCW）规定设备的一种操作，通常由命令码、数据主存地址、传送字节个数及标志码等部分组成。
操作系统用一组通道命令来执行一次输入输出应做的工作，这一组通道命令就组成了一个“通道程序”。
命令码分成三类：数据传输类、通道命令转移类和设备控制类。
数据主存地址对于不同的命令有不同的作用，比如命令码为写的操作，主存地址指定的区域存放输出到外围设备的信息。
标志码：为非0时表示通道程序未结束。为0时表示通道程序结束。
传送字节个数，表示本命令应传输的字节个数。
3、通道地址字（CAW）和通道状态字（CSW）
用来存放通道程序首地址的主存固定单元称为“通道地址字”。
通道状态字：用于记录通道和设备执行情况的主存单元。通常包括通道命令地址、设备状态、通道状态和剩余字节个数等几个字段。
4、I/O中断：是指中央处理器和通道协调工作的一种手段。通道借助I/O中断请求CPU进行干预，CPU根据产生的I/O中断事件了解输入输出操作的执行情况，I/O中断事件是由于通道程序的执行或其他外界原因引起的，对通道操作而言，当操作正常结束或异常结束（如设备故障、设备特殊情况引起异常结束）形成I/O中断，由CPU根据相应情况分别处理。
六、虚拟设备SPOOL系统（领会）
1、实现虚拟设备的目的：用一种物理设备模拟另一类物理设备，使各作业在执行期间只使用虚拟的设备而不直接使用物理的独占设备。这种技术可使独占的设备变成可共享的设备，使得设备的利用率和系统效率都能得到提高。
2、实现虚拟设备的硬件条件：大容量磁盘；中断装置和通道；中央处理器与通道并行工作的能力。（另外，实现虚拟设备的软件条件是要求操作系统采用多道程序设计技术。）
3、虚拟设备的实现原理：对于多道程序，输入时将一批作业的信息通过输入设备预先传送到磁盘上。输出时将作业产生的结果也全部暂时存在磁盘上而不直接输出，直到一个作业得到全部结果而执行结束时再行输出。（就是用磁盘来模拟输入机和打印机的工作，把它们的工作内容先保存起来，然后一并执行）
4、SPOOL系统的组成和实现：
井：为实现虚拟设备在磁盘上划出的专用存储空间，用于存放作业的初始信息和执行结果。
SPOOL系统由三部分程序组成：
预输入程序。通过该程序把作业流中每个作业的初始信息传送到“输入井”保存起来以以备作业执行时使用。
井管理程序：通过该程序来保证作业正确及时地从“井”中读取或写入信息。它使得每个用户感觉到自己都在使用独立的输入输出设备。
缓输出程序。它负责查看“输出井”中是否有待输出的结果信息，若有则启动打印机把作业结果输出
5、实现虚拟设备为什么可以提高系统效率：
SPOOL系统借助硬件的中断装置和通道技术使得中央处理器与各种外围设备以及各外围设备之间均可并行工作。操作系统采用多道程序设计技术，合理分配处理器，实现联机的外围设备同时操作。
作业执行时从磁盘上读写信息来代替从输入机和打印机的读写操作，不仅使多个作业可以同时执行，而且加快了作业的执行速度，提高了单位时间内处理作业的能力。在作业执行的同时还可利用输入机继续预输入作业信息和利用打印机输出结果，于是，整个系统可以是第一批作业的执行结果在打印输出，第二批作业正在处理，第三批作业信息正在预输入到磁盘的“输入井”中。
这种联机同时操作极大地提高了独占设备的利用率，也使计算机系统的各种资源被充分利用。

通常把通道程序的执行情况记录在（csw )中

SPOOL系统中的数据结构包括：
（1）作业表。用来登记进入“输入井”的各个作业的作业名、作业状态、作业拥有的文件数以及预输入表和缓输出表的位置等。
（2）预输入表。每个作业都有一张预输入表，用来登记该作业初始信息的各个文件。指出各文件的文件名、传输信息时使用的设备类型、文件的长度以及文件的存放位置等。
（3）缓输出表。每个作业设一张缓输出表，用来登记该作业产生的结果文件。

在SPOOL系统中设计了一张作业表，简述该表的作用。
答:作业表供调度选择处于“收容状态”的作业。
作业执行时可从中找到该作业的“预输入表”，从而找到所需的文件。
从作业表中可找到该作业的“缓输出表”，以登记作业的执行。
在SPOOL系统中设计了一张“缓输出表”，请问哪些程序执行时要访问缓输出表，简单说明之在SPOOL系统中有两个程序要访问缓输出表：
井管理写程序把作业执行结果文件登记在缓输出表中；
缓输出程序从缓输出表中查找结果文件并打印输出
} 13、若干个等待访问磁盘者依次要访问的柱面为20,44,40,4，80,12,76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。
} (1)先来先服务算法：(2)最短寻找时间优先算法。

答：先来先服务算法：(20+24+4+36+76+68+64)*3=292*3=876 ms
最短寻找时间算法：（0+4+24+8+8+72+4)*3=120*3=360 ms
（注：各算法使移动臂的移动次序和移动的柱面数如下：
（1）40 → 20 → 44 → 40 → 4 → 80 → 12 → 76
20） （24） （4） （36） （76） （68） （64）
共移动292柱面
（2）40 → 44 → 20 → 12 → 4 → 76 → 80
（4） （24） （8） （8） （72） （4）
共移动120柱面
第七章 进程同步与进程通信
进程的顺序性与并发性（领会）
　　有人说，在程序中不是有跳转语句和重复语句，怎么就是顺序执行？注意，这里是指进程在处理器中的执行，因为处理器每次只能执行一个操作，因此每条指令必须按顺序进入CPU执行，假使有一条指令是跳转的，那么执行本指令后，会取出跳转目的地址的指令进入CPU运行，这个顺序是程序规定的。所以对CPU而言，进程总是按顺序执行。
　 进程是一个程序在一个数据集合上的一次执行，同一个程序和同一个数据集的运行结果必然是相同的。这就是可再现性。
同时执行并不是真的同时，因为任一时刻CPU中只能有一个进程运行。
1、进程的顺序性：任何进程在顺序的处理器上的执行是严格按照顺序进行的，这就是进程的顺序性。当一个进程独占处理器顺序执行时，具有两个特性：一、封闭性 二、可再现性。
2、进程的同时执行：在多道程序设计系统中，一个进程的工作没有全部完成之前，另一个进程就可以开始工作，它们的执行在时间上重迭的，我们把它们称为是“可同时执行的”。
3、进程的并发性：若系统中存在一组可同时执行的进程，则说该组进程具有并发性，并把可同时执行的进程称为“并发进程” 。
4、并发进程间的关系：并发进程相互之间可能是无关的，也可能是交往的。如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则这些并发进程相互之间是无关的。如果一个进程的执行依赖其他进程的执行，则这些并发进程之间是有交往的。
二、与时间有关的错误（简单应用）
1、并发进程的执行速度取决于自身和进程调度策略。一个进程运行时会被中断，且断点是不固定的，一个进程被中断后，哪个进程可以运行，被中断的进程什么时候占用处理器，是与进程调度策略有关的。因此进程的执行速度不能由自己决定。
2、并发进程交替使用共享资源时会出现与时间有关的错误。 由于共享资源的原因，加上进程并发执行的随机性，一个进程对另一个进程的影响是不可预测的。造成不正确的因素与进程占用处理器的时间、执行的速度以及外界的影响有关。因此被称为与时间有关的错误。
3、分析并发进程中与时间有关的错误，请理解教材上的例子。
} 三.相关临界区（领会）
1、临界区的定义：并发进程中与共享变量有关的程序段称为“临界区”
2、什么是相关临界区： 相关临界区是指并发进程中涉及到相同变量的那些程序段。
3、对相关临界区的管理要求。
1）一次最多让一个进程在临界区执行，当有进程在临界区时其他想进入临界区执行的进程必须等待。
2）任何一个进入临界区执行的进程必须在有限的时间内退出临界区，即任何一个进程都不应该无限地逗留在自己的临界区。
3）不能强迫一个进程无限地等待进入它的临界区，即有进程退出时应让一个等待进入临界区的进程进入它的临界区。
} 四、进程的互斥（综合应用）
1、进程互斥的含义：进程的互斥是指当有若干进程都要使用某一共享资源时，任何时刻最多只允许一个进程去使用，其他要使用该资源的进程必须等待，直到占用资源者释放了该资源。 　　
PV操作是两个过程，由他们两个来控制一个信号S，假设S是红灯的个数。
每个进程进入临界区前都要先执行P操作。退出临界区时执行V操作。用下面的比喻很容易理解:临界区门前有棵树（S）
　　 用来挂红灯
　　 进程想进CPU的门
　　 先得上树取盏灯（调用一次P操作）
　　 取下一个去敲门(S=S-1)
　　 如果树上没灯取(S≤0)
　　 树说欠你一盏灯(S为负时)
　　 没辙只好外边排队等(Wait(S))

　　 得灯进程续运行
　　 运行完了要出门（调用一次V操作）
　　 马上还回一盏灯(S=S+1)
　　 若有进程在催债(S≤0)
　　 放个进去事完成(Release(S))
实现进程互斥的工具－－PV操作。
PV操作是由两个操作，即P操作和V操作组成。P操作和V操作是两个在信号量上进行操作的过程。假定用S表示信号量则把这两个过程记作P（S)和V（S),它们的定义如下：
Procedue P(Var S: Semaphore);
begin S:=S-1;
if S<0 then W(S) end;
{P} Procedue V(Var S: Semaphore);
begin S:=S+1;
if S<=0 then R(S) end; {V}
为了确保PV操作自身的正确执行，因此P（S）和V（S）操作中不可中断，这种不可被中断的过程称为“原语”。
3、用PV操作管理相关临界区的一般形式
一个信号量与一组涉及共享变量的相关临界区联系起来，信号量的初值定为“1”　　
任何一个进程要进入临界区前先调用P操作，执行临界区的操作后，退出临界区时调用V操作。
由于信号量的初值为“1”，P操作起到了限制一次只有一个进程进入临界区的作用，其余进程欲进入临界区必须符合对临界区管理的第一个要求，即一次最多让一个进程在临界区执行。进程退出后执行V操作，若有进程在等待则释放一个进程，这样就达到了对临界区管理的第二个和第三个要求（即不能无限逗留也不能无限等待）。
五、进程的同步（综合应用）
1、进程同步的含义：进程的同步是指并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。 “生产者”与“消费者”是同步问题的典型例子。
　　 这里有两个消息量：一是“缓冲器里有物品”，二是“可把物品存入缓冲器”，这两个消息量对应需要两个信号量SPut和SGet。SP的初始值为1，如果初始时可用的缓冲器为n个，则SP＝n;SG的初始值为0。
　　 生产者进程调用P(SP)和V(SG),
　　 消费者进程调用P(SG)和V(SP)，根据SG和SP的值来决定是否可以存或取物。
2、正确使用PV操作实现进程同步。
(1)用一个信号量与一个消息联系起来，当信号量的值为0时表示期望的消息尚未产生，当信号量值为非0时表示期望的消息已经存在。
(2)在用PV操作实现同步时，一个信号量与一个消息量联系在一起，当有多个消息时必须定义多个信号量；测试不同的消息是否到达或发送不同消息时，应对不同的信号调用P操作或V操作。
3、使用PV操作实现进程同步与互斥的混合问题。
　　 进程的同步与进程的互斥都涉及到并发进程访问共享资源的问题。可以看到进程的互斥实际上是进程同步的一种特殊情况。若干进程互斥使用资源时，一个等待使用资源的的进程在得到占用资源的进程发出“归还资源”的消息（调用了V操作）后，它就可去使用资源。因此，互斥使用资源的进程之间实际上也存在一个进程依赖另一个进程发出信息的制约关系。所以，也把进程的互斥与进程的同步称为进程的同步。
4、PV操作实现进程同步与互斥时怎样定义信号量，信号量的物理含义及其作用
利用PV操作实现进程互斥时，用一个信号量与一组相关临界区对应，这些进程在同一个信号量上调用P操作和V操作来实现互斥。
利用PV操作实现进程同步时，每一个消息与一个信号量对应，进程在不同信号量上调用P操作以测试自己需要的消息是否到达，在不同信号量上调用V操作把不同的消息发送出去。
信号量的物理含义：
S＞0时表示可使用的资源数或表示可使用资源的进程数。
S＝0时表示无资源可供使用或不允许进程进入临界区。
S＜0时表示等待使用资源的进程个数或表示等待进入临界区的进程个数。
根据PV操作的性质，任何进程在使用共享资源前应调用P操作。当有可以使用的资源或允许使用资源时（S＞0），调用P(S)后不会成为等待，进程可以使用资源。当无资源可使用或不允许使用资源时（S≤0）调用P(S)后必然等待。任何进程可调用V操作来归还共享资源的使用权，当S＞0时调用V（S）后使可用资源数加1或使可用资源的进程数加1（也就是树上多挂上一个红灯笼）。当S≤0时调用V(S)后将释放一个等待使用资源或者释放一个等待进入临界区者。
六、进程通信（领会）
1、进程通信的含义：通过专门的通信机制实现进程间交换大量信息的通信方式称为“进程通信”
2、实现进程通信的基本原语：有两条：“send（发送）”和“receive（接收）”原语。
3、利用信箱通信时“发送”和“接收”原语的功能。
send(N,M) 功能：把信件M送到指定的信箱N中。
receive(N,X) 功能：从指定信箱N中取出一封信，存放到指定的地址X中。
4、信箱的基本结构：一个信箱由“信箱说明”和“信箱体”两部分组成。
七、线程的概念（识记）
线程是进程中可独立执行的子任务，一个进程中可以有一个或多个线程，每个线程都有一个唯一的标识符。
支持线程管理的操作系统有Mach,OS/2,WindowsNT,UNIX等。

共享变量是指（　只能被多个进程互斥访问的变量　）访问的变量。

} 　8、多项选择：一个进程向其他进程发送消息时，应组织好一封信件，内容包括（　　）。
　　A、接收者名　　　B、发送者名　　　C、具体信息
　　D、等不等回信标志　　　　E、回信存放地址
} 线程与进程的根本区别是把进程作为_资源分配_单位，而线程是_调度和执行__单位。
9、在具有n个进程的系统中，允许m个进程（n≥m≥1）同时进入它们的临界区，其信号量S的值的变化范围是_n-m≤S≤m ，处于等待状态的进程数最多n-m_个。

第八章 死锁
} 一、死锁的产生（领会）
　1、什么叫死锁： 若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又都在等待其中另一个进程所占用的资源，这种等待永远不能结束，则说系统出现了“死锁”。或说这组进程处于“死锁”状态。
2、引起死锁的因素：死锁的出现除了与资源的分配策略有关外，也与并发进程的执行速度有关，即操作系统对资源管理不得当或没有顾及进程并发执行时可能出现的情况，则就可能形成死锁。
1、系统出现死锁必然同时保持的四个必要条件：
1）互斥使用资源
2）占有并等待资源
3）不可抢夺资源
4）循环等待资源
这4个条件是必要条件而不是充分条件，意思是，只要发生死锁，那么这四个条件必然都成立。反之则不然，有时候即使四个条件都满足，那也不一定发生死锁。（从资源分配图中可以分析得到，即使形成循环等待资源，也不一定形成死锁。）
2、死锁的防止策略:要防止死锁形成，只要采用的资源分配策略能使上述4个条件中有一个条件不成立就可以了。
1）破坏互斥使用资源的条件经常是行不通的。因为资源本身特性就是互斥使用的。
2）要破坏“占有并等待条件”则可以采取两种办法：静态分配和释放已占资源。
静态分配也称为预分配资源，要求每一个进程在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的资源申请要求且把资源分配给进程后，该进程才能开始执行。
释放已占资源就是指进程申请资源时必须没有占用资源，如果已经占用了资源就要先归还所占的资源再申请。
3）实现可抢夺式分配：如果一个进程已经占有了某些资源又要申请新资源，而新资源不能满足（已被其它进程占用）必须等待时，系统可以抢夺该进程已占有的资源。
4）实现按序分配：把系统中所有资源排一个顺序，对每一个资源给一个确定的编号，规定任何一个进程申请两个以上的资源时，总是先申请编号小的资源，再申请编号大的资源。
三、死锁的避免（简单应用） 　　
死锁的避免不同于死锁的防止，死锁的防止是采用某种分配策略后，系统就不会产生死锁，这好比是你打过了某种预防针，再也不会得那种病。而死锁的避免是没有打预防针，但是通过其他办法，避免得病。因此有“安全状态”的说法，对应的，当然也有不安全状态。就像人都有得病的可能，不必任何病都打预防针。只要注意防病，仍然可以安全健康的生活。
安全状态:如果操作系统能保证所有的进程在有限的时间内得到需要的全部资源，则称系统处于“安全状态”。
四、死锁的检测（领会） 死锁的检测
就是既不打预防针，也不去避免得病，而是经常去体检，如果发现有病了就治疗。这是一种事后解决的办法，也算是解决死锁问题的一条途径。但这毕竟要付出较大代价.
1、什么是死锁的检测：对资源的申请和分配不加限制，只要有剩余的资源就可把资源分配给申请者。这样可能会出现死锁，系统定时运行一个“死锁检测程序”，如果检测到死锁发生，则必须先解除死锁再继续工作。
2、怎样实现死锁的检测：1、每个资源当用中只有一个资源2、资源类中含有若干个资源。
3、死锁的解除：一般采用两种方式来解除死锁，一种是终止一个或几个进程的执行以破坏循环等待；另一种是从涉及死锁的进程中抢夺资源。
检测死锁和解除死锁都要付出很大代价。所以用死锁检测的方法解决死锁问题只适用于不经常发生死锁的系统中。
死锁检测必须解决两个问题，一是怎样_判断系统是否出现_死锁。二是当有死锁发生时怎样__解除__死锁。

总之，银行家算法要保证分配资源时系统现存资源一定能满足至少一个进程所需的全部资源。这样就可以保证所有进程都能在有限时间内得到需要的全部资源。这就是安全状态。

8 / 8