操作系统期末考试-考研-必考重点(个人总结)

共分2部分：Part1,Part2其中，Part1为基础部分，共占65分，包括：选择2’*15判断2’*10大题7’+8’内容为考研大纲上的85%---90%Part2为考研题型，占35分，与每年考研试卷中操作系统部分所占的题型、分数、数目完全一致（选择+2道大题）整张试卷，大题四道：1、P、V操作（若为前驱图，信号量必定=3）2、作业调度3、死锁银行家算法4、可变分区的3种方法（最先、最佳、最坏适应）5、地址映射（页式、段页式）6、内存置换（FIFO、OPT、LRU、时钟）、命中率7、磁盘调度算法（最基本的电梯调度、先来先到、单向扫描）8、索引结构、会画图（连续、链接、索引、I结点）9、磁盘的空间管理（给一个位图，转换物理块号）其中,Part1的两道大题出自4、5、6、8Part2的两道大题出自1、2、3、7、9第二章进程管理1本章要点基础：进程描述及控制策略：进程调度实现：互斥与同步避免：死锁与饥饿解决：几个经典问题关于：进程通信22.1进程的引入3程序顺序执行程序：源代码程序、目标程序和可执行程序程序执行：编辑、编译、链接、执行程序的结构：顺序结构、分支结构和循环结构4程序顺序执行程序顺序执行的特征：顺序性、封闭性、可再现性5程序并发执行多道程序设计技术：多个程序并发执行程序并发执行时的特征：间断性、非封闭性、不可再现性6程序并发执行引发的问题协调各程序的执行顺序例如，当输入的数据还未全部输入内存时，计算必须等待多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果选择哪些、多少个程序进入内存执行？内存中的执行程序谁先执行，谁后执行？内存如何有效分配？7进程的概念定义：可并发执行的程序，在一个数据集合上的运行过程。申请/拥有资源∽调度（线程）程序：静态概念，是指令和数据的集合，可长期存储进程与程序对应关系：-一个程序可以对应一个进程或多个进程-一个进程可以对应一个程序，或者一段程序8进程的特征动态性并发性独立性异步性9引入进程带来的问题增加了空间开销：为进程建立数据结构额外的时间开销：管理和协调、跟踪、填写和更新有关数据结构、切换进程、保护现场更难控制：-协调多个进程竞争和共享资源如何预防-解决多个进程因为竞争资源而出现故障处理机的竞争尤为突出10进程的结构组成（进程映像）:程序、数据集合、进程控制块PCB(ProcessControlBlock)PCB是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤消其PCB。11PCB进程标识信息：进程的内部和外部标识符处理机状态信息：通用寄存器值、指令计数器值、程序状态字PSW值、用户栈指针值进程调度信息：进程状态、进程优先权、进程调度的其它信息其它信息：程序及数据地址、进程同步和通讯机制、资源清单、链接指针12PCB的组织方式之一--单一队列所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。如，Windows操作系统。13PCB的组织方式之二--表格结构PCB按进程状态不同，组织成不同的表格：就绪进程表、执行进程表（多机系统中）及阻塞进程表系统分别记载各PCB表的起始地址14PCB的表格结构15PCB的组织方式之三--多级队列PCB按进程状态不同用链接指针组成不同队列：就绪进程队列、阻塞进程队列（可按阻塞原因不同，分别组织）系统分别记载各PCB链表的起始地址16PCB多级队列172.2进程的状态18进程执行轨迹进程的轨迹：进程执行的指令序列，用以观察处理机的执行过程。例，假设内存中有3个进程A、B、C，他们的程序代码已全部装入内存。若A、B两进程需要执行12条指令，C进程需要执行4条指令，且C进程执行到第4条指令处必须等待I/O1920假设分派程序分派处理机需要依次执行指令序列：s+0,s+1,…,s+5进程A的执行轨迹为a+0,a+1,a+2,a+3,…进程B的执行轨迹为b+0,b+1,b+2,b+3,…进程C的执行轨迹为c+0,c+1,c+2,c+3,当它执行到c+3指令时遇到了I/O指令，需要释放处理机，进行输入/输出操作2129s+030s+131s+232s+333s+434s+51a+02a+1a+2a+3a+4a+535a+636a+737a+838a+939a+1040a+117s+08s+19s+210s+311s+412s+513b+014b+115b+216b+317b+418b+525c+026c+127c+228c+341s+0s+1s+2s+3s+4s+519s+020s+121s+222s+323s+424s+57b+648b+749b+850b+951b+1052b+1122两状态进程模型两状态：执行、未执行-进程获得处理机，进入执行状态;当时间片结束或其它某种原因，进程释放处理机，暂停执行，处于未执行状态。23两状态进程模型：队列形式24注：并非所有进程只要“未执行”就处于就绪（ready），有的需要阻塞（blocked）等待I/O完成“未执行”又可分为就绪和阻塞25进程的五状态执行状态（Running）就绪状态（Ready）阻塞状态（Blocked）新状态（New）终止状态（Terminated）261.新状态：进程已经创建，但未被OS接纳为可执行进程2.就绪状态：准备执行3.执行状态：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）4.阻塞状态：等待某事件发生才能执行，如等待I/O完成等5.终止状态：因停止或取消，被OS从执行状态释放2728①空新状态新创建的进程首先处于新状态。②新状态就绪状态当系统允许增加就绪进程时，操作系统接纳新建状态进程，将它变为就绪状态，插入就绪队列中。③就绪状态执行状态当处理机空闲时，将从就绪队列中选择一个进程执行，该选择过程称为进程调度，或将处理机分派给一个进程，该进程状态从就绪转变为执行。④执行状态终止状态执行状态的进程执行完毕，或出现诸如访问地址越界、非法指令等错误，而被异常结束，则进程从执行状态转换为终止状态。29⑤执行状态就绪状态分时系统中，时间片用完，或优先级高的进程到来，将中断较低优先级进程的执行。进程从执行状态转变为就绪状态，等待下一次调度。⑥执行状态阻塞状态执行进程需要等待某事件发生。通常，会因为进程需要的系统调用不能立即完成，如读文件、共享虚拟内存、等待I/O操作、等待另一进程与之通信等事件而阻塞。⑦阻塞状态就绪状态当阻塞进程等待的事件发生，就转换为就绪状态。进入就绪队列排队，等待被调度执行。30注：某些系统允许父进程在任何情况下终止其子进程。如果一个父进程被终止，其子孙进程都必须终止。-新状态终止-就绪状态终止-阻塞状态终止3132问题：多个进程竞争内存资源内存资源紧张无就绪进程，处理机空闲：I/O的速度比处理机的速度慢得多，可能出现全部进程阻塞等待I/O33解决方法采用交换技术：换出一部分进程到外存，以腾出内存空间采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）34对换技术,交换技术(Swapping）将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外存，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的数据和程序，换入内存。35进程的挂起状态进程被交换到外存，状态变为挂起状态36进程挂起的原因进程全部阻塞，处理机空闲。系统负荷过重，内存空间紧张。操作系统的需要。操作系统可能需要挂起后台进程或一些服务进程，或者某些可能导致系统故障的进程。终端用户的请求。父进程的需求。37被挂起进程的特征不能立即执行可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行使之挂起的进程为：自身、其父进程、OS只有挂起它的进程才能使之由挂起状态转换为其他状态38挂起与阻塞问题是否只能挂起阻塞进程？如何激活一个挂起进程？39挂起与阻塞区分两个概念：?进程是否等待事件，阻塞与否?进程是否被换出内存，挂起与否４种状态组合：就绪：进程在内存，准备执行阻塞：进程在内存，等待事件就绪/挂起：进程在外存，只要调入内存即可执行阻塞/挂起：进程在外存，等待事件40注:处理机可调度执行的进程有两种：新创建的进程或换入一个以前挂起的进程通常为避免增加系统负载，系统会换入一个以前挂起的进程执行。41挂起接纳激活就绪/挂起图2.12具有挂起状态的进程模型挂起时间片完新建就绪执行阻塞终止分派/调度事件发生事件等待完成激活阻塞/挂起事件发生42具有挂起状态的进程状态转换阻塞阻塞/挂起：OS通常将阻塞进程换出，以腾出内存空间阻塞/挂起就绪/挂起:当阻塞/挂起进程等待的事件发生时，可以将其转换为就绪/挂起就绪/挂起就绪：OS需要调入一个进程执行就绪就绪/挂起：一般，OS挂起阻塞进程。但有时也会挂起就绪进程，释放足够的内存空间新就绪/挂起（新就绪）：新进程创建后，可以插入到就绪队列或就绪，挂起队列。若无足够的内存分配给新进程，则需要新就绪/挂起43具有挂起状态的进程状态转换（续）阻塞/挂起阻塞：当阻塞/挂起队列中有一个进程的阻塞事件可能会很快发生，则可将一个阻塞/挂起进程换入内存，变为阻塞执行就绪/挂起：当执行进程的时间片用完时，会转换为就绪。或，一个高优先级的阻塞/挂起进程正好变为非阻塞状态，OS可以将执行进程转换为就绪/挂起状态所有状态终止：通常，执行终止。但某些OS中，父进程可以终止其子进程，使任何状态的进程都可转换为退出状态442.3进程的控制45两种执行模式系统模式（又称为系统态）、控制模式或内核模式：-具有较高的特权-运行系统特定的指令,包括读/写控制寄存器的指令、基本I/O指令以及与存储器管理有关的指令，及一些特定的内存区-内核模式下的处理机及其指令、寄存器和内存都受到完全控制和保护用户模式（或用户态）-具有较低的特权-用户程序一般运行在用户模式46模式切换用户模式系统模式：用户程序执行到一条系统调用，进入操作系统内核执行系统模式用户模式：执行完系统调用的功能，返回到用户程序特殊情况：程序执行到结束语句时，切换到系统模式，不再返回到用户程序47操作系统内核（Kernel）操作系统的核心，是基于硬件的第一层软件扩充，提供操作系统最基本的功能，是操作系统工作的基础。现代操作系统设计中，为减少系统本身的开销，往往将一些与硬件紧密相关的（如中断处理程序、设备驱动程序等）、基本的、公共的、运行频率较高的模块（如时钟管理、进程调度等）以及关键性数据结构独立开来，使之常驻内存，并对它们进行特殊保护。通常把这一部分称为操作系统的内核。48用户通过系统调用访问操作系统的功能，这些功能最终都通过操作系统内核实现。不同的操作系统对内核的定义和功能范围的设定是不同的。一般地，操作系统内核的功能可以概括地划分为资源管理功能和支撑功能。-资源管理：进程管理、存储管理和I/O设备管理-支撑功能：中断处理、统计、监测、时钟管理、原语操作等。49资源管理功能进程管理：进程创建和终止、调度、状态转换、同步和通信、管理PCB存储管理：为进程分配地址空间、对换、段/页管理I/O设备管理：缓存管理、为进程分配I/O通道和设备50支撑功能中断处理时钟管理原语（Primitive）:原子操作统计监测51进程控制原语进程切换创建与终止阻塞与唤醒挂起与激活52进程创建:原因提交新的批处理作业交互式用户注册操作系统提供服务父进程创建子进程53进程创建:步骤为进程分配一个唯一标识号ID主进程表中增加一个新的表项为进程分配空间:用户地址空间、用户栈空间、PCB空间。若共享已有空间，则应建立相应的链接。初始化PCB:进程标识、处理机状态信息、进程状态建立链接:若调度队列是链表，则将新进程插入到就绪或就绪/挂起链表建立或扩展其他数据结构54进程终止:原因批处理作业执行到“结束”语句交互式用户“注销”停止进程（应用程序）的执行遇到错误或故障55进程终止:具体原因正常结束超时终止,执行时间超过预计时间内存不足,无法为进程分配所需的内存空间越界访问企图使用未允许用的数据，或操作方式错计算错,如除零，或企图存储硬件允许的最大数超时等待某事件发生56进