操作系统复习

操作系统的主要功能从资源管理观点看，操作系统具有五大功能：处理机管理存储器管理设备管理文件管理作业管理1.处理机管理主要任务：是对处理机的分配和运行实施有效管理。对处理机管理，可归结为对进程的管理。进程管理的主要功能进程控制：当用户作业要运行时，应为之建立一个或多个进程，并为它分配除处理机以外的所有资源，将它放入进程就绪队列。当进程运行完成时，立即撤消该进程，以便及时释放其所占有的资源。进程控制的基本功能就是创建和撤消进程以及控制进程的状态转换。进程同步：所谓进程同步是指系统对并发执行的进程进行协调。最基本的进程同步方式是使诸进程以互斥方式访问临界资源。此外，对于彼此相互合作、去完成共同任务的诸进程，则应由系统对它们的运行速度加以协调。进程通信：对于相互合作的进程，在它们运行时，相互之间往往要交换一定的信息，这种进程间所进行的信息交换称为进程通信。进程调度：当一个正在执行的进程已经完成，或因某事件而无法继续执行时，系统应进行进程调度，重新分配处理机。进程调度是指按一定算法，如最高优先算法，从进程就绪队列中选出一进程，把处理机分配给它，为该进程设置运行现场，并使之投入运行。2.存储器管理存储器管理的主要任务:为多道程序的并发运行提供良好环境；便于用户使用存储器；提高存储器的利用率；为尽量多的用户提供足够大的存储空间。存储器管理的功能内存分配：多道程序能并发执行的首要条件是，各道程序都有自己的内存空间，因此，为每道程序分配内存是存储器管理的最基本功能。内存保护：为保证各道程序都能在自己的内存空间运行而互不干扰，要求每道程序在执行时能随时检查对内存的所有访问是否合法。必须防止因一道程序的错误而扰乱了其它程序，尤其应防止用户程序侵犯操作系统的内存区。地址映射：在多道程序的系统中，操作系统必须提供把程序地址空间中的逻辑地址转换为内存空间对应的物理地址的功能。地址映射功能可使用户不必过问物理存储空间的分配细节，从而为用户编程提供了方便。内存扩充：由于物理内存的大小可能限制了大型作业或多个作业的并发执行，为了满足用户的要求并改善系统性能，必须对内存加以扩充。但我们无须去真正地增加内存空间，而只须借助于虚拟存贮技术，便可获得这样地效果，使系统能运行内存要求量远比物理内存大得多得作业，或让更多得作业并发执行。

3.设备管理1)设备管理的主要任务:为用户程序分配I/O设备；完成用户程序请求的I/O操作；提高CPU和I/O设备的利用率；改善人机界面。2)设备管理程序应具有的功能缓冲管理：几乎所有的外围设备于处理机交换信息时，都要利用缓冲来缓和CPU和I/O设备间速度不匹配的矛盾，和提高CPU与设备、设备与设备间操作的并行程度，以提高CPU和I/O设备的利用率。设备分配：系统根据用户所请求的设备类型和所采用的分配算法对设备进行分配，并将未获得所需设备的进程放进相应设备的等待队列。设备处理：启动指定的I/O设备，完成用户规定的I/O操作，并对由设备发来的中断请求进行及时响应，根据中断类型进行相应的处理。虚拟设备功能：通常，把一次仅允许一个进程使用的设备称为独占设备。系统可通过某种技术使该设备成为能被多个用户共享的设备，以提高设备利用率及加速程序的执行过程。可使每个用户都感觉到自己在独占该设备。4.文件管理文件存储空间的管理目录管理文件读、写管理文件保护向用户提供接口5.作业管理1）作业管理的主要任务:是根据系统条件和用户需要，对作业的运行进行合理的组织、调度及相应的控制。2）作业调度：作业调度是指根据系统的能力和当前作业的运行情况，按一定策略，从后备作业队列中选出一批作业，为它们分配所需的I/O设备和存储空间，将它们调入内存并为之建立相应的进程，使之成为具有获得处理机资格的侯选进程。3）作业控制：作业控制是指作业从进入系统开始，直到运行完成的整个过程中，用户可通过某种形式向系统发出各种命令，以对自己的作业进行控制和管理。───────────────────────────────────────进程状态转换条件在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：就绪-->运行系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的进程控制块的内容进程标识符：标识一个进程的编号，也称为进程的内部名；现性状态：说明进程的当前状态；现场保留区：保存进程由执行状态变为其它状态时的CPU现场信息；程序与数据地址：该进程的程序和数据所在位置信息；互斥与同步机构：实现进程间互斥与同步时所必须的机构；进程通信机制：用于实现进程间的通信所需的数据结构；优先级：表示进程使用CPU时优先级别的一个整数；资源清单：列出进程拥有的资源的记录；连接字：给出本进程所在队列中的下一个进程的PCB首址；家族联系：用于说明本进程与其它家族成员间的关系。进程映象(进程要素)用户程序用户数据栈用于过程调用和参数传递进程控制块PCB(执行上下文)控制进程所需的数据(进程属性)，包括:进程标识符信息处理器状态信息进程控制信息进程控制块的组织方式为了有效地对进程控制块进行管理，应该采用适当的方式把它们组织起来。目前常用的组织方式有以下两种：按链接方式组织PCB(队列)不同状态进程分别组成队列 运行队列、就绪队列、等待队列按索引方式组织PCB(表)对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址（其他方式：线性表或链表）为什么要线程的引入在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度信号量的物理含义：信号量S＞0时，S的数值表示某类可用资源的数目，执行P操作意味着申请分配一个单位的资源；当S≤0时，表示无资源可用，此时S的绝对值表示信号量S的阻塞队列中的进程数。执行V操作意味着释放一个单位的资源。S>0表示有S个资源可用S=0表示无资源可用S<0则|S|表示S等待队列中的进程个数P(S):表示申请一个资源V(S)表示释放一个资源。信号量的初值应该大于等于0───────────────────────────────────────处理机调度的基本概念在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。分时系统和实时系统的区别。各有什么特点？各自采用什么调度算法？分时系统:时间片轮转调度算法实时系统:在实时系统中,硬实时任务和軟实時任務都聯系着一個截止時間.1)非抢占式调度算法:非抢占式轮转调度算法非抢占式优先调度算法2)抢占式调度算法:基于时钟中断的抢占优先调度算法立即抢占优先权调度算法。周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待响应比:(等待時間+要求服務時間)/要求服務時間产生死锁的原因1.竞争系统资源2.进程的推进顺序不当产生死锁的必要条件互斥条件（资源独占）请求和保持条件（部分分配，占有申请）不剥夺条件（不可强占）环路等待条件。预防死锁的方法破坏产生死锁的四个必要条件之一1)资源一次性分配；(破坏请求和保持条件)2)可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源(破坏不可剥夺条件)3)资源有序分配法；做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反(破坏环路等待条件)

死锁避免死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。死锁的解除重要的是以最小的代价恢复系统的运行。方法如下：1）重新启动2）撤消进程3）剥夺资源4）进程回退───────────────────────────────────────虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换.虚拟存储器支持多道程序设计技术虚拟存储器具有请求调入功能和自换功能,能从逻辑上对内存容量进行扩充的存储器系统。虚拟存储器就是一个地址空间，且具有比实存大得多的容量。对用户：指令地址部分所限定的比实存大得多的地址实间。对系统：借助于各种表格机构，体现虚拟实间。虚拟存储器的容量一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址长度为32位，则程序可以寻址范围是0～(2^32)-1，即虚存容量为4GB。虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。页面置换算法 当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。最佳置换算法先进先出置换算法最近最久未用置换算法近似的LRU算法（NRU算法）最佳置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。先进先出(FIFO)页面置换算法 置换时选择在内存中驻留时间最长的页并淘汰之最近最久未使用(LRU)置换算法选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高（时间戳或硬件方法）LRU置换算法的硬件支持1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为:R=Rn-1Rn-2Rn-3…R2R1R02)栈改进型Clock置换算法由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。其执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。其它置换算法最少使用(LFU：LeastFrequentlyUsed)置换算法 2.页面缓冲算法(PBA：PageBufferingAlgorithm)───────────────────────────────────────与设备无关性（设备独立性）用户在编制程序时，使用逻辑设备名，由系统实现从逻辑设备到物理设备的转换用户能独立于具体物理设备而方便的使用设备用户申请使用设备时，只需要指定设备类型，而无须指定具体物理设备，系统根据当前的请求，及设备分配的情况，在相同类别设备中，选择一个空闲设备，并将其分配给一个申请进程引入缓冲技术

1.緩和CPU與I/O設備間速度不匹配的矛盾.2.减少對CPU的中斷頻率,放寬對CPU中斷响應時間的限制.3.提高CPU和I/O設備之間并行性.磁盘查找算法1.(First-Come,FirstServed)FCFS调度算法2.最短寻道时间优先SSTF(ShortestSeekTimeFirst)3.扫描(SCAN)算法 优先考虑磁頭當前的移動方向,在移動方向上沒有更外的的磁道需要訪問時,才輚換磁臂的移動方向4.循环扫描(CSCAN)算法 磁頭單向移動,當磁頭到最外的磁首并訪問後,磁頭立即返回到最里的欲訪問的磁道.5.N-Step-SCAN和FSCAN调度算法 N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一