操作系统概念.doc

操作系统：控制和管理计算机系统的软件和硬件资源，合理地组织计算机工作流程及方便用户使用的程序和数据集合。操作系统作为最基本的系统软件；操作系统作为资源管理器；操作系统作为虚拟机1多道程序设计原理：2多道程序设计的硬件支持：中断系统和通道技术。3多道程序设计的实现：多道程序设计的主要目的是充分利用系统的所有资源且尽可能地让他们并行操作。这种技术可把硬件的代价交叉地分布在大量并行用户之间而使计算机系统的代价极小化。优点: 多道程序共享资源,资源利用率高，系统吞吐量大,资源保持忙,系统开销小。缺点: 作业平均周转时间长,无交互能力。1操作系统的功能：1处理机管理；2存储管理；3设备管理；4文件管理；5用户接口。2操作系统的主要特征：1并发性：两个或多个事件在同一时刻发生；2共享性：系统中多个资源可供内存中多个并发执行的进程共同使用，有互斥和同步两种共享方式；3虚拟性：将一个物体影射为若干个逻辑实体；4不确定性：又称异步性,a程序执行结果不确定，程序执行结果不能再现,b多道程序设计环境下，程序按异步方式运行。1操作系统的结构包括1内核，2核外部分，它通常是一些实用程序。1传统的操作系统结构设计模式（针对单处理机）1整体式结构设计模式；2层次式结构设计模式；3、模块化结构设计模式。2现代的操作系统结构设计模式（针对多处理机）1客户/服务器模式2 面向对象技术3对称多处理模式。1操作系统的分类：单用户（微机）操作系统；批处理系统；分时系统；网络操作系统；分布式操作系统；多处理机操作系统。2批处理系统：操作员把用户提交的作业分类，把一批作业编成一个作业执行序列，由专门编制的监督程序(monitor)自动依次处理。为了提高资源利用率和系统吞吐量3批处理系统特点：用户脱机使用计算机、成批处理、多道程序运行。1分时系统：两个或两个以上的事件按时间划分轮流地使用计算机系统的某一资源。在一个计算机系统中如果多个用户分时地使用同一计算机，那么这样的计算机系统就称为分时系统。2. 分时系统的实现原理3.分时系统的特点：1)同时性，若干用户可以同时操作，共同使用统一系统的资源。2)独立性: 用户各占一个终端, 感觉像独占主机；3）及时性: 用户请求能在容许的响应周期内及时获得响应, 响应周期通常在3秒以内；4)交互性: 用户通过终端与系统进行广泛的人机对话, 以请求系统提供多方面的服务。程序顺序执行：程序执行时, 必须按某种先后次序, 只有当前操作完成后才能执行后继操作, 它体现了某种算法。程序的并发执行：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。并发执行是指两个程序的执行在时间上是重叠的。多个程序的并发执行：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。宏观上同时处于运行状态微观上各程序交替地间断运行。资源共享：系统中硬件和软件资源不再为单个用户程序所独占，而由几个用户程序共同使用。程序并发执行和资源共享是现代操作系统的基本特性，它们之间互为依存。并发的特征：1失去了程序的封闭性2程序和机器执行程序的活动不再一一对应3）并发程序间的相互制约.进程：程序的一次执行，该程序可与其它程序并发执行。进程：由程序、数据集合和进程控制块三部分组成。程序部分描述了进程所要完成的功能；数据集合包括程序在执行时所需要的数据和工作区；进程控制块（PCB）：用来描述进程当前状态的数据结构，是进程的动态特性的集中反映。随着进程的创建而产生，进程的撤销而被收。PCB应包含如下一些信息：进程表示名或标示数，位置信息，状态信息 ，进程的优先级，现场保护区，资源清单，队列指针或链接字，进程同步和通信等其它信息。进程的特征：1结构性，由程序+数据+进程控制块组成了进程实体, 称之为进程映像。进程控制块是进程存在的标志；2动态性，进程是进程实体的执行过程, 它由创建而产生, 由调度而执行,因某事件而暂停, 由撤销而消亡。在生命周期内, 进程在三种基本状态之间动态转换；3并发性，多个进程同时存于内存中,一起向前推进,并发执行；4独立性，进程是独立获得资源和独立调度的基本单位；5异步性，各进程都各自独立的不可预知的速度向前推进程序与进程之间的区别：进程更能真实地描述并发，而程序不能；进程是由程序、数据和进程控制块三部分组成的；程序是静态的，进程是动态的；进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的；一个程序可对应多个进程，反之亦然；进程具有创建其他进程的功能，而程序没有。进程的调度状态：1运行状态：进程占有CPU，并在CPU上运行2就绪状态：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）3阻塞状态：指进程因等待某种事件的发生而暂时不能运行的状态 （即使CPU空闲，该进程也不可运行）创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。内核的各项功能是通过执行原语来实现的原语的定义是指若干条机器指令构成的并用以完成特定功能的一段程序，这段程序在执行期间是不可分割的。由以下原语完成：进程创建原语，进程撤消原语，阻塞原语、唤醒原语，挂起原语、激活(解挂)原语进程图是用于描述进程家族关系的有向图，子进程可以继承父进程所拥有的资源。运行程序请求提供服务(如:打印文件),由OS创建 4）运行中进程因自己的需要,由它自己创建子进程进程的创建过程：一旦发现了要求创建新进程的事件,OS便调用创建原语, 按以下过程创建新进程。1）分配一个唯一的进程标识符,索取一个空白PCB2）为新进程的程序和数据分配内存空间3）初始化进程控制块，初始化标识符信息(填入)、处理机的状态信息(指令指针, 栈指针)和控制信息(状态,优先级.)4）设置相应的链接，把新进程加到就绪队列的链表中交通控制程序：主要职能是管理进程状态之间的转变和协调进程间的通讯。大多数的操作系统并未单独设置交通控制程序，而是将其功能分散到各处，以原语或广义指令的面貌出现。进程调度程序：在进程状态变化中，从就绪到运行的转变由有一个专门的程序来完成的，该程序称为进程调度程序。进程调度方式(1)非剥夺方式，在非剥夺方式下, 调度程序一旦把CPU分配给某一进程后便让它一直运行下去, 直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。(2)剥夺方式与非剥夺方式不同，这种方式规定，当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的情况有：优先级策略和时间片策略。显然这种调度方式通常用在分时系统和实时系统中，以便及时响应各进程的请求。进程调度的时机是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下1正在执行的进程正确完成,或由于某种错误而终止运行(陷阱或中断) 2）执行中的进程提出I/O请求, 等待I/O完成时;3)在分时系统中,按照时间片轮转,分给进程的时间片用完时4）按照优先级调度时, 有更高优先级进程变为就绪时(剥夺方式)5）在进程通讯中, 执行中的进程执行了某种原语操作, 如P操作、阻塞原语和唤醒原语时, 都可能引起进程调度。由于共享资源,使得系统中本来没有逻辑关系的进程, 因相互竞争资源而产生了制约关系。这种因共享资源而使并发执行的各进程之间产生的关系,叫做互斥关系（间接制约关系）这种关系可以用进程-资源-进程”来描述。通常, 一个用户作业要涉及一组并发进程(输入、计算和输出进程), 这些进程必须相互协作共同完成这项任务。具体说, 在运行过程中, 某进程可能要在某些同步点上等待另一伙伴(协作进程)为它提供消息, 在未获得消息之前, 该进程处于等待状态, 获得消息后被唤醒进入就绪态, 此后, 才能继续运行。进程之间的这种制约关系叫做直接制约关系,又叫同步关系。这种关系可用“进程-进程”来描述。临界资源(互斥资源)：系统中一次只允许一个进程访问的资源。这些资源既包括I/O设备, 如打印机等资源, 也包括软件资源, 如共享变量、共享文件等。临界区(互斥区):并发执行的进程中, 访问临界资源的必须互斥执行的程序段叫临界区。临界区分散在每个要并发执行的进程中, 它们都对某个共享的数据结构(共享资源)进行访问。通信过程：发送进程在自己的空间里制造一个消息，用发送原语将此消息发送出去；接收进程在自己的空间里开辟一个空间区，利用接收原语将此消息复制到消息队列对首指针指定的接收区信箱通讯，信箱用于存放信件，而信件是一进程发送给另一进程的消息。信箱为接收进程所拥有。信箱的数据结构：信箱名：boxname;信箱大小：boxsize;已存信件数：mesnum，接收进程的私用信号量，初值0；空的格子数：fromnum，发送进程的私用信号量，初值为格子数；用发送和接受原语实现：1）Send(boxname,msg)根据boxname找到信箱；判断信箱是否有空格子p(fromnum)：若有则按第二个参数指出的地址把信件送入该信箱。2）Receive(boxname,msg)1）根据boxname找到信箱；2) 判断信箱中是否有信件P(mesnum)：若有则取出一封信放入按第二个参数给出的进程中。死锁：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程说明:参与死锁的进程最少是两个；参与死锁的进程至少有两个已经占有资源；参与死锁的所有进程都在等待资源。注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。死锁产生的原因1.竞争资源引起2. 进程推进顺序不当引起，对资源采用“申请-分配-使用-释放”模式, 由于推进顺序不当两进程都要申请对方已占有的资源永久性资源:可以被多个进程多次使用(可再用资源)剥夺性资源(CPU、内存） 非剥夺性资源(磁带机、打印机) 争非剥夺性资源会引起死锁临时性资源:只可使用一次的资源； 如信号量,中断信号,同步信号等(可消耗性资源)。竞争临时性资源也会引起死锁产生死锁的四个必要条件1) 互斥条件（资源独占）：一个资源每次只能给一个进程使用；2) 不可剥夺条件（不可强占）：资源申请者不能强行的从资源占有者手中夺取资源, 资源只能由占有者自愿释放 ；3) 请求和保持条件: (部分分配,占有申请)在申请新的资源的同时保持对原有资源的占有。4) 循环等待条件：存在一个进程-等待资源环形链 P1 , P2 , , Pn, 其中P1等待P2占有的资源, P2等待P3占有的资源, , Pn等待P1占有的资源。 对死锁采取的对策：鸵鸟策略，采取不理睬的策略；预防策略，破坏死锁的四必要条件；避免策略，精心地分配资源，动态地回避死锁；检测和解除，一旦发生死锁，及时检测出来，并采取措施解除死锁。死锁的预防，系统设计时确定资源分配算法,保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。1. 破坏“不可剥夺”条件，在允许进程动态申请资源前提下规定, 一个进程在申请新的资源不能立即满足而变为等待状态之前, 必须释放已占有的全部资源, 若需要再重新申请。2.破坏“请求和保持”条件，要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。3.破坏“循环等待”条件，采用资源有序分配法: 把系统中所有资源编号, 进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。4、破坏“互斥性”条件，允许一个资源可由多个进程同时使用。缺点：对有的资源行不通，例如打印机死锁定理：如果资源分配图中没有环路, 则系统中没有死锁, 如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例, 则资源分配图环路是死锁存在的充分必要条件。死锁的解除：一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。死锁的解除(关键是代价最小)：1）重新启动2）撤消进程3）剥夺资源4）进程回退在多道程序环境下,程序要运行必须为之创建进程,而创建进程的第一件事,就是要将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序,通常要经过以下几步1) 编译.由编译程序将用户源代码译成若干个目标模块2) 链接.由链接程序将编译后形成的目标模块以及它们所需要的库函数,链接在一起,形成一个装入模块3) 装入.由装入程序(Loader)将装入模块装入内存。存储管理方案：单一连续分配适用于单道程序；分区分配为满足多道程序设计需要的一种简单的存储管理技术。单一的连续分配思想：单用户系统在一段时间内, 只有一个作业在内存, 故内存分配管理十分简单, 内存利用率低。内存分为两个区域, 一个供操作系统使用, 一个供用户使用。优点：方法简单，易于实现；缺点：仅适用于单道程序，因而不能使处理机和主存得到充分利用分区分配：系统把内存用户区划分为若干分区, 分区大小可以相等, 也可以不等。一个进程占据一个分区。按照分区的划分方式，可分为固定式分区、可变式分区、可再定位式分区和多重分区四种。可变式分区基本思想：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间空白区排列方法对应的算法：1）最佳适应算法：存储区（空白区）的数据结构：空白区按其容量大小递增连接起来，即：X1X2X3. Xn，设请求分配的容量为S，则从X1开始比较，直至SXi，然后，从Xi中减去S，如有剩余，则此空白区插入适当位置，否则（SSn），则分配失败。剩余空白区的处理：如果Xi-SG(参数)，则Xi全部给作业，否则，把Xi-S插入适当位置。特点：用最小空间满足要求，缺点：容易产生许多非常小的空白区（即碎片）2）最差适应算法，空白区按容量递减次序排列。x1=x2=.=xn如果要求分配的容量为S，且x1=S，则分配，否则分配失败。特点：分割后空闲块仍为较大空块。缺点：各空白区比较均匀地减小，工作一段时间后就不能满足对于较大空白区的分配要求3）最先适应算法，空白区按地址大小递增顺序排列特点：简单、快速分配缺点：在低地址部分集中了许多的小空白区，因而在空白区分配时，搜索次数增加，影响了工作效率。固定式分区和可变式分区总结，优点：有助于多道；硬件要求少；算法简单，易于实现。缺点：1、会产生很多碎片，降低了存储器的效率；1、分区大小受主存容量限制，无法扩充主存容量。可再定位分区分配基本思想：定时地根据一定条件将小的空白区合并成一个连续的空白区。解决程序的可再定位（浮动）的方法：1）使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始执行。2）动态再定位技术通过再定位寄存器实现3）合并时机， 当某个分区内的作业一完成，立即靠拢；某一作业请求分区时，现有空白区没有满足的，各空白区之和可以满足，则合并；分配算法(入口参数：申请长度)a.有符合长度要求的空白分区吗？有则进行分配，返回；否则转b。b.内存中空白分区之和能够满足要求吗？是，则转c;否则，给出无法分配的错误信息。c.进行紧凑，转a4）评价优点：消除碎片，便于大作业运行，提高了存储器的使用效率。缺点：提高了成本，降低了速度；紧凑时很浪费时间多重分区分配基本思想：一个作业由一些相对独立的程序段和数据段组成，段内在逻辑上必须是连续的，但相应的各分区却不要求是连续的，给一个作业分配一个以上分区。评价优点：存储空间的利用率提高了缺点：硬件费用高，管理也比较复杂分区的保护措施思想：为防止一个作业有意或无意地破坏操作系统或其他作业，应对各分区采取保护措施，通常采用界地址寄存器（或用基址、限长寄存器）的方法。分区分配方案的评价，优点：1实现了主存的共享，因而有助于多道程序设计，更有效地利用了处理机和I/O设备。2相对分页、分段的存储管理方式，占用存储容量较少，算法简单。3实现存储保护的措施也比较简单。4多重分区分配方案能实现对子程序、数据段的共享。缺点：1主存仍不能充分利用，存在严重的碎片问题。2不能实现对主存的扩充。3和单一连续分配一样，要求一个作业在执行之前必须全部装入主存，因此在主存中可能包含从未使用过的信息。4采用靠拢方法，虽能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。5除多重分区外，几个并发作业之间不能共享存入主存的单一信息副本（如共用子程序，数据段等）。分页原理，目的：解决系统里出现的碎片问题。原理：(1)把目标程序按逻辑地址划分成大小相等的部分, 称为页面(逻辑页)。(2) 把物理地址空间划分成和页面大小相同的片，称为页块。(3) 把主存以块为单位分给用户作业。地址映射：建立页面变换表PMT（简称页表）, 给出逻辑地址页号和内存物理块号对应的关系, 通过它进行地址映射。高速页面变换寄存器，采用高速寄存器实现地址变换。用高速寄存器来存储块号，以完成页号到块号的映射。联想寄存器（快表）它是介于内存与寄存器之间的存储机制, 为加快地址变换速度而设置;它的访问速度比页表快一个数量级, 它保存着正在运行进程的页表的子集(部分表项)。实现上采用“双管齐下”的方法。存放。当前频繁访问的那些页表项,表项含:1) 页号2) 页在内存的块号3) 标识(状态)位4) 淘汰位分页存储管理方案的评价1、采用动态地址变换会增加计算机成本和降低处理机的速度；2、各种表格要占用一定容量的主存空间，同时要花费一部分处理机时间来建立和管理表格；3、作业的最后一页一般都有不能充分利用的空白区；4、存储扩充问题仍未得到解决。抖动：在虚存中, 页面在内存与外存之间频繁调度, 以至于调度页面所需时间比进程实际运行的时间还多, 此时系统效率急剧下降, 甚至导致系统崩溃, 这种现象为抖动。产生原因：页面淘汰算法不合理；分配给进程的工作集窗口尺寸太小。页面置换算法1、先进先出算法（FIFO）基本思想：总是淘汰那些驻留在主存时间最长的页面。思想基础：最先调入主存的页面比最近调入主存的页面不再访问的可能性大。缺点：没有考虑访问频度的差别, 不能保证经常访问的页不被淘汰。 2、最近最久未用置换算法（LRU）思想：如果某一页被访问了，可能马上还要被访问；长时间不被访问的页，最近也不会访问。实现：（1）对每一个存储块增加一个引用位，当这一页被访问时，引用位由硬件置“1”；（2）给存储块再增加一个数据项，记录每一页从上次被访问以来的时间t；（3）淘汰时选择被访问以来时间最长的页淘汰。评价 ：常用的页不容易被置换出去，适用于各种类型程序；周期t过一段时间被计算一次，耽误时间，增加成本。3、LRU近似算法实现：给存储分块表MBT增加一个引用位，当这一页被访问时，引用位由硬件置“1”；管理软件周期性地将引用位逐个置“0”；淘汰时选择引用位为0的页淘汰，碰到引用位为1的，置为0。评价：比LRU算法简单；周期选择困难。4、其它算法随机算法（RAND)、近期最少使用算法（LFU）、最优替换算法（OPT）等内存物理空间的划分：内存空间被动态的划分为若干个长度不相同的物理段, 每个物理段由起始地址和长度确定。内存分配：以段为单位分配内存, 每个段在内存中占据连续空间(内存随机分割, 需要多少分配多少), 但各段之间可以不连续存放。分页和分段的主要区别1页是物理单位, 分页是为了消减内存的外零头以提高内存的利用率, 仅仅是系统的需要。段是逻辑单位, 分段是为了更好地满足用户需要。2.页的大小固定且由系统确定, 分页由硬件实现。段的长度不固定, 由编译时根据程序信息来划分。3分页的作业地址空间是一维的线性空间。标识地址时, 只需给出一个逻辑地址。分段的作业地址空间是二维的, 标识地址时, 必须给出段名和段内地址。分段存储管理方案的评价1、优点消除了碎片；提供了大容量的虚存；允许动态增加段的长度；便于动态装入和链接；可以实现若干作业共享主存；便于实现存储保护。2、缺点进行地址变换和实现靠拢要花费处理机时间，为管理各分段，要设立若干表格，提供附加的存储空间；在辅存上管理可变长度的段比较困难；段的最大长度受到实存容量的限制；会出现系统抖动现象。段页式存储管理基本思想：用户程序划分: 按段式划分(对用户来讲, 按段的逻辑关系进行划分; 对系统讲, 按页划分每一段)逻辑地址：处理机给出的有效地址被分成了三部分：段号、页号和页内地址。内存划分：按页式存储管理方案内存分配：以页为单位进行分配文件：一组带标识的在逻辑上有完整意义的信息项的序列，这个标识为文件名。通常由记录组成。信息项：构成文件内容的基本单位；长度：单个字节，或多个字节；文件内容的意义：由文件的建立者和使用者解释。文件是一个抽象机制，它提供了一种把信息保存在存储介质上，而且便于以后存取的方法，用户不必关心实现细节。文件系统定义：是操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。组成：与文件管理有关的软件、被管理的文件及实施文件管理所需的数据结构文件系统的功能(1)统一管理文件的存储空间，实施存储空间的分配与回收(2)实现文件的按名存取：名字空间 映射 存储空间(3)实现文件信息的共享，并提供文件的保护和保密措施(4)向用户提供一个方便使用的接口（提供对文件系统操作命令，以及提供对文件的操作命令：信息存取、加工等）(5)系统维护及向用户提供有关信息(6)文件系统的执行效率，文件系统在操作系统接口中占的比例最大,用户使用操作系统的感觉在很大程度上取决于对文件系统的使用效果.(7)提供与I/O的统一接口文件的分类1按文件性质和用途分类，系统文件： 有关OS及有关系统所组成文件，用户文件：受用户委托提供的信息，库文件：标准子程序及常用应用程序组成文件，允许用户使用但不能修改2.按信息保存期限分类，临时文件；永久文件；档案文件3.按文件的保护方式分类。只读文件；读写文件；不保护文件；可执行文件4.按文件的逻辑结构分类。流式文件；记录式文件，按文件的物理结构分类，顺序（连续）文件；链接文件；索引文件6.UNIX系统将文件分为三类 普通文件；目录文件；特殊文件（设备文件，把外部设备也看作文件）普通文件(regular)：包含的是用户的信息，一般为ASCII或二进制文件目录文件(directory)：管理文件系统的系统文件特殊文件(special file) 字符设备文件：和输入输出有关，用于模仿串行I/O设备，例如终端，打印机，网络等 块设备文件：模仿磁盘文件的逻辑结构从用户角度看文件，研究文件的组织形式1.流式文件：构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合。文件：一个无结构字节序列好处：提供很大的灵活性2.记录文件：文件是由若干个记录组成，每个记录有一个键，可按键进行查找。记录式文件是有结构的文件。文件：一个固定长度记录的序列，每条记录有其内部结构文件的物理结构是从系统的角度来看文件，从文件在物理介质上的存放方式来研究文件1. 连续结构（顺序）一个文件的信息存放在若干连续的物理块中。优点: 简单 、支持顺序存取和随机存取， 顺序存取速度快，所需的磁盘寻道次数和寻道时间最少缺点: A 文件不能动态增长，预留空间:浪费B 不利于文件插入和删除C 外部碎片问题文件存取方式1顺序存取方式在记录式文件系统中，按照物理记录排列的次序依次存取。分类：固定长和可变长2、随机(直接)存取方式记录按序排列，读取时直接取到某个记录。用户一般给出的是文件名和记录号。3、按键存取法：按键进行存取。文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合空闲块表 (类似于分区管理方式） 将所有空闲块记录在一个表中，即空闲块表评价：效率低、仅适合连续文件； 必须预先知道文件的大小。2. 空闲块链表