搜索
第一章操作系统引论1、什么是操作系统：操作系统(OS)是配置在计算机硬件上的第一层软件，是对硬件的首次扩充，是对计算机资源进行管理的软件。（操作系统是一组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合）2、操作系统的目标：1)方便性。2)有效性。3)可扩充性。4)开放性。3、操作系统的作用：1）OS作为用户与计算机硬件系统之间的接口。2）OS作为计算机系统资源的管理者。3）OS实现了对计算机资源的抽象。4、对应课本：1.2.2-1.2.5，看一遍课本，选择4.1、单道批处理系统主要特征如下：1)自动性。2)顺序性。3)单道性。缺点：系统中的资源得不到充分利用。4.2、多道批处理系统特征：1)多道性。2)无序性。3)调度性（作业调度和进程调度）。概念：在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。优缺点：1）资源利用率高。2）系统吞吐量大。3）平均周转时间长。4）无交互能力。需要解决的问题：1)处理机管理问题.2)内存管理问题.3)I/O设备管理问题.4)文件管理问题.5)作业管理问题.4.3、分时系统用户的需求具体表现：1)人—机交互。2)共享主机。3)便于用户上机。实现中的关键问题：1)及时接收。在系统中配置一多路卡(2)及时处理。分时系统的实现方法：1）作业应直接进入内存。2）规定每个程序只运行一很短的时间（时间片），然后便暂停该作业的运行并立即调度下一个程序运行。具体的实现方法：1）单道分时系统。2）具有“前台”和“后台”的分时系统。3）多道分时系统。特征：1）多路性。2)独立性。3)及时性。4)交互性。4.4、实时系统定义：是指系统能(或即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。实时任务的分类：1）按任务执行时是否呈现周期性来划分：周期性实时任务和非周期性实时任务。（外部设备所发出的激励信号并无明显的周期性，但都必须联系着一个截止时间(Deadline)。它又可分为：开始截止时间——任务在某时间以前必须开始执行；完成截止时间——任务在某时间以前必须完成。）2）根据对截止时间的要求来划分：硬实时任务。系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果；软实时任务。它也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大。实时系统与分时系统特征的比较：1）多路性。2）独立性。3）及时性。4）交互性。5）可靠性。5、操作系统的基本特征：实时、并发、共享、虚拟、异步。6、操作系统的主要功能：处理机管理，存储器管理，设备管理，文件管理，用户接口。第二章进程的描述与控制1、程序顺序执行时的特征：1）顺序性。2）封闭性。3）可再现性。2、程序并发执行时的特征：1）间断性。2）失去封闭性。3）不可再现性。3、进程的定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。4、进程的特征：1）动态性。2）并发性。3）独立性。4）异步性。5）结构特征（PCB结构）。5、进程实体的组成：程序段，相关的数据段，PCB（进程控制块）。6、进程的三种状态：就绪（Ready），执行（Running），阻塞（Block）就绪阻塞执行时间片完进程调度I/O完成I/O请求活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O7、PCB已成为进程存在于系统中的唯一标识。PCB常驻内存。8、进程标识符：1）外部标识符（不唯一，通常是由字母、数字组成）。2）内部标识符（唯一的数字标识符）。9、（了解知道）系统态：又称管态，内核态。用户态：又称目态。10、原语定义：由若干条指令组成，用于完成一定功能的一个过程。它们是“原子操作”，是一个不可分割的基本单位，在执行过程中不允许被中断。11、引起进程创建的事件(选择题)：用户登录、作业调度、提供服务、应用请求。12、进程的同步对应课本2.412.1、临界资源（区）：在一段时间内只允许一个进程访问或使用，这种资源被称为临界资源。每个进程中访问临界资源的那段程序称为临界区。12.2、同步机制应遵循的规则（同步规则）：1）空闲让进。2）忙则等待。3）有限等待。4）让权等待。12.3、信号量1）记录型信号量：在记录型信号量机制中，S.value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value∶=S.value-1；当S.value＜0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value∶=S.value+1操作表示资源数目加1。若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。2）互斥信号量：mutex，初值为1，取值范围（-1，0，1）。当mutex=1时，表示无进程进入，无进程等待进入该临界区；当mutex=0时，表示有一个进程进入，无进程等待进入该临界区；当mutex=-1时，表示有一个进程进入，有n个进程等待进入该临界区。12.4、前驱图例题：a,b,c,d,e,f,g=0,0,0,0,0,0,0；{S1；V(a)；V(b)；}{P(a)；S2；V(c)；V(d)；}{P(b)；S3；V(g)；}{P(c)；S4；V(e)；}{P(d)；S5；V(f)；}{P(e)；P(f)；P(g)；S6；}S4S5S3S1S6S2cefdabg13、经典进程的同步问题13.1生产者-消费者问题1、原型semaphoremutex=1，empty=n，full=0；生产者消费者{生产了一个产品；{P(full)；P(empty)；P(mutex)；P(mutex)；从缓冲区取产品；放到缓冲区；V(mutex)；V(mutex)；V(empty)；V(full)；}消费；}2、变型1：父亲分苹果和橘子问题(奇数-偶数问题)semaphoremutex=1，orange=apple=0，empty=n；父亲女儿儿子{洗一个水果；{P(apple)；{P(orange)；P(mutex)；取走；取走；if(苹果)V(apple)；V(mutex)；V(mutex)；elseV(orange)；}}}3、变型2：生产-加工-消费问题semaphoreempty1=x，empty2=y，full1=full2=0；生产加工消费{生产了一个产品；{P(full1)；{P(full2)；P(empty1)；从B1取走一个产品；从B2取走一个产品；放到缓冲区B1；V(empty1)；V(empty2)；V(full1)；加工；消费；}P(empty2)；}放入缓冲区B2；V(full2)；}注：若缓冲区B1,B2为互斥，则在B1,B2操作前后加上申请和释放互斥信号量即可。13.2哲学家就餐问题semaphoreS1=S2=S3=S4=S5=1；P1P2P3P4P5{饿了；{饿了；{饿了；{饿了；{饿了；P(S5)；P(S1)；P(S2)；P(S3)；P(S4)；P(S1)；P(S2)；P(S3)；P(S4)；P(S5)；吃；吃；吃；吃；吃；V(S5)；V(S1)；V(S2)；V(S3)；V(S4)；V(S1)；}V(S2)；}V(S3)；}V(S4)；}V(S5)；}注：解决死锁办法：任意一个人拿筷子的顺序相反。13.3读者-写者问题semaphorermutex=wmutex=1；intreadcount=0；读者写者{P(rmutex)；{P(wmutex)；if(readcount==0)P(wmutex)；//第一个读者写；readcount++；V(wmutex)；V(rmutex)；}读；P(rmutex)；readcount--；if(readcount==0)V(wmutex)；//最后一个读者V(rmutex)；}第三章处理机调度与死锁1、处理机调度的层次1.1、高级调度：又称长程调度或作业调度，他的调度对象是作业。JCB是作业存在的唯一标识。1.2、低级调度：又称进程调度或短程调度，他的调度对象是进程(或内核级线程)。1.3、中及调度：又称内存调度。2、作业调度算法(二选一考)：先来先服务(FCFS)调度算法和短作业优先(SJF)调度算法。3、周转时间：作业提交系统开始到作业完成的时间段。平均周转时间：T=n1nin1T。4、进程调度方式(算法)：非抢占方式(调度算法)和抢占方式(调度算法)。5、抢占方式的抢占原则：1）优先权原则。2）短进程优先原则。3）时间片原则。6、产生死锁的原因：竞争资源，进程间推进顺序非法。7、产生死锁的必要条件：1）互斥条件。2）请求和保持条件。3）不可抢占条件。4）循环等待条件。8、处理死锁的方法：1）预防死锁。2）避免死锁。3）检测死锁。4）解除死锁。9、预防死锁的方法：是通过破坏产生死锁的四个必要条件中的一个或几个，以及避免发生死锁，主要是破坏产生死锁的后三个条件：破坏“请求和保持”条件，破坏“不可抢占”条件，破坏“循环等待”条件。10、安全状态：是指系统能按某种进程顺序(P1,P2,…，Pn)为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称〈P1,P2,…,Pn〉序列为安全序列。11、利用银行家算法避免死锁:例题：P119在银行家算法中，若出现下述资源分配状况，试问：(1)该状态是否安全？Finish时全为True，所以状态安全。(2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？∵P2的Request2(1,2,2,2)≤Need2(2,3,5,6)且Request2(1,2,2,2)≤Available(1,6,2,2)∴进行预分配Available=(1,3,5,4)+(1,6,2,2)=(2,5,7,6)Allocation2=(1,6,2,2)-(1,2,2,2)=(0,4,0,0)∵Finish不全为True∴不能分配，恢复数据结构12、资源分配图(会画)以及资源分配图的简化。P115、P11613、死锁定理（S为死锁状态的充分条件）：当且仅当S状态的资源分配图是不可简化的。ProcessAllocationNeedAvailableWork+AllocationFinishP00,0,3,20,0,1,21,6,2,21,6,5,4TP11,0,0,01,7,5,02,9,8,6TP21,3,5,42,3,5,63,12,13,10TP30,3,3,20,6,5,21,9,8,6TP40,0,1,40,6,5,63,12,14,14T14、死锁的解除：1）剥夺资源。2）撤消进程。第四章存储器管理1、动态分区分配算法(选择题)：1)首次适应(FF)算法:空闲区按地址递增顺序排列。2)循环首次适应(NF)算法:空闲区按地址递减顺序排列。3)最佳适应(BF)算法：空闲区按大小递增顺序排列4)最坏适应(WF)算法：空闲区按大小递减顺序排列。2、分页存储管理方式：掌握一级页表的地址划分；掌握查页表，做地址变换。例题：页面大小4KB，按字节编址，写出地址划分。2的12次方等于4KB3112110页号页内地址3、分段存储管理方式：掌握地址划分。4、分页和分段的主要区别：1）页是信息的物理单位，段则是信息的逻辑单位。2）页的大小固定且由系统决定，段的长度不固定，决定于用户所编写的