西安交通大学操作系统复习.doc

OPERATING SYSTEM REVIEWCHAPTER 11操作系统定义：操控硬件的程序，用户与硬件的媒介，分配控制资源2操作系统目标：方便性（convenience），有效性（efficiency），（可扩充性开放性）3操作系统作用：资源管理（处理机管理，储存器管理，设备管理，文件管理，用户接口）；服务用户（提供接口）4操作系统分类(1)批处理(batch)：自动性，没有交互性。自动从一个job转移到另一个job。(2)分时(time-sharing)：允许多个用户同时使用，CPU在多个进程之间轮转，可及时响应用户需求。(3)实时(real-time)：实时性，对时间有严格的要求，对安全性要求高。(4)通用：同时具有两种或以上性质的操作系统。5操作系统特征(1)并发性(Concurrence): 并发是指两个或者多个事件在同一时间间隔内发生，在单处理机系统中，宏观上多道程序同时执行，微观上各个程序交替运行。并发与并行不同，并行是指两个或者多个事件在同一时刻发生。并发程序具有间断性、失去封闭性和不可再现性等特征。(2)共享性(Sharing): 共享是指在一段时间内多个并发进程交替使用有限的计算机资源，共同享有计算机资源，操作系统对资源要合理的分配和使用。共享资源有互斥共享方式和同时访问 方式。互斥访问方式是指当一个进程占有资源时，其他进程不能同时再使用这个资源，必须得等到资源被放弃时再使用。同时访问方式是指如程序段和磁盘等资源，可以由进程交替访问。(3)虚拟性(Virtual): 虚拟是指通过某种技术把物理实体转换成若干个逻辑对应物。例如，地址空间具有虚拟性，它是由内存空间通过划分段表/页表技术转换而来的。(4)异步性(Asynchronism): 异步性是指进程只要在相同的环境下，无论多少次运行，都会得到相同的结果。6相关技术(1)多道程序技术(multiprogramming)l 定义：当CPU正在处理的job需要等到I/O响应时，CPU并不会闲置，而是转去处理下一个job，直到之前的job在处理完IO后拿回CPU使用权。不可与用户交互。l 优点：提高CPU利用率，控制并发。(2)分时技术(time-sharing/multitasking)定义：logical extension of multiprogramming. The cpu executes multiple jobs by switching among them, but the switch so frequently that the users can interact with each program while it is running.CHAPTER 21操作系统接口(1)作业级接口(Command interface)：l 命令行(command line interface)l 批处理(batch):规定一种特殊的文件，通常该文件有特殊的扩展名，用户可预先把一系列命令组织在该文件中，一次建立多次执行l GUI：make mouse-based-window-and-menu system as interface(2)程序级接口(Program interface)系统调用(system call) 定义:system call provide an interface to the service made available by the operating system.操作系统内核提供的服务的接口。分类：进程管理process control文件操作file manipulation设备管理device manipulation信息维护information maintenance进程通信communication2操作系统结构(OS Structure)(1)简单结构(MS-DOS, original unix)l MS-DOS：interfaces and levels of functionality are not well separated.leave base hardware accessible.l UNIX：series of interfaces and device drivers. Monolithic structure is difficult to implement.(2)分层结构(layered):从资源管理的角度出发，把操作系统分为若干层次，在某一层上只能调用低层次上的代码，使模块的调用更加有序。有利于系统维护和可靠。(3)微内核结构(microkernel):去除内核中不必要的部分，将这些部分在用户模式下实现，从而只给内核最基本的功能。微内核提供给客户程序与运行在用户空间的各种服务提供通信(communication).MACHCHAPTER 3引入进程原因在多道程序设计的环境下，程序是并发执行的，它破坏了程序的封闭性和可再现性，使得程序和计算不再一一对应且由于资源共享，导致在各个程序之间可能存在相互制约的关系，出现了许多新的特征：动态性、并发性、独立性和异步性。程序(进程)并发的特点:间断性失去了封闭性不可再现性程序这个静态概念已经不能如实反映程序活动的这些特征。为此引入进程这个概念来描述系统和用户的活动。进程的概念：程序的一次执行进程的特性：(1)动态性：有生命周期(2)并发性：并发执行(3)独立性：独立获得资源、独立运行单位(4)异步性：推进速度不可预知道、执行结果不确定(5)结构性：由程序段、数据段和PCB组成进程的状态(process state)：进程的组成程序(text section),数据(data section),PCB(process control blocks)PCB的定义：记录OS所需的、用于描述进程的当前情况以及控制进程运行的全部信息，是进程存在的唯一标志，常驻内存。PCB的内容：进程标识符；处理机状态（CPU现场）；进程调度信息：状态、优先级、时间、事件；进程控制信息：地址、通信信息、资源。Program counter指明进程的下一条指令CPU registers 中断发生时，所有的寄存器需要被存储。CPU-scheduling info 包括进程优先级，进程队列指针等调度信息Memory-management info 包括基本寄存器的值，页表等信息Accounting info 记录进程运行的时间，使用了多少CPU等IO status info 包括分配给进程的设备进程与程序的区别联系（1）进程是程序的一次执行，是一个动态的概念；而程序是一组有序的指令， 是一种静态的概念。即进程是程序执行的动态过程，而程序则是进程运行的静态文本。（2）一个进程可以执行一个或几个程序，同一个程序也可能由几个进程同时执行。（3）程序可长期保存，而进程是有生命周期的。（4）进程是并发实体, 而程序则不是。进程与线程的区别联系（1）调度方面：线程作为调度分派的基本单位，而进程则是资源分配和调度的一个基本单位；（2）并发性方面：进程之间可以并发，一个进程的多线程之间也可并发执行；（3）拥有资源方面：进程作为拥有资源的基本单位，而线程只拥有少量必不可少的资源，但它可以访问所属进程的资源（4）系统开销方面：进程切换要涉及到进程环境的切换，开销较大，而线程间切换只需保存和设置少量的寄存器内容，开销远小于进程切换开销进程的控制(1) 进程控制由操作系统内核完成(2) 内核通过执行相应的原语(primitive)来实现进程的控制(3) 进程控制原语：创建，终止，阻塞，唤醒，挂起，激活创建原语完成以下工作：申请一个空PCB，初始化PCB中项目，把PCB插入就绪队列撤消原语完成以下工作：根据ID在PCB链中查找相应PCB，检查进程状态。若是执行状态则终止进程；终止其子进程；回收资源；撤销PCB阻塞原语：当出现阻塞事件，将状态改为阻塞状态，进入阻塞队列唤醒原语：将阻塞进程唤醒，状态改为READY，插入就绪队列。挂起原语：进程从内存转到外存，改变相应状态激活原语：进程从外存转到内存，改变相应状态CHAPTER 4线程(thread)定义：A thread is a basic unit of CPU utilization.处理机调度的基本单位，是进程内的一个可调度实体，又称轻量级进程。引入目的：提高系统效率，提高资源利用率，减少进程并发执行时所付出的时空开销，使操作系统有更好的并发性。(一个进程中的所有线共享同样的code,data,file，比如一个web server，对于所有的request，反应几乎一样，若为每个request新创建一个进程，会造成code,data,file的重复，造成空间，时间资源的浪费)线程包括：线程ID，当前指令指针(PC)，寄存器集合，堆栈。用户级线程和内核支持线程：(1)用户线程(user thread)：存在于用户空间中，其创建、撤消和切换都不需系统支持。(2)内核支持线程(kernel thread)：是依赖于内核的，其创建、撤消和切换都是由内核实现的。Multithreading modelsMany to one: many user level threads to one kernel thread.(因为只有一个线程可以access内核，因此多个线程不可以同时在多个内核上运行)One to one: each user thread to a kernel thread(多个线程可以在多个内核上同时运行，一个阻塞也不会影响其他，但每一个用户线程均要创立一个内核线程，额外开销大，限制应用程序的性能)Many to many: many user level threads to a smaller or equal number of kernel threads.(开销不大，而且线程可以并发)CHAPTER 5三级调度(1)高级调度：Long-term scheduler (job-scheduler): select a process from the pool and loads them into memory for execution.从job pool里选一个进程加载在内存里(2)低级调度：Short term scheduler (CPU-scheduler): select a process from the processes in memory that are ready to execute and allocates the CPU to the process.从内存中选择一个进程给CPU执行(3)中级调度：Mid-term scheduler: remove processes from memory and later reintroduce it into memory. 把内存中的进程swap出去再swap进来调度时机(1)现运行进程任务完成或出现异常(2)现运行进程因某种原因由执行变成阻塞状态(3)时间片用完(4)采用可剥夺调度方式时，有更高优先级进程进入就绪队列调度参数(scheduling criteria)周转时间(turnaround time)等待时间(waiting time)响应时间(response time)调度算法FCFS(first-come first-serve)SJF(shortest-job-first)Priority(优先权调度)Round-Robin(时间片轮转)Multilevel Queue(多级队列)：根据进程的性质将就绪队列分为几个队列，每个队列有不同的调度算法，队列与队列之间的调度一般为优先级调度或时间片。Multilevel Feedback-Queue(多级反馈队列)：主流OS使用此算法。与多级队列算法不同的是，多级反馈队列允许进程转移到其他队列。因此多级反馈队列还要设计进程的升级与降级规则。（此处还有多处理机的调度，线程的调度）CHAPTER 6基本概念临界区（critical section）：一段代码，用来修改临界资源，只能有一个进程处于临界区进入区（entry section）：请求进入临界区的程序退出区（exit section）：紧跟着临界区后的程序剩余区（remainder section）：剩下的程序解决临界区问题的三个要求互斥(Mutual exclusion)：保证安全有空让进(Progress)：保证资源利用率有限等待(Bounded waiting)：防止饥饿Peterson算法(1) 只能控制两个进程(2) 程序P0: flag0 = true; turn = 1; while (flag1 = true & turn = 1) / busy wait / critical section flag0 = false; / end of critical sectionP1: flag1 = true; turn = 0; while (flag0 = true & turn = 0) / busy wait / critical section flag1 = false; / end of critical section(3) 程序分析满足互斥：如果两个进程都在临界区，则FLAGi=FLAGj=1。但turn必然会取0或1中的一个，因此必有一个while满足条件，故必有一个进程在while循环中等待。因此假设错误，不可能有两个进程同时在临界区。满足有空让进和有限等待：假设Pi已经准备好进入临界区，正在while循环中等待。对于Pj的以下三种情况：l 若Pj未准备好，则FLAGj = 0，那么Pi的while条件不再满足，进入临界区。l 若Pj准备好了，且也在while循环中，则turn = 0, 那么Pi的while条件不再满足，进入临界区。l 若Pj刚出临界区，则FLAGj = 0，那么Pi的while条件不再满足，进入临界区。因此，只要Pj不在临界区了，Pi就可以进入临界区，因此满足有空让进；当Pj执行完临界区，Pi就可以进入临界区，满足有限等待。信号量（Semaphore）与PV操作信号量：A Semaphore is a special integer variable, it can be accessed only through two standard atomic operations。P操作( wait)：request a resourceWait(S) while S = 0 ; / no-opS-;V操作( signal)：release a resourcesignal (S) S+;/P.V操作必须成对出现，有一个P操作就一定有一个V操作/当为互斥操作时，它们处于同一进程/当为同步操作时，则不在同一进程中出现/对于前后相连的两个P(S1)和P(S2) ，顺序是至关重要的:同步P操作应该放在互斥P操作前,而两个V操作顺序则无关紧要信号量实现互斥为临界资源设置一个互斥信号量mutex，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间信号量实现同步P.V操作必须成对出现，有一个P操作就一定有一个V操作三个经典问题（1）生产者消费者（2）读者写者（3）哲学家吃米饭While (true) wait ( chopsticki ); wait ( chopStick (i + 1) % 5 ); / eat signal ( chopsticki ); signal (chopstick (i + 1) % 5 ); / think管程（Monitor）的定义：一个管程定义了一个数据结构和能为并发进程调用的在该数据结构上的一组操作过程，这组互斥操作的过程，能同步进程和改变管程中的数据。 管程实现互斥：外部等待队列。一个管程的程序在运行一个线程前会先获取互斥锁，直到完成线程或是线程等待某个条件被满足才会放弃互斥锁。管程实现同步：内部设置条件变量。一个条件变量就是一个线程队列(queue), 其中的线程正等待某个条件变为真。CHAPTER 7 DEADLOCK死锁(deadlock)的概念计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。死锁产生原因众多进程竞争有限资源；进程推进顺序不合适。死锁产生的必要条件互斥使用（Mutual exclusion）不可剥夺（No preemption）请求保持（Hold and wait） 环路等待（Circular wait）解决死锁的方案（1）设计无死锁的系统：预防、避免（2）允许出现死锁然后排除：检测并解除（3）置之不理资源分配图（resource-allocation graph）中的概念辨析没有环路，则没有死锁有环路，可能有死锁也可能没有若每种资源只有一个实例，有环路就有死锁死锁的预防破坏四个必要条件之一，通常是破坏第三、四个条件。（1）资源的静态分配方法：进程运行前一次性申请全部资源,破坏请求和保持条件.（2）资源的顺序分配法：系统的全部资源进行编号，只允许按编号顺序递增地申请，破除环路待。（3）一个已占有资源的进程,若要申请新的资源，必须先放弃已占有的资源，破坏请求保持条件。死锁的避免每当进程申请资源时，都根据一定的算法判断是否安全安全状态：当多个进程动态申请资源时，系统按某一顺序逐次地为每个进程分配所需资源，使每个进程都可以在最终得到最大需求量后依次顺利完成。不安全状态：可能死锁避免死锁的关键：让系统在动态分配资源的过程中，不要进入不安全状态银行家算法死锁的解除：删除法：删除死锁进程，将其资源分给其他进程剥夺法：剥夺某些进程的资源CHAPTER 8 MAIN MEMORY一些概念l 逻辑地址：an address generated by cpul 物理地址：an address seen by the memory unitl 内存管理单元(MMU-memory management unit): 包括一个基地址寄存器(relocation register)和一个加法器，在程序运行时map虚拟地址到物理地址。l Compiler bind symbolic address to reloacatable addressl Loader/linkage editor bind relocatable address to absolute address重定位动态重定位：在程序执行期间每次访问内存之前进行重定位。这种变换是靠硬件地址变换机构实现的。通常采用重定位寄存器，其中放有当前正在执行的程序在内存空间中的起始地址，而地址空间中的代码在装入过程中不发生变化。静态重定位：在目标程序装入内存时，由装入程序对目标程序中的指令和数据的逻辑地址改成物理地址。对每个程序来说，这种地址变换只是在装入时一次完成，在程序运行期间不再进行重定位。内存为程序分配空间的四种方式（1） 连续分配方式（contiguous memory allocation）单一连续分配固定分区分配：分区容量和数目固定不变，大小可不等，每个分区容纳一道作业可变分区分配：动态分区，作业装入内存时才建立分区（根据作业的大小）/四种动态分区分配算法：l 首次适应(first fit):allocate the first holel 最佳适应(best fit):allocate the smallest holel 最差适应(worst fit): allocate the largest holel Next fit: 从刚刚分配出的内存开始查找合适的hole分配可重定位分区分配：重定位寄存器(relocation register)、紧凑技术（把进程统一移向一边）（2） 基本分页存储管理方式(paging) 分页引入：动态分区方式产生“外碎片”，采用紧凑技术要付出很大开销，于是引入了页式存储管理。分页定义A memory-management scheme that permits the physical address space of fitting memory to be noncontiguous.分页原理：l 将物理内存分割为等份，叫做物理块(frame)，大小一般为2的次方l 将逻辑地址分割为等份，叫做页(page)，大小与frame相等l 建立page与frame的关系映射，叫做页表(page table)，页表在内存里。l 地址转换是在进程执行过程中进行的。分页的地址变换过程当一个进程转入执行状态时，其页表的始址和长度从其PCB中装入页表寄存器。当进程要访问某个逻辑地址中的指令或数据时，地址变换机构自动地将逻辑地址分为页号和页内地址两部分，并将页号与页表寄存器中的页表长度比较，若页号不小于页表长度，便产生越界中断，否则以页号为索引，去检索页表，从中得到该页的物理块号，送入物理地址寄存器与页内地址拼接，形成物理地址。快表(TLB-translation look-aside buffer)为了提高访问速度，存放被频繁访问的页面的页表项。先查快表，没有查到再查页表。快表很小，访问很快，造价高。内存访问时间的计算(effective access time)Effective access time = 快表命中率*（快表时+内存时）+（1-快表命中率）*（快表时+2*内存时）（3） 基本分段存储管理方式(segmentation)硬件实现定义：a memory-management scheme that support the user view of memory. A logical address space is a collection of segments. Each has a name and a length.（4） 段页式存储管理方式对换技术(swapping)定义：把主存中暂时不能运行的进程调出到外存,以便腾出足够的内存空间，再将具备运行条件的进程调入内存。作用：从逻辑上扩充内存空间,从而使整个系统资源利用率提高.整体对换:以进程为单位,进程对换部分对换:页面对换,分段对换碎片(fragmentation)内部碎片(internal fragmentation)：已被分配出去的内存空间大于请求所需的空间外部碎片(external fragmentation)：还没有被分配出去但由于太小而无法分配给新进程的空闲块分区的保护：(1)界地址寄存器一对界地址寄存器存放分区的上、下界地址，物理地址需满足如下关系：上界地址寄存器内容= 物理地址 =下界地址寄存器内容(2)基址限长寄存器(base register and limit register):这两个寄存器只有os才可以修改 基址寄存器: 分区的首址 限长寄存器: 作业地址空间的长度物理地址 基址寄存器内容 = 限长寄存器内容(3)分页管理中在页表中的每一项设置保护位CHAPTER 9VIRTUAL MEMORY虚拟内存(virtual memory)具有请求调入功能和置换功能、能从逻辑上对内存容量加以扩充的存储器系统称为虚拟存储器Virtual memory is a technique that allows the execution of processes that may not be completely in memory.Virtual memory is the separation of user logical memory from physical memory.请求分页(demand paging)定义：基本分页的基础上增加请求调页功能 和页面置换功能。作业被调度投入运行前，只装入部分页面到内存，其他各页，根据请求而被装入。页表增加以下内容：存在位P、访问字段A、修改位M、外存地址。地址变换过程页面置换算法(page replacement algorithm)l FIFO：换出去最老的一页l 理想页面置换算法OPT(optimal page replacement)：换出去在reference string中最远的页，也就是未来最后才出现页l 最久未使用算法LRU(least-recently-used)：换出去最久没有被使用的页，可以用counter 或 stack 来实现。l LRU近似算法a) 附加引用位算法(additional reference bit)：每个页设置8个附加位，每次引用时右移（丢掉末尾，首位补一或补零，置换出八位数字最小的那个页）b) 二次机会算法(second chance)：设置一个附加位，换出附加位是0的，附加位是1的给一次机会，然后置0c) 增强型二次机会算法(enhanced second chance)：设置两个附加位，一个表示引用一个表示修改。颠簸(thrashing)定义：页面频繁地调入或换出，CPU利用率低下解决方案：l 采用局部置换：若一个进程开始颠簸，采用局部置换，不会使其它进程也发生颠簸l 给进程提供足够的物理块：根据进程执行的局部模型，来确定进程真正需要多少物理块l 一种更加直接的防止颠簸的方法是控制缺页频率（ Page-Fault Frequency ）工作集模型(working-set model)：用参数定义一个工作集窗口，如果工作集窗口中的页面不再活跃，移动工作集。预调页(prepaging):当一个新进程开始进入内存时，会发生很多缺页中断。可以使用工作集模型，在挂起一个进程时记录下工作集，然后resume时先调入工作集里所有的页。CHAPTER 10FILE-SYSTEM INTERFACE文件定义具有文件名的一组相关信息的集合。A file is a named collection of related information that is recorded on secondary storage.文件的属性信息(file attributes)Name identifier location type protection size time, date, and user identification文件的操作(file operations): 用户通过文件系统提供的系统调用实施文件的操作l 创建文件：分配磁盘空间，创建文件目录入口l 写文件：从目录中找到文件地址，置写指针l 读文件：在文件目录中找到文件入口，置读指针l 文件指针重定位(repositioning within a file)l 删除文件：在目录中找到文件，释放磁盘空间，删除文件目录信息l 删除文件内容(truncating a file)文件的逻辑结构(file structure)分为有结构文件（记录式文件）、无结构文件（流式文件）。记录式文件：顺序文件：记录通常是定长的，顺序存取；索引文件：记录通常是变长的，方便直接存取；索引顺序文件：前二者的结合，减少了索引表所占的空间文件的访问方式(access method)顺序访问（磁带模型）/随机访问（磁盘模型）/索引表访问目录(directory)：即文件夹,是用来记录每个文件在磁盘上的地址的数据结构.它保存的不是用户数据,而是关于文件及文件系统的信息,即文件夹里面存放的是从文件到文件所在磁盘地址的映射. FCB的有序集合，其中的每个FCB叫作一个目录项。目录管理的目标：实现按名存取文件，提供快速的目录查询手段以提高对文件的检索速度，并能为文件的共享和重名提供方便。目录结构单级目录结构；l 两级目录结构： 一级称为主文件目录（MFD），给出用户名，用户子目录所在的物理位置；二级称为用户文件目录（UFD，又称用户子目录），给出该用户所有文件的FCBl 多级目录结构：当前目录（工作目录）、绝对路径、相对路径；当前目录(current directory):contain most of the files that are of current interest to the process绝对路径(absolute path):从根目录开始到指定文件的路径；相对路径(relative path):从当前目录出发到指定文件的路径。目录查询：系统利用用户给定的路径名对目录进行查询，找到对应的FCB或索引结点，然后找到具体的文件提高目录检索效率将文件名和描述信息分开（如UNIX的iNode）哈希表文件的保护/此处的复习PPT不知道哪来的实现分级的文件保护.第一级是要区分用户.第二级是区分文件的访问权限.实现基于用户身份的文件保护的一个方法是为每个文件或者目录增加一个访问控制表(access control list),列出不同用户对该文件或者目录的访问权限.当用户请求访问一个文件时,OS首先检查其访问控制表,看该用户有无相应的访问权限.文件共享/此处的复习PPT同样不知道在说什么CHAPTER 11 FILE-SYSTEM IMPLEMENT文件系统：定义：OS中与文件管理有关的部分软件及被它们管理的文件和文件属性的集合。组成部分A collection of files: storing related dataA directory structure: organizing and providing information about all the files in the sytemFCB（file-control block）文件控制表：与文件一一对应。其基本的内容包括文件名、文件的物理地址、文件的逻辑结构、物理结构、文件的长度、存取权限、文件的建立日期、修改日期及时间、连接计数文件主标识符等。文件的物理结构（文件在磁盘上的分配方式）l 连续分配Contiguous allocation方法：每个文件在磁盘上占据一片连续的blocks优点：简单、顺序访问速度快、支持随机存取缺点：外碎片、空间利用率低、不利于文件的动态增长l 链接分配Linked allocationa) 隐式链接：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块消除了外碎片、允许作业动态增长；可靠性差、只适于顺序访问b) 显式链接：文件分配表FAT（整个磁盘只有一张）储存了链接的关系不支持高效的随机存取，FAT表占用空间l 索引分配Indexed allocation每个文件建立一张索引表，指出分配给该文件的所有物理块号支持高效随机存取、消除了外碎片、允许文件动态增长；但索引表占用较多空间文件存储空间的管理(free-space management)l 空闲表法(counting)：适用于连续分配。系统建立一张空闲表，每个表项对应一个空闲区，登记的该区的起始块号和块数等。分配算法：首次适应、最佳适应等。l 空闲链法(linked list)：把空闲块组织成一个链接文件l 位示图法(bit vector)：适用于所有分配方式l 成组链接法(grouping)：将一个文件卷的所有空闲盘块按固定大小（如每组100块）分成若干组，并将每组的盘块数和该组所有盘块号记入前一组的最后一个备用块内，第一组的盘块数（可小于100）和该组所有的盘块号记入超级块的空闲盘块号栈中。/文件的物理结构，文件操作的系统实现，目录检索，文件的访问方式与文件结构之间的关系。CHAPTER 12DISK ATTACHMENT磁盘访问的时间(random access time)包括 寻道时间(seek time)：磁头移动到指定磁道旋转时间(rotational latency)：等待指定扇区从磁头下旋转经过数据传输时间：数据在磁盘与内存之间的传输时间磁盘调