计算机操作系统(第四版)汤晓丹著复习摘记

1.2操作系统的发展过程操作系统的定义:是一组能有效组织和管理计算机硬件和软件资源，合理对各类作业进行调度，以及方便用户使用的程序的集合。1.2.1未配置操作系统的计算机系统1、人工操作方式[缺点:用户独占全机，CPU等待人工IO操作]，严重降低了计算机资源的利用率。2、脱机输入/输出(Off-LineI/O)方式，程序和数据的输入实在外围机(脱离主机)的控制下完成，[优点:减少了CPU的空闲时间(IO操作不占用主机时间)，提高了IO速度(数据直接从高速磁带上输入到内存中)]1.2.2单道批处理系统先把一批作业以脱机方式输入到磁带上，在系统监督程序的控制下，使作业能够一个接着一个的连续处理。批处理系统旨在提高系统资源的利用率和系统吞吐量。[缺点:资源得不到充分的利用(当程序发出IO请求后，CPU必须等待)]1.2.3多道批处理系统利用作业调度算法，当一程序因IO操作而使CPU空闲时，调用执行另个程序。[优点:资源利用率高，系统吞吐量大。缺点:平均周转时间长，无交互能力]多道批处理系统需要解决的问题有：1处理机争用问题，2内存分配和保护问题，3IO设备分配问题，4文件的组织和管理问题，5作业管理问题，6用户与系统的借口问题。1.2.4分时系统指在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户通过自己的终端，以交互方式使用和计算机，共享主机中的资源。及时接受，及时处理。[特性:多路性，独立性，及时性，交互性]1.2.5实时系统指系统能够及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控制所有实时人物协调一致地运行。[实时系统的类型]：工业控制系统，信息查询系统，多媒体系统，嵌入式系统。1.2.6微机操作系统的发展1、单用户单任务操作系统:只允许一个用户上机，且只允许用户程序作为一个任务运行。2、单用户多任务操作系统:只允许一个用户上机，但允许用户把程序分为若干个任务，并发执行，有效的改善系统的性能。3、多用户多任务操作系统:允许多个用户通过各自的终端，使用同一台机器，共享主机系统中的各种资源。每个用户程序又可以进一步分为几个任务，并发执行，进一步提高资源利用率和系统吞吐量。1.3操作系统的基本特征1.3.1并发与并行并行指两个或多个事件在同一时刻发生，并发性指两个或多个事件在同一时间间隔内发生。1.3.2进程指在系统中能够独立运行并作为资源分配的基本单位，由一组机器指令，数据和堆栈等组成，是一个活动实体。多个进程之间可以并发执行和交换信息。能够极大的提高系统资源的利用率和增加系统吞吐量。2.1.3程序并发执行只有在不存在前趋关系的程序之间才有可能并发执行。2.程序并发执行的特征:间断性，失去封闭性，不可再现性。程序并发执行时由于共享系统资源和为完成同一项任务而相互合作，致使并发的程序之间形成了相互制约的关系。程序并发执行时，系统中共享的资源状态有并发程序来改变，使任一程序在运行时，其环境都会受到其他程序的影响而失去封闭性。程序失去了封闭性，也将导致失去可再现性。2.2.1进程的定义与特征定义：为了使程序能够并发运行并保持独立性，对并发的程序加以描述和控制，引入进程。操作系统为保证并发程序的独立性，设置了一个专门的数据结构：进程控制块PCB。利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。创建撤销进程，就是创建撤销进程实体中的PCB。进程是进程实体的运行过程，是系统进行资源分配和调度的独立单位。进程的特征动态性，并发性，独立性，异步性。进程同步机制，当进程在并发运行具有异步性时，保证进程并发执行的结果是可再现的。进程的三种基本状态:就绪状态，执行状态，阻塞状态。另外有创建状态和终止状态。引入创建状态是为了保证进程的调度必须在创建工作完成后进行，确保对PCB操作的完整性，也增加了管理的灵活性。挂起操作和进程状态的转换:引入挂起操作的原因：终端用户的需要，父进程请求，对换需要，负荷调节的需要，操作系统的需要。处于挂起状态的进程不能接收处理机调度。状态的转换：1.活动就绪-静止就绪，2.活动阻塞-静止阻塞，3.静止就绪-活动就绪，4.静止阻塞-活动阻塞。2.2.4进程控制块PCB的作用PCB是操作系统中最重要的记录型数据结构。1.作为独立运行基本单位的标志，PCB已成为进程存在于系统中的唯一标志。2.实现间断性运行方式。3.提供进程管理所需要的信息。4.提供进程调度所需要的信息。5.实现与其他进程的同步与通信。进程控制块中的信息：主要包括1.进程标志符，2.处理机状态，3.进程调度信息，4.进程控制信息。处理机状态信息主要由处理机的各种寄存器中的内容组成，包括1.通用寄存器，2.指令计数器，3.程序状态字，4用户栈指正。当进程被切换时，处理机状态信息必须保存在相应的PCB中，以便在进程重新执行时能够从断点继续。进程控制块的组织方式:1.线性方式，将系统中所有的PCB都组织在一张线性表中。2.链接方式，把具有相同状态的PCB分别通过PCB中的链接字链接成一个队列。如就绪队列，阻塞队列和空白队列。3.索引方式，根据进程状态的不同，建立几张索引表，如就绪索引表和阻塞索引表。2.4.1进程同步的基本概念进程同步机制的主要任务是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能够按照一定的规则共享系统资源，并能很好的相互合作，从而使程序的执行具有可再现性。1。两种形式的制约关系：1).间接相互制约关系，进程之间因为临界资源的使用而相互制约。因此系统的资源必须有系统实施统一分配，用户先申请才能使用资源。2).直接相互制约，进程之间有严格的执行次序的制约。2.临界资源：不同进程之间所共享的数据，变量，资源，涉及使用和修改时，都需要作为临界资源互斥访问。3.临界区：访问临界资源的代码称为临界区。4.进程同步应遵循的规则：1).空闲让出，临界资源空闲时需要立即让请求的进程使用该资源。2).忙则等待，临界资源被使用时，其他进程需要等待资源使用完毕再使用。3).有限等待，保证进程能在有限的时间内进入临界区，以免进入忙等。4).让权等待，进程不能进入临界区时，让出处理机，以免进入忙等状态。2.4.2硬件同步机制1.关中断2.利用Test-and-Set指令3.利用Swap指令硬件指令能够有效的实现进程互斥，但是容易让进城进入忙等状态，也很难解决复杂的进程同步问题。2.4.3信号量机制1.整型信号量：一个用于表示资源数目的整型量S，仅能通过两个标准的院子操作wait(S)和signal(S)来访问。整型信号量未遵循让权等待原则2.记录型信号量：是一种不存在忙等的进程同步机制。在信号量机制中，还增加了一个进程链表指针list，用于链接所有等待进程。3.AND型信号量：将进程在整个运行过程中需要的资源一次性分配，结束后一次性释放。4.信号量集：对AND信号量进行扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，再一次PV原语操作中完成申请和释放。信号量集的特殊情况：1).Swait(S,d,d),信号量集中只有一个信号量S，允许每次申请d个资源，当现有资源少于d时，不予分配。2).Swait(1,1),蜕变为记录型信号量或互斥量。3).Swait(s,1,0)，当S》=1时，允许多个进程进入临界区，当S变为0时，阻止任何进程进入临界区。2.4.5管程机制管程是对进程共享资源的申请，释放和其他操作的封装。代表共享资源的数据结构及有对该共享数据结构操作的一组过程组成的资源管理程序构成了一个操作系统的资源管理模块，管程。管程的主要特性：1).模块化，2).抽象数据类型，3).信息掩蔽2.条件变量：当一个进程调用了管程，在管程中时被阻塞或挂起，直到解除为止的期间内，如果不释放管程，其他进程便无法进入管程，被迫长时间等待。因此引入条件变量，指引起进程阻塞和挂起的条件的变量。x.wait是将因某个条件阻塞或挂起的进程送入等待队列，并释放管程，x.signal是将因某个条件送入等待队列的进程激活。3.1.1处理机调度的层次1.高级调度：调度对象是作业，根据某种算法将外村上处于后备队列中的哪几个作业调入内存，创建进程，分配必要的资源，放入就绪队列。多用于多道批处理系统中。2.低级调度：调度对象是进程，根据某种算法，保存处理机的现场信息，并决定就绪队列中的哪个进程获得处理机。进程调度是一种最基本的调度。3.中级调度:又为内存调度，对象是进程。主要目的是提高内存利用率和系统吞吐量，把暂时不能运行的进程调至外存等待，进程状态变为挂起状态。当运行条件具备和内存空余时，再把进程调度到内存中的就绪队列，变为就绪状态。3.1.2处理机调度算法的目标共同目标:1.提高资源利用率，使处理机和其他所有资源尽可能的保持忙碌状态。2.公平性，每个进程都获得合理的CPU时间，不发生进程饥饿现象。3.平衡性，尽可能保持系统资源使用的平衡性。4.策略强制执行。批处理系统的目标:1.平均周转时间短，作业被提交给系统开始到作业完成为止的时间间隔短。应使作业周转时间和平均周转时间都尽可能短。2.系统吞吐量高，指单位时间内系统所完成的作业数，与处理的作业从平均长度有关。3.处理机使用率高。分时系统的目标:1.响应时间快，从用户提交一个请求开始到显示出处理结果为止。2.均衡性好，指系统响应时间的快慢与用户请求服务的复杂性相适应。实时系统的目标:1.截止时间短，2.可预测性。3.2.3先来先服务FCFS和短作业优先SJF调度算法FCFS:系统按照作业到达的先后次序进行调度。主要用于与其他调度算法结合，形成一种更为有效的调度算法，如可以把进程按优先级设置多个队列，每个队列采用FCFS。SJF:作业时间短，优先级高。[缺点：]1.必须预知作业的运行时间。2.对长作业非常不利。3.无法时间人机交互。4.不能保证紧迫作业及时执行。3.2.4优先级调度算法PSA和高响应比优先调度算法HRRNPSA：根据作业或进程的紧迫程度设置的优先级进行调度。HRRN：是既考虑了作业的等待时间，又考虑了运行时间的调度算法[优点:]既照顾了短作业，又不使长作业的等待时间过长，改善了处理机调度的性能。优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间。1.如果作业等待时间相同，则要求服务时间越短，优先权越高，有利于短作业。2.当要求服务时间相同，优先权取决于响应时间。3.对于长作业，优先级随着等待时间的增加而提高。[缺点:]调度前需要做响应比计算，增加系统开销。3.3.1.1进程调度的任务1.保存处理机的现场信息。2.按某种算法选取进程。3.把处理器分配给进程。3.3.1.2进程调度机制1.排队器，事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列。2.分派器，将处理机分配个新选出的进程。3.上下文切换器，分派处理器时，新选进程的CPU现场信息装入到处理器的各个寄存器中；阻塞进程时，将处理器寄存器中的现场信息保存到进程PCB中。3.3.1.3进程调度方式1.非抢占方式：把处理机分配给进程后，只有当进程运行结束或者阻塞时，才将处理机分配给其他进程。[优点:]实现简单，系统开销小。适用于大多数批处理系统。2.抢占方式，允许调度程序根据某种原则，去暂停某个正在执行的进程，将处理机分配个另一个进程。抢占原则1.优先权原则，2.短进程优先原则，3.时间片原则。3.3.2转轮调度算法基本原理：基于时间片的调度算法，让就绪队列上的每个进程每次仅运行一个时间片，保证就绪队列中的所有进程在确定的时间内，都能获得一个时间片的处理机时间。进程切换时机：1.时间片未用完，进程已经结束。2.时间片已用完。时间片大小的确定：一个较为可取的时间片是略大于一个典型交互所需要的时间，使大多数交互进程能在一个时间片内完成，从而获得很小的响应时间。3.3.3优先级调度算法1.非抢占式优先级调度算法。2.抢占式优先级调度算法。优先级类型：1.静态优先级，在创建进程时确定，整个运行期间不会改变。2.动态优先级，进程创建初期赋予一个优先级，随着进程的推进或等待时间的增