操作系统复习.doc

第一章操作系统定义： 操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。操作系统功能： (1)存储管理功能：内存分配（策略）、地址映射（转换）、内存保护（不干扰不越界）、内存扩充（逻辑扩充：虚拟存储器与置换）。(2)处理机管理功能：作业和进程调度（创建进程，算法）、进程控制（创建、撤销、唤醒、挂起等）和进程通信（依赖和制约：同步和互斥）。(3)设备管理功能：缓冲区管理（速度匹配），设备分配（请求、策略），设备驱动（通道）和设备无关性（逻辑设备名、物理设备名）。(4)文件管理功能：文件存储空间的管理（分配与回收），文件操作的一般管理（创建、删除、打开、关闭），目录管理，文件的读写管理和存取控制（防止越权与破坏）。(5)用户接口：命令界面:这是指由OS提供了一组联机命令(语言)， 用户可通过键盘输入有关命令，来直接操纵计算机系统。程序界面：OS提供了一组系统调用，用户可在自己的应用程序中通过相应的系统调用，来操纵计算机。图形界面：用户通过屏幕上的窗口和图标来操纵计算机系统和运行自己的程序。并发：是指两个或多个活动在同一给定的时间间隔中进行。宏观概念。如CPU共享。共享：是指计算机系统中的资源被多个进程所共用。如CPU、硬盘、内存、数据等。 互斥地共享：某进程申请资源、若空闲、分配、运行，下一个进程只能等待，直到前一进程释放资源。 宏观上同时访问、微观上并发执行的共享：如硬盘上文件的访问。不确定性：是指系统中各种事件发生顺序的不可预测性。多道程序设计：基本思想是在内存中同时存放多道程序，在管理程序的控制下交替地执行。这些作业共享CPU和系统中的其他资源。分时系统：操作系统多个用户终端，分时共享主机资源。时间片、交互性。实时系统：系统及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。实时性、高可靠性。第二章进程：进程最根本的属性是动态性和并发性，指程序在并发环境中的执行过程。进程队列的连接方式：线性队列，链接，索引。进程和线程的关系： 一个进程可以有多个线程，但至少要有一个线程；而一个线程只能在一个进程的地址空间内活动。 资源分配给进程，同一进程的所有线程共享该进程的所有资源。 处理机分配给线程，即真正在处理机上运行的是线程。 线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。进程的同步：同步进程通过共享资源来协调活动，在执行时间的次序上有一定约束。在协调动作的情况下，多个进程可以共同完成一项任务。虽然彼此不直接知道对方的名字，但知道对方的存在和作用。进程的互斥：逻辑上这两个进程本来完全独立，不知对方的存在，毫无关系，只是由于竞争同一个物理资源而相互制约。信号量：用于解决进程同步、互斥问题的通用工具。PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：将信号量S的值减1，即S=S-1； 如果S0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：将信号量S的值加1，即S=S+1； 如果S0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。 一般来说，信号量S0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。【例1】生产者-消费者问题在多道程序环境下，进程同步是一个十分重要又令人感兴趣的问题，而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题，深入地分析和透彻地理解这个例子，对于全面解决操作系统内的同步、互斥问题将有很大帮助。（1）一个生产者，一个消费者，公用一个缓冲区。定义两个同步信号量：empty表示缓冲区是否为空，初值为1。 full表示缓冲区中是否为满，初值为0。生产者进程while(TRUE)生产一个产品; P(empty); 产品送往Buffer; V(full);消费者进程while(True)P(full); 从Buffer取出一个产品; V(empty); 消费该产品; （2）一个生产者，一个消费者，公用n个环形缓冲区。定义两个同步信号量：empty表示缓冲区是否为空，初值为n。full表示缓冲区中是否为满，初值为0。 设缓冲区的编号为1n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指，指向下一个可用的缓冲区。生产者进程while(TRUE) 生产一个产品; P(empty); 产品送往buffer（in）； in=(in+1)mod n； V(full);消费者进程while(TRUE) P(full); 从buffer（out）中取出产品； out=(out+1)mod n； V(empty); 消费该产品; （3）一组生产者，一组消费者，公用n个环形缓冲区 在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。定义四个信号量：empty表示缓冲区是否为空，初值为n。full表示缓冲区中是否为满，初值为0。mutex1生产者之间的互斥信号量，初值为1。mutex2消费者之间的互斥信号量，初值为1。 设缓冲区的编号为1n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。生产者进程while(TRUE) 生产一个产品; P(empty); P(mutex1)； 产品送往buffer（in）； in=(in+1)mod n； V(mutex1); V(full);消费者进程while(TRUE) P(full) P(mutex2)； 从buffer（out）中取出产品； out=(out+1)mod n； V（mutex2）； V(empty); 消费该产品; 需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。【例2】读者写者问题：（1）读者优先。对于读者优先，应满足下列条件：如果新读者到：无读者、写者，新读者可以读；有写者等待，但有其它读者正在读，则新读者也可以读；有写者写，新读者等待。如果新写者到：无读者，新写者可以写；有读者，新写者等待；有其它写者，新写者等待。设置两个信号量：读互斥信号量rmutex和写互斥信号量wmutex。另外设立一个读计数器readcount，它是一个整型变量。rmutex：用于读者间互斥地访问读者计数的公用变量readcount（临界资源） ，初值为1。readcount初值为0。wmutex：用于保证一个写者与其他读者或写者互斥地访问共享资源，初值为1。读者Readers: while(TRUE) P(rmutex); /开始对rc共享变量进行互斥访问 readcount=readcount+1; /来了一个读进程，读进程数加1 if(readcount=1) /如是第一个读进程，判断是否有写进程在临界区 P(wmutex); /若有，读进程等待，若无，阻塞写进程 V(rmutex); /结束对rc共享变量的互斥访问 执行读操作； P(rmutex); /开始对rc共享变量的互斥访问 readcount=readcount-1; /一个读进程读完，读进程数减1 if(readcount=0)/最后一个离开临界区的读进程需要判断是否有写进程 V(wmutex); /需要进入临界区，若有，唤醒一个写进程进临界区 V(rmutex); /结束对rc共享变量的互斥访问 其他使用读取的数据 写者Writers： while(TRUE) P(wmutex); /无读进程，进入写进程；若有读进程，写进程等待 执行写操作 V(wmutex); /写进程完成；判断是否有读进程需要进入临界区， /若有，唤醒一个读进程进临界区 P(wmutex); /无读进程，进入写进程；若有读进程，写进程等待 执行写操作； V(wmutex); /写进程完成；判断是否有读进程需要进入临界区， /若有，唤醒一个读进程进临界区 读者出读者进同步机制的原则：空闲让进，忙则等待，有限等待，让权等待。第三章死锁的定义： 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。产生死锁的根本原因：资源有限，且操作不当产生死锁的四个必要条件：互斥条件，占有且等待条件，不可抢占条件，循环等待条件安全状态：在当前分配状态下，进程的安全序列P1,P2, Pn是这样组成的：若对于每一个进程Pi（1in），它需要的附加资源可被系统中当前可用资源与所有进程Pj（ ji）当前占有资源之和所满足，则P1, P2, Pn为一个安全序列。这时系统处于安全状态。安全序列：针对当前分配状态来说，系统至少能够按照某种次序分配资源(直至最大需求)，并且使它们依次成功地运行完毕，这种进程序列P1,P2,Pn就是安全序列*存在安全序列时不会死锁；但系统进入不安全状态也未必产生死锁；死锁是不安全状态的特例；银行家算法：p82三级调度各指的什么： 作业调度（高级调度）:从用户工作流程的角度。从输入的一批作业中选出若干作业，为其分配必要的内存，建立相应的用户进程和系统进程，然后将程序和数据调入内存，等待进程调度。时间上通常是分钟、小时或天。作业状态 提交状态 后备状态 执行状态 完成状态作业调度功能： 记录系统中各个作业的情况。 按照某种调度算法从后备作业队列中挑选作业。 为选中的作业分配内存和外设等资源。（通常由存储管理与外设管理程序完成） 为选中的作业建立相应的进程，并把该进程放入就绪队列中。 作业结束后进行善后处理工作。 进程挂起与对换（中级调度）:从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。(指令和数据必须在内存里才能被CPU直接访问。) 进程调度（低级调度）:指根据一定的算法，将CPU分派给就绪队列中的一个进程，获得CPU的控制权。先来先服务算法（FCFS）：非抢占式优先级算法：采用非抢占式优先算法时，最先来到的是进程P1，所以最先处理进程P1直到它结束，由于其他进程不能抢占P1的进程，所以只能等待P1完成，假设这些等待进程（注意，是等待中的进程，还未到达的进程不能参与比较，到达时间非常重要！）中P4的优先数最高，所以当P1执行完成后，先执行进程P4，以此类推。更多列题见p129（8&9）。时间片法：主要用于分时系统中的进程调度。中断：指当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。第五章逻辑地址：用户程序经编译之后的每个目标模块都以0为基地址顺序编址，其余指令中的地址都相对于首地址而编址。这种地址称为相对地址或逻辑地址；物理地址：内存中各物理存储单元的地址是从统一的基地址开始顺序编址的，这种地址称为绝对地址或物理地址。地址重定位：把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。动态地址重定位：在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序。有利于实现共享。它是虚拟存储的基础。缺点：需要硬件支持（通常是CPU），OS实现较复杂。碎片：经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。 在一个分区内部出现的碎片（即被浪费的空间）称做内部碎片，如固定分区法会产生内部碎片。 在所有分区之外新增的碎片称做外部碎片。拼凑：移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端。这种技术称为紧缩（或拼凑）内存管理保护措施：防止地址越界&防止操作越权分页技术（地址转换的计算）： 内存快 页面页号块号0213283645p=INT A/L d=A MOD LA为逻辑地址L为页面大小页号p / 页内地址d例题：某作业J的逻辑地址空间为5个页，每页2048字节，且已知该作业的页表如右图请画出地址转换图，求出有效逻辑地址4865B所对应的物理地址。A=4865B,L=2048B,则 P=2, d=769.则物理地址为17153B分段技术（地址转换的技术）：段号s段内地址d逻辑地址：例题：已知段表如图所示，将下面的逻辑地址转化为物理地址段号基址长度合法0 / 非法10219600 01230014 0290100 131327580 04195296 0(0，430),(1,10),(1,11),(2,500),(3,400),(4,112)219+430=649虚拟存储器：借助于外存空间，允许一个进程在其运行过程中部分装入内存。虚拟存储系统将内存和外存有机结合在一起，从而得到一个容量相当于外存，速度接近于内存的存储体系。请求分页原理：请求分页存储管理技术是在单纯分页技术基础上发展起来的，二者的根本区别在于请求分页提供虚拟存储器。基本思想是：当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入内存。页面走向： 0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105 若每页100个字节，则页面走向简化为：1，4，1，6，1，6，1，6，1，6，1以下为缺页率计算的图示-先进先出法FIFO：最佳置换法OPT：最近最少使用置换法LRU：抖动：在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象为“抖动或颠簸”。第六章文件系统的功能： 文件管理。创建、删除、读写、执行等。 目录管理。每个文件创建一个目录项，若干目录项构成一个目录文件。可进行文件检索和权限限制。 文件存储空间管理。对文件存储空间的分配与回收、文件逻辑地址与物理地址的映射。 文件的共享和保护。共享、保护、转储、恢复。 提供方便的接口。用户观点（方便、可靠、共享、保护）、系统的观点（存储空间组织、分配、信息传输等）。文件系统目录的作用：为了加快对文件的检索，往往将文件控制块集中在一起进行管理。这种文件控制块的有序集合称为文件目录。文件控制块就是其中的目录项。完全由目录项构成的文件称为目录文件。文件目录实现文件名与存放盘块之间的映射。UNIX系统中目录分解的意义（课后题会计算）：【课后题】在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法”。假设目录文件存放在磁盘上，每个盘块512字节。文件控制块占64字节，其中文件名占8字节。通常将文件控制块分解成两部分，第1部分占10字节（包括文件名和文件内部号），第2部分占54字节（包括文件内部号和文件其他描述信息）。（1）假定某一目录文件共有254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录的某一个文件控制块的平均访问磁盘次数。（2）一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号，请给出访问磁盘次数减少的条件。答：（1）采用分解法前，一个盘块存放5l2/64=8目录项，254个目录项需要32个盘块，查找一个文件的平均访问的盘块数：(1+32)/2=16.5次； 采用分解法后，一个盘块存放5l2/10=51目录项，254个目录项需要5个盘块，查找一个文件的第1部分平均访问的盘块数：(1+5)/2=3次；查找第2部分需要访问磁盘1次，故查找一个文件控制块的平均访问磁盘次数是314次。（2）访问磁盘次数减少的条件为：（n1）/2（m1）/21 即 mn2第七章按使用性质对设备的分类： 存储设备：计算机用来存储信息的主要设备。 输入/输出设备：字符设备。SPOOLING系统概念：SPOOLing实现过程：SPOOLing技术的特点:(1)提高了I/O速度.从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作,如同脱机操作一样,提高了I/O速度,缓和了CPU与低速I/O设备速度不匹配的矛盾.(2)设备并没有分配给任何进程.在输入井或输出井中,分配给进程的是一存储区和建立一张I/O请求表.(3)实现了虚拟设备功能.多个进程同时使用一独享设备,而对每一进程而言,都认为自己独占这一设备,不过,该设备是逻辑上的设备.磁盘调度算法：要访问的磁道分别是：98，183，37，122，14，124，65，67最早来的请求是访问98道，最后一个是访问67道。设磁头最初在53道上。共移动640个磁道共移动236个磁道53，65，67，37，14，98，122，124，18353，37，14，65，67，98，122，124，183寻道时间-例题：磁盘请求以10,22,20,2,40,6,38柱面的次序到达磁盘驱动器,寻道时每个柱面移动需要6ms,计算先到先服务算法和电梯调度算法的寻道次序以及寻道时间。（所有情况下磁壁的起始位置都是柱面20）寻道时间=磁道移动总量*6ms(1) 先到先服务调度顺序20-10-22-20-2-40-6-38 磁道移动总量=10+12+2+18+38+34+32=146；寻道时间=146*6=876ms(2) 电梯调度顺序20-22-38-40-10-6-2 磁道移动总量=2+16+2+30+4+4=58：寻道时间=58*6=384ms磁盘存取时间： (1)磁盘寻道时间（即磁头从当前磁道移至指定磁道所用的时间） (2)旋转延迟时间（即磁头从当前位置落到指定扇区开头所用的时间） (3)数据传输时间 减少平均寻道时间就可以显著地改善系统性能。缓冲技术的作用： 缓解CPU与I/O设备间速度不匹配的矛盾。 提高它们之间的并行性。 减少对CPU的中断次数，放宽CPU对中断响应时间的要求。设备管理的主要功能： （1）监视设备状态 （2）进行设备分配 （3）完成I/O操作 （4）缓冲管理与地址转换（逻辑设备和物理设备的转换）