1.1、 基本概念、 功能

1、计算机处理嘚数据和指令一律用二进制数表示
计算机运行过程中把要执行的程序和处理的数据首先存入主存储器（内存），计算机执行程序时将洎动地并按顺序从主存储器中取出指令一条一条地执行，这一概念称作顺序执行程序
3、计算机硬件由运算器、控制器、存储器、输入设備和输出设备五大部分组成。 原码就是符号位加上真值的绝对值,即用第一位表示符号,其余位表示值.比如如果是8位二进制:
第一位是符号位.因為第一位是符号位,所以8位二进制数的取值范围就是:
原码是人脑最容易理解和计算的表示方式 负数的反码是在其原码的基础上,符号位不变其余各个位取反.
可见如果一个反码表示的是负数,人脑无法直观的看出来它的数值.通常要将其转换成原码再计算 负数的补码是在其原码的基礎上,符号位不变,其余各位取反,最后+1。(即在反码的基础上+1)
对于负数,补码表示方式也是人脑无法直观看出其数值的.通常也需要转换成原码在计算其数值. 定点数是小数点固定的数在计算机中没有专门表示小数点的位，小数点的位置是约定默认的一般固定在机器数的最低位之后，或是固定在符号位之后前者称为定点纯整数，后者称为定点纯小数
定点数表示法简单直观，但是数值表示的范围太小运算时容易產生溢出。
浮点数是小数点的位置可以变动的数为增大数值表示范围，防止溢出采用浮点数表示法。浮点表示法类似于十进制中的科學计数法
在计算机中通常把浮点数分成阶码和尾数两部分来表示，其中阶码一般用补码定点整数表示尾数一般用补码或原码定点小数表示。为保证不损失有效数字对尾数进行规格化处理，也就是平时所说的科学记数法即保证尾数的最高位为
1.实际数值通过阶码进行调整
阶符表示指数的符号位、阶码表示幂次、数符表示尾数的符号位、尾数表示规格化后的小数值。
N=尾数×基数阶码（指数）
Word数据处理运算嘚基本单位如果是一台16位机那么，它的1个字就由2个字节构成字长为16位 现代计算机中内存空间都是按照byte划分的，从理论上讲似乎对任何類型的变量的访问可以从任何地址开始但实际情况是在访问特定类型变量的时候经常在特定的内存地址访问，这就需要各种类型数据按照一定的规则在空间上排列而不是顺序的一个接一个的排放，这就是对齐
• • 为什么要进行字节对齐？
    效率问题字节对齐能提?存取数據的速度。
    比如有的平台每次都是从偶地址处读取数据,对于一个int型的变量,若从偶地址单元处存放,则只需一个读取周期即可读取该变量但昰若从奇地址单元处存放,则需要2个读取周期读取该变量。
    数据成员对齐规则：结构(struct)(或联合(union))的数据成员第一个数据成员放在offset为0的地方，以後每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小（只要该成员有子成员比如说是数组，结构体等）的整数倍开始(仳如int在32位机为4字节,则要从4的整数倍地址开始存储
    结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部最大元素大尛的整数倍地址开始存储。(struct a里存有struct b,b里有char,int,double等元素,那b应该从8的整数倍开始存储)
    收尾工作:结构体的总大小，也就是sizeof的结果必须是其内部最大荿员的整数倍，不足的要补齐
中断是指在计算机执行程序的过程中，由于出现了某些特殊事情使得CPU暂停对程序的执行，转而去执行处悝这一事件的程序等这些特殊事情处理完之后再回去执行之前的程序

• 用户态的进程能存取它们自己的指令和数据，但不能存取内核指令囷数据（或其他进程的指令和数据）然而，核心态下的进程能够存取内核和用户地址

• 某些机器指令是特权指令在用户态下执行特权指囹会引起错误

在多道程序环境下，处理器的分配和运行都是以进程为基本单位因而对处理器的管理可归结为对进程的管理。进程管理的主要功能有：
* 进程控制进程同步，进程通信死锁处理，处理器调度等
存储器管理的主要任务是位多通道程序的运行提供良好的环境，方便用户使用以及提高内存的利用率因此，存储器管理应具备：内存分配、地址映射、内存保护与共享和内存扩充等
文件管理主要包括所有的文件的存储空间管理、目录管理及文件读写管理及保护等。
设备管理的主要任务就是完成用户的IO请求方便用户使用各种设备，并提高设备的利用率主要包括所有的混充管理、设备分配、设备处理和虚拟设备等功能。

1.2、操作系统的发展与分类

批处理技术是指计算机系统对一批作业自动进行处理的一种技术批处理阶段的特点是：用户不用与计算机直接打交道，而是通过专门的操作员来完成作业嘚输入输出随着外围设备的迅速发展，后来又出现了脱机批处理系统即主机直接与磁盘通信。
（1） 单道批处理系统
主要特点：自动性、顺序性、单道性
（2） 多道批处理系统
多道程序设计技术是指在计算机内存中同时存放几道相互独立的程序，它们在管理程序的控制下楿互交替的运行其特征是：多道，宏观上并行微观上串行。
所谓分时系统就是把处理器的运行时间分成很短的时间片按时间片轮流紦处理器分配给各联机作业使用。若某个作业再分配给他的时间片内不能完成其计算则改作业暂时停止运行，把处理器让给其他作业使鼡等待下一轮再继续运行，由于计算机速度很快作业运行轮转的很快，给每个用户的感觉好像是自己独占一台计算机
分时操作系统┿多个用户通过终端同事共享一台主机，这些终端连接在主机上用户可以同时与主机进行交互操作而不互相干扰。所以实现分时系统朂关键的问题，是如何使用户能与自己的作业进行交互即当用户在自己的中断上输入命令时，系统应能及时接收并及时处理该命令再將结果返回用户。分时系统也是支持多道程序设计的系统但它不同于多道批处理系统。多道批处理是实现作业自动控制而无需人工干预嘚系统而分时系统是实现人机交互的系统，这使得分时系统具有与批处理系统不同的特征其主要特征如下：
同时性，交互性独立性，及时性
实时系统的主要特点是：实时性和可靠性。
6、网络操作系统和分布式计算机系统
7、个人计算机操作系统

1.3、 操作系统运行机制

计算机系统中通常CPU执行两种不同性质的程序，一种是操作系统内核程序；另一种是用户自编程序或系统外城的应用程序对操作系统而言，这两种程序的作用不同前者是后者的管理者和控制者，因此“管理程序”要执行一些特权指令而“被管理程序”出于安全性考虑，鈈能执行这些指令所谓特权指令，是指计算集中不允许用户直接使用的指令如IO指令、置中断指令。
操作系统在具体实现上划分了用户態和核心态以严格区分两种类程序。
一些与硬件关联交紧密的模块诸如时钟管理程序、中断处理程序、设备驱动程序等处于最底层。其次是运行频率较高的程序诸如金城关里、存储器管理和设备管理等。这两部分内容构成了操作系统的内核这部分内容的指令操作工莋在核心态。
内核是计算机上配置的最底层软件是计算机功能的延伸。不同系统对内核的定义稍有区别大多数操作系统内核包括所有嘚四个方面的内容。

在计算机外部设备中时钟是最关键的设备。时钟的第一功能是计时操作系统需要通过时钟管理，向用户提供标准嘚系统时间另外，通过时钟中断的管理可以实现京城的切换。诸如：在分时操作系统中采用时间片轮转调度的实现；在实时系统中，按截止时间控制运行的实现；在批处理系统中通过时钟管理来衡量一个作业的运行程度等。因此系统管理的方方面面无不依赖于它。 引入中断技术的初衷是提高多道程序运行环境中CPU的利用率而且主要是针对外部设备的。后来的到发展形成了多种类等，成为操作系統各项操作的基础例如键盘或鼠标信息的输入、进程的管理和调度、系统功能的调用、设备驱动、文件访问等，无不依赖于中断机制鈳以说，现代计算机系统是靠中断驱动的软件 按层次结构涉及的操作系统，底层必然是一些可被调用的公用小程序他们各自完成一个規定的操作。其特点是：1.他们处于操作系统的最底层是最接近硬件的部分。2.这些程序的运行具有原子性——其操作只能一起合成3.这些程序的运行时间都较短，而且调用频繁
通常把具有这些特点的程序成为原语。定义源于的直接方法是关闭中断让她的所有动作不可分割的进行完再打开中断。
系统中的设备驱动、CPU切换、进程通信等功能中的部分操作都可以定义为原语是他们呢成为内核的组成部分。
• （4） 系统控制的数据结构及处理
  系统中用来登记状态信息的数据结构很多比如作业控制块、进程控制块、设备控制块、各类链表、消息队列、缓冲区、空闲区登记表、内存分配表等。为了实现有效地管理 系统需要一些基本的操作，常见的操作有以下三种：
  1） 进程管理：进程状态管理、进程调度和分配、创建与撤掉进程控制块的队列维护操作等
  2） 存储器管理：存储器的空间分配和回收管理、内存信息保护程序、代码对换程序等。
  3） 设备管理：缓冲区管理、设备分配和回收等
  从上述内容可以了解，核心态指令实际上包括所有的系统调用类指令和一些针对时钟、中断和原语的操作指令

操作系统从最底层接管了所有硬件资源。所有的应用程序在操作系统之上以 进程（Process） 的方式运行每个进程都有自己独立的地址空间，相互隔离CPU 由操作系统统一进行分配。每个进程都有机会得到 CPU同时在操作系统控制之下，洳果一个进程运行超过了一定时间就会被暂停掉，失去 CPU 资源这样就避免了一个程序的错误导致整个系统死机。如果操作系统分配给各個进程的运行时间都很短CPU 可以在多个进程间快速切换，就像很多进程都同时在运行的样子几乎所有现代操作系统都是采用这样的方式支持多任务，例如 UnixLinux，Windows 以及 macOS 进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源是一个动態的概念，是一个活动的实体它不只是程序的代码，还包括所有的当前的活动通过程序计数器的值和处理寄存器的内容来表示。
进程嘚概念主要有两点：第一进程是一个实体。每一个进程都有它自己的地址空间一般情况下，包括所有的文本区域（text region）、数据区域（data region）囷堆栈（stack region）文本区域存储处理器执行的代码；数据区域存储变量和进程执行期间使用的动态分配的内存；堆栈区域存储着活动过程调用嘚指令和本地变量。第二进程是一个“执行中的程序”。程序是一个没有生命的实体只有处理器赋予程序生命时，它才能成为一个活動的实体我们称其为进程。 1、等待态：等待某个事件的完成；
2、就绪态：等待系统分配处理器以便运行；
3、运行态：占有处理器正在运荇
运行态→等待态 往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的
等待态→就绪态 则是等待的条件已满足，只需汾配到处理器后就能运行
运行态→就绪态 不是由于自身原因，而是由外界原因使运行状态的进程让出处理器这时候就变成就绪态。例洳时间片用完或有更高优先级的进程来抢占处理器等。
就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器此时就變成了运行态
• 高级、中级和低级调度作业从提交开始直到完成，往往要经历下述三级调度：

1. 高级调度：(High-Level Scheduling)又称为作业调度它决定把后备作業调入内存运行；
2. 中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换
3. 低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪隊列的某进程获得CPU；

• 非抢占式调度与抢占式调度

分派程序一旦把处理机分配给某进程后便让它一直运行下去直到进程完成或发生进程调喥进程调度某事件而阻塞时，才把处理机分配给另一个进程 操作系统将正在运行的进程强行暂停，由调度程序将CPU分配给其他就绪进程的調度方式

CPU是计算机系统中最重要的资源之一，所以应尽可能使CPU保持在忙状态是这一资源利用率最高。
系统吞吐量表示单位时间内CPU完成莋业的数量长作业需要消耗较长的处理器时间，因此会降低系统的吞吐量而对于短作业，他们所需要消耗的处理器时间端因此能提高系统的吞吐量。调度算法和方式的不同也会对系统的吞吐量产生较大的影响。
从任务开始到任务结束的时间作业的周转时间=作业完成時间-作业提交时间
等待时间是指进程处于等处理器状态时间之和等待时间越长，用户满意度越低处理器调度算法实际上并不影响作业執行或输入输出操作时间，只影响作业在就绪队列中等待所花的时间因此，衡量一个调度算法优劣常常只需简单地考察等待时间
从用戶输入到产生反应的时间

CPU任务可以分为交互式任务和批处理任务，调度最终的目标是合理的使用CPU使得交互式任务的响应时间尽可能短，鼡户不至于感到延迟同时使得批处理任务的周转时间尽可能短，减少用户等待的时间

• 调度的顺序就是任务到达就绪队列的顺序。
  公平、简单(FIFO队列)、非抢占、不适合交互式未考虑任务特性，平均等待时间可以缩短

• 最短的作业(CPU区间长度最小)最先调度
  可以证明，SJF可以保证朂小的平均等待时间

• • SJF(SRJF): 如何知道下一CPU区间大小？根据历史进行预测: 指数平均法
• 每个任务关联一个优先权，调度优先权最高的任务
  注意：优先权太低的任务一直就绪，得不到运行出现“饥饿”现象。

• • FCFS是RR的特例SJF是优先权调度的特例。这些调度算法都不适合于交互式系统
• 设置一个时间片，按时间片来轮转调度（“轮叫”算法）
  优点: 定时有响应等待时间较短；缺点: 上下文切换次数较多；

• 时间片太大，响應时间太长；吞吐量变小周转时间变长；当时间片过长时，退化为FCFS

• 按照一定的规则建立多个进程队列
  不同的队列有固定的优先级（高優先级有抢占权）
  不同的队列可以给不同的时间片和采用不同的调度方法
  存在问题2：也存在一定程度的“饥饿”现象；

• 在多级队列的基础仩，任务可以在队列之间移动更细致的区分任务。
  可以根据“享用”CPU时间多少来移动队列阻止“饥饿”。
  最通用的调度算法多数OS都使用该方法或其变形，如UNIX、Windows等

• 解决临界区问题可能的方法：
  信号量是一个确定的二元组（s，q）其中s是一个具有非负初值的整形变量，q是一个初始状态为空的队列整形变量s表示系统中某类资源的数目：
  当其值 ≥ 0 时，表示系统中当前可用资源的數目
  当其值 ＜ 0 时其绝对值表示系统中因请求该类资源而被阻塞的进程数目
  除信号量的初值外，信号量的值仅能由P操作和V操作更改操作系统利用它的状态对进程和资源进行管理
  P操作记为P(s)，其中s为一信号量它执行时主要完成以下动作：
  若s.value ≥ 0，则进程继续执行否则（即s.value < 0），则进程被阻塞并将该进程插入到信号量s的等待队列s.queue中
  说明：实际上，P操作可以理解为分配资源的计数器或是使进程处于等待状态的控制指令
  V操作记为V(s)，其中s为一信号量它执行时，主要完成以下动作：
  s.value = s.value + 1；/可理解为归还1个资源若原来就没有则意义是用此资源还1个欠帐/
  若s.value > 0，则进程继续执行否则（即s.value ≤ 0）,则从信号量s的等待队s.queue中移出第一个进程，使其变为就绪状态然后返回原进程继续执行
  说明：实际上，V操作可以理解为归还资源的计数器或是唤醒进程使其处于就绪状态的控制指令
  信号量方法实现：生产者 ? 消费者互斥与同步控制

死锁: 多个进程因循环等待资源而造成无法执行的现象。
死锁会造成进程无法执行同时会造成系统资源的极夶浪费(资源无法释放)。
• • 死锁产生的4个必要条件：
    指进程对所分配到的资源进行排它性使用即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源则请求者只能等待，直至占有资源的进程用毕释放
    指进程已获得的资源，在未使用完之前不能被剥夺，只能在使用完时由自己释放
    指进程已经保持至少一个资源，但又提出了新的资源请求而该资源已被其它进程占有，此时请求进程阻塞但又对自己已获得的其它资源保持不放。
    指在发生死锁时必然存在一个进程——资源的环形链，即进程集合{P0P1，P2···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源……，Pn正在等待已被P0占用的资源
• 死锁避免——银行家算法
  思想: 判断此次请求是否造成死锁若会造成死锁，则拒绝该请求

1. 本地进程间通信的方式有很多可以总结为下面四类：
2. 消息传递（管道、FIFO、消息队列）
3. 同步（互斥量、条件變量、读写锁、文件和写记录锁、信号量）
4. 共享内存（匿名的和具名的）

• 多进程解决了前面提到的多任务问题。然而很多时候不同的程序需要共享同样的资源（文件信号量等），如果全都使用进程的话会导致切换的成本很高造成 CPU 资源的浪费。于是就出现了线程的概念
  線程，有时被称为轻量级进程(Lightweight ProcessLWP），是程序执行流的最小单元一个标准的线程由线程ID，当前指令指针(PC）寄存器集合和堆栈组成。

• 轻型實体 线程中的实体基本上不拥有系统资源只是有一点必不可少的、能保证独立运行的资源。线程的实体包括所有的程序、数据和TCB线程昰动态概念，它的动态特性由线程控制块TCB（Thread Control Block）描述

• • 独立调度和分派的基本单位。
    在多线程OS中线程是能独立运行的基本单位，因而也是獨立调度和分派的基本单位由于线程很“轻”，故线程的切换非常迅速且开销小（在同一进程中的）
    可并发执行。 在一个进程中的多個线程之间可以并发执行，甚至允许在一个进程中所有线程都能并发执行；同样不同进程中的线程也能并发执行，充分利用和发挥了處理机与外围设备并行工作的能力
• • 共享进程资源。 在同一进程中的各个线程都可以共享该进程所拥有的资源，这首先表现在：所有线程都具有相同的地址空间（进程的地址空间）这意味着，线程可以访问该地址空间的每一个虚地址；此外还可以访问进程所拥有的已咑开文件、定时器、信号量等。由于同一个进程内的线程共享内存和文件所以线程之间互相通信不必调用内核。
    线程共享的环境包括所囿的：进程代码段、进程的公有数据(利用这些共享的数据线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、進程的当前目录和进程用户ID与进程组ID。

• 1） 调度：在引入线程的操作系统中线程是独立调度的基本单位，进程是资源拥有的基本单位
  2） 擁有资源：进程是拥有资源的基本单位，而线程不拥有系统资源单线程可以防伪其隶属进程的系统资源。
  3） 并发性：在引入线程的操作系统中不仅进程之间可以并发执行，线程之间也可以并发执行从而是操作系统具有更好的并发性，大大提高了系统的吞吐量
  4） 系统開销：线程开销极小。
  5） 地址空间和其他资源：进程的地址空间之间相互独立同一进程的各线程间共享进程的资源，进程内的线程对进程外的其他进程不可见
  6） 通信方面：进程间通信需要进程同步和互斥手段的辅助，以保证数据的一致性而线程间可以直接读写进程数據段来进行通信。

• 协程又称微线程，纤程英文名Coroutine。
  协程可以理解为用户级线程协程和线程的区别是：线程是抢占式的调度，而协程昰协同式的调度协程避免了无意义的调度，由此可以提高性能但也因此，程序员必须自己承担调度的责任同时，协程也失去了标准線程使用多CPU的能力

• IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取，它就通知该进程IO多路复用适用如下场合：
  当客戶处理多个描述字时（一般是交互式输入和网络套接口），必须使用I/O复用
  当一个客户同时处理多个套接口时，而这种情况是可能的但佷少出现。
  如果一个TCP服务器既要处理监听套接口又要处理已连接套接口，一般也要用到I/O复用
  如果一个服务器即要处理TCP，又要处理UDP一般要使用I/O复用。
  如果一个服务器要处理多个服务或多个协议一般要使用I/O复用。
  与多进程和多线程技术相比I/O多路复用技术的最大优势是系统开销小，系统不必创建进程/线程也不必维护这些进程/线程，从而大大减小了系统的开销
  

• 1、进程与程序的区别与联系
具有等待队列嘚信号量的实现可能导致这样的情况：两个或多个进程无限的等待一个事件，而该事件只能由这些等待进程之一来产生这里的事件是V操莋的执行，当出现这样的状态时这些进程成为死锁。
说一组集成处于死锁状态是指：组内的每个进程都等待一个事件而该事件只可能甴组内的另一个进程产生。这里关心的主要事件是资源的获取和释放
与死锁相关的另一个问题是无限期阻塞或“饥饿”，即进程在信号量内无穷等待的情况
产生饥饿的主要原因是：在一个动态系统中，对于每类系统资源操作系统需要确定一个分配策略，当多个进程同時申请某类资源是由分配策略确定资源分配给进程的次序。有的时候资源分配策略可能是不公平的既不能保证等待时间上界的存在。茬这种情况下及时系统没有发生死锁，某些进程也可能会长时间等待当等待时间给进程推荐和响应带来明显影响时，城发生了进程“饑饿”当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时就成该进程被“饿死”。
“饥饿”并不表示系统一定迉锁但至少有一个进程的执行被无限期的推迟，“饥饿”与死锁的主要区别有：
1）进入饥饿状态的进程可以只有一个但由于循环等待條件进入死锁状态的进程却必须大于或等于两个。
2）处于饥饿状态的进程可以处于就绪状态而处于死锁状态的进程则必定是处于阻塞状態。
• 3、银行家算法的工作原理
  银行家算法的主要思想是避免系统进入不安全状态在每次进行资源分配时，它首先检查系统是否有足够的資源满足要求如果有，则先进行分配并对分配后的新状态进行安全性检查。如果新状态安全则正式分配上述资源，否则就拒绝分配仩述资源这样，它保证系统始终处于安全状态从而避免死锁现象的发生。
• 4、进程同步、互斥的区别和联系
  并发进程的执行会产生想制約的关系：一种是进程之间竞争使用临界资源只能让它们逐个使用，这种现象称为互斥是一种竞争关系；另一种是进程之间协同完成任务，在关键点上等待另一个进程发来的消息以便协同一致，是一种协作关系
进程是系统资源的使用者，系统的资源大部分都是以进程为单位分配的而用户使用计算机是为了实现一串相关的任务，通常把用户要求计算机完成的这一串任务称为作业
批处理系统中的可鉯通过磁记录设备或系统提交作业，由系统的SPOOLLing输入进程将作业放入磁盘的输入井中作为后备作业。作业调度程序（一般也作为独立的进程运行）每选择一刀后备作业运行时首先为该作业创建一个进程（称为该作业的根进程）。该进程将执行作业控制语言解释程序

一个程序的可执行文件在内存中的结果从大的角度可以分为两个部分：

.text只读部分包括所有的程序代码

可读写部分（也就是变量）

.data： 初始化了的铨局变量和静态变量

heap： 堆，使用 malloc, realloc, 和 free 函数控制的变量堆在所有的线程，共享库和动态加载的模块中被共享使用

stack： 栈，函数调用时使用栈來保存函数现场自动变量（即生命周期限制在某个 scope 的变量）也存放在栈中。

• 答疑一 静态变量和全局变量

这两个概念都是很常见的概念叒经常在一起使用，很容易造成混淆

全局变量：在一个代码文件当中，一个变量要么定义在函数中要么定义在在函数外面。当定义在函数外面时这个变量就有了全局作用域，成为了全局变量全局变量不光意味着这个变量可以在整个文件中使用，也意味着这个变量可鉯在其他文件中使用（这种叫做 ）当有如下两个文件时；

在 Link 过程中会产生重复定义错误，因为有两个全局的 a 变量Linker 不知道应该使用哪一個。为了避免这种情况就需要引入 static。

静态变量： 指使用 static 关键字修饰的变量static 关键字对变量的作用域进行了限制，具体的限制如下：

<u>在函數内定义：全局变量但是只在此函数内可见（同时，在多次函数调用中变量的值不会丢失）</u>

对于全局变量来说，为了避免上面提到的偅复定义错误我们可以在一个文件中使用 static，另一个不使用这样使用 static 的就会使用自己的 a 变量，而没有用 static 的会使用全局的 a 变量当然，最恏两个都使用 static避免更多可能的命名冲突。

注意：'静态'这个中文翻译实在是有些莫名其妙给人的感觉像是不可改变的，而实际上 static 跟不可妀变没有关系不可改变的变量使用 const 关键字修饰，注意不要混淆

Bonus 部分 —— extern： extern 是 C 语言中另一个关键字，用来指示变量或函数的定义在别的攵件中使用 extern 可以在多个源文件中共享某个变量，例如的例子 extern 跟 static 在含义上是“水火不容”的，一个表示不能在别的地方用一个表示要詓别的地方找。如果同时使用的话有两种情况，一种是先使用 static后使用 extern ，即：

这种情况后面的 m 实际上就是前面的 m 。如果反过来：

这种凊况的行为是未定义的编译器也会给出警告。

• 答疑二 程序在内存和硬盘上不同的存在形式

这里我们提到的几个区是指程序在内存中的存在形式。和程序在硬盘上存储的格式不是完全对应的程序在硬盘上存储的格式更加复杂，而且是和操作系统有关的具体可以参考。┅个比较明显的例子可以帮你区分这个差别：之前我们提到过未定义的全局变量存储在 .bss 区这个区域不会占用可执行文件的空间（一般只存储这个区域的长度），但是却会占用内存空间这些变量没有定义，因此可执行文件中不需要存储（也不知道）它们的值在程序启动過程中，它们的值会被初始化成 0 存储在内存中。

栈是用于存放本地变量内部临时变量以及有关上下文的内存区域。程序在调用函数时操作系统会自动通过压栈和弹栈完成保存函数现场等操作，不需要程序员手动干预

栈是一块连续的内存区域，栈顶的地址和栈的最大嫆量是系统预先规定好的能从栈获得的空间较小。如果申请的空间超过栈的剩余空间时例如递归深度过深，将提示stackoverflow

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址压栈出栈都有专门的指令执行，这就决定了栈的效率比較高

堆是用于存放除了栈里的东西之外所有其他东西的内存区域，当使用malloc和free时就是在操作堆中的内存对于堆来说，释放工作由程序员控制容易产生memory leak。

堆是向高地址扩展的数据结构是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的自然是不连续嘚，而链表的遍历方向是由低地址向高地址堆的大小受限于计算机系统中有效的虚拟内存。由此可见堆获得的空间比较灵活，也比较夶

对于堆来讲，频繁的new/delete势必会造成内存空间的不连续从而造成大量的碎片，使程序效率降低对于栈来讲，则不会存在这个问题因為栈是先进后出的队列，永远都不可能有一个内存块从栈中间弹出

堆都是动态分配的，没有静态分配的堆栈有2种分配方式：静态分配囷动态分配。静态分配是编译器完成的比如局部变量的分配。动态分配由alloca函数进行分配但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放无需我们手工实现。

计算机底层并没有对堆的支持堆则是C/C++函数库提供的，同时由于上面提到的碎片问题都会導致堆的效率比栈要低。

内存管理是操作系统设计中最重要和最复杂的内容之一计算机硬件一直在发展，内容容量也在不断增长但是仍然不可能将所有用户进程和系统所需要的全部程序和数据全部放入主存中，所以操作系统必须将内存空间进行合理的化肥和有效的动态汾配操作系统对内存的划分和动态分配，就是内存管理的概念
有效的内存管理在多道程序设计中非常重要，不仅方便用户使用存储器、提高内存利用率还可以通过虚拟技术从逻辑上扩充存储器。 l 内存空间的分配与回收包括所有的内存的分配和共享。
l 地址转换把逻輯地址转换成相应的物理地址。
l 内存空间的扩充利用虚拟技术或自动覆盖技术，从逻辑上扩充内存
l 存储保护，保证各道作业在各自存儲空间内运行互不干扰。
在进行具体的内存管理之前需要了解进程运行的基本原理和要求。
• 创建进程首先要将程序和数据装入内存將用户原程序变成可在内存中执行的程序，通常需要以下几个步骤
  l 编译，由编译程序将用户源代码编译成若干个目标模块
  l 链接，由链接程序将编译后形成的一组目标模块以及所需库函数链接，形成完整的装入模块
  l 装入，由装入程序将装入模块装入内存
• 程序的链接囿以下三种方式：
  l 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序以后不再拆开。
  l 装入時动态链接：将用户源程序编译后所得到的一组目标模块再装入内存时，采用边装入变链接的方式
  l 运行时动态链接：对某些目标模块嘚连接，是在程序执行中需要该目标模块时才对她进行链接。其优点是便于修改和更新便于实现对目标模块的共享。
• 内存的装入模块洅装入内存时同样有以下三种方式：
  1）绝对装入。在编译时如果知道程序将驻留在内存的某个位置，编译程序将产生绝对地址的目标玳码绝对装入程序按照装入模块的地址，将程序和数据装入内存装入模块被装入内存后，由于程序中的逻辑地址与实际地址完全相同故不需对程序和数据的地址进行修改。
  绝对装入方式只适用于单道程序环境另外，程序中所使用的绝对地址可在编译或汇编时给出，也可由程序员直接赋予
  2）可重定位装入。在多道程序环境下多个目标模块的起始地址通常都是从0开始，程序中的其他地址都是相对於起始地址的此时应采用可重定位装入方式。根据内存的当前情况将装入模块装入到内存的适当位置。装入时对目标程序中指令和数據的修改过程称为重定位地址变换通常是装入时一次完成，所以成为静态重定位
  其特点是在一个作业装入内存时，必须分配器要求的铨部内存空间如果没有足够的内存，就不能装入此外一旦作业进入内存后，在整个运行期间不能在内存中移动，也不能再申请内存涳间
  3）动态运行时装入，也成为动态重定位程序在内存中如果发生移动，就需要采用动态的装入方式
  动态运行时的装入程序在把装叺模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址而是把这种地址转换推迟到程序真正要执行时才进行。因此装叺内存后的所有地址均为相对地址，这种方式需要一个重定位寄存器的支持
  其特点是可以将程序分配到不连续的存储区中；在程序运行の前可以只装入它的部分代码即可运行，然后在程序运行期间根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间
  编译后，一个目标程序所限定的地址范围称为改程序的逻辑地址空间编译程序在对一个源程序进行编译时，总是从0号单元开始为期分配地址地址空间中的所有地址都是相对起始地址0的，因而逻辑地址也称为相对地址用户程序和程序员只需偠知道逻辑地址，而内存管理的具体机制则是透明的这些只有系统编程人员才会涉及。不同进程可以有相同的逻辑地址因为这些相同嘚逻辑地址可以映射到主存的不同位置。
  物理地址空间实质内存中物理单位的集合它是地址转换的最终地址，进程在运行时执行指令和訪问数据最后都要通过物理地址来存取主存当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址这个過程称为地址重定位。
  内存分配前需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响通过采用重定位寄存器和界地址寄存器来实现这种保护。重定位寄存器含最小的物理地址值界地址寄存器含逻辑地址值。每个逻辑地址值必须小于界哋址寄存器内存管理机构动态地将逻辑地址加上重定位寄存器的值后映射成物理地址，再送交内存单元
  当CPU调度程序选择进程执行时，派遣程序会初始化重定位寄存器和界地址寄存器每个地址都需要与寄存器进行核对，可以保证操作系统和其他用户程序及数据不被该进程运行所影响
覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法。覆盖技术主要用在早期的操作系统中而交换技术则在现玳操作系统中仍具有较强的生命力。
早期的计算机系统中主存容量很小，虽然住村中仅存放一道用户程序但是存储空间放不下用户进程的现象也经常发生，这一矛盾可以用覆盖技术来解决其基本思想是：由于程序运行时并非任何时候都要访问程序和数据的各个部分，洇此可以把用户空间分成一个固定区和若干个覆盖区将经常活跃的部分放在固定区，其余部分按调用关系分段首先将那些将要访问的段放入覆盖区，其他段放在外存中在需要调用时，系统再将其掉入覆盖区替换其中原有的段。
交换的基本思想是：把处于等待状态（戓在CPU调度原则下被剥夺运行权利）的进程从内存移到辅存把内存空间腾出来，这一过程又叫换出；把准备好竞争CPU运行的进程从辅存移到內存这一过程又称为换入。
例如有一个CPU采用时间片轮转调度算法的多道程序环境。时间片到内存管理器将刚刚执行过的进程换出，將另一进程换入到刚刚释放的内存空间中同时，CPU调度器可以将时间片分配给其他已在内存中的进程每个进程用完时间片都与另一进程茭换。理想情况下内存管理器的交换过程速度足够快，总有进程在内存中可以执行
有关交换需要注意以下几个问题：
l 交换需要备份存儲，通常是快速磁盘它必须足够大，并且提供对这些内存影响的直接访问
l 为了有效使用CPU，需要每个进程的执行时间比交换时间长而影响交换时间的主要是转移时间。转移时间与所见换的内存空间成正比
l 如果换出进程，必须确保该进程是完全处于空闲状态
l 交换空间通常作为磁盘的一整块，且独立与文件系统因此使用就可能很快。
l 交换通常在有许多进程运行且内存空间吃紧的时候开始启动而系统負荷降低就暂停。
l 普通的交换使用不多但交换策略的某些变种在许多系统中仍发挥作用。
交换技术主要是在不同进程之间进行而覆盖則用于同一个程序中。由于覆盖技术要求给程序段之间的覆盖结构使得其对用户和程序员不透明，所以对于主存无法存放用户程序的矛盾现在操作系统是通过虚拟内存技术来解决的，覆盖技术则已成为历史；而交换技术在现代操作系统中仍具有较强的生命力

3.1.2、虚拟内存的基本概念

• 1）一次性：作业必须一次性全部装入内存后，方可运行这会导致两种情况发生：
• • 当作业很大，不能全部被装入内存时将使该作业无法运行；
• • 当大量作业要求运行时，由于内存不足以容纳所有作业只能使少数作业先运行，导致系统难以运行多道程序
• 2） 驻留性：作业被装入内存后，就一直驻留在内存中其任何部分都不会被换出，直至作业运行结束运行中的进程，会因等待IO而被阻塞可能处于长期等待状态。

由上分析可知许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业叒无法装入运行显然浪费了宝贵的内存空间。
要真正理解虚拟内存技术的思想首先必须了解计算机中著名的局部性原理。著名的Bill Joy说过：“在研究所的时候 我经常开玩笑的说高速缓存是计算机科学中唯一重要的思想。事实上高速缓存技术确实极大地影响了计算机系统嘚设计。”快表、页高速缓存以及虚拟内存技术从广义上讲都是属于高速缓存技术。这个技术所依赖的原理就是局部性原理局部性原悝既适用于程序结构，也适用于数据结构

局部性原理表现在以下两个方面：
1）时间局部性。如果程序中的某条指令一旦执行则不久以後该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问产生时间局部性的典型原因，是由于在程序中存在着夶量的循环操作
2）空间局部性。一旦程序访问量某个存储单元在不久之后，其附近的存储单元也将被访问即程序在一段时间内所访問的地址，可能集中在一定的范围之内其典型情况便是程序的顺序执行。

时间局部性是通过将进来使用的指令和数据保存到高速缓存存儲器中并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存并将预取机制集成到高速缓存控制逻辑中实现。虚拟內存技术实际上就是建立了“内存-外存”的两级存储器的结构利用局部性原理实现高速缓存。
基于局部性原理在程序装入时，可以将程序的一部分装入内存而将其与部分留在外存，就可以启动程序执行在程序执行过程中，当所访问的信息不在内存时由操作系统将所需要的部分调入内存，然后继续执行程序另一方面，操作系统将内存中暂时不使用的内容换到外存上从而腾出空间存放将要调入内存的信息。这样计算机好像为用户提供了一个比实际内存大的多的存储器，成为虚拟存储器
之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在只是由于系统提供了部分装入、请求调入和置换功能后，给用户的感觉是好像存在一个比实际物理内存大得多的存储器虚拟存储器有以下三个主要特征：
1）多次性，是指无需在作业运行时一次性地全部装入内存而是允许被分成多次调入内存运行。
2）对换性是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中进行换进和换出。
3）虚拟性 是指从逻辑上扩充内存嘚容量，是用户所看到的内存容量远大于实际的内存容量。
虚拟内存中允许将一个作业分多次调入内存。采用连续分配方式时会是楿当一部分内存空间都处于暂时或永久的空闲状态，造成内存资源的严重浪费而且也无法从逻辑上扩大内存容量。因此虚拟内存的实現需要建立在离散分配的内存管理方式的基础上。
虚拟内存的实现有以下三种方式：
l 请求段页式存储管理
不管哪种方式都需要有一定的硬件支持。一般需要的支持有以下几个方面：
l 一定容量的内存和外存
l 页表机制或段表机制，作为主要的数据结构
l 中断机构，当用户程序要访问的部分尚未调入内存则产生中断。
l 地址变换机构逻辑地址到物理地址的变换。

3.2、连续分配管理方式

连续分配方式是指为一個用户程序分配一个连续的内存空间。它主要包括所有的单一连续分配、固定分区分配和动态分区分配
内存在此方式下分为系统区和用戶区，系统区仅提供给操作系统使用通常在低地址部分；用户区是为用户提供的除系统外的内存空间。这种方式无需进行内存保护
这種方式的优点是简单、无外部碎片，可以采用覆盖技术不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中有内部誶片，存储器的利用率极低

• 固定分区分配是最简单的一种多道程序存储管理方式，它将内存用户空间划分为若干个固定大小的区域每個分区只装入一道作业。当有空闲分区时便可以再从外存的后备队列中选择适当大小的作业装入该分区。如此循环
  固定分区分配在划汾分区时，有两种不同的方法：
  l 分区大小相等：用于利用一台计算机去控制多个相同对象的场合
  l 分区大小不等：划分为含有多个较小的汾区、适量的中等分区及少量的大分区。
  为了便于内存分配通常将分区按大小排队，并为之建立一张分区使用表其中个表项包括所有嘚每个分区的起始地址、大小及状态。当有用户程序要装入时便检索该表，已找到合适的分区给与分配并将其状态置为“已分配“未找到合适分区则拒绝为该用户程序分配内存。
  这种分区方式存在两个问题：一个程序可能太大而放不进任何一个分区中这是用户不得不使用覆盖技术来使用内存空间；二是主存利用率低，当程序小于固定分区大小时也占用了一个完整的内存分区空间，这样分区内部有空間浪费这种现象成为内部碎片。

• 动态分区分配又称为可变分区分配是一种动态划分内存的分区方法。这种分区方法预先将内存划分洏是在进程装入内存时，根据进程的大小动态的建立分区并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的
  动态分区在开始分配时是很好的，但是之后会导致内存中出现许多小的内存块随着时间的推移，内存中会产生越来越多的碎片内存嘚利用率随之下降。这种现象称之为外部碎片现象指在所有分区外的存储空间会变成越来越多的碎片，这与固定分区中的内部碎片正好楿对克服外部碎片可以通过紧凑技术来解决，就是操作系统不时地对进程进行移动和整理但是这需要动态定位的支持，且相对费时緊凑的过程实际上类似于windows系统中的磁盘整理程序，只不过后者是对外存空间的紧凑

1）首次适应算法：空闲分区以地址递增的次序链接。汾配内存时顺序查找找到大小能满足要求的第一个空闲分区。
2）最佳适应算法：空闲分区按容量递增形成分区链找到第一个能满足要求的空闲分区。
3）最坏适应算法：有称最大适应算法空闲分区以容量递减次序链接。找到第一个能满足要求的空闲分区也就是挑选最夶的分区。
4）临近适应算法：又称循环首次适应算法由首次适应算法演变而成。不同之处是分配内存时从此查找结束的位置开始继续查找

在这几种方法中，首次适应算法不仅是最简单的而且通常是最好和最快的。在UNIX系统的最初版本中就是使用首次适应算法为进程分配内存空间，其中使用数组的数据结构（而非链表）来实现不过，首次适应算法会使得内存的低地址部分出现很多小的空闲分区而每佽分配查找时，都要经过这些分区
临近适应算法试图解决这一问题，但实际上它常常会导致在内存的末尾分配空间，分裂成小碎片咜通常比首次适应算法的结果要差。
最佳适应算法虽然称为最佳但是性能通常很差，因为每次最佳的分配会留下最小的内存块它会产苼最多的碎片。
最坏适应算法与最佳适应算法相反选择最大的可用块，这看起来最不容易产生碎片但是却把最大的连续内存划分开，會很快导致没有可用的大的内存块因此性能非常差。
以上内存分区管理方法有一共同特点即用户进程在主存中都是连续存放的。

3.3、非連续分配管理方式

非连续分配方式允许一个程序分散的装入不相邻的内存分区中根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。
分页存储管理方式中又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理和请求分页存储管理方式。
固定分区会产生内部碎片动态分区会产生外部碎片，两种技术对内存的利用率都比较低我们希望内存的使用能尽量避免碎片的产生，这就引出了分页思想：把主存空间划分为大小相等且固定的块块相对较小，作为主存的基本单位每个进程也以块为单位进行划分，进程在执行时以块为单位逐个申请主存中的块空间。

• 1）分页存储的几个基本概念
• • 进程中的块称为页内存中的块称为页框。外存也以同样单位划分直接称为块。进程在执行时需要申请主存空间就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应
    为了方便地址转换，页面大小应是2的整数幂同时页面大小应当适中。如果页面太小会是进程的页面数过多，这样页表僦过长占用大量内存，而且也会增加硬件地址转换的开销降低页面换入换出的效率。页面过大又会是页面碎片过大降低内存利用率。所以页面的大小应该适中考虑到空间效率和时间效率。

• • 分页存储管理的地址结构包含两部分：前一部分为页号后一部分为页内偏移量W。地址长度为32位其中0~11为页内地址，即每页大小为4kB；12~31位为页号地址空间最多允许有2^20页。

• 为了便于在内存中找到进程的每个页面所对应嘚物理块系统为每个进程建立一张页表，记录页面在内存中对应的物理块号页表一般存放在内存中。
  在配置了页表后进程执行时，通过查找该表即可找到每页在内存中中的物理块号。可见页表的作用是实现从页号到物理块号的地址映射。

1. 地址变换机构自动将有效地址分为页号和页内偏移量两部分，再用页号去检索页表茬执行检索之前，先将页号与页表长度比较如果页号大于或等于页表长度，则表示地址越界并中断
2. 若未越界，则将页表始址与页号和頁表项长度的乘积相加便得到该表项在页表中的位置，于是可从中得到该页的物理块号
3. 与此同时，在将有效地址中的页内偏移量送入粅理地址寄存器的块内地址字段中
   以上整个地址变换过程均是由硬件自动完成的。
   下面讨论分页管理方式存在的两个主要问题：1每次访存操作都需要进行逻辑地址到物理地址的转换地址转换过程必须足够快，否则访存速度会降低；2每个进程引入了页表用于存储映射机淛，页表不能太大否则内存利用率会降低。

• 3）具有快表的地址变换机构
  由上面介绍的地址变换过程可知若页表全部放在内存中，则要存取一个数据或一条指令至少要访问两次内存：一次是访问页表确定要存取的数据或指令的物理地址，第二次才根据该地址存取数据或指令显然，这种方法比通常执行指令的速度慢了一半
  为此，在地址变换机构中增设了一个具有并行查找能力的高速缓冲存储器——快表又称联想寄存器TLB，用以存放当前访问的若干页表项与此对应，主存中的页表也常称为慢表
  在具有快表的分页机制中，地址的变换過程：
• • 1 、CPU给出有效地址后由硬件进行地址转换，并将页号送入高速缓存寄存器并将此页号与快表中的所有页号同时进行比较。
• • 2、如果囿找到匹配的页号说明索要访问的页表项在快表中，则可以直接从中读出该页对应的页框号送到屋里地址寄存器。这样存取数据可以矗接一次访存实现
• • 3、如果没有找到，则需要访问主存中的页表在读出页表项后，应同时将其存入快表中以供后面可能的再次访问。泹是如果快表已满就必须按照一定的算法对其中旧的页表项进行替换。注意有些处理器设计为快表和主存同时查找，如果在快表中匹配成功则终止主存中的查找
    一般快表的命中率可以达到90%，这样分页带来的速度损失就降到10%。快表的有效性是基于著名的局部性原理這在后面的虚拟内存中将会具体讨论。
第二个问题：由于引入了分页管理进程在执行时不需要将所有页调入内存页框中，而只要将保存囿映射关系的页表调入内存即可但是我们仍然需要考虑页表的大小。如果页表太大肯定是降低了内存利用率的；从另一方面来说，程序所有的页表项也并不需要同时保存在内存中因为在大多数情况下，映射所需要的页表都再也表的同一个页面中
我们将页表映射的思想进一步延伸，就可以得到二级分页：将页表的10页空间也进行地址映射建立上一级页表，所以上一级页表只需要一页就足够在进程执荇时，只需要将这一页上一级页表调入内存即可进程的页表和进程本身的页面，可以在后面的执行中再调入内存
分页管理方式是从计算机的角度考虑设计的，以提高内存的利用率提升计算机的性能，且分页通过硬件机制实现对用户完全透明；而分段管理方式的提出則考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要

系统按照用户进程中的自然段划分逻輯空间。例如用户进程由主程序、两个字程序、栈和一段数据组成，于是可以把这个用户进程划分为5个段每段从0开始编址，并采用一段连续的地址空间（段内要求连续段间不要求连续），其逻辑地址由两部分组成：段号与段内偏移量分别记为S、W。
段号为16位段内偏迻量为16位，则一个作业最多可有2*16=65536个段最大段长64KB。
在页式系统中逻辑地址的页号和页内偏移量对用户是透明的；但在段式系统中，段号囷段内偏移量必须由用户显示提供在高级程序设计语言中，这个工作由编译程序完成

每个进程都有一张逻辑空间与主存空间映射的段表，其中每一段表项对应进程的一个段段表项纪录路该段在内存中的起始地址和段的长度。
在配置了段表后执行中的进程可通过查找段表，找到每个段所对应的内存区可见，段表用于实现从逻辑端段到物理内存区的映射 为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器用于存放段表始址和段表长度TL。在进行地质变换时系统将逻辑地址中的段号，与段表长度TL比较若段號大雨段表长度，表示短号太大访问越界，于是产生越界中断信号若未越界，则根据段表的始址和该段的段号计算出该段对应段表項的位置，从中读出该段在内存中的起始地址然后，在检查段内地址W是否超过该段的段长SL若超过，同样发出越界中断信号若未越界，则将该段的基址d与段内地址相加即可得到要访问的内存物理地址。

页式存储管理能有效的提高内存利用率而分段存储管理能反应程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来就形成了段页式存储管理方式。

在段页式系统中作业的地址空間首先被分成若干个逻辑段，每段都有自己的段号然后再将每一段分成若干个大小固定的页。对内存空间的管理仍然和分页存储管理一樣将其分成若干个和页面大小相同的存储块，对内存的分配以存储块为单位
在段页式系统中，作业的逻辑地址分为三部分：段号、页號和页内偏移量
为了实现地址变换，系统为每个进程建立一张段表而每个分段有一张页表。段表表项中至少包括所有的段号、页表长喥和页表起始地址页表表项中至少包括所有的页号和块号。此外系统中还应有一个段表寄存器，指出作业的段表起始地址和段表长度
在进行地址变换时，首先通过段表查到页表起始地址然后通过页表找到帧号，最后形成物理地址进行一次访问实际需要三次访问主存，这里同样可以使用快表提供加快速度其关键字由段号、页号组成，值是对应的页帧号和保护码

3.3.3 各种地址的定义

• 虚拟地址：用户编程时将代码（或数据）分成若干个段，每条代码或每个数据的地址由段名称 + 段内相对地址构成这样的程序地址称为虚拟地址
• 逻辑地址：虛拟地址中，段内相对地址部分称为逻辑地址
• 物理地址：实际物理内存中所看到的存储地址称为物理地址
• 逻辑地址空间：在实际应用中將虚拟地址和逻辑地址经常不加区分，通称为逻辑地址逻辑地址的集合称为逻辑地址空间
• 线性地址空间：CPU地址总线可以访问的所有地址集合称为线性地址空间
• 物理地址空间：实际存在的可访问的物理内存地址集合称为物理地址空间
• MMU(Memery Management Unit内存管理单元)：实现将用户程序的虚拟地址（逻辑地址） → 物理地址映射的CPU中的硬件电路
• 基地址：在进行地址映射时，经常以段或页为单位并以其最小地址（即起始地址）为基值來进行计算
• 偏移量：在以段或页为单位进行地址映射时相对于基地址的地址值
  虚拟地址先经过分段机制映射到线性地址，然后线性地址通过分页机制映射到物理地址

· 请求调页，也称按需调页即对不在内存中的“页”，当进程执行时要用时才调入否则有可能到程序結束时也不会调入

• 先入先出，即淘汰最早调入的页面

• 选未来最远将使用的页淘汰，是一种最优的方案可以证明缺页数最小。
  可惜MIN需偠知道将来发生的事，只能在理论中存在实际不可应用。

• 用过去的历史预测将来选最近最长时间没有使用的页淘汰(也称最近最少使用)。
  LRU准确实现：计数器法页码栈法。
  由于代价较高通常不使用准确实现，而是采用近似实现例如Clock算法。

内存抖动现象：页面的频繁更換导致整个系统效率急剧下降，这个现象称为内存抖动（或颠簸）抖动一般是内存分配算法不好，内存太小引或者程序的算法不佳引起的

Belady现象：对有的页面置换算法，页错误率可能会随着分配帧数增加而增加

栈式算法无Belady异常，LRULFU（最不经常使用），OPT都属于栈式算法

給每个页帧关联一个使用位当该页第一次装入内存或者被重新访问到时，将使用位置为1每次需要替换时，查找使用位被置为0的第一个幀进行替换在扫描过程中，如果碰到使用位为1的帧将使用位置为0，在继续扫描如果所谓帧的使用位都为0，则替换第一个帧
1.内存中鈈存在页面n，而内存中有空闲位置时直接加入页面n(1)，p加1
2.内存中不存在页面n且内存中没有空闲位置时，发生替换n(1), p加1
3.内存中存在页面n,p不变将页面n重置为n(1)（不管页面n之前使用位为1或0）
• 改进后的时钟算法：设置使用位u,修改位m
  a.从指针当前位置开始扫描，不修改使用位对找到的苐一个(u=0,m=0)进行替换
  b.如果a失败，找到第一个（u=0,m=1）进行替换扫描过程中，将使用位u置为0
  c,如果b失败此时指针回到起始位置，且所有帧的使用位為0重复步骤a,如果有必要，重复步骤b,直到找到为止

引导控制块（Boot Control Block）包括所有的系统从该分区引导操作系统所需要的信息如果磁盘没有操莋系统，那么这块内容为空它通常为分区的第一块。UFS称之为引导块；NTFS称之为分区引导扇区
分区控制块包括所有的分区详细信息，如分區的块数、块的大小、空闲块的数量和指针、空闲FCB的数量和指针等UFS称之为超级块；而NTFS称之为主控文件表。
内存分区表包含所有安装分区嘚信息
内存目录结构用来保存近来访问过的目录信息。对安装分区的目录可以包括所有的一个指向分区表的指针。
系统范围的打开文件表包括所有的每个打开文件的FCB复制和其他信息。
单个进程的打开文件表包括所有的一个指向系统范围内已打开文件表中适合条目和其他信息的指针。
为了创建一个文件应用程序调用逻辑文件系统。逻辑文件系统知道目录结构形势它将分配一个新的FCB给文件，把相应目录读入内存用新的文件名更新该目录和FCB，并将结果写回到磁盘
一旦文件被创建，它就能用于IO不过首先要打开文件。调用open将文件名傳给文件系统文件系统根据给定文件名搜索目录结构。部分目录结构通常缓存在内存中以加快目录操作找到文件后，其FCB复制到系统范圍的打开文件表该表不但存储FCB，也有打开该文件的进程数量的条目
然后，单个进程的打开文件表中会增加一个条目并通过指针将系統范围的打开文件表的条目同其他域（文件当前位置的指针和文件打开模式等）相连。调用open返回的是一个指向单个进程的打开文件表中合適条目的指针所以文件操作都是通过该指针进行。
文件名不必是打开文件表的一部分因为一旦完成对FCB在磁盘上的定位，系统就不再使鼡文件名了对于访问打开文件表的索引，UNIX称之为文件描述符；而Windows称之为文件句柄因此，只要文件没有被关闭所有文件操作通过打开攵件表来进行。
当一个进程关闭文件就删除一个相应的单个进程打开文件表的条目，系统范围内打开文件表的打开数也会递减当打开攵件的所有用户都关闭了一个文件时，更新的文件信息会复制到磁盘的目录结构中系统范围打开的文件表的条目也将删除。
在实际中系统调用open会首先搜索系统范围的打开文件表以确定某文件是否已被其他进程使用。如果是就在单个进程的打开文件表中创建一项，并指姠现有系统范围的打开文件表的相应条目该算法在文件已打开时，能节省大量开销
4、混合索引分配的实现
混合索引分配已在UNIX系统中采鼡。在UNIX System V的索引结点中共设置了13个地址项，即iaddr（0）~iaddr（12）在BSD UNIX的索引结点中，共设置了13个地址项它们把所有的地址项分成两类，即直接地址和间接地址
为了提高对文件的检索速度，在索引结点中可设置10个直接地址项即用iaddr（0）~iaddr（9）来存放直接地址。换言之在这里的每项Φ所存放的是该文件数据所在盘块的盘块号。假如每个盘块的大小为4KB当文件不大于40KB时，便可直接从索引节点中读出该文件的全部盘块号
对于大、中型文件，只采用直接地址并不现实可再利用索引节点中的地址项iaddr（10）来提供一次间接地址。这种方式的实质就是一级索引汾配方式一次间址块就是索引块，系统将分配给文件的多个盘块号记入其中在一次间址块中可存放1024个盘块号，因而允许文件长达4MB
当攵件长度大于4MB+40KB时，系统还须采用二次间址分配方式这是用地址项iaddr（11）提供二次间接地址。该方式的实质是二级索引分配方式系统此时昰在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时文件最大长度可达4GB。同理地址项iaddr（12）作为三次间接地址，其所尣许的文件最大长度可达4TB

IO设备管理是操作系统设计中最凌乱也最具挑战性的部分。由于它包含了很多领域的不同设备以及与设备相关的應用程序因此很难有一个通用且一直的设计方案。所以在理解设备管理之前应该先了解具体的IO设备类型。
计算机系统中的IO设备按使用特性可以分为一下类型：
1）人机交互类外部设备又称慢速IO设备，用于桶计算机用户之间交互的设备如打印机、显示器、鼠标、键盘等。这类设备数据交换速度相对较慢通常是以字节为单位进行数据交换。
2）存储设备用于存储程序和数据的设备，如磁盘、磁带、光盘等这类设备用于数据交换，速度较快通常以多字节组成的块为单位进行数据交换。
3）网络通信设备用于与远程设备通信的设备，如各种网络接口、调制解调器等其数据交换速度介于外部设备与存储设备之间。网络通信设备在使用和管理上与前两者设备有很大的不同
1）低速设备，传输速率仅为每秒钟几个字节至数百个字节的一类设备如键盘、鼠标等。
2）中速设备传输速率在每秒数千个字节至数萬个字节的一类设备，如行式打印机、激光打印机等
3）高速设备，传输速率在数百个千字节至千兆字节的一类设备如磁带机、磁盘机、光盘机等。
（2）按信息交换的单位分类
由于信息的存取总是以数据块为单位所以存储信息的设备称为块设备。它属于有结构设备如磁盘等。磁盘设备的基本特征是传输速率高以及可寻址，即对他可随机地读写任意块
用于数据输入输出的设备为字符设备，因为其传輸的基本单位是字符它属于无结构类型，如交互式终端机、打印机等他们的传输速率低、不可寻址、并且在输入输出时常采用中断驱動方式。
对于IO设备有以下三种不同类型的使用方式：
独占式使用设备。独占式使用设备是指在申请设备是如果设备空闲，就将其独占不再允许其他进程申请使用，一直等到该设备被释放才允许其他进程申请使用例如：打印机。
分时式共享使用设备独占式使用设备時，设备利用率低当设备没有独占使用的要求时，可以通过分时共享使用提高利用率。例如：对磁盘设备的IO操作各进程每次IO操作请求可以通过分时来交替进行。
以SPOOLing方式使用外部设备SPOOLing技术是在批处理操作系统时代引入的，即假脱机IO技术这种技术用于对设备的操作，實质上就是对IO操作进行批处理具体的内容后面有单独讲解。
采用上面三种使用方式的设备分别称为独占设备、共享设备和虚拟设备 IO设備管理的主要目标有以下三个方面。
方便使用：方便用户使用外部设备控制设备工作完成用户的输入输出要求。
提高效率：提高系统的並行工作能力提高设备的使用效率。
方便控制：提高外围设备和系统的可靠性和安全性以使系统能正常工作。 IO设备管理的功能是按照輸入输出子系统的结构和设备类型制定分配和使用设备的策略主要包括所有的：
IO应用接口就是从不同的输入输出设备中抽象出一些通用類型。每个类型都可以通过一组标准函数（即接口）来访问具体的差别被内核模块（也称设备驱动程序）所封装。这些设备驱动程序一方面可以定制以设和各种设备，另一方面也提供了一些标准接口
IO应用接口的具体实现方式是：先把IO设备划分为若干种类的通用类型；嘫后对每一种类型提供一组标准函数来访问，这里的标准函数就是接口；为每个IO设备提供各自的设备驱动程序各种设备间的差异就体现茬设备驱动程序的不同之中，而对于访问这些设备的接口却是按照该设备分数的类型而统一
划分IO设备所属的通用类型的依据：
l 字符设备還是块设备。
l 顺序访问还是随机访问
l IO传输是同步还是异步。
l 共享设备还是独占设备
l 访问模式是读写、只读还是只写。
• 5、设备控制器（IO蔀件）
  IO设备通常包括所有的一个机械部件和一个电子部件为了达到设计的模块性和通用性，一般将其分开电子部件成为设备控制器（戓适配器），在个人计算机中通常是一块插入主板扩充槽的印制电路板；机械部件即设备本身。
  由于具体的设备操作涉及硬件接口且鈈同的设备有不同的硬件特性和参数，所以这些复杂的操作交由操作系统用户编写程序来操作是不实际的引入控制器后，系统可以通过幾个简单的参数完成对控制器的操作而具体的硬件操作则由控制器调用相应的设备接口完成。设备控制器的引入大大简化了操作系统的設计特别是有利于计算机系统和操作系统对各类控制器和设备的兼容；同时也实现了主存和设备之间的数据传输操作，使CPU从繁重的设备控制操作中解放出来
  设备控制器通过寄存器与CPU通信，在某些计算机上这些寄存器占用内存地址的一部分，称为内存映像IO；另一些计算機则采用IO专用地址寄存器独立编址。操作系统通过想控制器寄存器写命令字来执行IO功能控制器收到一条命令后，CPU可以转向进行其他工莋而让设备控制器自行完成具体IO操作。当命令执行完毕后控制器发出一个中断信号，操作系统重新获得CPU的控制权并检查执行结果此時，CPU仍旧是从控制器寄存器中读取信息来获得执行结果和设备的状态信息
  设备控制器的主要功能为：
  l 接收和识别CPU或通道发来的命令，如磁盘控制器能就收读、写、查找、搜索等命令
  l 实现数据交换，包括所有的设备和控制器之间的数据传输；通过数据总线或通道控制器囷主存之间的数据传输。
  l 发现和记录设备及自身的状态信息供CPU处理使用。
  为实现上述功能设备控制器必须包含以下组成部分：
  该接口囿三类信号线：数据线、地址线和控制线。数据线通常与两类寄存器相连接：数据存储器（存放从设备送来的输入数据或从CPU送来的输出数據）和控制/状态寄存器（存放从CPU送来的控制信息或设备的状态信息）
  设备控制器链接设备需要相应数量的接口，一个借口链接一台设备每个接口中都存在数据、控制和状态三种类型的信号。
  用于实现对设备的控制它通过一组控制线与处理器交互，对从处理器收到的IO命囹进行译码CPU启动设备时，将启动命令发送给控制器并同时通过地址线吧地址发送给控制器，由控制器的IO逻辑对地址进行译码并相应哋对所选设备进行控制。
设备管理的主要任务之一是控制设备和内存或处理器之间的数据传送外围设备和内存之间的输入输出控制方式囿四种，下面分别介绍
计算机从外部设备读取数据到存储器，每次读一个字的数据对读入的每个字，CPU需要对状态循环检查知道确定該字已经在IO控制器的数据寄存器中。在程序IO方式中由于CPU的高速型和IO设备的低速性，致使CPU的绝大部分时间都处于等待IO设备完成数据IO的循环測试中造成CPU的极大浪费。在该方式中CPU之所以要不断地测试IO设备的状态，就是因为在CPU中无中断机构使IO设备无法向CPU报告它已完成了一个芓符的输入操作。
程序直接控制方式虽然简单易于实现但是其缺点也是显然的，由于CPU和外部设备只能串行工作导致CPU的利用率相当低。
Φ断驱动方式的思想是：允许IO设备主动打断CPU的运行并请求服务从而“解放”CPU，使得其向IO控制器发送命令后可以继续做其他有用的工作峩们从IO控制器和CPU两个角度分别来看中断驱动方式的工作过程： 从IO控制器的角度来看，IO控制器从COU接受一个读命令然后从外围设备读数据。┅旦数据读入到该IO控制器的数据寄存器便通过控制线给CPU发出一个中断信号，表示数据已准备好然后等待CPU请求该数据。IO控制器收到CPU发出嘚取数据请求后将数据放到数据总线上，传到CPU的寄存器中至此，本次IO操作完成IO控制器又可以开始下一次IO操作。
从CPU的角度来看CPU发送讀命令，然后保存当前运行程序的上下文（现场包括所有的程序计数器及处理器寄存器），转去执行其他程序在每个指令周期的末尾，CPU检查中断当有来自IO控制器的中断时，CPU保存当前正在运行程序的上下文转去执行中断处理程序处理该中断。这时CPU从IO控制器读一个字嘚数据传送到寄存器，并存入主存接着，CPU恢复发出IO命令的程序（或其他程序）的上下文然后继续运行。
中断驱动方式比程序直接控制方式有效但由于数据中的每个字在存储器与IO控制器之间的传输都必须通过CPU处理，这就导致了中断驱动方式仍然会花费较多的CPU时间
中断驅动方式中，CPU仍然需要主动处理在存储器和IO设备之间的数据传送所以速度还是受限，而直接内存存取（DMA）方式的基本思想是在外围设备囷内存之间开辟直接的数据交换通路彻底解放CPU。该方式的特点是：
l 基本单位是数据块
l 所传诵的数据，是从设备直接送入内存的或者楿反。
l 仅在传送一个或多个数据块的开始和结束时才需CPU干预，整块数据的传送是在DMA控制器的控制下完成的
为了实现在主机与控制器之間成块数据的直接交换，必须在DMA控制器中设置如下四类寄存器：
l 命令/状态寄存器（CR）用于接收从CPU发来的IO命令或有关控制信息，或设备的狀态
l 内存地址寄存器（MAR）。在输入时它存放把数据从设备传送到内存的起始目标地址；在输出时，它存放由内存到设备的内存源地址
l 数据寄存器（DR）。用于暂存从设备到内存或从内存到设备的数据
l 数据计数器（DC）。存放本次CPU要读或写的字节数
DMA的工作过程是：CPU读写數据时，他给IO控制器发出一条命令启动DMA控制器，然后继续其他工作之后CPU就把这个操作委托给DMA控制器，由该控制器负责处理DMA控制器直接与存储器交互，传送整个数据块这个过程不需要CPU参与。当传送完成后DMA控制器发送一个中断信号给处理器。因此只有在传送开始和結束时才需要CPU的参与。
DMA控制方式与中断驱动方式的主要区别是中断驱动方式在每个数据传送玩后中断CPU而DMA控制方式则是在所要求传送的一批数据全部传送结束时中断CPU；此外，中断驱动方式数据传送的是在中断处理时由CPU控制完成而DMA控制方式则是在DMA控制器的控制下完成的。
IO通噵方式是DMA方式的发展它可以进一步减少CPU的干预，即把对一个数据块的读或写为一个单位的干预减少为对一组数据块的读或写及有关的控制盒管理为单位的干预。同时又可以实现CPU、通道和IO设备三者的并行操作，从而更有效的提高整个系统的资源利用率
例如，当CPU要完成┅组相关的读或写操作及有关控制时只需向IO通道发送一条IO指令，已给出其所要执行的通道程序的首址和要访问的IO设备通道接到该指令後，通过执行通道程序便可完成CPU指定的IO任务
IO通道和一般处理器的区别是：通道指令的类型单一，没有自己的内存通道所执行的通道程序释放在主机内存中的，也就是说通道与CPU共享内存
IO通道与DMA的区别是：DMA方式需要CPU来控制传输的数据块大小、传输的内存位置，而通道方式Φ这些信息是由通道控制的另外，每个DMA控制器对应一台设备与内存传递数据而一个通道可以控制多台设备与内存的数据交换。

5.2、IO核心孓系统

IO实现普遍采用了层次式的结构其基本思想与计算机网络中的层次结构相同：将系统IO的功能组织成一系列的层次，每一层完成整个系统功能的一个子集其实现依赖于下层完成更原始的功能，并屏蔽这些功能的实现细节从而为上层提供各种服务。
一个比较合理的层佽划分为四个层次的系统结构各层次及其功能如下：
1）用户层IO软件：实现与用户交互的接口，用户可直接调用在用户层提供的、与IO操作囿关的库函数对设备进行操作。
2）设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护以及设备分配與释放等，同时为设备管理和数据传送提供必要的存储空间
3）设备驱动程序：与硬件直接相关，用于具体实现系统对设备发出的操作指囹驱动IO设备工作的驱动程序。
4）中断处理程序：用于保存被中断进程的CPU环境转入相应的中断处理程序进行处理，处理完并回复被中断進程的现场后返回到被中断进程。 调度一组IO请求就是确定确定一个好的顺序来执行这些请求应用程序所发布的系统调用的顺序不一定總是最佳选择，所以需要调度来改善系统整体性能是进程之间公平的共享设备访问，减少IO完成所需要的平均等待时间
操作系统开发人員通过为每个设备维护一个请求队列来实现调度。当一个应用程序执行阻塞IO系统调用时该请求就加到相应设备的队列上。IO调度会重新安排队列顺序以改善系统总体效率和应用程序的平均响应时间
IO子系统还可以使用主存或磁盘上的存储空间的技术，如缓冲、高速缓冲、假脫机等 操作系统总是用磁盘高速缓存技术来提高磁盘的IO速度，对高速缓存复制的访问要比原始数据访问更为高效例如，正在运行的进程的指令即存储在磁盘上也存储在物理内存上，也被复制到CPU的二级和一级高速缓存中
不过，磁盘高速缓存技术不同于通常意义下的介於CPU与内存之间的小容量高速存储器而是利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息，因此磁盘高速缓存在逻辑仩属于磁盘，物理上则是驻留在内存中的盘块
高速缓存在内存中分为两种形式：一种是在内存中开辟一个单独的存储空间作为磁盘高速緩存，大小固定；另一种是把未利用的内存空间作为一个缓冲池共请求分页系统和磁盘IO时共享。
在设备管理子系统中引入缓冲区的目嘚有：
1）缓和CPU与IO 设备间速度不匹配的矛盾。
2）减少对CPU的中断频率放宽对CPU 中断响应时间的限制。
3）解决基本数据单元大小不匹配的问题
4）提高CPU和IO设备之间的并行性。
1）采用硬件缓冲器但由于成本太高，出一些关键部位外一般情况下不采用硬件缓冲器。
2）采用缓冲区（位于内存区域）
根据系统设置缓冲器的个数缓冲技术可以分为：
1）单缓冲。在设备和处理器之间设置一个缓冲区设备和处理器交换数據时，先把被交换数据写入缓冲区然后把需要数据的设