操作系统--windows(个人总结版).pdf

-1-操作系统 一、重要知识点归纳.-2-二、操作系统绪论.-7-三、进程.-8-四、进程同步.-11-五、调度和死锁.-12-六、存储管理.-14-七、设备管理.-18-2-一、一、重要知识点归纳重要知识点归纳 操作系统发展过程 1、人工操作方式 2、单道批处理系统 3、多道批处理系统 4、分时系统 5、实时系统 操作系统基本特征 并发、共享、虚拟、异步 并发和共享是操作系统的两个最基本特征 程序独占处理机顺序执行时特征 顺序性 封闭性 可再现性 程序并发执行特征 间断性 失去封闭性 不可再现性 进程：可并发执行的程序在一个数据集合上的运行过程 动态性、并发性、独立性、异步性 进程的三种基本状态 就绪状态（R 态）-只要获得 CPU，就可立即执行 执行状态（E 态）-只有一个进程处于执行态 阻塞状态（B 态）-缺少某个资源 -3-进程控制块 PCB 初始化包括 1、初始化标识信息 2、初始化处理机状态信息 3、初始化处理机控制信息 同步机制应遵循的规则 空闲让进 忙则等待 有限等待 让权等待 信号量机制（wait(mutex)和 signal(mutex)必须成对出现 1、整型信号量（P、V 操作）wait（s）和 signal（s）操作 2、记录型信号量 3、AND 型信号量 4、信号量集（Swait（s,d,d）、Swait（s,1,1）、Swait（s,1,0）经典进程的同步问题 1、生产者消费者问题 2、哲学家进餐问题 3、读者写者问题 进程通信的类型 1、共享存储器系统 2、消息传递系统 3、管道通信 消息传递通信的实现方法 1、直接通信方式 2、间接通信方式 -4-线程：比进程更小的能独立运行的基本单位 一般而言，线程自己不拥有系统资源（也有一点必不可少的资源）处理机调度的层次 1、高级调度 2、低级调度 3、中级调度 进程调度方式 1、非抢占方式 2、抢占方式(1).优先权原则(2).短作业优先原则(3).时间片原则 进程调度算法 1、先来先服务和短作业优先调度算法（周转时间=完成时间-到达时间、带权周转时间=周转时间/服务时间）(1).先来先服务调度算法(2).短作业优先调度算法 2、高优先权优先调度算法(1).非抢占式优先权算法(2).抢占式优先权调度算法(3).高响应比优先调度算法-优先权=（等待时间+要求服务时间）/要求服务时间 3、基于时间片的轮转调度算法 (1).时间片轮转法 (2).多级反馈队列调度算法 产生死锁的原因 1、竞争资源(1).竞争非剥夺资源(2).竞争临界资源 2、进程间推进顺序非法 产生死锁的必要条件 1、互斥条件 2、请求和保持条件 3、不剥夺资源 4、环路等待条件 预防死锁的方法 1、摒弃“请求和保持条件”（一次性申请全部资源）2、摒弃“不剥夺条件”（再次提出申请资源不能满足时，释放所有资源）3、摒弃“环路等待条件”（资源按类型进行线性排队，并赋予不同序号）-5-利用银行家算法避免死锁 死锁的解除 1、剥夺资源 2、撤销进程 多级存储结构 1、CPU 寄存器（寄存器）2、主存（高速缓存、主存、磁盘缓存）3、辅存（磁盘、可移动存储介质）程序的装入 1、绝对装入方式 2、可重定位装入方式 3、动态运行时装入方式 程序的链接 1、静态链接方式 2、装入时动态链接 3、运行时动态链接 连续分配方式（为一个用户程序分配一个连续的内存空间）1、单一连续分配 2、固定分区分配 3、动态分区分配 分区分配算法(1).首次适应算法(2).循环首次适应算法(3).最佳适应算法(4).最坏适应算法(5).快速适应算法 4、可重定位分区分配 基本分页存储管理方式 地址结构：31 12 11 0 页号 P 位移量 W 基本分段存储管理方式 段号 段内地址 31 16 15 0 分页和分段的主要区别 1、页是信息的物理单位 -6-2、页的大小固定且由系统决定 3、分页的作业地址空间是一维的 虚拟存储器的特征 多次性、对换性、虚拟性 页面置换算法 1、最佳置换算法 2、先进先出页面置换算法 3、最近最久未使用置换算法 4、CLOCK 置换算法 设备与控制器之间的接口 1、数据信号线 2、控制信号线 3、状态信号线 I/O 控制方式 1、程序 I/O 方式 2、中断驱动 I/O 控制方式 3、直接存储器（DMA）I/O 控制方式 DMA 控制器的组成(1).命令/状态寄存器 CR(2).内存地址寄存器 MAR(3).数据寄存器 DR(4).数据计数器 DC 4、I/O 通道控制方式 磁盘访问时间 Ta Ta=Ts+Tr+Tt=Ts+1/2r+b/rN 寻道时间 Ts=m*n+s 移动 n 条磁道、启动磁臂时间 s 旋转延迟时间 Tr 传输时间 Tt=b/rN r 为磁盘每秒钟的转数、b 为字节数 磁盘调度算法 1、先来先服务 2、最短寻道时间优先 3、扫描算法 4、循环扫描算法 5、NstepScan 和 FSCAN 调度算法 文件系统 1、FAT12：每个分区容量为 2M，只能支持 8+3 格式文件名 2、FAT16：最大分区容量为 2G -7-3、FAT32：不支持容量小于 512M 分区、单个文件的长度不能大于 4G、不能保持向下兼容 4、NTFS：支持长文件名（256 个字符）、数据保护和数据恢复 UNIX 的调度算法：动态优先数轮转调度算法 二、二、操作系统操作系统绪论绪论 操作系统的发展过程 1.手工操作阶段（40 年代）2.单道批处理阶段（50 年代）3.多道批处理（60 年代初）4.分时系统（60 年代中）5.实时操作系统（60 年代中）多道批处理系统的优点 1.资源利用率高。2.系统吞吐量大。多道批处理系统的缺点 1.平均周转时间长。2.无交互能力。推动多道批处理系统形成和发展的动力是提高资源利用率和系统吞吐量。推动分时系统形成和发展的主要动力是用户的需要：交互、共享主机、方便上机。分时系统是指在一台主机上连接多个带有显示器和键盘的终端，同时允许多个用户通过自己的键盘，以交互的方式使用计算机，共享主机中的资源。分时系统的特征 1.多路性：允许同一主机联接多台终端。2.独立性：每一用户独占一个终端；每个用户感觉不到其他用户的存在。3.及时性：用户请求能及时响应。4.交互性：可进行广泛的人机对话。实时系统（RealTime System）是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。实时系统的特征：1.多路性 2.独立性 -8-3.及时性（开始截止时间/完成截止时间）4.交互性（仅限于访问专用服务程序）5.可靠性（多级容错措施保障系统和数据安全）操作系统的特性 1.并发（Concurrence）2.共享（Sharing）3.虚拟（Virtual）4.异步性（Asynchronism）并发性：引入进程、线程 据资源属性的不同，有两种资源共享方式：1.互斥共享方式（临界/独占资源）2.同时访问方式 并发和共享是 OS 的两个最基本的特性，二者互为条件！处理机管理包括以下几方面：进程控制、进程同步、进程通信、调度 存储器管理具备下列功能：1.内存分配 2.地址映射：把程序中的逻辑地址映射为物理地址 3.存储保护：使多道程序间互不干扰 4.存储扩充：用辅存扩充主存，实现“虚拟存储器”设备管理的功能 1.缓冲管理：为设备提供缓冲区以缓和 CPU 同设备的 I/O 速度不匹配的矛盾。2.设备分配 3.设备驱动：为设备提供驱动程序。4.设备独立性和虚拟设备 文件系统管理的功能：1.文件存储空间管理。2.目录管理：为了用户方便找到他所需的文件。3.文件的读写管理和存取控制：存取控制就是防止文件被非法使用。三、三、进程进程 程序顺序执行的特点 1.顺序性：一个程序开始执行必须要等到前一个程序已执行完成。2.封闭性：程序运行时独占计算机资源，资源的状态只能由本程序修改。程序一旦开始执行，-9-其计算结果不受外界因素影响。3.可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。程序并发执行的特点 1.间断性 2.失去程序的封闭性 程序在并发执行时，是多个程序共享系统中的资源，因此这些资源的状态将由多个程序来改变。3.不可再现性 进程是可并发执行的程序在一个数据集合上的运行过程。进程是指进程实体的运行过程。程序是静态的，进程是动态的；程序是永久的，进程是暂时的；进程是由程序和数据、进程控制块 PCB 三部分组成的。进程的特征 1.结构性：由程序段、数据段、进程控制块三部分组成；2.动态性：进程是程序的执行过程；3.并发性：多个进程可同存于内存中，能在一段时间内同时运行；4.独立性：独立运行的基本单位，独立获得资源和调度的基本单位；5.异步性：各进程按各自独立的不可预知的速度向前推进。进程的三种基本状态 1.就绪状态（Ready）：存在于处理机调度队列中的所有进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。2.运行状态（Running）：正在运行的进程所处的状态为运行状态。单处理机系统 只有一个进程处于该状态 多处理机系统有多个进程处于运行状态 3.等待/阻塞/睡眠状态（Wait/Blocked）：若一进程正在等待某一事件发生（如等待输入输出工作完成），这时，即使给它 CPU，它也无法运行，称该进程处于等待状态（阻塞、睡眠、封锁状态）。进程控制块（PCB）PCB 是 OS 中最重要的记录型数据结构。PCB 是 OS 感知进程存在的唯一标志。进程与 PCB 是一一对应的。PCB 随进程创建而建立，随进程结束而回收。PCB 应常驻内存。进程描述信息：进程标识符(process ID)：唯一，通常是一个整数 -10-进程名：通常基于可执行文件名（不唯一）用户标识符(user ID)：进程组关系 原语：由多条指令组成，是一种特殊的系统功能调用，它可以完成一个特定的功能。原语的特点：1.执行时不可中断 2.不可并发 3.在管态下执行，常驻内存 进程创建 1.申请空白 PCB 2.为新进程分配资源 如内存 3.初始化进程控制块 4.将新进程插入就绪队列 进程终止的事件：1.正常结束 2.异常结束 越界错误 保护错 特权指令错 非法指令错 I/0 故障 等 运行超时 等待超时 算术运算错 3.外界干预:操作员或 OS 干预；父进程请求；父进程终止，子孙进程被终止。进程阻塞是进程自身的一种主动行为。进程阻塞或唤醒的原因 1.请求系统服务：如请求打印机 2.启动某种操作：如 I/O 操作 3.新数据还未到达：合作进程之间需要数据传递 4.无新工作可做：如发送进程发送完数据后 线程是进程中的一个实体，是被系统独立调度的基本单位。引入进程的目的是为了使多个程序更好的并发执行，改善资源利用率、提高系统效率。进程是一个资源分配的基本单位。进程是一个可独立调度和分派的基本单位。线程的特征 1.结构性：-11-TCB：标识、现场信息(寄存器、PC、栈指针)、调度信息(状态、优先级)数据块：过程参数、数据、系统与用户堆栈 2.并发性：同一进程中的各线程在同一主存空间，可以共享进程中的所有资源（数据、设备、文件），线程间通信方便。3.共享性：同一进程的各线程 4.动态性：有生命期，有状态变化，可创建子线程 系统调度的基本单位是线程而不是进程,每当创建一个进程时，至少要同时为该进程创建一个线程，否则该进程无法被调度执行。线程状态：运行、就绪和阻塞三种状态。线程的状态转换类似于进程。四、四、进程同步进程同步 临界资源(Critical Resource/CR)：一次仅允许一个进程访问的资源。临界区(Critical Section/CS)：临界段，在每个程序中，访问临界资源的那段程序。临界区的调度原则：1.一次至多允许一个进程进入临界区内 2.一个进程不能无限地停留在临界区内 3.一个进程不能无限地等待进入临界区 同步机制应遵循的规则：1.空闲让进 2.忙则等待 3.有限等待 4.让权等待 信号量(Semaphore)机制 1、整型信号量 定义为一个整型量，由两个标准原子操作 wait(S)（P 操作）和 signal(S)（V 操作）来访问。整型信号量出现“忙等”现象。2、记录型信号量 3、AND 型信号量 AND 信号量是针对进程间共享多个资源；AND 同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未分配给进程，其它所有可能为之分配的资源，也不分配。4、信号量集 信号量集是指同时需要多种资源、每种占用的数目不同，且可分配的资源还存在一个临界值时的信号量处理。-12-经典的进程同步问题 1.生产者/消费者问题 2.读者/写者问题 3.哲学家进餐问题 一个管程包含一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。进程通信类型 1.共享存储器系统(Shared-Memory System)进程间通过共享某些数据结构或共享存储区进行通信。2.消息传递系统(Message Passing System)进程间的数据交换以格式化的消息为单位，程序员利用系统的通信原语实现通信。如：网络中的报文。消息通信分为直接通信和间接通信。3.管道(Pipe)通信(共享文件方式)管道，是指用于连接一个读进程和一个写进程的文件，称 pipe 文件。五、五、调度和死锁调度和死锁 处理机调度分为三个层次：高级调度 中级调度 低级调度 进程调度的两种方式：1.抢占方式(Preemptive Mode)允许调度程序根据某种原则，暂停正在执行的进程，将处理机重新分配给另一进程。抢占原则：优先权原则、短作业（进程）优先原则、时间片原则。2.非抢占方式 CPU 调度过程。即进程切换的步骤：1.保存现场：顺序保存，最后一步保存 PSW 2.选择要运行的程序（如果没有就绪进程，系统会安排一个闲逛进程(idle)，没有其他进程时，该进程一直运行，在执行过程中可接收中断）3.恢复现场：最后一步恢复选中进程的 PSW 调度算法是指根据系统的资源分配策略所规定的资源分配算法。调度算法：1.先来先服务调度算法 FCFS FCFS 调度算法比较有利于长作业（进程），而不利于短作业（进程）。-13-FCFS 调度算法有利于 CPU 繁忙型的作业，不利于 I/O 繁忙型的作业。2.短作业优先调度算法 SJ(P)F 能有效地降低作业的平均等待时间，提高系统吞吐量。对长作业不利 未考虑作业的紧迫程度 作业的估计运行时间不准确 3.高优先权调度算法 HPF 响应比 Rp=1+（作业等待时间/作业处理时间）4.基于时间片的轮转调度算法 RR 各种调度算法性能对比 实时调度算法的分类 1.非抢占式调度算法 非抢占式轮转调度算法 非抢占式优先调度算法 2.抢占式调度算法 基于时钟中断的抢占式优先权调度算法 立即抢占的优先权调度算法 常用的两种实时调度算法 1.最早截止时间优先算法 EDF 2.最低松弛度优先算法 LLF(Least Laxity First)松弛度必须完成的时间本身运行的时间当前时间 死锁产生的原因 1.竞争资源引起进程死锁 竞争非可剥夺资源 竞争临时性资源(进程通信)2.进程推进顺序不当引起死锁 产生死锁的必要条件 -14-1.互斥条件：涉及的资源是非共享的。2.不剥夺条件：不能强行剥夺进程拥有的资源。3.请求和保持条件：进程在等待一新资源时继续占有已分配的资源。4.环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。死锁的预防方法：破坏产生死锁的四个必要条件之一。1、破坏请求和保持条件。即在执行时不会再提出资源请求在等待时未占有任何资源。2、破坏不剥夺条件。一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源。3、破坏环路条件。系统将所有资源按类型进行线性排序，并赋予不同的序号，所有进程对资源的请求必须严格按照资源序号递增的次序提出。利用银行家算法避免死锁 六、六、存储管理存储管理 存储器的层次结构 存储器管理的功能 1.地址映射 2.主存分配与回收 3.存储保护 4.主存扩充(虚拟内存)地址映射(地址重定位)内存的每个存储单元都有一个编号，这种编号称为内存地址（或物理地址，绝对地址）。实现虚拟内存的基本原理 将程序正在使用的部分内容放在内存，而暂时不用的部分放在外存，在需要时由系统调入内存，并将不需要（或暂不需要）的部分调出内存。-15-程序的装入与链接（1）编译。由编译程序将用户源代码编译成若干个目标模块。（2）链接。由链接程序将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块。（3）装入。由装入程序将装入模块装入主存的过程。（加载）程序的装入就是把程序装入内存空间。采用三种方式：1.绝对装入方式(Absolute Loading Mode)在可执行文件中记录内存地址，装入时直接定位在（即文件中记录的地址）内存地址。2.可重定位方式(Relocatable Loading Mode)在可执行文件中，列出各个需要重定位的地址单元和相对地址值。3.动态运行时装入方式(Dynamic Run-time Loading)把装入模块装入主存后，并不立即将装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正执行时才进行。实现链接的方法有三种：1.静态链接：事先进行链接，以后不再拆开的链接方式。2.装入时动态链接：用户源程序经编译后所得到的目标模块，在装入主存时，边装入边链接的。3.运行时动态链接：可将某些目标模块的链接，推迟到执行时才进行。连续分配方式是指为一个用户程序分配一个连续的内存空间。1.单一连续分配 2.固定分区分配 3.动态分区分配 4.可重定位分区分配 有作业序列：作业 A 要求 18K；作业 B 要求 25K，作业 C 要求 30K。系统中空闲区按三种算法组成的空闲区队列：-16-基本分页存储管理方式 逻辑上相邻的页，物理上不一定相邻。-17-有 2 页分别装入内存的第 5、6 块；作业 2 有 3 页装入内存的第 2、4、7 块；作业 3 有 1 页装入内存的第 8 块 页大小的选择 太大：浪费；太小：页表过长。设页长为 1K，程序地址字长为 16 位，用户程序空间和页表如图。快表又叫联想存储器(associative memory)或 TLB(Translation Lookaside Buffers)基本分段存储管理方式 -18-七、七、设备管理设备管理 设备是指计算机系统中除 CPU、内存和系统控制台以外的所有设备。设备的分类 1.按传输速率分 低速设备：每秒几个到数百字节。如键盘 中速设备：每秒数千到数万字节。如打印机 高速设备：每秒数百 K 到数兆。如磁盘、光盘 2.按信息交换的单位分类 字符设备：I/O 传输的单位是字节，如打印机、modem 等。特征：速率较低、中断驱动。块设备：I/O 传输的单位是块，如磁盘/带。特征：速率高（几兆）、可随机访问任一块、DMA 方式驱动。3.按资源管理方式分类 独占设备：在任一时间内最多有一个进程占用它，字符设备及磁带机属独占型设备。即临界资源。共享设备：多个进程对它可进行交叉访问，共享设备必须是可寻址和可随机访问的设备。如：磁盘 虚拟设备：在一类设备上模拟另一类设备。常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚拟设备。设备控制器是一个可编址设备，分为字符设备控制器和块设备控制器，是 CPU 与设备间的-19-接口。功能:接收和识别命令 数据交换 设备状态的了解和报告 地址识别 数据缓冲、差错控制 设备控制器的组成（三部分）1.设备控制器与处理机的接口 数据线（数据寄存器、控制/状态寄存器）地址线 控制线 2.设备控制器与设备的接口 数据信号、状态信号、控制信号 3.I/O 逻辑：实现对设备的控制 I/O 控制是设备管理的另一功能，它包括设备驱动处理（块设备）和设备中断处理（字符设备）。I/O 控制方式 1.循环测试 I/O 方式 2.I/O 中断方式 3.DMA 方式 4.通道方式 I/O 控制器是 OS 同硬件之间的接口。它有两个寄存器：数据缓冲寄存器、控制寄存器。DMAC 组成 -20-DMA 方式 USB 的传输方式 1.中断传输方式 2.控制传输方式 3.批传输方式