理工类专业课复习资料-操作系统期末复习资料(知识点汇总)

开放性理计算机系统资源、实现对计算机资源的抽象式、单道批处理系统、多道批处理系统、分时系统、实顺序性：各道作业是顺序进入内存，顺序完成操作(类似队列)行成一个队列，称为后备队列；之后，由作业调度程序按一定的算法从后备队列中选择若干作业调入内存，共享CPU和系统资源。资源利用率高、系统吞吐量(单位时间内完成的总工作量)大、平均周转时间(从作业进入系统，到完成并退出系统为止的时间)长，缺点在于无交互能力。O题，引入分时系统，可以将一台计算机提供给多个用个终端较短时间内相应时间内完成对该事件的处理，并控制所有实时序。多用户多任务利用进程的资源。进程是分配资源的基本单位，线程1度必然小于等于1/N。类似，空分复用实现虚拟，空间利用也小于等于1/N。进程，撤销结束的进程，以及控制进程的状态转换互斥、进程同步两种方式干作业调入内存，为其建立进程，使之成为就需进程，并间辑地址转换为内存空间的物理地址设备分配：根据用户进程的I/O请求，为之分配所需设备。设备处理：实现CPU与设备控制器之间的通信分配外存空间设计分为若干子功能，每个子功能为一个模块，再进一步细分，使若干层，每层由若干模块组成。各层之间只存在单向息，客户机接受消息。此种模式实现了数据的分布存储，便于2个操作完成后开始全部资源，不受外界影响初始条件相同，当程序重复执行时，结果相同制约。将导去了再现性。即使执行环境和初始条件相同，结果却程由程序段，相关数据段和PCB三部分组成独立性：进程实体可以独立运行，独立分配资源和独立接受调度(线程)。而未建立PCB的。就绪状态：进程已分配到除了CPU之外的所有必要资源，只要再获得CPU，便可立即执行。起。许可创建就绪I/0完成进程调度时间片完I/O请求执行进程终止：首先等待操作系统进行善后处理，然后清空PCB，并将PCB空间返还系统。3进程状态、进程优先级、进程调度所需其他信息、事件(阻塞原因)。原语：由若干指令组成，用于完成一定功能的一个过程，是原子操作。在管态(核心态)下进程才能在系统中运行，为了能让程序运行，需要建立进程。引起正常结束、异常结束、外界干预(父进程请求，父进程终止，操作系统干预等)2.若该进程正处于执行状态，则立即终止其执行，并置调度状态为真，表示该进程被终止止进程的全部资源，或归还父进程，或归还操作系统5.将被终止进程的PCB从所在队列中移出。在执行的进程，发现阻塞事件时，由于无法继续执行，于是进程调用block为。进程的唤醒过程：首先将被阻塞的进程从等待队列中移出，将其PCB中的现行状态改为就B4挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于存调入内存，检查其现行状态，若是静止就绪，便改为活动就绪；若作临界资源实例-生产者消费者/*#include<stdio.h>#defineMAX10typedefstructqueue{AXevoidproducer(queue&q,intdata){if(isfull(q)==1){//如果队列为满，生产者无法插入数据}else{ueqdata}}voidcustomer(queue&q){if(isempty(q)==1){//如果队列为空，消费者取不到东西}else{intdata=outqueue(q);}}那段代码称为临界区，临界区前面需要增加一段用于冲突检验的代，在临界区后面加上一段退出区代码，用于将临界区正被访问的标5子操作wait(),signal()来访问，即P，V操作。原子操作在执行时不可中断。voidwait(ints){while(s<=0)//当没有资源可以利用时，等待;s=s-1;//当有资源时，使用。每使用一个，资源个数减一}voidsignal(ints){s=s+1;//释放资源，资源个数加一}当信号量S<=0时，就会不断检测，未遵循让权等待。因此，除了需要一个用于代表资源数//记录型结构体typedefstructsemaphore{intvalue;//记录资源个数structsemaphore*L;//链接等待进程phorevoidwait(semaphore&s){//value表示系统中某类资源数目，每次wait操作，系统中可供分配的资源数减一s.value=s.value-1;//value值可以一直减下去，为负数也可以，当为负数的时候，说明有进程自我阻塞了lueblock(s.L);//当没有资源可用时，进程调用block将自己阻塞。}voidsignal(semaphore&s){valuesvalueif(s.value<=0)//若加一后，value值还是小于等于.则说明链表中还有阻塞的进程，需调用唤醒wakeup(s.L);}注：若value初值为1，表示只允许一个进程访问临界资源，此时的信号量化为互斥信号量Dtypedefstructsource{intarr[MAX];//source资源结构体，数组中存放每种资源的对应可用数目intlength;//总的资源种类数ce6voidsignal(source&s){for(inti=0;i<s.length;i++)s.arr[i]++;//一次性全部释放}voidwait(source&s){agfor(inti=0;i<s.length;i++){if(s.arr[i]>=1)//判断所需的全部种类资源是否都能够分配给进程flag=1;else{flag=0;break;}}if(flag==1){//如果能，则一次性全部分配给相应的进程forinti0;i<s.length;i++)s.arr[i]--;}else{}}为了使多个进程能互斥地访问谋临界资源，只需为该资源设置一互斥信号量mutex(资源个操作之间。在使用信号量实现互斥时，wait操作和signal操作需要成对出现。结构，对该数据结构进行操作的一组过程，对管publicclassMonitor{public};emonitornamevoidinit_value();voiduse_value();voidpublic_use_value();7题voidinit(semaphore&s){emptyMAXsfull;s.mutex=1;}//这些操作都可以循环执行，如下的只是他们的一次活动voidproducer(queue&q,semaphore&s){wait(s.empty);//先执行对资源信号量的操作wait(s.mutex);//再执行对互斥信号量的操作eqdatanalsmutexlsfull}voidcustomer(queue&q,semaphore&s){waits.full);wait(s.mutex);ueqnalsmutexalsempty}的号量的P,V操作也要成对出现。每个程序的多个P,V操作必须成对出现。其次，对于资源信Dtex用Swait(full,mutex);替换/采用循环队列方式，假设有N==5个哲学家，//所有信号量初始化为，第i为哲学家一次的活动方式如下，可以循环执行如下活动voidprofess(semaphore&s){//采用记录型方式wait(s.chopstick[i]);//拿左边的筷子wait(s.chopstick[(i+1)mod(s.n)]);//拿右边的筷子gnalschopstickisignalschopsticki)mod(s.n)]);k8}voidprofess(semaphore&s){//采用AND信号量方式kSwaitschopstickischopsticki1)mod(s.n));Ssignalschopstickischopsticki)mod(s.n)]);}置了一个互斥信号量Wmutex,另外，再设置一个voidinit(semaphore&s){s.rmutex=1;s.wmutex=1;sreadcount;}voidreader(semaphore&s){wait(s.rmutex);//判断有没有其他读者dcountwait(s.wmutex);//有没有作者正在写s.readcount++;//没有，则读者数加一read;//阅读wait(s.rmutex);//判断有没有其他读者s.readcount--;readcountsignal(s.wmutex);//只有当没有读者时，才执行此操作，为写操作提供资源nalsrmutex}voidwriter(semaphore&s){waits.wmutex);writelswmutex}9建立建程。基本单位、可并发执行、共享进程资源程。效率较高，但如果一个线程执行阻塞，其他线程三处理机调度和死锁才能得到，这些步骤叫做作业步(jobstep)。的编译、连接装配(将若干程序段装配为可执行程序)、运行(目标程序调入内存)流。作业控制块JCB：销JCB。于调度算法。最简单的2.低级调度(进程调度)：调度算法选取进程、把处理器分配给进程列入分派程序的上下文，以便分派程序运行。在第二对上下2．短作业(进程)优先原则：当新到达的作业(进程)比正在执行的作业(进程)明显短时，将暂停当前长作业(进程)的执行，使短作业优先执行。3中级调度(中程调度)：开始，到作业完成的这段时间间隔。包括四部分，作业在就绪队列上等待调度时间，进程执行时间，以及进程等待I/O操作完成的时间。T=sT=信息传送到处理机的时间，处理机对请求信息进行处理的时开始执行的最晚时间，或必须完成的最晚时间个重要指标先来先服务FCFS调度算法：FCFS算法有利于长作业(进程)，而不利于短作业(进程)。有利于而不利于I/O繁忙型的作业。短作业(进程)优先SJ(P)F调度算法：进程类型、进程对资源的需求、用户要求优先权=(等待时间+要求服务时间)/要求服务时间=(响应时间)/要求服务时间CPU并令其执行一个时间片，当执行的时间片用完，由FCFS算法排队等待调度，。若其未能完成，则调度程序将其转到下一个队列的队尾，同样按FCFS方式等待调度。如此继续下去。当一个长进程或长作业从第一个队列依此降至第n个队列后，在第n个队列中便采用按时间片轮转方仅当第1-(i-1)队列均空时，才会调度第i个队列的进程运行。若处理机正在第i个队列夺性资源。前者指进程在获得这类资源后，该。例如，系统中只有一个打印机和一个磁带机，供两个进程共享。若A进程已占用了打印塞；若A有要求磁带机，则A也阻塞。因而两者都等待对方的资源，但它们又因为阻塞。能产生死锁ELEASESELEASESELEASES环路等待条件：指发生死锁时，必然存在一个进程-资源的环形链。必要条件中的一个或几个条件分配过程中，用某种方式阻止系统进入不安全状态不检测系统是否进入不安全区，而是通过检测机制，及时检测出。#defineMAX10/*置的该类全部可用资源的数目。如果MAXn个进程对iRjavaliablejk则表示k分配矩阵allocation[i][j]=k,表示进程i当前获得的资源Rj有k个needijkiRj类资源k个dijMaxijAllocationijtypedefstructbank{intavaliable[MAX];//可利用资源向量intMax[MAX][MAX];//最大需求矩阵intAllocationMAXMAX/分配矩阵intneed[MAX][MAX];//需求矩阵设request_i是进程Pi的请求向量，如果request_i[j]=k,表示进程Pi需要K个Rj类requestijneedij转向2，否则认为出错。2)若request_i[j]<=avaliable[j],则转向3，否则认为出错3)系统分配资源给进程，并修改数据结构中数据Avaliable[j]=avaliable[j]-request_i[j];Allocation[i][j]=allocation[i][j]+request_i[j];jneedijrequestijvoidallocate(bank&ba,intrequest[][MAX],inti,intj){ifrequestijbaneedi][j]){if(request[i][j]<=ba.avaliable[i][j]){资源分配baavaliableijbaavaliableijrequestij];baAllocationijbaAllocationijrequestij;baneedijbaneedijrequestij];}}}work类资源数目，初始，work=lable量Finish，表示系统是否有足够的资源分配给进程，使之运行完成。初始，voidcheck(bank&ba,intwork[],boolfinish[],inti,intj){if(finish[i]==false&&ba.need[i][j]<=work[j]){Pi未结束，其所需资源系统可以满足它的资源。workj]=work[j]+ba.Allocation[i][j];finish[i]=true;}else{if(finish[i]==true)终止}}死锁检测可以利用资源分配图来描述。该图由一组节点N和一组边E所组成的一个对偶把N分为两个互斥的子集，即一组进程节点P和一组资源节点R，N=P并R。凡是属于E的边，都连接着jR1R2源点统处于S状态时是否为死锁状态。方法为：在资源分配图中，找一个既不阻塞又非独立的进程节点Pi,在顺利的情况下，Pi可以获得所需资源而继续运行，直至运行完毕，再释放其所占的所有资源，相当于消去Pi如上图，将P1两个分配边和一个请求边消去，留下一个孤立的P1节点。这样，图中所有的资源由P2使用，当P2获得资源并执行完毕后，将P2的边也删去。利用这用简化方式，如进程四存储器结构一个可在内存中执行的程序，首先要编译，由编译程序将源程序链接程序将编译后的目标模块，以及所需库函数链接起知道程序将驻留在内存的什么位置，则，编译程序将产生绝将各自目标模块及其所需库函数，链接成一个装入模块，以后CALLC语句。欲将A,B,C装配成一个装入模块。需要修改两个东西：)对相对地址进行修改2)变换外部调用符号，将调用符号换成相对地址0块ACALLBL-10模块AJSRL0M-10L-1L模块BCALLCL+M-1模块C模块BJSRL+M模块CN-1L+M+N-1次适应FF算法：空闲分区为止，然后再按照作业的大小，从该分区中划，不再是每次都从链首开始查找，而是从上一次找到的空闲分块满足要3)最佳适应BF算法：4)最坏适应WF算法：，总是挑选一个最大的空闲分区分割给作业，优点在于可5)快速适应QF算法：大小进行分类，对于每一类具有相同容量的所有空闲分区，单独存在多个空闲分区链表，同时在内存中设立一张闲分区类型，并记录该类型空闲分区链表头中，主要操作是分配内存和回收内存，无论分配分区还是空闲分区，分区大小均为序，紧凑后的用户程序在内存中的位置发生改变，因此，需要重和>=请求区进行紧凑形成连续空闲区按动态分区方式进行分配修改有关数据结构修改有关数据结构别称之为。内碎片”。页面大小一般为2的幂。分页地址由页号，偏移量(页内地址)组成。如下例：位移量若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号和页内地址D为：D=[A]MODL将页表地址与页号和页表项长度的乘积相加(即，基地址+偏移量)得到该表项在页表中的CPU构自动将页号送入快表，并将此以32位逻辑空间为例，当页面大小为4KB(12位)，若采用一级页表结构，对应(32-12)20位的页号。若采用二级页表，则需要对页表分页，外层页表中的页内地址为10位，外层页号也为10位。页表的首表结构的情况下，对于正在运行的进程，必须将1)方便编程：用户把作业按照逻辑关系划分为若干段，每段从0开始编址2)信息共享：分页系统中的页只存放信息的物理块，无完整意义，而段是信息的逻辑单位3)信息保护4)动态增长：处理数据段的动态增长5)动态链接：只有当目标程序运行过程中，才将某段目标程序调入内存并链接少个段，段内地址显示出段的大小项，物理地址=