操作系统原理

第一章绪论

本章主要介绍了操作系统的发展历史、基本概念和类型

操作系统在计算机系统中的地位

存储程序式计算机的结构和特点：集中顺序过程控制

操作系统与各层之间的关系：操作系统连接了裸机底层硬件和软件应用程序。

操作系统与底层硬件：操作系统控制CPU的工作、访问存储器、设备驱动、中断处理；硬件为操作系统提供运行环境。

操作系统与上层软件的关系：操作系统管理和控制上层软件的运行；上层软件要求操作系统能够提供方便的用户界面和优质的服务。

操作系统与计算机体系结构的关系：存储程序式计算机底层硬件提供顺序计算模型，而操作系统需要为上层提供并行计算模型。为了解决这一矛盾，操作系统层面采用了多道程序设计技术、分时技术、资源分配与调度等软件技术，硬件方面采用了不同的硬件架构如多处理机系统（一台电脑多个CPU）、消息传递型多计算机（多台独立计算机通过定制网络传递消息）、计算机网络等。

操作系统的形成与发展

初级阶段
- 手工操作：用户以手工的方式通过安装或拆卸纸带完成数据的输入输出，通过设置物理地址启动程序运行。随着计算机处理速度的增长，人工干预与计算机速度之间的矛盾越来越大。
- 早期批处理：设计监督程序，操作员集中将一批程序输入计算机，由监督程序对作业进行调度。监督程序实现了计算机的成批处理，但是监督程序由CPU执行，故I/O工作由CPU直接控制，这样的系统称为早期联机批处理系统。监督程序实现了作业的自动过渡，解决了人工干预与计算机速度之间的矛盾，但是由于CPU控制着一切，而CPU的速度比I/O快得多，于是又产生了I/O与CPU执行速度之间的矛盾
- 脱机批处理：为了解决CPU与I/O速度之间的矛盾，将I/O工作拆出交给卫星机处理，卫星机将纸袋输入磁带，磁带直接交给主机，主机只负责运算。主机和卫星机能够并行工作，大大提高了计算机工作效率。这种卫星机和主机分离且卫星机独立工作的系统称为脱机批处理系统。但是卫星机和主机之间磁带转移依然需要人工干预，并且系统缺少保护（说白了就是没有异常处理机制）。
- 执行系统：随着通道技术（控制控制一台或多台外设，负责外设与主存之间信息传输的设备，类似DMA）和中断技术的出现，I/O设备可以在主机的控制之下完成，且I/O和计算可以具有一定并行性，其中负责调度作业自动运行和I/O控制功能的软件称为执行系统。执行系统不仅实现了作业自动调度和并行I/O，由于联机的处理方式，又增强了保护能力。但是此时的执行系统的并行是由限度的，取决于程序的运行特征。
形成阶段
- 多道程序处理技术：在批处理系统中只有当一个程序既有I/O又有计算时可以做到一定程度的并行，其核心原因是主机在一段时间内只是运行一个程序，故联机批处理、脱机批处理、执行系统统称为单道批处理系统。为了提高效率，可以在计算机主存中同时存放几道相互独立的程序，在操作系统的控制之下相互穿插运行，交叉占用不同设备，在宏观上并行，微观上串行，称为多道程序处理技术。类似频分复用技术，但程序不是像频分复用中一直占据一个频段一样一直占用一个设备，而是哪个设备空闲占用哪个。引入多道程序处理技术之后可以实现多道成批处理系统，在这样的系统中，用户以脱机的方式（指用户无法干预程序运行）将程序以作业为单位送入机器，能够充分利用资源，完成大吞吐量的计算。
- 分时技术：人们还希望能够直接控制程序的运行，让一台主机服务于多个用户，于是采用了分时技术：处理机时间划分成很短的时间片（如几百毫秒）轮流分配给各个应用程序使用，若应用程序在分配的时间片用完之前还未完成计算，则暂时中断，等待下一轮继续计算。类似时分复用技术，但是分时技术是配合多道程序处理技术一起使用的。在分时技术的基础上出现的分时系统使用户可以进行联机交户，且响应时间快。
- 实时处理：对响应速度有要求的系统，称为实时系统。（属实没讲啥东西）
发展阶段
- 个人操作系统
- 具有并行结构的计算机系统配置的操作系统
- 移动式计算机操作系统
- 嵌入式设备中的操作系统

操作系统的基本概念

操作系统的定义：操作系统是一个大型的程序系统，它负责计算机系统软、硬件资源的分配；控制和协调并发活动；提供用户接口，使用户获得良好的工作环境。

操作系统的特征：

并发性：要求具有处理多个同时性活动的能力，通过并行处理技术实现，指进程概念以及进程的控制、通信、调度技术
共享：要求能够实现多个计算任务对系统资源的共同享用，通过虚拟技术实现，指将实体机器、存储空间虚拟为虚拟机个虚拟空间。
不确定性：要求能够处理随机事件，并能够保证任务的正确运行。

操作系统的资源管理：

处理器管理：包括进程调度策略、进程调度算法和处理器的分派
存储器管理：包括存储分配和存储无关性（管理其他应用程序的地址并提供映射机制，使其他应用程序无需关心存储细节），存储保护（隔离应用程序避免存串了），存储扩充
设备管理：包括设备无关性（操作系统提供设备访问方式，使用户无需关心具体设备，方便用户访问设备），设备分配，设备传输控制
信息管理：文件系统管理

操作系统的基本类型

批量操作系统：把用户提交的程序组织成作业的形式，成批送入计算机，然后由作业调度程序自动选择作业，在系统内多道运行。系统吞吐率高，但作业周转时间长，用户使用不方便
分时操作系统：采用时间片轮转的办法，使一台计算机同时为多个终端用户服务，系统对每个用户都能保证足够快的响应时间，并提供交互会话功能。具有并行性、交互性和独占性
实时操作系统：对外部输入的信息，能够在规定的时间内处理完毕并作出反应。实时响应，安全可靠。
嵌入式操作系统：作为一个部件嵌入到更大的、专用的系统中的计算机系统，特点是小而专用。
个人操作系统：不再是最大化CPU和外设的利用率，而是最大化用户方便性和响应速度。
网络操作系统：除了具备一般操作系统应具有的功能模块外，还要增加一个网络通信模块。网络操作系统允许用户访问网络主机中的各种资源，并进行访问控制。
分布式系统：由于计算机网络不能支持筒木的资源存取，合作计算，也不乏对网络资源进行有效的统一管理，故设计一个功能更强大的操作系统来屏蔽网络结构的复杂性，使用户以统一的界面、标准的接口使用系统的各种资源，实现所需要的操作。系统的各部分依然像网络一样自治，但是由分布式操作系统对资源进行全局和动态的管理控制。具有可扩展性，增强性能，高可靠性，高性价比等等特性

操作系统实例

UNIX特点：

UNIX结构上分为核心层和实用层。核心层小巧，可常驻内存，实用层丰富，以核外程序的形式出现并在用户环境下运行
使用灵活的命令语言shell
使用维护简单、实现高效的树型文件系统
文件、设备统一处理
使用C语言编写，移植性良好

Linux特点：

类UNIX系统，按照GNU通用公共许可证，开源，遵循POSIX操作系统调用服务接口标准，与UNIX兼容
Linux内核由负责进程管理与调度程序、主存管理程序、网络和进程间的通信程序、中断处理程序和设备驱动程序组成，模块间的通信通过直接调用其他模块中的函数实现，属于单体结构。但同时也提供了可动态装载和卸载的模块，如设备驱动程序，使Linux系统更为灵活
系统提供的操作接口是shell，也可以使用X-windows图像用户界面。
Linux系统还包含一组实用工具如vi、Emacs等。
支持多处理器
使用强大的面向对象虚拟文件系统技术实现对多种文件的支持。

第二章操作系统的结构和硬件支持

本章主要介绍了操作系统内核的结构，特权级和中断。

操作系统虚拟机

虚拟的概念可以有效实现资源共享，使一定的物理资源具有更强的能力。

只有硬件的裸机，其只支持其机器指令，而加上操作系统之后，机器变可以支持更多指令，这个支持更多指令的机器我们称之为操作系统虚拟机。

操作系统虚拟机提供的全部操作命令的集合称为操作命令语言，是用户和系统进行通信的界面，分为两类：

操作命令（命令接口）：用户直接对机器发出的命令，包括键盘命令，批处理系统中的作业控制语言，以及图形化用户界面
系统功能调用（程序接口）：在用户程序中直接使用的用来钱气操作系统提供服务的接口。

操作系统的组织结构

操作系统由内核（核心层）和其他操作系统功能组成，核心层包括操作系统最重要的几个模块（处理器管理，存储管理，设备管理和文件管理以及中断的俘获和处理），所以人们讨论操作系统时往往涉及的是操作系统的内核，包括前面说的操作系统虚拟机也是裸机加上操作系统内核。操作系统的组织结构也是针对内核的，分为单内核和微内核两种，单内核分为单体结构、模块结构和层次结构，微内核则是可扩展结构。

结构分类只是在主体上进行讨论，一个操作系统在实现时并不会十分清晰地采用某一种方式。

单体结构：在单体结构中操作系统是一组过程的集合，基本没有结构，效率高但是难以理解和维护。Unix和Linux都基本采用一体化结构
模块结构：在单体结构的基础上对逻辑独立的模块进行封装，采用模块化的结构来实现操作系统。优点是便于理解，缺点是存在性能的退化。目前没有纯模块化的商业化操作系统，但是需要注意的是单体结构也是有模块的，只是没有显式封装。
层次结构：将操作系统分为若干层，各层之间只能是单向以来或单项调用关系。优点是整体问题局部化，可以一层层验证正确性，缺点是操作系统作为一个非常复杂的软件很难准确分层，且由于分层单项以来，必须要建立模块间的通信机制，降低系统效率。一般用于涉及操作系统时作为一种指导原则。
可扩展内核结构：再次将核心分为基础核心和其他功能两部分，基础和小提供最基本的进程、线程管理功能、第级存储器管理、中断和陷入处理，其他功能为服务进程，操作系统以CS模式为用户程序服务，即用户通过微内核与其他功能模块通信，再由微内核返回处理消息，从而达到策略（做什么）与机制（怎么做）的分离。优点是扩展性、可靠性强，且支持分布式系统，企鹅电视系统开销大

操作系统为用户提供服务有两种方式：

作为子例程被调用：操作系统的服务历程作为用户进程的一个函数被调用
作为进程被调用：操作系统是一个单独的进程，用户进程请求操作系统服务时相当于客户机向服务器发送消息，这种处理方式更加灵活，适用于分布式系统，便于实现多种不同的服务类型，具有较好的容错性，但是开销大

处理机的特权级

由于计算机系统中运行着大量的程序，程序之间互不干扰由操作系统保证，但是操作系统也不能被干扰。为了保证操作系统的管理程序不被破环，需要设定一些特权指令，这些指令只能提供给操作系统的核心程序使用。而当前处理机能执行那些指令由处理机的状态决定，处理及的状态又称为处理机的特权级。

特权指令包括：改变处理机状态的指令，改变特殊寄存器的指令，涉及外部设备输入输出的指令等。

根据能否使用特权指令，将处理及的特权级分为管态（系统态）和用户态（目态）。管态是操作系统的管理程序执行时处理机所处的状态，可以使用全部指令和全部系统资源；用户态是用户程序执行时处理及所处的状态，不能使用特权指令，不能直接取用资源和改变机器状态且只能访问自己的存储区域。

有的系统将管态进一步分为管态和核态，核态具有所有权限，管态运行使用一些在用户态下不能使用的资源，但是不允许修改状态

中断及其处理

所谓中断是指某个事件 (例如电源掉电、定点加法溢出或I/O传输结束等) 发生时，系统中止现行程序的运行、引出处理事件程序对该事件进行处理，处理完毕后返回断点继续执行的过程。

按中断功能，中断可以分为以下五类：

输入/输出中断：I/O传输结束或出错中断（注意是结束）
外中断：机器中断、操作员控制台中断、通信中断
机器故障中断：电源故障、总线错误等
程序性中断：定点溢出、除0等程序非法操作
访管中断：应用程序对操作系统提出某种需求时发出的中断

按中断方式分类

强迫性中断：除了访管中断以外的所有中断，即不是程序所期待的中断
自愿中断：访管中断

按中断来源分类：

中断：由处理机外部事件引起的中断
俘获：由处理机内部事件引起的中断

有两种不同的中断机制：向量中断和探询中断，前者每一个中断都有一个独特的标识，决定中断处理程序入口地址，后者则先将中断分为几大类，一个中断产生时先决定该中断是哪一类，然后再由程序判断应该使用哪个具体中断处理程序。

CPU发现中断时需要通知当前程序执行并转到中断处理程序，这一过程称为中断响应，也称为中断进入。中断响应由硬件完成。

中断响应有几个重要步骤和概念

保护和恢复现场：由于中断执行完后还要回到中断发生前的程序继续执行，所以要保护现场，现场包括：后继指令虽在主存的单元号，程序运行所处的状态，指令的执行情况和中间结果。
程序状态字寄存器：存储反映程序执行时机器所处的现行状态的代码，包括：指令地址、指令执行情况、处理机状态、应屏蔽的中断等，有的处理机使用一个寄存器，有的使用多个，不如Intel Pentium使用一个EFLAGS和一个EIP
中断响应过程：首先将程序状态字保存起来，比如压倒栈里，然后将中断程序的状态字送进程序状态寄存器，执行完后恢复原程序状态字。

Linux的特权级与中断处理

以运行在i386上的Linux为例，使用两个特权级：特权级0（管态）和特权级3（用户态）。

为提高中断处理的效率，中断处理程序的执行必须快速、简洁。为此，Linux 系统将中断处理程序分为上半部和下半部。

上半部的处理有严格限制，且不可被打断，通常是一些硬中断

下半部是可以稍后完成的工作，通常在开中断的情况下执行

Linux中用于实现将工作退后执行的机制称为下半部机制，通过tasklet或工作队列实现

tasklet：通过软中断实现，可以理解为一个tasklet就是一个下半部，由一个结构体标识，结构体里有该下半部的状态、引用计数器、处理函数和参数。一个软中断在当一个硬件中断返回，或者在ksoftirqd内核线程中，或者在显示检查和执行带处理的软中断的代码中时会被检查执行。一个tasklet属于一个软中断，所有tasklet以链表的方式连接，由函数tasklt_schedule()调度，该函数将等待执行的tasklet挂到链表表头然后唤醒tasklet软中断，执行该tasklet
工作队列：工作队列机制将中断处理程序的下半部交给一个内核线程去执行，下半部是在进程上下文执行，可以睡眠和被重新调度。内核中有一个工作者线程处理各种中断处理程序交给他的下半部，其将下半部构成work_struct并用队列链表的形式组织起来，同时执行一个死循环函数，不断处理工作队列链表中的work_struct函数，当工作队列为空时线程睡眠，有新的work_struct函数时唤醒。

第三章操作系统的用户接口

用户工作环境

首先明确操作系统提供的环境有：提供各种硬件、软件资源；设计并提供使用方便的命令集合；将操作系统装入计算机并初始化形成用户环境。

接下来一个重要的问题就是系统如何装入计算机，就是系统生成和系统初启的内容。

系统生成是指为了满足物理设备的约束和需要的系统功能，通过组装一批模块来产生一个清晰的、使用方便的操作系统的过程。系统生成需要确定一系列硬件参数，然后通过内核编译，生成所需要的操作系统可执行代码。

系统初启将操作系统的必要部分装入主存并对系统进行初始化工作，最终使系统处于命令接收状态。主要有两种方式，一是独立引导方式，二是辅助下装方式。

辅助下装方式用于多计算机系统，由主控机与前端机构成的系统以及分布式系统种，OS的主要问价不放在系统本身的存储设备种，在系统启动后从另外的计算机系统中将操作系统的常驻部分传送到该计算机中。

独立引导方式又称滚雪球方式，适用于微机和大多数系统，分为以下几步：

初始引导：首先系统加电，然后CPU从ROM中固定位置读取并执行引导程序BIOS，对系统进行自检，保证没有硬件错误。检查完后从硬盘中读入引导程序到固定位置并开始执行
引导程序执行：引导程序执行，将操作系统内核文件读入内存，并将控制交给内核的初始化程序。
内核初始化：完成内核相关的初始化，包括建立与进程、存储管理、设备管理、文件系统等有关的数据结构以及初始化时钟。
系统初始化：完善OS的操作环境，包括加载命令处理程序或者图形用户界面并初始化等。

以Linux为例，其系统初始化包括以下几个步骤：

系统加电或复位
BIOS启动
引导程序执行
Setup.s执行，检查代码，获取主存容量信息，设置设备模式，准备进入保护模式，并设置中断描述符表和全局描述符表
Heads执行，准备中断向量表，检查CPU类型，进行页面初始化
Start_Kernel执行：对CPU、主存、、主存管理程序、进程调度程序、文件系统、中断向量表初始化，建立init进程
init进程对每一个练级终端建立getty进程，此时用户屏幕出现登陆提示符，系统启动完毕。

最后是操作系统对用户程序的处理，其步骤就是程序的编译运行过程，如下图

在连接这一步骤中，以前通常采用静态连接，将所有的外部调用函数都连接到目标文件中形成一个完整的主存映像文件。缺点是若多个应用程序都调用了同一个库中的外部函数，则每个执行文件中都会包含这个外部函数对应的代码。

现代常采用动态连接的方式，动态链接不需要将外部函数链接到目标文件中。而是在应用程序中需要调用外部函数的地方作记录，并说明要使用的外部函数名和引用入口号，形成函数调用链表。

用户接口

就是在第二章中提到过的命令接口和程序接口。这里主要介绍命令接口，又称为操作接口（这书怎么一大堆乱七八糟的名词）

键盘命令：主要功能有注册、通信和注销
图形化用户界面：：分为菜单驱动方式和图符驱动方式
作业控制语言：批处理语言

_{我也不晓得这一节意义在哪里}

系统功能调用

用户程序对操作系统例行子程序的调用以一种特殊的调用方式，也就是访管方式实现。操作系统提供实现各种功能的例行子程序，每个功能对应一个功能号，CPU提供访管指令：svc n，其中svc表示访管指令的记忆符，n为功能号，应用程序通过访管指令调用操作系统例程，处理机执行到访管指令时发生中断，该中断称为访管中断。

这里的系统调用代码属于OS，与一般的库函数不同，库函数由编译器开发商提供，使用系统调用时会引起CPU状态的改变，而一般库函数不会，会引发CPU状态改变的库函数会隐式发出系统调用请求。

不同的操作系统，系统调用实现的具体方法有所不同，但其实质基本如下：

每个系统调用对应一个系统调用号
每个系统调用对应一个执行程序段
每个系统调用要求一定数量的输入参数和返回值

所以实现系统调用需要完成以下工作：

编写实现特定功能的例行子程序
编写访管中断程序，使访管中断发生时能够保护现场并跳转到对应子例程
构造子程序入口地址表

UNIX与Linux的系统功能调用

UNIX与Linux都遵循POSIX标准，系统调用接口完全兼容，大致分三类：进程管理、文件与玩蛇管理、系统状态改变。

UNIX使用自陷指令trap实现访管，trap最低六位只是系统调用类型，Linux使用异常类型，执行int 0x80实现访管，寄存器eax用来传递系统调用号。

在Linux中增加一个新的系统调用功能分以下几步

添加新的功能服务历程，即在/usr/src/linux/kernel/sys.c中田间一个新的函数
添加新的系统调用号，在文件include/asm-i386/unistd.h 添加一项#define __NR_mysyscall xx，名字自己取，数值必须是未选用的数值
修改系统调用表，在/arch/i386/kernel/entry.S中的系统调用表sys_call_table中添加指向新的系统调用的指针。
重新编译并启动新内核。

第四章进程及进程管理

进程引入

在单处理器上单个程序的执行是由严格顺序的，顺序程序有以下几个特点。

顺序性：处理机的操作严格按照程序所规定的顺序执行
封闭性：程序一旦开始执行，其计算结果不受外界因素的影响
可再现性：由于程序的结果只与输入和初始条件有关，所以结果可以再现

但是前面已经提到过，一个程序虽然必须顺序执行，但是多道程序是可以并发执行的，基本思想每个程序依然顺序执行，但是不同程序是轮流占据设备，尽量不要让设备空闲下来，造成微观上串行，宏观上并行的现象。

并发程序具有以下特点：

程序与计算不再一一对应，因为同一时间可以多次调用一个程序，调用一次就是一次计算
程序并发执行时有相互制约的关系，主要表现在对资源和公共变量的争夺上
失去程序的封闭性和可再现性，因为并发执行的程序具有相互制约的关系，尤其是对于共享变量，可能会因为并发程序的执行次序不同导致共享变量具有不同的值，导致错误，这种错误称为与时间有关的错误

进程概念

有了并发程序的概念之后，显然并发程序和顺序程序不太一样，所以有了进程的概念：进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动。

进程和程序有以下区别：

程序是静态的概念，进程是动态的概念
进程是一个独立运行的活动单位
进程是竞争系统资源的基本单位
一个程序可以对应多个进程，一个进程至少包含一个程序

进程有三个基本状态：

运行状态：指正在处理机上运行
等待状态：进程正等待着某一事件的发生而暂时停止执行。这时，即使给它CPU控制权，它也无法执行。
就绪状态：进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行

如果将进程的创建和销毁也视为一个状态，则进程的状态变迁图如下图：

由于进程具有动态的特征，因此除了基本的程序与数据外，操作系统使用进程控制块（PCB）描述进程与其他进程、系统资源的关系以及进程的状态。PCB一般包含以下内容：

进程标识符：进程的唯一标识
进程的状态
当前队列指针next：系统中存在大量的进程，这些进程的PCB以链表队列的形式组织起来
进程优先级
CPU保护现场：当进程释放CPU资源但又未执行完时，CPU的现场需要保存下来以便再次执行
通信信息：进程间通信时的有关信息
家族信息：进程与家族的联系
占用资源清单

Linux中的PCB结构是task_struct，可在include/linux/sched.h中找到相关定义

进程控制

操作系统对进程的管理主要有：进程控制，进程调度，进程同步与通信。

进程控制的主要负责进程的创建、撤销、等待和唤醒。这些操作通过一些不可中断的系统调用完成，称为原语。

进程创建原语：基本过程为首先尝试申请一块空闲的PCB结构，申请失败则报错，成功则将用户指定信息填入PCB，将PCB放入就绪队列，最后返回进程PID
进程撤销原语：基本过程为将本进程所占用的资源给父进程，然后将进程从总队列中摘下，然后释放PCB结构，最后转进程调度。注意撤销进程原语在要被撤销的进程中调用
进程等待原语：基本过程为保护现场，改变状态，让偶将PCB插入等待队列，然后转进程调度。进程等待原语一般在要等待的进程中调用
进程唤醒原语：基本过程为找到某个等待队列，依据为传入的参数，一般是某个造成其他进程等待的事件。对于等待该事件的进程，将队首进程移出等待队列，并置为就绪状态，将PCB插入就绪队列中。显然想要唤醒一个进程应该在另外一个进程中调用唤醒原语

在Linux中，使用函数fork()来创建子进程，调用fork()的函数称为父进程。子进程从父进程继承整个进程的地址空间，子进程和父进程共用代码段，数据段和堆栈段则需要重新开辟。fork()函数在子进程中返回值为0，父进程中返回值为创建的子进程的进程号。Linux还提供exec()系列函数改变进程的执行代码，可以将调用exec()的进程代码变为传入函数的地址指向的可执行文件或者脚本。

Linux中使用exit()撤销一个进程，撤销后的子进程的数据结构被销毁，但是PCB仍然存在，等待父进程回收，父进程未回收前子进程的状态称为僵尸状态。如果父进程在子进程结束前结束了，子进程变为孤儿进程，被1号进程接管，1号进程定期清理僵尸进程

Linux中可以主动让父进程进入等待子进程结束的状态，使用wait()或者waitpid()，前者是等待任意一个子进程结束，后者是等待特定pid进程结束。等待结束的过程中子进程exit后父进程会回收相关资源

进程中的约束关系

进程间的相互制约关系分为两种情况，一是一是由于竞争系统资源而引起的间接相互制约，二是由于共享数据引起的直接相互制约。要写台哦各进程前进的步伐，需要进行进程间的同步，同步的方式可以细分为：进程互斥、进程同步和进程直接通信。直接通信很好理解，就是直接发消息，下面主要介绍互斥和同步

进程互斥指当某进程正在访问某一存储区域时，就不允许其他进程来读出或者修改该存储区的内容，否则，就会发生后果无法估计的错误。共用的存储区域称为临界资源，进程中访问临界资源的程序段称为临界区。

进程同步指并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。本质上来说进程互斥是一种特殊的进程同步，但是为了便于区别一般只把有严格执行顺序的进程同步称为同步问题，所以同步问题一般翻译合作关系，和互斥问题一般反映竞争关系。

同步机构

操作系统提供两种同步机构，一个是锁，一个是信号灯

用变量w代表某种资源的状态，w称为锁，进入临界区前首先检查w的值，如果w是1表示临界区已上锁，继续检测，如果w的值未0则进入临界区并上锁，完成临界区操作后开锁。为了提高效率一般当w为1时不会一直让进程等待，而是转进程调度。

信号灯是一个确定的二元组（s,q），s是一个非负处置的整型变量，q是该信号灯对应的一个队列。s>=0时表示绿灯，进程执行，否则进程PCB进入队列q并被置为等待状态。

使用P和V对信号灯进行操作。

P(s)、V(s)表示对信号灯s进行操作，其两者的基本过程如下

P(s){
	s--;
	if(s<0){
		保留调用进程CPU现场;
		该进程PCB插入s的等待队列;
		置该进程为等待状态;
		转进程调度;
	}
}

V(s){
	s++;
	if(s<=0){//说明有进程在等待
		移出s等待队列队首元素;
		将该进程PCB加入就绪队列;
		将进程状态置为就绪;
	}
}

下面用信号灯解决经典的生产者——消费者问题。生产者——消费者问题是指一到多个生产者和一到多个消费者共享一个可同时容纳多个产品的缓冲区，生产者不断生产产品并放入缓冲区，消费者不断从缓冲区取出产品并消耗它。，并且要求任何时刻最多只有一个生产者或消费者访问缓冲区，机制生产者向满缓冲区输送产品，机制消费者从空缓冲区提取产品。代码如下

main(){
	int full=0;//满缓冲区数目
	int empty=n;//空缓冲区数目
	int mutex=1;//互斥灯
	cobegin
		p1();p2();...;pn();
		c1();c2();...;cn();
	coend
}

producer(){
	while(生产未完成){
		...
		生产一个产品
		p(empty);
		p(mutex);
		送一个产品到缓冲区;
		v(mutex);
		v(full);
	}
}

consumer(){
	while(还要继续消费){
		p(full);
		p(mutex);
		从有界缓冲区中取产品
		v(mutex);
		v(empty);
		...
		消费一个产品;
	}
}

在Linux中提供信号量作为同步机构。使用

int semget(key_t key,int num_sems,int sem_flags)

创建信号灯数组，第一个参数是信号量的标识，用于在不同进程之间使用同一信号量，第二个参数是信号灯数组中元素的个数，第三个参数是访问权限等标记集合，返回值是信号灯集的标识符。

控制信号灯使用

int semctl(int sem_id,int sem_num,int command,...)

该函数主要用于对信号灯的初始化和删除，第一个参数指定信号灯集标识符，第二个参数指定对信号灯集中的哪一个信号灯操作，第三个参数说明操作类型，可以是赋值或者删除等，具体的值被定义为一系列宏，可变参数是赋值时具体的值，是一个联合类型，具体是啥懒得写了，上网查吧。

操作信号灯使用函数

int semop(int sem_id,struct sembuf *sem_ops,size_t num_sem_ops);
/*
struct sembuf{
	short sem_num; 数组下标
	short sem_op; 操作类型，-1为p，1为v
	short sem_flg; 一般设为0
}
*/

第一个参数指明信号灯集id，第二个参数是一个结构体，集体内容如上，最后一个是操作次数，一般为1。通过这个函数可以封装一个P操作或者V操作。

进程通信

进程通信（IPC）是指进程之间传递信息及同步的机制。由于不同进程之间只能在自己的存储空间内访问，因此要实现进程间的通信，需要操作系统提供IPC机制。IPC需要提供两个基本操作：发送和接收消息，基本通信流程为：首先建立链路，然后使用发送和接收消息操作交换信息。

进程通信在同步方式上分为以下几种：

发送端阻塞，接收端阻塞：消息发出去后两端都阻塞，接收后两端都唤醒，用于强同步场合
发送端不阻塞，接收端阻塞：发送端发完就跑，接收端等待，使用最广泛的方案
两端都不阻塞：直接异步，但是可能导致发送失败

在通信时有两种方式，一是直接通信，一个进程直接指明通信进程然后发送消息；二是间接通信，即消息鲜卑发送到一个消息队列，或称为信箱中，然后由接收端去取，这里就有一个信箱的归属权问题，信箱可以在创建它的进程空间中，也可以在操作系统中，前者访问消息简单，可以随意创建，但是创建的开销大，且可能被进程破坏；后者安全，但是由于操作系统空间有限，无法开辟太多信箱。

在Linux中进程可以通过信号这种进行异步通信，信号是一种软中断，属于直接通信；还可以通过管道进行通信，还可以通过消息队列进行通信，还可以通过共享内存进行通信，课程实验都有涉及，懒得写了。

线程的概念及特点

线程可以这样描述：

线程是进程中的一条执行路径
每个线程由自己的私用堆栈和处理机执行环境
线程共享父进程的主存
单个进程可以创建多个同时存在的线程

引入线程概念后，进程的两项功能——“独立分配资源”和“被调度执行”分离开来：进程依然是资源占用的基本单位，而线程则是调度和执行的基本单位。

线程有以下优点：

创建线程开销远比创建进程小
由于共享内存，线程间的通信十分高效
线程的切换十分高效
线程可以提高系统的并行处理能力

但是多线程程序中，一个线程的崩溃会导致所有线程崩溃。

线程同样存在互斥和同步问题，而线程使用的同步机制和方法与进程一样。

线程创建时分为用户级线程和内核级线程。用户级线程的管理工作由创建线程的进程完成，由线程库实现，其创建和调度不需要内核干预，创建和管理的速度快，但是一旦一个线程阻塞整个进程将会阻塞，难以利用多核；内核级线程的管理工作由操作系统完成，创建和切换的速度较慢，但是当线程阻塞时内核会自动调度另一个线程运行，且能很好利用多处理器。

Linux和windows都提供了线程库来创建线程和等待线程执行完毕。

第五章资源的分配与调度

资源管理概述

在第四章_{就在上面几行}提到过，进程是资源占用的基本单位。但是在批处理系统中，还有由多个进程组成的作业，其也需要分配资源，所以对批处理系统有两级资源分配，先分配给作业，再分配给进程。

资源管理的目的：

保证资源的高利用率
在合理的时间内使所有的客户有获得所需资源的机会
对不可共享的资源实施互斥使用
防止由资源分配不当引发的死锁

资源分配应实现的功能：

确定资源数据结构的描述
确定资源的分配原则
实施资源的分配
对资源的存取进行控制并提供安全保护

需要注意的是操作系统分配的资源是虚拟资源，而不是实际的物理资源。虚拟资源可以方便用户的使用并提高资源利用率，前面操作系统的概述中已经提到。

资源分配主要有两种方式，一种是静态分配，即根据用户给出的作业所需资源提前分配，作业运行完毕后收回资源。这种方法常用于批处理系统中作业层面的资源分配；另一种是动态分配，系统在运行过程中根据进程提出的资源需求进行资源动态分配，对进程的资源分配常采用这种方式。

资源管理机制与策略

资源分配机制有资源描述器和资源信息块，前者用于描述资源实体，后者用于描述资源分配状态。

资源描述器（rd）是描述各类资源的最小分配单位的数据结构，如主存的快，磁盘的扇区，文件等。其包括资源名称、类型、最小分配单位大小、地址、分配标志，描述其链接信息、存取权限、密级、存取时间等。

资源信息块（rib）描述某类资源的请求者、可用资源和资源分配程序，其内部有三个指针，一个指向请求进程的PCB队列，一个指向该类资源的rd队列，一个指向资源分配程序。

一般分配资源时有两种角度，一种是站在资源的角度选择请求者，一种是站在请求者的角度选择资源，由于一般请求者远大于资源，显然资源应该占据选择的主动权，所以资源分配策略特指选择请求者。常用的资源分配策略有以下几种：

先请求先服务：直接用一个队列实现
优先调度：为每个请求指定一个优先级，然后以优先级为key用优先队列实现
针对设备特性的调度：本质上还是优先调度，但是优先级和设备特性相关。以磁盘请求为例，由于磁盘速度慢，其读取是靠机械移臂和读写头旋转实现的，针对机械设备的特点，有移臂调度和旋转调度。移臂调度总是选取与当前移臂前进方向上最短的请求，旋转调度总是选取与当前旋转方向上最近的请求。移臂调度有最短寻道时间优先算法（SSTF），即每次寻找据当前移臂最近的单位，和扫描算法（电梯调度），即每次寻找沿着当前方向最近的请求。

死锁

在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，称这一组进程产生了死锁。

死锁可以由系统资源分配图看出来。系统资源分配图的顶点由进程和资源表示，圆圈为进程，方框为资源，方框中的点为资源实例。圆圈指向方框表示进程请求资源，方框中的点指向圆圈表示资源实例已经分配给进程。当没有环路时不会发生死锁，当有环路，且环路上所有资源的实例都分配给了环路上的进程时会发生死锁。如下图中P1-R1-P2-R3-P3-R2-P1环路会发生死锁，但是环路P2-R3-P3-R2不会发生死锁，因为R2中还有一个实例不是分配给P2和P3的。（当然实际上会死锁，但是不是因为这个环路，而是因为前面那个个环路）

产生死锁的必要条件有：

互斥条件：设计的资源是非共享的
不剥夺条件：进程所获得的资源在未使用完毕前不能被其他进程强行夺走
占有并等待：进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源。
环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。

解决死锁有以下策略：

静态分配：属于死锁的预防，在作业调度时为选中的作业分配它所需要的所有资源，资源一旦分配给该作业后，在其整个运行期间这些资源为它独占，破坏了占有并等待条件。但是要一次提出全部资源很困难，容易造成资源的浪费。
有序资源分配法：属于死锁的预防，给系统中所有的资源给定一个编号，分配时必须以上升次序进行，破坏了死锁的环路条件。但是进程实际需要的资源顺序不一定和编号升序一致，假设我现在使用顺序是2~1，但是我必须按1_{2顺序请求资源}，这样的话1就会在我手上闲置一段时间，会造成浪费。
银行家算法：属于死锁的避免，需要知道当前进程需要的资源数和已有的资源数，剩余资源优先满足能够运行完成的进程，然后该进程就可以把资源释放，然后对剩下的进程进行同样的操作，类似银行贷款时优先给能够如期还款的人。该算法和静态分配一样需要提前知道需求量，比较难实现，同时算法比较保守，因为进程并不是总是需要最大资源量才能运行完成。
死锁的检测和解除：对资源的分配不加任何限制，也不采取死锁避免措施。系统定时地运行一个“死锁检测”程序，判断系统内是否已出现死锁，如果检测到系统已发生了死锁，再采取措施解除它。检测就通过资源分配图检测，解除的方法有很多，从简单粗暴到精打细算，有重启操作系统，杀死所有死锁进程，逐个杀死进程直至死锁解除，逐个剥夺死锁进程资源直至死锁解除，根据系统的checkpoint回退进程直至死锁解除。
忽略死锁：死锁也不是什么常见问题，操作系统懒得管了，死锁发生的时候人手工解决一下。解决方法参考上一条。

第六章处理机调度

处理机的多级调度

处理机本质上也是一种资源，但是对于单处理机机器，处理机是单入口资源，所以在处理机调度方面，人们更关心运行时间。

和上一章一样，由于批处理系统的特殊性，作业调度和进程调度的方法也有所不同。由于现代操作系统中一般采用分页分段的虚拟内存机制，所以处理机的调度还涉及程序的从辅存交换器的换入。因此处理机的调度分为多级。分别是长期调度（作业调度），中期调度（换入调度）和短期调度（进程和线程的调度）。

本章主要涉及的是作业调度和进程调度（线程大差不差）

作业调度

在批处理系统中，作业调度程序负责作业一级的处理。

首先作业调度应该有一个数据结构描述作业，这个数据结构称为作业控制块（jcb），其记录了作业名称、作业资源要求、作业类型、作业使用情况、作业优先级和作业状态。其中名称不用解释，资源包括估计执行时间、最迟完成时间以及需要的硬件资源，这些需要用户给出，资源使用情况包括作业加入系统时间，开始执行时间，已执行时间以及硬件资源占用情况，类型由作业运行特性决定，优先级不用解释，作业状态分为后备状态，执行状态和完成状态。

调度算法的性能由两个指标，分别是平均周转时间t和平均带权周转时间w，计算方法如下

其中t_ci为作业i完成时间，t_si为作业进入时间，t_ri为作业实际执行时间，t_i称为周转时间。

作业调度算法有以下几种

先来先服务算法：老熟人了
短作业优先法：可以理解为优先级为作业执行时间，越短优先级越高。效率最好（算法考试哭泣）但是对长作业不公平
响应比者高优先：响应比就是w_i，相当于优先级就是他，可以照顾一下等了老长时间的作业。
优先调度算法：设个优先级

进程调度

首先明确两个概念

调度：在众多处于就绪状态的进程中，按一定的原则选择一个进程。
分派：当处理机空闲时，移出就绪队列中第一个进程，并赋予它使用处理机的权利。

进程调度首先要有描述进程的数据结构，前面提过了是PCB，然后要决定分配策略，最后实施处理机的分配与回收。

CPU在下面的几个时机发生进程的调度：

当一个进程从运行态切换成等待态时;
当一个进程从运行态切换成就绪态时;
当一个进程从等待态切换成就绪态时;
当一个进程终止时。

进程调度方式主要有先来先服务后优先调度两种。通过前面的论述基本可以看到先来先服务很少曹勇，所以主要介绍优先调度。

在优先调度中首先确定的原则是当一进程正在处理机上执行时，若有某个更为“重要而紧迫”的进程需要进行运行，系统如何分配处理机。如果当前进程允许被打断，称为剥夺方式，否则称为非剥夺方式。

下面介绍几种进程调度算法：

进程优先数调度算法：很直观，关键在于优先数的确定。优先数分为静态优先数和动态优先数。前者是进程被创建时确定的，确定后不再改变，一般通过需要的资源、估计的运行时间和进程的类型确定；后者是进程运行期间可以改变的，通过使用CPU的时间、进行I/O操作的时间以及等待时间确定。UNIX、Linux都采用这种方法，且使用静态动态优先数配合使用。
循环轮转调度算法：简单的循环轮转调度算法就是FIFO的改进，首先确定一个时间片，t为响应时间，n是最大进程数。进程PCB按照FIFO的就绪队列组织，每次出队一个进程，执行时间q后切换进程，将该进程转为就绪态放到就绪队列末尾。改进的循环轮转调度算法有：
- 可变时间片轮转调度：时间片的大小是可以改变的，系统可以根据系统中当前集成商来确定时间片的大小这种算法从理论上克服了系统中进程数很少时系统开销大的缺点，但修改时间片的大小、统计系统进程的数量也需要消耗系统时间。另外，调整时间片大小的周期若太大，等于是固定时间片；若太小，则系统开销很大，得不偿失。
- 多重时间片循环调度：又称反馈循环队列或者多队列策略。要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片，较低优先级分配较长的时间片，处理器调度从该机就绪队列选取进程，当高级就绪队列为空时，才从低一级的队列取进程。一个进程执行完一个时间片后如果没有完成，进入低一级就绪队列。

以上只是大概分为两种，其实还可以时间片和优先数混合调度，因为循环轮转调度中反正也有队列，也可以用优先队列。

Linux系统的进程调度

Linux的进程调度策略基于动态优先级和可变时间片的调度，且为可抢占式调度。

动态优先级方面，首先进程创建时有一个静态优先级，动态优先级的计算方式为max(100,min(静态优先级-bonus+5，139))。其中bonus与进程的平均睡眠时间有关。优先级越小优先级越高。

可变时间片与静态优先级有关，有一张表记录优先级和基本时间片的典型值。

调度时Linux维护的最重要的数据结构是可运行队列，其给定处理机上可运行进程的链表。

可运行队列中重要的数据还有两个优先级数组，优先级数组是prio_array类型的结构体，该数组描述了可运行进程的集合，包括其包含一个集合中进程数量的计数器，一个优先级位图，以及140个双向链表表头，每一个链表对应一个可能的进程优先级队列。调度时可以通过查找优先级位图来查找优先级最高的链表，由于位图的位数有限，所以复杂度O(1)

第七章主存管理

主存管理概述

现代操作系统主存以分片的形式实现共享，片的大小可以相等，也可以不等，不相等时称为按区（或按段分配），相等时称为按页分配。

现代操作系统中，用户并不直接使用物理地址，而是使用逻辑地址，每一个应用程序都相信它的主存是从0开始的一段地址空间。

应用程序的地址组织方式有两种，一种是一维的，即地址按照物理地址组织为连续的地址空间；第二种是二维的，首先将程序分为不同的段，比如堆栈段、数据段、代码段，不同段内按一维方式组织数据。

现代操作系统提供的主存管理功能包括以下几点：

将逻辑地址映射为物理主存地址
在多用户之间分配物理主存
对各用户的信息提供保护措施
扩充逻辑主存区

本章先介绍上面几个功能的实现，然后介绍几种分片形式，包括分区、分页和分段。

主存管理功能

虚拟存储器：是主存管理最基本的概念，实现的是扩充逻辑主存区的功能。其基本思路是计算机在处理应用程序时只装入部分程序代码和数据就启动运行，由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样使得用户能够使用的主存大小几乎等于主存加辅存的大小，相应的用户使用的地址也是虚地址空间的逻辑地址。其能够实现的原因是程序局部性原理
地址映射：实现的是将逻辑地址映射为物理主存地址的功能。由于应用程序认为自己的地址是从0开始的，所以其物理地址等于程序装入空间的首地址加上虚拟地址（目前只是朴素的想法，实际上对于分段和分页式存储管理有自己的地址映射方式）。根据地址映射的时机，可以分为编译时确定（程序编译好后地址就定死了），静态地址映射（程序装入主存后定死在程序里），动态地址映射（有一个重定位寄存器，在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射，地址不用定在程序里）
主存分配：根据不同存储管理方式有很大不同，但是基本要解决三个问题：放在哪儿，何时放，主存满时如何淘汰，即放置策略、调入策略和淘汰策略
存储保护：在多用户环境中，主存储器按区分配给各用户程序使用。为了互不影响，必须由硬件 (软件配合)保证各用户程序只能在给定的存储区域内活动，这种措施叫做存储保护。常用手段有界地址保护（每个应用程序有一对寄存器记录其上下界地址，访问地址只允许在这里面进行）和存储键保护（为每个进程的连续存储器分配一个若干位的存储保护键，相当于锁，每个进程也有一个保护键，相当于钥匙，一个进程访问这一段存储区域时要用钥匙开锁）

分区存储管理及其存在的问题

静态分区存储管理在操作系统初启时将内存分为一个个区，固定不变，一个程序只能进入一个区允许，操作系统中有一张表记录区的大小地址和使用情况。

动态分区存储管理在操作系统初启时低端留给操作系统，高地址端为空闲区。当有程序到来时根据程序需要为它在空闲区分配一块区域，程序运行完后释放资源。显然释放资源后可能会在占用区之间留下空闲区，即空闲区将不再是连续的区域，这些空闲区需要操作系统进行记录。

为了完成动态分区管理，需要两个数据结构，一个是主存资源信息块（m_rib），其记录了当前整个系统中等待分配的队列、空闲区队列头指针和主存分配程序入口地址；第二个是分区描述器，其中描述了一个分区的状态（即是否分配）、起始地址、大小和next指针。一个主存分配情况以及m_rib情况如下图所示

在有新的进程需要分配内存时，显然应该在空闲区队列里找一块分配，然后更新空闲区队列，空闲区可以分配给进程的基本要求就是空闲区大小大于进程要求的大小。由于使用链表组织空闲区队列，放置策略基本上和链表的排序方式是绑定的，因为基本操作是从前往后遍历找到的第一个符合要求的空闲区。下面讨论三种放置策略以及他们对应的排序原则算法。

首次匹配：对应首次适应算法，队列按照地址升序排列，有点事能够尽可能利用低地址空闲区，缺点是低地址小分区多，查找效率低。
最佳匹配：对应最佳适应算法，队列按照空闲区大小升序排列，优点是能够尽量利用小分区，缺点是小分区多，查找效率低，且一般很难找到刚好匹配的空闲区，生成更多的小分区。
最坏匹配：对应最坏适应算法，队列按空闲区大小降序排列。优点是尽可能地利用存储器中的空闲区，分配时查找效率高。缺点是容造成大分区减少，难以满足大型程序的需要。

回收时的策略基本按照放置策略来，释放空间后合并相邻空间然后重新排序。显然首次匹配回收时最简单，只需按地址合并。最佳匹配和最坏匹配在合并后需要重新排序，效率低。

为了充分利用主存，必要时候需要移动存储器中的某些已分配区中的信息使碎片空闲区链接为一个大的空闲区，这个开销非常大。碎片问题也是分区存储最大的问题，除此之外，分区存储还有以下问题：

程序必须整体装入，但实际上大部分时候程序只会允许一部分代码，剩下的代码基本上就占着主存不动
需要连续的存储空间，也就是导致碎片问题的一个原因。

页式存储管理

程序的地址空间被分为大小相等的片，称为页面或者虚页，主存同样被分为大小相等的片，称为主存块或者实页、页框。主存块与页面大小相等。这样的话一个程序的字节逻辑地址可以被分为两部分，一部分是页号，一部分是页内偏移，由于主存块和页面大小相同，故逻辑地址和物理地址的页内偏移相同，寻址只需知道虚页和实页之间的对应关系，对应关系存在页表中

有了以上概念，在一个简单的页式存储管理系统中，地址映射的过程为：将逻辑地址分为页号和页内偏移，将页号加上页表基址寄存器得到页表的对应项，取出主存块号和页内偏移拼接即可得到实地址。

页表可以存放在高速缓存中，也可以存放在主存中，但是一般页表较大，存放在高速中成本太高，而全部存放在内存中由太慢，一般的解决方式是考虑到程序的局部性，将常用的部分部分存放在cache中，称为快表TLB，这个cache称为联想寄存器，整个页表还是在内存中。地址映射时TLB和内存同时开查，若在TLB查到表项则停止内存查找，直接完成地址转换，否则在内存中找到后，将该项换入TLB，进行地址转换。

有了页式系统，我们可以做到一次只调入程序的一部分进入主存运行，则页表需要扩充两项，一项标识该页是否存在主存中，另一项记录该页在辅存中的地址。进行地址转换时如果某页不在主存中，发生缺页中断，由操作系统将该页从辅存中调入，并更新页表，然后回到中断发生处继续执行。

有了换页操作后，一个自然的问题是主存满时，要换入一页必须淘汰一页，淘汰哪一页呢。目前由以下几种淘汰算法

最佳算法（OPT）：只是概念上的算法，当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页。引入一个概念叫缺页中断率，等于发生缺页中断的次数除以总访问页表的次数
先进先出算法（FIFO）：老朋友了，实现这个算法需要记录页面调入次序以及最先进入的页面。
最久未使用淘汰算法（LRU）_{实际上LRU应该是最近未使用淘汰算法，最久未使用应该是LFU。但是教材和老师都是这么教的，要恰分的嘛。}：字面意思，需要使用一个计数器，或者页面栈。计数器很好理解，每个表项加一个计数器，访问一次加1，然后挑计数值最小的淘汰。页面栈是教材和老师的教法，但是根据描述这更像一个队列，基本思想是访问一次页面就把一个页号压栈，如果页号已经在栈里就把靠近栈底的那个号删了，一旦栈满就淘汰栈底元素。_{这个栈算法就有LRU的味道，不知道怎么分类}
LRU近似算法（CLOCK）_{貌似这才是LRU算法}：为每个表项加一个引用位，周期性置0，一个页面被访问到了就置1。选择一个引用位为0的页表项淘汰。

段式和段页式存储管理

段的概念前面在论述二维地址空间已经说过了，其地址映射和页式差不多，逻辑地址分为段号和段内偏移，有一个段表提供段号对应的段长度和段基址的转换。

虽然地址映射方式相似，但是段式存储管理和页式存储管理有本质的区别：

段是按逻辑划分的，而页仅仅是一个物理概念
段长是可变的，页是固定大小的
段对用户是可见的，而页对用户不可见
段是二维的，即每一段内地址是有界的，溢出是有错误的，在逻辑上就是不成立的，但是页是一维的，页内偏移溢出逻辑上相当于翻一页而已。

综合段式和分页存储管理，即可得到段页式系统，即在段式管理的基础上，为每一段引入分页管理。

Linux存储管理

Linux采用段页式存储管理技术，基础地址映射细节不必赘述。值得注意的是Linux在分页时使用的是三级页表，一个地址分为页目录、页表和页内偏移三段，通过页目录找到应该查哪个页表，通过页表号确定实页号，最后找到物理地址

第八章设备管理

设备管理概述

操作系统的设备管理，又称输入输出管理，负责管理设备和I/O传输操作。设备管理的主要目的是提高设备利用率，合理安排设备提高设备与CPU的并行性，以及方便用户使用，屏蔽设备的物理细节。

设备管理应实现以下功能：

设备状态跟踪：设计并维护描述设备状态信息的数据结构
设备分配：将设备分配给需要使用的进程
设备控制：发出I/O指令

为了方便用户使用，操作系统需要保证设备独立性，即用户在程序中使用的设备与实际使用的设备无关，也就是在用户程序中仅使用逻辑设备名。设备独立性有两种，一种是要求程序独立于分配给它的某种类型的具体设备，即绝对的设备独立性，第二种是程序应尽可能与它使用的I/O设备无关，即相对的设备独立性。

常见的实现设备独立性的方式有软通道和指派命令，基本形式都是讲逻辑符号与设备实体建立联系，一般建立联系后进程控制块PCB的ldd_ptr指向的链表会多一项逻辑设备描述器，描述了逻辑设备的信息，包括设备的逻辑和物理名称以及设备控制块。

最后是描述设备状态的数据结构设备控制块，其中记录了设备名称、属性、状态、命令转换表等一系列设备信息。命令转换表包含了设备特定的I/O操作程序的地址。

缓冲技术

第一章提到过I/O设备和CPU之间的速度是不匹配的，通道和中断的出现缓解了这一问题，为了进一步缓解这一问题，可以采用缓冲的技术，即在高速CPU和慢速I/O设备之间加一个缓冲，CPU要输出时先输出到缓冲，缓冲再慢慢输出到I/O，CPU要输入时先可以转进程调度，I/O先往缓冲里输，输的差不多CPU再来快速读取数据。

缓冲可以通过硬件实现，也可以通过在主存或者较高速的辅存中开辟一块软件缓冲区实现。

引入缓冲后，可以处理数据流的生产者与消费者间的速度差异，协调传输数据大小不一致的设备，同时可以在拷贝时将缓冲区复制到内核缓冲区保证应用程序的拷贝语义。

常见的缓冲技术有双缓冲、环形缓冲和缓冲池，搞得花里胡哨的，基本原理都差不多，就是开辟多个缓冲区，轮流使用这些缓冲区提高并行性。

设备分配

设备本质上是一种资源，其实还是遵循前面的资源分配的，分配策略也就是FIFO和优先级分配，这里不做赘述。结合更加具体的物理特性，将分配分为三种：

独享分配：静态资源分配，针对无法共享的设备，比如一次要打完一篇文章的打印机、重新读写需要重新定位的磁带等设备，在进程需要时直接分配给一个进程
共享分配：可以在多个进程之间来会切换使用的设备，分配方式按照前面的资源动态分配来进行
虚拟分配：主要是针对独占分配，将独占设备虚拟化为共享设备，比如打印机，可以在磁盘上开几个缓冲区，一个缓冲区就是一个虚拟打印机，进程往这里面输出，然后由缓冲区向物理打印机输出字符。这样的好处是提高了那些不适合共享的设备的设备的利用率。

输入输出控制

在组成原理中已经见过大部分的I/O设备控制方式了，下面简单总结一下：

循环测试方式：当CPU需要I/O时，向I/O设备发信号，测试I/O设备是否准备好，是则开始I/O，否则进入循环测试，或者转进程调度，过一段时间再来测试。
中断方式：和循环测试方式相比，主动权在I/O设备上。首先仍然是CPU发I/O信号，然后转进程调度，当I/O设备准备好后发中断信号，CPU处理I/O中断，进入I/O操作。
DMA方式：需要I/O时，DMA与CPU通信后接管总线控制权，将I/O数据由DMA设备控制直接从I/O设备写道主存，最后通过中断使CPU重新获得总线控制权
通道方式：由I/O处理机专门处理I/O，遇到I/O请求时CPU启动通道程序，由通道程序完成时机的I/O，当通道传输完成最后一条指令时，向CPU发I/O 中断，并且通道停止工作。CPU接收中断信号，从通道状态字CSW中取得有关信息，决定下一步做什么。类似通道程序类似脱机批处理中的卫星机，但是通道依然手CPU调控。同时通道和DMA页不同，一般DMA是在设备上的。

现代计算机系统中由大量的设备，为了方便用户使用，将特性相同的设备归为一类，对不同类的设备按统一方式进行处理，使用设备驱动程序对设备的物理差别进行封装，然后在I/O子系统层为用户提供应用接口。

说白了，I/O子系统层给用户提供统一接口，比如read、write和生成socket等，具体的设备控制由I/O子系统核心，即设备驱动程序完成。I/O子系统使进程能与外部设备以及网络进行通信，即实施I/O控制功能。I/O控制功能主要包括

解释用户的I/O系统调用
设备驱动
中断处理

实现控制的方式有两种，一种是直观地使用系统调用命令，另一种是将设备像文件一样对待。

需要提到的是在控制I/O设备时，对于高速、大容量的存储设备，比如磁盘，可能会有大量的I/O请求在等待，此时就要用到第五章提到的移臂算法和旋转算法了。

第九章文件管理

文件系统概述

文件是在逻辑上具有完整意义的信息集合，它有一个名字以供标识，文件名是有若干约束的字符串。文件的文件名是文件的标识，同一目录下不允许出现同名文件。文件还有路径名，在多级文件目录结构中，文件路径名是唯一的。一般文件还有扩展名，用来表明文件的使用特征。每个文件都有自己的属性，描述了文件的类型、保护级等信息。

文件的组织方式可以从两个方面研究，一是逻辑文件，用户通过逻辑文件对文件进行检索和加工，基本单位是逻辑记录；二是物理文件，物理存储器以物理文件的方式存储文件，基本单位是物理记录，在磁盘上就是一个磁盘块

文件系统是操作系统中负责管理和存取文件信息的软件机构，由管理文件的数据结构（目录表、文件控制块、存储分配表等）、文件管理程序组成。文件系统需要为用户提供按名存取的功能，需要为系统提供辅存空间管理、存取文件、构造文件结构、文件保护、文件共享以及一组文件操作命令。

文件的逻辑结构和存取方法

文件的逻辑结构分为流式文件和记录式文件。流式文件是相关有序字符的集合，是无结构的，以信息的个数或者特殊字符为界进行存取；记录式文件是一组连续顺序的记录组成的，记录可以是定长的，也可以是变长的，存取时以记录为基本单位进行。

文件的存取方法分为顺序存取和随机存取。顺序存取时总是在上一次存取的基础上进行的，随机存取根据指出的位置进行存取。

文件的物理结构

首先要明确的是磁盘中数据存取的基本单位是块，而不是字节。磁盘中的块同样有编号

常用的文件物理结构有连续文件、串联文件和索引结构。

连续文件是由一组分配在辅存连续区域的物理块组成的，即文件存放的块号是连续的。当知道文件逻辑记录长度时，要查找文件某一块逻辑记录的物理块号，可以直接根据物理块大小和文件目录想指出的第一个逻辑记录块号直接得到相应的物理块号，存取方便。但是连续文件修改起来比较困难，而且由于文件必须连续存储，可能会造成磁盘中有小的空间无法被利用。

串联文件在每一个磁盘块中分配一个指针区指向下一个磁盘块号。这样能够较好录用辅存空间，且修改简单，但是随机访问时存取速度慢。为了解决这个问题，引入文件映照机构，使用一个单独的文件映照结构记录链表的连接情况，Windows中的FAT就是采用这种方式记录磁盘分配和跟踪空白磁盘簇。

索引文件为每个文件建立逻辑块号与物理块号的对照表，称为索引表。索引文件有数据文件和索引表构成，查找文件时先查文件索引，得到对应逻辑块号的物理块号，然后取物理块号，这是直接索引。当然还可以增加多级索引使索引文件能够表示更大的文件。

文件存储空间的管理

主要是记录空闲磁盘块，空闲磁盘块可视为一个空闲文件占用。常用的方法有

空闲文件目录：用一张表记录空闲文件的位置和大小，当磁盘中存在大量小的空闲文件时表会很大
空闲块链：将空闲块组织成一个链表，分配时按照链表一块块分就好，实现简单，但是当需要增加或者移动空闲块时效率很低，因为相当于操纵一个辅存中的链表，涉及大量的I/O操作，速度比主存可慢多了
位示图：用二进制表示磁盘分配情况，每一字位对应于一个物理块，字位值为1表示被占用，0表示空闲。对于大容量磁盘，位示图较大，需要常驻内存、并建立辅助统计表来提高访问速度，且分配时需要顺序扫描空闲区，速度慢

文件目录

首先明确文件系统管理文件的数据结构是文件控制块FCB，其中包括文件标识和控制信息、逻辑结构信息、物理结构信息、使用信息和管理信息。系统为了加快文件的查找速度，通常将FCB集中起来管理，组成文件目录。

文件目录包括两种目录项：具体文件的FCB和描述子目录的目录文件FCB。由目录项构成的文件称为目录文件。

早期文件系统采用一级目录文件，所有文件在同一级目录下，该目录文件记录了所有文件的FCB，实现了按名存取功能，但是在多用户环境下容易出现重名问题。

现代操作系统一般采用多级文件目录，构成树性目录文件结构，在多级目录系统中 (除最末一级外)，任何一级目录的目录项可以描述一个目录文件，也可以描述一个非目录文件 (数据文件)，而数据文件一定在树叶上。文件的路径名是由根目录到该文件的通路上所有目录文件符号名和该文件的符号名组成的字符串，相互之间用分隔符分隔，这样就解决了重名问题，同名文件放在不同目录下即可。

多级目录结构可以采用纯树型结构，即一个文件只有一个父目录，但是这样难以实现文件的共享，所以一般采用DAG目录结构，运行一个文件有多个目录结构，即允许不同的目录指向同一个文件。

共享与安全

文件共享是指某一个或某一部分文件可以让事先规定的某些用户共同使用，文件的安全是指不同用户对文件的使用权限。

实现文件权限控制有以下几种方法

访问控制表：用矩阵记录所有用户对每个文件的权限
存取控制表：文件主创建文件时将用户分为几类记录在存取控制表中，每一类用户对文件有不同的权限，简化了访问控制表。
用户权限表：和存取控制表相反，对文件进行分组，每个用户对每个组的访问权限不同
口令：用户访问文件时提供口令，操作系统比对口令是否一致再让用户访问文件
密码：用户键入代码键，如果代码键正确，系统对文件能够正确解码，用户能够访问

共享文件的基本问题是如何查找文件。最直观的方法肯定是直接使用绝对路径。下面介绍另外两种方法

当前目录：相对路径寻找文件，这里书上例子中给的当前目录不用./，父目录使用*/而不是../
连接技术：基础是上一节中的DAG，可以在一个目录中直接连访其他目录的文件。UNIX/Linux下的链接文件有两种，硬链接指向的是文件的索引节点，软连接又称符号链接，相当于Windows下的快捷方式，它指向文件的路径。删除硬链接会使文件的引用计数减1，当减为0后文件被删除，删除软连接不会对源文件造成任何影响。

文件操作与文件备份

常用文件操作有创建、删除、重命名、打开、关闭、读、写。以打开和关闭为例：

打开文件指将文件有关目录标目复制到主存中并建立FCB，建立用户与文件的联系。
关闭文件指将FCB从主存中删除。

文件的备份分两种：

周期性转储：按固定的时间周期把存储器中所有文件的内容转存到某种介质上，通常是磁带或磁盘。
增量性转储：只是从上次转储以后已经改变过的信息；增量转储的信息量较小，故转储可在更短的时间周期内进行。

Unix文件系统的主要结构及实现技术

Unix文件有以下特点：

树型文件目录结构
可安装拆卸的文件系统
文件是无结构的字节流式文件
外部设备也是文件

Unix文件的目录项中只有文件名和索引节点编号，其他信息全部放在索引结点编号指向的索引节点上，包括文件所有者标识、文件类型、存取许可权、链接计数、文件存取时间、文件长度和地址索引表。索引节点又称i节点。

Unix文件采用索引结构存储，也就是i节点中的地址索引表。地址索引表根据UNIX 7和UNIX system V不同，索引结构也不同

UNIX 7中地址索引表为i_addr[8]，对小型文件使用8个直接索引，对大型文件使用7个一级间接索引，对巨型文件使用7个一级间接索引和1个二级间接索引
UNIX system V中地址索引表为i_addr[13]，前10个为直接索引，剩下三个分别为一级、二级、三级间接索引

Unix文件目录为目录表，每个目录表算一个目录文件，目录文件由目录项组成，目录项为16个字节，前两个字节为辅存i节点号，后十四个字节为文件名。每个系统有一个根目录，根目录i节点很好找，可以根据i节点找到根目录文件，通过根目录文件找到目录项中某个文件名的i节点，查找的过程基本就是“i节点→目录项→i节点……”直到最后找到。

Unix允许文件链接，前面已经说过了，链接分为软链接和硬链接。

Unix打开文件需要活动i节点表、打开文件表和用户文件描述符表等数据结构维护有关信息：

活动i节点表：当执行打开文件操作时，将文件辅存i节点的有关信息拷贝到主存，形成活动i节点（主存索引节点），若干个活动i节点组成活动i节点表，其内容就是i节点的内容
系统打开文件表：记录打开文件所需的附加信息，包括读写标志，应用计数、指向主存索引节点的指针以及读写位置的指针
用户描述符表：用户进程扩充控制块user中的一个数组u_ofile[NOFILE] 称为用户文件描述符表，其中的每一项 (指针)指向系统打开文件表的一个表项。一个打开文件在用户文件描述表中所占的位置就是它的文件描述符 (或称打开文件号)。

值得注意的是子进程共享父进程的系统打开文件表项，只是单纯把引用计数fcount加1，子进程直接可以使用该文件。但是父进程close()不影响子进程，反之亦然。

Unix使用文件卷描述文件系统。文件卷指可以有组织地存放信息且通常可装卸的存储介质。一个文件卷的结构如下图所示

系统使用管理块记录文件使用情况，管理块内容如下：

struct filsys
{
    int s_isize； /* i节点区总块数 */
    int s_fsize； /* 文件卷总块数 */
    int s_nfree； /* 直接管理的空闲块数 */
    int s_free［100］； /* 空闲块号栈 */
    int s_ninode； /* 直接管理的空闲i节点数 */
    int s_inode［100］； /* 空闲i节点号栈 */
    char s_flock； /* 空闲块操作封锁标记 */
    char s_ilock； /* 空闲i节点分配封锁标记 */
    char s_fmod； /* 文件卷修改标记 */
    char s_ronly； /* 文件卷只读标记 */
    int s_time； /* 文件卷最近修改时间 */
}

需要足以的是s_free[]本质上是一张空闲块表，记录了空闲块的块号。

系统使用成组链接法管理空闲块，即将空闲表和空闲链两种方法相结合，每一组有一张空闲表，每组之间成空闲链。系统初启时，文件存储区是空闲的。将空闲块从尾倒向前，每100块分为一组 (注：最后一组为99 块，因为不用索引表)，每一组的最后一块作为索引表，用来登记下一组100 块的物理块号和块数，即s_nfree和s_free[]。注意，虽然最后一组只有99块，但它的前一组的索引块中依然记块数为100，且s_free[0]=0，以标记空闲块数用完。最前面的一组可能不足100 块，这一组的物理块号和块数存放在管理块的s_free[100] 和s_nfree中。

分配时是看管理块中的s_nfree和s_free[]，每次分配s_nfree减1，只要大于0就说明当前管理块记录的这一组还有空闲块，就分。如果为0，说明已经没有空闲块了，最后一块是下一组的索引，所以将索引复制到管理块中，开始分配这一组的空间。

释放时如果管理块管理的组没满则直接压栈，弄一个新组出来，这个组的索引表就是管理块的索引表，而管理块的索引中s_nfree变1，s_free[0]指向这个刚释放的块。