搜索
ByTouchkiss2014-1-19第一章引论【了解和知道】1.小标题，概念，各种名词，基本控制，（填空选择）1.操作系统的目标:有效性（提高系统资源利用率、提高系统的吞吐量）、方便性、可扩充性、开放性。2.操作系统的作用（1）OS作为用户与计算机硬件系统之间的接口；（命令方式、系统调用方式、图形窗口方式）（2）OS作为计算机系统资源的管理者；（3）OS实现了对计算机资源的抽象。3.推动操作系统发展的主要动力（1）不断提高计算机资源的利用率；（2）方便用户；（3）器件的不断更新换代；（4）计算机体系结构的不断发展。4.单道批处理系统的特征：（1）自动性。在顺利情况下，在磁带上的一批作业能自动地逐个地依次运行，而无需人工干预。（2）顺序性。磁带上的各道作业是顺序的进入内存，各道作业的完成顺序与他们进入内存的顺序，在正常情况下应完全相同，亦即先调入内存的作业先完成。（3）单道性。内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存运行，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。5.多道批处理系统特点：（1）资源利用率高；（2）系统吞吐量大；（3）平均周转时间长；（4）无交互能力。6.分时系统特点：（1）多路性；（2）独立性；（3）及时性；（4）交互性。7、操作系统的特征：并发性、共享性、虚拟性、异步性。最基本的是并发性。【重点】1.4操作系统的主要功能：处理机管理功能：1、进程控制2、进程同步：为多个进程的运行进行协调进程互斥方式：诸进程在对临界资源进行访问时进程同步方式：相互合作去完成共同任务时ByTouchkiss2014-1-193、进程通信：合作的进程处于同一计算机上采用直接通信方式。4、调度：作业调度：选出若干作业，为他们分配资源进程调度：从线程队列中选出一个线程，分配处理机存储器管理功能：1、内存分配：为每道程序分配内存空间，提高存储器的利用率，以减少不可用的内存空间。可采用动态和静态2、内存保护：确保每道程序都在自己的内存空间内运行；决不允许用户程序访问操作系统的程序和数据；不允许用户程序转移到其他非共享程序中去执行3、地址映射4、内存扩充：用来实现请求调入功能和置换功能。设备管理功能：1、缓冲管理：为了有效缓和CPU与IO设备速度不匹配的矛盾，提高CPU的利用率2、设备分配3、设备处理4、虚拟设备文件管理功能：1、文件存储空间管理：提高外存利用率2、目录管理3、文件的读/写管理和保护操作系统与用户之间的接口：1、用户接口2、程序接口第二章进程管理1.进程的基本概念：前趋图：有向无循环图，必须不存在循环进程与线程的关系：进程和线程都是由操作系统所体会的程序运行的基本单元。进程与线程的不同点【重点】（简答）1、线程的划分尺度小于进程，使得多线程程序的并发性高。2、进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。3、每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。4、从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。2.进程同步：（貌似不考信号量）就绪和转换图就绪(IO完成)(进程调度)(时间片完)ByTouchkiss2014-1-19阻塞(IO请求)执行P34程序顺序执行时的特征顺序性封闭性可再现性P37进程的特征与状态【理解】结构特征：程序段、相关的数据段、PCB动态性：最基本的特征。并发性：进程实体能和其他进程并发执行，而程序不能。独立性：进程实体是一个能独立运行，独立分配资源和独立接受调度的基本单位异步性：进程按各自独立地不可预知的速度前进。P38进程的三种状态{图2-5进程的三种基本状态及其转换}就绪(IO完成)(进程调度)(时间片完)阻塞(IO请求)执行P39进入挂起状态的主要原因{图2-6具有挂起状态的进程状态图}1、终端用户的请求2、父进程的请求3、负荷调节的需要4、操作系统的需要P40加了创建和终止的状态图进程控制块的作用和组织方式{对每个进程是不是只有一个，记录进程的状态及名称，是不是在主存当中}对每个进程只有一个作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发的进程.PCB是进程存在的唯一标志.PCB应常驻内存.组织方式：1、链接方式：具有统一状态的PCB链接字链接的队列2、索引方式：根据所有进程的状态建立索引表2.2进程控制：掌握各种状态的基本含义和过程2.3进程同步：什么叫临界资源，同步机制应遵循的规则，信号量的主要应用{P50主要目的：同步，还有利用信号量实现前驱关系，进程互斥}ByTouchkiss2014-1-19临界资源是一次仅允许一个进程使用的共享资源。各进程采取互斥的方式，实现共享的资源称作临界资源。属于临界资源的硬件有打印机、磁带机等,软件有消息缓冲队列、变量、数组、缓冲区等。诸进程间应采取互斥方式，实现对这种资源的共享。每个进程中访问临界资源的那段代码称为临界区.同步机制应遵循的原则：1、空闲让进2、忙则等待3、有限等待4、让权等待信号量的主要应用：1、利用信号量实现进程互斥2、利用信号量实现前驱关系3、管程机制：进程的同步工具2.5进程通信：进程通信的类型1、共享存储器系统：基于共享数据结构的通信方式寄语共享存储区的通信方式2、消息传递系统：应用最为广泛3、管道通信2.6线程的基本概念，P73线程与进程在几方面的比较，P75线程间的同步和通信习题P813、4、7第三章处理机调度与死锁3.1处理机调度的层次3.1.1高级调度1．高级调度：又称为作业调度或长程调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，也就是说，它的调度对象是作业。2．作业：是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。3．作业步：在作业运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤成为一个作业步。4．作业流：若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。ByTouchkiss2014-1-193.1.2低级调度1.通常把低级调度称为进程调度或短程调度，它所调度的对象是进程。进程调度是最基本的一种调度，再多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。2.功能：（1）保存处理机的现场信息（2）按照某种算法选取进程（3）把处理器分配给进程3.进程调度三个基本机制（1）排队器。为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快的找到它。（2）分派器（分派程序）。分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后进行上下文切换，将处理机分配给它。（3）上下文切换机制。4.进程调度方式（1）非抢占方式：一旦处理机分配给某进程后，不管运行多长时间，都不会因时钟中断等原因而抢占正在运行进程的处理机，也不允许其他进程抢占已分配给他的处理机。（2）抢占方式：优先权原则、短作业优先原则、时间片原则。3.1.3中级调度1.中级调度：又称中程调度。引入的主要目的是为了提高内存利用率和系统吞吐量。中级调度实际上就是存储器管理中的对换功能。3.3调度算法3.3.1先来先服务和短作业优先调度算法1.先来先服务FCFS2.短作业优先调度算法SJ（P）F3.3.2高优先权优先调度1.优先权调度算法类型：非抢占式优先权算法、抢占式优先权调度算法。2.优先权的类型：静态优先权（进程类型、进程对资源的需求、用户要求）、动态优先权3.高响应比优先调度算法ByTouchkiss2014-1-193.3.3基于时间片的轮转调度算法1.时间片轮转法2.多级反馈队列调度算法3.多级反馈队列调度算法的性能（1）终端型作业用户。系统只要能使这些作业在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。（2）短批处理作业用户。可以满意（3）长批处理作业用户。用户不必担心其作业长期得不到处理。3.4实时调度3.4.1实时调度基本条件1.提供必要的信息:就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级。2.系统处理能力强3.采用抢占式调度机制4.具有快速切换机制：对外部中断的快速响应能力、快速的任务分派能力。3.4.2实时调度算法的分类1.非抢占式调度算法：非抢占式轮转调度算法、非抢占式优先调度算法。2.抢占式调度算法：基于时钟中断的抢占式优先权调度算法、立即抢占的优先权调度算法。3.4.3常用的几种实时调度算法1.最早截止时间优先即EDF（earliestdeadlinefirst）算法：非抢占式调度算法用于非周期实时任务、抢占式调度方式用于周期实时任务2.最低松弛度优先LLF（leastlaxityfirst）算法3.5产生死锁的原因和必要条件1.死锁：是指多个进程在运行过程中因争夺系统资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前推进。3.5.1产生死锁的原因（竞争资源、进程间推进顺序非法）1.竞争资源引起进程死锁ByTouchkiss2014-1-19（1）可剥夺和非剥夺性资源（2）竞争非剥夺性资源（3）竞争临时性资源2.进程推进顺序不当引起死锁3.5.2产生死锁的必要条件1.互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。2.请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源有已被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。3.不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。4.环路等待条件：3.5.3处理死锁的基本方法（1）预防死锁。较易实现，但会导致系统资源利用率和系统吞吐量降低。（2）避免死锁。只需事先施加较弱的限制条件，便可获得较高的资源利用率和系统吞吐量。（3）检测死锁。（4）解除死锁。与检测死锁相配套的一种措施。3.6预防死锁的方法3.6.1预防死锁1.摒弃“请求和保持”条件2.摒弃“不剥夺”条件3.摒弃“环路等待”条件4.环路等待条件严重问题：（1）为系统中各类资源所分配的序号必须相对稳定，这就限制了新类型设备的增加。（2）尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：即作业（进程）使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。（3）为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、自主的编程。ByTouchkiss2014-1-193.6.2系统安全状态1.安全状态：是指系统能按某种进程顺序，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。2.银行家算法之例：假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-15T0时刻的资源分配表（1）T0时刻的安全性：图3-16T0时刻的安全序列（2）P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：a)Request1(1,0,2)≤Need1(1,2,2)b)Request1(1,0,2)≤Available1(3,3,