操作系统概念（黑皮书）阅读笔记

操作系统概念（黑皮书）阅读笔记

进程和内存管理部分章节

• 导论：

  • 操作系统类似于政府，其本身不能实现任何有用功能，而是提供一个方便其他程序执行有用工作的环境

    ​ 个人理解：os是government的作用，有着最高权限，去管理和分配资源，有效且公平

  • 计算机系统的根本目的是，执行用户程序并更容易解决用户程序。控制和分配I/O设备资源的共同功能被组成一个软件模块：os

  • os是一直运行在计算机上的程序（内核）

  • 除内核外，还有两类程序：

    1. 系统程序：与系统运行有关，但不是内核的一部分

    2. 应用程序：与系统运行无关的其他程序

       个人理解：系统程序是编译器、链接器那种性质的，但不是os；应用程序就是除开系统程序和os

  • os的运行：

    • 计算机开机后，先加载位于只读内存ROM上的引导程序，在通过引导程序去定位os内核并加载到内存，一旦内核加载到内存并执行，它就开始为系统和用户提供服务，除了内核，系统程序也提供了一些服务，他们在启动时加载到内存成为系统后台程序。一旦这个阶段完成，系统就完全启动了，等待事件发生
    • 事件发生通常硬件或软件的中断来通知。
      • 硬件通过系统总线发送信号到CPU，来触发中断
      • 软件可通过执行系统调用，来触发中断

  • CPU被中断时，它停止正在做的是事情，立即转到固定位置（中断服务程序的开始地址），执行该中断服务程序结束，再去重新执行中断的计算

  • 存储结构：

    • 内存，也称随机访问内存（Random Access Memory， RAM），通常为动态随机访问内存（DRAM）

      ​ 个人理解：内存中的数据就是随机分布并不连续，所以是随机访问

    • 只读内存（Read Only Memory， ROM），数据不可修改

    • 内存特点：易丢失，掉电丢失数据。但是ROM不是这样，ROM已经固化在内存上了

    • 外存，数据持久化

  • I/O结构：

    • 每个设备控制器管理一系列特定类型的设备
    • os为每个设备控制器提供了设备驱动程序

  • os是中断驱动的，事件是由中断或陷阱（或异常）引起的

    • 陷阱（或异常）是一种软件生成的中断，或源于出错，或源于用户程序的特定请求

  • 双重模式与多重模式的执行：

    • 为确保os的正确运行，必须区分操作系统代码和用户代码的执行
    • 用户模式和内核模式：
      • 计算机硬件可以通过模式位（mode bit）来表示当前模式：内核模式（0）和用户模式（1）
      • os执行用户应用时，系统处于用户模式，当用户通过系统调用，请求操作系统服务时，系统必须从用户模式切换为内核模式

  • 进程管理：

    • 执行中的程序称为进程
    • 程序本身不是进程，程序是被动实体，进程是主动实体
    • 进程是系统的工资单元。系统由多个进程组成，其中有操作系统进程和用户进程。所有进程并发执行。

  • 内存管理：

    • 内存是以一个大的字节数组
    • 如果CPU需要执行指令，那么这些数据必须首先通过CPU的IO调度从硬盘传到内存
    • 为了改进CPU的利用率和用户的计算机响应速度。计算机在内存中保留了多个程序，这就需要内存管理

  • 存储管理：

    • 操作系统对存储设备的物理属性进行了抽象，并定义了逻辑单元，即文件（ File）。os映射文件到物理媒介，并通过存储设备来访问文件

• 操作系统结构：

  • 用户与os的界面：命令解释程序和图形用户界面（GUI）

    • 有的os内核就包括命令解释程序。解释程序称为Shell（外壳），将用户输入的命令转换为机器指令
    • GUI消耗资源更多，系统更复杂，bug也更多

  • 系统调用提供os服务接口.这些API通常以c 、 cpp 、汇编写的

    • 开发人员根据API来设计程序
    • 系统调用大致分为六大类：
      • 进程控制、文件管理、设备管理、信息维护、通信、保护

  • 随着内核功能越来越多，内核变得更大和难以管理，采用微内核技术对内核进行模块化，即从内核中删除所有不必要的部件，将他们当作系统级与应用级的程序来实现，使得内核变小

  • 微内核的主要功能是为客户端程序和运行在用户空间的各种服务提供通信，通信是通过消息传递来提供的

  • 优点：便于拓展os，更安全，便于移植

  • 缺点：增加系统功能的开销，微内核性能受损

  • 个人理解：把很多原来在内核态运行的服务放出去了，导致调用时频繁切换状态

• 进程

  • 现代os允许加载多个程序到内存，以便并发执行。这些需求导致进程这个概念的产生，进程即为执行中的程序

  • 程序本身不是进程。程序是被动实体。如存储在磁盘上的包含一系列指令的文件（可执行文件）

  • 而进程是活动实体。当一个可执行文件被加载到内存时，这个程序就成为进程

  • 进程是执行中的程序实体（这话不一定准确）

  • 进程是os进行资源分配和调度的基本单位

  • os中的每个进程采用进程控制块（Process Control Block， PCB）表示

    • PCB保存一系列信息，进程状态、进程编号、pc、寄存器、内存界限、打开文件列表。。。。。
    • PCB存在一个双向链表中
    • 进程的上下文采用进程PCB表示

  • 分时系统的目的是在进程之间快速切换CPU，以便用户在程序运行时能与其交互

  • 进程在进入系统时，会被加入作业队列（job queue）

  • 驻留在内存中的，就绪的，等待运行的进程保存在就绪队列上，这个列表，通常用链表实现

  • 等待特定IO设备的进程列表，称为设备列表

  • 上下文切换的时间是纯粹的开销，在这个过程中，CPU没有做任何有用的工作

  • 大多数OS对进程的识别采用唯一的进程标识符（process identifier ，pid），通常是一个整数值。

  • 通过pid可以访问内核中的进程的各种属性

  • 进程间通信：

    1. Soket
       • Socket为通信的端点。通过网络通信的每对进程需要一对Socket，即每个进程各一个Socker
       • 每个Socket由 ip 和端口组成
       • 使用Socket通信，常用且高效，属于是分布式进程之间的一种低级形式的通信。因为通信进程之间交换的是无结构的字节流，客户端和服务器程序需要自己加上数据结构
    2. RPC
    3. 管道

• 多线程编程：

  • 每个线程是CPU使用的一个基本单元

  • 线程包括线程ID，pc，寄存器组和堆栈。它与同一进程的其他线程共享代码段、数据段和os其他资源

  • 一个进程一般具有多个线程，那么进程能同时执行多个任务

  • 一个进程为什么要创建多个线程？

    1. OS创建多个进程比一个进程中创建多个线程开销大
    2. 进程间通信比线程间通信更复杂

  • 优点：

  • 响应性：如果一个交互程序采用多线程，那么即使部分阻塞或执行冗余操作，它仍然可以继续执行，从而增加对用户的响应速度

  • 资源共享：进程只能通过共享内存和消息传递之类的技术共享资源。而线程默认共享它们所属进程的内存和资源

  • 经济：进程创建所需的内存和资源分配非常昂贵

  • 可伸缩性：对于多处理器体系结构，多线程的优点更大，因为线程可在多处理器核上并行运行

  • 多线程模型：

    • 用户线程：位于内核之上，它的管理无需内核支持
    • 内核线程：由OS来直接支持与管理

• 进程调度：

  • 调度程序是一个模块，用来将CPU控制权交给由短期调度程序选择的进程。

    • 功能包括：
      • 切换上下文
      • 切换到用户模式
      • 跳转到用户模式的合适位置，以便重启程序

  • 不同的调度算法具有不同的特点

  • 最简单的CPU调度算法是先到先服务（First - Come First - Served, FCFS）调度算法。先请求CPU的进程首先分配到CPU，通过FIFO队列简单实现

    • FCFS调度算法是非抢占的

    • 优点：实现简单

    • 缺点：平均等待时间往往很长

  • 最短作业优先（Shortest - Job - First， SJF）调度算法将每个进程与其下次CPU执行的长度关联起来。当CPU空闲时，它会被赋给具有最短CPU执行的进程

  • SJF算法是最优的，因为平均等待时间最小（CPU更忙碌）

  • SJF调度经常用于长期调度。对于批处理系统的长期调度，可以将用户提交作业指定的进程时限作为长度

  • SJF算法不能在短期CPU调度上加以实现，没法知道下次CPU执行的长度

  • FCFS调度算法是非抢占的或抢占式

  • 优先级调度算法

    • 优先级调度算法是非抢占的或抢占式
    • 它的主要问题是无穷阻塞或饥饿问题
    • 饥饿的解决方案之一是老化，就是说逐渐增加等待很长时间的优先级

  • 轮转（Round - Robin）调度算法专门为分时系统设计

    • 将一个时间单元（10ms ~ 100ms）定义为时间片。就绪队列作为循环队列，为每一个进程分配不超过一个时间片的CPU执行
    • 时间片一到，就会中断OS，进行上下文切换
    • RR调度的平均等待时间通常较长

  • 多级队列调度算法将就绪队列分成多个单独队列

    • 根据进程属性，如内存大小，进程优先级，进程类型等，一个进程永久分到一个队列。每个队列有自己的调度算法
    • 每个队列与更低层队列相比有绝对的优先
    • 缺点：可能存在饥饿问题
    • 允许进程在队列之间迁移

  • 之前讨论的是单处理器的调度问题，如果多个CPU，则负载均衡成为可能，但调度就更复杂

  • 多处理器调度：

    • 非对称多处理：
      • 让一个CPU去处理所有调度决定、IO处理以及其他系统活动，其他CPU只执行用户代码
      • 这样，因为只有一个CPU访问系统数据结构，减少了数据共享的需要
    • 多对称处理（SMP）：
      • 每个CPU关系平等
      • 对SMP来说负载平衡很重要

  • 处理器亲和力：

    • 大多数OS避免将一个进程从一个cpu移到另一个cpu，而是试图让它始终运行在一个cpu上
    • 即一个进程对它运行的处理器具有亲和力
    • 个人理解：迁移进程，那么在原先CPU缓存中的数据还要删除和迁移，麻烦耗资源，所以要避免

  • 负载平衡：

    • 分为推迁移和拉迁移
    • 这两个迁移就是方向不一样，高负载CPU到低负载CPU就是推，反之就是拉
    • 在负载平衡中二者是并行实现

  • 实时CPU调度：

    • 软实时
    • 硬实时

  • 延迟：

    • 中断延迟
    • 调度延迟

  • 用于实时OS的调度程序应支持抢占的、基于优先级的算法

• 同步：

  • 每个进程在执行一段代码可能修改公共变量，那这段代码称为临界区

    • 不能有两个进程在它们的临界区共同执行

  • 硬件同步：

    • 基于加锁为前提，通过锁来保护临界区。通过硬件指令来解决临界区问题

  • 软件同步：

    • 最简单的是使用互斥锁，防止竞争条件

      • 一个进程在进入临界区的时候得到锁，退出临界区的时候释放锁
      • 忙等待：当一个进程在临界区中，任何其他进程在进入临界区必须不断循环判断。这种互斥锁也叫自旋锁，进程不断旋转，等待锁变得可用
      • 忙等待浪费CPU周期，优点是没有切换上下文

    • 信号量：

      • 一个信号量S是一个整形变量。它除了初始化只能通过两个标准原子操作：wait（）和signal（）来访问

      • wait（）最初称为P原语（测试）减一

      • siganl（）最初称为V原语（增加）加一

      • OS通常区分技术信号量与二进制信号量

      • 二进制信号量类似于互斥锁

      • 计数信号量可以用于控制访问具有多个实例的某种资源。信号量的初始值为可用资源数

      • 当进程需要使用资源时，对信号量执行wait（）操作

      • 进程释放资源时，再对信号量执行signal（）操作

      • 多个进程无限等待一个事件，而该事件只能由这些等待进程之一来产生。这种状态称为死锁

      • 内核数据通常是用锁保护的，较高优先级的进程不得不等待较低优先级的进程用完资源

      • 经典同步问题：

        1. 有界缓存问题：
        2. 哲学家就餐:

• 死锁：

  • 如果所申请的资源被其他进程占有，那么该等待等待进程有可能再也无法改变状态。这种情况称为死锁
  • 多进程对共享资源的竞争可能导致死锁
  • 系统中可能产生死锁的四个条件：
    • 互斥：这个资源一次只能被一个进程使用
    • 占有并等待：一个进程占有至少一个资源，并等待另一个资 源 ，而该资源被其它进程所占有
    • 非抢占：资源不能被抢占，只能自己资源释放
    • 循环等待
  • 死锁恢复：
    • 中止一个或多个进程来打破循环等待
    • 从一个或多个死锁进程那里抢占一个或多个资源

• 内存管理：

  • 内存由一个很大的字节数组来组成，每个字节都有各自的地址（即内存地址）

  • CPU根据PC的值从内存中提取指令，这些指令可能引起对特定内存地址的额外加载与存储

  • 首先需要确保每个进程都有一个单独的内存空间，单独的空间才能保障不互相影响。

  • 需要确定一个进程可以访问的合法地址的范围，且确保该进程只能访问这个合法地址

  • 通过两个寄存器，通常为基地址和界限地址。

    • 基地址寄存器保存的时最小的合法的物理内存地址。
    • 界限寄存器保存的是范围的大小，也就是偏移量

  • 内存空间保护的实现是通过CPU硬件对在用户模式下产生的地址与寄存器的保存的地址比较来完成的

  • 大多数系统允许用户进程放在物理内存中的任意位置

  • 源程序中的地址通常是用符号表示

  • 编译器将这些符号地址绑定到可重定位的地址（如：“从本模块开始的第14字节”）

  • 链接程序或加载程序再将这些可重定位的地址绑定到绝对地址（如324312）

  • 每次绑定都是从一个地址空间到另一个地址空间的映射

  • 指令和数据绑定到存储器地址可在沿途的任何一步中进行

  • 逻辑地址：CPU生成的地址称为逻辑地址

    • 个人理解：代码加载运行时的变量的地址
    • 本书中，逻辑地址和虚拟地址

  • 虚拟地址到虚拟地址的映射是由MMU内存管理单元

  • 不连续内存分配：

    • 分段：

      • 根据段号去段表查询界限位置和基地址

    • 分页：

      • 避免了外部碎片
      • 分页就是将内存分成固定大小的块
      • 根据页码去页表查询基地址和偏移量，有TCL就先查TCL（缓存）
      • 分页优点之一是可以共享内存。多个分页可以指向同一块内存地址

• 虚拟内存管理：

  • 虚拟内存将用户逻辑内存与物理内存分开

  • 虚拟内存允许执行进程不必完全处于内存

  • 允许进程轻松实现共享文件和内存

  • LRU算法（Least - Recent - Used）最近最少使用