操作系统知识点

PAGEPAGE1操作系统书本知识点第一章操作系统引论主要内容操作系统的目标、作用和模型操作系统的发展过程操作系统的基本特征OS（OperatingSystems)的主要功能OS的结构设计本章要点计算机系统结构：了解操作系统的地位什么是操作系统：3种基本观点现代操作系统的功能、特性、类型基本概念：批处理、多道程序、作业、进程、任务、虚拟技术、并发性、异步性操作系统的作用(1)作为用户与计算机硬件系统之间的接口作为计算机系统资源的管理者处理机管理：分配和控制处理机存储器管理：分配及回收内存I/O(Input/Output)设备管理：I/O分配与操作文件管理：文件存取、共享和保护监视这些资源实施某种资源分配策略分配这种资源回收这种资源OS实现了对计算机资源的抽象操作系统的发展过程1.2.1无操作系统时的计算机系统人工操作方式如纸带输入机。特点是用户独占全机及CPU等待人工操作。脱机I/O方式（图1.3）引入I/O机的概念，解决前者的缺点。特点是减少了CPU的空闲时间且提高I/O速度。单道批处理系统处理过程（图1.4）概念：系统对作业的处理都是成批进行的、且内存中始终只保持一道作业，称为单道批处理系统（simplebatchsystem）。批处理系统的引入是为了提高系统资源的利用率和吞吐量概念：运行控制权特征自动性、顺序性、单道性多道批处理系统（1）优点资源利用率高系统吞吐量大平均周转时间长无交互能力缺点平均周转时间长、无交互能力分时系统分时系统的产生概念：指一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户共享主机中的资源，各个用户都可通过自己的终端以交互方式使用计算机。分时系统在实现中的关键问题及时接收：多终端卡、输入缓冲区及时处理：交互作业应在内存、响应时间应短分时系统的特征多路性独立性及时性交互性可靠性类型实时控制实时信息处理实时系统(2)实时任务类型按任务执行是否呈现周期性来划分周期性的（联系周期）；非周期性的（联系开始或完成截止时间）根据对截止时间的要求来划分硬实时任务软实时任务实时、分时的比较多路性：相同独立性：相同及时性：实时系统要求更高交互性：分时系统交互性更强可靠性：实时系统要求更高思考试在交互性、及时性和可靠性方面，将分时系统和实时系统进行比较。操作系统的基本特征(1)并发性并行是指两或多个事件在同一时刻发生。并发是两或多个事件在同一时间间隔内发生。进程：系统中能独立运行并作为资源分配的基本单位。引入线程后，独立运行的单位变为线程。共享性系统中资源可供内存中多个并发执行的进程共同使用互斥共享：一段时间只允许一个进程访问该资源同时访问：微观上仍是互斥的虚拟性通过某种技术把一个物理实体变为若干个逻辑上的对应物。若n是某一物理设备所对应的虚拟的逻辑设备数，则虚拟设备的速度必然是物理设备速度的1/n。异步性运行进度不可预知。操作系统的功能处理器管理功能(1)进程和作业调度进程：指在系统中能独立运行并作为系统资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个活动实体。作业调度（又称高级调度或长程调度）：用于把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。2）进程控制为作业创建进程，撤消已结束的进程、阻塞进程和唤醒进程。（3）进程同步使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。 可能存在两种制约关系：间接相互制约关系、直接相互制约关系。（4）进程通信进程间信息的交换存储器管理功能主要指内存管理，即如何分配内存空间，如何提高存储器的利用率以及能从逻辑上扩充内存。（1）内存的分配静态分配方式：每个作业的内存在作业装入时确定；在作业装入后的整个运行期间，不允许该作业再申请新的内存空间，也不允许作业在内存中“移动”。动态分配方式：允许作业在内存中“移动”。为此，需内存分配的数据结构及内存分配和回收功能2）存储保护指存储管理应确保每道用户程序都只在自己的内存空间内运行，彼此互不干扰。例：设置上、下界寄存器，每条指令进行越界检查（一般是硬件实现）（3）地址映射完成逻辑地址到物理地址的转换（4）内存扩充采用虚拟技术实现内存扩充，具有请求调入和页面置换功能。设备管理功能完成设备的分配和回收，设备的控制和信息传输，提高CPU和I/O设备的并行程度和利用率，方便、快捷地完成用户提出的I/O请求。 如：CPU快则应多创建缓冲区（1）缓冲管理 有效地缓和CPU和I/O设备速度不匹配问题，提高CPU利用率，提高系统吞吐量。 常见的缓冲区机制有：单缓冲机制、双缓冲机制（2）设备分配包括：设备，设备控制器，I/O通信的分配和回收（3）设备处理指控制设备进行实际的操作，包括读、写等以及向CPU发中断。设备处理/驱动程序应能根据用户的I/O请求，自动地构成通道程序。4）设备独立性独立性，即program与设备无关性，使program易于重定向，增加了可移植性。（5）虚拟设备管理文件管理功能对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安全性。（1）文件存储空间的管理（2）目录管理使用户按名存取，提高速度。（3）文件的读/写管理和保护用户接口一、命令接口由一组“命令”集组成，分为联机和脱机用户接口1.联机用户接口由一组键盘操作命令及命令解释程序所组成2.脱机（批处理用户接口）用JCL写作业说明书二、程序接口系统调用高级语言的库函数三、图形接口如win的copy文件，采用“拖”来完成，生动，不需记忆OS的结构设计无结构操作系统模块化结构操作系统分层式结构操作系统微内核操作系统结构1.无结构操作系统一组过程集，各过程可相互调用，也叫整体系统结构。缺点：逻辑复杂，维护困难.2、模块化操作系统通过分解来控制大型软件复杂度。如：进程模块、内存模块…，各模块内进一步划分子模块。优点：提高了OS设计的可维护性增强的OS的可适应性加速了OS的开发过程：并行开发模块缺点：接口不易确定模块依赖关系可能复杂（对于大型软件而言）3、分层式操作系统有序分层的基本概念可简化设计的复杂度下层为上层提供服务层次的设置应考虑的因素程序嵌套：各模块间嵌套关系复杂运行频率：随层次的增高，相应软件的运行速度就随之下降公用模块：低层用户接口：高层微内核操作系统结构（1）提高了系统的灵活性和可扩充性提高了软件的可靠性适合于分布式系统微内核操作系统结构（2）面向对象的程序设计技术概念：优点：a.可扩展性b.继承性微内核技术引入：提高系统的灵活性；采用C/S模式基本功能进程、内存、IPC等基本管理功能第二章进程管理程序顺序执行时的特征(1)顺序性(2)封闭性程序是在封闭的环境下运行的。即程序在运行时，它独占全机资源。一旦运行,不受外界影响.(3)可再现性只要程序执行时的环境和初始条件相同，当程序多次重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。进程的特征(1)动态性进程是程序的一次执行过程，因此，属于动态概念，是进程的最重要的特征。动态性还表现为:“它由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤消而消亡”。可见,进程有一定的生命期。而程序只是一组有序指令的集合，并长期存放在某种介质上，本身并无运动的含义，因此，程序是个静态实体。进程和程序不是一一对应的，如几个进程可同时执行一个程序。(2)并发性这是指多个进程实体，同存于内存中，能在一段时间内同时运行。并发性是进程的第二个最重要特征。引人进程的目的也正是为了使其程序能并发执行，而程序是不能并发执行的。(3)独立性这是指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。凡未建立进程的程序，都不能作为一个独立的单位参加运行。(4)异步性这是指进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。正是这一特征，将导致程序执行的不可再现性。因此，在OS中必须采取某种措施来保证各程序之间能协调运行。(5)结构特征从结构上看，进程实体是由程序段、数据段及进程控制块三部分组成。进程的三种基本状态注意：*可逆：仅就绪àß执行*主动：仅执行阻塞*微观上：执行状态时，程序在运行*宏观上：进程建立后直至撤消，程序都在运行。1)就绪(Ready)状态一个刚被创建的进程，它的初始状态是就绪。进程所请求的一次打印输出结束后，将使进程状态从等待态变为就绪态。2)执行状态单CPU系统中,最多只有一个进程处于运行状态。分配到必要的资源并获得处理机时的进程状态是执行状态。如：某进程已获得运行所需的其它资源(CPU除外)，将处于就绪，当它获得CPU时，就将处于运行（执行）状态。进程从运行状态进入就绪状态的原因可能是时间片用完。3)阻塞状态进程管理中，在等待的事件发生情况下，进程将从阻塞状态变为就绪状态。一个进程状态转换的发生是否一定会导致另一个状态的转换发生，列出所有可能：进程同步基本概念（1）进程同步的两种形式的制约关系：间接相互制约关系。此时进程同步的主要任务是保证诸进程能互斥的访问临界资源。因此，资源应由系统同一分配。直接相互制约关系。此时此时进程同步的主要任务是保证相互合作的进程在执行次序上的协调，避免出现与时间有关的错误。临界资源一次仅允许一个进程使用的资源叫临界资源。Ÿ属于临界资源的物理设备，如输入机、打印机、磁带机等。Ÿ属于临界资源的软件资源，如多个进程共享的变量、数据、队列等。两个交往的并发进程，其中一个进程对另一个进程的影响常常是不可预期的，甚至是无法再现，因为两个并发进程执行的相对速度无法控制，所以一个进程的速率通常无法为另一个进程所知。如：两个进程P1，P2共享变量counter（初值5）： P1P2 registerl＝counter； register2＝counter； registerl＝registerl+1； register2＝register2–1； Counter=register1 Counter=register2；如果一个进程先执行，然后另一进程再执行，则counter的值仍为5。如改变执行次序，counter可能为4或6。原因：两个进程共享了变量counter.解决方法：把counter作为临界资源处理。临界区程序上如何实现互斥使用临界资源呢？只要把进程中访问临界资源的那段代码分离出来（它被称为临界区），诸进程互斥地进入自己的临界区即可。信号量机制1965年，荷兰学者dijkitra提出的信号量机制是一种卓有成效的进程同步工具。现在信号量机制已被广泛地应用于单处理机和多处理机系统，以及计算机网络中。P、V操作操作系统利用信号量实现对进程和资源的控制和管理。信号量的值仅由P、V操作来改。P、V操作是能够实现对临界区管理要求的两条原语，P操作起到了限制一次只有一个进程进入临界区的作用，而V操作将唤醒位于阻塞队列中的头一个进程，使其可以进入临界区，保证了进程在临界区内逗留有限时间。P原语操作的主要动作是：Semaphore减1；若Semaphore减1后仍>=0,则进程继续执行。若Semaphore减1后<0,则进程被阻塞在与该信号相对应的队列中，然后转进程调度。V原语操作的主要动作是：Semaphore加1；若Semaphore加1后仍>0,则进程继续执行。若Semaphore加1后<=0,则从信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。利用信号量实现前驱关系T1T1T2T3T4Vara,b,c,d,e,f,g:semaphore:=0;Beginparbegins1:v(a);v(b);p(a);s2;v(c);v(d);p(b);s3;v(e);p(c);s4;v(f);p(d);s5;v(g);p(e);p(f);p(g);s6;end;Parendend设有一个作业由4个进程组成，这4个进程必须按下图所示的次序运行，试用P、V操作表达4个进程的同步关系。2.4经典进程同步问题在多道程序环境个，进程同步问题是十分重要的，也是相当有趣的问题，因而吸引了不少学者对它进行研究，由此而产了一系列经典的进程同步问题，其中“生产者—消资者问题”、“读者—写者问题”、“哲学家进餐问题”很具有代表性，是许多实际的进程同步问题的抽象，具有实用价值。1、生产者－消费者问题生产者－消费者问题是一个著名的同步问题。其描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程和消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中，消费者可从一个缓冲区中拿走产品去消费。生产者与消费者是等效的，只要有空时，生产者可送入，只要有满buf，消费者可取走。这是多个进程相互合作的一种抽象，如输出时：计算进程是生产者，打印进程是消费者。分析：从资源的观点很容易解这个问题。1.有空buf生产者才能送数据，可设计数信号量empty，初值为n。2.有装满数据的buf，消费者才能取数据，故设数信号量full，初值为0。3.对某个buf应互斥使用，设互斥信号量mutex，初值为1。如何用P.V操作同步：此处可以看到：1.P.V操作必须成对出现2.两个P操作次序不可颠倒，为什么？对于n个环行buf的生产者—消费者问题的进程同步算法描述：varmutex,empty,ful1：semaphore:＝1,n,0;buffer：array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbeginproducer:beginrepeatproduceraniteminnextp;wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);untilfalse endconsumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalseendparendend2哲学家进餐问题哲学家进餐问题是典型的同步问题。它是由Dijkstra提出并解决的。该问题是描述有五个哲学家，它们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。利用记录型信号量解决哲学家进餐问题经分析可知，筷子是临界资源，用如下信号量数组实现互斥：varchopstick：array［0，…，4］ofsemaphore；所有信号量被初始化为1，第i个哲学家的活动可描述为：repeatwait(chopstick[i])；先拿左边的筷子wait(chopstick[(i+1)mod5])；再拿右边的筷子eat;signal(chopstick[i])；signal(chopstick[(i＋l)mod5])；think;untilfalse；问题：哲学家如各自拿起左边的筷子时，就会产生死锁。对于这样的死锁问题可采取以下几种解决方法：(1)至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。(2)仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子进餐。(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。3、读者一写者问题一个数据文件和记录，可以被多个进程共享，我们把只要求读该文件的进程称为reader进程，把其他进程称为writer进程。允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个writer进程和其他reader进程或writer进程同时访问共享对象。一.利用信号量机制解法：设置两个信号量，一个整型变量。Ÿ写互斥信号量wmutex：用于实现一个写者与其它读写者互斥访问共享对象，事实上，它被第一个进入的读者和最后一个离去的读者使用，中间读者不用。Ÿ读互斥信号量rmutex：使读者互斥访问readcount——当前读者进程数。Ÿ一个整型变量：readcount初值为0。读者—写者问题可描述如下：semaphorermutex=1，wmutex=1;Intreadcount=0;While(true)wait(rmutex);(rmutex代表的是读进程互斥访问readcount)ifreadcount==0wait(wmutex);readcount=readcount+1;signal(rmutex);Performreadoperation；wait(rmutex)；readcount=readcount一1；ifreadcount=0signal(wmutex);signal(rmutex)；writer：repeatwait(wmutex);Performwriteoperation；signal(wmutex)；untilfalse;end进程通信进程的互斥与同步就是一种进程间的通信方式。由于进程互斥与同步交换的信息量较少且效率较低，因此称这种通信方式为低级进程通信方式，相应的也将P、V原语称为两条低级进程通信原语。第3章处理机调度与死锁高级调度作业控制块JCB过程每当作业进入系统时，系统便为每个作业建立一个JCB，根据作业类型将它插入相应后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。在作业运行期间，系统就按照JCB中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤销它的作业控制块。低级调度进程调度可采用下述两种方式：1．非抢占方式(Non-PreemptiveMode)采用这种调度方式时，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。优点是实现简单、系统开销小，适用于大多数的批处理系统环境。但它难于满足紧急任务的要求：立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中不宜采用这种调度方式。2．抢占方式(PreemptiveMode)这种调度方式，允许调度程序根据某种原则，去停止某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程；抢占的原则有：(1)时间片原则。各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数实时系统，以及要求较高的批处理系统。(2)优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行(3)短作业(进程)优先原则，当新到达的作业(进程)比正在执行的作业(进程，明显地短时，将剥夺长作业(进程)的执行，将处理机分配给短作业(进程)，使之优先执行。中级调度中级调度又称为中程调度(Medium-TermScheduling)。引入中级调度的主要目的，是为了提高内存的利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上，等待进程调度。中级调度实际上就是存储器管理中的对换功能。调度算法先来先服务调度算法(FCFS)作业调度和进程调度都可使用，最简单，本质上属于非剥夺方式。有利于长作业/进程。显然有利于CPU繁忙型的作业(如通常的科学计算)，而不利于I／O繁忙阻的作业/进程（如大多数的事务处理)。短作业(进程)优先调度算法(SJF/SPF)有利于短作业/进程。平均周转时间短，系统吞吐量高。缺点：长作业可能发生“饥饿”现象，也不能保证紧迫性作业(进程)会得到及时处理，用户可能会有意或无意地缩短其作业的估计执行时间。优先权调度算法一、优先权调度算法的类型为了照顾到紧迫型作业在进入系统后便能获得优先处理引入最高优先权调度算法，它常被用于批处理系统中作为作业调度算法，也是最常用的进程调度算法。用于进程调度时，又可分成两种方式：非抢占式优先权算法和抢占式优先权算法，差别在于：一旦出现了另一个优先权更高的进程时，对抢占式，其可抢先运行。二、优先权的类型1．静态优先权优先权是在创建进程时确定的，在进程的整个运行期间保持不变。确定进程优先权的依据有： (1)进程类型，系统进程高于用户进程，I/O繁忙进程高于CPU繁忙进程，前台（交互型用户进程）高于后台（批处理进程）。 (2)进程对资源的需求。估计执行时间及内存需要量少 (3)根据用户要求。静态优先权法简单易行、系统开销小，但某些进程可能长期等待.2．动态优先权优先权是可以随进程的推进而改变，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a增加。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将最先获得处理机。此即FCFS算法；若所有的就绪进程具有各不相同的优先权初值，对于优先权初值低的进程，在等待足够的时间后，其优先权便可能升为最高，从而可以获得处理机执行。当采用抢占式优先权调度算法时，如果再规定正在执行的进程，其优先权以速率b下降，于是便可防止一个长作业长期地垄断处理机。高响应比优先调度算法时间片轮转调度算法本质上属于剥夺方式,分时系统中无例外采用(为确保响应时间)系统使每个进程依次按时间片q轮流的方式执行，q的大小从几ms到几百ms。当时间片用完时，计时器触发一个中断，重新调度，从而让就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。时间片大小是关键问题太大，大到每个进程部能在一个时间片内执行完毕，则退化为FCFS算法，过小，进程切换时间比重过大影响CPU使用率。通常要考虑到以下几个因素：1.对响应时间的要求与就绪队列中进程数目响应时间T直接与用户(进程)数目N和时间片q成比例,即T=Nq。q正比与响应时间，反比与就绪队列中进程数目。2.计算机的处理能力。速度快，q可小些。通常q值是这样决定的：批处理系统：80%的CPU周期在一个时间片内完成。分时系统：q=T/NmaxT-响应时间上限Nmax-最大进程数多级反馈队列调度算法实时调度2.最低松弛优先算法算法（LLF）该算法是根据任务的紧急的程序，来确定任务的优先级；任务的紧急程序越高，为该任务所赋予的优先级就愈高，以使之优先执行该算法主要用于可抢占调度方式中某一进城的松弛度=必要完成时间-其本身运行时间-当前时间死锁的基本概念所谓死锁(Deadlock)，是指一组进程因竞争资源