操作系统-=《操作系统整理

第一章操作系统概述识记：1.OS有哪3种观点（目标？）和OS的定义:操作系统是一组计算机程序的集合1)控制和管理计算机的硬件和软件资源，2)合理地组织计算机的工作流程，使之可以得到更加合理的共享及保护，以及尽量好的性能。3)向应用程序和用户提供方便、快捷、友好的使用接口。2.OS有哪3种基本类型及其目标:1)批处理操作系统：提高系统资源利用率和作业吞吐率2)分时操作系统：满足用户交互的及时响应3)实时操作系统：提高系统的及时性和可靠性（？）3.OS有哪4个特征:并发性、共享性、虚拟性、异步性（随机性）4.OS有哪5大功能：（6？）进程管理、存储管理、文件管理和设备管理是操作系统的基本功能，网络通信与服务、安全与保护是现在主流操作系统的衍生功能。第二章进程管理识记：1.进程的定义：可并发执行的程序在某个数据集合上的一次执行过程,是操作系统资源分配、保护和调度的一个基本单位进程的基本状态：就绪状态，运行状态，阻塞状态（等待状态）进程的组成：进程控制块（PCB）+程序块+数据块+堆栈进程控制块的组织方式：线性方式（有？）链接方式：单向，或双向索引方式：对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址2.原语的定义:由若干条指令所组成，用来实现某个特定功能，在执行过程中不可被中断的程序段3.进程互斥的定义:若干进程因相互争夺独占型资源而产生的竞争制约关系（若干个进程要访问同一共享资源时，任何时刻最多允许一个进程访问，其他进程必须等待，直到占有资源的进程释放该资源）4.临界资源和临界区的定义；临界资源：某段时间内只能允许一个进程使用的共享资源临界区：访问临界资源的代码段5.进程同步的定义：为完成共同任务的并发进程基于某个条件来协调其运行进度、执行次序而等待、传递信号或消息而产生的协作制约关系理解：1.进程同步机制；锁、信号量、管程、消息传递2.进程互斥与进程同步的异同点；（？）异：进程同步是为完成共同任务的并发进程基于某个条件来协调其运行进度、执行次序而等待、传递信号或消息而产生的协作制约关系，而进程互斥是若干进程因相互争夺独占型资源而产生的竞争制约关系。同：互斥是一种特殊的同步关系——以一定次序协调地使用共享资源3.调用信号量S的P(S)操作与V(S)操作及其处理的物理意义。（P39）P(s)：将信号量s的值减1，若结果小于0，则调用P(s)的进程被阻塞，并进入信号量s的阻塞队列中;若结果大于等于0，则调用P(s)的进程继续运行物理意义：P(s)操作表示进程申请一个资源，求而不得则阻塞进程voidP(semaphore&s){s.value--;if(s.value0)block(s.list);//阻塞本进程并进入S信号量队列}V(s)：将信号量s的值加1，若结果不大于0，则调用V(s)的进程从该信号量阻塞队列中释放，唤醒一个处于等待状态的进程，将其转换为就绪状态，调用V(s)的进程继续运行;若结果大于0，则调用V(s)的进程继续运行。物理意义：V(s)操作表示释放一个资源，若此时还有进程在等待获取该资源，则被唤醒voidV(semaphore&s){s.value++;if(s.value=0)wakeup(s.list);//唤醒s信号量队列中的一个进程入就绪队列}简单应用：利用信号量解前趋图问题。（？）利用信号量描述程序和语句之间的前驱关系如果进程p1中有语句s1，p2中有语句s2，为实现s1执行后再执行s2，只需让p1,p2进程共享一个公共信号量S,且init(S)=0例题：在公共汽车上，司机和售票员的工作流程如下图所示。为保证乘客的安全，司机和售票员应协调工作：停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调分析:司机启动车辆的动作必须于售票员关车门的动作取得同步，售票员开车门的动作也必须与司机停车取得同步综合应用：.1.能写和理解计算、打印问题程序，生产者/消费者问题程序；（P43）（生产者进程可以是计算、发送进程，消费者进程可以是打印、接受进程）计算、打印问题程序设信号量bufempty=1(表示缓冲区数)buffull=0（表示运算结果数）processC(){processP(){while(true){while(true){P(bufempty);P(buffull);计算；取出buf中的数据buf计算结果置空标记，打印V(buffull);V(bufempty);}}}}生产者/消费者问题：m个生产者和n个消费者共享k件产品缓冲区，只要缓冲区未满，生产者就可送入缓冲区；只要缓冲区不空，消费者就可从缓冲区取走并消耗产品解：互斥信号量mutex:限制生产者和消费者互斥地对缓冲区进行存取，初值为1同步信号量empty:保证生产者不向已满地缓冲区中放入产品，初值为k同步信号量full：保证消费者有产品消费，初值为0in和out：放入缓冲区指针和取出缓冲区指针itemB[k];//缓冲区，长度ksemaphoreempty=k;//可用的空缓冲区数semaphorefull＝0;//缓冲区内可用的产品数semaphoremutex＝1;//互斥信号量intin=0;//缓冲区放入位置intout=0;//缓冲区取出位置cobeginprocessproducer_i(){processconsumer_j(){while(true){while(true){produce();//生产一个产品P(full);P(empty);//申请空缓冲区P(mutex);P(mutex);//申请互斥使用缓冲区take()fromB[out];appendtoB[in];//产品放入缓冲out=(out+1)%k;in=(in+1)%k;//更新缓冲区指针V(mutex);V(mutex);V(empty);V(full);consume();}}}}coend2.能写和理解哲学家问题的程序；（P46）有五个哲学家围坐在一圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之间放一个筷子。每个哲学家思考、饥饿，然后想吃通心面。为了吃面，每个哲学家必须获得两个筷子，规定每人只能直接从其左边或右边去取筷子解：筷子是共享资源，需要互斥访问(信号量解决互斥问题)。引入五个互斥信号量。给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之semaphorechopsticks[5];for(inti=0;i5;i++)chopsticks[i]=1;cobeginprocessphilmac_i(){//i=0,1,2,3,4think()；if(i%2==0){P(chopsticks[i])；P(chopsticks[(i+1)%5])；}else{P(chopsticks[(i+l)%5]);P(chopsticks[i]);}eat()；V(chopsticks[i])；V(chopsticks([i+1]%5)；}coend3.能写和理解读者/写者问题的程序。(P45)有两组并发进程，读进程与写进程，共享一个文件，为防止出错，要求：1）允许多个读进程同时读文件；2）只允许一个写进程写文件；3）写进程在没有写完成之前不允许其他读写；4）写之前应该让所有已经在读或写的进程操作完成。解：引入一个计数器和两个信号量解决此问题：信号量：ws:允许写信号量，初值为1mutex:互斥访问rc计数器信号量，初值为1计数量：readcount:读进程计数器intreadcount=0;//读进程计数器semaphorews=1,mutex:=1;cobeginprocessreader_i(){processwriter_j(){P(mutex);P(ws);readcount++;写文件;if(readcount==1)P(ws);V(ws);V(mutex);}读文件；P(mutex);readcount--;if(readcount==0)V(ws);V(mutex);}coend处理器调度识记：1.作业调度的定义；按一定的算法对外存输入井上的大量后备作业进行选择调入内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行（or：按照某种调度算法从后备作业队列中选取作业，使其进入内存运行）2.进程调度的定义；用来决定就绪队列中的哪个进程应获得处理机，再由分派程序执行把处理机分配给该进程的具体操作3.中级调度的定义；为了提高内存的利用率和系统吞吐量，根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换4.进程调度的两种方式；非抢占方式，抢占方式5.作业平均周转时间的公式T；T=(ΣTi)/n6.作业平均带权周转时间的公式W；W=(ΣWi)/n综合应用：作业采用先来先服务、短作业优先、优先级高优先的调度算法时计算一批作业的T和W。（P55）(一)先来先服务算法（FCFS）【例】系统中现有5个作业A、B、C、D、E同时提交（到达顺序也为ABCDE），其预计运行时间分别10、1、2、1、5个时间单位，如表所示，计算FCFS调度下作业的平均周转时间和平均带权周转时间解：设作业到达时刻为0，根据定义计算，系统运行情况【例】在单道环境下，某批处理系统有四道作业，已知它们的进入系统的时刻、估计运算时间如下：用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间解:1)调度次序：12342)完成时间图:3)T=2+2+1.6+1.3)÷4＝1.725(h)W=(2/2+2/0.5+1.6/0.1+1.3/0.2)÷4＝6.875(h)(二)短作业优先算法（SJF）【例】设有5道作业解：根据SJF原则，调度次序为：P1-P2-P5-P4-P3T=(0.3+0.6+0.4+0.8+1.3)÷5＝0.68(h)W=(0.3/0.3+0.6/0.5+0.4/0.2+0.8/0.3+1.3/0.4)÷5＝2.024(h)(三)优先级高优先算法（HPF）【例】系统的进程调度采用抢占式优先权调度算法，优先数越小优先级越高，其参数如表所示，求平均周转时间和平均等待时间解：作业进程综合调度示例：平均周转时间T=（15+8+12+4）/4=9.75平均等待时间Tw=（8+4+11+0）/4=5.75死锁理解：1.死锁检测；（P66）对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运行一个“死锁检测”程序，判断系统内是否已出现死锁，如果检测到系统已发生了死锁，再采取措施解除它。关键难点:确定何时运行死锁检测算法2.死锁解除；（P66）重启、撤销、剥夺、回滚3.死锁预防；（P62）主要方法：（都会造成系统资源利用率和吞吐率降低）（1）破坏互斥条件：使资源可同时访问而不是互斥使用，受资源本身特性限制，可行性较差（2）破坏占有并请求(等待):静态分配（进程必须获得所需要的所有资源才能运行），严重降低资源利用效率（3）允许剥夺：剥夺式调度算法，只适用于CPU和内存（4）阻止环路等待：层次分配策略，低效，限制新设备类型的增加，使执行速度变慢，并可能在无必要的情况下拒绝资源访问4.死锁避免。（P63）常见的方法：银行家算法不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能够完全的分配，在确定不会发生死锁的情况下，才把资源真正分配给进程，从而避免死锁的发生综合应用：银行家算法的具体应用。（必考）（P63-65）多种资源的银行家算法的具体过程：【例】设有五个进程{P0,P1,P2,P3,P4}，三类资源｛A,B,C｝，各拥有资源数｛10，5，7｝，（1）在T0时刻系统的资源分配情况如下：当前状态为：Available={3,3,2}则目前系统处于安全状态，因为存在安全序列：{P1,P3,P0,P2,P4}，满足安全性条件（2）假定进程P1又要申请1个A类资源和2个C类资源，判断此申请能否获得批准？首先检查Request的有效性：Request1(1,0,2)=S1(1,2,2)，Request1(1,0,