1、OS操作系统复习第一章1理解操作系统的概念操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合它们管理和控制计算机系统中软硬件资源，合理地组织计算机工作流程，以便有效地利用这些资源为用户提供一个足够的功能、使用方便、可扩展、安全和可管理的工作环境，从而在计算机与用户之间起到接口作用。 2掌握三种基本类型及特点（1）批处理操作系统的特点是：脱机使用，多道和成批处理（2）分时操作系统特点：交互性，多用户同时性，独立性（3）实时系统的特点：提供即时响应和高可靠性3理解操作系统的功能4*熟练掌握算法描述的规则 (参第三章的实例)变量定义：a：int变量赋值：a:=2开始结束：beginen
2、d循环：Repeatforever，repeatuntil，whiledood，ifthenelsefi第2章1理解操作系统与用户两类接口。操作系统为用户提供两个接口界面。一个是系统为用户提供的各种命令接口界面。用户利用这些操作命令来组织和控制作业的执行或管理计算机系统。另一个接口是系统调用。编程人员使用系统调用来请求操作系统提供服务。操作系统的命令控制界面就是用来组织和控制作业运行的。 2理解作业级接口 （1）图形用户接口图形接口:图形用户接口采用了图形化的操作界面，用非常容易识别的各种图标来将系统各项功能、各种应用程序和文件，直观、逼真地表示出来。用户可通过鼠标、菜单和对话框来完成对应程序
3、和文件的操作。图形用户接口元素包括窗口、图标、菜单和对话框，图形用户接口元素的基本操作包括菜单操作、窗口操作和对话框操作等。 （2）命令行接口命令接口:为了便于用户直接或间接控制自己的作业，操作系统向用户提供了命令接口。命令接口是用户利用操作系统命令组织和控制作业的执行或管理计算机系统。命令是在命令输入界面上输入，由系统在后台执行，并将结果反映到前台界面或者特定的文件内。命令接口可以进一步分为联机用户接口和脱机用户接口。3掌握常用操作系统的命令、命令组合（课堂介绍的）Ls列出当前目录下的文件和目录（Linux） cd设置当前目录（Linux and Windows）Dir列出当前目录下的文件和
4、目录（Windows） type显示文件内容（windows）Cat 显示文件内容（Linux） ipconfig ip配置 path显示路径设置Echo off关闭回显。 Mem查看内存使用情况 重定向符号“”xcopy 拷贝目录与文件 ren改变文件名4能阅读理解简单的batch和shell脚本程序 (课件 5，28，作业)例如：c:copy try.bat d: & del *.bat c:copy try.bat d: | del *.bat5了解系统调用的概念及基本用法系统调用是操作系统提供给编程人员的唯一接口。大致分为以下六类：（1）设备管理。该类系统调用被用来请求和释放有关设备以
5、及启动设备操作等（2）文件管理。包括对文件的读写创建删除等（3）进程控制。进程是一个在功能上独立的程序的一次执行过程。进程控制的有关调用包括（4）进程创建，执行，撤销，执行等待和执行优先级控制等（5）存储管理。包括调查作业占据内存区的大小，获取作业占据内存去的始址等。（6）进程通信。该类系统调用被用在进程之间传递信息或信号。（7）线程管理。包括线程创建调度执行撤销等。6了解系统调用的实现原理把用户进程的请求传达给内核，待内核把请求处理完毕后再将处理结果送回给用户空间。第3章 1掌握进程的概念、组成、并发、并行与执行的异步性。(课件6) 了解并发执行条件（Beistein条件）(1)概念：进程是
6、一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。(2)组成：进程的静态描述由三部分组成：进程控制块PCB，有关程序段和该程序段对其进行操作的数据结构集。(3)并发、并行：并发和并行是即相似又有区别的两个概念，并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。倘若在计算机系统中有多个处理机，则这些可以并发执行的程序便可被分配到多个处理机上，实现并行执行，即利用每个处理机来处理一个
7、可并发执行的程序，这样，多个程序便可以同时执行。(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)
8、W(S2)=， W(S1) R(S2)=， W(S1) W(S2)= 同时成立，则语句S1和S2是可以并发执行的。 有以下语句P1-P4，其中a、b、c、d、x、y、z为变量并有初值；试写出它们的读集与写集，判断哪些语句可以并发执行？画出它们的前趋图。 P1: a=x+y P2: b=z+1 P3: c=a+b P4: d=c-2(6)程序执行的异步性经典例子：例1：设余票单元为 count，xi为工作变量单元；有 N 个售票窗口进行售票 Process Pi(i=1,2,n) begin Begin count:integer; Var Xi:integer; Cobegin 按旅客要求找到
9、 count; P1; Xi:=count; P2; If Xi=1 then begin Pn; Xi:=Xi-1; Coend count:=Xi; end. 输出一张票; end else 输出“票已售完”; End;例2：2掌握PCB的作用与地位（1）作用：系统根据PCB感知进程的存在和通过PCB中所包含的各项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。（2）地位：进程控制块是用来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。PCB集中反映一个进程的动态特征。3了解进程上下文的概念，
10、进程切换与模式切换（1）操作系统中把进程物理实体（程序、数据和PCB）和支持进程运行的环境（寄存器与堆栈）合称为进程上下文，实际上是进程执行过程中顺序关联的静态描述。它与进程的切换和处理机状态转换（用户态 系统态，也称为模式切换）有关。所谓上文是指已执行过的进程指令和数据在相关寄存器与堆栈中的内容；正文是指正在执行的进程指令和数据在相关寄存器与堆栈中的内容；下文是指待执行的进程指令和数据在相关寄存器与堆栈中的内容。（2）（3）模式切换并不同与进程切换，它不一定引起进程状态的改变，在大多数操作系统中也不一定引起进程的切换，因此，它常常只需要保存一些寄存器中的内容、根据中断号设置PC的内容、切换到
11、系统态执行中断处理程序。当系统调用完成后再次通过模式切换来继续执行原来被中断的用户进程。4*熟练掌握进程的状态及其转换，转换原因思考：1、为什么没有从就绪态到等待态的转换？ 2、为什么没有从等待态到执行态的转换？5理解进程控制的实现所谓进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。一般地，把系统态下执行的某些具有特定功能的程序段称为原语。原语可分为两类：一类是机器指令级的，其特点是执行期间不允许中断，正如在物理学中的原子一样，在操作系统中，它是一个不可分割的基本单位。另一类是功能级的，其特点是作
12、为原语的程序段不允许并发执行。这两类原语都在系统态下执行，且都是为了完成某个系统管理所需要的功能和被高层软件所调用。用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等。6掌握进程间的制约关系及所表现的互斥与同步概念，要能判断进程间的同步和互斥（1）临界区：一次只允许一个进程进行访问的资源。（2）间接制约：由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约，简称间接制约。（3）互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资
13、源的并发进程同时进入临界区称为互斥。（4）一组并发进程互斥执行时必须满足如下准则：不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区。（并发进程异步执行）并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区。（临界区空闲让进）并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。（并发进程互斥执行）并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区。（并发进程有限等待）（5）同步：存在有因为并发进程互相共享对方的私有资源所引起的直接制约。直接制约
14、将使得各并发进程同步执行。7理解锁机制解决互斥的方法设临界区的类名为。为了保证每一次临界区中只能有一个程序段被执行，又设锁定位 key 。key表示该锁定位属于类名为的临界区。加锁后的临界区程序描述如下： lock(key ) 临 界 区 unlock(key ) 设key =1时表示类名为的临界区可用，key =0时表示类名为的临界区不可用。则，unlock(key )只用一条语句即可实现。即： key 1 不过，由于lock(key )必须满足key =0时，不允许任何进程进入临界区，而key =1时仅允许一个进程进入临界区的准则，因而实现起来较为困难。8掌握信号量（私有、公有）和P、V原
15、语的概念及用法（直接制约） （间接制约）私有信号量 公有信号量一般来说，也可以把各进程之间发送的消息作为信号量看待。与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为私用信号量（Private Semaphvre）。一个进程Pi的私用信号量Semi是从制约进程发送来的进程Pi的执行条件所需要的消息。与私用信号量相对应，称互斥时使用的信号量为公用信号量。信号量的物理意义：大于零：表示可用资源数目。小于零：绝对值表示请求资源而被阻塞的进程数p原语为申请资源v原语为释放资源pv操作必须成对出现。关于，原语的实现，有许多方法。这里介绍一种使用加锁
16、法的软件实现方法，实现过程描述如下： （sem）： begin 封锁中断； lock（lockbit） valsem=valsem-1 if valsem=1 then begin Pn; Xi:=Xi-1; coend count:=Xi; end. V(s); 输出一张票; End Else Begin V(s); 输出“票已售完”; End; End; 两个火车站 A、B 之间是单轨连接，现有许多列车同时到达 A 站，经 A 站到 B 站，列车驶出 B 站后又可分路行驶。为了保证行车安全，请用信号量机制设计一个自动调度算法。 Program mutualexclusion; begin
17、( * 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)。且数据的发送和接收过程满足
18、如下条件：（1）在PA至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度），即缓冲区空时PB不能取数；（2）PA往缓冲队列发送数据时，至少有一个缓冲区是空的，即缓冲区满时PA不能送数；（3）由PA发送的数据块在缓冲队列中按先进先出（FIFO）方式排列。描述发送过程deposit(data)和接收过程remove(data)。解：由题意可知，进程PA调用的过程deposit(data)和进程PB调用的过程remove(data)必须同步执行，因为过程 deposit(data)的执行结果是过程remove(data)的执行条件，而当缓冲队列全部装满数据时，r
19、emove(data)的执行结果又是deposit(data)的执行条件，满足同步定义。从而，按以下三步描述过程deposit(data)和remove(data)：（1）设Bufempty为进程PA的私用信号量，Buffull 为进程PB的私用信号量；（2）令Bufempty的初始值为n（n 为缓冲队列的缓冲区个数），Buffull 的初始值为0；（3）描述：PA: deposit(data): begin local x P(Bufempty)； 按FIFO方式选择一个空缓冲区Buf(x)； Buf(x) data Buf(x)置满标记 （Buffull） endPB: remove(da
20、ta): Begin local x （Buffull）； 按FIFO方式选择一个装满数据的缓冲区Buf(x) data Buf(x) Buf(x)置空标记 （Bufempty） end这里，局部变量x用来指明缓冲区的区号，给Buf(x)置标志位是为了便于区别和搜索空缓冲区及非空缓冲区。（思考：在该题中需要考虑互斥吗？为什么？如果每次只允许一个进程对缓冲队列进行操作时怎么办？）10*熟练掌握应用P、V原语解决同步问题（生产者与消费者、读者与写者（读者优先）（多看实例） 假如是一个生产者、一个消费者，且缓冲区有 N 个单元。 当缓冲区没有放满 N 个数据时，生产者进程调用 P（Se）都不会成为等
21、待状态，可以把数据送入缓冲区。但当缓冲区中已有 N 个数据时，生产者进程想要再送数将被拒绝。由于每送入一个数后要调用 V（Sf），所以此时 Sf 的值表示缓冲区中可取的数据数，只要 Sf 0，消费者进程在调用 P（Sf）后总可以从缓冲区取数。每取走一个数据就调用 V（Se），因此增加了一个存放数据的位置。可以用指针 in 和 out 分别指示生产者进程向缓冲区送数和消费者进程从缓冲区取数的相对位置；指针的初始值为“0”。 这种情况下生产者与消费者进程的同步算法为：读者/写者问题：读者优先信号量 wsem 用来实现互斥，只要有 writer在访问共享数据区，其他 writers 或 reader
22、s 就不能访问数据区。reader 进程同样利用 wsem 实现互斥。为了适用于多个 reader，当没有 reader 读时，第一个进行读的 reader 要测试 wsem，当已经有 reader 在读时，随后的 reader 无须等待就可读取数据区。一旦有一个 reader 访问数据区，只要还有一个 reader 在进行读操作，reader 就可以保持对数据区的控制，这就容易导致 writers 饥饿。 设A、B两点之间是一段东西向的单行车道，现在要设计一个AB路段自动管理系统，规则如下：当AB间有车辆在行驶时，同方向的车辆可以驶入，另一方向的车辆必须在AB段外等待；当AB段之间无车辆行驶
23、时，任一方向到达的车辆都可驶入，但不能从两个方向同时驶入；当某方向在AB段行驶的车辆驶出AB段且暂无车辆进入AB段时，应该让另一方向等待的车辆进入AB段行驶。试用信号量和P、V操作管理AB段车辆的行驶。 信号量设置如下：Int CA：=CB：=0；Var mutex,ma,mb：semaphore；mutex：=ma：=mb：=1； 算法描述如下： cobegin P向西； P向东； coend11理解进程的通信方式（消息缓冲、邮箱、管道）（1）消息缓冲机制 发送进程和接收进程采用消息缓冲机制进行数据传送时，发送进程在发送消息前，先在自己的内存空间设置一个发送区，把欲发送的消息填入其中，然后再
24、用发送过程将其发送出去。接收进程则在接收消息之前，在自己的内存空间内设置相应的接收区，然后用接收过程接收消息。由于消息缓冲机制中所使用的缓冲区为公用缓冲区，使用消息缓冲机制传送数据时，两通信进程必须满足如下条件： 消息队列的互斥操作-在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对该缓冲区消息队列的访问。否则，将引起消息队列的混乱。同理，当接收进程正从消息队列中取消息缓冲时，也应禁止其他进程对该队列的访问。 收发进程的同步-当缓冲区中无消息存在时，接收进程不能接收到任何消息。思考：为什么不考虑缓冲区消息满的问题？ 至于发送进程是否可以发送消息，则由发送进程是否申请到缓冲区决
25、定。 设公用信号量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从缓冲区
26、复制到接收区 释放缓冲区 （mutex） end一般来说，尽管系统中可利用的缓冲区总数是已知的，但由于消息队列是按接收进程排列，因而，在同一时间内，系统中存在着多个消息队列；且这些队列的长度是不固定的。因此，发送进程无法在Send过程用操作判断信号量SM（2）邮箱通信 邮箱通信就是由发送进程申请建立一与接收进程链接的邮箱。发送进程把消息送往邮箱，接收进程从邮箱中取出消息，从而完成进程间信息交换。设置邮箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制。一个邮箱可考虑成发送进程与接收进程之间的大小固定的私有数据结构，它不像缓冲区那样被系统内所有进程共享。邮箱由邮箱头和邮箱体组成。其中邮箱
27、头描述邮箱名称、邮箱大小、邮箱方向以及拥有该邮箱的进程名等。邮箱体主要用来存放消息（图3.18）。对于只有一发送进程和一接收进程使用的邮箱，则进程间通信应满足如下条件： 发送进程发送消息时，邮箱中至少要有一个空格能存放该消息。 接收进程接收消息时，邮箱中至少要有一个消息存在。设发送进程调用过程 deposit（m）将消息发送到邮箱，接收进程调用过程remove（m）将消息m 从邮箱中取出。另外，为了记录邮箱中空格个数和消息个数，信号量fromnum 为发送进程的私用信号量，信号量mesnum为接收进程的私用信号量。fromnum 的初值为信箱的空格数 n，mesnum 的初值为 0。则 dep
28、osit（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开始，提供有名管道和无名管道两种数据通信方式，这里介绍无名管道。 管道是在内存中开辟的一块缓冲区，操作系统将一个命令的输出，通过该缓冲区作为另一个命令的输入。一般操作系统既向用户提供作业级接口的管道操作符，如|符
