操作系统原理

操作系统原理A进程管理1进程的定义人们在使用计算机来完成各自所要求的功能时，总是使用“程序”这个概念。程序是一个在时间上严格次序前后相继的操作序列，是一个静态的概念。显然，一个程序只有经过执行才能得到最终的结果，而且一般用户在编写程序时不考虑在自己的程序执行过程中还有其他用户程序存在这个事实。程序的执行分为两种：顺序执行和并发执行。我们把一个具有独立功能的程序独占处理机知道最终结束的过程称为程序的顺序执行。顺序执行的特点是：1,顺序性。2,封闭性。3,可再现性。我们把一组在逻辑上相互独立的程序或者程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的方式称为并发执行。1966年Bernstein提出了并发执行的充分条件：①R(S1)CW(S2)=®②W(S1)CR(S2)二®③W(S1)CW(S2)=｛势。进程，即是一个具有一定独立功能的程序对某个数据集合在处理机上的执行过程和分配资源的基本单位。相对于程序来说，进程是一个动态的概念，具有并发特征，而且不同的进程可以包含同一个程序。进程的描述进程控制块PCB：包含了进程的描述信息、控制信息及资源信息，是进程动态特征的集中反映。通过对PCB的操作，系统为有关进程分配资源从而使得有关进程得以被调度执行；与进程有关的所有现场信息都保存在PCB中；进程执行结束后，OS通过释放PCB释放进程占有的资源。进程的上下文实际上是进程执行活动全过程的静态描述。具体的说，进程上下文包括计算机系统中与执行该进程有关的各种寄存器的值以及正文集、数据集、堆栈值和PCB结构。一个进程的生命期可以划分为一组状态，这些状态刻画了整个进程。进程的三个基本状态为：就绪状态、执行状态和等待状态。进程的状态转化时一个非常复杂的过程。从一个状态到另一个状态的转化除了要使用不同的控制过程，有时还要借助硬件触发器才能完成。PV原语实现互斥和同步在计算机中由于资源有限，就会导致进程之间的资源竞争和共享。临界区就是不允许多个并发进程交叉执行的一段程序。由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象称为间接制约。所以，为了解决并发进程对资源的竞争问题，一种方法就是对临界区加锁以实现互斥。当某个进程进入临界区后，它将锁上临界区，直到它退出临界区为止。并发进程在申请进入临界区时，首先测试改临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得该临界区。这就是互斥的加锁实现。但是，加锁实现互斥时会产生不公平现象。为了解决这个问题，荷兰学科学家E.W.Dijkstra提出了信号量(sem)和P.V原语的概念。信号量sem是一个整数，代表的是资源的个数。P原语操作使得信号量sen减1，而一次V操作将使得信号量sem加1。除了并发进程执行过程中因竞争公共资源而产生制约之外，还存在因为并发进程相互共享对方的私有资源所引起的制约，称为直接制约。进程的通信方式Hansen在1973年首先提出了用消息缓冲作为进程通信的一种基本方式。发送进程在发送消息之前，现在自己的内存空间设置一个发送区，把欲发送的消息填入其中，然后再用发送过程将其发送出去。接收进程则是在接收消息之前，在自己的的内存空间中设置相应的接收区，然后用接收过程接收消息。进程的另一个通信实例就是管道，管道一般按照FIFO方式传送消息，且只能单向传送消息。死锁死锁是指各并发进程彼此相互等待对方所拥有的资源，而且这些并发进程在得到对方资源之前不会释放自己所拥有的资源。产生死锁的条件是：1.互斥条件。2.不剥夺条件.3.部分分配条件4.环路条件。解决死锁的方法是限制并发进程对资源的请求或者通过外力破坏死锁发生的条件。一般而言,由于操作系统的并行与共享以及随机性等特点通过预防和避免的手段达到排除死锁的目的是一件困难的事情.这需要较大的系统开销，甚至不能充分利用资源.相反，死锁的检测和恢复则与此相反，不必花费多少执行时间就能发现死锁.因此，在实际操作系统中大都使用检测和恢复排除死锁.进程是指在系统中正在运行的一个应用程序；线程是系统分配处理器时间资源的基本单元，或者说进程之内独立执行的一个单元。对于操作系统而言，其调度单元是线程。一个进程至少包括一个线程，通常将该线程称为主线程。一个进程从主线程的执行开始进而创建一个或多个附加线程，就是所谓基于多线程的多任务。那进程与线程的区别到底是什么？进程是执行程序的实例。例如，当你运行记事本程序(Nodepad)时，你就创建了一个用来容纳组成Notepad.exe的代码及其所需调用动态链接库的进程。每个进程均运行在其专用且受保护的地址空间内。因此，如果你同时运行记事本的两个拷贝，该程序正在使用的数据在各自实例中是彼此独立的。在记事本的一个拷贝中将无法看到该程序的第二个实例打开的数据处理机的调度作业调度一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成4个状态。作业调度主要是完成作业从后备状态到执行状态的转化，以及从执行状态到完成状态的转变。衡量调度的性能一般依据4点：1.对所有作业时公平合理的。2.使设备又高的利用率。3.每天尽可能执行多的作业。4.有很快的响应时间。进程调度进度的调度实质是一个进程上下文切换的过程。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。进程调度原因有：1.正在执行的进程执行完毕.2.执行中进程提出I/O请求后被阻塞.3.在分时系统中时间片已经用完.常用的调度算法有：1.先来先服务(FCFS)调度算法。2.轮转法(roundrobin)。3.多级反馈轮转法(roundrobinwithmultiplefeedback)。4.优先级法。5.最短作业优先法(shortestjobfirst)。最高响应比优先法(highestresponse_rationext)。先来先服务是将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行处理调度。轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。优先级方法的核心是确定进程或作业的优先级，然后根据优先级依次调度。最短作业优先法就是选择那些执行时间最短的作业投入执行，为它们创建进程和分配资源。HRN是对FCFS方式和SJF方式的一种综合平衡。因为FCFS方式未考虑执行时间的长短，SJF方式未考虑等待时间的长短。作业调度和进程调度之间的一个基本的区别是它们执行的频率不同。进程调度必须相当频繁地为CPU选择进程。一个进程在等待I/O请求之前仅仅执行几个毫秒，因而进程调度可能每10ms执行一次。由于执行期间很短，所以，进程调度必须非常快。如果进程调度程序运行时间占1ms，挑选的进程运行10ms，那么有1/(10+1)聂的CPU时间用于这种简单的调度工作。另一方面，作业调度执行的次数很少，新作业到达系统的间隔可以是几分钟。作业调度控制着程序的道数(即内存中进程的数目)。如果系统中作业道数保持不变，那么进入系统的作业的平均到达速率就一定等于离开系统的作业的平均离去速率。这样，仅当有作业离开该系统时才需要调用作业调度程序。因为执行它的时间间隔较长，所以，作业，作业调度完全可以花费较多时间去决定哪个作业将被选去执行。在某些方面系统中没有作业调度，或者即使有也很小。例如，在分时系统中往往没有作业调度程序，而是简单地把每个新进程装入内存，供进程调度程序使用。这种系统的稳定性既取决于物理上的限制(如可用终端的数目)，又取决于用户自身调节的性质。如果性能变得太差了，某些用户则应退出系统，去干其它事情。作业调度为进程活动做准备，进程调度使进程活动起来•作业调度次数少，进程调度频率高•有的系统不设作业调度，但进程调度必不可少。存储管理存储器由内存(primarystorage)和外存(secondarystorage)组成。内存由顺序编址的块组成，每块包含相应的物理单元。虚拟存储器(virtualmemory)是存储器管理的核心概念。它不考虑物理存储器的大小和信息存放的实际位置，只规定每个进程中相互关联的信息的相对位置。分区存储管理分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区，以连续存储各进程的程序和数据，使各进程得以并发执行。按分区管理可以分为固定分区法和动态分区两种：固定分区法固定分区法就是把内存区固定地划分为若干大小不等的区域，分区划分的原则由一般系统操作员或操作系统决定。例如可划分为长作业分区和短作业分区。分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。动态分区法与固定分区法相比，动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。c.分区算法动态分区时有3种分配方法：最先适应法、最佳适应算法、最坏适应算法；最先适应算法要求可用表或自由链按起始地址递增的次序排列。该算法最大特点是找到大于或等于内存长度的分区，则结束探索。最佳适应算法要求从小到大的次序组成空闲区可用表或自由链。当用户作业或进程申请一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求空闲区时，停止查找。最坏适应算法要求空闲区按其大小的次序组成空闲区可用表或自由链。此外，在分区管理中还经常用到的两种技术是覆盖和交换技术。覆盖技术主要用在早期的操作系统中，而交换技术则在现代操作系统中仍具有较强的生命力。覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时运行的程序段共享同一块内存区域。程序段先保存在磁盘上，当有关程序的前一部分执行结束后，把后续程序段调入内存，覆盖前面的程序段。交换技术：在分时系统中，用户的进程比内存能容纳的数量更多，系统将那些不再运行的进程或某一部分调出内存，暂时放在外存上的一个后备存储区，通常称为交换区，当需要运行这些进程时，再将它们装入内存。页式管理基本原理页式管理的基本原理如下：首先，各进程虚拟空间被划分成若干个长度相等的页。页长的划分和内存外存之间数据传输速度以及内存大小有关。再者，页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理。内存内只存放那些经常被执行的页，那些不常被执行的页则被存放在外存中等待需要时调入。静态页面管理静态页面管理方法在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装入内存的各个页面中，并通过页表(pagemappingtable)和硬件地址变换机构实现虚拟地址到内存物理地址的地址映射。动态页式管理算法动态页式管理是在静态页式管理的基础上发展起来的。请求页式管理和预调入页式管理在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。页式管理中的置换算法有：随机淘汰算法(randomglongram)、轮转法(roundrobin)、最近最久未使用页面置换算法(leastrecentlyused)、理想型淘汰算法(optimalreplacementalgorithm)随机淘汰算法(randomglongram):在系统设计人员认为无法确定哪些页面被访问的概率较低时，随机地选择某个用户的页面并将其换出将是一种明智的作法。轮转法(roundrobin)：轮转法循回换出内存可用区内一个可以被换出的页，无论该页是刚被换进或一换进内存很长时间。最近最久未使用页面置换算法(leastrecentlyused)：该算法的基本思想是：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页最先淘汰。理想型淘汰算法(optimalreplacementalgorithm)：该算法淘汰在访问串中将来再也不出现的或是在离当前最远的位置上出现的页。段式和段页式管理在分区存储管理和页式存储管理中，供用户使用的逻辑地址都是连续的。在有些情况下如用户在编制大型程序时就会感到不便利，因为用户希望他们程序是由若干段组成的，可以由一个主程序、若干子程序、符号表、栈以及数据等等若干段组成。每一段都有完整的逻辑意义，每一段的程序都可独立编制，且每一段的长度可以不同。采用段式存储管理方案就可以支持程序的分段使用。段式管理段式管理是基于为用户提供一个方便灵活的程序设计环境而提出来的。段式管理的基本思想是：把程序按内容或过程(函数)关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。在段式存储管理中，每个段地址的说明为两个量：一个段名和一个位移。在段内，是连续完整存放的。而在段与段之间是不一定连续编址的。段名和位移构成了一种二维编址。段式管理是不连续分配内存技术中的一种。其最大特点在于他按照用户观点，即按程序段、数据段等有明确逻辑含义的"段”，分配内存空间。克服了页式的、硬性的、非逻辑划分给保护和共享与支态伸缩带来的不自然性。段的最大好处是可以充分实现共享和保护，便于动态申请内存，管理和使用统一化，便于动态链接；其缺点是有碎片问题段页式管理分页式存储管理的基本思想是：用段式方法对用户程序按照在的逻辑关系划分成若干段，每段的逻辑地址仍是从“0”开始的一组连续地址。用页工方法来分配和管理内存空间，即把内存划分为若干大小相等的页面。在具体分厂空间时，不再为每一段分配一个连续的主存空间，而是把每段分成若干页面，从而把一段的信息分页存放。这些页面显然是分布在不必相邻的空闲主存块中。采用段页式存储管理方案时，具有独立逻辑功能的程序或数据仍被划分为段，并有各自的段号，这反映和继承了段式管理的特征。对于段中的程序或数据，则按照一定的大小将其划分为不同的页，最后不足一页的部分仍占一南，这反映了段页式管理中的页式特征。由于内存空间的最小单位是页，而不是段，从而内存可用区也就被划分成为若干个大小相等的页面，且每段所拥有的程序和数据在内存中可以分开存放。分段的大小也不再受内存可用区的限制。段页式管理的基本思想是把段式管理和页式管理结合起来让其互相取长补短。不过，由于段式管理和页式管理都需要较大的系统开销，可以预计到段页式管理的开销会更大。因此，段页式管理一般只用在大型机系统中。抖动问题局部性原理(principleoflocality):指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：时间局部性，即一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；空间局部性，即当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。任何程序在局部性放入时，都有一个临界值要求。当内存分配小于这个临界值时，内存和外存之间的交换领率将会急剧增加，而内存分配大干这个临界值时，再增加内存分配也不能显著减少交换次数。这个内存要求的临界值被称为工作集。当给进程分配的内存小时，由于内存外存之间交换频繁，访问外存时间和输入/输出处理时间大大增加，反而造成CPU因等待数据空转，使得整个系统性能大大下降，这就造成了系统抖动。文件管理文件逻辑结构文件的逻辑结构是用户可见结构。文件的逻辑结构可分为两大类：字符流式的无结构文件和记录式的有结构文件。对于字符流式的无结构文件来说，查找文件中的基本信息单位，例如某个单词，是比较困难的。但反过来，字符流的无结构文件管理简单，用户可以方便地对其进行操作。记录式的有结构文件可把文件中的记录按各种不同的方式排列，构成不同的逻辑结构，以便用户对文件中的记录进行修改、追加、查找和管理等操作。常用的记录式结构有连续结构，多重结构(multi_list)，转置结构(invertedfile)和顺序结构。连续结构是一种把记录按生成的先后顺序连续排列的逻辑结构。其特点是适用性强，可用用于所有文件。多重结构是把记录名和键排列成行列式结构。转置结构把含有相同键的记录指针全部指向该键。顺序结构是根据给定的顺序规定，把文件中的键按规定的顺序排列起来。用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。常用的存取方法有：顺序存取法、随机存取法、按键存取法顺序存取是按照文件的逻辑地址顺序存取。随机存取法允许用户根据记录的编号来存取文件的任一记录，或是根据存取命令把读写指针移到欲读写处读写。按键存取法是一种用在复杂文件系统，特别是数据库管理系统在的存取方法。文件物理结构文件系统往往根据存储设备类型、存取要求、记录使用频度和存储空间容量等因素提供若干种文件存储结构。用户看到的是逻辑文件，处理的是逻辑记录，按照逻辑文件形式去存储，检索和加工有关的文件信息，也就是说数据的逻辑结构和组织是面向应用程序的。然而，这种逻辑上的文件总得以不同方式保存到物理存储设备的存储介质上去，所以，文件的物理结构和组织是指逻辑文件在物理存储空间中存放方法和组织关系。文件的物理结构是指文件在存储设备是的存放方法：常用的文件物理结构有：连续文件、串联文件和索引文件.连续文件是一种最简单的物理文件结构，它把一个在逻辑上连续的文件信息依次存放到物理中。优点是：1.简单；支持顺序存取和随机存取；顺序存取速度快；所需的磁盘寻道次数和寻道时间最少缺点是：1.建立文件前需要能预先确定文件长度，以便分配存储空间;修改、插入和增生文件记录有困难；对直接存储器作连续分配，会造成少量空闲块的浪费。串联文件结构用非连续的物理块来存放文件信息。这些非连续的物理块之间没有顺序关系，其中每个物理块设有一个指针，指向其后续连接的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。优点是：1.提高了磁盘空间利用率，不存在外部碎片问题.有利于文件插入和删除.有利于文件动态扩充缺点是：1.存取速度慢，不适于随机存取.可靠性问题，如指针出错.更多的寻道次数和寻道时间.链接指针占用一定的空间.索引结构要求系统为每个文件建立一张索引表，表中每一栏目指出文件信息所在的逻辑块号和与之对应的物理块号。优点是：1.即能顺序存取,又能随机存取.2.满足了文件动态增长、插入删除的要求.缺点是：索引表本身带来了系统开销如：内外存空间，存取时间.存储空间管理存储空间管理是文件系统的重要任务之一。只有有效地运行存储空间管理，才能保证多个用户共享文件存储设备，同时得以实现文件的按名字存取。由于文件存储设备是分成若干个大小相等的物理块，并以块为单位来交换信息的，因此，文件存储空间的管理实质上是一个空闲块的组织和管理问题，它包括空闲块的组织，空闲块的分配与空闲块的回收等问题。空闲块管理方法有三种：第一个方法是空闲文件目录，空闲方法就是把文件存储设备中的空闲块的块号统一放在一个物理块中。第二个方法是空闲块链方法，即把所有空闲块链接在一起，当申请者需要空闲块时，分配程序从链头开始摘取空闲块。另外一个常用方法的是位示图。系统为每个文件存储建立一张位示图，图中的‘0’位代表可用，‘1’位代表不可用。文件目录可分为单级目录、二级目录和多级目录。单级目录是一种最简单、最原始的目录结构。文件系统为存储设备的所有文件建立一张目录表，每个文件在其中占有一项用来存放文件说明信息。在二级目录中，各个文件的说明信息被组织成目录文件，而且以用户为单位把各自的文件说明划分为不同组。把二级目录的层次关系加以推广，就形成了多级目录。在多级目录中，除了最低一级的物理块中装有文件信息外，其他每一级目录中存放的都是下一级目录的说明信息。文件管理师操作系统的五大职能之一，主要涉及文件的逻辑组织和物理组织，目录的结构和管理。文件管理是操作系统中一项重要的功能。其重要性在于，在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。可以说，尽管文件有多种存储介质可以使用，如硬盘、软盘，光盘，闪存，记忆棒等等，但是，它们都以文件的形式出现在操作系统的管理者和用户面前。设备管理1.控制数据传送在计算机系统中，除了CPU和内存之外，其他的大部分硬件设备为外部设备。设备管理的主要任务就是控制设备和内存或CPU之间的数据传送，而且尽量做到使得I/O设备尽量忙，而CPU等待时间少。常用数据传送控制方式有以下四种：程序直接控制方式(programmeddirectcontrol)就是由用户进程来直接控制内存或CPU和外围设备之间的信息传送。中断(interrupt)方式能更好的减少CPU等待时间，以及提高系统的并行工作程度。DMA(directmemoryaccess)方式是在外围设备和内存之间开辟直接的数据交通道路。通道控制(channelcontrol)方式是一种以内存为中心，实现设备和内存直接交换数据的控制方式。中断技术中断(interrupt)只指计算机在执行期间，系统内发生急需处理事件，使得CPU暂时中断当前程序，呆处理完毕后，又返回或者调度新的进程执行的过程。根据系统对中断处理的需要，操作系统一般对中断进行分类。不同的中断同时发生时，会按照轻重缓急进行处理。外中断主要指在处理机和内存外部发生的中断。外中断在狭义上一般称为中断。内中断指在处理机和内存内部发生的中断。内中断一般称为陷阱(trap)。软中断是通信进程之间用来模拟硬中断的一种信号通信方式。我们可以通过例子，来了解中断技术的重要性。假设有一个朋友来拜访你，但是由于不知何时到达，你只能在门口等待，于是什么事情也干不了；但如果在门口装一个门铃，你就不必在门口等待而可以在家里去做其他的工作，朋友来了按门铃通知你，这时你才中断手中的工作去开门，这就避免了不必要的等待。而计算机也一样，例如打印文稿的操作。因为cpu传送数据的速度高，而打印机速度较慢，如果不采用中断技术，cpu将经常处于等待状态，这会使得电脑的工作效率极低。而采用了中断方式后，cpu就可以在打印的同时进行其他的工作