操作系统期末考试总结

第一篇：操作系统期末考试总结

第一章 操作系统概论

第一章主要内容

各节基本概念，操作系统的发展过程，操作系统的基本特征。

操作系统的目标

1.有效性

2、方便性

3、可扩充性4．开放性

分时系统实现中的关键问题

(1)及时接收(2)及时处理

主要特征1.多路性2.独占性3.及时性4.交互性

实时操作系统按其用途的不同可分为两种类型：实时控制系统和实时信息处理系统 3．实时系统与分时系统特征的比较

(1)多路性。实时信息处理系统也按分时原则为多个终端用户服务。实时控制系统的多路性则主要表现在系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制。而分时系统中的多路性则与用户情况有关，时多时少。

(2)独立性。实时信息处理系统中的每个终端用户在向实时系统提出服务请求时，是彼此独立地操作，互不干扰；而实时控制系统中，对信息的采集和对对象的控制也都是彼此互不干扰。(3)及时性。实时信息处理系统对实时性的要求与分时系统类似，都是以人所能接受的等待时间来确定的；而实时控制系统的及时性，则是以控制对象所要求的开始截止时间或完成截止时间来确定的，一般为秒级到毫秒级，甚至有的要低于100微秒。

(4)交互性。实时信息处理系统虽然也具有交互性，但这里人与系统的交互仅限于访问系统中某些特定的专用服务程序。它不像分时系统那样能向终端用户提供数据处理和资源共享等服务。(5)可靠性。分时系统虽然也要求系统可靠，但相比之下，实时系统则要求系统具有高度的可靠性。因为任何差错都可能带来巨大的经济损失，甚至是无法预料的灾难性后果，所以在实时系统中，往往都采取了多级容错措施来保障系统的安全性及数据的安全性。

操作系统的特征

（1）共享性

从资源使用的角度来讲，所谓共享性是指操作系统程序与多个用户程序共同使用系统中的各种资源。

 互斥共享方式  同时访问方式

（2）虚拟性

指把一个物理上的实体，变为若干个逻辑上的对应物。前者是实际存在的；而后者是虚的，只是用户的一种感觉。

 时分复用：虚拟处理机

 空分复用：虚拟磁盘、虚拟I/O设备、虚拟存储器

（3）并发性：

是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指宏观上在一段时间内有多道程序在同时运行。但在单处理机系统中，每一时刻仅能执行一道程序，故微观上这些程序是在处理机上交替执行。

• • • 与并行的区别 进程 线程

（4）异步性(不确定性）

指在多道程序环境下，程序以异步方式执行。即每道程序在何时执行、各自执行的顺序、完成每道程序所需要的时间都是不确定的，也是不可预知的。

并发 和 共享 是操作系统的两个最基本的特征。5 大管理功能 1.处理机管理

(1)进程控制

2.存储管理

(1)内存分配

3.设备管理

(1)设备分配

4.文件管理（软件资源管理）

(1)文件存储空间的管理

5．作业管理(用户接口)

(1)命令接口提供一组命令供用户直接或间接控制自己的作业；

(2)程序接口提供一组系统调用供用户应用程序和其他系统程序调用操作系统的功能。

(2)目录管理

(3)文件保护

(4)文件操作管理

(2)设备处理

(3)缓冲管理

(2)存储保护

(3)存储扩充

(4)地址映射

(2)进程调度

(3)进程同步

(4)进程通信

总结：

计算机操作系统是方便用户使用，管理和控制计算机软硬件资源的系统软件。

目前操作系统有六大类型:批处理系统、分时系统、实时系统、单用户系统、网络系统和分布式系统。

五大管理功能:处理机管理、存储管理、设备管理、文件管理和作业管理(用户接口)。

四大特性:并发性、共享性、虚拟性和异步性。

操作系统的最主要设计目标有两个：

1)向用户提供方便、简单的使用计算机的环境；

2)使计算机系统能高效地工作，提高系统资源的利用

第二章主要内容（重点）

2.1 进程的基本概念 2.2 进程控制 2.3 进程同步

2.4 经典进程的同步问题

以上各节讲过的内容，重点是进程的基本状态及转换、信号量的原理和应用、进程同步和互斥。

第二章 进程管理

4.2.1 程序的装入

1.绝对装入方式(Absolute Loading Mode)

从R开始

2.可重定位装入方式(Relocation Loading Mode)

从0开始

3.动态运行时装入方式(Denamle Run-time Loading)重定位不在装入内存时进行，在真正执行程序时执行

4.2.2 程序的链接

1.静态链接方式(Static Linking)

2.装入时动态链接(Load-time Dynamic Linking)

装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。

3.运行时动态链接(Run-time Dynamic Linking)4.3 连续分配方式 4.3.1 单一连续分配

单用户、单任务

• • • 存在内碎片问题

优点：易于实现，开销小。缺点：

– –

• • • • • 内碎片造成浪费

分区总数固定，限制了并发执行的程序数目。4.3.2

固定分区分配

可以和覆盖、交换技术配合使用。

采用的数据结构：分区表－－记录分区的大小和使用情况

动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。优点：没有内碎片。缺点：有外碎片。4.3.3 动态分区(dynamic partitioning)

1.分区分配中的数据结构

(1)空闲分区表(2)

空闲分区链。2.分区分配算法

(1)首次适应算法(first fit)

(2)循环首次适应算法(next fit)，该算法是由首次适应算法演变而成的。从上次分配的分区起查找

(3)最佳适应算法(best fit)。(4)最坏适应算法(worst fit)

(5)快速适应算法(quick fit)根据其容量大小进行分类

• 分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。• 分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断和合并时机的选择)

内存回收时的情况

4.3.6 可重定位分区分配 1.动态重定位的引入

• • • 紧缩（或拼凑）可重定位分区法

紧缩时机

1释放所占分区时

2分配进程分区时

4.3.7 对换(Swapping)

3.进程的换出与换入

阻塞状态且优先级最低

换出时间(换出到磁盘上)最久的进程

4.4.3 两级和多级页表

4.5.2 分段系统的基本原理

段号 段内地址

例子

段式存储管理中供用户使用的逻辑地址为24位，其中段内地址占用16位 用户程序最多可以分为多少段？2^8

当把用户程序装入内存时，每段占用内存的最大连续区为多少字节？2^16

4.6 虚拟存储器的基本概念

4.6.1 虚拟存储器的引入

1.常规存储器管理方式的特征

(1)一次性。(2)驻留性。

2.虚拟内存可行性基础：局部性原理

3.虚拟存储器定义

：请求调入功能和置换功能

4.6.2 虚拟存储器的实现方法

1.分页请求系统

(1)硬件支持

① 请求分页的页表机制 ② 缺页中断机构

(2)实现请求分页的软件 4.6.3 虚拟存储器的特征

多次性

对换性 虚拟性 离散性

③ 地址变换机构

最本质的特征：离散性；最重要的特征：虚拟性。

2.缺页中断机构

4.7.2 内存分配策略和分配算法

1.最小物理块数的确定

2.物理块的分配策略

内存分配策略－－即固定和可变分配策略。置换－－即全局置换和局部置换。

1)固定分配局部置换(Fixed Allocation, Local Replacement)

2)可变分配全局置换(Variable Allocation, Global Replacement)

3)可变分配局部置换(Variable Allocation, Local Replacemen 3.物理块分配算法

1)平均分配算法

2)按比例分配算法

物理块数b=(s/S)*m

m为物理块总数 s页面数 3)考虑优先权的分配算法 4.8 页面置换算法

1.最佳置换算法（Optimal Replacement, OPT）：将来不被使用，或者是在最远的将来才被访问

2.先进先出(FIFO)页面置换算法：总是淘汰在内存中停留时间最长（年龄最老）的一页

• • 优点：容易理解，方便程序设计。缺点：

●性能并不很好，效率不高

●存在Belady异常现象，即缺页率随内存块增加而增加

4.8.2 最近最久未使用(LRU)置换算法：最近一段时间里最久没有使用过的页面予以淘汰。

LRU置换算法的硬件支持

47071******074112074

221074662107

1)寄存器

2)特殊栈

4.8.3 Clock置换算法

2.改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面：

1类(A=0, M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。

2类(A=0, M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。

3类(A=1, M=0)：最近已被访问，但未被修改，该页有可能再被访问。

4类(A=1, M=1): 最近已被访问且被修改，该页可能再被访问。

其执行过程可分成以下三步

(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。

(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

4.8.4 其它置换算法

1.最少使用(LFU： Least Frequently Used)置换算法

选择在最近时期使用最少的页面作为淘汰页。

2.页面缓冲算法(PBA： Page Buffering Algorithm)两个链表：空闲链表、已修改页面的链表 4.9 请求分段存储管理方式 4.9.1 请求分段中的硬件支持

1.段表机制2.缺段中断机构3.地址变换机构

4.9.2 分段的共享与保护

1.共享段表

2.共享段的分配与回收 ：对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区始址填入段表把count置为1 1)共享段的分配

2)共享段的回收：count∶=count-1 3.分段保护

1)越界检查

2)存取控制检查

• • •

• • • 只读

只执行

读/写

3)环保护机构

一个程序可以访问驻留在相同环或较低特权环中的数据。

一个程序可以调用驻留在相同环或较高特权环中的服务。

5.6.2 磁盘调度

1．先来先服务(FCFS)

2．最短寻道时间优先(SSTF):

每次的寻道时间最短

(从100#磁道开始，向磁道号增加方向访问)被访问的下 移动距离 一个磁道号(磁道数)150 50 160 10 184 24 90 94 58 32 55 3 39 16 38 1 18 20平均寻道长度：27.8(从100#磁道开始，向磁道号增加方向访问)被访问的下 移动距离 一个磁道号(磁道数)150 50 160 10 184 24 18 166 38 20 39 1 55 16 58 3 90 32平均寻道长度: 35.8

4．循环扫描(CSCAN)算法:CSCAN算法规定磁头单向移动

第六章主要内容

6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理

6.5 文件存储空间的管理

以上各节讲过的内容，重点是文件的逻辑结构、物理结构、目录管理、存储空间管理的方法 6.1 文件与文件系统

文件说明1）文件类型。2）文件长度。3）文件的位置。4）文件的存取控制。5）文件的建立时间

文件的分类

按文件用途：1.系统文件 2.用户文件 3.库文件 按数据形式：1.源文件 2.目标文件 3.可执行文件 按操作保护：1.只读文件 2.读写文件3.执行文件 按文件性质：1.普通文件 2.目录文件 3.特殊文件

4、文件的操作(文件接口）

（1）创建文件。（2）删除文件。（3）打开文件（4）读文件（5）写文件（6）关闭文件 文件的逻辑结构：用户关心：文件内容或记录 1．有结构的文件(记录型文件）

定长记录型

变长记录型 2．无结构文件（流式文件）

文件的物理结构：系统关心：文件存储、提取 1．连续文件2.链接文件3．索引文件

记录星文件的组织方式：1.顺序文件 2 索引文件 3.索引顺序文件

1、顺序文件

1）分：串结构、顺序结构

2）读/写操作

3）优

适合批量存取

缺点

不适合交互应用，记录的删改

2、索引文件

优：速度缺：存储空间

3、索引顺序文件

1）读/写操作

2）优点：折中

比较检索效率 记录个数N 顺序文件N/2 索引顺序文件 根号2

6.3.3 FAT和NTFS技术

计算以盘块为分配单位时，所允许的最大磁盘容量。

 一个FAT表所能描述的最大容量=最多允许表项数*盘块大小  最大磁盘容量 =一个FAT表所能描述的最大容量*卷的个数

=最多允许表项数*盘块大小*卷的个数 故：FAT12 最大磁盘容量=212*29*4=8*220（8M）

引入一个新的分配单位——簇

问题:造成簇内零头

6.4 文件目录

文件目录项（FCB）：一般情形下包括三类信息：1）基本信息2）存取控制信息3）使用信息类

目录结构 单级目录结构

缺点:(1)查找速度慢。(2)不允许重名。(3)不便于实现文件共享。

二级目录结构优点：

(1)提高了检索目录的速度。

(2)在不同的用户目录中，可以使用相同的文件名。(3)不同用户还可使用不同的文件名来访问系统中的 同一个共享文件

多级目录结构

1）树型目录结构2)路径名

3)当前目录(Current Directory)1.相对路径名(relative path name)2.绝对路径名(absolute path name)从根开始 6.4.3 目录查询技术 1．线性检索法

线性检索法又称为顺序检索法。

根目录结点6是132号盘块是/usr的目录/usr的目录

1·6·

1· ·1· ·

bin 419dick 7dev132 30erik14lib

51jimetc 9 626astusr

tmp45bal 8 在结点6中查找usr字段

2．Hash方法

结点26是/usr/ast的目录496号盘块是/usr/ast的目录26664·· ·grantsbooksmboxminiksrc49692608117对于使用了通配符的文件名，系统便无法利用Hash方法检索目录。

在进行文件名的转换时，有可能把n个不同的文件名转换为相同的Hash值，即出现了所谓的“冲突”。

6.5.1空闲表法和空闲链表法

1．空闲表法

空闲表法属于连续分配方式

2、空闲块（区）链

空闲链表法是将所有空闲盘区拉成一条空闲链

6.5.2．位示图

对应物理块：b=n*i+j（1，7）→16*1+7=23 6.5.3．成组链接法

第二篇：郑州大学操作系统期末考试重点整理

操作系统是管理系统资源、控制程序执行、改善人机界面、提供各种服务、合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的一种系统软件。

资源管理1资源复用(空分复用共享，时分复用共享)2资源虚化3资源抽象4组合使用抽象和虚化技术

1）进程抽象（2）虚存抽象（3）文件抽象（4）其他资源抽象

操作系统的作用:（1）OS作为用户接口和公共服务程序：（2）OS作为扩展计算机或者虚拟计算机（2）OS作为资源的管理者和控制者（4）OS作为程序执行的控制着和管理者 从资源管理的角度，看操作系统具有六项主要功能：处理器管理，存储管理，设备管理，文件管理，网络与通信管理，用户接口

操作系统的主要特性：并发性，共享性，异步性 并发性：指两个或两个以上事件或活动在同一时间间隔内发生。

并行性：指两个或两个以上事件或活动在同一时刻发生。关系：并行活动一定是并发的，反之并发活动未必是并行的，并行性是并发性的特例，并发性是并行性的扩展。共享性：指操作系统中的资源可被多个并发执行的进程共同使用，而不是被其中某一个程序所独占。

1，透明资源共享：必须妥善解决的问题有资源隔离，授权访问2，显式资源共享：独占资源是指同一时间段内只允许一个进程访问的资源

异步性：由计算机系统中的资源有限而进程众多，每个进程的执行并非连贯的，而是以“走走停停”的方式向前推进。多道程序设计是指允许多个程序同时进入一个计算机系统的主存储器并启动进行交替计算的方法。从宏观上看，多道程序并发运行，它们都处于运行过程中，但都未运行结束。从微观上看，多道程序的执行是串行的，各道程序轮流占用CPU，交替地执行。1，提高CPU、主存和设备的利用率，2，提高系统的吞吐率，是单位时间内完成的作业数增加。3充分发挥计算机系统部件的并行性 操作系统可分为三种基本类型： 批处理操作系统 分时操作系统.实时操作系统

通用操作系统：如果某个操作系统兼具批处理、分时、实时处理的全部或两种功能，则为通用OS

操作系统为用户提供两种调用其服务和功能的接口:程序接口：允许运行程序调用操作系统的服务和功能。许多操作系统的程序接口由一组系统调用（System Call)）组成，用户程序使用“系统调用”就可获得操作系统的底层服务，使用或访问系统的各种软硬件资源。操作接口：操作系统为用户提供的操作控制计算机工作和提供服务手段的集合，通常有操作控制命令、图形操作界面、以及批处理系统提供的作业控制语言等实现手段。内核是一组程序模块，作为可信软件来支持进程并发执行的基本功能和基本操作，通常驻留在内核空间，运行于核心态，具有访问硬件设备和所有主存空间的权限，是仅有的能执行特权指令的程序。分类可分为微内核和单内核两种类型。功能1）资源抽象2）资源分配3）资源共享。

属性1）内核是由中断驱动的2）内核的执行是连续的3）内核在屏蔽中断状态下执行4）内核可以使用特权指令。从操作系统的运行方式来看，可分成：独立运行的内核模型、在应用进程内执行的模型和作为独立进程运行的模型。处理器流可以分作以下四类：单指令流单数据流（SISD）：传统的计算机系统。单指令流多数据流（SIMD）和多指令流多数据流（MIMD）都属于并行计算机！多指令流单数据流（MISD）：在研究中

处理器现场：处理器包括一组寄存器，用于存放数据、变量和中间结果，这组寄存器所存储的信息与程序的执行有很大关系，构成了处理器现场。

特权指令是指只能提供给操作系统的核心程序使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清内存、建立存储键，加载PSW（程序状态字）等。

非特权指令：指供应用程序使用的、权限较低的指令。处理器状态分类：核心状态和用户状态。

核心态具体的权限有：1，CPUU运行可信软件2，硬件执行全部机器指令3，可以访问所有内存单元和系统资源4，具体改变处理器状态的能力。

用户态具有的权限有：1，CPU运行非可信软件2，程序无法执行特权指令3，访问权限仅限于当前进程的地址空间4，不具有改变处理器状态的能力 处理器状态之间的转换：(1)用户状态向核心状态的转换：一是程序请求操作系统服务，执行一条系统调用；二是程序运行时，产生了一个中断（或者异常）事件，运行程序被中断，让中断处理程序工作。这两种情况都是通过中断机构发生的。中断（异常）是用户态到核心态转换的唯一途径。(2)核心状态向用户状态的转换 ：每台计算机通常会提供一条特权指令称作加载程序状态字LPSW（Load PSW），用来实现操作系统向用户程序的转换。加载程序状态字指令的作用：把哪个程序的程序状态字加载到程序状态字寄存器中，就意味着该程序获得CPU控制权执行。

中断是指程序执行过程中，遇到急需处理的某个事件时，暂时中止CPU上现行程序的运行，转而执行相应的事件处理程序执行的过程，待处理完毕之后再返回断点（继续执行）或者调度其他程序执行。中断源是引起中断的事件。中断装置是发现中断源并产生中断的硬件。

中断源分类：1.从中断事件的性质和激活的手段来分，可以分成两类：强迫性中断事件和自愿性中断事件。2按照中断信号的来源和实现手段来分：可分为硬中断和软中断两类。硬中断可以分为外中断和内中断。

中断/异常响应需要顺序执行的四个步骤： 发现中断源，保护现场，转向中断/异常事件的处理程序，恢复现场。

进程(process)是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。

进程的属性(进程与程序比较)：(1)结构性(2)共享性(3)动态性(4)独立性(5)制约性(6)并发性 三态模型：运行态，就绪态，等待态

五态模型：新建态，终止态，运行态，就绪态，等待态 进程映像的组成进程组成主要包括：进程控制块，进程程序块，进程核心栈，进程数据块

进程控制块三类信息：标识信息、现场信息、控制信息允许发生进程上下文切换的四种情况 ：(1)当进程进入等待态时；(2)当进程完成其系统调用返回用户态，但不是最有资格获得CPU时；(3)当内核完成中断处理，进程返回用户态但不是最有资格获得CPU时；(4)当进程执行结束时。模式切换和进程切换的联系与区别：1，模式切换不一定会引起进程状态的转换，也不一定引起进程切换。,2，在完成系统调用服务或者中断处理之后，可通过模式切换来恢复被中断进程的运行。

进程控制原语：1.进程创建 2.进程的撤销 3.进程的阻塞和唤醒 4.进程的挂起和激活

线程的实现分三类：1，用户级线程2内核级线程 3混合式线程

处理器调度可分为三个级别：高级调度、中级调度和低级调度

作业和进程的关系： •作业是任务实体，进程是完成任务的执行实体；没有作业任务，进程无事可干，没有进程，作业任务没法完成。•作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统

资源竞争产生两个控制问题：一个是死锁(Deadlock)问题，就是一组进程如果都获得了部分资源，还想要得到其他进程所占用的资源，最终所有进程都将陷入死锁。一个是饥饿(Starvation)问题，是指一个进程由于其它进程总是优先于它而被无限期拖延。既要解决饥饿问题，又要解决死锁问题。解决饥饿问题的最简单策略是FCFS资源分配策略。

临界区的调度原则 :一次至多允许一个进程进入临界区内；一个进程不能无限地停留在临界区内；一个进程不能无限地等待进入临界区；

管程：属性共享性：安全性：互斥性： 进程通信分类：1）信号（signal）通信机制；2）管道（pipeline）通信机制；3）消息传递(message passing)通信机制；4）信号量（semaphore）通信机制5）共享主存（shared memory）通信机制

死锁的定义:如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，而无限期陷入僵持的局面称为（这一组进程）发生了死锁。

产生死锁的因素:系统拥有的资源数量。与资源分配策略。进程对资源的使用。并发进程的推进顺序。

产生死锁的四个必要条件：互斥条件：进程互斥使用资源。占有和等待条件(部分分配条件)：进程在请求资源得不到满足而等待时，不释放已占有资源。不剥夺条件：已占有的资源只能由属主释放，不允许其他进程强制剥夺。循环等待条件(环路条件)：存在一组循环等待链，其中每一个进程都在链中等待下一个进程所持有的资源，造成种族进程处于永远等待状态。

文件系统是操作系统中负责存取和管理信息的模块，文件不但反映了用户概念中的逻辑结构，而且和存放它的辅助存储器的存储结构紧密相关。一个文件必须从逻辑文件和物理文件两个侧面来观察它。逻辑结构，即记录及其逻辑关系，数据独立于物理环境； 物理结构，数据被文件系统按照某种规则排列和存放到物理存储介质上。

顺序存取:按记录顺序进行读/写操作的存取方法.主要用于磁带文件以及磁盘上的顺序文件.直接存取:以任意次序直接读写某个记录.用户提供相对块号给操作系统,绝对块号由系统换算得到.索引存取:文件专门有一个按记录关键字有序的索引表,用户通过查找索引表定位并读出记录.文件系统给每个文件建立唯一的管理数据结构，即文件控制块（FCB），也叫文件目录项。

文件目录的基本功能是将文件名转变成此文件信息在磁盘上的物理位置。为了加快文件的查找速度，通常把ＦＣＢ集中起来进行管理，组成文件目录。

目录中的文件名和管理信息分开，后者单独组成数据结构，称索引节点（i-node）

块是存储介质上连续信息所组成的一个区域，也叫做物理记录。块是主存储器和辅助存储设备进行信息交换的物理单位，每次总是交换一块或整数块信息

文件的逻辑结构分两种形式：流式文件，记录式文件 流式文件指文件内的数据不再组成记录，只是依次的一串信息集合，可以看成是只有一个记录的记录式文件 记录式文件是一种有结构的文件,包含若干逻辑记录，逻辑记录是文件中按信息在逻辑上的独立含意划分的信息单位。顺序文件(连续文件)一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块上便形成顺序文件。连接文件使用连接字，又叫指针来表示文件中各个记录之间的关系.第一块文件信息的物理地址由文件目录给出,每一块的连接字指出文件下一个物理块位置

直接文件(哈希文件)记录的关键字与其地址间可通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件。

索引文件的优点:不要求物理块连续,便于直接存取,便于文件 的增、删、改。缺点:增加了索引表的空间开销和查找时间.文件的静态共享：允许一个文件同时属于多个目录，但实际上文件仅有一处物理存储，这种文件在物理上一处存储，从多个目录可到达该文件的结构称为文件链接。要实现静态链接，只要不同目录的索引结点i-node号，指定为同一文件的索引结点即可。文件的动态共享：是系统中不同的用户进程或同一用户的不同进程并发地访问同一文件。共享关系只有当用户进程存在时才可能出现，一旦用户的进程消亡，其共享关系也就自动消失。

外围设备分为两类:存储型设备和输入输出型设备.I/O系统：I/O设备及其接口线路、控制部件、通道和管理软件的总称。I/O设备可以划分为输入型、输出型和存储型外围设备三类。按照I/O信息交换的单位, I/O设备可分为字符设备和块设备。

存储型外围设备可以划分为顺序存取存储设备和直接存取存储设备。顺序存取存储设备严格依赖信息的物理位置进行

定位和读写，如磁带机。直接存取存储设备的特点是存取任何一个物理块所需的时间几乎不依赖于此信息的位置，如磁盘。

I/O设备的4种控制方式分类：轮询方式：轮询方式又称程序直接控制方式，特点：CPU不停测试设备状态，直到设备准备就绪，开始传输数据；中断方式：启动I/O后，不必查询I/O是否就绪，继续执行现行程序。特点：不需要CPU做忙式测试，直到设备准备就绪之后产生中断。DMA方式：I/O设备能直接与主存交换数据而不占用CPU,其利用率还可提高。特点：负责数据的交换，CPU不必参与；从设备读数据，存入缓冲寄存器，这个过程与CPU无关；与内存交换数据时，是一次交换一块数据；与内存进行数据交换时，需要抢占内存总线（周期窃取），此时CPU必须等待。通道方式：为获得CPU和外围设备间更高的并行工作能力,引入了自成独立体系的通道结构。特点：通道负责管理设备与内存之间的数据传送的一切工作；数据传输完毕后，产生中断，CPU执行中断处理；数据传输中如果出错，产生中断，CPU执行中断处理。

I/O设备设备控制器或适配器，机械部件则是设备本身。操作系统基本上与控制器打交道，而非设备本身。I/O软件总体设计目标:高效率。通用性。I/O软件组织成四个层次: I/O中断处理程序。设备驱动程序。与设备无关的操作系统I/O软件。用户层I/O软件.笼统地说，设备驱动程序的功能是从独立于设备的软件中接收并执行 I/O请求。设备驱动程序主要包括三部分功能：1设备初始化2执行设备驱动例程3执行中断处理例程。SPOOLing又称为假脱机操作.Spooling技术就是利用一类物理设备模拟另一类物理设备的技术,是使独占使用的设备变成可共享设备的技术.为什么需要缓冲技术？改善中央处理器与外围设备之间速度不匹配的矛盾，协调逻辑记录大小与物理记录大小不一致，提高CPU和I/O设备的并行性。

提高磁盘I/O速度的方法:提前读:在读当前块的同时，将下一个盘块中的数据也读入缓冲区。延迟写:本应写回磁盘的缓冲区中的数据不久之后可能还会再被访问，因而不立即将其写回磁盘。虚拟盘:利用内存空间仿真磁盘，又称为RAM盘。虚拟盘中的数据在掉电或系统重启动以及发生故障时会丢失。

设备独立性带来的好处:用户与物理的外围设备无关，系统增减或变更外围设备时程序不必修改；易于对付输入输出设备的故障。

为了存放从输入设备输入的信息以及作业执行的结果,系统在磁盘上开辟两个大的存储空间,称为井.存储器的层次：寄存器、高速缓存、主存储器，磁盘，磁带。内存是程序运行的主要场所，是进程映像（进程实体）存在的主要位置。

把程序和数据的逻辑地址转换为物理地址的工作称为地址转换或重定位.一种方式是在程序装入时根据程序所装入的内存位置由装入程序依据重定位信息一次性将程序中所有的逻辑地址都转变为物理地址，称为静态重定位，不允许程序在内存中移动位置。另一种方式是在程序执行过程中，地址转换工作穿插在指令执行的过程中，每执行一条指令，CPU对指令中涉及的逻辑地址进行转换，称为动态重定位，允许程序在内存中移动位置。动态重定位必须借助于硬件的地址转换机构实现。

页框：物理地址分成大小相等的许多区域，每个区域叫做一块（或者一个页框page frame）。

页面：逻辑地址分成大小相等的区域，每个区域的大小与块的大小相等，叫做一个页面（page）。

逻辑地址形式：分页式存储器的逻辑地址由两部分组成：页号和单元号(页内位移)。页表：操作系统需为每个作业建立一张页表,该表登记该作业的页号—物理块号对应信息,系统通过页表可以准确访问内存中属于一个作业的所有页面.所以页表实际上用于完成地址变换.虚拟存储器的定义：在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理内存容量大得多的，可寻址的一种“内存储器”。假定作业p共计n页，系统分配给它的主存块只有m块（１≤m≤n）。如果作业p在运行中成功的访问次数为s，不成功的访问次数为F，则总的访问次数Ａ为：A = S + F又定义：f = F / A称f为缺页中断率。影响缺页中断率f的因素有：1)主存页框数。2)页面大小。3)页面替换算法。4)程序特性。最佳页面算法(OPT)、先进先出页面淘汰算法(FIFO)、最近最久未使用页面淘汰算法(LRU)、外围设备分为两类:存储型设备和输入输出型设备。设备管理具有以下功能1外围设备中断处理。2缓冲区管理。3外围设备的分配 4外围设备驱动调度。5虚拟设备及其实现 存储型外围设备可以划分为顺序存取存储设备和直接存取存储设备。顺序存取存储设备严格依赖信息的物理位置进行定位和读写，如磁带机直接存取存储设备的特点是存取任何一个物理块所需的时间几乎不依赖于此信息的位置，如磁盘。

有三个并发进程：R 负责从输入设备读入信息块，M 负责对信息块加工处理；P 负责打印输出信息块。今提供； l）一个缓冲区，可放置K 个信息块； 2）二个缓冲区，每个可放置K 个信息块； 试用信号量和P、V 操作写出三个进程正确工作的流程。答：1 一个缓冲区：cobegin

Semaphore sread,smanager,sprint;item a[K];int rr,rm,rp;item x;

sread=k;smanager=0;sprint=0;rr=rm=rp=0;process PR()

{while(true){ P(sread);a[rr]=x;

rr=(rr+1)%K;V(smanager);} }

process PM()

{ while(true){ P(smanager);x=a[rm];rr=(rr+1)%K;V(sprint);} } process PP()

{while(true){ P(sprint);x=a[rp];

rr=(rr+1)%K;V(sread);} } Coend

(2）两个缓冲区：

semaphore swrite1, sread1, swrite2, sread2;Swrite1=swrite2=1;sread1 =sread2=0;

item A1[k],A2[k];read1=write1=read2=write2=0;cobegin

process PR { while(true){ P(swrite1);A1[write1]=x;

write1=(write1+1)%K;

V(sread1);} }process PM { while(true)

{ P(sread1);

x=A1[read1];

read1=(read1+1)%K;

V(swrite1);P(swrite2)

A2[write2]=x;

write2=(write+1)%K;V(sread2);}}process PP { while(true)

{ P(sread2);x=A2[read2];

read2=(read2+1)%K;V(swrite2);}}coend

设公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆：正常行车；到站停车。售票员的活动：关车门；售票；开车门。在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V 操作实现它们的同步。

答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。应设置两个信号量：S1、S2;S1 表示是否允许司机启动汽车（其初值为0);S2 表示是否允许售票员开门（其初值为0）。用P、v 原语描述如下：

var S1 , S2 : semaphore;S1=0；S2=0； cobegin{ driver();busman();}coenddriver()begin

while(1){ P(S1)

启动车辆；正常行车；到站停车；V(S2);}end

busman()begin

while(1){ 关车门；V(51)售票;P(S2)开车门；上下乘客； }end

一条公路两次横跨运河，两个运河桥相距100 米，均带有闸门，以供船只通过运河桥。运河和公路的交通均是单方向的。运河上的运输由驳船担负。在一驳船接近吊桥A 时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾P 通过此桥为止。对吊桥B 也按同样次序处理。一般典型的驳船长度为200 米，当它在河上航行时是否会产生死锁？若会，说明理由，请提出一个防止死锁的办法，并用信号量来实现驳船的同步。

答：当汽车或驳船未同时到达桥A 时，以任何次序前进不会产生死锁。但假设汽车驶过了桥A，它在继续前进，并且在驶过桥B 之前，此时有驳船并快速地通过了桥A，驳船头到达桥B，这时会发生死锁。因为若吊起吊桥B 让驳船通过，则汽车无法通过桥B ；若不吊起吊桥B 让汽车通过，则驳船无法通过桥B。可用两个信号量同步车、船通过两座桥的动作。var Sa , Sb : semaphore;Sa:=Sb:=1;cobegin

{ process 驳船 beginP(Sa);P(Sb);

船过桥A、B;V(Sa);V(Sb);end

process 汽车 beginP(Sa);P(Sb);

车过桥A、B;V(Sa);V(Sb);end }coend

假定磁盘有200 个柱面，编号O-199，当前存取臂的位置在143 号柱面上，并刚刚完成了125 号柱面的服务请求，如果请求队列的先后顺序是：86 , 147 , 91 , 177 , 94 , 150 , 102 , 175 , 130 ；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。(1）先来先服务算法FCFS;

(2）最短查找时间优先算法SSTF :(3）扫描算法SCAN。(4）电梯调度。答：(l）先来先服务算法FCFS 为565，依次为143-86-147-91-177-94-150-102-175-130。(2）最短查找时间优先算法SSTF 为162，依次为143-147-150-130-102-94-91-86-175-177。(3）扫描算法SCAN 为169，依次为143-147-150-175-177-199-130-102-94-91-86。(4）电梯调度为125，依次为143-147-150-175-177-130-102-94-91-86。

先来先服务算法 FCFS策略：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。这是一种非剥夺式算法。

最短作业优先算法SJF：以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。这是一种非剥夺式调度算法 例： 作业所需CPU 9 作业作业作业作业

•SJF的作业调度顺序为作业2、4、1、3，平均作业周转时间T =(4+12+21+31)/4= 17

平均带权作业周转时间W=(4/4+12/8+21/9+31/10)/4 = 1.98 •如果对它们施行FCFS调度算法，平均作业周转时间T =(9+13+23+31)/4 = 19

平均带权作业周转时间W =(9/9+13/4+23/10+31/8)/4 = 2.51

最短剩余时间优先SRTF算法

把SJF算法改为抢占式的调度算法：当一个作业正在执行时，一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业 优先级调度算法

这种算法是根据确定的优先级来选取进程/线程，每次总是

选择优先级最高的作业。

第三篇：操作系统总结

什么是OS，OS有哪几个特征？其最基本的特征是什么？

答：操作系统是为了达到方便用户和提高利用率的目的而设计的，控制和管理计算机硬件和软件资源，合理的组织计算机工作流程的程序的集合它具有并发，共享，虚拟，异步性四个基本特征。其中最基本的特征为并发性

2什么是进程及与程序的区别与联系，为什么PCB是进程存在的唯一标志？

进程是程序的一次执行过程，是系统进行资源分配和调度的一个独立单位。

区别：（1）进程是动态的，程序是静态的。（2）进程具有并发性，而程序没有（3）进程是资源分配和处理机调度的独立单位，其并发性受系统制约（4）一个程序多次执行，对应多个进程，不同的进程可以包含同一程序PCB：因为在进程的整个生命期中，系统总是通过PCB对进程进行控制的3处理机三级调度分别完成什么工作？

（1）高级调度：就是作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行

（2）低级调度：就是进程调度，它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作

（3）中级调度：实际上就是存储器管理中的对换功能试说明引起进程调度的时机是什么？

（1）进程完毕（2）时间片用完（3）I/O请求发生某个事件（4）原语：wait操作，阻塞（5）高优先者进入 5什么是临界资源和临界区？

一次仅允许一个进程访问的资源称为临界资源。访问临界资源的代码段称为临街区

6试修改下面生产者---消费问题中，如果将两个wait操作即wait(full)和wati(mutex)互换 位置，或者将signal(mutex)与signal(full)互换位置，结果会如何？

（1）wait(full)和wait(mutex)互换位置后，因为mutex在这儿是全局变量，执行完wait(mutex)，则mutex赋值为0，倘若full 也为0，则该生产者进程就会转入进程链表进行等待，而生产者进程会因全局变量mutex为0 而进行等待，使full 始终为0，这样就形成了死锁.（2）而signal(mutex)与signal(full)互换位置后，从逻辑上来说应该是一样的.7什么是死锁?死锁产生的有哪些

死锁是因多个进程因竞争资源而造成的一种僵局（1）互斥条件：一个资源每次只能被一个进程使用。（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。（4）环路等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。同步机制应遵循的基本准则是什么?

(1)空闲让进（2）忙则等待（3）有限等待（4）让权等待.程序有几种连接方式

（1）静态链接方式（2）装入时动态链接（3）运行时动态链接

10什么是动态重定位方式及为什么要引入动态重定位方式及如何实现？

程序和数据装入内存时需对目标程序中的地址进行修改。这种把逻辑地址转变为内存的物理地址的过程叫重定位

11什么是分页，什么是分段，在存储管理中两者的区别

（1）分页是将一个进程的逻辑地址空间分成若干大小相等的部分，每一部分称作页面，内存划分成与页面大小相等的物理块，进程的任何一页可放入内存的任何一个物理块中,段是信息的逻辑单位，含有一组意义相对完整的信息，更好的来满足用户的需要。

（2）分段是一组逻辑信息的集合，即一个作业中相对独立的部分。多个段在内存中占有离

散的内存单元，对每个段，在内存占有一连续的内存空间，其内存的分配与回收同可变分区的内存分配与回收办法

分页与分段的主要区别是？

（1）页是信息的物理单位，分页是为了实现离散分配方式，以消减内存的外零头，提高内存的利用率（2）页的大小固定，并且有系统决定，而段的长度不固定决定于用户所编写的程序（3）分页作业的地址空间是一维的，段是二维的。

12动态分区存储管理中内存的回收方式

13.什么是对换，对换的分类及主要用途在进程换出时应遵循什么原则

对换是把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把因具备运行条件的进程或者进程所需要的程序或数据调入内存。

分类：（1）整体对换（进程对换）：以整个进程为单位（2）页面对换（分段对换/部分对换）：以页和段为单位

规则：内存空间不够用才换出。系统处于阻塞状态，且优先级最低的进程最先换出。若换入：系统处于就绪状态，且优先级最高的进程最先换入，直至无可换入的进程为止。

14.什么是虚拟存储器虚拟存储器具有哪些特性，最基本的特性是什么？虚拟存储器的容量受哪两方面的限制？

虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

特征：（1）离散性（最基本的特征）（2）多次性（3）对换性（4）虚拟性

虚拟存储器的容量主要受指令中表示地址的字长和外存的容量的限制。

15.在没有快表的分页存储管理中取一条指令需访问几次内存及访问内存的目的，及具有快表的分页存储管理系统的地址变换过程。

两次。第一次：访问内存中的页表，从中找到页的物理块号，再将块号与页内偏移量W拼接，形成物理地址。第二次：从第一次所得的物理地址中获得所需数据

地址变换过程：CPU给出有效地址后，地址变换机构将页号与快表中的所有页号进行比较，若有与此相匹配的页号，则表示所访问的页在快表中，从中读出物理块号与页内地址相拼接，得到物理地址；若访问的页不在快表中，则要访问在内存中的页表，从页表中读出物理块号与页内地址相拼接，得到物理地址，同时，还应将此页表项写入快表中，若此时快表已满，则OS必须找到一个老的并且被认为不再需要的页表项将它换出。

16.什么是紧凑技术及为什么要引入

紧凑：把原来多个分散的小分区拼接成一个大分区的方法

引入：提高内存的利用率，让大容量的作业可以装入并且减少零头或碎片

17程序的局部性原理是什么局限性的两个主要表现方面

局部性原理：（1）程序执行时，除少部分转移和过程调用指令外，大多数条件下任是顺序执行的（2）过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经验就看出过程调用的深度在大多数情况下不会超过5（3）程序中存在许多循环结构，这些虽然只能由少数指令构成但它们将多次执行（4）程序中还包括许多对数据结构的处理

主要表现在：（1）时间局限性（2）空间局限性

18.什么是spooling技术spooling系统有哪些组成Spooling技术是对脱机输入，输出系统的模拟。

组成：（1）输入井和输出井（2）输出缓冲区和输入缓冲区（3）输入进程SPi和输出进程SPo（4）请求打印队列

特点：（1）提高了I/O的速度（2）将独占设备改为共享设备（3）实现了虚拟设备功能

第四篇：操作系统总结

第一部分概述

一、导论

1.操作系统做什么

① 冯诺依曼体系结构

② OS角色：对上：控制程序正确执行，使用方便；对下：资源分配器

③ 核心功能：进程管理，内存管理，文件管理，输入输出，保护和安全

2.计算机系统组织

① 中断

② 存储结构：寄存器→高速缓存→主存→电子磁盘→光盘→磁带

③ I/O结构：I/O的同步、异步；慢速设备（中断）快速设备（DMA）

3.操作系统结构：多道（使CPU总有一个任务执行）、分时（高频率切换任务）

4.进程管理

① 进程有其生命周期，进程是执行中的程序

② 管理活动：创建或删除用户或系统进程；挂起或重启进程；防死锁；提供进程

同步、通信机制

③ 目的：使进程可以运行，相互协调不死锁

5.内存管理

① 目标：内核健壮

② 保护方法：独立操作模式:用户模式，内核模式；计数器定时中断防止死循环

6.存储管理

① 解决问题：速度匹配→缓存（缓存的命中率）

② 等级问题：一致性；多处理器下各缓存的一致性

二、操作系统结构

1.操作系统服务：用户界面，程序执行，I/O操作，文件系统操作，通信，错误检测，资源分配，统计，保护和安全。

2.操作系统的用户界面：命令解释程序，图形用户界面

3.系统调用类型：进程控制，文件管理，设备管理，信息维护，通信

4.系统程序分类：文件管理，状态信息，文件修改，程序设计语言支持，程序装入和

执行，通信，系统工具，应用程序。

5.操作系统结构：

① 简单结构(MS-DOS)：小空间多功能，应用程序直接操作硬件，不安全，无模块，接口和功能层次没有区分

② 分层法：难划分，效率低，但是构造和调试简单化

③ 微内核：包括最小的进程和内存管理以及通信，便于扩充操作系统。

④ 模块化：动态加载模块，允许内核提供核心服务，也能动态的实现特定的功能 ⑤ 组合结构

第二部分进程管理

一、进程

1.进程的概念

① 进程通常包括：程序计数器，栈，数据段

② 进程状态：新建，运行，等待，就绪，终止

③ 进程控制块PCB：进程状态，程序计数器，CPU寄存器，CPU调度信息，内存

管理信息，记账信息，I/O状态信息

④

2.进程调度

① 调度队列：作业队列，就绪队列，设备队列P80

② 调度程序：长期调度程序（作业调度程序）：从作业池中选择进程，并装入内存

准备执行。短期调度程序（CPU调度程序）：从准备执行的进程中选择进程，并为之分配CPU时间。中期调度程序：能将进程从内存中移出。

长短期的区别是执行频率；长期调度控制多道程序设计的程度，中期调度可以降低多道。

③ I/O绑定进程，CPU绑定进程

④ 上下文切换：将CPU切换到另一个进程需要保存当前进程的状态和恢复另一进

程的状态。

3.进程操作

① 进程创程：创建新进程的执行方式（父子进程并发执行；父进程等待直到某个

或全部子进程执行完毕）

新进程地址空间（子进程是父进程的副本；子进程装入另一个新程序）

资源共享（所有/子集/不共享）

② 进程终止

父进程终止子进程的原因（子进程使用了超过它分配的资源；分配给子程序的任务不需要了；父进程结束）

4.进程间通信

① 通信基本模型：共享内存，消息传递

② 共享内存：消费者可能等待生产者；无限缓冲区，有限缓冲区的区别

③ 消息传递：

命名：直接通信（对称寻址：接受者命名发送者；非对称寻址：接受者不需要命名发送者）间接通信（邮箱、端口的参与）

同步：阻塞与非阻塞（发送，接收），同步与异步

缓冲：零容量（无缓冲）；有限容量、无限容量（自动缓冲）

5.客户机-服务器通信：套接字SOCKET，RPC远程调用，RMI远程方法调用

二、线程

1.概述：多线程优点：响应度高，资源共享，经济，多处理器体系结构的利用

2.多线程模型：用户层的用户线程或内核层的内核线程，用户线程受内核支持，而无

需内核管理，而内核线程由操作系统直接支持和管理，这两种方法支持多线程。① 多对一模型（效率比较高，阻塞系统调用的后果）

② 一对一模型（更好的并发功能，缺点是创建一个用户线程就需要一个内核进程）③ 多对多模型（用户可以创建任意多的线程；二级模型=多对多+一对一）

3.多线程问题

① 系统调用fork().exex()

② 线程取消异步取消（立即终止），延迟取消（检查是否应该终止）

③ 信号处理：信号必须有一个处理程序

④ 线程池：优点（处理请求速度快，线程数量可控制）

三、CPU调度

1.基本概念

① CPU区间和I/O区间的概念

② 抢占与非抢占调度的概念（发生在：一个进程从运行切换到等待、运行切换到

就绪、等待切换到就绪、以及终止，1,4非抢占，2,3抢占）

2.调度准则：CPU利用率（使CPU尽量忙），吞吐量（测量工作的方法），周转时间（从

进程提交到完成的时间），等待时间，响应时间

3.调度算法

① 先到先服务调度FCFS（非抢占的）

② 最短作业优先调度SJF（抢占，最优算法，难知道下一CPU区间长度，用于长

期调度）

③ 最短剩余时间优先调度SRTF（强占式的SJF，适合长期调度）

④ 优先级调度（问题：无穷阻塞或饥饿，老化来解决；非抢占方式不用占用CPU

切换）

⑤ 轮转调度RR（专为分时系统设计，是可抢占的，时间片过大变为FCFS，时间片

过小等待时间段，但是切换频繁）

⑥ 多级队列调度（前台与后台的调度算法不同，RR与FCFS）？

⑦ 多级反馈队列调度

⑧ 实时调度：硬实时（在特定硬件上保证时间），软实时：尽力而为，优先级不变，没有饥饿现象

4.算法评估

① 确定性模型甘特图

② 排队模型 N=入*W（N平均队列长度，W为队列的平均等待时间，入为新进程

到达队列的平均到达率）

③ 模拟

④ 实现

四、进程同步

1． 背景：竞争条件：共享内存，共享变量

2． 临界区问题

① 临界区解决方案：进入去，临界区，退出区，剩余区

② 效果：互斥，有空让进，有限等待

③ 证明：1.互斥，临界区一个时间只能有一个进程2.前进，临界区内无进程执行，那么只有那些不在剩余区内执行的进程可参加选择，这种选择不能无限延迟3.有限等待，从一个进程做出进入临界区的请求，知道该请求允许为止，其他进程允许进入其临界区的次数有上限。

④ PETERSON算法

3． 信号量：计数信号量，二进制信号量

① 技术信号量用于控制访问：当每个线程需要使用资源时，需要对该信号量执行

acquire()操作，当线程释放资源时，需要对该信号执行release()操作。

② 用信号量解决同步问题

4． 管程：管程结构确保一次只有一个进程能在管程内活动

5． 经典同步问题

① 生产者消费者问题

② 读者写者问题

③ 哲学家吃饭问题

五、死锁

1.死锁特征

① 必要条件：互斥，占有并等待，非抢占，循环等待

② 资源分配图：分配图没有环则没有死锁，有环则有死锁；有环则可能有死锁。

2.死锁预防

① 互斥：通常不能通过否定互斥条件来预防死锁：有的资源本身就是非共享的。② 占有并等待：协议一：每个进程在执行前申请并获得所有资源；协议二，允许

进程在没有资源时才可以申请资源。协议缺点：资源利用率低，可能发生饥饿。③ 非抢占：协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那

么其现在已分配的资源都可被抢占。

④ 循环等待：对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请

资源。

3.死锁避免

① 安全状态:如果系统能按某个顺序为每个进程分配资源并能避免死锁，那么系统

状态就是安全的。

② 单实例：资源分配图：申请边，分配边，需求边

③ 多实例：银行家算法Available(向量),Max（矩阵）,Allocation（矩阵），Need(矩

阵),4.死锁检测

① 单实例：等待图：当且仅当等待图中有一个环时，系统存在死锁

② 多实例：类似银行家算法

5.死锁恢复

① 进程终止：终止所有死锁进程；一次只终止一个进程，直到取消死锁循环为止 ② 资源抢占：问题：选择一个牺牲品；回滚；饥饿

第三部分内存管理

一、内存管理

1.背景

① 地址绑定：编译时（编译时就知道进程将在内存中的驻留地址，那么就可以生

成绝对代码），加载时（生成可重定位的代码），运行时（如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才进行）

② 逻辑地址（CPU所生成的地址）物理地址（内存单元所看到的地址）

③ 动态加载（子程序只在调用时加载，优点不用的子程序绝不会被加载）④ 动态链接与共享库（将连接延迟到运行时）

2.交换（没看）

3.连续内存分配：单分区，多分区

4.非连续内存分配：分页（分页技术不会产生外部碎片）

5.动态存储分配问题：首次适应，最佳适应，最差适应

6.页表结构：层次页表，哈希页表，反向页表

二、虚拟内存

1.背景

① 多道尽可能多的程序，这也是内存管理的目标

② 虚拟内存好处：可以运行比物理内存大的程序；更快的启动和响应（载入更快）；

更多的多道；更容易的共享文件盒地址空间；更少的输入输出。

2.按需调页：在需要时才调入页

① 有效位-无效位来来确定页是否在内存

② 有帧就加入，无帧就换页，页错误处理流程：检查内部表确定引用是否合法→

非法则终止，合法则调入→找到空闲帧，装入内存→修改内部表→重启指令 ③ 按需调页的有效访问时间：effective access time=(1-p)*ma+p*处理页错误的时间

3.页面置换（引用串）

① FIFO 先入先出

② 最优算法：向后看，换页的时候看内存中哪个页最晚用；是所有算法中产生页

错误最低的算法；问题：需要引用串的未来知识

③ LRU最近最少使用算法：往前看，内存中哪页在列表序列中离的最远，无Belady

异常

④ 算法实现：计数器（最近最少使用：换计数器值最小的）代价大：系统级，可

能溢出，一定会写全表

页码堆栈：每当引用一个页，该页就从栈中删除并放在栈顶。严格实现，但是代价高。

二次机会：引用位，引用时改为1,；换页时，是1则置零，是0则换

计数算法：LFU最不经常使用，MFU最经常使用（可采用老化）

4.帧分配

① 分配策略限制：所分配的帧不能超过可用帧的数量，大于最小需求

② 每个进程帧的最少数量是由体系结构决定的，而最大数量帧是由可用物理内存

决定的。

③ 当指令完成之前出现页错误，该指令必须重新执行

④ 帧分配方法：

固定分配：平均分配、按比例分配

优先级分配：全局置换（帧数可变），局部置换（固定）；全局置换算法的一个问题是进程不能控制其页错误率，但是全局置换通常会有更好的系统吞吐量，且更为常用。

5.系统颠簸

① 颠簸产生的原因：抢帧→I/O上升→CPU使用率降低→多道继续增加→忙于换页 ② 工作集合策略防止了颠簸，并尽可能的提高了多道程序的程度，可以通过页错

误频率PFF来直接测量和控制页错误以防止颠簸。上限之上分配更多，下限之下，减少帧数

6.其他问题

① 预调页关键问题：采用预调页的成本是否小于处理响应页错误的成本。② 页大小问题：最佳页大小的选择，大页，小页

③ 优化程序结构

第四部分存储管理

一、文件系统接口

1.文件概念

① 文件是逻辑外存的最小分配单元，即数据除非在文件中，否则不能写到内存中。② 文件操作：写，读，重定位，删除，截短

③ 文件加锁：共享锁，专用锁；强制，建议文件加锁机制

2.访问方法：顺序访问，直接访问，其他方法（索引）

3.目录结构

① 目录操作：创建文件，删除文件，遍历目录，重命名文件，跟踪文件系统 ② 评价目录结构：命名（不同文件同名），分组（同一文件不同命名）

③ 单层结构目录（命名，分组均无），双层结构目录（可命名不可分组），树状结

构（绝对，相对路径；可命名分组），无环图目录（硬链接，软链接），通用图目录

二、文件系统实现

1.文件系统结构：应用程序→逻辑文件系统→文件组织模块→基本文件系统→I/O控

制→设备

2.目录实现：线性列表（编程简单，运行费时，查找文件需要线性搜索）

哈希表（采取策略避免冲突）

3.分配方法

① 连续分配：每个文件在磁盘上占有一组连续的块；困难时为新文件找到空间，外部碎片问题也可能很大，确定文件分配多大空间，② 链接分配：解决了连续分配的所有问题；必须顺序访问文件，指针需要空间，由于指针分配在整个磁盘，可靠性就成了一个问题。

FAT文件分配表：改善了随机访问时间，但是需要大量磁头寻道时间

③ 索引分配：把所有指针都放在一起，构成索引块；支持直接访问，且没有外部

碎片问题，但是会浪费空间；索引块分多大是个问题

链接方案（一个索引块可以指向另一索引块构成链接）

多层索引（第一个索引块指向第二个索引块，第二个指向文件数据块）

组合方案P404 N级间接块（计算）

4.空闲空间管理：为向量（1空0满）块号码计算：（值为0的数字）*（一个字的位

数）+第一个值为1的位的偏移；链表（所有空闲的块用链表链接起来）；组（将N个空闲块的地址存储在第一个空闲块中）；计数（）

第五篇：操作系统总结

操作系统基本基础概念

多任务是指用户可以在同一时间内运行多个应用程序,每个应用程序被称作一个任务。像Windows、LINUX就是支持多任务的操作系统。每个任务使用由操作系统分配的短暂的时间片(Timeslice)轮流使用CPU,由于CPU对每个时间片的处理速度非常快,在用户看来好像这些任务在同时执行，这叫做时间片轮转调度法。还有更多的多任务调度方法。

实时系统

（REAL TIME system）是指系统能及时的响应外部时间的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。分为硬实时任务和软实时任务，系统对任务的截止时间有要求否则会出现难以预测的结果，这就是硬实时任务，反之要求不是很严格则为软实时任务。

操作系统的基本特性

并发与并行：并发性是两个或多个事件在同一时刻发生。而并行性是两个或多个事件在同一时间间隔内发生。

进程：为了使多个程序能并发的执行，系统必须为每个程序建立进程（process）。简单说来~进程是指在操作系统中能独立运行并作为资源分配的基本单位。他是由一组机器指令数据、堆栈等组成的，是一个能独立运行的活动实体。多个进程之间可以并发的执行和交换信息。一个进程在运行时需要一定的资源，如CPU、内存空间、IO设备等。

我的注解：进程很重要。Linux的进程之间的关系可以这样描述：一个完整的main函数运行的时候，在linux里是以进程的形式存在的。系统启动之后运行的第一个进程的进程号是1，叫做init进程，一切进程都从它派生出来，一个父进程可以派生另一个进程，即为子进程，这俩进程为并行关系。子进程也可以创建子进程。

进程的创建在linux里边用fork（）函数它有两个返回值，一个是在父进程中返回，返回的是子进程号，一个是在子进程中返回，如果子进程创建成功，则返回的是0。子进程是父进程的一个拷贝，现代的进程创建都用vfork（）创建子进程之后，并不拷贝全部的进程空间，只有在用到时才拷贝，叫做写时复制技术（copy on write）。

Linux里边这样创建子进程：

pid_t pid=fork();//这里的pid_t是一种数据类型（如int），这里代表进程号（实质上也是个整形变量int）

If(pid==0){这里边就是子进程代码}

Else if(pid>0){这里边是父进程代码，pid的值是子进程的进程号PID}

线程：通常在一个进程中可以包含若干个线程，他们可以利用进程所拥有的资源。在引入线程的操作系统中，一般都把进程作为分配资源的基本单位。而把线程作为独立运行和独立调度的基本单位。优点：运行效率更高。

进程的状态：一般分为就绪状态。执行状态。阻塞状态。

操作系统产生死锁的原因：1.竞争资源。2.进程间推进顺序非法。比如说：一个进程占有一个资源A，当他运行到需要用到被另一个进程占用的资源B时，没有得到，于是进入等待退出运行，而这个占有资源B的进程还想得到资源A，但是占有A的进程此刻在休眠，也没得到，所以这个进程也进入等待退出运行。这样两两相互等待造成了死锁。解决方法：1.在进程运行开始时就把所有资源占好。2.按顺序加锁。比如要得到资源B首先要对A加锁，如果得不到就不能加锁。所有进程都按照这个方法进行。