操作系统期末复习.docx

第一章 4分1.计算机系统组成的四个部分（硬件、操作系统、系统程序与应用程序、用户）2.操作系统位于那一层、上下层关系 操作系统控件和协调各用户的应用程序对硬件的使用3.操作系统的两个角色（资源分配器、控制程序）4.操作系统运行过程中的二态性（内核态、用户态）5.操作系统的计算环境（传统计算、客户机-服务器计算、对等计算、基于Web的计算）6.OS五个基本模块：（进程管理、进程通信、I/O、内存管理、文件系统）7.进程是操作系统工作的基本单元第二章4分操作系统服务用户界面、程序执行、I/O操作、文件系统操作、通信、错误检测、资源分配、统计、保护和安全了解系统调用（提供了操作系统提供的有效服务界面，最小的功能单位） API：应用程序接口1.程序的可移植性 2.实际的系统调用比API更注重细节和困难向操作系统传递参数的三种方法a.寄存器传递参数 b.通过程序放入堆栈中 c.块和堆栈的方法操作系统结构（单核、微核）系统调用的五类： a.进程控制 b.文件管理 c.设备管理 d.信息维护 e.通信单核操作系统的结构以及例子（简单结构-DOS、层次结构-UNIX、模块化-solaris）操作系统设计的策略和机制的区别（策略决定做什么、机制决定怎么做）微核与模块化的区别相同点：拆分功能，实现模块化，维护简单不同点：微核的模块位于用户空间、模块化的模块位于内存空间；性能上：微核更为灵活，可以随意加卸载，但是带来的系统开销更大（通信开销）、模块化需要进行编译才能加载（更改，不能在运行时更改），模块之间有一定依赖关系第三章8分进程概念（执行中的程序）进程区别于程序（程序是非运行态的，而进程是运行着的；进程还包括程序计数器、寄存器、堆栈段、数据段、堆（可能）等）进程状态&进程状态图（见图3.2）（ps：联系到第五章的：CPU调度牵涉到这其中的状态变化有：运行到等待（非抢占）、运行到就绪（抢占）、运行到结束（非抢占）、等待到就绪（抢占）CPU调度发生在进程调度的什么时候：运行态到等待态（非抢占）运行到就绪（抢占）等待到就绪（抢占）进程终止（非）PCB的概念&包含的内容（进程状态、程序计数器、CPU寄存器、内存管理信息、记账信息、I/O状态信息）调度队列（作业队列、就绪队列、设备队列）调度队列迁徙图调度（长期-作业调度、中期-存储器调度、短期-CPU调度）I/O绑定、CPU绑定I/O绑定:当io时间比cpu时间大的时候(执行I/O方面比执行计算花费时间多)CPU绑定:当io时间比cpu时间短的时候如果均以I/O为主，则就绪队列几乎为空，短期调度程序没什么可做如果均以CPU为主，则等待队列几乎总为空，从而几乎不使用设备上下文切换的概念 将CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态。 进程上下文用进程的PCB表示。通过执行一个状态保存来保存CPU当前状态（不管它是模式还是用户模式），之后执行一个状态恢复重新开始运行。进程通信、生产者消费者模型有限缓冲区无限缓冲区的问题 有限缓冲：对缓冲大小没有限制。消费者可能不得不等待新的项，但生产者总是可以产生新项 无限缓冲：假设缓冲大小固定。对于这种情况，如果缓冲为空，那么消费者必须等待;如果缓冲为满，那么生产者必须等待。进程间通信的实现方式 进程通信的两种模式：共享内存/消息传递进程通信的技术有：管道通信、消息通信、网络方式、共享内存sockts套接字概念（其中ip是用来找到机器的（地址）、端口号是用来找到进程的）第四章4分线程的概念 是CPU使用的基本单元，它由线程ID、程序计数器、寄存器集合和栈组成。它与属于同一进程的其他线程共享代码段、数据段和其他操作系统资源。 一个进程中的多个线程必须共享地址空间。多线程编程优点： 响应度高、资源共享、经济、多处理器体系结构的利用。映射模型 用户级线程映射到内核线程。多对一：线程管理是由线程库在用户空间进行的。效率比较高。但是如果一个线程执行了阻塞系统调用，那么整个进程会阻塞。而且，因为任一时刻只有一个线程能访问内核，多个线程不能并行运行在多处理器上。一对一：一个线程执行阻塞系统调用时，能允许另一个线程继续执行，它提供了比多对一模型更好的并发功能;它也允许多个线程能并行地运行在多处理器系统上。缺点：每创建一个用户线程就需要创建一个相应的内核线程。由于创建内核线程的开销会影响应用程序的性能，所以这种模型绝大多数实现限制了系统所支持的线程数量。多对多：可创建任意多的用户线程，并且相应内核线程能在多处理器系统上并发执行。*优先级调度大问题第五章10分分派程序功能： 切换上下文、切换到用户模、跳转到用户程序的合适位置，以重新启动程序。调度准则cpu利用率、吞吐量（系统）、周转时间、等待时间（进程）、响应时间（用户）需要使CPU使用和吞吐量最大化，而使周转时间、等待时间和响应时间最小化调度算法先来先服务（非） 短作业优先（非、抢）优先级调度（非、抢，包含FCFS和SJF）轮转（抢）多级队列调度： 多级反馈队列调度：第六章14分竞争条件的定义（并发进程对于共享变量的访问造成数据不一致的现象） 多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关临界区的三个准则（a.互斥:同一时刻只能有一个进程进入临界区 b.前进：当没有进程在临界区时，在临界区外等待的进程不会发生死锁 c.有限等待：保证所有进程在有限的司机等待后都能进入临界区）解决同步问题三级：指令集层次:提供特殊的硬件指令,使得特定代码可以顺序执行而不被抢占(仅适用单CPU);操作系统内核：分抢占式内核和非抢占式内核，非抢占内核可以免除竞争条件的困扰；编译器层次：可以通过同步信号量等同步原语来控制线程的同步。信号灯wait&signal&分清有无忙等待的情况经典同步问题（有点缓冲区&读者作者问题：必考代码；哲学家进餐问题的两个原理：死锁、饥饿） 缓冲池有n个缓冲项。Mutex初始化为1，信号量empty、full分别用来表示空缓冲项和满缓冲项的个数。信号量empty初始化为n;而信号full初始化为0。 Do doWait(empty); wait(full); Wait(mutex); wait(mutex); Signal(nutex); signal(mutex); Signal(full); signal(empty);while(true); while(true);生产者进程结构 消费者进程结构读者-写者问题：读者进程共享以下数据结构：Semaphore mutex,wrt;Int readcount;信号量mutex和wrt初始化为1;readcount初始化为0写者进程结构：DoWait(wrt); Signal(wrt);while(true);读者进程结构：DoWait(nutex);Redcount+;If(redcount=1) Wait(wrt);Signal(nutex);Wait(nutex);Redcount-;If(readcount=0) Signal(wrt);Signal(mutex);while(true);管程概念 任意时刻只能有一个进程在管程中处于活动状态。 第七章6分死锁的四个必要条件（互斥、拥有并且等待、不可剥夺、循环）四个条件什么时候变成充要条件（每个资源类型刚好有一个实例）解决方法（防患（预防和避免的区别:前者是精确打击，后者是扩大打击）、恢复、鸵鸟政策） 死锁预防：确保至少一个必要条件不成立。 死锁避免：安全状态、资源分配图算法、银行家算法死锁处理方法1. 使用协议以预防或避免死锁2. 允许系统进入死锁状态3. 忽视这个问题，认为死锁不可能在系统内发生资源分配图 申请边、分配边 成环不一定有死锁（每个资源只有一个实例情况下一定有死锁） 不成环一定没有死锁死锁恢复 进程终止：1. 终止所有死锁进程2. 一次只终止一个进程直到取消死锁循环为止资源抢占：1. 选择一个牺牲品：必须确定抢占顺序以使代价最小2. 回滚3. 饥饿第八章16分逻辑物理地址的区别 逻辑地址：CPU所生成的地址 物理地址：内存单元所看到的地址（即加载到内存地址寄存器中的地址）地址绑定过程的三个过程编译时：如果编译时就知道进程将在内存中的主流位置，那么就可以生产 绝对代码。加载时：如果再编译时不知道进程将驻留在内存的什么地方，那么编译器就必须生成可重定位代码。 执行时：如果进程在执行是就可以从一个内存段转移到另一个内存段那么绑定必须延迟到执行时进行。MMU： 内存管理单元，实现由虚地址向物理地址映射的硬件单元。内存分配方法首次适应：分配第一个足够大的孔最佳适应：分配最小的足够大的孔（比较次数最多，效率最高）最差适应：分配最大的孔（比较次数最少，效率最低）首次和最佳都会产生外部碎片问题。内外碎片的概念区别 内部碎片：内存以固定大小的块为单元来分配。这部分内存在分区内，但又不能使用（不连续分配产生） 外部碎片：分页地址转换-页号、偏移两次内存访问；EAT计算公式（eat时间在一级页表是2倍、二级页表是2倍）；TLB页表结构的实现方案1分层页表 优点：减少了每一集页表所需的存储空间，缺点：增加了内存访问次数，需要更多的内存访问才能获得物理地址。2 HASH页表 。优点：提高了效率，缺点：实现复杂，还可能出现多个地址映射到HASH表中的同一行从而导致访问效率下降。3反向页表。优点：系统只需要一个页表，减少了再每个进程总存储表所需的内存空间，缺点：搜索页表的时间增加，不便于实现共享内存。分段方式的概念 段表在寄存器，不用多次访问内存第九章22分虚拟内存的基本原理虚拟内存技术应许执行进程不必完全在内存中，虚拟内存将内存抽象成一个巨大的，统一的存储数组，进而将用户看到的逻辑内存与物理内存分开。pagefault的处理步骤（图9.6）（分别位于用户还是内核态）把书274页左下角的东西打上来有效访问时间换页（FIFO、最优置换、最近最少使用置换）系统颠簸产生的原因 操作系统监视CPU的使用率，如果太低，就向系统中引入新进程，以增加多道程序的程度。新进程试图从其他运行进程中拿到帧，从而引起更多页错误，形成更长的调页设备的队列。两种解决方案 工作集合模型 页错误频率程序局部性原理 顺序访问、向量操作纯代码、堆栈（好）、指针bad、链表、二分查找（bad） 范围跨度越大越不好内核内存的分配 Buddy系统 造成内部碎片第十章 共6分文件的概念文件的属性 名称、标识符、类型、位置、大小、保护、（时间、日期和用户标识）基本操作 创建文件、写文件、读文件、在文件内重定位、删除文件、截短文件目录相关操作有那些 搜索文件、创建文件、删除文件、遍历目录、重命名文件、跟踪文件系统目录结构 单层结构、双层结构、树状结构、无环图、通用图第十一章文件系统层次概念 几层（图11.1） 应用程序、逻辑文件系统、文件组织系统、基本文件系统、I/O控制、设备三种分配法 连续分配（可随机访问）优点：顺序存取简单高效，寻道距离次数少，访问速度快，适合随机访问，算出块地址直接访问。缺点：有外部碎片，外村利用率低，插入删除不容易。 链接分配（不可随机访问）优点：消除外部碎片，外存利用率高，有利于文件的动态扩充，容易插入和删除。缺点：不适合随机访问，可靠性差，寻道次数多速度慢显示链接分配可显著减少寻道次数，提高检索速度，内存占用空间大、。索引分配（可随机访问）优点：有链接分配的全部优点，还适合随机访问，寻道次数少，速度快。缺点：索引块浪费较多空间，小文件特别，混合索引可避免这个缺点。第十三章 6分io基本操作模式（轮询、中断、直接内存访问DMA）轮询：由用户进程来直接控制内存或CPU和外围设备之间的信息传送。当主机要通过端口来读写数据时候，主机与控制器握手不断轮询地读取状态寄存器的忙位，直到忙位被清除，设置写位后写入一字节并设置命令就绪位，此时忙位被设置上，控制器便开始读取读字节并向设备执行io操作，最后清除各项设置的位。这样一来，程序轮询毕竟占据了CPU相当一部分处理时间，CPU和I/O设备串行工作，整个系统效率很低。在现代计算机系统中已很少应用。中断：当CPU检测到