《计算机操作系统》复习笔记

第一章操作系统引论【操作系统】是一组控制和管理计算机硬件和软件的资源、合理地对各类作业进行调度，以及方便用户使用计算机的程序的集合。是配置在计算机硬件上的第一层软件，是对硬件的首次扩充。【操作系统的目标】方便性，有效性，可扩展性，开放性。在计算机中配置操作系统的目的主要是提高系统资源的利用率。操作系统主要是管理计算机中的资源，包括存储器（主要为进程管理）和处理机。【操作系统的作用】从用户的观点，是用户和计算机硬件系统之间的接口（命令方式，图形窗口方式，系统调用方式）；从资源管理观点，是计算机资源的管理者（处理机，存储器，文件设备管理）；从虚拟机的观点，是扩充裸机功能的软件；从任务组织观点，是计算机工作流程的组织者。【操作系统的发展过程】人工操作方式，脱机输入/输出方式，单道批处理系统（自动性，顺序性，单道性），多道批处理系统（多道性，调度性，无序性），分时系统（多路性，独立性，及时性，交互性），实时系统。【操作系统的基本特征】并发（最基本特征），共享（互斥共享，同时访问），虚拟，异步性。【操作系统的功能】处理机管理（进程控制，进程同步，进程通信，进程调度），存储器管理（内存分配，内存保护，地址映射，内存扩充），设备管理（缓冲管理，设备分配，设备处理），文件管理（文件存储空间的管理，目录管理，文件的读写管理和保护），提供友好用户接口（命令，程序，图形用户接口）。五大功能的必要性：为了使多道批处理系统有序高效进行，并方便用户的使用。【操作系统的结构设计】整体式系统，模块化结构，分层式结构，微内核结构。【分时操作系统】允许多个用户已交互的方式使用计算机，方便用户。根据用户所能接受等待时间来确定的。多方面服务程序。【批处理操作系统】允许多用户将若干个作业提交给计算机系统集中处理，提高资源利用率。为了充分利用资源，一帮优先选择计算型和I/O型多个作业投入运行。批处理作业，必须提供相应的作业控制信息【实时操作系统】计算机系统能及时的处理由过程控制的反馈数据并响应。根据控制对象所能接受的时延。专用服务程序。第二章进程管理【进程的顺序执行】若干个程序必须严格按照某种先后次序执行。特点：封闭性，顺序性，可再现性。【前驱图】有向无循环图，描述进程或是程序间的先后次序，节点为程序。【并发性】若干事件在同一时间间隔内发生。提高资源利用率和系统吞吐量。特点：间断性，不可再现，不封闭。【进程】结构特征：含有一个数据结构PCB，进程控制快；动态性（有一定的生命周期）最基本特征；并发性；独立性；异步性。进程是程序的一次执行。进程与程序不一一对应。【进程的三种状态】就绪（以获得CPU以外的所有必须资源）——执行（得到CPU）——阻塞，挂起状态（静止状态），可腾出内存给其他程序【进程控制块PCB】是进程实体的一个组成部分，记录了OS所需的、用于描述进程的当前状态以及控制进程的全部信息。作用是将进程变成可并发执行的进程。进程存在的唯一标示。通常包含：进程标示符，处理机状态，进程调度和控制信息。一个系统中通常有多个PCB。【进程控制】最基本功能。用于创建和撤销进程。内核通过原语【原语】由若干条指令组成、用来实现某个特定的一个过程。具有原子性。【处理机的两种执行状态】系统状态，用户状态。【进程同步】对多个相关进程在执行次序上进行协调，使个程序协调合作，从而具有再现性。包含两种形式的制约关系：间接相互制约，直接相互制约。【临界资源】一段时间内只允许一个进程使用的资源。诸进程应采用互斥的方式进行共享。互斥访问：打印，输入，磁带，共享变量，共享数据结构。互斥是解决进程间竞争关系，同步解决协作关系。【同步机制应遵守的原则】空闲让进，忙则等待，有限等待，让权等待【信号量机制】整型信号量，记录型，AND型（避免死锁）。看PPT上的关于写信号量的例题。【管程机制】代表临界资源的数据及在其上操作的一组过程，即用少量的信息和对该资源所执行的操作来表征该资源。【管程】代表共享资源的数据结构以及又对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块。它被请求和释放资源的进程所调用。管程有四个部分组成：名称，局部于管程内部的共享（只能被局限于内部的过程所访问）数据结构说明，对该数据结构进行操作的一组过程，对共享数据设置初始值的语句。【管程的特性】模块化，抽象数据类型，信息掩盖。在利用管程实现进程同步时，必须设置同步工具，两个操作原语：wait，signal。【进程通信的类型】共享存储器系统，消息传递系统（send和receive两条通信命令），管道通信（连接两个进程的一个打开的共享文件）。【线程】比进程更小可以独立运行的基本单位。是进程内的一个执行单元（执行路径），是系统独立调度和分派的基本单位。每个线程都有独立的堆栈和线程控制块TCB。一般现成自己不拥有系统资源。在操作系统中引入进程的目的是使多道程序能并发执行，在操作系统中再引入线程（Thread），则是为了减少程序并发执行所付出的时空开销，使操作系统具有更好的并发性。【进程的两个属性】拥有资源的独立单位；调度和分派的基本单位资源分配的实体还是进程，进程相当于将他的两个属性拆开来使用。线程是进程中的实体，一个进程可以拥有多个线程，一个线程必须有一个父进程。【线程的属性】轻型实体，独立调度和分配的基本单位，可并发执行，共享进程资源【线程的状态】1）状态参数：在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。①寄存器状态；②堆栈；③线程运行状态；④优先级；⑤线程专有存储器；⑥信号屏蔽。【多线程OS中的进程属性】作为系统资源分配的单位。可包括多个线程。进程不是一个可执行的实体。【互斥锁】实现线程间资源的互斥，适合于高频使用。每个条件变量通常与一个互斥锁一起使用，在创建互斥锁时就会联系一个条件变量。【用户级线程】管理过程全部由用户程序完成，操作系统内核心只对进程进行管理。调用时阻塞进程【内核支持线程】由操作系统内核进行管理。操作系统内核给应用程序提供相应的系统调用和应用程序接口API，以使用户程序可以创建、执行、撤消线程。调用时阻塞线程进程转换中，决不可能发生的是：就绪-阻塞，一般不会发生的是：阻塞-执行。活动就绪-静止就绪：suspend原语对于记录性信号，执行一次wait时，信号量的值-1，当其值为小于0，进程阻塞；执行signal，信号量+1，当其值为小于等于0是，唤醒阻塞生产消费者问题：mutex：1，full：0，empty：n信号量初值不能为负；线程是CPU调度的基本单位，但不是资源分配的基本单；管程每次只允许一个进程进入；wait，signal可以解决一切互斥问题第三章处理机调度与死锁【高级调度】决定把后备队列作业中的哪些作业调入主存，为它们创建进程并启动它们运行。做出两种选择：多道程序度（接纳多少作业），各种调度算法（接收哪些作业）。四种状态：提交，后备，执行，完成。调度对象是作业，运行频率低，常用批处理（设置作业控制块JCB，作业在系统中存在的标志），分时实时不常用。在批处理操作系统中，作业首先进入系统在辅存上的后备作业队列等候调度，因此，作业调度是必须的。在纯粹的分时或实时操作系统中，通常不需要配备作业调度。【低级调度】决定就绪队列中哪个进程应先获得处理机，并将处理及分配给选中的进程。最基本的调度。可采取以下两种方式：非抢占式方式（获得CPU后一直使用，直到完成或阻塞。简单开销小），抢占方式（抢占原则：优先权原则，短作业优先原则，时间片原则）【进程调度的功能】保存处理机的现场信息。按调度算法选择进程运行。由分配程序实施处理机的分配及回收【中级调度】按照一定的算法将外村中已经具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出内存。目的是解决内存紧张问题常用于分时系统和虚拟存储器系统中。【处理机调度的主要任务】是按一定的调度算法选择进程（作业），并使它们运行【选择调度算法有以下准则】面向用户的准则（周转时间短：批处理系统用户看重；响应时间快：分时系统用户看重。截止时间的保证：实时系统用户看重。稳定性：面向用户的准则）。面向系统准则（系统吞吐量高：批处理系统看重。CPU利用率好：大中型主机看重，对微机和实时系统不太重要。各类资源的平衡利用：大中型主机看重，对微机不太重要周转时间＝完成时刻－提交（到达）时刻n个作业的平均周转时间：即n个作业的平均带权周转时间：带权周转时间：周转/服务【先来先服务调度算法】可用于作业调度，也可用于进程调度。非抢占式有利于长作业，不利于短作业。【短作业优先调度算法】总是选择估计运行时间最短的作业或进程，可分别作用与进程和作业调度，有抢占和非抢占两种。可降低作业平局等待时间，提高系统吞吐量。多个作业同时到达时，短作业优先调度算法的平均周转时间最小【最短剩余时间优先调度算法（抢占式优先权调度）】即当一个新进程进入就绪队列时，若其需要的运行时间比当前运行进程的剩余时间短，则它将抢占CPU【最高响应比优先调度算法】特点：有利于短作业；考虑等待时间；不会饥饿对于每一个运行完的时刻进行计算响应比，最高的则为下一个运行的进程。【时间片轮转调度算法】就绪进程按到达时间的先后次序排成一个队列（FIFO队列），每次调度时把CPU分配给队首进程，并令其执行一个时间片。当时间片用完时，停止该进程的执行，将它送至就绪队列末尾等待下一次执行，然后再把处理机分配给就绪队列中的新队首进程。时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。？【多级反馈队列】应设置多个就绪队列，并为每个队列赋予不同的优先级。第1个队列的优先级最高，第2队列次之，其余队列的优先级逐次降低。同一队列中进程执行的时间片大小相同，不同队列时间片大小不同，队列的优先级越高，其相应的时间片就越短。【死锁】是指多个进程因竞争系统资源而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。【死锁产生的原因】竞争资源；进程推进顺序不当。【产生死锁的条件与预防】互斥，请求与保持（要求进程一次申请它所需的全部资源，若有足够的资源则分配给进程，否则不分配资源，进程等待。这种方法称为静态资源分配法），不剥夺（一个已保持了某些资源的进程，若新的资源请求得不到满足，则它必须释放已获得的所有资源，待以后需要时再重新申请），环路等待（将所有资源按类型排队，并赋予不同序号，要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。这种方法称为有序资源分配法），破坏一个既可防止死锁参与死锁的进程至少有两个；参与死锁的进程至少有两个已经占有资源；参与死锁的所有进程都在等待资源；参与死锁的进程是当前系统中所有进程的子集【死锁避免】允许进程动态申请资源，系统在为申请者分配资源前先检查资源分配的安全性。【安全状态】是指系统能按某种顺序如P1,P2,…,Pn来为每个进程分配其所需的资源，称序列P1,P2,…,Pn为安全序列。不安全状态不一定会导致系统进入死锁【银行家算法接触死锁】详见课本P110【死锁检测】一个检测系统状态从而确定是否出现了死锁的算法。【死锁解除】一个从死锁状态恢复的算法。可提高利用率，但是难度大【资源分配图】可以用来描述系统死锁。由节点（圆圈表示进程，方框加圆圈为资源，此时圆圈表示此类资源的个数），和边（请求边由进程指向方框，分配边由方框中的一个点指向进程）。简化资源分配图可以检测死锁:找出一个既不阻塞又非孤立的进程结点,删除他的分配和请求边,以此类推.若最后全为孤立的点则为完全简化.【死锁定理】S为死锁状态的条件是当且仅当S状态的资源分配图是不可完全简化的【死锁解除的方法】剥夺资源，撤销进程。三种基本类型的操作系统中,都设置了进程调度,批处理还设置了作业调度,分时还设置了中级调度.作业调度是从处于后备状态的队列中选取作业投入,周转时间是指作业进入系统到作业完成所经历的时间间隔,时间片轮转不适合作业调度.先到先服务只可非抢占,时间片轮转法只能抢占,其余的都可以为了照顾短作业用户,采用短作业优先;为照顾紧急用户,采用优先权调度;实现人机交互,采用时间片轮转;为了兼顾