操作系统-基本知识点

1、操作系统复习提纲 目录1.操作系统概述41.1.操作系统的概念41.2.计算机的特征41.2.1.计算机的功能41.3.计算机提供的服务41.4.操作系统的发展与分类41.5.操作系统的运行环境 （内核态与用户态、中断、异常、系统调用）41.6.操作系统体系结构52.进程管理62.1.进程与线程62.1.1.进程概念62.1.2.进程的状态与转换62.1.3.进程控制62.1.4.进程组织62.1.5.进程通信（共享存储、消息传递、管道通信）62.1.6.线程概念与多线程模型72.2.处理机调度72.2.1.调度的基本概念72.2.2.典型调度算法82.3.进程同步与互斥82.3.1

2、.进程同步的基本概念82.3.2.实现临界区互斥的基本方法：软件实现方法、硬件实现方法82.3.3.信号量、管程92.3.4.经典同步问题102.4.死锁102.4.1.产生死锁的原因102.4.2.产生死锁的必要条件102.4.3.处理死锁的方法103.内存管理113.1.内存管理基础113.1.1.内存管理概念113.1.2.程序装入与链接、逻辑地址与物理地址空间、内存保护113.1.3.交换与覆盖113.1.4.连续分配管理方式113.1.5.非连续分配管理方式113.2.虚拟内存管理113.2.1.虚拟内存基本概念113.2.2.请求分页管理方式123.2.3.页面置换算法123.2.

3、4.工作集、抖动124.输入输出（I/O）管理134.1.I/O管理概述134.2.I/O控制方式134.3.I/O软件层次结构134.4.I/O调度概念134.4.1.磁盘访问时间：134.4.2.磁盘调度144.5.出错处理144.6.高速缓存与缓冲区144.6.1.缓冲引入的原因：144.6.2.缓冲的种类：144.6.3.高速缓存：144.7.假脱机技术（SPOOLing）144.8.设备分配与回收155.文件管理165.1.文件系统基础165.1.1.文件概念与逻辑结构165.1.2.文件的结构165.1.3.目录结构165.1.4.文件共享175.1.5.文件保护：访问类型、访问控

4、制175.2.文件系统实现175.2.1.文件系统层次结构175.2.2.目录实现175.2.3.文件实现175.3.磁盘组织与管理175.3.1.磁盘的结构175.3.2.磁盘调度算法：先来先服务（FCFS）、最短寻道时间优先（SSTF）、电梯算法（SCAN）175.3.3.磁盘的管理171. 操作系统概述1.1. 操作系统的概念计算机操作系统是指控制和管理计算机的软、硬件资源，以合理组织的计算机的工作流程，方便用户使用的程序集合。1.2. 计算机的特征A. 并发性：单处理机并发（两个或多个事物在同一时间间隔内发生），多处理机可以并行（两个或多个事物在同一时刻发生）。进程是在系统中能够独立运

5、行并作为资源分配的基本单位。在引入线程的OS中，通常都是把进程作为分配资源的基本单位，把线程作为独立运行和调度的基本单位。B. 共享性：即系统中的资源可以共内存中多个并发执行的程序共同使用。可分为互斥共享方式和同时访问方式。C. 虚拟性：即通过一种技术把一个物理实体变为若干个逻辑上的对应物。有时分复用技术（虚拟处理机技术）和空分复用技术（虚拟内存）。D. 异步性：进程都是以不可预知的速度向前推进。1.2.1. 计算机的功能E. 处理机管理功能进程的创建，撤销，同步，通信和调度。F. 存储器管理功能内存的分配，保护，地址映射，和虚拟内存功能G. 设备管理功能为用户进程分配回收I/O设备，完成I/

6、O请求，提高CPU和I/O设备之间的利用率（缓冲管理）。H. 文件管理功能文件存储空间管理，目录管理和文件的读写保护。I. 操作系统与用户之间的接口功能可分为用户接口和程序接口。1.3. 计算机提供的服务1.4. 操作系统的发展与分类发展：无操作系统的计算机系统单道批处理系统多道批处理系统分时系统实时系统微机操作系统的发展：单用户单任务操作系统单用户多任务操作系统多用户多任务操作系统1.5. 操作系统的运行环境 （内核态与用户态、中断、异常、系统调用）1.6. 操作系统体系结构J. 传统的操作系统结构无结构OS，模块化OS，分层式OSK. 客户/服务器模式L. 面向对象的程序设计模式

7、M. 微内核OS结构足够小的内核，基于C/S模式，应用“机制与策略相分离”原理，采用面向对象技术。2. 进程管理2.1. 进程与线程1.1.1.2.1.1. 进程概念进程进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程实体即是由程序段，相关的数据段和PCB三部分构成。程序顺序执行拥有顺序性，封闭性，和可再现性三个特征。2.1.2. 进程的状态与转换2.1.3. 进程控制操作系统是根据PCB来对并发执行的进程进行控制和管理的，所以说PCB是进程存在的唯一标识。在进程控制块中主要包含一下四方面的内容：A. 进程标识符包含内部标识符和外部标识符B. 处理机状态通用寄存器，指令计数器，

8、程序状态字PSW，和用户栈指针C. 进程调度信息进程状态，进程优先级D. 进程控制信息程序和数据地址，进程同步和通行机制，资源清单，链接指针2.1.4. 进程组织目前常用的两种方式如下：A. 连接方式把具有统一状态的PCB链接成一个队列。B. 索引方式把具有统一状态的PCB组织为一张索引表。2.1.5. 进程通信（共享存储、消息传递、管道通信）A. 共享存储：共享又可分为基于共享数据结构的通信方式和基于共享存储区的通信方式。B. 管道通信：是指由于连接一个读进程和一个写进程以实现他们之间的通行。C. 消息传递系统：直接消息传递方式：Send(receiver,message);Receive(

9、sender,message);间接消息传递：Send(mailbox,message);Receive(mailbox,message);2.1.6. 线程概念与多线程模型 线程是比进程更小的能独立运行的单位。线程有以下三种实现方式：A. 内核支持线程B. 用户级线程C. 组合方式2.2. 处理机调度1.2.2.2.1. 调度的基本概念调度可分为一下三种A. 高级调度（作业调度）主要功能是根据某种算法，把外存上处于后备队列中那些作业调入内存。B. 低级调度（进程调度）用于决定就绪队列中的哪个进程应获得处理机。C. 中程调度将那邪恶暂时不能运行的进程调到外存上等待，而不再浪费宝贵的内存资源。1

10、.2.2.1.2.2.2.2.1.2.2.1.1. 调度的基本准则调度有两个基本准则：A. 面向用户的准则a) 周转时间短平均周转时间：T=1ni=1nTi，平均带权周转时间W=1ni=1nTiTsb) 响应时间快从键盘键入信息传送到处理器的时间，处理机处理的时间，返回到终端显示器的时间。c) 截至时间保证这是评价实时系统性能的重要指标d) 优先权准则保证紧急作业得到即时处理B. 面向系统的准则a) 系统吞吐量b) 处理机利用率c) 各类资源的平衡利用2.2.1.2. 调度方式与时机进程的调度可以分为一下两种A. 非抢占式在该模式下，可能引起进程调度的因素可以归为一下几类a) 正在执行的进程执

11、行完毕，或是发生某些事件而不能继续执行。b) 执行中的进程提出I/O请求二暂停执行c) 执行了某种元语B. 抢占式抢占式可以防止某一长进程长时间占用处理机，能为大多数的进程提供更公平的服务。抢占的调度方式是基于一定原则的。2.2.1.3. 切换与过程A. 保存处理机的现场B. 按某种算法选取进程C. 把处理器分配给进程2.2.2. 典型调度算法2.2.2.A. 先来先服务(FCFS)与短作业（短进程、短线程）(SJ(P)F)优先SJ(P)F较FCFS能明显的提高平均周转时间和带权周转时间，但该算法对长作业不利，也未考虑作业的紧迫程度。B. 时间片轮转时间片的取值略大于一次典型交互所需的时间。C

12、. 优先级优先级法可分为静态优先级和动态优先级。D. 最高响应比优先优先权=等待时间+要求服务时间要求服务时间=响应时间要求服务时间。E. 多级反馈队列调度算法2.3. 进程同步与互斥1.3.2.3.1. 进程同步的基本概念A. 两种制约关系间接相互制约关系直接相互制约关系B. 临界资源诸进程应采用互斥的方式实现对这种资源的访问，如打印机等。C. 临界区进程中访问临界资源的那段代码称为临界区D. 同步机制原则a) 空闲让进b) 忙则等待c) 有限等待d) 让权等待2.3.2. 实现临界区互斥的基本方法：软件实现方法、硬件实现方法A. 软件实现方法：a) 单标志法：/*P0进程*/while(t

13、urn!=0);critical section;turn=1;remainder section;/*P1进程*/while(turn!=1);critical section;turn=0;remainder section;两个进程必须交替访问临界区，违背空闲让进。b) 双标志先查法：/*P0进程*/while(flagj);flagi=ture;critical section;flagi=FALSE;remainder section;/*P1进程*/while(flagi);flagj=TURE;critical section;flagj=FLASE;remainder sect

14、ion;检查对方和设置自己不是一次执行的，故可能会违背忙则等待原则。c) 双标志后查法：/*P0进程*/flagi=ture;while(flagj);critical section;flagi=FALSE;remainder section;/*P1进程*/flagj=TURE;while(flagi);critical section;flagj=FLASE;remainder section;违背空闲让进d) Petersons Algorithm/*P0进程*/flagi=TURE;turn=j;while(flagj&&turn=j);critical sectio

15、n;flagi=FALSE;remainder section;/*P1进程*/flagj=TURE;turn=I;while(flagi&&turn=j);critical section;flagj=FALSE;remainder section;利用flag解决互斥访问，利用turn解决“饥饿”现象。B. 硬件实现方法：a) 中断屏蔽法b) 硬指令法i. TestAndSet指令：while TestAndSet(&lock);critical section;lock=false;remainder section;ii. Swap指令：key=ture; /*

16、local variable*/while(key!=FAlSE)/*lock is a share var*/ Swap(&lock, &key);ritical section;lock=FALSE;remainder section;2.3.3. 信号量、管程A. 整型信号量违背让权等待原则。B. 记录型信号量C. AND型信号量D. 信号量集E. 管程一个管程定义了一个数据结构和能为并发进程所执行的在该数据结构上的一组操作，这组操作能同步进程和改变管程中的数据。2.3.4. 经典同步问题A. 生产者-消费者问题：c) 使用记录型信号量d) 使用and信号量解决e) 利用

17、管程B. 哲学家进餐问题：f) 利用记录型型号量解决g) 利用AND信号量解决C. 读者-写者问题：h) 利用记录型信号量解决i) 利用信号量集机制解决2.4. 死锁1.4.死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前推进。2.4.1. 产生死锁的原因A. 竞争资源B. 进程间推进顺序非法2.4.2. 产生死锁的必要条件A. 互斥条件B. 请求和保持条件C. 不剥夺条件D. 环路等待条件2.4.3. 处理死锁的方法A. 预防死锁破坏死锁的四个必要条件中的一个或多个从而达到预防死锁的目的。但由于所施加的条件太严格可能会导致系

18、统资源利用率和系统吞吐量下降。摒弃“请求和保持”条件摒弃“不剥夺”条件摒弃“环路等待”条件B. 避免死锁在资源的动态分配过程中，用某种方法去防止系统进入不安全状态。如银行家算法。C. 检测死锁&解除死锁资源分配图死锁定理：当且仅当该状态的资源分配图是不可完全化简的时，该状态即为死锁状态。死锁解除：剥夺资源和撤销进程。3. 内存管理3.1. 内存管理基础3.1.1. 内存管理概念操作系统的存储管理，负责对可执行存储器的分配，回收以及提供在存储层次间数据移动的管理机制。3.1.2. 程序装入与链接、逻辑地址与物理地址空间、内存保护A. 装入：a) 绝对装入方式b) 可重定位装入方式c) 动

19、态运行时装入方式B. 链接： a) 静态链接b) 装入时动态链接c) 运行时动态链接3.1.3. 交换与覆盖对换可分为整体对换和部分对换。为了实现进程的对换，系统必须实现三方面的功能：对换空间的管理，进程的换入，进程的换出。3.1.4. 连续分配管理方式 A. 单一连续分配方式内存分为用户区和系统区两部分。只适用于单用户单任务系统。B. 固定分区分配划分分区的方法可以有分区大小相等和分区大小不等两种方式。C. 动态分区分配a) 数据结构：i. 空闲分区表ii. 空闲分区链b) 分区分配方法：i. 首次适应算法ii. 循环首次适应算法iii. 最佳适应算法iv. 最坏适应算法v. 快速适应算法D

20、. 可重定位分区分配利用动态运行时，地址的转换是在程序执行时完成。故可以使用“紧凑”将多个分散的小分区拼接成一个大分区。3.1.5. 非连续分配管理方式A. 分页管理方式B. 分段管理方式C. 段页式管理方式3.2. 虚拟内存管理3.2.1. 虚拟内存基本概念虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。3.2.2. 请求分页管理方式A. 硬件支持：a) 页表机制：页号物理块状态位访问字段修改位外存地址b) 缺页中断机构：与一般中断相比，缺页中断发生在指令执行期间，且在一条指令可能产生多次中断。c) 地址变换机构：加入虚拟存储管理后的地址变换流程。B.

21、内存分配策略和分配算法：a) 最小物理块数：保证进程运行的最小物理块数量，与硬件平台有关。b) 物理块分配策略：i. 固定分配局部置换ii. 可变分配全局置换iii. 可变分配局部置换c) 物理块分配算法：i. 平均分配算法ii. 按比例分配算法iii. 考虑优先权的分配算法C. 调页策略：a) 时机：iv. 预调页策略v. 请求调页策略b) 何处：vi. 系统拥有足够的对换区vii. 系统缺少足够的对换区D. UNIX方式3.2.3. 页面置换算法A. 最佳置换算法（OPT）B. 先进先出置换算法（FIFO）C. 最近最少使用置换算法（LRU）D. 时钟置换算法<CLOCK>3.

22、2.4. 工作集、抖动抖动是指频繁的页面对换行为，最坏的情况是刚刚换出的页面马上又要换入，刚刚换入的页面马上又要换出。工作集是指在某段时间内，进程要访问的页面的集合。为了防止系统出现抖动现象，需要选择合适的工作集大小。4. 输入输出（I/O）管理 4.1. I/O管理概述I/O设备可按如下分类。按设备的使用特性可分为：存储设备，输入/输出设备；按传输速率可分为：低速设备、中速设备、高速设备；按信息交换的单位可分为：块设备、字符设备；按设备的共享属性可分为：独占设备、共享设备、虚拟设备；I/O设备与设备控制器间的接口有三种类型信号：数字信号线、控制信号线、状态型号线。I/O通道有三种通

23、道类型：字节多路通道、数组选择通道、数组多路通道4.2. I/O控制方式程序I/O方式中断驱动I/O控制方式直接存储访问（DMA）I/O控制方式I/O通道控制方式4.3. I/O软件层次结构用户软件层：实现与用户的交互。设备独立性软件：负责实现与设备驱动器的统一接口、设备命名、设备保护以及设备分配与释放设备驱动软件：与硬件直接相关中断处理程序：保存被终端进程的CPU环境，转入中断处理程序处理后再恢复硬件：执行I/O操作4.4. I/O调度概念磁盘的结构分为：盘片、盘面、磁道、扇区。磁盘的常见分类为：硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头等。2.2.1.2.2.2.3.2.4.4.4.1

24、. 磁盘访问时间：A. 寻道时间Ts：把磁臂移动到指定磁道上所经历的时间。Ts=m×n+sm是一个常数，对一般磁盘而言m=0.2,对于高速磁盘m<0.1，s是磁臂启动时间约为2ms。B. 旋转延迟时间：指定扇区移动到磁头下方所经历的时间：对于15000r/min的硬盘，每转约4ms，则其平均延时时间Tr为2msC. 传输时间：把数据从磁盘读出或写入的时间Tt的大小与每次所读写的字节数b和旋转速度有关Tt=brN其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数。因此，访问时间Ta可表示为：Ta=Ts+12r+brN4.4.2. 磁盘调度先来先服务（FCFS, first com

25、e first served）最短寻道时间为优（SSTF, shotest seek time first）扫描算法（SCAN）循环扫描算法（CSCAN）NStepSCAN和FSCAN调度算法4.5. 出错处理一般而言错误多数是与设备紧密相关的，因此对错的处理应尽可能在接近硬件层面处理，在底层软件能够解决的错误就不让高层软件感知，只有底层软解决不了的错误才通知高层软件解决。4.6. 高速缓存与缓冲区4.6.1. 缓冲引入的原因：缓和CPU与I/O设备间的速度不匹配矛盾减少CPU的中断频率，放宽对CPU中断响应时间的限制提高CPU和I/O设备之间的并行性4.6.2. 缓冲的种类：单缓冲双缓冲循环

26、缓冲缓冲池4.6.3. 高速缓存：磁盘高速缓存是指利用内存中的存储空间来暂存从磁盘读出的一系列盘块中的信息。数据交付方式：数据交付、指针交付。置换算法：LRU、NRU、LFU等。周期性写回磁盘4.7. 假脱机技术（SPOOLing）外围机操作与CPU对数据的处理同时进行，这种在联机情况下实现的同时外围操作称为SPOOLing或假脱机操作。SPOOLing系统的组成：A. 输入井和输出井模拟脱机输入输出时的磁盘设备B. 输入缓冲区和输出缓冲区缓和CPU和磁盘的速度不匹配C. 输入进程SPi和输出进程SPo模拟外围控制机SPOOLing设备的特点：A. 提高了I/O速度B. 将独占设备改造为共享设备C. 实现了虚拟设备功能4.8. 设备分配与回收系统设备表（SDT）设备控制表（DCT）控制器表（COCT）通道表（CHCT）5. 文件管理5.1. 文件系统基础5.1.1. 文件概念与逻辑结构由创建者所定义的、具