1. 基础知识

1.1、 基本概念、 功能

• 冯诺伊曼体系结构
  1、计算机处理的数据和指令一律用二进制数表示
  2、顺序执行程序
  计算机运行过程中，把要执行的程序和处理的数据首先存入主存储器（内存），计算机执行程序时，将自动地并按顺序从主存储器中取出指令一条一条地执行，这一概念称作顺序执行程序。
  3、计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成。
• 原码
  原码就是符号位加上真值的绝对值,即用第一位表示符号,其余位表示值.比如如果是8位二进制:
  [+1]原=0000 0001
  [-1]原=1000 0001
  第一位是符号位.因为第一位是符号位,所以8位二进制数的取值范围就是:
  [1111 1111,0111 1111]
  [-127,127]
  原码是人脑最容易理解和计算的表示方式
• 反码
  反码的表示方法是:
  正数的反码是其本身
  负数的反码是在其原码的基础上,符号位不变，其余各个位取反.
  [+1]=[00000001]原=[00000001]反
  [-1]=[10000001]原=[11111110]反
  可见如果一个反码表示的是负数,人脑无法直观的看出来它的数值.通常要将其转换成原码再计算
• 补码
  补码的表示方法是:
  正数的补码就是其本身
  负数的补码是在其原码的基础上,符号位不变,其余各位取反,最后+1。(即在反码的基础上+1)
  [+1]=[00000001]原=[00000001]反=[00000001]补
  [-1]=[10000001]原=[11111110]反=[11111111]补
  对于负数,补码表示方式也是人脑无法直观看出其数值的.通常也需要转换成原码在计算其数值.
• 定点数与浮点数
  定点数是小数点固定的数。在计算机中没有专门表示小数点的位，小数点的位置是约定默认的。一般固定在机器数的最低位之后，或是固定在符号位之后。前者称为定点纯整数，后者称为定点纯小数。
  定点数表示法简单直观，但是数值表示的范围太小，运算时容易产生溢出。
  浮点数是小数点的位置可以变动的数。为增大数值表示范围，防止溢出，采用浮点数表示法。浮点表示法类似于十进制中的科学计数法。
  在计算机中通常把浮点数分成阶码和尾数两部分来表示，其中阶码一般用补码定点整数表示，尾数一般用补码或原码定点小数表示。为保证不损失有效数字，对尾数进行规格化处理，也就是平时所说的科学记数法，即保证尾数的最高位为
  1.实际数值通过阶码进行调整
  阶符表示指数的符号位、阶码表示幂次、数符表示尾数的符号位、尾数表示规格化后的小数值。
  N=尾数×基数阶码（指数）
  位(Bit)、字节(Byte)、字(Word)
  Bit最小单位
  1 Byte=8 Bit
  Word数据处理运算的基本单位如果是一台16位机，那么，它的1个字就由2个字节构成，字长为16位
• 大端小端模式
  小端字节序指低字节数据存放在内存低地址处，高字节数据存放在内存高地址处；
  大端字节序是高字节数据存放在低地址处，低字节数据存放在高地址处。
  Big Endian
  低地址高地址
  ---------------------------------------------------->
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |12|34|56|78|
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  Little Endian
  低地址高地址
  ---------------------------------------------------->
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |78|56|34|12|
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
• 字节对齐
  现代计算机中内存空间都是按照byte划分的，从理论上讲似乎对任何类型的变量的访问可以从任何地址开始，但实际情况是在访问特定类型变量的时候经常在特定的内存地址访问，这就需要各种类型数据按照一定的规则在空间上排列，而不是顺序的一个接一个的排放，这就是对齐。
• • 为什么要进行字节对齐？
    效率问题，字节对齐能提⾼存取数据的速度。
    比如有的平台每次都是从偶地址处读取数据,对于一个int型的变量,若从偶地址单元处存放,则只需一个读取周期即可读取该变量，但是若从奇地址单元处存放,则需要2个读取周期读取该变量。
    字节对齐的原则
    数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小（只要该成员有子成员，比如说是数组，结构体等）的整数倍开始(比如int在32位机为4字节,则要从4的整数倍地址开始存储。
    结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部最大元素大小的整数倍地址开始存储。(struct a里存有struct b,b里有char,int,double等元素,那b应该从8的整数倍开始存储。)
    收尾工作:结构体的总大小，也就是sizeof的结果，必须是其内部最大成员的整数倍，不足的要补齐。
• 中断
  中断是指在计算机执行程序的过程中，由于出现了某些特殊事情，使得CPU暂停对程序的执行，转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序
  1、内部中断
  2、软中断
  3、外部中断
• • 中断优先级
    机器错误>时钟>磁盘>网络设备>终端>软件中断
• • 系统调用
    在讲系统调用之前，先说下进程的执行在系统上的两个级别：用户级和核心级，也称为用户态和系统态(user mode and kernel mode)。
    程序的执行一般是在用户态下执行的，但当程序需要使用操作系统提供的服务时，比如说打开某一设备、创建文件、读写文件等，就需要向操作系统发出调用服务的请求，这就是系统调用。
    发生系统调用时，进程不做工作，由内核做相应操作。
• • 用户态：
    用户态的进程能存取它们自己的指令和数据，但不能存取内核指令和数据（或其他进程的指令和数据）。然而，核心态下的进程能够存取内核和用户地址
• • 核心态：
    某些机器指令是特权指令，在用户态下执行特权指令会引起错误

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

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

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

1.3、 操作系统运行机制

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

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

2. 进程管理

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

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

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

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

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

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

• 调度算法
• • FIFO或First Come, First Served (FCFS)
    调度的顺序就是任务到达就绪队列的顺序。
    公平、简单(FIFO队列)、非抢占、不适合交互式。未考虑任务特性，平均等待时间可以缩短
• • Shortest Job First (SJF)
    最短的作业(CPU区间长度最小)最先调度。
    可以证明，SJF可以保证最小的平均等待时间。
• • Shortest Remaining Job First (SRJF)
    SJF的可抢占版本，比SJF更有优势。
• • SJF(SRJF): 如何知道下一CPU区间大小？根据历史进行预测: 指数平均法。
• • 优先权调度
    每个任务关联一个优先权，调度优先权最高的任务。
    注意：优先权太低的任务一直就绪，得不到运行，出现“饥饿”现象。
• • FCFS是RR的特例，SJF是优先权调度的特例。这些调度算法都不适合于交互式系统。
• • Round-Robin(RR)
    设置一个时间片，按时间片来轮转调度（“轮叫”算法）
    优点: 定时有响应，等待时间较短；缺点: 上下文切换次数较多；
• • • 如何确定时间片？
      时间片太大，响应时间太长；吞吐量变小，周转时间变长；当时间片过长时，退化为FCFS。
• • 多级队列调度
    按照一定的规则建立多个进程队列
    不同的队列有固定的优先级（高优先级有抢占权）
    不同的队列可以给不同的时间片和采用不同的调度方法
    存在问题1：没法区分I/O bound和CPU bound；
    存在问题2：也存在一定程度的“饥饿”现象；
• • 多级反馈队列
    在多级队列的基础上，任务可以在队列之间移动，更细致的区分任务。
    可以根据“享用”CPU时间多少来移动队列，阻止“饥饿”。
    最通用的调度算法，多数OS都使用该方法或其变形，如UNIX、Windows等。

• 进程同步

• 临界资源与临界区
  在操作系统中，进程是占有资源的最小单位（线程可以访问其所在进程内的所有资源，但线程本身并不占有资源或仅仅占有一点必须资源）。但对于某些资源来说，其在同一时间只能被一个进程所占用。这些一次只能被一个进程所占用的资源就是所谓的临界资源。典型的临界资源比如物理上的打印机，或是存在硬盘或内存中被多个进程所共享的一些变量和数据等(如果这类资源不被看成临界资源加以保护，那么很有可能造成丢数据的问题)。
  对于临界资源的访问，必须是互斥进行。也就是当临界资源被占用时，另一个申请临界资源的进程会被阻塞，直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。
  对于临界区的访问过程分为四个部分：
  进入区:查看临界区是否可访问，如果可以访问，则转到步骤二，否则进程会被阻塞
  临界区:在临界区做操作
  退出区:清除临界区被占用的标志
  剩余区：进程与临界区不相关部分的代码
• 解决临界区问题可能的方法：
  一般软件方法
  关中断方法
  硬件原子指令方法
  信号量方法
  信号量
  信号量是一个确定的二元组（s，q），其中s是一个具有非负初值的整形变量，q是一个初始状态为空的队列，整形变量s表示系统中某类资源的数目：
  当其值 ≥ 0 时，表示系统中当前可用资源的数目
  当其值 ＜ 0 时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目
  除信号量的初值外，信号量的值仅能由P操作和V操作更改，操作系统利用它的状态对进程和资源进行管理
  P操作：
  P操作记为P(s)，其中s为一信号量，它执行时主要完成以下动作：
  s.value = s.value - 1； /可理解为占用1个资源，若原来就没有则记帐“欠”1个/
  若s.value ≥ 0，则进程继续执行，否则（即s.value < 0），则进程被阻塞，并将该进程插入到信号量s的等待队列s.queue中
  说明：实际上，P操作可以理解为分配资源的计数器，或是使进程处于等待状态的控制指令
  V操作：
  V操作记为V(s)，其中s为一信号量，它执行时，主要完成以下动作：
  s.value = s.value + 1；/可理解为归还1个资源，若原来就没有则意义是用此资源还1个欠帐/
  若s.value > 0，则进程继续执行，否则（即s.value ≤ 0）,则从信号量s的等待队s.queue中移出第一个进程，使其变为就绪状态，然后返回原进程继续执行
  说明：实际上，V操作可以理解为归还资源的计数器，或是唤醒进程使其处于就绪状态的控制指令
  信号量方法实现：生产者 − 消费者互斥与同步控制

semaphore fullBuffers = 0; /*仓库中已填满的货架个数*/
semaphore emptyBuffers = BUFFER_SIZE;/*仓库货架空闲个数*/
semaphore mutex = 1; /*生产-消费互斥信号*/
Producer() 
{ 
while(True)
{  
/*生产产品item*/
emptyBuffers.P(); 
mutex.P(); 
/*item存入仓库buffer*/
mutex.V();
fullBuffers.V();
}
}
Consumer() 
{
while(True)
{
fullBuffers.P(); 
mutex.P();    
/*从仓库buffer中取产品item*/
mutex.V();
emptyBuffers.V();
/*消费产品item*/
}
}
使用pthread实现的生产者－消费者模型：
#include <pthread.h>#include <stdio.h>
#include <stdlib.h>#define BUFFER_SIZE 10
static int buffer[BUFFER_SIZE] = { 0 };static int count = 0;
pthread_t consumer, producer;pthread_cond_t cond_producer, cond_consumer;pthread_mutex_t mutex;
void* consume(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == 0){
printf("empty buffer, wait producer\n");
pthread_cond_wait(&cond_consumer, &mutex); 
}
count--;
printf("consume a item\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_producer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
void* produce(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == BUFFER_SIZE){
printf("full buffer, wait consumer\n");
pthread_cond_wait(&cond_producer, &mutex);
}
count++;
printf("produce a item.\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_consumer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
int main() {
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&cond_consumer, NULL);
pthread_cond_init(&cond_producer, NULL);
int err = pthread_create(&consumer, NULL, consume, (void*)NULL);
if(err != 0){
printf("consumer thread created failed\n");
exit(1);
}
err = pthread_create(&producer, NULL, produce, (void*)NULL);
if(err != 0){
printf("producer thread created failed\n");
exit(1);
}
pthread_join(producer, NULL);
pthread_join(consumer, NULL);  
//sleep(1000);
pthread_cond_destroy(&cond_consumer);
pthread_cond_destroy(&cond_producer);
pthread_mutex_destroy(&mutex);
return 0;
}

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

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

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

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

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

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

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

2.2 疑难问题

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

3. 内存管理

程序可执行文件的结构

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

只读部分

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

.rodata程序中的常量

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

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

.bss： 即 Block Started by Symbol， 未初始化的全局变量和静态变量

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

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

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

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

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

a.c
#include <stdio.h>
int a;
int compute(void);
int main(){
    a = 1;
    printf("%d %d\n", a, compute());
    return 0;
}
b.c
int a;
int compute(void){
    a = 0;
    return a;
}

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

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

<u>在函数外定义：全局变量，但是只在当前文件中可见（叫做 internal linkage）</u>

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

<u>（C++）在类中定义：全局变量，但是只在此类中可见</u>

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

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

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

static int m;extern int m;

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

extern int m;static int m;

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

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

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

栈

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

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

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

堆

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

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

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

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

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

3.1 内存分配

内存管理基础

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

3.2、连续分配管理方式

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

• • 固定分区
    固定分区分配是最简单的一种多道程序存储管理方式，它将内存用户空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备队列中选择适当大小的作业装入该分区。如此循环。
    固定分区分配在划分分区时，有两种不同的方法：
    l 分区大小相等：用于利用一台计算机去控制多个相同对象的场合。
    l 分区大小不等：划分为含有多个较小的分区、适量的中等分区及少量的大分区。
    为了便于内存分配，通常将分区按大小排队，并为之建立一张分区使用表，其中个表项包括每个分区的起始地址、大小及状态。当有用户程序要装入时，便检索该表，已找到合适的分区给与分配并将其状态置为“已分配“。未找到合适分区则拒绝为该用户程序分配内存。
    这种分区方式存在两个问题：一个程序可能太大而放不进任何一个分区中，这是用户不得不使用覆盖技术来使用内存空间；二是主存利用率低，当程序小于固定分区大小时，也占用了一个完整的内存分区空间，这样分区内部有空间浪费。这种现象成为内部碎片。
• • 动态分区
    动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分区方法预先将内存划分，而是在进程装入内存时，根据进程的大小动态的建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。
    动态分区在开始分配时是很好的，但是之后会导致内存中出现许多小的内存块。随着时间的推移，内存中会产生越来越多的碎片，内存的利用率随之下降。这种现象称之为外部碎片现象，指在所有分区外的存储空间会变成越来越多的碎片，这与固定分区中的内部碎片正好相对。克服外部碎片可以通过紧凑技术来解决，就是操作系统不时地对进程进行移动和整理。但是这需要动态定位的支持，且相对费时。紧凑的过程实际上类似于windows系统中的磁盘整理程序，只不过后者是对外存空间的紧凑。
• 动态分区的分配策略

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

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

3.3、非连续分配管理方式

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

3.3.1、 分页存储

• 1）分页存储的几个基本概念
• • 1. 页面和页面大小。
       进程中的块称为页，内存中的块称为页框。外存也以同样单位划分，直接称为块。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。
       为了方便地址转换，页面大小应是2的整数幂。同时页面大小应当适中。如果页面太小，会是进程的页面数过多，这样页表就过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入换出的效率。页面过大又会是页面碎片过大，降低内存利用率。所以页面的大小应该适中，考虑到空间效率和时间效率。
• • 2. 地址结构。
       分页存储管理的地址结构包含两部分：前一部分为页号，后一部分为页内偏移量W。地址长度为32位，其中0~11为页内地址，即每页大小为4kB；12~31位为页号，地址空间最多允许有2^20页。
• • 3.页表。
    为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表一般存放在内存中。
    在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
• 2）基本地址变换机构
  地址变换机构的任务是将逻辑地址中的页号，转换为内存中物理块号，地址变换是借助于页表实现的。
  在系统中通常设置一个页表寄存器PTR，存放页表在内存的初值和页表长度。
  逻辑地址到物理地址的变换过程如下：

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

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

3.3.2 分段存储

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

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

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

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

3.3.3 各种地址的定义

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

虚拟内存

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

页面置换算法

• FIFO算法
  先入先出，即淘汰最早调入的页面。

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

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

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

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

FIFO会产生Belady异常。

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

image.png

• Clock：时钟替换算法（Clock）,
  给每个页帧关联一个使用位。当该页第一次装入内存或者被重新访问到时，将使用位置为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
  1.最近未被访问，未被修改(u=0,m=0)
  2.最近被访问，未被修改(u=1,m=0)
  3.最近未被访问，被修改(u=0,m=1)
  4.最近被访问，被修改(u=1,m=1)
  a.从指针当前位置开始扫描，不修改使用位，对找到的第一个(u=0,m=0)进行替换
  b.如果a失败，找到第一个（u=0,m=1）进行替换，扫描过程中，将使用位u置为0
  c,如果b失败，此时指针回到起始位置，且所有帧的使用位为0，重复步骤a,如果有必要，重复步骤b,直到找到为止

4. 文件管理

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

5. 输入输出系统

5.1、IO管理概述

• 1、IO设备
  IO设备管理是操作系统设计中最凌乱也最具挑战性的部分。由于它包含了很多领域的不同设备以及与设备相关的应用程序，因此很难有一个通用且一直的设计方案。所以在理解设备管理之前，应该先了解具体的IO设备类型。
  计算机系统中的IO设备按使用特性可以分为一下类型：
  1）人机交互类外部设备，又称慢速IO设备，用于桶计算机用户之间交互的设备，如打印机、显示器、鼠标、键盘等。这类设备数据交换速度相对较慢，通常是以字节为单位进行数据交换。
  2）存储设备，用于存储程序和数据的设备，如磁盘、磁带、光盘等。这类设备用于数据交换，速度较快，通常以多字节组成的块为单位进行数据交换。
  3）网络通信设备，用于与远程设备通信的设备，如各种网络接口、调制解调器等。其数据交换速度介于外部设备与存储设备之间。网络通信设备在使用和管理上与前两者设备有很大的不同。
  1）低速设备，传输速率仅为每秒钟几个字节至数百个字节的一类设备，如键盘、鼠标等。
  2）中速设备，传输速率在每秒数千个字节至数万个字节的一类设备，如行式打印机、激光打印机等。
  3）高速设备，传输速率在数百个千字节至千兆字节的一类设备，如磁带机、磁盘机、光盘机等。
  （2）按信息交换的单位分类
  1）块设备
  由于信息的存取总是以数据块为单位，所以存储信息的设备称为块设备。它属于有结构设备，如磁盘等。磁盘设备的基本特征是传输速率高，以及可寻址，即对他可随机地读写任意块。
  2）字符设备
  用于数据输入输出的设备为字符设备，因为其传输的基本单位是字符。它属于无结构类型，如交互式终端机、打印机等。他们的传输速率低、不可寻址、并且在输入输出时常采用中断驱动方式。
  对于IO设备，有以下三种不同类型的使用方式：
  独占式使用设备。独占式使用设备是指在申请设备是，如果设备空闲，就将其独占，不再允许其他进程申请使用，一直等到该设备被释放才允许其他进程申请使用。例如：打印机。
  分时式共享使用设备。独占式使用设备时，设备利用率低，当设备没有独占使用的要求时，可以通过分时共享使用，提高利用率。例如：对磁盘设备的IO操作，各进程每次IO操作请求可以通过分时来交替进行。
  以SPOOLing方式使用外部设备。SPOOLing技术是在批处理操作系统时代引入的，即假脱机IO技术。这种技术用于对设备的操作，实质上就是对IO操作进行批处理。具体的内容后面有单独讲解。
  采用上面三种使用方式的设备分别称为独占设备、共享设备和虚拟设备。
• 2、IO管理目标
  IO设备管理的主要目标有以下三个方面。
  方便使用：方便用户使用外部设备，控制设备工作完成用户的输入输出要求。
  提高效率：提高系统的并行工作能力，提高设备的使用效率。
  方便控制：提高外围设备和系统的可靠性和安全性，以使系统能正常工作。
• 3、IO管理功能
  IO设备管理的功能是按照输入输出子系统的结构和设备类型制定分配和使用设备的策略，主要包括：
  设备的分配和回收。
  外围设备的启动。
  对磁盘的驱动调度。
  外部设备中断处理。
  虚拟设备的实现。
• 4、IO应用接口
  IO应用接口就是从不同的输入输出设备中抽象出一些通用类型。每个类型都可以通过一组标准函数（即接口）来访问。具体的差别被内核模块（也称设备驱动程序）所封装。这些设备驱动程序一方面可以定制，以设和各种设备，另一方面也提供了一些标准接口。
  IO应用接口的具体实现方式是：先把IO设备划分为若干种类的通用类型；然后对每一种类型提供一组标准函数来访问，这里的标准函数就是接口；为每个IO设备提供各自的设备驱动程序，各种设备间的差异就体现在设备驱动程序的不同之中，而对于访问这些设备的接口却是按照该设备分数的类型而统一。
  划分IO设备所属的通用类型的依据：
  l 字符设备还是块设备。
  l 顺序访问还是随机访问。
  l IO传输是同步还是异步。
  l 共享设备还是独占设备。
  l 操作速度的高低。
  l 访问模式是读写、只读还是只写。
• 5、设备控制器（IO部件）
  IO设备通常包括一个机械部件和一个电子部件。为了达到设计的模块性和通用性，一般将其分开。电子部件成为设备控制器（或适配器），在个人计算机中，通常是一块插入主板扩充槽的印制电路板；机械部件即设备本身。
  由于具体的设备操作涉及硬件接口，且不同的设备有不同的硬件特性和参数，所以这些复杂的操作交由操作系统用户编写程序来操作是不实际的。引入控制器后，系统可以通过几个简单的参数完成对控制器的操作，而具体的硬件操作则由控制器调用相应的设备接口完成。设备控制器的引入大大简化了操作系统的设计，特别是有利于计算机系统和操作系统对各类控制器和设备的兼容；同时也实现了主存和设备之间的数据传输操作，使CPU从繁重的设备控制操作中解放出来。
  设备控制器通过寄存器与CPU通信，在某些计算机上，这些寄存器占用内存地址的一部分，称为内存映像IO；另一些计算机则采用IO专用地址，寄存器独立编址。操作系统通过想控制器寄存器写命令字来执行IO功能。控制器收到一条命令后，CPU可以转向进行其他工作，而让设备控制器自行完成具体IO操作。当命令执行完毕后，控制器发出一个中断信号，操作系统重新获得CPU的控制权并检查执行结果，此时，CPU仍旧是从控制器寄存器中读取信息来获得执行结果和设备的状态信息。
  设备控制器的主要功能为：
  l 接收和识别CPU或通道发来的命令，如磁盘控制器能就收读、写、查找、搜索等命令。
  l 实现数据交换，包括设备和控制器之间的数据传输；通过数据总线或通道，控制器和主存之间的数据传输。
  l 发现和记录设备及自身的状态信息，供CPU处理使用。
  l 设备地址识别。
  为实现上述功能，设备控制器必须包含以下组成部分：
  该接口有三类信号线：数据线、地址线和控制线。数据线通常与两类寄存器相连接：数据存储器（存放从设备送来的输入数据或从CPU送来的输出数据）和控制/状态寄存器（存放从CPU送来的控制信息或设备的状态信息）。
  设备控制器链接设备需要相应数量的接口，一个借口链接一台设备。每个接口中都存在数据、控制和状态三种类型的信号。
  用于实现对设备的控制。它通过一组控制线与处理器交互，对从处理器收到的IO命令进行译码。CPU启动设备时，将启动命令发送给控制器，并同时通过地址线吧地址发送给控制器，由控制器的IO逻辑对地址进行译码，并相应地对所选设备进行控制。
• 6、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核心子系统

• 1、IO层次结构
  IO实现普遍采用了层次式的结构。其基本思想与计算机网络中的层次结构相同：将系统IO的功能组织成一系列的层次，每一层完成整个系统功能的一个子集，其实现依赖于下层完成更原始的功能，并屏蔽这些功能的实现细节，从而为上层提供各种服务。
  一个比较合理的层次划分为四个层次的系统结构，各层次及其功能如下：
  1）用户层IO软件：实现与用户交互的接口，用户可直接调用在用户层提供的、与IO操作有关的库函数，对设备进行操作。
  2）设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护，以及设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
  3）设备驱动程序：与硬件直接相关，用于具体实现系统对设备发出的操作指令，驱动IO设备工作的驱动程序。
  4）中断处理程序：用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完并回复被中断进程的现场后，返回到被中断进程。
• 2、IO调度概念
  调度一组IO请求就是确定确定一个好的顺序来执行这些请求。应用程序所发布的系统调用的顺序不一定总是最佳选择，所以需要调度来改善系统整体性能，是进程之间公平的共享设备访问，减少IO完成所需要的平均等待时间。
  操作系统开发人员通过为每个设备维护一个请求队列来实现调度。当一个应用程序执行阻塞IO系统调用时，该请求就加到相应设备的队列上。IO调度会重新安排队列顺序以改善系统总体效率和应用程序的平均响应时间。
  IO子系统还可以使用主存或磁盘上的存储空间的技术，如缓冲、高速缓冲、假脱机等。
• 3、高速缓存与缓冲区
  操作系统总是用磁盘高速缓存技术来提高磁盘的IO速度，对高速缓存复制的访问要比原始数据访问更为高效。例如，正在运行的进程的指令即存储在磁盘上，也存储在物理内存上，也被复制到CPU的二级和一级高速缓存中。
  不过，磁盘高速缓存技术不同于通常意义下的介于CPU与内存之间的小容量高速存储器，而是利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息，因此，磁盘高速缓存在逻辑上属于磁盘，物理上则是驻留在内存中的盘块。
  高速缓存在内存中分为两种形式：一种是在内存中开辟一个单独的存储空间作为磁盘高速缓存，大小固定；另一种是把未利用的内存空间作为一个缓冲池，共请求分页系统和磁盘IO时共享。
  在设备管理子系统中，引入缓冲区的目的有：
  1）缓和CPU与IO 设备间速度不匹配的矛盾。
  2）减少对CPU的中断频率，放宽对CPU 中断响应时间的限制。
  3）解决基本数据单元大小不匹配的问题。
  4）提高CPU和IO设备之间的并行性。
  其实现方法有：
  1）采用硬件缓冲器，但由于成本太高，出一些关键部位外，一般情况下不采用硬件缓冲器。
  2）采用缓冲区（位于内存区域）
  根据系统设置缓冲器的个数，缓冲技术可以分为：
  1）单缓冲。在设备和处理器之间设置一个缓冲区。设备和处理器交换数据时，先把被交换数据写入缓冲区，然后把需要数据的设备或处理器从缓冲区取走数据。
  在块设备输入时，假定从磁盘把一块数据输入到缓冲区的时间为T，操作系统将该缓冲区中的数据局传送到用户区的时间为M，而CPU对这一块数据处理的时间为C。由于T和C是可以并行的，所以可把系统对每一块数据的处理时间表示为Max（C,T）+M。
  2）双缓冲。双缓冲区机制又称缓冲对换。IO设备输入数据时先输入到缓冲区1，直到缓冲区1满后才输入到缓冲区2，此时操作系统可以从缓冲区1中取出数据放入用户进程，并由CPU计算。双缓冲的使用提高了处理器和输入设备的并行操作的程度。
  系统处理一块数据的时间可以粗略地认为是Max（C,T）。如果CT，则可使CPU不必等待设备输入。对于字符设备，若采用行输入方式，则采用双缓冲可使用户再输入完第一行之后，在CPU执行第一行中的命令的同事，用户可继续向第二缓冲区输入下一行数据。而单缓冲情况下则必须等待一行数据被提取完毕才可输入下一行的数据。
  如果两台机器之间通信仅配置了单缓冲，那么，他们在任意时刻都只能实现单方向的数据传输。为了实现双向数据传输，必须在两台机器中都设置两个缓冲区，一个用作发送缓冲区，另一个用作接收缓冲区。
  3）循环缓冲：包含多个大小相等的缓冲区，每个缓冲区中有一个缓冲区，最后一个缓冲区指针指向第一个缓冲区，多个缓冲区构成一个环形。用于输入输出时，还需要有两个指针in和out。对输入而言，首先要从设备接收数据到缓冲区中，in指针指向可以输入数据的第一个空缓冲区；当运行进程需要数据时，从循环缓冲去中去一个装满数据的缓冲区，并从此缓冲区中提取数据，out指针指向可以提取数据的第一个满缓冲区。输出正好相反。
  4）缓冲池：由多个系统共用的缓冲区组成，缓冲区按其使用状况可以形成三个队列：空缓冲队列、装满输入数据的缓冲队列（输入队列）和装满输出数据的缓冲队列（输出队列）。还应具有四种缓冲区：用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区、用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区。
  （4）高速缓存与缓冲区的对比
  高速缓存是可以保存复制数据的高速存储器。访问高速缓存比访问原始数据更高效，速度更快。
• 4、设备的分配与回收
  设备分配的基本任务是根据用户的IO请求，为他们分配所需的设备。设备分配的总原则是充分发挥设备的使用效率，尽可能地让设备忙碌，又要避免由于不合理的分配方法造成进程死锁。从设备的特性来看，可以把设备分成独占设备、共享设备和虚拟设备三类。
  对于独立设备，讲一个设备分配给某进程后，便有改进成都站，直至该进程完成或释放该设备。对于共享设备，可以同时分配给多个进程使用，但需要对这些进程访问该设备的先后次序进程合理的调度。虚拟设备属于可共享设备，可以将它同时分配给多个进程使用。
  设备分配依据的主要数据结构有设备控制表（DCT）、控制器控制表（COCT）、通道控制表（CHCT）和系统设备表（SDT），各数据结构功能如下：
  设备控制表：系统为每一个设备配置一张DCT，它用于记录设备的特性以及与IO控制器连接的情况。DCT包括设备标示符、设备类型、设备状态、指向COUCT的指针等。其中，设备队列指针指向等待使用该设备的进程组成的等待队列，控制表指针指向于该设备相连接的设备控制器。
  控制器控制表：每个控制器都配有一张COCT，它反应设备控制器的使用状态以及和通道的连接情况等。
  通道控制表：每个通道配有一张CHCT。
  系统设备表：整个系统只有一张SDT，它记录已连接到系统中的所有物理设备的情况，每个物理设备占一个表目。
  由于在多道程序系统中，进程数多于资源数，会引起资源的竞争。因此，要有一套合理的分配原则，主要考虑的因素有：IO设备的固有属性，IO设备的分配算法，设备分配的安全性，以及设备独立性。
  1）设备分配原则。设备的分配原则应根据设备特性、用户要求和系统配置的情况来决定。设备分配的总原则既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开。
  2）设备分配方式。设备分配方式有静态分配和动态分配两种。
  静态分配主要用于对独占设备的分配，它在用户作业开始执行前，有系统一次性分配该作业所要求的全部设备、控制器（和通道）。一旦分配后，这些设备、控制器（和通道）就一直为高作业所占用，知道该作业被撤销。静态分配方式不会出现死锁，但设备的使用效率较低。因此，静态分配方式并不符合分配的总原则。
  动态分配是在进程执行过程中根据执行需要进行。当进程需要设备时，通过系统调用命令向系统提出设备请求，由系统按照事先规定的策略给进程分配所需要的设备、IO控制器，一旦用完之后，便立即释放。动态分配方式有利于提高设备的利用率，但如果分配算法使用不当，则有可能造成进程死锁。
  3）设备分配算法。常用的动态设备分配算法有先请求先分配、优先级高者优先等。
  对于独占设备，即可以采用动态分配方式也可以静态分配方式，往往采用静态分配方式，即在作业执行前，将作业所要用到的这一类设备分配给它。共享设备可被多个进程所共享，一般采用动态分配方式，但在每个IO传输的单位时间内只被一个进程所占有，通常采用先请求先分配和优先级高者先分的分配算法。
  设备分配的安全性是指设备分配中应防止发生进程死锁。
  1）安全分配方式。每当进程发出IO请求后便进入阻塞状态，直到其IO操作完成时才被唤醒。这样，一旦进程已经获得某种设备后便阻塞，不嫩再请求任何资源，而且在它阻塞时也不保持任何资源。有点事设备分配安全；缺点是CPU和IO设备是串行工作的。
  2）不安全分配方式。进程在发出IO请求后继续运行，需要时发出第二个、第三个IO请求等。仅当进程所请求的设备已被另一进程占用时，才进入阻塞状态。有点事一个进程可以同时操作几个设备，从而市金城推进迅速；缺点是这种设备分配有可能产生死锁。
  为了提高设备分配的灵活性和设备的利用率、方便实现IO重定向，因此引入了设备独立性。设备独立性是指应用程序独立于具体使用的物理设备。
  为了实现设备独立性，在应用程序中使用逻辑设备名来请求使用某类设备，在系统中设置一张逻辑设备表（LUT），用于将逻辑设备名映射为物理设备名。LUT表项包括逻辑设备名、物理设备名和设备驱动程序入口地址；当进程用逻辑设备名来请求分配设备时，系统为他分配相应的物理设备，并在LUT中建立一个表项，以后进程再利用逻辑设备名请求IO操作时，系统通过查找LUT来寻找相应的物理设备和驱动程序。
  在系统中可采取两种方式建立逻辑设备表：
  1）在整个系统中只设置一张LUT表。这样，所有进程的设备分配情况都记录在这张表中，故不允许有相同的逻辑设备名，主要适用于单用户系统中。
  2）为每个用户设置一张LUT。当用户登录时，系统便为用户建立一个进程，同时也位置建立一张LUT，并肩改变放入进程的PCB中。
• 5、SPOOLing（假脱机技术）
  为了缓和CPU的高速型与IO设备低速性之间的矛盾而引入了脱机输入、脱机输出技术。该技术是利用专门的外围控制机，将低速IO设备上的数据传送到高速磁盘上；或者相反。SPOOLing的意思是外部设备同时联机操作，又称为假脱机输入输出操作，是操作系统中采用的一项将独占设备改造成共享设备的技术。
  再次攀上开辟出的两个存储区域。输入井模拟脱机输入时的磁盘，用于收容IO设备输入的数据。输出井模拟脱机输出的磁盘，用于收容用户程序的输出数据。
  在内存中开辟的两个缓冲区。出入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用于暂存从输出井送来的数据，以后再传送到输出设备。
  输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井。当CPU需要输入数据时，直接将数据从输入井读入内存。输入进程模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备。
  共享打印机是使用SPOOLing技术的一个实例，这项技术已被广泛的用于多用户系统和局域网络中。当用户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为她做两件事：
  1）由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中。
  2）输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列中。
  SPOOLing系统的特点是：提高了IO速度；将独占设备改造为共享设备；实现了虚拟设备功能。
• 6、出错处理
  操作系统可以采用内存保护，这样一来就可以预防许多 硬件和应用程序的错误，即便有一些设备硬件上的适龄也不回导致系统的完全崩溃。
  IO设备传输中出现的错误很多，如网络上的堵塞和传输过载等。操作系统可以对一些短暂的出错进行处理，比如读取磁盘出错，那么可以选择重新常识对磁盘进行read操作；再比如在网络上发送数据出错，那么只要网络通信协议允许，就可以做resend操作。但是，如果计算机系统中的重要组件出现了永久性错误，那么操作系统将无法恢复。
  作为一个规则，IO系统调用通常返回一位调用状态信息，以表示成功或失败。在UNIX系统中，用一个名为errno的全局变量来表示出错代码，以表示出错原因。
  注意：read、send和resend都是操作系统的基本输入输出命令，分别用来读、发送和重发数据。

5.3、本章疑难点

1）分配设备。首先根据IO请求中的物理设备名查找系统设备表（SDT），从中找出该设备的DCT，再根据DCT中的设备状态字段，可知该设备是否正忙。若忙，便将请求IO进程的PCB挂在设备队列上；空闲则按照一定算法计算设备分配的安全性，安全则将设备分配给请求进程，否则仍将其PCB挂到设备队列。
2）分配控制器。系统把设备分配给请求IO的进程后，再到其DCT中找出与该设备连接的控制器的COCT，从COCT中的状态字段中可知该控制器是否忙碌。若忙，便将请求IO进程的PCB挂在该控制器的等待队列上；空闲便将控制器分配给进程。
3）分配通道。在该COCT中又可找到与该控制器连接的通道CHCT，再根据CHCT内的状态信息，可知该通道是否忙碌。若忙，便将请求IO的进程挂在该通道的等待队列上；空闲便将该通道分配给进程。只有在上述三者都分配成功时，这次设备分配才算成功。然后，便可启动该IO设备进行数据传送。
为使独占设备的分配具有更强的灵活性，提高分配的成功率，还可以从以下两方面对基本的设备分配程序加以改进：
1）增加设备的独立性。进程使用逻辑设备名请求IO。这样，系统首先从SDT中找出第一个该类设备的DCT。若该设备忙，又查找出第二个该设备的DCT。仅当所有该类设备都忙时，才把进程挂在该类设备的等待队列上；只要有一个该类设备可用，系统便进一步计算分配该设备的安全性。
2）考虑多通路情况。为防止IO系统的“瓶颈”现象，通常采用多通路的IO系统结构。此时对控制器和通道的分配同样要经过几次反复，即若设备（控制器）所连接的第一个控制器（通道）忙时，应查看其所连接的第二个控制器（通道），仅当所有的控制器（通道）都忙时，此次的控制器（通道）分配才算失败，才把进程挂在控制器（通道）的等待队列上。而只要有一个控制器（通道）可用，系统便可将它分配给进程。

6. 常见考点

6.1 进程的平均周转时间

有4个进程A,B,C,D,设它们依次进入就绪队列，因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位，设时间片为1。四个进程的平均周转时间为 （）？

结果：详细如图 （7+14+20+24）/4=16.25

进程的堆栈、数据区、代码区在内存的映射

栈 存放局部变量 传递参数 存储函数的返回地址
堆 malloc 和new进行分配时 所得的地址就在堆中 程序员负责申请和销毁
数据区 全局、静态、常量是分配到数据区中的 数据区包括bbs 未初始化数据区 初始化数据区
堆向高内存地址生长 栈向高内存地址生长 两者相向而生

C语言中堆和栈的区别

一.前言：

C语言程序经过编译连接后形成编译、连接后形成的二进制映像文件由栈，堆，数据段（由三部分部分组成：只读数据段，已经初始化读写数据段，未初始化数据段即BBS）和代码段(文本常量区)组成，如下图所示：

image.png

1.栈区(stack):由编译器自动分配释放，存放函数的参数值，局部变量等值。其操作方式类似于数据结构中的栈。

2.堆区(heap):一般由程序员分配释放，若程序员不释放，则可能会引起内存泄漏。注堆和数据结构中的堆栈不一样，其类是与链表。

3.程序代码区：存放函数体的二进制代码。

4.数据段：由三部分组成：

1>只读数据段：

只读数据段是程序使用的一些不会被更改的数据，使用这些数据的方式类似查表式的操作，由于这些变量不需要更改，因此只需要放置在只读存储器中即可。一般是const修饰的变量以及程序中使用的文字常量一般会存放在只读数据段中。

2>已初始化的读写数据段：

已初始化数据是在程序中声明，并且具有初值的变量，这些变量需要占用存储器的空间，在程序执行时它们需要位于可读写的内存区域内，并且有初值，以供程序运行时读写。在程序中一般为已经初始化的全局变量，已经初始化的静态局部变量(static修饰的已经初始化的变量)

3>未初始化段（BSS）：

未初始化数据是在程序中声明，但是没有初始化的变量，这些变量在程序运行之前不需要占用存储器的空间。与读写数据段类似，它也属于静态数据区。但是该段中数据没有经过初始化。未初始化数据段只有在运行的初始化阶段才会产生，因此它的大小不会影响目标文件的大小。在程序中一般是没有初始化的全局变量和没有初始化的静态局部变量。

二.堆和栈的区别

1.申请方式

(1)栈（satck）:由系统自动分配。例如，声明在函数中一个局部变量int b;系统自动在栈中为b开辟空间。

(2)堆（heap）:需程序员自己申请（调用malloc,realloc,calloc）,并指明大小，并由程序员进行释放。容易产生memory leak.

eg:char p;

  p = (char *)malloc(sizeof(char));

但是，p本身是在栈中。

2.申请大小的限制

（1）栈：在windows下栈是向底地址扩展的数据结构，是一块连续的内存区域(它的生长方向与内存的生长方向相反)。栈的大小是固定的。如果申请的空间超过栈的剩余空间时，将提示overflow。

（2）堆：堆是高地址扩展的数据结构（它的生长方向与内存的生长方向相同），是不连续的内存区域。这是由于系统使用链表来存储空闲内存地址的，自然是不连续的，而链表的遍历方向是由底地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。

3.系统响应：

（1）栈：只要栈的空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

（2）堆：首先应该知道操作系统有一个记录空闲内存地址的链表，但系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的free语句才能正确的释放本内存空间。另外，找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。

说明：对于堆来讲，对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，

4.申请效率

（1）栈由系统自动分配，速度快。但程序员是无法控制的

（2）堆是由malloc分配的内存，一般速度比较慢，而且容易产生碎片，不过用起来最方便。

5.堆和栈中的存储内容

（1）栈：在函数调用时，第一个进栈的主函数中后的下一条语句的地址，然后是函数的各个参数，参数是从右往左入栈的，然后是函数中的局部变量。注：静态变量是不入栈的。

当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续执行。

（2）堆：一般是在堆的头部用一个字节存放堆的大小。

6.存取效率

（1）堆：char *s1=”hellow tigerjibo”;是在编译是就确定的

（2）栈：char s1[]=”hellow tigerjibo”;是在运行时赋值的；用数组比用指针速度更快一些，指针在底层汇编中需要用edx寄存器中转一下，而数组在栈上读取。

补充：

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。

7.分配方式：

（1）堆都是动态分配的，没有静态分配的堆。

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

image.png

//main.cpp 
int a = 0; 全局初始化区 
char *p1; 全局未初始化区 
int main() 
{ 
int b; 栈 
char s[] = "abc"; 栈 
char *p2; 栈 
char *p3 = "123456"; 123456在常量区，p3在栈上。 
static int c =0； 全局（静态）初始化区 
p1 = (char *)malloc(10); 
p2 = (char *)malloc(20); 
分配得来得10和20字节的区域就在堆区。 
strcpy(p1, "123456"); 123456放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。 
}

死锁

所谓死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

（1）因为系统资源不足。（2）进程运行推进的顺序不合适。（3）资源分配不当等。如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。（1）互斥条件：一个资源每次只能被一个进程使用。（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。（4）循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

进程状态

image.png