操作系统导论

• 定义
  • 操作系统是一个大型的系统软件，由大量的程序模块和数据结构集合而成
• 操作系统地位
  • 计算机硬件->操作系统->语言编译程序->应用软件、支撑软件
• 操作系统的作用
  • 提高效率：管理和分配硬件、软件资源，合理地组织计算机的工作流程
  • 扩展功能：提供软件的开发与运行环境，是计算机从最基本的硬件(裸机)不断的得到扩充
  • 方便性：提供良好的、一致的用户接口，弥补硬件系统的类型和数量差别
• 操作系统的功能
  • OS主要任务是对系统中的软件，硬件实施有效的管理，以提高系统资源的利用率
  • 分为：进程管理、作业与用户界面管理、存储管理、设备管理、文件管理

OS发展史/主要分类

• 手工操作-电子管时代
  • 特点：没有操作系统，用户(一个程序)独占全机cup
  • 编程语言：机器语言
  • 输入输出：纸袋或卡片
• 单道批处理系统（监控程序Monitor阶段）-晶体管
  • 使用汇编语言
  • 批处理分为：联机批处理和脱机批处理
• 多道批处理系统，集成电路
  • 特点：并发性、共享性、随机性
  • 由调度程序来分配cpu资源
  • 核心技术：作业调度、资源共享、内存使用（覆盖，交换和虚拟存储）、内存保护、文件非顺序存放和随机存取
  • 出现了：作业管理、处理机管理、存储管理、设备管理、文件系统管理等概念
• 分时操作系统-大规模集成电路
  • 由两个及以上的事件按时间划分轮流的使用系统资源
  • 特点：同时性或多路性、独占性、及时性、交互性
  • 调进调出是实现分时系统的主要方式
  • 响应时间是衡量分时系统性能的重要标志
  • 响应时间T与时间片q和用户个数n之间的关系为：T=nq
  • 现在的许多操作系统都具有分时处理的功能，在此基础上，发展分化了：实时系统、通用系统、个人系统等。
• 微机
  • 和传统主机的os相比，微机的文件管理和交互管理能力增强，其他功能减弱
  • 典型代表：windows
  • 特点：单用户多任务、交互性非常强、以实时多任务方式支持多媒体处理
• 网络操作系统
  • 网络操作系统是在通常操作系统的功能上提供网络通信和服务功能的系统
  • 计算机网络的基本概念：
  • 计算机网络：是计算机技术与通信技术相结合的产物，是互连起来的计算机的集合
  • 背景：微电子技术的发展与进步、计算机的应用社会化、通信技术的进步和普及
  • 特征：资源共享性；独立自主性
  • 微机网络：已成为计算机网络中最活跃的一个分支
  • 功能：高效可靠的通信、共享资源有效的管理、电子邮件、文件传输、共享硬盘、打印机等服务、网络安全管理、提供互操作能力
• 分布式操作系统
  • 以计算机完了为基础的计算机系统，包含多台处理机，每台处理机完成系统中指定的一部分功能，从硬件上和局域网没有区别，关键是软件的不同
  • 特点：所有系统任务可在系统中任何处理机上运行，自动实现全系统的任务分配并自动调度各处理机的工作负载
  • 功能：进程迁移、分布式同步、任务分配、资源管理
• 多处理操作系统
  • 是由多台处理器组成的计算机，多处理的出现是为了提高系统性能和可靠性
• 现在流行的OS：蓝色巨人的OS/2、大型计算机IBM OS/390、自由之梦Linux、Sun的solaris、常青树Unix、Windows系列
• 进程与资源
  • 进程定义：一个进程就是一个程序针对某个数据集（处理对象）的一次执行过程
  • 资源分类：共享资源、独占资源、可抢占资源、不可抢占资源、永久资源、临时资源
• OS依赖的硬件环境(基本都是遵循冯·诺依曼提出的计算机体系架构)
  • 主存器
  • 处理机(CPU): 运算器、控制器、寄存器
  • 外设控制器(键盘、鼠标...)

  60年代硬件两个重大进展：中断技术、通道技术

  • 通道是一台功能单一结构简单的I/O处理机，它单独与CPU连接，并直接控制外部设备，与内存进行数据传输
  • 通道有专用的I/O处理器，可与CPU并行工作。具有自己的指令，可编程实现复杂的I/O处理
  • CPU与通道之间为主(CPU)从(通道)关系, 采用通道进行数据传输的过程如下：CPU向通道发出I/O指令；通道执行程序进行I/O操作；完成或出错时以中断的方式请求CPU处理

  中断

  • 中断：指在收到外部中断信号后，停止原来工作，转去处理该中断事件，完毕后回到原来断点继续
  • 中断处理过程分为：中断请求、响应、中断点、中断处理例程、中断返回
  • 中断分类：硬件中断(硬件故障、I/O中断、外部中断)、软件中断(程序中断<如：地址越界>、访管中断)

  硬件保护机制

  • 核心操作只允许系统进程做
  • 特权指令和非特权指令
  • 处理器的工作态：管理态，用户态
  • PSW中的值决定处理器的工作态

研究分析OS的几种观点

• 资源管理观点-OS作为资源管理器:
  • 功能：跟踪资源状态、分配资源、回收资源、保护资源
  • 资源分类：处理机、存储器、I/O设备、信息(程序和设备)。相应的可将操作系统分为四类管理器：处理机管理、存储管理、设备管理、信息管理(文件系统)
• 进程观点-进程管理是OS的核心工作
  • 进程之间存在相互制约的关系，分为用户进程和系统进程
• 软件分层、扩充机器的观点-虚拟机
  • 提供硬件的高层界面，取消硬件限制
  • 操作系统提供无限的内存、无限的CPU
  • 扩充机器，功能更强大，使用更方便

  使用户在不必涉及和了解硬件工作细节的情况下能方便的使用计算机，而为用户所提供的一个等价的扩展计算机，称为虚拟计算机

目前微机常用操作系统

DOS

• 特点
  • 单用户、单任务；突出文件管理和设备管理；结构简单；字符命令行式的用户界面；通过系统配置文件在引导过程中影响操作系统的性能
• 开机->IO.SYS->MSDOS.SYS->CONFIG.SYS->COMMAND.COM->AUTOEXEC.BAT

Windows

• 特点
  • 单用户、多任务
  • 虚拟存储管理系统
  • 图形用户界面GUI
  • 支持多种文件系统
  • 设备无关性，可以在不同的硬件设备上运行
  • 集成了网络功能

Unix

• 特点
  • 多用户、多任务
  • 移植性好
  • 可装卸的树形结构的文件系统
  • 请求页式的虚拟存储系统
  • 良好的用户界面
  • 强大的网络功能

Linux

• 特点
  • 多用户、多任务
  • 符合POSIX标准
  • 支持多文件系统
  • 具有强大的网络功能
  • 支持的硬件多
  • 软件丰富

操作系统的结构

• OS的设计要求：
  • 可靠性高、维护性好、并发性好，资源利用率高、适应性强
• 层次结构
  1. (上层)最靠近用户与用户作业有关，与资源控制管理无关的模块，如用户界面管理。
  2. (中间层)文件设备、设备管理、存储管理
  3. (底层)最靠近硬件的、直接与硬件有关的模块，如IO,中断维持进程工作的基本模块

应用程序	应用程序	应用程序	应用程序
应用层序接口			api接口
子系统	子系统	子系统	子系统
核心程序：			内存管理、设备管理、作业管理
设备驱动	设备驱动	设备驱动	设备驱动

• 内核加外核程序结构

核心态	用户态
内核程序	核外程序

• 操作系统的引导
  • OS的启动只能靠‘自举’，即：自己把自己一步步导入内存，开始工作。(通电即启动)
  • 关机时也必须按一定顺序逐个结束程序，并保证各个有关数据结构的完整
• 操作系统的基本工作机制
  • 程序用户 -> 编程接口 -> OS
  • 普通用户 -> 命令接口 -> OS
• 系统调用
  • OS提供若干个实现各种核心功能的子程序，供编程人员在应用程序中以一种专门的方式加以调用
  • 开发它的动机：OS的核心功能不允许用户直接使用，但有时用户程序又必须使用（比如：各种I/P操作）
  • 工作原理：通过一个类似硬件中断处理的机构，暂时中止应用程序的执行，并将处理机状态改为和心态，再执行系统调用，完成后再回复应用程序的执行
  • 系统调用是OS给程序员的唯一接口

用户与操作系统

作业及管理

1. 作业及相关概念

• 作业：用户在一次解题过程中或一个事务处理中要求计算机系统所作工作的总和，它是用户向计算机系统提交一项工作的基本单位
  • 用户的观点：再一次业务处理过程中，从输入程序和数据到输出结果的过程
  • 系统观点(针对作业镜像资源分配)：作业由程序及数据(作业体)和作业说明书(作业控制语言)
• 作业步：是一个作业的处理过程中，计算机所做的相对独立的工作
• 作业流：批量系统中需要将一批作业依次输入到辅助存储器中，形成作业流

2. 作业和进程的关系

• 父进程和子进程
  • 每个作业拥有一个独立的根进程和0到多个子进程
• 作业是用户提交的任务实体，进程则是任务的执行实体
• 作业的管理和进程的管理不尽相同

3. 对作业的管理

• 进程管理是一个进程从建立到结束的过程中的管理
• 作业管理则是对整个作业的组织、调度、控制

4. 作业类型

• 脱机作业：也称为批量型操作，在一次业务处理过程中，从输入程序和数据到输出结果的全过程
• 联机作业：也称为交互型操作或终端操作，是指用户直接与计算机系统交互作用来控制作业的运行
• 在兼顾分时操作与批量处理的系统中，终端作业称为前台作业，而批量作业称为后台作业

5. 作业控制

• 脱机锁业控制：用户输入作业控制卡或作业说明书，整个作业的运行由系统控制
• 联机作业控制：通过人机会话方式控制作业运行
• 作业说明书
  • 作业基本情况的描述：作业名称、作业主人的用户名、使用的语言、完成期限等
  • 作业控制的描述：控制方式、作业各个阶段的先后顺序与衔接以及如何传递信息、在不同的情况下分别做什么操作、如果出现错误或故障应该如何处理，等待
  • 作业对系统需求的描述：CPU处理时间、运行的优先级、内存空间、外存空间、输入输出设备的类型和数量、使用的软件资源(库函数、实用程序)，等等
• 作业的状态：提交、后备、运行、完成
• 作业调度：任务是根据当前系统中的空闲资源，并按照一定算法在后备作业队列中选取一个适合的作业投入运行（改变作业状态、分配资源、创建进程、回收资源），作业调度也称为宏观调度
  • 调度算法的评价因素：
    • 作业吞吐率（单位时间里处理作业的个数）：运行尽可能多的作业
    • 充分利用资源：CPU忙、I/O设备忙
    • 对各作业公平、合理、使用户满意：执行时间长短、等待时间等
  • 周转时间：从提交到完成的时间。等待+运行
  • 常见的调度算法
    1. 先来先服务(FIFO)：按照作业进入系统的先后次序进行调度，先进先调度；即启动等待时间最长的作业
    2. 短作业优先(SJF)：以要求运行时间长短进行调度，即启动要求运行时间最短的作业
    3. 高响应比优先：响应比最高的作业优先启动；响应比=(估计运行时间+等待时间)/估计运行时间;优点：公平，吞吐率大；缺点：增加了计算，增加了开销
    4. 高优先级优先：由用户指定作业优先级，优先级高的先启动
    5. 资源均衡型调度：把作业分类，作业调度从不同类型作业中去调度作业，根据作业对资源要求分类:I/O型、CPU型、均衡型

系统调用

** 系统调用是操作系统提供给润软件开发人员的唯一接口，开发人员可利用它使用系统功能。OS核心中都有一组实现系统功能的过程(子系统),系统调用就是对上述过程的调用 **

1. 系统调用的一般概念

• 算态与管态：计算机系统中的程序可分为系统程序与用户程序两类。处理器运行系统程序的状态称为管态、特权状态或系统状态;运行用户程序的状态为算态、目态或用户态。通常在程序的状态字中设置
• 特权指令与访管指令：
  • 特权指令是一类只能在管态下而执行的特殊机器指令。分为：传送程序状态字指令；启动、测试和控制外设指令；存取特殊寄存器指令
  • 访管指令是用户在程序中用来调用操作系统提供的子功能合集。其中每一个子功能称为一个系统调用命令，也称为一条广义指令(若干条机器指令构成，用以完成特定功能的一段程序)。主要功能分为：实现从算态到管态的改变；在算态下由操作系统代替用户完成请求；操作系统工作完成后由管态返回算态

2. 系统调用及其作用：为了保证OS不被用户程序破坏，不允许用户程序直接访问OS的系统程序和数据，只能用系统调用访问。用户在程序中调用操作系统提供的子功能称为系统调用。利用系统调用，可以动态请求和释放系统资源，完成与硬件相关的工作以及控制程序的执行等
   • 系统调用是特殊的过程调用，由特殊的机器指令（广义指令）实现
   • 系统调用指令还将系统转入管态
3. 系统调用与一般过程调用的比较
   • 相同点：改变指令流程，转去执行公用程序段
   • 不同点：
     • 运行状态：一般过程调用，调用程序和被调用程序都运行在相同状态；而系统调用，调用程序在算态，被调用程序在管态
     • 申请机制：一般过程调用不须转换系统状态，直接转向被调用过程；而系统调用要先通过软件中断机制将系统由用户态转换为和心态，在OS核心分析后，再转向相应的系统调用处理子程序
     • 调用后的处理：一般过程调用执行完一定返回原来的调用程序，但系统调用完，未必回到调用处
4. 系统调用类型：系统的功能分为两部分：1系统自身所需的；2作为服务提供给用户的
   • Linux系统调用的类型：
     • 进程控制类型系统调用：创建和中止进程、等待子进程结束、获得和设置进程属性、执行一个可执行文件(覆盖调用者)、进程暂停
     • 进程通讯类系统调用：消息传递方式（打开/接收连接、发送/接收消息）;共享存储方式（建立存储区、建立连接、读/写存储区）
     • 文件管理类系统调用：创建和删除文件、打开和关闭文件、读写文件、移动读写指针、改变文件属性、共享的连接和去连接、建立目录
     • 信息维护类系统调用；设置和获得系统时间、获得进程时间、设置文件访问和修改时间、获得当前系统名称串/标准名/在网络中的名称
     • 存储管理类系统调用：如获取作业进程占用的内存区域信息等等
     • 设备管理类系统调用：如打开设备、获取或设置某设备的信息、向设备输入等等
5. 系统调用的实现过程: 需要有一个类似于硬件中断处理的处理机构（陷入硬件机构）。当用户使用操作系统调用时，产生一条相应的指令，处理机在执行到该指令时发生相应的中断，并发出有关的信号给该处理机构，该处理机构在收到了处理机发来的信号后，启动相关的处理程序去完成该系统调用所要求的系统

• 中断和陷入硬件机构
  1. 中断是CPU对系统发生的某（外部）事件的响应
  2. 陷入(内中断，捕获)是由CPU内部事件引起的中断如：非法指令、地址越界、溢出、电源故障等。(陷入由执行现行指令引起，中断则与现行指令无关。还可以把由于系统调用引起处理机中断的指令称为陷入或异常指令(或访管指令)，或软中断指令。从中断的观点看，引起中断的事件就是系统调用本身)
  3. 每个系统调用都对应一个事先给定的功能号。在陷入指令中必须包括对应系统调用的功能号，而且，还带有传给陷入处理机构和内部处理程序的有关参数
  4. 中断和陷入向量：必须为系统调用功能的各个程序编造陷入（中断）向量表，每个表目由入口地址和处理机状态字PSW两个字组成；陷入处理机构把陷入指令包含的功能号与入口地址表项相对应，执行对应的子程序。
  5. 保护和恢复现场：在进入系统调用之前，在系统栈保护处理机现场。在系统调用结束后要恢复处理机现场

windos的用户界面-图形用户接口GUI

1. 窗口系统(window system)的特点

• 利用图形元素表示功能：将各种图形元素显示在屏幕上，用户可以通过操纵图形元素(如：餐单、图标)来执行相应的功能
• 同屏多窗口与并发进程相对应：屏幕上同时显示多个窗口；一个进程可以对应一个或多个窗口；窗口动态创建、改变、撤销
• 输入方式：鼠标指针点击(或其他定位设备)和键盘输入；通常是即时交互一致的图形元素风格可方便用户学习和使用（如：按钮、滚动条）
• 优点：操作直观，可与多个进程交互，便于进行多媒体处理。简而言之：交互的并发性好、传递信息量大\

2. 窗口系统的图形元素及其状态

• 窗口：屏幕上的矩形区域
  • 包括：标题条、边框、窗口角、系统菜单、按钮、滚动条
  • 状态：当前/非当前窗口、窗口的前后遮盖、焦点
• 图标：供鼠标指针点击
• 鼠标指针：通常对应屏幕上的光标
• 按钮：提供单项或多项选择
• 菜单：弹出菜单、下拉菜单
• 对话框：临时窗口，显示提示信息

3. windows的操作命令接口

• windows是运行在微机上的单用户多任务操作系统，用户以联机的方式向系统提供终端型作业
• windows采用的是事件驱动机制的命令界面，用户使用鼠标或键盘在窗口内对图标、菜单、按钮等对象进行相应的操作，都会产生对应的事件Event

4. 编程接口

• windows采用的是内核加核外程序的结构形式，但它的内核并不是自己的功能子程序，而是以系统调用的方式提供给应用程序的编程人员，windows通过一组包含在动态链接库中的函数来提供服务，这些函数就称为‘win32应用程序编程接口api’
• 所谓动态链接库就是一种包含许多函数过程的可执行代码库，应用程序调用这些函数的过程，并不是在编译链接时就把函数的代码放进自身的执行文件中，而只是插入那些函数在库中的定位信息，等到应用程序实际运行到该调用时才转移到动态链接库中
• win32api既包括许多关于用户程序环境、图形界面的一般函数，也包括许多对操作系统核心服务的调用
  • kernel32.dll 操作系统核心功能服务
  • user32.dll 主要用来控制用户界面
  • gdi32.dll 主要辅助图形操作

进程管理

进程

进程的基本特征

1. 程序的顺序执行和并发执行

• 程序的执行有两种方式：顺序执行和并发执行
• 顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统
• 现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率
• 顺序执行的特征：
  • 顺序性：按照程序结构所指定的次序（可能有分支或循环）
  • 封闭性：独占全部资源，计算机的状态只由该程序的控制逻辑所决定
  • 可再现性：初始条件相同则结果相同
• 并发执行：
  • 并发执行：在多道程序下，任意时刻系统中有多个活动并发执行。这是现代os的一个基本特征
  • 资源共享：系统中的硬件资源和软件资源由多道用户程序共同使用，资源的状态由多道程序所决定。这是现代os的一个基本特征
  • 间断（异步）性：‘走走停停’，一个程序可能走到中途停下来，失去原有的时序关系
  • 失去封闭性：共享资源，受其他程序控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征
  • 失去可再现性：程序与CPU执行的活动之间不再一一对应，程序经过多次的运行，虽然其各次的环境和初始条件相同，但得到的结果却各不相同
  • 相互作用和制约性：系统中并发执行的程序具有相互独立的一面（表现在每个程序为用户提供特定的功能，它们之间相互独立），但是有时也会直接或间接的发生相互依赖和制约
• 概念：进程没有非常确切的定义，为了强调进程的并发性和动态性将其定义为：进程是程序的一次执行，该程序可以与其他程序并发执行。进程包括程序、程序运行需要的存储空间和运行时的现场场景，是系统进行资源分配和调度的一个独立单位
• 动态性：是进程实体的执行过程，它由创建而产生，由调度而执行，因某事件而暂停，由撤销而消亡
• 并发性：多个进程同时存于内存中，一起向前推进，并发执行
• 独立性和异步性：进程是独立获得资源和独立调度的基本单位，由各自的工作环境和内存空间。其完成速度不确定，不同步
• 相互制约性：相互调用的进程间直接制约，其他进程间竞争软件硬件资源而间接制约
• 结构性：由程序+数据+进程控制块组成了进程实体，其中进程控制块是进程存在的标志

进程状态及其转变

1. 进程的三种基本状态及其转换

• 进程在生命期内处于且仅处于三种基本状态之一
• 运行态（Running）:当一个进程在处理机上运行时，则称该进程处于运行状态
• 就绪态(Ready)：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行
• 等待态(Blocked)：当一个进程正在等待某一事件发生(例如：请求I/O)而无法运行时称为等待态
• 状态转换：在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换\
  • 就绪->运行:调度程序选择一个新的进程运行
  • 运行->就绪：运行进程用完时间片被中断或在抢占调度方式中，因为一高优先级进程进入就绪态
  • 运行->等待：进程发生I/O请求或等待某事件时
  • 等待->就绪：当I/O完成或所等待的事件发生时
• 阻塞即运行到等待的过程；唤醒即等待到就绪的过程
• 新建是指进程正在创建过程中，操作系统正在为它分配资源
• 退出是指进程已经结束运行，退出后操作系统需要回收一些资源并撤销它

2. 细分的进程调度状态-挂起状态

• 所谓挂起则是强行使进程从内存换到外存。由于终端用户及操作系统的需要（排除故障或为系统减负），为了能够将指定进程暂时静止下来，增加了挂起等待和挂起就绪态，原等待和就绪改称为活动等待和活动就绪状态
• 运行或活动就绪->静止就绪，活动等待->挂起等待
  • 通过挂起操作(suspend)
• 挂起就绪->活动就绪，挂起等待->活动等待
  • 通过激活操作(activate)
• 挂起等待->挂起就绪：当等待的事件发生时

进程的描述

1. 进程的组成：通常由三部分组成

• 程序：描述了进程所要完成的功能，是进程执行时不可修改的部分
• 数据集合：程序执行时所需要的数据和工作区，为一个进程专用，可修改
• 进程控制块PCB(process control block):包含了进程的描述信息和控制信息，是进程动态特性的集中反应

2. 进程控制块PCB

• 为了对进程进程有效的控制和管理，系统为每一进程设置一个进程控制块，PCB是进程存在的唯一标志。通常包含以下几类信息：
  • 进程描述信息
    • 进程标示名(Process ID):也称为标识符或标识数，为进程的内部标识，用来唯一标识一个进程，通常是一个整数
    • 进程名：为进程的外部标识，通常基于可执行文件名（不唯一）
  • 进程控制信息
    • 当前状态：进程当前所处状态，为进程调度之用
    • 优先级：进程需要处理的缓急程度标识
    • 程序和数据的地址：程序和数据所在的内存和外存地址
    • 队列指针或链接字：处于同状态的进程链接指针
  • 资源占用信息
    • 进程执行时除CPU外的资源的需求、分配、控制信息
  • CPU现场保护信息
    • 它由处理机各种寄存器(通用寄存器、指令计数器、程序状态字PSW、用户栈指针等)的内容所组成，该类信息使进程被中断后重新执行时能恢复现场从断点处继续运行
• PCB的作用
  • PCB是系统感知进程存在的唯一标志，是系统管理的实际对象
  • 操作系统对进程进行各种控制、调度、都离不开对PCB的读写
  • 其他存储如存储管理、设备管理、文件管理等也都是面向进程展开的也都离不开对PCB的读写

3. 进程与程序的区别

• 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件，可以复制
• 进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存
• 进程与程序的对应关系：通过多次执行一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序
• 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块

进程控制

• 处理机的执行状态分为两种：
  • 系统态(核心态、管态):有特权，能执行所有指令，能访问所有寄存器和存储区
  • 用户态（目态、算态）：无特权，只能执行规定指令，只能访问指定的寄存器和存储区
• 用户程序运行在用户态，它不能执行OS执行，不能访问OS区域，防止对OS的破坏
• 进程控制包含在OS的内核(Kernel)中,它常驻内存，执行效率高
• 操作系统内核是系统硬件的首次延申，通过执行各种原语操作来实现对进程的控制功能（创建、调度、通讯、撤销等）[原语（Primitive）:由若干条机器指令构成，并用以完成特定功能的一段程序，而且这段程序在执行期间不允许中断。原语又称为原子操作（Atomic Operation）过程，作为一个整体而不可分隔--要么都完成，要么都失败]
  • 内核中包含的进程控制原语主要有：进程创建原语、进程撤销原语、等待原语、唤醒原语、挂起原语、激活(解挂)原语
• 进程的创建-进程何时创建？-引起创建进程的事件
  • 用户登录、作业调度、提供服务、应用请求
  • 用户登录时，由OS为合法终端创建一个进程
  • 调度到某个批处理作业时，由作业调度程序创建
  • 运行程序请求提供服务(如：打印文件)，由OS创建
  • 运行中进程因自己需要，由它自己创建子进程
• 进程图：OS允许进程创建子进程，子进程还可以创建自己的子进程，从而形成树形的进程家族。进程图是用于描述进程家族关系的有向图，子进程可以继承父进程所拥有的资源
  • 树形结构系统的优点：
    • 资源分配严格：祖先拥有进程家族的所有资源，子进程可在祖先进程所拥有的资源中进行分配、使用、归还
    • 进程控制灵活：可根据选需要给与进程不同的控制权力，而且可根据需要创建多个子进程并行工作，协同完成任务
    • 进程层次清晰，关系明确
• 进程如何创建？-有两种方式：
  • 系统生成就会建立起一些系统进程：主要用于创建常驻内存的系统进程
  • 经创建原语产生的进程：主要用于创建非常驻的系统进程和用户进程
• 进程的创建过程：一旦发现了要求创建新进程的事件，OS便调用创建原语，按以下过程创建新进程：
  • 索取一个空白PCB，一旦成功，则分配一个唯一的进程标识符
  • 为新进程的程序和数据分配内存空间
  • 初始化进程控制块：初始化标识符信息（填入）、处理机的状态信息（指令指针，栈指针）和控制信息（状态，优先级...）
  • 设置相应的链接。如：把新进程加到就绪队列的链表中
• 进程的终止（撤销）
  • 何时终止：
    • 正常结束：批处理系统中，进程已运行完成遇到Halt指令；分时系统中，用户退出登录
    • 异常结束：本进程发生出错或故障事件：存储区越界、保护性错误（如：写只读文件）、特权指令错误、非法指令（如：程序错转到数据区）、算术运算错误、运行超时、等待超时、I/O失败
    • 外界干预：操作系统干预、父进程请求、父进程终止
  • 进程的终止过程：一旦发生终止进程的事件，OS便调用撤销原语，按照以下步骤终止该进程：
    • 从PCB中读取进程的状态
    • 若进程处于执行态，应立即终止该进程的执行，并置调度标志为真（以便该进程终止后系统重新进行调度，将处理机分配给新选择的进程）
    • 若有子孙进程则将其全部终止，以防它们失控
    • 将该进程所占有的全部资源还给父进程或系统
    • 将该进程的PCB从所在队列中移出
• 进程的状态的转换
  • 进程的阻塞：处于运行状态的进程，在其运行过程中期待某一事件发生（如：请求系统服务、等待键盘输入、等待数据传输完成、等待其他进程发送消息）当被等待的事件未发生时，由进程调用等待原语（block），将自己等待；等待原语使处于运行态的进程停止运行，将运行现场保存在其PCB的CPU现场保护区，然后将PCB中的现行状态由运行态变为等待态，并将该进程插入到相应事件的等待队列中。最后转进程调度程序重新调度，将处理机分配给一个就绪进程，按新进程PCB中的处理机状态设置CPU环境，使它投入运行
  • 进程的唤醒：当被等待进程期待的事件到来时，由中断处理进程或其他产生该事件的进程调用唤醒原语（Wakeup），将期待该事件的进程唤醒；唤醒原语执行时，将被等待进程从相应的队列中移出，并将其PCB中的现行状态由等待改为就绪态，然后将该进程插入就绪队列中；若事件是等待I/O完成，则由硬件提出中断请求，CPU响应中断，暂停当前进程的执行，转去中断处理。检查有无等待该I/O完成的进程，若有则将它唤醒。然后结束中断处理，返回被中断进程或重新调度；若事件是等待某进程发消息，则由发送进程把该等待进程唤醒
  • 进程的挂起：当进程请求将自己挂起或父进程请求将子进程挂起时，调用挂起原语（suspend），将指定进程挂起。
    • 执行过程：检查要挂起进程的状态，若处于活动就绪就将其改为静止就绪态，对于活动等待态的进程则将其改为静止等待态。如果被挂起的进程正在执行则还要转到调度程序重新调度
  • 进程的激活：要激活指定进程，调用激活原语（active）将它激活
    • 执行过程：将要激活的进程调入内存，并检查它的状态，若是静止就绪态则将其改为活动就绪态，若为静止等待态就将其改为活动等待态。如果采用的是抢占调度策略，被激活的进程优先级高则引起重新调度

线程

• 线程概念的引入：作为并发执行的进程具有两个基本的属性：

  1进程即是一个拥有资源的独立单位，它可以独立分配虚拟地址空间、主存和其他系统资源； 2进程又是一个处理器可独立调度和分派的基本单位；

  这两个基本属性使进程成为并发执行的基本单位。在一些OS中（如：unix）进程同时具有这两个属性，而两一些OS中（如：WinNT）这两个属性由OS独立处理，为了区分两个属性，资源拥有单元称为进程任务，调度的单位称为线程

• 线程的定义：线程是进程内的一个执行单元或可调度实体。

  线程只拥有运行中必不可省的资源，但它可与同属一个进程的其他线程共享进程拥有的全部资源。

  在具有多线程的操作系统中，处理机调度的基本单位是线程。一个进程可以有多个线程，而且至少有一个可执行线程。这些线程可以并发工作。线程也叫‘轻权进程’

  当一个应用由几个独立部分组成，而且这几个部分不需要顺序执行时，则每个部分可以以线程方式实现

  线程是由进程派生出来的一组代码（指令组）的执行过程。进程仍然是资源分配的基本单位，而一个进程内的线程成为处理器调度的基本单位。进程的执行只能通过它的各个线程的执行来体现。为了进行管理，每个线程都有一个线程标识码和一个线程控制块(TCB)

• 引进线程概念的目的就是提高资源利用率，有以下好处：

  • 一个进程内的多个线程并发，效率高
  • 由于共享资源，所以同一个进程内的各个线程之间通信方便
  • 线程建立、撤销、调度切换等的系统开销少
  • 便于多处理器体系结构的利用

• 线程的特征

  • 创建线程比创建进程块，且节省开销
  • 一个进程至少要有一个可执行线程
  • 参与竞争处理机的基本调度单位是线程
  • 线程调度程序是内核的主要成分，也是其主要功能之一
  • 一个线程可以创建它所需的线程
  • 一个线程可以有就绪、等待、运行，等状态
  • 方便而有效地实现并行性：进程可创建多个线程来执行同一个程序的不同部分
  • 用线程实现并行性比用进程实现更方便更有效

• 线程的种类与实现

  • 不同的操作系统实现线程的方式不尽相同
  • 核心级（内核级）线程：由系统内核直接提供线程机制，如：一个线程由于I/O而进入等待，系统内核可以调度另一个线程（同进程或不同进程）执行
  • 用户级线程：有的系统在系统内核这一级上只支持进程的概念，由用户程序在自己进程之内运用函数库中提供的线程控制函数来创建、管理、调度多个线程
  • 有的系统则既支持用户级线程，又支持核心级线程

• 进程和线程的关系

  • 线程是进程的一个组成部分，每个进程创建时通常只有一个线程，需要时可创建其他线程
  • 进程的多线程都在进程的地址空间活动
  • 资源是分给进程的，不是分给线程的，线程在执行中需要资源时，可从进程资源中划分
  • 处理机调度的基本单位时线程，线程之间竞争处理机，真正在CPU上运行的是线程
  • 线程在执行时，需要同步

windows系统中的进程和线程

• windows系统支持核心级线程，每个进程在建立时就同时建立起它的第一个线程作为它的执行体，这个线程也可以称为进程的主线程，由它还可以再建立同一进程内的其他线程
• windows的进程管理模块负责创建进程、创建线程、挂起线程、终止线程、终止进程等待，系统相应地提供了若干API函数。
  • CreateThread：创建线程的API函数
  • SuspendThread：挂起指定线程的函数
  • ResumeThread：激活指定线程
  • Sleep 用于把当前正执行的线程本身挂起一段时间，这段时间的长短就用该函数的唯一参数dwMilliseconds指定，它是一个Long类型的数值，单位为毫秒
  • GetThreadPriority：获取指定线程的相对优先级
  • SetThreadPriority：设置指定线程的相对优先级

处理器调度

• 交通控制程序和进程调度程序：在多道程序环境下，系统中有多个进程同时运行。多个的进程竞争处理机，就要求系统提供进程调度功能，将处理机动态地分配给各个进程，使之能够协调一致的运行
  • 交通控制程序：主要任务是管理进程状态之间的转变和协调进程间的通讯，使得各进程能保证协调一致的工作。在大多数的OS中，并没有单独设立交通控制程序，而是将其功能分散到各处，以原语或广义指令的形式出现
  • 进程调度程序：主要任务是安装一定的调度算法从就绪队列中选取一个进程，把处理机分配给它（亦称微观调度），功能：1物理CPU->多逻辑CPU
• 进程调度程序的功能：
  • 记录系统中所有进程的状态、优先数和资源的需求情况
  • 确定调度算法，决定将CPU分配给哪个进程及多长时间
  • 分配处理机给进程，进行CPU现场的保护和移交，并实现CPU使用权的移交
  • 处理机是及玄机最重要的资源，如何提高处理机的利用率及改善系统性能，在很大程度上取决于进程调度（亦称处理机调度）性能的好坏，进程调度成为操作系统设计中心工作
• 调度类型：
  • 高级调度：又称为作业调度、长期调度或宏观调度。它负责决定把外存中哪些个后备作业送入内存、建立相应的进程，使其能得到执行的机会。这种调度发生的时间间隔比较长，其时间尺度通常是分钟、小时或天
  • 中级调度：又称中程调度、交换调度。它需要决定把内存中哪个等待或就绪进程换出到外存，并在适当的时候决定把外存中某个就绪进程换回进内存。这种调度发生的时间间隔比作业调度要短得多
  • 低级调度：又称为进程调度、短期调度或微观调度。它需要经常选择让内存中哪个就绪进程去占有CPU、得到执行。它是系统中最频繁的调度、也是算法最复杂的调度，其时间尺度通常是毫秒级的
  • 并不是任何一个操作系统都具有这三种调度的。中级调度和高级调度就并非一定存在。所有操作系统都有低级调度，不过有的系统中低级调度的对象不是进程而是线程

进程调度算法设计

• 进程调度方式：

  1. 非抢占方式：在非抢占方式下，调度程序一旦把CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将CPU分配给其他进程

  这种调度方式通常在批处理系统中。它的主要优点是简单、系统开销小 2. 抢占方式：当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其他进程。剥夺的原则有：优先权原则、短进程优先原则和时间片原则

  这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求

• 引进进程调度的时机：进程调度的时机是与进程调度的方式有关的。通常当发现以下情况时，当前运行进程的CPU被收回，需要重新进行进程调度

  • 正在执行的进程正确完成，或由于某种错误而终止运行（陷阱或中断）
  • 执行中的进程提出I/O请求，等待I/O完成时
  • 在分时系统中，分给进程的时间片用完时
  • 按照优先级调度时，有更高优先级进程变为就绪时（抢占方式）
  • 在进程通讯中，执行中的进程执行了某种原语操作，如wait操作、等待原语和唤醒原语时，都可能引起进程调度

• 进程调度算法的评价准则：我们可从不同的角度来判断处理机调度算法的性能。实际的处理机调度算法选择是一个综合的判断结果

  1. 面向系统的调度性能准则

     • 吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系-批处理系统。

     注意：平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如在2小时内完成4个作业，每个周转时间是1小时，吞吐量是2个作业/小时

     • 处理机利用率：大中型主机
     • 各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙(指次数多，每次时间短)的作业搭配-大中型主机

  2. 面向用户的调度性能准则

     • 周转时间：作业从提交到完成所经历的时间-批处理系统
     • 响应时间：用户输入一个请求到系统给出首次响应的时间-分时系统
     • 截止时间：开始截止时间和完成截止时间-实时系统，与周转时间有些相似
     • 公平性：不因作业或进程本身的特性而使上述指标过分恶化，如长作业等待很长时间
     • 优先级：可以使关键任务达到更好的指标

  3. 调度算法本身的性能准则

     • 易于实现
     • 执行开销比
     • 要设计一个理想的调度算法是一件十分困难的事，在实际系统中，调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法

进程控制块PCB的组织方式

• PCB表：系统把所有的PCB组织在一起，并把它们放在内存固定区域，就构成了PCB表。PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度
• PCB表组织方式有两种：
  • 索引方式：对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址
  • 链接方式：对具有相同状态的进程，分别各自链接起来组成进程PCB链队列：运行队列、就绪队列、等待队列、空闲队列

进程调度算法

1. 先来先服务FCFS(先进先出调度算法，FIFO)

• 算法思想：最简单的算法
  • 按照进程进入就绪队列的先后次序，分派cpu；
  • 当前进程占用cpu，知道执行完或等待，才让出cpu(非抢占方式)
  • 在进程唤醒后(如I/O完成)，并不立即恢复执行，通常等到当前进程出让cpu
• 特点：
  • 比较有利于长作业，而不利于短作业
  • 有利于cpu繁忙的作业，不利于I/O繁忙的作业

2. 短进程优先调度算法(SJF,SPF)

• 算法思想：选择就绪队列中估计运行时间最短的进程投入运行，通常后来的短作业不抢先正在执行的作业
• 优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量
• 缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业(进程)的执行时间，从而影响调度性能

3. 优先权调度算法(HPF-highest priority first)

• 算法思想：优先选择就绪队列中优先级最高的进程投入运行，分为：
  • 非抢占式优先级算法：仅发生在当前运行的进程放弃CPU时
  • 抢占式优先级算法：可剥夺当前运行的进程CPU
• 优先权的类型：
  • 静态优先级：在进程创建时指定优先级，在进程运行时优先数不变
  • 动态优先级：在进程创建时创立一个优先级，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变
• 确定优先级的依据：进程类型、对资源的需求、根据用户要求

4. 高响应比优先(HRRN - highest response ratio next)：HRRN是FCFS和SJF的折衷算法，响应比R用下式动态计算：R=等待时间+要求服务时间/要求服务时间

• 特点：
  • 等待时间相同要求服务的时间越短优先权越高，有利于短作业
  • 要求服务时间相同，等待时间越长优先权越高，近似于先来先服务
  • 长作业的优先权会随等待时间加长而升高，长作业也会得到执行

5. 时间片轮转调度算法

• 算法思想：通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率
  • 将系统中所有的就绪进程按照FCFS原则，排成一个队列
  • 每次调度时将CPU分派给队首进程，让其执行一个时间片，时间片的长度从几个ms到几百个ms
  • 在一个时间片结束时，发生时钟中断
  • 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程
  • 进程可以未使用完一个时间片，就出让CPU(如等待)
• 时间片长度的确定
  • 时间片长度变化的影响：过长-退化为FCFS算法，进程在一个时间片内都执行完，响应时间长；过短-用户的一次请求需要多个时间片才能处理完，CPU现场切换次数增加，响应时间长
  • 对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)
  • 时间片长度的影响因素
    • 就绪进程的数目：数目越多，时间片越小(当响应时间一定时)
    • 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长

6. 多级反馈队列算法(多队列轮转法)

• 算法思想：
  • 设置多个就绪队列，分别赋予不同的优先级，队列1的优先级最高，其他逐级降低。每队列分配不同的时间片，规定优先级越低则时间片越长
  • 新进程就绪后，先投入队列1的末尾，按FCFS算法调度。若一个时间片未能执行完，则降低投入到队列2的末尾；一次类推，降低到最后的队列，则按时间片轮转算法调度直到完成
  • 进程由于等待事件而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列
  • 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾
• 补充说明
  • I/O型进程：让其进入最高优先级队列，以 及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到等待队列
  • 计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数
  • I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降
  • 为适应一个进程再不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级
• 算法优点
  • 为提高系统吞吐量和缩短平均周转时间而照顾短进程
  • 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程
  • 不必估计进程的执行时机，动态调节
  • 多级反馈队列调度算法，则不必事先知道各种进程所需的执行时间，仍能基本满足短进程优先和I/O频繁的进程优先的需要，因而是目前公认的较好的一种进程调度算法。在UNIX系统、WindowsNT、OS/2中都采用了类似的调度算法

进程调度的操作内容

每当到了前面导论过的进程调度时机，系统就会执行一个软中断指令，进入CPU特权状态工作，转入进程调度程序的工作，它依次做以下几件事：

• 用专门的指令把原执行进程的CPU现场信息(各有关寄存器的内容)按照一定的顺序写入其PCB的特定单元里，并修改PCB中其他某些内容
• 按照调度算法从就绪队列中选出一个进程
• 专门的指令把新进程PCB特定单元里的、即上次退出执行时保存起来的现场信息按照一定顺序写入CPU各寄存器，并修改PCB中其它某些内容
• 进程切换或处理器场景切换

Windows系统的线程调度

• 优先级的等级划分
  • 优先级分为32各等级，0即保留给系统的空闲线程，16-31级为实时优先级，分配给高优先级任务，固定不变；1-15级为可变优先级，分配给普通任务，动态可变。线程的优先级由其所属进程的优先级类型和线程自己的相对优先级组合而成
  • 每个进程在创建时指定一个优先级类型，一共有6种优先级类型；实时、高级、中上级、中级、中下级、空闲、每种类型都是一个优先级范围，其中间值就是各个系统类型的基本优先级，分别为：24、13、10、8、6、4级
  • 线程在创建时继承所属进程的基本优先级，并加上线程自己的相对优先级，形成该线程的基本优先级。线程相对优先级的值可以是0或正负数(通常为正负1、正负2)
• 时间片
  • windows系统规定每个线程一次执行最长不能超过一个时间片
  • windows2000系统对前、后台状态的线程采用不同的时间配额，即前台长一些(比如60毫秒)、后台短一些(比如20毫秒)，这样前台任务就能执行得快一些
• 可抢占
  • 一旦在就绪状态种出现了一个优先级比目前正执行的线程还要高的线程，比如有一个新创建的高优先级线程或是有一个高优先级的线程从等待状态进入就绪，就会触发调度程序工作，强行把正执行的线程退到就绪，把CPU分配给那个优先级更高的线程
• 具有实时优先级的线程
  • 一个线程如果具有16-31级范围内的一个基本优先级，那么在其整个生命周期内优先级不变
• 具有可变优先级的线程
  • 一个线程如果具有1-15级范围内的一个基本优先级，那么在其整个生命周期内优先级会随时根据情况在变化，每时每刻该线程还有一个当前优先级。当前优先级的变动范围在基本优先级和15级之间，以基本优先级为基础，在一些特定情况下系统会提高它的优先级，反之，在另一些情况下，系统又会降低它的优先级，但是最低只能降到它的基本优先级

进程通信和死锁

死锁

1. 基本概念：死锁就是若干进程由于互相等待已被对方占有的资源而处于一种僵持状态

• 死锁发生的原因
  • 存在两个或多个进程，它们都处于等待状态，各自占用着一些资源，按照它们各自的工作进展顺序分别提出新的资源申请
  • 一方面如果它们申请的资源恰恰是已经被这个集合里别的进程占有着、不可抢占的独享资源，另一方面它们得不到新资源就进行不下去、也就不能释放自己已占有的资源，于是形成死锁
• 死锁的描述
  • 用资源分配图来描述死锁的产生
  • 圆圈代表一个进程
  • 方框代表某类资源
  • 方框种的圆点代表该类资源中的一个个具体资源
  • 由进程指向资源框的箭头(只能到方框的边为止)代表该进程正在申请某类资源
  • 由资源圆点指向进程的箭头代表这个资源已经分配给了该进程
  • 如果资源分配图中没有形成环路，就不会死锁。否则有可能发生死锁；当每类资源中只有一个具体资源时，一定死锁；当每类资源中有多于一个具体资源时，可能死锁，因为环路外的进程也可能释放环路内正等待的资源
• 死锁发生的条件
  • 资源互斥：所涉及的资源是独享的
  • 资源不可抢占：只能由占用该资源的进程自己把它释放，其它进程才能占用
  • 资源部分分配(占有并等待)：进程在工作过程中所需的全部资源是随着工作的进展一步步申请并获得的，所以有可能在已占有一些资源且不释放的时候又申请别的资源
  • 循环等待：存在着一个由等待进程组成的集合{p1,p1,...pn}，其中p0正在等待一个由p1占据的资源，p1正在等待一个由p2占据的资源...pn却正在等一个由p0占据的资源
• 死锁的预防：设计os时采用合理的算法，破坏上述四个条件中的任何一条，就可以不发生死锁
  • 资源互斥和资源不可抢夺一般不能改变
  • 为了破坏'占有且等待'条件,有的操作系统采用资源静态分配法，即每个进程必须得到其工作所需的全部资源后才能开始执行，或仅仅当进程不占据资源时，才允许它请求资源
  • 为了破坏循环和等待条件，可以在资源分配上采用有序使用法
• 死锁的避免-死锁可以避免
  • 系统安全状态
    • 系统处于安全状态：假设系统中现在有n个进程，如果存在着至少一种进程安全序列{P1,P2,...Pn}则系统处于安全状态
    • 安全序列：是指其中任何一个进程Pi的最大需求，都能在它之前的各个进程Pj(j < i)释放它们占据的所有资源后得到满足
    • 如果一个系统处于安全状态，就可以避免死锁。反之，存在死锁的可能性。所以每当一个进程申请某一资源时，操作系统按照一定的算法预测一下系统是否会进入不安全状态，若会，则拒绝该申请
  • 银行家算法：如果系统现有的剩余资源能够满足某个进程此后的最大需求，就满足该进程的申请，分配给它
• 死锁的检测与解除

  • 关键是诊断，即判断系统中当前是否已经发生了死锁。所以系统必须每隔一定时间就检查并判定所查出来的等待是正常的还是死锁

  • 发生死锁的解除措施

    • 资源剥夺法：按一定的顺序强行剥夺某些进程的资源并重新分配给已死锁的进程
    • 撤销进程法：按一定顺序强行撤销已死锁的那些进程并收回其占有的资源。

    首先要选择那些如果剥夺或撤销后造成损失最小的进程。并且每次收回资源后应立即再分配并再检测是否还有死锁

进程间的同步与互斥

1. 进程之间的关系

• 无关进程与相关进程
  • 在功能上、逻辑上彼此没有任何联系的进程互称为无关进程(独立进程、不相交进程)
  • 在功能上或逻辑上彼此有某种联系的进程互称为相关进程(合作进程、相交进程)
• 间接制约与直接制约
  • 间接制约：由于共享同一个资源而产生对各进程执行的制约关系 进程-资源-进程
  • 直接制约：由于进程之间必须按一定顺序协调一致地执行特定操作，而形成的关系 进程-进程
  • 从广义上来说，所有进程(无论是无关进程还是相关进程)共享处理器、内存空间、公有数据等公有资源就都形成间接制约

2. 同步与互斥

• 广义同步：指如何保证进程之间的协调一致，不发生与时间有关的错误。分为互斥和同步

  • 和时间相关的错误：进程进展速度、处理器切换时机等时间因素导致程序运行结果不确定。为了避免这种错误需要运用同步机制

• 狭义的同步：指的是几个进程合作完成一个任务时，进程间存在的时序关系，必须按一定顺序协调一致地执行特定操作

• 互斥：几个进程需使用同一个共享资源，而这些资源同一时刻只能被一个进程使用

• 临界资源：是指那些每次只允许一个进程使用的资源(如：共享变量)。这种资源只能被一个进程独享而且其他进程不可抢占，又称为互斥资源

• 临界区：是指在进程的程序中涉及到临界资源的程序段，又称为互斥区；多个进程中涉及到同一个临界资源的临界区称为相关临界区

• 临界区的使用原则：无空等待、有空让进、多中选一、有限等待、让权等待。与狭义的同步机制相比，此时各进程使用该资源的先后顺序是无关紧要的

3. 生产者和消费者问题

• 生产者是一个进程，不断地把自己的产品(如数据)送入缓冲区，消费者是另一个进程，不断地从缓冲区中取走产品，这个共享缓冲区最多可容纳N个产品。系统中可以有若干个生产者进程和若干个消费者进程并发
• 上面的流程安排由于没有考虑进程间的协调，无法避免与时间有关的错误
• 是一个同步问题，且是双向同步问题
• 也是一个互斥问题，共享缓冲区是个临界资源，因此，各生产者进程和各消费者进程必须互斥地执行对缓冲区的访问
• 解决一个问题首先要看它是互斥问题还是同步问题或两者兼有，然后采取相应的措施

4. 进程互斥的一种实现方法

• 即平等协商方式，其基本思路是：一个进程在进入临界区之前检查和设置一些标志，退出临界区以后再修改标志成为原始状态。申请进入临界区的进程在进入之前等待，直至其他进程退出临界区
• 运用系统提供的加锁与开锁原语，就可以这样来实现互斥：
  • 进程甲->lock(x)->临界区->unlock(x)->
  • 进程乙->lock(x)->临界区->unlock(x)->
• 加锁原语LOCK(X)的操作内容：
  • 测试x的值是否为0
  • 如果为0则将x的值赋为1，加锁成功
  • 如果不为0则返回对x的测试
• 开锁原语UNLOCK(X)的操作内容：
  • 将x的值赋为0
• 每个进程在申请一个临界资源时执行加锁操作，如果加锁成功就可以使用该资源，否则只有等待、继续测试。而每个正在占有该资源的进程在使用完了资源后应当立即执行解锁操作。二者配合完成互斥通信
• 算法缺点：由各个进程自己反复去进行申请测试，进程之间没有直接通信。所以虽然简单，但是工作效率不高，很可能出现'饥饿'现象

进程间的低级通信：进程间传递的信息仅为一个信号(通常是一个整型变量甚至就是一个bit)，使用少量的低级通信原语对这个信号进行处理，当然，这个信号代表的含义是事先由通信双方约定好的

• 信号量：是一个数据机构，它包括一个整型变量(S)和一个与之联系的进程队列
• 数据结构：

struc semaphore {
    int value;
    pointer_PCB queue;
}

• 整型变量S的值表示某类资源的数目，S>0表示尚有S个资源可以分配，S<0表示该资源已经被占用完，目前不能申请

• 信号量的值只能通过P、V操作这两个原语来改变

• P操作：S值减1；如果S>=0则该进程继续进行；否则该进程进入等待状态 并被加入到S的等待队列

• V操作：S值加1如果S<=0则将等待队列中的第一个进程释放，把它的状态转为就绪；无论S值如何，执行这个V操作的进程都继续执行

• 运用信号量实现同步与互斥：在程序中给信号量赋予一定的初值后(初值应大于等于0)，利用P、V操作既可以实现进程间的互斥通信，也可以实现同步通信，功能比较完备

• 利用P、V操作实现进程间的互斥

  • 进程甲 -> p(x) -> 临界区 -> v(x)->
  • 进程乙 -> p(x) -> 临界区 -> v(x)->
  • 同一个信号量的P、V操作必须成对出现
  • 而且当实现互斥操作时，同一个信号量的一对P、V操作出现在一个进程程序之内，P操作出现在进入临界区之前，V操作出现在退出临界区之后

• 利用P、V操作实现进程之间的同步

  • 进程甲：p(s2) -> 把数据写入文件 -> v(s1) ->
  • 进程乙：p(s1) -> 从文件中读取数据 -> v(s2) ->
  • 同一个信号量的P、V操作必须成对出现
  • 同一信号量的一对P、V操作分别出现在两个进程程序内，P操作出现在被动的、其进度需要等待对方信号通知的那个进程里，V操作则出现在主动的、让对方等待自己通知的那个进程里

• windows系统中的同步与互斥：为此，windows系统提供了若干种机制，包括一定的对象及其相应的API函数

  • 信号量对象：在物理意义与使用方法等方面基本上对应于前面介绍的'信号量'
    • API对象CreateSemaphore用于建立一个信号量对象
    • OpenSemaphore用于根据信号量的名称返回一个已经建立的信号量对象的句柄
    • ReleaseSemaphore用于释放一个信号量所对应的资源，类似于对信号量进行V操作
    • WaitForSingleObject用于申请一个信号量所对应的资源，类似于对信号量进行P操作
  • 互斥对象：是信号量对象的一个特例，互斥对象在建立后有两种状态：信号态与非信号态
    • 信号态是指该互斥对象的值为1，即目前没有任何线程进入相关临界区
    • 非信号态则指该互斥对象的指为0，这表明已经有一个线程对它进行了P操作并进入了相关临界区，又称那个线程'占有'了该互斥对象
  • 信号量对象和互斥对象之间的区别
    • 信号量对象既能用于控制互斥也能用于控制同步，而互斥对象只能用于控制互斥
    • 信号量对象的最大值可以为某个指定的正整数，而互斥对象的最大值只能为1
    • 信号量对象的初始值可以为某个指定的正整数或0，而互斥对象的初始值只能为1
  • 互斥对象举例：
    • CreateMutex用于创建一个互斥对象
    • WaitForSingleObject用于申请对一个互斥对象的'占有'，成功则继续，失败则等待。既可用于操作信号量对象，也可用于操作互斥对象
    • ReleaseMutex用于放弃对一个互斥对象的占有，它只有一个参数hSemaphore(Long类型)，指定该互斥对象的句柄

进程间的高级通信：进程间传递的信息量较大(比如通过内存的一个缓冲区甚至通过外存上的一个文件)、含义较丰富，当然，相应地高级通信原语也就较复杂

• 进程间的高级通信也称为进程通信(IPC--InterProcess Communication)。它提供在进程间传递较大量信息的机制。PIC建立在主存系统基础上
• 相互通信的进程间设有公共内存，一组进程向公共内存中写，另一组进程从公共内存中读，从而实现进程通信
• 常见的高级通信：

1. 消息缓冲通信

• 消息，就是在进程之间传递的一组信息
• 操作系统在自己的内存工作区里建立并管理着若干个消息缓冲区
• 消息缓冲区的结构：消息长度m-size、消息正文m-text、发送者m-sender、消息队列指针m-next
• 是一种直接通信方式：
  • 进程甲如果要向进程乙发生消息，就向系统申请一个消息缓冲区，把消息(包括正文和长度)写入该缓冲区，然后由进程乙读取

2. 信箱通信

• 是一种间接通信方式
• 信箱：是一种公共的数据结构，发送进程把要传递的信息组成'信件'放入信箱，接收进程则从中读取'信件'
• 一个信箱中可以存放若干个信件
• 信箱由信箱说明与信箱体组成
  • 信箱体可以看成由若干个格子组成，每个格子内可以存放一封信件，每个格子都有一个'已用或空闲'的标志
  • 信箱说明又称为信箱头，包括：信箱名称boxname、信箱大小(格子数目)boxsize、已存放信件数m-number、空闲的格子数m-free

3. 管道通信

• 管道就是一个打开的、供两个进程共享的文件，所以它是建立在文件系统基础上的、
• 两个进程可以利用它以比特流的、先进先出的方式传递消息，而且是单向的。一个进程只能从管道的这端写入信息，另一进程则只能从管道的另一端读取信息

存储管理(主要是内存)

存储管理的基本概念

1. 存储系统的层次组织

• 内外存都有统一的编址，内存以字节位基本的存取单位；外存以块位读写单位
• 内存的速度高，价格高，容量少；外存速度慢，便宜，容量大
• cpu读取的对象是内存，内外存之间通过IO操作交换数据
• cache容量最小，速度最快，存放着cpu刚访问过的且还要被访问的指令和数据
• 存储管理就是对内存的管理，确切地讲就是对用户空间的管理
  • 操作系统运行占用的空间称作系统空间
  • 用户程序占用的空间称作用户空间

2. 程序及其运行与存储器地址的关系

• 地址空间：程序从设计到运行的过程中，存在着三种地址空间
  • 符号地址空间：变量的名称、语句的标号等。每个源程序单位的符号地址是独立安排的，与其他程序单位无关
  • 相对地址(也称为逻辑地址)空间
  • 绝对地址(也称为物理地址)空间
• 逻辑空间：源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据--单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址
• 内存空间(或物理空间)：内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可唯一标识一个存储单元，称为内存地址(或物理地址)
• 地址重定位：从相对地址找到绝对地址的过程叫做'地址重定位'
  • 静态地址重定位：是在程序执行之前由操作系统的重定位装入程序完成的
  • 动态地址重定位：是程序执行期间进行的

3. 存储管理的基本任务

• 内存分配：按分配时机的不通过，可分为两种方式
  • 静态存储分配：指内存分配是在作业运行之前各目标块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的
  • 动态存储分配：作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成
• 存储保护
  • 上下界存储保护：是一种简单的存储保护技术。系统可为每个作业设置一对上下界寄存器，分别用来存放当前运行作业在内存空间的上下边界地址，用它们来限制用户程序的活动范围
  • 基址-限长存储保护：上下界保护的一个变种
• 存储共享
  • 多个进程在运行过程中有可能都要访问同一个存储单元，特别是多个作业可能都要调用某些系统程序或系统数据，需要进行存储共享管理
  • 存储共享管理的内容包括：决定哪些内存是可共享的，哪些是不可以共享的；各个进程对共享的权限
• 存储扩充
  • 对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术
  • 虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延申，用户并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必须一部分信息存入内存，其他则存于外存，当访问的信息不在内存时，系统自动将其从外存调入内存

分区存储管理 把内存空间分配给一个进程时，是分配给它一片地址连续的空间，还是分配给它一些分散的空间，从这个角度可以分成连续和非连续两大类，内存分区管理属于前者

1. 分区存储管理技术

• 内存分区的基本思想是由系统把实际内存的物理空间划分为若干个分区，每个分区都是一片在地址上连续的'小'空间
• 某个进程建立时就获得一个内存分区，进程完成后则归还该分区
• 分区的实际位置可以用一对寄存器的内容来标识：分区的上界地址和下界地址；或者分区的基地址和分区的长度

2. 固定分区存储管理：固定分区的存储管理是实现多道程序设计的最简单的一种存储管理技术。其基本思想是，在作业未进入内存之前，就由操作员或操作系统把内存可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个用户共享，因为在系统运行期间，分区大小、数目都不变，所以固定式分区也称为静态分区
3. 可变式分区存储管理

• 空间分区的组织形式
  • 空闲分区链表的组织是：在每个空闲分区的起始部分分开劈出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志
• 内存的分配和回收
  • 当某一个用户作业完成释放所占分区时，系统进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置
• 常用的分配算法
  • 首次适应算法
  • 最佳适应算法
  • 最差适应算法
• 可变式分区的地址重定位

可变式分区的地址重定位可采用静态重定位，也可采用动态重定位。如采用静态重定位，因用户作业进入内存后，程序的逻辑地址实现了重定位，不能在内存中再进行移动，经过一段时间的运行，内存中不能再分配利用的小碎片越来越多。有时可能会出现这种情况，即当一个作业申请一定数量的内存时，虽然此时空闲区的总和大于新作业的内存要求，但却没有单个的空闲区足以装下该作业

采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作 4. 覆盖技术

无论是固定分区管理还是可变分区管理，都解决不了'内存扩充'的问题。如果某个作业对内存空间的需求量超过内存分区的大小、甚至超过整个实际内存的用户空间，怎么办？对此，可以在程序设计时采用'覆盖技术'来适当解决

简单页式存储管理

• 内存分区管理的缺点：
  • 碎片、存储共享困难、无法满足作业对大空间的需求
• 页式存储管理技术分配给进出的内存空间不是连续的
• 页式分区管理
  • 简单页式
  • 请求页式
• 页面的概念
  • 把进程所使用的逻辑地址空间划分为固定大小的一个个'页面'，按顺序从0开始编有'页面号'
  • 把实际内存的物理地址空间也划分为固定大小的一个个'页帧'，也按顺序从0开始编有'页帧号'
  • 系统为进程的每个逻辑页面分配一个内存物理页帧
  • 一个进程的逻辑地址空间是连续的，而各逻辑页面所对应的物理页帧在物理空间中不一定是连续的
  • 不同的操作系统采用的页面大小也不同，不过一般都采用2的整数次幂个字节
• 纯分页存储管理中存储块的分配和回收
  • 通常由两种记录空闲存储块的方法：位图法和链表法
• 页表与地址映射
  • 页面号和位移量：由于逻辑页面与物理页帧的大小一样，某一存储单元在逻辑页面内处于什么相对位置(称为页面内的位移量或页内地址)，到了对应的物理页面内仍然处于什么相对位置，逻辑位移量就是物理位移量
  • 页表：为此，系统为每个进程建立一个反映这种页面对应关系的数据结构，称为'页表'。一个进程的逻辑空间包含多少个逻辑页面，它的页表就由多少个'表项(即条目)'组成，每一表项里记载着该逻辑页面对应的物理页帧号
• 联想存储器

从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问两次内存。一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半

应用联想存储器和页表相结合的方式，可以有效地提高系统动态地址转换的速度，是一种行之有效的方法

• 快表与关联寄存器

从地址转换的过程还可以看出，进程每访问一个存储单元，实际上都要访问两次内存(第一次访问页表，第二次才是访问真正的目的单元)

为了解决这个问题，许多系统使用一个专门的高速缓冲存储器，存放当前执行进程最近使用的页表表项，形成一个'快表'。由于它实际上就是若干个成对的寄存器，所以也称为'关联寄存器/联想存储器'

• 分页式存储的四种保护方式
  1. 禁止做任何操作
  2. 只能执行
  3. 只能读
  4. 能读能写

当要访问某页时，先判断该页的存取控制和存储保护信息是否允许

• 交换技术：用于解决多个作业对存储空间的需求与相对狭小的内存物理空间之间的矛盾
  • 换出又称为'挂起'，换入又称为'激活'。'交换调度'又称为'中级调度'
  • 进程被换出到磁盘上时，换出换入的是进程所占有的全部内存空间，甚至包括保存在进程控制块(PCB)中的许多信息，仅留下一些最重要的信息(PCB的主体)还在内存，以便将来再换入
  • 有的操作系统并不采用交换技术，因而没有交换调度

请求页式虚拟存储器管理

1. 虚拟存储的一般概念

• 把每个进程的逻辑地址空间加大，可以大大超过实际内存空间(确切地说是超过分配给进程的内存空间)，成为一个一维的、连续的'虚拟地址空间'。虚拟空间里的地址称为'虚拟地址'
• 虚空间内存放的指令、数据对应地在实空间中，有的在内存里可以直接访问，但更多地是放在磁盘上，等到要被访问时再调入内存，暂时用不到的则调出内存仍放到磁盘上
• 虚拟存储技术是用大容量的外存作为内存的后盾，通过信息在内外存之间的传递来解决实际内存空间不足的问题，当然，传递信息是要耗费时间的，所以是用时间换空间

2. 请求页式存储管理技术

• 访问有效和访问无效

在请求页式管理中，进程的逻辑空间被视为容量可以很大的'虚拟'空间，其中的虚页面彼此是连续的。而进程得到的内存实际页帧不但彼此可能非连续而且其总和数量有限。一个进程在某一时刻占有的所有内存页帧构成该进程当时的工作区(在有的系统中又称为工作集)

工作区中的页帧数目总是远小于虚空间中的虚页面数。这就意味着虚页面对应的物理位置只有一部分在实际内存中，其余则在外存磁盘上

当经常访问某个虚地址、需要进行如前所述的地址映射时，虚页面所对应的实页面如果已经在内存中(即在进程的工作集中)，称为'访问有效'或'页面有效'，转去执行'地址转换'；虚页面所对应的实页面如果还在磁盘中，则称为'访问无效'、'页面无效'或者'缺页'，转去执行'调页'

• 页表表项：由于在进行地址映射时需要区分两种情况、分别做不同的处理，所以在页表中必须对这一点做出反应，页表表项的内容就要比简单页式管理中的复杂得多。通常，页表表项包括这样一些字段：
  • 页面状态(是在内存还是在外存)位(如果页面在内存)对应的实页帧号(如果页面在外存)对应的外存地址信息
  • 访问标志位(该页面被访问的情况)
  • 修改标志位(该页面是否被修改过)
  • 访问权限位，等

3. 调页与页面淘汰

• 调页：是当虚页面对应的实页面目前还不在内存中时由软件实现的操作。步骤如下：
  • 当进程执行某条执行、要访问某个虚地址单元时，安装地址转换的流程查找到页表相应表项，如果表项中'页面状态位'表明属于'访问无效',就会发出一个'缺页'中断信号，暂停用户进程的执行，转而执行一个系统的调页程序
  • 该程序把用户进程所需的那个页面从磁盘上的指定位置复制到内存的一个实际页帧里，并使之成为该进程工作集的一个成员，同时修改相应页表表项中的'页面状态位'、填入实页帧号。然后恢复中断现场，继续执行刚才被中断的用户进程，再次执行刚才未能完成的那条指令，这次的'地址转换'肯定是'访问有效'，能够访问成功了
• 页面淘汰
  • 一般在一个进程刚建立时，系统可能只分配给它少量内存页帧组成其工作集。随着进程程序的执行，这个进程的工作集便一页页扩大
  • 当内存空间已经占满时，再要调页，系统手中已经没有空闲的内存页帧了。只能从已存在的一个工作集中取出一个实际页帧，清除其原有内容，装入'调页'的新内容。这个过程就称为'页面淘汰'
  • 页面淘汰可以在整个内存范围内进行，但是最好是在进程各自的空间内进行。即进程的工作集不能无限地扩大，系统对每个进程工作集大小的上限有个规定，当进程的工作集扩充到达其上限后，再进行调页、'请求'一个实帧时，必须先从自己的工作集中交出一个页帧，才能换回一个相应的实页帧用于新调入的内容
• 修改页面的处理

当从工作集中淘汰一个页面时，还应当注意这个页面自进入工作集以来其内容是否被修改过。如果没有修改过，该页面可以直接淘汰，即用新调入页面的内容覆盖这个页面。如果被淘汰的页面的内容修改过，那应先把其内容写回外存，再做调页覆盖。为了区分这两种情况，在页表表项中应当有个'修改标志位'作为标识

• 磁盘有关文件

调页，是把用户进程所需的那个页面从磁盘上的指定位置复制到内存的一个实际页帧里，这里所说的'磁盘上的指定位置'是什么呢？从理论上说，请求页式系统中需要在磁盘上建立一个专门的'调页文件(pagefile)'，可以近似地把这个调页文件就看作为'虚拟空间'

4. 页面置换算法

• 最优算法(OPT算法)

最理想的页面置换算法是：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。这种算法本身不是一种实际的方法，因为页面访问的顺序是很难预知的。但是，可以把它作为一种评价标准，比较其他实用方法的优劣，所以最优算法只具有理论上的意义

• 先进先出算法(FIFO算法)

这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉

• 最久未使用页面算法(LRU算法)

这种算法的基本思想是：如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。实现这种算法可通过周期性地对'引用位'进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面

• LRU近似算法

这种算法，只要在存储分块表(或页表)中设一个'引用位'，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个周期T内，某些被访问过的页面其引用位位1，而未被访问过的页面其引用位为0。因此，可根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页

5. 局部性原理与抖动现象

• 请求页式虚拟存储管理技术的优点是
  • 提高内存使用效率
  • 减少'碎片'
  • 便于实现存储分配、存储保护、存储共享和存储扩充
• 能应用该技术的主要原因是程序的执行往往有相当强的局部性。一般情况下，进程是不会以相等的概率去随机地访问地址空间所有部分的
• 实践也表明，在一个局部的时间段内，一些指令、数据，以及和这些指令、数据在存储空间相邻的那些内容，往往会被多次执行、访问
• 请求页式虚拟存储管理技术的缺点：容易产生'抖动'现象
• 所谓抖动(又称为颠簸)：一个页面被调入工作区后不久就被淘汰，然后很快又被调入，...，如此频繁地进行页面的输入输出，对系统效率有严重的影响
• 产生抖动的主要原因有二
  • 分配给进程的工作集太小
  • 进程的程序本身质量不高
• 缺页率：考察进程的工作集大小是否合适的指标，又称'页面失效率'。就是测试一个进程在执行时单位时间内'缺页'的次数。现代许多虚拟存储操作系统对各个进程的工作集采用某种动态调整的策略

段式与段页式存储管理

• 一个用户作业往往是由若干个程序、子程序、数据结构组成的，也就是说有其自己的逻辑模块结构，每个模块有相对的独立性，模块内部则联系密切

• 页式管理却没有考虑这一点，一律以'页面'作为内外之间传递信息的单位，是一种按照'系统'观点设计的方法

• 段式存储管理技术则可以认为是一种按照'用户'观点设计的方法

• 地址空间

  • 段式管理技术就是把一个进程的逻辑空间按照其程序数据模块结构划分为若干个'逻辑段'，各有一个段号(从0开始编号)
  • 各段的逻辑空间长度是不同的，但每段内的逻辑地址都从0开始顺序编址，称为段内地址。这样，整个进程所涉及到的每一个逻辑地址都由'段号'(本身是一维的)和'段内地址'(本身也是一维的)两部分组成，也就是一种二维的地址
  • 实际内存空间被动态地划分为若干个大小不一的物理存储区(或称为'物理段')，类似于分区管理那样。每个区内的地址是连续的，也可以从0开始编排一种'段内相对地址位移'

• 内存空间的分配

  • 当一个进程进入内存后，其每个逻辑段被分配给一个长度适当的物理存储区。一个进程的各个逻辑段从逻辑关系上是连续的，但为它们分配的物理段却不一定连续
  • 段式管理也可采用虚拟存储技术。与页式管理类似，有的逻辑段对应的物理存储区在内存中，把逻辑段号转换为对应的内存分区的起始地址，再加上段内地址就得到实际内存地址；有的逻辑段对应的物理存储区则在外存中，于是产生一个缺段中断，运用软件手段把其调入内存(得到一个内存分区)后再访问
  • 系统建立并维护着一个内存分区表，记载着各物理存储区的位置、状态(空闲或已分配)，并可以把空闲区建立一个队列(或空闲区表)，用来掌握内存空间的分配与回收

• 地址映射

  • 在段式管理的地址映射中起关键作用的就不是'页表'而是'段表'。每个进程有自己的段表

• 动态连接

  • 段式管理的另一个优点就是可以实现逻辑段的动态连接。采用动态连接装配，就是把对某个子程序的连接装配工作推迟到运行中要访问它的时候再做。由于在段式管理中每个程序模块为一个逻辑段，所以动态逻辑就有了可能

• 段页式存储管理

  • 段式管理与页式管理各有所长，所以很自然地想到把二者结合起来，这就是段页式存储管理
  • 在段页式存储管理中，进程逻辑空间仍然是二维空间，按照模块结构划分为逻辑段，每段有段号(这些是段式管理的思想)。每段逻辑空间再划分为页面，与物理空间的实页帧对应(这些是页式管理的思想)
  • 作业的虚地址由段号、(段内的)虚页面号和(页面内的)位移量组成，由虚地址到实地址的映射既要使用段表，又要使用页表。每个进程有一个段表，每个段有一个页表

设备管理

基本概念

• 设备管理就是对计算机外部设备的管理

1. 设备的分类

• 按使用性质分类：输入输出(I/O)设备和存储设备
• 按信息组织方式分类
  • 有块设备和字符(或字节)设备
  • 目前的外存设备，通常称为'块设备'。而I/O设备中有不少常被称为'字符设备'
• 按管理特点分类
  • 独享设备，一般的I/O设备都属于这一类
  • 共享设备，主要指磁盘驱动器
  • 虚拟设备，指通过SPOOLING技术等手段加以改造的独享设备，改造后共享
• 按所属关系分类
  • 系统设备，指标准外设，一般OS中已经包含了它们的驱动程序，并在系统生成时配置好，用户可以直接使用
  • 用户设备，即非标准的、在系统生成以后根据不同用户的需要逐步加入到系统中来的设备，需要安装设备驱动程序

2. 设备管理的任务

• 实现设备的独立性
  • 向用户提供统一、方便的设备应用接口，使用户能够很简便地使用各种外设，而不必去多管它们具体的物理特性和I/O操作细节
• 提高并行程度
  • 通过使各个外设之间、外设与CPU之间并行工作提高外设的使用率和整个系统的效率
• 设备管理的主要功能
  • 实现具体的设备驱动和I/O操作
  • 为多道作业合理地分配和回收设备
  • 管理缓冲区
  • 实现外部设备中断请求的处理
  • 实现虚拟设备技术

3. 设备的连接与控制

• 为了连接和控制各种外设，首先需要有设备控制器，外部设备与主机相连接是通过相应的控制器和主机的总线实现的。外设的种类不同，其控制电路自然也不同。而且，在各种外部设备控制电路和计算机总线之间需要加入一个接口电路，外设情况各不相同，接口也就有多种类型
• 控制适配器综合了接口电路、控制电路。它的功能主要是：
  • 接收CPU发来的命令信息，为此它的内部需要有相应的控制寄存器，以及对CPU命令进行译码与执行的部件
  • 向CPU报告外设当前状态信息，以便CPU实施控制，为此它的内部需要有相应的状态寄存器
  • 在外设与主机之间完成数据传输与缓冲，以及必要的检测、校验，为此它的内部需要有相应的数据缓冲寄存器
• CPU怎样查找这些寄存器并与之交换信息呢？
  • 这就需要地址。如同管理和使用内存地址空间那样，系统也分配给各个设备控制器一定的地址空间范围，于是就想访问内存单元那样来访问设备控制器上的寄存器

4. 设备的控制方式

• 循环测试方式(程序直接控制方式)：
  • 由用户进程的程序采用循环测试，通过主机CPU主动地、周期性地访问外设控制器，发出或读取信息
  • 最简单，只需一般的I/O控制器。但传递的数据量少，CPU的利用率低。且CPU和外设不能并行工作
• 中断方式
  • CPU不再去一遍遍地询问外设(或通道)的状态，而是由外设控制器(或通道)在需要的时候请求CPU来访问自己
  • 要求设备控制器应带有中断机制
  • 优点：CPU利用率较高；支持多道程序、支持外设并行工作；能及时响应和处理外设(或其他硬件)的故障
  • 缺点：但是一个进程要完成一批数据的传递需要多次中断
• DMA(直接存储器存取)方式
  • 外设和主机内存之间直接传递数据
  • 优点：外设与内存间能有较高的数据传输速率，且大大减少了CPU的中断次数，仅在启动和数据传送结束时需要CPU进行处理
  • 缺点：CPU在一段时间内不得不停止涉及总线的工作。
  • 在硬件支持方面，需要专门的DMA控制器(与一般的I/O控制器相比，还要包括字节数寄存器、内存起始地址寄存器等)
• 通道方式
  • 通道是比DMA控制器功能更强的一种硬件，CPU的工作负担更轻(只需发一个启动通道的指令)。而且进一步提高了外设的并行程度
  • 通道的工作原理：通道有自己的控制运算部件和指令，可分别执行读、写、转移等操作。用这些指令事先编好控制各对应控制器和设备的所谓通道程序，存放在内存中(一般情况下通道也使用主机内存，而不是自己单设内存)。每当用户程序要进行I/O操作时，主机CPU就执行启动该通道的指令，使通道开始执行上述通道程序。这以后通道与CPU并行工作
  • 通道的控制结构：一个通道可能连接着若干个控制器，一个控制器也可能连接着若干台设备。为了提高整个系统的可靠性，可以在通道和控制器之间采用交叉连接
  • 通道的分类：按照通道与所连接的设备之间信息交换方式的不同，通道可分为：
    • 字节多路通道
    • 选择通道
    • 成组多路通道

在四种方式中，除了'循环测试方式'以外的三种方式都采用中断技术：中断方式的中断次数最频繁，DMA方式的中断次数较少，通道方式的中断次数最少。DMA方式和通道方式都采用在外设和内存之间直接传递数据(前者由DMA控制器来控制，后者由通道来控制) 5. 缓冲区的管理

• 为了提高整个系统的效率，还需要解决另一个矛盾：主机CPU与外部设备的工作速度相差太大
• DMA方式和通道方式必须结合使用缓冲技术才能真正发挥其作用
• 缓冲技术可以用硬件实现，也可以用软件实现，即由操作系统在内存中设置并管理专门的缓冲区，用来存放输入输出操作中需要传递的数据，这是操作系统对设备进行管理的重要内容之一
• 操作系统通常在内存中开辟多个缓冲区
  • 单缓冲区的设置和管理都比较简单，但是主机CPU和通道对这个缓冲区的使用是互斥的，效率不高
  • 如果使用双缓冲区，主机CPU和通道可以交替地使用它们，工作效率得以提高。类似地，还可以设置多缓冲区
  • 不少操作系统在内存中建立缓冲池，就是把多个通道(或控制器)的缓冲区集中在一起，组成队列，统一管理和分配，以便进一步提高效率。缓冲池属于操作系统掌握的系统空间

I/O软件原理

• 计算机系统中外设的使用与控制，即需要硬件，也需要软件

• 软件方面统称为设备处理程序，也称为'I/O软件'，它们形成一种层次关系

  • 用户空间的I/O软件->与设备无关的I/O软件->设备驱动程序->中断处理程序->硬件(设备控制器)

• 设备处理程序：涉及设备管理的中断处理程序，包括对各种设备工作中可能发出的中断信号进行响应操作的子程序

• 设备驱动程序

  • 设备驱动程序：是用来对各种设备、I/O控制器、DMA控制器进行启动、打开、读、写、关闭等操作的许多子程序
  • 设备驱动程序的具体内容取决于具体的设备和前面所讲的控制技术、缓冲技术等等
  • 设备驱动程序与外设硬件密切相关，只有它才完全了解对应设备的具体参数和工作机制，以及对应的设备控制器上都有什么寄存器
  • 设备驱动程序的代码完全依赖于它所管理的设备硬件(设备和控制器)，一般都直接用汇编语言编写

• 与设备无关的I/O软件

  • 主要功能是向上一级用户级软件提供统一的接口，同时向下面临着多个设备驱动程序，它需要把用户进程的需求转变为对某个设备驱动程序的要求
  • 这一层的一个重要任务就是设备的分配。对可共享的设备和对独占设备显然要采取不同的分配策略，而且还要解决从逻辑设备名到物理设备名再到设备驱动程序的对应
  • 此外，缓冲区的管理、缓冲技术的应用，也主要在这一层次内完成

• 用户空间的I/O软件

  • 主要是在用户程序中运用'系统调用'来提出使用设备的请求。比如在windows系统中就提供了若干个涉及外设操作的API函数

• 物理设备与逻辑设备

  • 系统给每台设备指定一个物理的、实际的设备名或绝对号
  • 但用户进程在程序中使用逻辑的设备名或相对号进行申请和操作
  • 每当一个用户进程提出对一个逻辑设备(或相对号设备)的使用操作时，操作系统的'设备分配程序'就根据情况分配一个实际设备(或绝对设备号)与该逻辑设备(或相对号)建立起对应关系，所有让后者进行的操作都由前者去完成。这也体现了'设备独立性'

• I/O进程的工作过程

  • I/O进程在不同的操作系统中有不同的安排：
    • 整个操作系统共同使用一个I/O进程
    • 使用两个I/O进程(一个输入、一个输出)
    • 对每一类外设有一个专门的I/O进程
  • I/O进程被调用的时机与原因：
    • 一是某个用户进程发出I/O请求后本身进入阻塞，操作系统则调度相应的I/O进程执行
    • 二是某个外设发出中断请求，操作系统予以响应、调度相应的I/O进程执行

• I/O进程执行过程

  • 如果是某个用户进程发出I/O请求，则
    • 首先由与设备无关I/O软件分析用户的请求(申请的逻辑设备名、操作类型、数据长度、内存起始地址等)
    • 然后由设备分配模块分配适当的物理设备、控制器、通道，把逻辑设备名转换为物理设备名，如果无资源可分配则把这个I/O请求置为等待
    • 再由缓冲区管理模块分配适当的缓冲区
    • 最后执行相应的设备驱动程序，或是启动通道
  • 如果是外设发出中断请求，则：
    • 首先调用相应的中断处理程序，分析中断请求的原因。
    • 然后转给设备驱动程序，释放已分配给该I/O请求的设备、控制器、通道；唤醒等待该I/O完成的进程，使其由等待状态进入就绪状态；另外如果有等待相应资源(设备、控制器、通道)的I/O完成的进程，使其由等待状态进入就绪状态；另外如果有等待相应资源(设备、控制器、通道)的I/O请求，也要通知相应的进程

设备的分配与回收

• 设备分配的一般问题：设备分配就是为每个申请的逻辑设备分配一个相应的物理设备。与'分配'相对应的操作就是'回收'
• 设备管理所需要的数据结构：设备分配程序为了完成分配与回收任务，需要建立和维护若干数据结构，它们称为'控制表(CT)'，也称为'控制块(CB)'，其中主要有：
  • 设备控制表
  • 控制器控制表
  • 通道控制表
  • 整个系统还要建立一个系统设备表
• 设备分配时机与策略
  • 静态分配
    • 在一个作业投入运行之前把它需要的设备分配给它(若设备非空闲，不能分配，就推迟作业的运行)，直到该作业结束或明确说明不再使用时才回收，面向作业
    • 简单，不会'死锁'，但设备利用率低，难以满足多个进程并行工作的要求，不符合设备管理的基本任务要求
  • 动态分配
    • 仅当进程在工作中确实要使用某一设备时才分配给它该设备，而且操作完成后便立即回收设备，以便再分配给其他进程。面向进程
    • 动态分配的分配策略主要有：'先请求先服务(FCFS)'算法和'最高优先级'算法
  • 独享设备多采用静态分配，共享设备则多采用动态分配
• 虚拟设备与SPOOLing技术
  • SPOOLing是'外部设备同时联机操作'的英文缩写
  • 原理：运用磁盘这种工作速度较高的大容量共享设备来模拟那些工作速度较低的独享设备(如打印机)，使后者在用户角度上看来也改造成为一种'共享'设备。通常把这种'被改造的设备'称为'虚拟设备'

磁盘调度问题

• 磁盘驱动器的结构特点：OS一般都给所有扇区统一编一个物理块号。'块'在整个磁盘存储空间中的具体位置由磁头号、柱面号和扇区号来决定
• 磁盘I/O时间：当需要对某个物理块进行实际读写时，需要按照这种三维参数来具体定位。对一个物理块访问的总时间就由三部分动作的耗时组成。访问时间=寻道时间+旋转时间+磁头读写时间，在一次访问的总时间内，占比例最大而且取值变化幅度最大的就是寻道时间
• 磁盘是共享设备，会有多个进程同时(或说是在一个很短的时间段内)提出读写请求，形成一个等待分配的队列
• 为了提高总体的访问速度，需要研究磁盘调度问题，具体说有移臂调度和旋转调度两个方面，分别优化寻道过程和旋转定位过程
• 寻道(查找)优化策略：为了提高效率，需采用特殊的优化策略(算法)，其中经常采用的两种算法如下：
  • 最短寻道时间优先服务(SSTF)：每次访问结束后选择所要访问的柱面最接近当时磁头位置的那个请求作为下一个访问。按照这种算法使得每次磁头移动的距离尽可能小，减少了大跨度移动
  • 扫码服务(SCAN)：这种算法在具体细节上又可以分为几种。其中最常用的称为电梯算法
• 旋转优化策略
  • 与寻道不同的是，旋转动作总是按照一个方向，没有反方向动作。所以优化算法就比较简单，就是寻找最短距离。当有几个进程提出访问同一柱面不同扇区的请求时，不是按请求的先后而是按照扇区号的顺序(即沿旋转方向会遇到的顺序)给以响应。这样就可以在一圈旋转之内完成各个访问
  • 为了减少旋转等待时间，有的操作系统采取对数据存放位置实施优化分布措施，比如把数据不按扇区连续存放，而是间隔一、两个扇区存放；有的系统采取'按道缓存'的措施，即一次读写一个磁道的数据

文件管理

文件系统的基本概念

1. 文件与文件系统
   • 文件(file)
     • 是外存上用'文件名'标识的一组相关信息的有序集合
     • 文件时操作系统对信息资源进行管理时的基本单位
   • 文件系统：是OS中负责文件管理的程序模块与数据结构的总称。其功能是完成用户需要的各种文件存取和维护，包括：
     • 统一管理文件的存储空间(即外存)，实施外存空间的分配与回收
     • 建立文件的逻辑结构和物理结构，提供对文件的存取方法
     • 实现文件的按名存取，即能够把文件名映射为该文件的物理存储位置
     • 实现文件的各种控制操作(创建、打开、关闭、改名、撤销)和存取操作(读、写、修改、复制、转存等)
     • 实现文件信息的共享，并提供可靠的文件保护措施和保密措施 每个OS都包括至少一种文件系统，例如windos2000就支持FAT16、FAT32、NTFS三种文件系统，由用户决定在某个逻辑磁盘上建立哪种文件系统
   • 每种文件系统都有自己规定的文件逻辑结构、文件物理结构、目录结构一级相应的文件查找、映射手段、
   • 按名存取：
     • 在文件的概念和文件系统的功能里，最核心的一点就是'按名存取'。文件名是区分、标识文件的唯一标志，数据具有物理上的独立性，文件具有一定程度的共享
2. 外存设备的存储特点

• 磁盘的存储特点
  • 扇区(又称为磁盘'块')是磁盘进行空间分配、读写和信息传送的基本单位。所有扇区都有一个'物理块号'
  • 大容量磁盘，往往不是以'块'而是以'簇'作为基本的存取单位。所谓'簇'就是连续的几个块，也编有簇号。磁盘是一种'直接存取'的存储设备
• 磁带的存储特点
  • 数据也以块的形式安排，并且以块为读写单位
  • 磁带的启动和停止都需要一段时间，所以磁带上数据块之间需要有一段间隙。因此，数据块应当取得大一些
  • 磁带存储器是一种'顺序存取'的存储设备，即，做读写操作时，只能按照顺序依次读(或写)各个块的数据，而无法直接定位到所需要的块进行读写

3. 文件的逻辑结构

• 文件的分类
  • 按照内容的性质与用途分：
    • 系统文件
    • 库文件
    • 用户文件
  • 按照信息流向分
    • 输入文件
    • 输出文件
    • 输入输出文件
  • 按照存在期限分
    • 永久文件
    • 临时文件
  • 按照文件的保护方式分
    • 只读文件
    • 可读可写文件
    • 可执行文件
    • 无保护文件
• 文件的组织结构
  • 文件的组织结构应当分为两个方面：逻辑结构和物理结构。文件系统的主要功能之一就是根据逻辑结构找到物理结构
• 文件的逻辑结构：指的就是从用户角度所看到的文件内信息的组织结构。基本的逻辑结构有两种：
  • 流式文件：(字符)流式文件是字符的有序集合，实际上是一种'无结构'的方式
  • 记录式的文件：记录式是'有结构'的方式，是指文件内部的信息被划分为若干部分，每部分称为一个记录。记录是对这种文件进行增添、删除、管理等操作的基本单位。记录式文件又可分为定长记录和变长记录两类
  • 每种文件系统对其管理的文件的逻辑结构有明确的规定，目前多数操作系统，都不支持记录式文件，而只支持流式文件

4. 文件的物理结构

• 是文件在外存器上的实际存储结构，即如何组织这些数据块，文件内各块的逻辑块号与它们的物理块的块号之间怎样对应的问题
• 基本的文件物理结构主要有三种
  • 连续结构(顺序结构)，可在磁盘、磁带上实现
    • 连续结构又称为顺序结构，是指一个文件占用盘、带上连续的若干个物理块、
    • 使用这种结构的文件称为'连续文件'
    • 这种结构简单、容易实现，但是文件一旦需要修改、长度发生变化，将代理一系列问题。所以这种结构主要用于那些一旦建立后其内容就基本不再变化的文件(称为静态文件)
  • 链接结构(串联结构)，只能在磁盘上实现
    • 链接结构又称为串联结构，是指文件所占用的'物理块'在磁盘上可以是非连续的，为了能从前一个块找到后一个块，在每个块内需要拿出少量字节来记载后面一个块的物理块号，叫做'连接字'，也就是一个'指针'。用这些指针把整个文件串联起来
    • 采用这种结构的文件称为'串联文件'
    • 只要知道了文件起始物理块号，就可以沿着这些'指针'访问到整个文件。采用指针结构，文件的长度扩充或减少都比较方便，但存取速度要稍受影响，空间利用率稍低一些
  • 索引结构，只能在磁盘上实现
    • 索引结构也是由若干个可以不连续的物理块组成整个文件，但它不采用'连接指针'，而是对每个文件再建立一个'索引'，其中按照该文件各个逻辑块号的顺序记载着每个逻辑块号对应着的物理块号
    • 当要访问某个逻辑号的数据块时，需要首先访问该文件的'索引'，从中查到该块的物理号，然后才能再去实际访问这个块
    • 这种结构的文件虽然复杂一些，但是增删改都非常方便(只需要修改其索引即可)。特别是，对于文件中任何一个数据块都可以做到直接访问，不必在文件中一个块一个块地顺序查找
• 每种操作系统对其管理的文件的物理结构都有明确规定，它们可以是三种基本结构之一，也可能是在这三种基本结构基础上的变化发展。比如在windows系统中，FAT16、FAT32等文件采用根据文件分配表中按簇号链接的结构，而NTFS等文件系统则采用索引/多重索引的结构

5. 文件的存取方式

常用的文件存取方式有两种

• 顺序存取
  • 根据用户指定的开始位置和要读写的字符数或记录数，顺着文件的物理结构依次往下读或写。各种物理结构的文件(磁盘和磁带上的)都可以进行顺序存取
• 直接存取
  • 根据用户指定的逻辑块号，直接对指定数据块进行读写
  • 对于物理上是顺序结构的磁盘文件，可以很容易地换算出该逻辑块号对应的物理块号
  • 对于物理上是索引结构的磁盘文件，可以很容易地查找出该逻辑块号对应的物理块号
  • 物理上的链接结构的磁盘文件则做不到这一点
  • 直接存取只能在磁盘上实现

文件系统的实现

文件系统的基本任务，就是根据用户的要求按照文件名建立文件、管理文件、访问文件

1. 文件目录

• 为了实现以'按名存取'的原则对所有文件进行管理，并对其存取操作施加控制，操作系统需要建立若干数据结构。其中主要是文件控制块(FCB)和目录文件。每个文件都有一个文件控制块，把所有文件的文件控制块放在一起，就形成一个'目录'
• 文件控制块(FCB)
  • 文件控制块是系统用来掌握文件情况的基本工具，它是一个数据结构，记载着该文件最重要的属性信息
  • 文件控制块是与文件一一对应的，它与对应的文件同时被建立、同时被删除，而且每个文件在被使用的过程中不但要依靠相应的文件控制块，还会随时更新相应文件控制块的内容
• 文件控制块的内容
  • 文件名
  • 文件类型
  • 文件长度
  • 文件建立的日期时间
  • 文件最近一次访问的日期时间
  • 文件的主人
  • 文件的存取权限
  • 文件在磁盘上共占用多少个块
  • 文件的物理位置，比如对于连续结构或链接结构的文件要指出从哪一个物理块开始，如果是采用索引结构，则需要指出其索引的位置，等等
• 目录文件
  • 有了文件控制块，文件系统对文件的管理就可以归结为对一个文件控制块的管理。所以，文件系统把所有文件的文件控制块放在一起，这样就形成一个'目录'
• 树形目录结构
  • '二级目录'的结构，每个用户目录是主目录的子目录，相对于子目录而言，主目录成了父目录。每个目录又可以发展自己的子目录，形成树形结构的多级目录，每个目录下也可以存放文件
• 目录路径
  • 在树形目录结构中，从根目录开始向下到每一个文件都有一条唯一的'路径'，叫做目录路径，它是在文件系统中确定一个文件位置的唯一方法。用户在进行文件操作时，必须指明作为操作对象的那个文件的路径和文件名
• 目录文件的内容安排
  • 目录文件太大也会使在其中查找文件的速度下降
  • 有的操作系统采取把目录文件的内容分开安排的措施
    • 对每个文件分配一个唯一的'文件号'，目录文件中仅包含文件名与其对应文件号的对照表
    • 文件的FCB则按照文件号的顺序放在另一个文件中

2. 盘图文件

• 文件系统在磁盘上建立和使用一种'盘图文件'，来动态地记录该磁盘各个物理块的使用情况、动态地进行分配与回收。常用的有：
  • 位示图文件：也称为字位映像文件，是一个连续结构的文件，由连续的二进制数字串组成，每一位对应着一个物理块的情况、
  • 自由盘块列表：又称空闲块列表，这是一个链接结构或索引结构的文件，由磁盘上所有目前未被使用的块(称为自由块或空闲块)组成

3. windows的FAT文件系统

FAT文件系统包括FAT12、FAT16、FAT32等版本，它们都以文件分配表(File Allocatin Table)作为基础性的数据结构，因此被称为FAT系统

• 磁盘分区
  • windows管理下的硬盘必须在格式化之后进行分区
  • 所谓硬盘分区，就是把一个物理硬盘划分为一至四个分区，其中可以有一个扩展分区(Extended Partition)，其余为主要分区(Primary Partition)
  • 主要分区可以用于安装不同的操作系统，并指定其中一个是活动分区(active)，也就是开机启动时所使用哪个操作系统所在的分区
  • 扩展分区可以再分成几个逻辑盘，以便于管理和维护
• 整个硬盘的第一个扇区是主引导程序，之后是64个字节的分区表。分区表内每一个表项占16个字节，描述一个分区的属性

字节号	内容
0	是否可以引导DOS或windows系统(80H为可以)
1-3	分区的开始地址(柱面号、扇区号、磁头号)
4	是否为DOS或windows分区(01H为是)
5-7	分区的终止地址(柱面号，扇区号、磁头号)
8-11	分二期的相对扇区数目
12-15	分区的实用扇区数目

软盘则由于容量小，不分区，也可以看作就是一个逻辑盘

• FAT文件系统的磁盘布局
  • '高级格式化'就是在一个逻辑盘上建立起一个文件系统的基本框架，包括该系统所需的基本数据结构
  • 对于FAT文件系统，格式化后每个逻辑盘上这些数据结构的安排布局为，从第一个扇区开始依次有：引导记录、文件分配表(FAT)、根目录、数据区
• 引导记录扇区里包括引导程序和磁盘I/O表：

字节号	内容
0-2	一条转移指令
3-10	OEM名称与版本
11-12	每个扇区的字节数目
13	每个簇包含的扇区数目
14-15	保留扇区
16	文件分配表的个数
17-18	根目录的目录项数目
19-20	总扇区数
21	磁盘介质描述
22-23	每个文件分配表占用的扇区数目
24-25	每磁道的扇区数目
26-27	磁头数目
28-29	隐含的扇区数目
30-	引导程序

• windows所管理的文件都放在磁盘的数据区内，所以数据区又称为文件区
• windows在为文件分配存储空间时，不采用扇区(sector)、而采用'簇'(cluster)作为分配单位
• '簇'是一组连续的扇区。一个簇所包含的扇区数依磁盘容量不同而不同，比如：软盘一般是一个扇区，硬盘则可能是16个、或32个、或64个等等
• 格式化时会依次给簇编排簇号
  • 0号和1号这两个簇号保留不用，实际应用的簇号由2开始
  • 数据区才是实际应用的簇，簇号2是数据区的起点
  • 由于数据区以前的引导记录、文件分配表和根目录所占用的扇区数目随磁盘的不同而不同，所以簇号2所对应的扇区号也就不同
• 根据文件在磁盘上占据的簇的簇号就可以找到该文件，这就是文件系统对簇的'寻址'
• 早期的DOS系统采用12位二进制数字作为簇号。即一个逻辑盘最多只能有4096个簇，这种文件系统就称为FAT12，在3.5英寸(1.4MB)软盘上是这种格式
• 后来的DOS系统采用16位二进制数字作为簇号，这种文件系统就叫做FAT16，一个逻辑盘最多有65536个簇
• 而windows所支持的FAT32系统采用32位二进制数字作为簇号
• 三寸高密度软盘的容量是固定的(1.44MB)所以参数是统一的
• 软盘空间分布举例：

簇号	扇区号	内容
--	0	引导记录
--	1-9	第一个文件分配表
--	10-18	第二个文件分配表
--	19-32	根目录
2	33	数据区
3	34	.
4	35	.

• 硬盘空间分布举例：

簇号	扇区号	内容
--	0	引导记录
--	1-252	第一个文件分配表
--	253-504	第二个文件分配表
--	504-536	根目录(ROOT)
2	537-600	数据区(DATA)
3	601-664	.
4	665-728	.

• FAT文件系统中的文件物理结构
  • 各文件都放在磁盘的数据区内，即从2号簇开始存放
  • FAT采用一种改进的链接式物理结构。使用了'文件目录表(FDT)'和'文件分配表(FAT)'这两种数据结构
    • 文件目录表，简称目录或文件，由若干个目录登记项组成，每个目录登记项对应于一个文件，相当于文件控制块，其中记载着该文件的起始簇号
    • 文件分配表记载了是否还有其他的簇、簇号是多少，文件分配表还起着'盘图文件'的作用，动态地记载着磁盘块的使用情况
  • FAT采用树形结构的多级目录来组织管理磁盘文件
  • 每个逻辑磁盘有且仅有一个根目录，有多层子目录
  • 根目录放在磁盘的ROOT区。子目录本身也是一个文件，存放在磁盘的数据区(DATA)内，也有文件名
  • 根目录和每个子目录都由若干个目录登记项组成，每个目录登记项对于一个文件(或子目录文件)
  • 目录登记项长度为32个字节，其中记载着该文件的文件名、扩展名、属性、建立的日期时间、文件长度，特别是记载着起始簇号
  • 根据用户指定的文件路径和文件名，系统可以查找最终在其目录登记项中找到该文件的起始簇号
  • FAT16文件目录登记项的内容
    • 每个扇区(512个字节)容纳16个登记项
    • 根目录下容纳的目录登记项数目是有限的
    • 子目录下的目录登记项数目可以不受限制

字节号	内容
0-7	文件名
8-10	扩展名
11	文件属性
12-21	系统保留，暂时未用
22-23	文件生成或最后修改的时间
24-25	文件生成或最后修改的日期
26-27	文件起始的簇号
28-31	文件的长度(字节数)

• FAT文件系统中的文件分配表
  • 每个逻辑磁盘在格式化时都要建立一个FAT，由于它的重要性，所以通常保留有备份，也就是说每个磁盘上至少有两个同样的FAT
  • 在硬盘的FAT中，每两个字节对应于磁盘的一个簇(与16位二进制的簇号格式相适应)，说明该簇的状况和簇间的连接情况
  • 软盘的FAT也一样，只是每个簇的状态用1.5个字节标识(与12位二进制的簇号格式相适应)
  • FAT32系统在FAT模式基础上进行了增强。簇号采用32位二进制，能对更多的簇进行寻址，能以较小的簇尺寸支持管理更大容量的硬盘。且根目录也以目录文件的形式存在，可以放在任何地方，它包含的目录登记项数目也没有限制

4. windows的NTFS文件系统

• NTFS的磁盘结构
  • NTFS也建在磁盘分区的基础上，，与FAT类似。但NTFS的基本管理单位不是'逻辑盘'而是'卷'
  • 卷是以'簇'为单位面向文件进行分配与回收的，每个簇包括若干个连续的磁盘扇区(磁盘块)，簇的尺寸(即所含扇区的数目)根据卷的大小来定，通常为1、2、、4、8等
  • 所有簇统一顺序编号，称为逻辑簇号(LCN)。根据簇的LCN和簇尺寸，就能换算出该簇的第一个扇区在磁盘上的物理位置(磁头号、柱面号、扇区号)
  • 每个文件按长度，也可以根据同样的簇尺寸划分为若干个'虚拟簇'，顺序编出虚拟簇号(VCN)。要访问文件中某个字节，只需从文件开头加上字节数，就能换算出它的虚拟簇
  • 文件较大、需要占用若干个簇时，可以把连续的几个簇组织成为一个'片'(又称范围extent)，按'片'分给文件。不过'片'不是固定单位，其大小完全在分配空间时根据情况临时确定
• NTFS的文件目录
  • NTFS也采用树型的目录结构，每个卷有一个根目录。包括根目录在内的各级目录本身都是一个文件
  • 与FAT系统不同的是，每个目录文件中并不包含所有下属文件或子目录文件的详细属性(如同一个个文件控制块)，而仅仅是这些文件的文件名与文件引用号的一个对照表，而且是按照一种能快速查找文件名的索引方式组织起来的
• NTFS的主文件表
  • 每个卷有一个主文件表(Master File Table，MFT)，里面存放着该卷中全部文件的属性信息。每个文件有一条记录，长度固定为1KB
  • 各个文件的记录按照引用号顺序排列，所以根据文件引用号就能在MFT中迅速定位到对应的文件记录
  • 每个文件的MFT记录(长度1KB)包含：
    • 文件名
    • 基本属性(如文件主人、建立时间、最后访问时间等)
    • 其他属性
    • 文件本体的内容或是这些内容在磁盘上的位置
  • NTFS对大小不一的文件采用了灵活的管理方法
• NTFS的位图文件
  • NTFS系统没有文件分配表
  • 为了掌握卷中各个簇的使用情况，及时了解哪些簇当前是空闲的，NTFS系统采用了'位示图'的手段
  • 每个卷有一个位图文件，其中每一个二进制位(bit)代表卷中一个簇的使用情况

文件的共享与安全

1. 文件的共享有两类：

• 通过建立文件目录之间的链接关系实现文件的共享
• 通过明确指定相应的路径来访问共享文件

2. 文件的保密

• 文件的保密是指防止未经授权的用户访问文件，或是进行超出权限的访问
• 具体的保密措施从用户和文件两个角度施加：
  • 在用户一方，包括：设置和验证用户名与密码，用户分组(不同的组有不同的权限)，设置与验证特权等
  • 在文件一方，包括：设置文件访问口令，文件加密，设置文件访问权限等
• 关于文件访问权限，常用的方式有：
  • 文件保护码(存取控制码)
  • 存取控制表

3. 文件的保护

• 文件的保护是指防止文件因用户操作错误或系统故障而受到破坏
• 保护措施有：
  • 建立文件副本(文件复制)：
    • 对单个文件通过复制操作建立文件的副本
    • 文件系统都提供复制操作。这种方法简单，但占用的外存空间太多，且各个副本之间很难保持一致
  • 磁盘定期备份(文件转储)：
    • 将磁盘上的所有文件定期转储，全部复制到磁带上。一旦系统出现故障，再由磁带恢复到磁盘上来
    • 通常采用'全备份'与'增量备份'相结合的办法

4. NTFS的安全性措施

• 文件安全描述符
  • 包括目录在内的每个文件都有一组安全描述符，详细记载了各个用户或用户组对该文件的访问权限
  • 每个卷有一个安全文件，存放着卷中所有文件的安全描述符数据库。它与操作对用户、用户组的管理措施(如账户、登录等)相结合，可以有效地对文件访问实施控制
• 操作日志：系统在每个卷上建立一个日志文件，所有对该卷的文件操作在真正实施之前，都会先记入这个日志文件
• 可恢复性技术
  • 系统把有关文件的操作都作为一种'原子事务'(Atomic Transaction)来对待
  • 一个'事务'中的所有操作要么全部完成要么就一项也不做，每个'事务'从一开始就受到系统的追踪，一旦中途失败，系统将采取回退措施，完全恢复到'事务'开始之前的状况
• 文件加密技术
  • 系统包含了一个加密工具，能够对文件加密
  • 这个工具基于较先进的加密算法，每个合法用户都有自己的私钥
  • 凡是已经被用户加密的文件，在用户自己读取时自动解密，而当文件内容数据发生变化时又会再自动加密

文件操作的实现过程

1. 文件系统的功能模块

• 命令解释
• 目录检索
• 权限检查
• 地址确定
• 结构映射
• 传输与设备I/O
• 盘块管理

2. 文件操作的基本内容与过程

• 文件操作的基本内容
  • 对文件目录的操作
  • 对文件整体的操作
  • 对文件内容的使用操作
• 建立文件与删除文件
  • 所谓建立目录或文件，主要就是再其父目录中建立一个FCB
  • 所谓删除目录或文件，主要就是在其父目录中清除它的FCB
• 打开文件与关闭文件
  • 打开文件，就是在目录中找到指定文件的FCB，把这个FCB复制到内存中一个称为'活动文件表'的区域里来，这个过程又叫使它成为'活动的'FCB
  • 文件一经打开，能被多次读写。每次读写前都要检查权限，然后将用户指定的位置映射为物理位置，再实际读写数据，并相应地修改文件内部位置指针
  • 关闭文件是打开文件的反动作，对指定文件的FCB做必要的修改后存回到磁盘上相应的目录文件中，并撤消内存中相应的FCB信息
  • 上述各种文件操作是一个一级一级地、反复地递归操作过程
• 文件操作的基本手段
  • 文件系统提供了上述各种功能，同时也向用户提供了进行文件操作的各种手段
    • 命令接口
    • 编程接口。不过其中绝大多数操作都已经包装成为各种程序设计语言的库函数或过程，可以之间在编程中使用

3. windows文件系统的层级结构

• windows支持多种文件系统。之所以能这样，是因为其文件管理采用了层次型的结构
• 任何操作系统的文件管理都是建立在设备管理基础之上的，因为各种文件操作最终都要通过设备操作去实现
• windows系统中的文件管理与设备管理更加融为一体，因为系统把所有I/O操作都当作是对一个虚拟文件的操作，于是就形成了一种层次结构