OS操作系统复习(共62页)

精选优质文档-倾情为你奉上第一章1理解操作系统的概念操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合它们管理和控制计算机系统中软硬件资源，合理地组织计算机工作流程，以便有效地利用这些资源为用户提供一个足够的功能、使用方便、可扩展、安全和可管理的工作环境，从而在计算机与用户之间起到接口作用。 2掌握三种基本类型及特点（1）批处理操作系统的特点是：脱机使用，多道和成批处理（2）分时操作系统特点：交互性，多用户同时性，独立性（3）实时系统的特点：提供即时响应和高可靠性3理解操作系统的功能4*熟练掌握算法描述的规则 (参第三章的实例)变量定义：a：int变量赋值：a:=2开始结束：beginend循环：Repeatforever，repeatuntil，whiledood，ifthenelsefi第2章1理解操作系统与用户两类接口。操作系统为用户提供两个接口界面。一个是系统为用户提供的各种命令接口界面。用户利用这些操作命令来组织和控制作业的执行或管理计算机系统。另一个接口是系统调用。编程人员使用系统调用来请求操作系统提供服务。操作系统的命令控制界面就是用来组织和控制作业运行的。 2理解作业级接口（1）图形用户接口图形接口:图形用户接口采用了图形化的操作界面，用非常容易识别的各种图标来将系统各项功能、各种应用程序和文件，直观、逼真地表示出来。用户可通过鼠标、菜单和对话框来完成对应程序和文件的操作。图形用户接口元素包括窗口、图标、菜单和对话框，图形用户接口元素的基本操作包括菜单操作、窗口操作和对话框操作等。（2）命令行接口命令接口:为了便于用户直接或间接控制自己的作业，操作系统向用户提供了命令接口。命令接口是用户利用操作系统命令组织和控制作业的执行或管理计算机系统。命令是在命令输入界面上输入，由系统在后台执行，并将结果反映到前台界面或者特定的文件内。命令接口可以进一步分为联机用户接口和脱机用户接口。3掌握常用操作系统的命令、命令组合（课堂介绍的）Ls列出当前目录下的文件和目录（Linux）cd设置当前目录（Linux and Windows）Dir列出当前目录下的文件和目录（Windows） type显示文件内容（windows）Cat 显示文件内容（Linux） ipconfig ip配置 path显示路径设置Echo off关闭回显。 Mem查看内存使用情况重定向符号“”xcopy 拷贝目录与文件ren改变文件名4能阅读理解简单的batch和shell脚本程序 (课件 5，28，作业)例如：c:copy try.bat d: & del *.batc:copy try.bat d: | del *.bat5了解系统调用的概念及基本用法系统调用是操作系统提供给编程人员的唯一接口。大致分为以下六类：（1）设备管理。该类系统调用被用来请求和释放有关设备以及启动设备操作等（2）文件管理。包括对文件的读写创建删除等（3）进程控制。进程是一个在功能上独立的程序的一次执行过程。进程控制的有关调用包括（4）进程创建，执行，撤销，执行等待和执行优先级控制等（5）存储管理。包括调查作业占据内存区的大小，获取作业占据内存去的始址等。（6）进程通信。该类系统调用被用在进程之间传递信息或信号。（7）线程管理。包括线程创建调度执行撤销等。6了解系统调用的实现原理把用户进程的请求传达给内核，待内核把请求处理完毕后再将处理结果送回给用户空间。第3章 1掌握进程的概念、组成、并发、并行与执行的异步性。(课件6) 了解并发执行条件（Beistein条件）(1)概念：进程是一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。(2)组成：进程的静态描述由三部分组成：进程控制块PCB，有关程序段和该程序段对其进行操作的数据结构集。(3)并发、并行：并发和并行是即相似又有区别的两个概念，并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。倘若在中有多个处理机，则这些可以并发执行的程序便可被分配到多个处理机上，实现并行执行，即利用每个处理机来处理一个可并发执行的程序，这样，多个程序便可以同时执行。(4)执行的异步性：在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行开始时间都是随机的。(5)Beistein条件:1966年Bernstein（伯恩斯坦）提出了两相邻语句S1，S2可以并发执行的条件：将程序中任一语句Si划分为两个变量的集合R(Si)和W(Si)。R(Si)称为读集；W(Si)称为写集。其中R(Si)=a1 a2 am，ai(j=1，m)是语句Si在执行期间必须对其进行读的变量；W(Si)=b1 b2 bn，bj(j=1，n)是语句Si在执行期间必须对其进行修改的变量；如果对于语句S1和S2，有 R(S1) W(S2)=， W(S1) R(S2)=， W(S1) W(S2)= 同时成立，则语句S1和S2是可以并发执行的。n 有以下语句P1-P4，其中a、b、c、d、x、y、z为变量并有初值；试写出它们的读集与写集，判断哪些语句可以并发执行？画出它们的前趋图。n P1:a=x+yn P2:b=z+1n P3:c=a+bn P4:d=c-2(6)程序执行的异步性经典例子：例1：设余票单元为 count，xi为工作变量单元；有 N 个售票窗口进行售票Process Pi(i=1,2,n) beginBegin count:integer;Var Xi:integer; Cobegin按旅客要求找到 count; P1;Xi:=count; P2; If Xi=1 then begin Pn; Xi:=Xi-1; Coend count:=Xi; end. 输出一张票; endelse 输出“票已售完”;End;例2：2掌握PCB的作用与地位（1）作用：系统根据PCB感知进程的存在和通过PCB中所包含的各项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。（2）地位：进程控制块是用来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。PCB集中反映一个进程的动态特征。3了解进程上下文的概念，进程切换与模式切换（1）操作系统中把进程物理实体（程序、数据和PCB）和支持进程运行的环境（寄存器与堆栈）合称为进程上下文，实际上是进程执行过程中顺序关联的静态描述。它与进程的切换和处理机状态转换（用户态 系统态，也称为模式切换）有关。所谓上文是指已执行过的进程指令和数据在相关寄存器与堆栈中的内容；正文是指正在执行的进程指令和数据在相关寄存器与堆栈中的内容；下文是指待执行的进程指令和数据在相关寄存器与堆栈中的内容。（2）（3）模式切换并不同与进程切换，它不一定引起进程状态的改变，在大多数操作系统中也不一定引起进程的切换，因此，它常常只需要保存一些寄存器中的内容、根据中断号设置PC的内容、切换到系统态执行中断处理程序。当系统调用完成后再次通过模式切换来继续执行原来被中断的用户进程。4*熟练掌握进程的状态及其转换，转换原因思考：1、为什么没有从就绪态到等待态的转换？ 2、为什么没有从等待态到执行态的转换？5理解进程控制的实现所谓进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。一般地，把系统态下执行的某些具有特定功能的程序段称为原语。原语可分为两类：一类是机器指令级的，其特点是执行期间不允许中断，正如在物理学中的原子一样，在操作系统中，它是一个不可分割的基本单位。另一类是功能级的，其特点是作为原语的程序段不允许并发执行。这两类原语都在系统态下执行，且都是为了完成某个系统管理所需要的功能和被高层软件所调用。用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等。6掌握进程间的制约关系及所表现的互斥与同步概念，要能判断进程间的同步和互斥（1）临界区：一次只允许一个进程进行访问的资源。（2）间接制约：由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约，简称间接制约。（3）互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。（4）一组并发进程互斥执行时必须满足如下准则：不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区。（并发进程异步执行）并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区。（临界区空闲让进）并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。（并发进程互斥执行）并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区。（并发进程有限等待）（5）同步：存在有因为并发进程互相共享对方的私有资源所引起的直接制约。直接制约将使得各并发进程同步执行。7理解锁机制解决互斥的方法设临界区的类名为。为了保证每一次临界区中只能有一个程序段被执行，又设锁定位 key 。key表示该锁定位属于类名为的临界区。加锁后的临界区程序描述如下：lock(key )临 界 区unlock(key )设key =1时表示类名为的临界区可用，key =0时表示类名为的临界区不可用。则，unlock(key )只用一条语句即可实现。即：key 1不过，由于lock(key )必须满足key =0时，不允许任何进程进入临界区，而key =1时仅允许一个进程进入临界区的准则，因而实现起来较为困难。8掌握信号量（私有、公有）和P、V原语的概念及用法（直接制约） （间接制约）私有信号量 公有信号量一般来说，也可以把各进程之间发送的消息作为信号量看待。与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为私用信号量（Private Semaphvre）。一个进程Pi的私用信号量Semi是从制约进程发送来的进程Pi的执行条件所需要的消息。与私用信号量相对应，称互斥时使用的信号量为公用信号量。信号量的物理意义：大于零：表示可用资源数目。小于零：绝对值表示请求资源而被阻塞的进程数p原语为申请资源v原语为释放资源pv操作必须成对出现。关于，原语的实现，有许多方法。这里介绍一种使用加锁法的软件实现方法，实现过程描述如下：（sem）：begin封锁中断；lock（lockbit）valsem=valsem-1if valsem=1 then begin Pn;Xi:=Xi-1; coendcount:=Xi; end.V(s);输出一张票;EndElseBeginV(s);输出“票已售完”;End;End; 两个火车站 A、B 之间是单轨连接，现有许多列车同时到达 A 站，经 A 站到 B 站，列车驶出 B 站后又可分路行驶。为了保证行车安全，请用信号量机制设计一个自动调度算法。 Program mutualexclusion; begin ( * main program * ) Count=n; (* n为列车数*); cobegin Var s:semaphore(:=1); P(1); Procedure P(i:integer); P(2); Begin P(n); Repeat coend P(s); end. 列车驶入A、B段; V(s); 列车分路行驶 Forever End;用，原语操作实现同步：例：设进程PA和PB通过缓冲区队列传递数据（如图3.13）。PA为发送进程，PB为接收进程。PA发送数据时调用发送过程deposit(data)，PB接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件：（1）在PA至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度），即缓冲区空时PB不能取数；（2）PA往缓冲队列发送数据时，至少有一个缓冲区是空的，即缓冲区满时PA不能送数；（3）由PA发送的数据块在缓冲队列中按先进先出（FIFO）方式排列。描述发送过程deposit(data)和接收过程remove(data)。解：由题意可知，进程PA调用的过程deposit(data)和进程PB调用的过程remove(data)必须同步执行，因为过程 deposit(data)的执行结果是过程remove(data)的执行条件，而当缓冲队列全部装满数据时，remove(data)的执行结果又是deposit(data)的执行条件，满足同步定义。从而，按以下三步描述过程deposit(data)和remove(data)：（1）设Bufempty为进程PA的私用信号量，Buffull 为进程PB的私用信号量；（2）令Bufempty的初始值为n（n 为缓冲队列的缓冲区个数），Buffull 的初始值为0；（3）描述：PA: deposit(data):begin local xP(Bufempty)；按FIFO方式选择一个空缓冲区Buf(x)；Buf(x) dataBuf(x)置满标记（Buffull）endPB: remove(data):Begin local x （Buffull）；按FIFO方式选择一个装满数据的缓冲区Buf(x)data Buf(x)Buf(x)置空标记 （Bufempty）end这里，局部变量x用来指明缓冲区的区号，给Buf(x)置标志位是为了便于区别和搜索空缓冲区及非空缓冲区。（思考：在该题中需要考虑互斥吗？为什么？如果每次只允许一个进程对缓冲队列进行操作时怎么办？）10*熟练掌握应用P、V原语解决同步问题（生产者与消费者、读者与写者（读者优先）（多看实例） 假如是一个生产者、一个消费者，且缓冲区有 N 个单元。 当缓冲区没有放满 N 个数据时，生产者进程调用 P（Se）都不会成为等待状态，可以把数据送入缓冲区。但当缓冲区中已有 N 个数据时，生产者进程想要再送数将被拒绝。由于每送入一个数后要调用 V（Sf），所以此时 Sf 的值表示缓冲区中可取的数据数，只要 Sf 0，消费者进程在调用 P（Sf）后总可以从缓冲区取数。每取走一个数据就调用 V（Se），因此增加了一个存放数据的位置。可以用指针 in 和 out 分别指示生产者进程向缓冲区送数和消费者进程从缓冲区取数的相对位置；指针的初始值为“0”。 这种情况下生产者与消费者进程的同步算法为：读者/写者问题：读者优先信号量 wsem 用来实现互斥，只要有 writer在访问共享数据区，其他 writers 或 readers 就不能访问数据区。reader 进程同样利用 wsem 实现互斥。为了适用于多个 reader，当没有 reader 读时，第一个进行读的 reader 要测试 wsem，当已经有 reader 在读时，随后的 reader 无须等待就可读取数据区。一旦有一个 reader 访问数据区，只要还有一个 reader 在进行读操作，reader 就可以保持对数据区的控制，这就容易导致 writers 饥饿。 设A、B两点之间是一段东西向的单行车道，现在要设计一个AB路段自动管理系统，规则如下：当AB间有车辆在行驶时，同方向的车辆可以驶入，另一方向的车辆必须在AB段外等待；当AB段之间无车辆行驶时，任一方向到达的车辆都可驶入，但不能从两个方向同时驶入；当某方向在AB段行驶的车辆驶出AB段且暂无车辆进入AB段时，应该让另一方向等待的车辆进入AB段行驶。试用信号量和P、V操作管理AB段车辆的行驶。 信号量设置如下：Int CA：=CB：=0；Var mutex,ma,mb：semaphore；mutex：=ma：=mb：=1；算法描述如下：cobeginP向西；P向东；coend11理解进程的通信方式（消息缓冲、邮箱、管道）（1）消息缓冲机制发送进程和接收进程采用消息缓冲机制进行数据传送时，发送进程在发送消息前，先在自己的内存空间设置一个发送区，把欲发送的消息填入其中，然后再用发送过程将其发送出去。接收进程则在接收消息之前，在自己的内存空间内设置相应的接收区，然后用接收过程接收消息。由于消息缓冲机制中所使用的缓冲区为公用缓冲区，使用消息缓冲机制传送数据时，两通信进程必须满足如下条件： 消息队列的互斥操作-在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对该缓冲区消息队列的访问。否则，将引起消息队列的混乱。同理，当接收进程正从消息队列中取消息缓冲时，也应禁止其他进程对该队列的访问。 收发进程的同步-当缓冲区中无消息存在时，接收进程不能接收到任何消息。思考：为什么不考虑缓冲区消息满的问题？至于发送进程是否可以发送消息，则由发送进程是否申请到缓冲区决定。设公用信号量mutex 为控制对缓冲区访问的互斥信号量，其初值为1 。设SM为接收进程的私用信号量，表示等待接收的消息个数，其初值为0 。设发送进程调用过程send(m)将消息m 送往缓冲区，接收进程调用过程Receive(m)将消息m从缓冲区读往自己的数据区，则Send(m)和Receive(n)可分别描述为：Send（m）:begin向系统申请一个消息缓冲区（mutex）将发送区消息m送入新申请的消息缓冲区把消息缓冲区挂入接收进程的消息队列（mutex）（SM）endReceive（n）:begin（SM）（mutex）摘下消息队列中的消息n 将消息n从缓冲区复制到接收区释放缓冲区（mutex）end一般来说，尽管系统中可利用的缓冲区总数是已知的，但由于消息队列是按接收进程排列，因而，在同一时间内，系统中存在着多个消息队列；且这些队列的长度是不固定的。因此，发送进程无法在Send过程用操作判断信号量SM（2）邮箱通信邮箱通信就是由发送进程申请建立一与接收进程链接的邮箱。发送进程把消息送往邮箱，接收进程从邮箱中取出消息，从而完成进程间信息交换。设置邮箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制。一个邮箱可考虑成发送进程与接收进程之间的大小固定的私有数据结构，它不像缓冲区那样被系统内所有进程共享。邮箱由邮箱头和邮箱体组成。其中邮箱头描述邮箱名称、邮箱大小、邮箱方向以及拥有该邮箱的进程名等。邮箱体主要用来存放消息（图3.18）。对于只有一发送进程和一接收进程使用的邮箱，则进程间通信应满足如下条件： 发送进程发送消息时，邮箱中至少要有一个空格能存放该消息。 接收进程接收消息时，邮箱中至少要有一个消息存在。设发送进程调用过程 deposit（m）将消息发送到邮箱，接收进程调用过程remove（m）将消息m 从邮箱中取出。另外，为了记录邮箱中空格个数和消息个数，信号量fromnum 为发送进程的私用信号量，信号量mesnum为接收进程的私用信号量。fromnum 的初值为信箱的空格数 n，mesnum 的初值为 0。则 deposit（m）和remove（m）可描述如下：deposit（m）:begin local x（fromnum）选择空格x将消息m放入空格x中置格x的标志为满（mesnum）endremove（m）:begin local x（mesnum）选择满格x把满格x中的消息取出放m中置格x标志为空（fromnum）end显然，调用过程deposit（m）的进程与调用过程remove（m）的进程之间存在着同步制约关系而不是互斥制约关系。另外，在许多时侯，存在着多个发送进程和多个接收进程共享邮箱的情况。这时需要对过程deposit（m）和remove（m）作相应的改动（思考：如何改？）。（3）管道pipe进程通信的实用例子之一是UNIX系统的管道通信。UNIX系统从System开始，提供有名管道和无名管道两种数据通信方式，这里介绍无名管道。 管道是在内存中开辟的一块缓冲区，操作系统将一个命令的输出，通过该缓冲区作为另一个命令的输入。一般操作系统既向用户提供作业级接口的管道操作符，如|符号；也向用户提供程序级的管道操作系统调用。 例如，希望在输出设备上分屏显示文件的内容，可以使用：type 文件名|more无名管道为建立管道的进程及其子孙提供一条以比特流方式传送消息的通信管道。该管道在逻辑上被看作管道文件，在物理上则由文件系统的高速缓冲区构成，而很少启动外设。发送进程利用文件系统的系统调用write（fd1,buf,size），把buf中的长度为size字符的消息送入管道入口fd1，接收进程则使用系统调用read（fd0,buf,size）从管道出口fd0 读出size字符的消息置入buf 中。这里，管道按FIFO（先进先出）方式传送消息，且只能单向传送消息（图3.21）。12理解死锁的概念所谓死锁，是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。下面以生产者/消费者问题为例来进一步看看死锁的概念。设生产者进程已获得对缓冲区队列的操作权，生产者进程进一步要求对缓冲区内的某一空缓冲区进行置入消息操作。然而，设此时缓冲队列内所有缓冲区都是满的，即只有消费者进程才能对它们进行取消息操作。因此，生产者进程进入等待状态。反过来，消费者进程拥有对各缓冲区操作的操作权，为了对各缓冲区进行操作，它又要申请对缓冲队列操作的操作权。由于对缓冲队列的操作权被生产者进程掌握，且生产者进程不会自动释放它，从而消费者进程也只能进入等待状态而陷入死锁。思考：写出以上会死锁的算法。13掌握死锁的必要条件死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。但是，可以采用适当的资源分配算法，以达到消除死锁的目的。为此，先看看产生死锁的必要条件。产生死锁的必要条件(1) 互斥条件。并发进程所要求和占有的资源是不能同时被两个以上进程使用或操作的，进程对它所需要的资源进行排他性控制。(2) 不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放。(3) 部分分配。进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。(4) 环路条件。存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。显然，只要使上述4个必要条件中的某一个不满足，则死锁就可以排除。14掌握防止死锁的方法及应用，了解理解资源分配图解决死锁的方法一般可分为预防、避免、检测与恢复等三种。预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。避免是指系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生。死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。在实际操作系统中大都使用检测与恢复法排除死锁。.死锁预防第一种方法是打破资源的互斥条件；即阻止互斥，例如允许进程同时访问某些资源等。破坏第一个条件，使资源可以同时访问而不是互斥使用，这是个简单的方法，但在进程并发执行的情况下往往有许多资源是不能同时访问的（如写操作），所以这种方法不能解决访问那些不允许被同时访问的资源时所带来的死锁问题。只能对可共享的资源（如只读文件或记录等）这样做。不适合非共享资源，例如、为写而打开的文件，打印机等。第二种方法是打破不可剥夺条件，即允许剥夺；具体是： 做法1：若拥有某种资源的进程在申请其他资源时遭到拒绝，则它必须释放其占用的资源，以后若有必要可再次申请上述资源。做法2：当一进程申请的资源正被其他进程占用时，可通过操作系统抢占该资源，此方法在两个进程优先级相同时，不能防止死锁。 优点：对状态容易保留和恢复的资源较为方便。 缺点：实现困难，恢复现场代价高；导致过多的不必要抢占；易导致循环重启。第三种方法则是打破资源的部分分配这个死锁产生的必要条件。即预先分配各并发进程所需要的全部资源。如某个进程的资源得不到满足时，则安排一定的等待次序让其他进程释放资源。但是，这种方法也有如下问题：（1）在许多情况下，一个进程在执行之前不可能提出它所需要的全部资源。（2）无论所需资源何时用到，一个进程只有在所有要求资源都得到满足之后才开始执行。（3）对于那些不经常使用的资源，进程在生存过程期间一直占用它们是一种极大的浪费。（4）降低了进程的并发性。这种方法必须保证：当一个进程申请一个资源时，它不能占有其它资源。因此，一般采用资源的静态预分配策略，进程一次申请所有的资源。优点：简单安全，易于实施；在进程的活动较单一时性能好；无须抢占。缺点：资源利用率低；启动进程慢，效率低；有“饥饿”现象存在。第四种死锁预防的方法是打破死锁的环路条件。即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。如有m种资源，则列出R1R2Rm。若进程Pi保持了资源Ri，则它只能申请比Ri级别更高的资源Rj（Ri Rj ）。释放资源时必须是Rj先于Ri被释放，从而避免环路的产生。优点： 资源的申请与分配逐步进行，比预分配策略的资源利用率高； 易实现编译期间的检查； 无须执行时间，在系统设计阶段问题就已解决。缺点： 严格限制资源的顺序性，不允许增加资源请求； 在使用资源的顺序与系统规定不一致时，资源利用率降低； 不能抢占。 15、 熟练掌握哲学家进餐问题的几种解法。（基本解法，可能死锁；改进算法）16、 一种简单的解决方法是每支筷子都用一个信号量来表示。 信号量是一个整型变量，其初值为1。 一个哲学家要通过在信号量上执行P操作才能拿到筷子。并规定每个哲学家先拿左手边的筷子后拿右手边的筷子。 一个哲学家要通过在适当的信号量上执行V操作才释放相应的筷子。 用信号量方案解决。Semaphore S1，S2，S3，S4，S5 或Semaphore chopstick0.4思考：如何用P、V操作实现？ 哲学家用餐问题是一个死锁和饥饿的典型问题，也是一大类并发控制所面临的问题。 方法1：每个哲学家先拿其左边的筷子然后再拿右边的筷子。哲学家用完餐后再将筷子放回原来的位置。这种解决方法可能导致死锁。 方法2：为避免死锁，可以只允许不超过4个哲学家同时用餐。这样就至少有一个哲学家可以得到两根筷子。这个方法可避免死锁和饥饿，但并不公平。 方法3：效果与方法二相同，但有较好的公平性。即对资源进行编号，采用按序分配的原则。思考：方法2、3如何实现？方法4：奇数号哲学家拿他左边的筷子，然后再拿他右边的筷子；而偶数哲学家则相反。15*熟练掌握死锁避免的方法及应用（安全状态，银行家算法及安全测试子算法）死锁避免死锁避免可被称为动态预防，因为系统采用动态分配资源，在分配过程中预测出死锁发生的可能性并采取措施加以避免。死锁避免方法并不是严格限制产生死锁必要条件的存在，只是防止系统进入不安全状态，从而避免死锁的发生。死锁避免算法就是避免系统进入不安全状态的算法。银行家（Banker）算法是最著名的死锁避免算法。 16理解线程的概念、基本状态、使用场合及与进程的区别（1）一个进程内的基本调度单位称为线程或称为轻权进程（Light weight process），这个调度单位既可以由操作系统内核控制，也可以由用户程序控制。（2）一个新派生出来的线程具有相应的数据结构指针和变量，这些指针和变量作为寄存器上下文放在相应的寄存器和堆栈中。新派生线程被放入就绪队列。阻塞（Block）：如果一个线程在执行过程中需要等待某个事件发生，则被阻塞。阻塞时，寄存器上下文、程序计数器以及堆栈指针都会得到保存。激活（unblock）：如果阻塞线程的事件发生，则该线程被激活并进入就绪队列。调度（schedule）：选择一个就绪线程进入执行状态。结束（Finish）：如果一个线程执行结束，它的寄存器上下文以及堆栈内容等将被释放。线程的状态和操作关系如图3.30。图3.30 线程的状态与操作需要注意的一点是，在某些情况下，某个线程被阻塞也可能导致该线程所属的进程被阻塞。（3）最适合使用线程的系统是多处理机系统。服务器中的文件管理或通信控制。前后台处理。异步处理。（4）服务器应该建立独立的线程以便服务新的客户请求。进程是资源分配的基本单位。所有与该进程有关的资源，例如打印机，输入缓冲队列等，都被记录在进程控制块PCB中。以表示该进程拥有这些资源或正在使用它们。进程拥有一个完整的虚拟地址空间（后述）。与进程相对应，线程与资源分配无关，它属于某一个进程，并与进程内的其他线程一起共享进程的资源。再者，当进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地址空间。线程只由相关堆栈（系统栈或用户栈）寄存器和线程控制表TCB组成。寄存器可被用来存储线程内的局部变量，但不能存储其他线程的相关变量。第4章 1理解处理机调度的四个层次（1）作业调度：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，还负责回收系统资源。（2）交换调度：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。交换调度主要涉及到内存管理与扩充。（3）进程调度：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。（4）线程调度。2了解作业与进程的关系作业可被看作是用户向计算机提交任务的任务实体，例如一次计算、一个控制过程等。反过来，进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。 一个作业总是由一个以上的多个进程组成的。首先，系统必须为一个作业创建一个根进程。然后，在执行作业控制语句时，根据任务要求，系统或根进程为其创建相应的子进程，然后，为各子进程分配资源和调度各子进程执行以完成作业要求的任务。3了解作业的组织与调度（1）记录系统中各作业的状况。（2）从后备队列中挑选出一部分作业投入执行。（3）为被选中作业做好执行前的准备工作。（4）在作业执行结束时做善后处理工作。一般来说，调度目标主要是以下4点：（1）对所有作业应该是公平合理的；（2）应使设备有高的利用率；（3）每天执行尽可能多的作业；（4）有快的响应时间。4*熟练掌握常用的调度算法，应用及评价指标（平均周转时间，带权周转时间）算法：FCFS，SJF，HRN，RR，优先级带权周转时间是作业周转时间与作业执行时间的比响应比R定义如下：R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。先来先服务（FCFS），轮转法（round robin），优先级法（适用于作业或进程），最短作业优先法（shortest job first），最高响应比优先法（highest responseratio next）（适用于作业）第5章 1掌握虚拟存储器的概念，实现的理论根据（程序运行的局部性原理）所谓的虚拟存储器就是操作系统对内存与辅存进行统一管理，当程序运行时并不是将所有的程序与数据装入内存，而是先装入一部分，当用到不在内存的程序或数据时再从辅存中调入内存；如果内存中没有足够的空间，则将内存中的部分程序或数据调出内存（送到辅存）。2*熟练掌握地址的映射的方法（静态、动态）（1） 静态地址重定位（static address relocation）是在虚拟空间程序执行之前由装配程序完成所有地址映射工作，执行期间不再进行地址映射。静态重定位的优点是不需要硬件支持。但是，使用静态重定位方法进行地址变换无法实现虚拟存储器，静态重定位方法将程序一旦装入内存之后就不能再移动，并且必须在程序执行之前将有关部分全部装入。（2） 动态地址重定位（dynamic address relocation）是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。动态重定位的主要优点有:（1）可以对内存进行非连续分配。显然，对于同一进程的各分散程序段，只要把各程序段在内存中的首地址统一存放在不同的BR中，则可以由地址变换机构变换得到正确的内存地址。（2）动态重定位提供了实现虚拟存储器的基础。因为动态重定位不要求在作业执行前为所有程序分配内存，也就是说，可以部分地、动态地分配内存。从而，可以在动态重定位的基础上，在执行期间采用请求方式为那些不在内存中的程序段分配内存，以达到内存扩充的目的。（3）有利于程序段的共享。3理解内存的共享与保护常用的内存信息保护方法有硬件法、软件法和软硬件结合三种。上下界保护法是一种常用的硬件保护法。上下界存储保护技术要求为每个进程设置一对上下界寄存器。上下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中,在对内存进行访问操作时首先进行访址合法性检查,即检查经过重定位后的内存地址是否在上、下界寄存器所规定的范围之内。若在规定的范围之内，则访问是合法的；否则是非法的，并产生访址越界中断。上下界保护法的保护原理如图5.4。 另外，保护键法也是一种常用的存储保护法。保护键法为每一个被保护存储块分配一个单独的保护键。在程序状态字中则设置相应的保护键开关字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键匹配。保护键可设置成对读写同时保护的或只对读，写进行单项保护的。例如，图5.5中的保护键0，就是对2K到4K的存储区进行读写同时保护的，而保护键2则只对4K到6K的存储区进行写保护。如果开关字与保护键匹配或存储块未受到保护，则访问该存储块是允许的，否则将产生访问出错中断。另外一种常用的内存保护方式是：界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。UNIX系统就是采用的这种内存保护方式。4掌握分区管理的概念、分配与回收算法、回收区的合并、内存拼接、内存利用率等概念：分区管理是把内存划分成若干个大小不等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享。分区管理是满足多道程序设计的一种最简单的存储管理方法。分配与回收算法：（1）固定分区时的分配与回收 固定分区法时的内存分配与回收较为简单，当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。 固定分区的回收更加简单。当进程执行完毕，不再需要内存资源时，管理程序将对应的分区状态置为未使用即可。（2）动态分区时的分配与回收动态分区时的分配与回收主要解决三个问题: （1）对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。（2）分配空闲区之后，更新可用表或自由链。（3）进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。 动态分区时的分配方法从可用表或自由链中寻找空闲区的常用方法有三种。它们是最先适应法（first fit algorithm），最佳适应法（best fit algorithm）和最坏适应法（worst fit algoriathm）。这三种方法要求可用表或自由链按不同的方式排列。最先适应法要求可用表或自由链按起始地址递增的次序排列。最佳适应算法要求从小到大的次序组成空闲区可用表或自由链。最坏适应算法要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。 设内存中有两个空闲区。F1 为 110KB，F2 为 60KB（F1 的地址低于 F2）；现依次有 A、B、C 三个作业请求装入运行，它们的内存需求分别是 20K、80K和50K。试描述三种分配算法的效果。 若采用 WF 算法：作业 A 可获得 F1 中的 20K，作业 B 可获得 F1 中的 80K，作业 C 获得 F2 中的50K，三个作业都得到满足。 若采用 BF 算法： 作业 A 获得 F2 中的 20K，作业 B 获得 F1 中的 80K，而作业 C 的需求无法满足。 若采用 FF 算法： 由于 F1 的地址低于 F2 的地址，所以、采用 FF 算法的结果于 WF 算法一样首先，从分配速度上看，最先适应算法具有最佳性能。尽管最佳适应算法或最坏适应算法看上去能很快地找到一个最适合的或最大的空闲区。再者，从回收过程来看，最先适应算法也是最佳的。因为使用最先适应算法回收某一空闲区时，无论被释放区是否与空闲区相邻，都不用改变该区在可用表或自由链中的位置，只需修改其大小或起始地址。最先适应算法的另一个优点就是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。 最佳适应法找到的空闲区是“最佳”的（即能满足用户请求的最小空闲区）。不过，在某些情况下并不一定提高内存的利用率。最坏适应算法正是基于不留下碎片空闲区这一出发点的。它选择最大的空闲区来满足用户要求，以期分配后的剩余部分仍能进行再分配。总之，上述三种算法各有特长，针对不同的请求队列，效率和功能是不一样的。回收区的合并：动态分区时的回收与合并（书上的概念存在问题） 当用户作业或进程执行结束时，存储管理程序要收回已使用完毕的空闲区，并将其插入空闲区可用表或自由链。这里，在将回收的空闲区插入可用表或自由链时，和分配空闲区时一样，也要碰到剩余空闲区合并问题。 解决这个问题的办法之一就是在内存回收时或在内存分配时进行空闲区合并，以把连续相邻的空闲区集中起来。 在将一个新可用区插入可用表或队列时，该空闲区和上下相邻区的关系是下述4种关系之一: a）该空闲区的上下两相邻分区都是空闲区；b）该空闲区的上相邻区是空闲区；c）该空闲区的下相邻区是空闲区；d）两相邻区都不是空闲区。如图5.12所示。 静态地址重定位和动态地址重定位技术，都可用来完成分区式内存管理的地址变换。显然，动态分区时分区大小不固定，而空闲区的拼接会移动内存中的程序和数据，因此，使用静态地址重定位的方法来完成动态分区时的地址变换是不妥当的。5了解覆盖与交换技术的用途把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。这使得用户看来，好像内存扩大了，从而达到了内存扩充的目的。交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构。6理解段、页式存储管理的基本原理 分区式管理方式尽管实现方式较为简单，但存在着严重的碎片问题使得内存的利用率不高。再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放，进程的大小仍受分区大小或内存可用空间的限制。而且，分区式管理也不利于程序段和数据的共享。页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放于外存待执行时调入，以提高内存利用率而提出来的。页式管理的基本原理如下：首先，各进程的虚拟空间被划分成若干个长度相等的页（page）。页长的划分和内存外存之间数据传输速度以及内存大小等有关。一般每个页长大约为1-4K，经过页划分之后，进程的虚地址变为页号p与页内地址w所组成。例如，一个页长为1 K，拥有1024页的虚拟空间地址结构如图5.14。思考：进程虚地址转换成P、W的公式是什么？除了把进程