操作系统1 shuitang

概述

An operating system is a program that acts as an interface between the user and the computer hardware and controls the execution of all kinds of programs.

操作系统是什么?

  • 实际上是一个程序,在用户接触硬件资源的过程中扮演了一个接口的角色并且控制了程序的执行过程(实际上就是对CPU资源的控制),总结来说操作系统就是对计算机各种资源进行统一管理的程序。
  • 管理的方面包括:
    • 内存管理(管理对内存(主存)资源的使用)
    • 处理器管理(管理对CPU资源的使用,特别是多处理的系统中)
    • 设备管理(管理对各种外部设备的使用:I/O,键盘,声卡,网卡等等,通过驱动(drivers)来管理)
    • 文件管理(对信息存储和获取的方式的管理)
      • 文件系统通过组织成目录:为了方便导航和使用。
        • 跟踪信息,定位,使用,状态等等,这些构成的整体成为文件系统;
    • 其他功能:
      • 安全性管理(访问权限资源的管理)
      • 控制系统性能:
        • 记录服务请求和系统响应之间的延迟
      • 作业统计:
        • 跟踪各种作业和用户使用的时间和资源
      • 错误检查工具

硬件资源

什么是硬件资源?

即物理实实在在存在的资源,比如声卡、网卡、显卡、键盘的输入、物理磁盘、CPU资源等等。

举例:显卡资源的利用,显示图像啊;网卡:接受和发送来自/去往网络的信息,磁盘资源存储信息。

如今的计算机架构

冯诺依曼体系架构

  • 也称存储程序型电脑。把指令当成一种特别类型的静态数据,一台存储型电脑可轻易改变其程序,并在程序下改变其运算内容。
  • 把 CPU 与存储器分来,CPU 根据指令的不同来负责四种基本动作:
    • 处理器-存储器之间传送数据
    • 处理器-I/O 之间传送数据
    • 数据处理:执行很多与数据相关的算术操作和逻辑操作
    • 控制:跳转,影响下一次取值的地址(PC 的值)

计算机主要有 4 个结构化部件:

  • 处理器(Processor):运算器和控制器。
  • 内存(Main memory)
  • 输入/输出模块(I/O)
  • 系统总线(System bus):

    • 系统总线系统总线(英语:System Bus)是一个单独的电脑总线,是连接电脑系统的主要组件。这个技术的开发是用来降低成本和促进模块化。系统总线结合数据总线的功能来搭载信息,地址总线来决定将信息送往何处,控制总线来决定如何动作。虽然系统总线于1970年代至1980年代广受欢迎,但是现代的电脑却使用不同的分离总线来做更多特定需求用途。

    • 1)总线周期:总线上两个部件完成一次完整且可靠的数据传输时间; 2)总线周期分为四个阶段:

      • 申请分配阶段:申请总线
      • 寻址阶段:发出地址及有关命令
      • 传数阶段:进行数据交换
      • 结束:从总线上撤除信号,让出总线

模块化视图如下:

处理器的一种功能就是与存储器交换数据。使用两个内部(对处理器而言)寄存器:存储器地址寄存器:明确下一次读/写的存储器地址;存储器缓冲寄存器:存放要写入存储器的数据或从存储器读取数据。同理,还有指定特定的输入/输出设备的缓冲寄存器,用于在输入/输出模块和处理器间交换数据。

image-20200813095615509

中断:

中断是指:计算机提供的允许其他模块(I/O、寄存器)中断处理器正常处理过程的机制。即其他模块发送一个请求给处理器,处理器暂停当前任务的过程。中断不是程序调用过程中的一个例程,它可以在任何时候发生,因而可以在用户执行过程中任何一点发生,不可预测。

中断的简单分类:

image-20200813102042705

引入中断程序的指令周期

image-20200813102404636

存储器的层次结构

局部性原理:

  • 时间局部性:同一个数据,在一段时间内,可能会被多次访问。
  • 空间局部性:如果某个数据被访问,那么与它相邻的数据项很可能也将被访问。

高速缓存

在处理器和内存之间提供一个容量很小但速度很快的存储器,称之为高速缓存。

直接内存存取 DMA

执行 I/O 操作的技术有三种:可编程 I/O、中断驱动 I/O 和直接内存存取(DMA)。

  • 可编程 I/O
    • 处理器执行程序时遇到一个 I/O 相关的指令时,它会通过相应的 I/O 模块发送命令来执行这个命令。使用可编程I/O操作时,I/O 模块执行请求的动作并设置 I/O 状态寄存器中的相应的位,但它并不会进一步通知处理器,尤其不会中断处理器。因此处理器需要在执行 I/O 指令后,还要定期检查 I/O 模块的状态,以确定 I/O 操作是否完成。
  • 中断驱动 I/O
    • 处理器给 I/O 模块发送 I/O 命令,然后处理器继续做其他一些有用的工作。当 I/O 模块准备好与处理器交换数据时,它将打断处理器的执行并请求服务。处理器和前面一样执行数据传送,然后恢复处理器以前的执行过程。

以上两种 I/O 都需要处理器参与数据的传送,有两方面的固有缺陷:

  • I/O 传送速度受限于处理器测试设备和提供服务的速度
  • 处理器忙于管理 I/O 传送的工作,必须执行很多指令以完成 I/O 传送

需要移动大量数据时,有一种更有效的技术为:直接内存存取(Direct Memory Access)。

DMA 功能可以由系统总线中的一个独立模块完成,也可以并入 I/O 模块。该技术的工作方式如下:

  • 在处理器读或写一块数据时,给 DMA 模块产生一条命令,发送以下信息:
    • 是否请求一次读或写
    • 所涉 I/O 设备的地址
    • 开始读或写的存储器单元
    • 需要读或写的字数
  • 之后处理器继续执行其他工作。处理器直接把这个操作委托给 DMA 模块负责处理。DMA 模块直接与存储器交互,传送整个数据块,每次传送一个字。这个过程不需要处理器参与,传送完成后,DMA 模块向处理器发送一个中断信号。因此,只有开始传送和结束传送的时候,处理器才会参与。

但是,DMA 模块需要控制总线来与存储器进行数据传送。由于总线的使用中存在竞争,当处理器需要使用总线时,要等待 DMA 模块。这并不是一个中断,处理器没有保存上下文环境去做其他事情,而只是暂停一个总线周期(总线上传输一个字的时间)。因此,在 DMA 传送过程中,当处理器需要访问总线时,处理器执行速度会变慢。

操作系统发展历史

  • 串行处理

  • 简单批处理系统(第一个操作系统)

    • 一个监控程序的软件。操作员把作业按顺序组织成批,并将整个批作业放在输入设备伤,供监控程序使用。每个程序完成处理后返回到监控程序,同时监控程序自动加载下一个程序。

      执行过程:监控程序 控制权 =》用户程序,执行完毕 控制权 =》监控程序

      目的:充分利用处理器资源,没有任何空闲时间(不需要每次额外准备作业的时间)。但是如果程序有长时间 I/O 操作的话,还是会浪费资源。

  • 多道批处理系统

    • 简单批处理系统的一个改进:操作系统内部多保留几个程序,当一个程序进行 I/O 操作时,切换另一个程序来运行。
  • 分时系统
    • 多个用户共享处理器的时间,分时技术。多个用户通过终端访问系统,操作系统在每个用户程序中很短的时间交替执行。
    • 本质是利用人的反应时间比计算机响应时间慢许多的特点
  • 现代操作系统

    • Linux, Windows, Mac OS, 分布式操作系统 etc.

进程

为什么要有进程这个概念?设计这样概念的目的是什么?

这个问题不好回答,我想等我复习完之后,我再回答或者逐渐补全回答:

  • 目的之一:表征(用来描述)一个正在执行的程序
  • 目的之二:操作系统为每个要执行的程序创建进程,利用进程达到控制程序的执行的效果

进程是什么?它由什么构成?

是对执行的程序的一种抽象表达:程序执行的实体称之为进程:即一个正在执行(注意是执行)的程序。

基本构成:

  • 程序代码和与之关联的数据集

  • 可以用如下元素来表征一个进程

    • 标识符:PID
    • 状态:运行,阻塞等等
    • 优先级:相对于其他进程的优先顺序
    • 程序计数器:PC
    • 内存指针:包括程序代码和进程相关数据的指针,以及与其他进程共享内存块的指针
    • 上下文数据:进程执行时处理器的寄存器的数据
    • I/O 状态信息:显示 I/O 请求,分配给进程的 I/O 设备和被进程使用的文件列表
    • 记账信息:包括处理器的时间总和。

    上述信息将放在一个称之为 PCB 的数据结构中。

进程模型

五状态进程模型

  • 新建态:程序对应的进程被创建,但是还没有加载至内存
  • 就绪态:进程做好了准备,只要有机会就会开始执行
  • 运行态:进程正在执行
  • 阻塞态:进程再某些事情发生前不能执行,比如等待 I/O 操作
  • 退出态:从可执行的进程组中释放出的进程

image-20200813231048351

七状态进程模型

image-20200814101549726

进程描述

为了管理进程和资源,必须掌握每个进程和资源的当前状态。普遍采用的方法是,操作系统构造并维护其管理的每个实体的信息表。操作系统维护 4 种不同类型的表:内存、I/O、文件和进程。其中这些表并不是独立的,它们之间以某种方式链接起来或交叉引用。

  • 内存表
    • 分配给进程的内存
    • 分配给进程的外存
    • 内存块或虚存储块的任何保护熟悉,如哪些进程可以访问某些共享内存区域
    • 管理虚存所需要的任何信息
  • I/O 表
    • 管理计算机系统中的 I/O 设备和通道。
  • 文件表
    • 文件表提供文件是否存在、文件在外存中的位置、当前状态和其他属性的信息。
  • 进程表
    • 管理进程的表
    • 进程映像( process image ):等价一个进程
      • 程序(代码)
      • 数据
      • 属性集合(PCB)
        • 进程标识信息:PID, 用户 ID
        • 进程状态信息:处理器的状态信息(寄存器等等)
        • 进程控制信息

进程创建

操作系统创建进程的一般步骤:

  • 为新进程分配一个唯一的进程标识符。主进程表添加一个新表项,每个进程一个表项;
  • 为进程分配空间。操作系统需要知道私有用户地址空间(程序和数据)和用户栈需要多少空间;
  • 初始化进程控制块PCB。PC,系统栈指针等等。
  • 设置正确的链接。比如若操作系统将每个调度队列都维护一个链表,则新进程必须在就绪或挂起链表中。
  • 创建或扩充其他数据结构。比如维护一个记账文件。

进程切换

  • 将程序计时器置为中断处理程序的开始地址
  • 从用户模式切换到内核模式
  • 保存原先进程的状态:
    • 保存处理器上下文,包括寄存器,PC,栈指针等等
    • 更新当前处于运行态进程的PCB,比如更改里面的进程的状态
    • 把该进程的PCB表移到相应的队列
    • 选择另一个进程执行
    • 更新所选的 PCB, 比如状态改为运行态
    • 更新内存管理数据结构
    • 载入程序计数器和其他寄存器先前的值(换入的进程)

线程

为什么引入线程概念?

进程概念本身其实具有两个性质:一个与资源所有权(进程映像)相关,另一个与执行相关。为了区分这两个特点,引入线程来分离进程执行的特点。

进程和线程的定义?

在多线程环境下的定义:

  • 进程是操作系统分配资源的最小单元和保护单元
  • 线程是操作系统分派执行的最小单元

进程和线程的特点?

进程,和之前构成无区别:

  • 容纳进程映像的虚拟地址空间
  • 对处理器、其他进程(通信)、文件和 I/O 资源的受保护访问

线程的构成

  • 一个线程执行状态(运行、就绪等)
  • 为运行时保存的线程上下文;线程可视为在进程内的一个独立的程序计数器
  • 一个执行栈
  • 每个线程用于局部变量的一些静态存储空间
  • 与进程内其他线程共享的内存和资源访问

线程与进程相比有什么优缺点?

  • 在已有的进程中创建一个新线程的时间远远少于创建一个全新进程的时间:

    • 创建进程需要创建PCB表项,需要分配较多的地址空间(代码,栈区等等);还需要设置诸多控制访问信息:文件信息,I/O 控制访问信息等等;

    • 而创建线程轻量许多:只需要重新分配一个栈空间,一个新的PC(程序计数器),线程控制块中信息比进程控制块中少很多,比如控制访问信息可以不需要。

  • 销毁也是线程占优势:

    • 线程
      • 释放栈空间
      • 释放线程控制块
  • 切换也是线程占优:

    • 进程
    • 线程:
      • 把当前 PC 指向切换程序的首地址
      • 保存当前线程的处理器的上下文信息:寄存器信息(包含了栈指针),PC 信息
      • 更新线程控制块的信息,比如线程的状态变为阻塞态
      • 把新的线程的上下文信息载入
      • 更改 PC 为当前线程的指令地址
    • 线程的切换不需要更换当前的地址空间,而进程切换很可能需要切换地址空间。切换地址空间可能会扰乱缓存机制。
  • 线程之间的通信效率更高:因为共享地址空间,可以通过共享内存实现通信;而进程需要更为复杂的通信机制:管道,消息队列,套接字等等

  • 进程的安全性较高。因为不同的进程隔离在不同的地址空间中运行,所以安全性较高。

线程的分类:

用户级线程:就是用户管理所有的线程的创建,切换等等

内核级线程:内核直接管理线程。

Linux 的进程和线程管理

Linux 中的进程或任务由一个 task_struct 数据结构表示。task_struct 数据结构包含以下各类信息:

  • 状态
  • 调度信息:优先级顺序
  • 标识符:PID
  • 进程间通信
  • 链接:到父进程和兄弟进程的链接,以及所有子进程的链接
  • 时间和计时器
  • 文件系统:包括指向该进程打开的任何文件的指针和指向该进程当前目录和根目录的指针
  • 地址空间:定义分配给该进程的虚拟地址空间
  • 处理器上下文:构成该进程的上下文寄存器和栈信息

Linux 线程

传统 UNIX 系统支持在每个进程中只执行一个线程,老版本的 Linux 内核不支持多线程。多线程应用程序需要一组用户级程序库来编写,以便所有线程映射到一个单独的内核级进程中,比如 pthread 库。现代 Unix 提供内核级线程。Linux 提供一种不区分进程和线程的解决方案。将用户级线程映射到内核级进程。组成一个用户级进程多个用户级线程则映射到共享同一个组 ID多个 Linux 内核级进程上。

  • 用户级内的多线程 =》同一个组 ID 的内核多进程上。
  • 这些组内的进程共享文件和内存等资源,使得组内进程调度切换不需要切换上下文。

  • Linux 中通过复制可以创建一个新进程。新进程创建后可共享资源,如文件、信号处理程序和虚存,共享虚存,其实可视为同一个进程中的两个线程。Linux 没有给线程定义单独的数据结构,所以在内核中 Linux 中进程和线程没有区别

Linux 命名空间

Linux 中和每个进程相关联的是一组命名空间。命名空间的总体目标之一就是为实现控制组(cgroups, 词嵌也称容器) 提供支持,控制组是一个轻量级可视化工作,它使得进程或进程组好像是系统上的唯一进程。说白了,感觉命名空间就是起到资源的隔离的效果。

Linux 有 6 中命名空间

  • mnt:为进程提供文件系统层次结构视图
  • pid:隔离进程 ID 空间,使得不同 PID 命名空间中进程可以拥有相同的 PID。
  • net:隔离与网络相关的资源
  • ipc:隔离某些进程间通信
  • uts:UNIX timesharing,和系统调用 uname 相关。主要是设计一组机器的命名问题
  • user:用户命名空间为其自身的 UID 集提供容器,与父进程分离。

并发:互斥和同步

书上言:操作系统设计中的核心问题是进程和线程的管理。其中并发是所有问题的基础,也是操作系统设计的基础。

并发的概念

多个程序(两个以上)在时间上以一种不可预测的顺序、重叠或交替执行。

操作系统希望找到一种方式确保一个进程的功能和输出结果必须与执行速度无关

一些术语:

image-20200817144242994

进程的交互:

  • 进程之间互相不知道对方的存在
  • 进程间接知道对方的存在:不知道对方 ID,但它们共享某些对象;
  • 进程直接知道对方的存在:知道对方的 ID,可直接通信。

访问竞争资源的会出现三种问题

  • 互斥
  • 死锁
  • 饥饿

互斥的要求

提供对互斥的支持,需满足:

  • 必须强制实施互斥:临界区至多只有一个进程进入
  • 一个在非临界区停止的进程不能干涉其他进程
  • 绝不允许出现需要访问临界区的进程被无限延迟的情况,即避免死锁和饥饿
  • 没有进程在临界区时,需要进入临界区的任何进程需要马上能够进入
  • 对相关进程的执行速度和处理器的数量没有人任何要求和限制
  • 一个进程驻留在临界区的时间必须是有限的

互斥的实现

  1. 单处理器只需要禁用中断即可。

  2. 专用机器指令:

    多处理配置中,几个处理器共享对内存的访问。所以设计互斥的出发点就是:在硬件级别上,对相同位置的存储单元的访问实现互斥。硬件人员设计了一些机器指令,确保两个动作的原子性,如在一个取指周期内对一个存储单元的读和写或读和测试。这些指令执行过程中,任何其他指令访问内存都将被阻止。

    常见的指令:

    • CAS,compare_and_swap

      int compare_and_swap(int *word, int testval, int newval){
          int oldval;
          oldval = *word;
          if(oldval == testval) *word = newval;
          return oldval;
      }
      
    • exchange 指令,exchange 指令定义如下:

      void exchange(int* register, int *memory){
          int temp;
          temp = *memory;
          *memory = *register;
          *register = temp;
      }
      

    硬件的方法一般会使用忙等待,可能会饥饿,可能有死锁。

  3. 信号量

    这是由操作系统提供的并发性的机制。

    三部分构成:

    • r 资源量, semaphore
    • P 操作 semWait:r–,如果 r <0, 则把当前执行 P 操作的进程阻塞
    • V 操作 semSignal: r++,如果 r <=0, 则唤起一个阻塞的进程
  4. 管程

    由程序设计语言提供的并发的机制,功能与信号量相同,主要是便于设计一个正确的程序。管程是由一个或多个过程、一个初始化序列和局部数据组成的软件模块,主要特点如下:

    • 局部数据变量只能被管程的过程访问,任何外部过程不能访问。
    • 一个进程通过调用管程的一个过程进入管程
    • 在任何时候,只能有一个进程在管程中执行,调用管程的任何其他进程都被阻塞,以等待管程可用。

    主要实现涉及三方面:

    • 条件变量:只有管程能够操作
    • cwait(ConditionVariable c): 在 c 上把该进程阻塞,放入一个和 c 相关联的阻塞队列
    • csignal(ConditionVariable c):释放一个 c 上队列阻塞的进程,执行该过程后退出管程

    个人感觉和二元信号量没啥太大区别。

  5. 消息传递

    为实施互斥,进程间需要同步;为实现合作,进程间需要交换信息。一种实现方法就是消息传递。在分布式系统、共享内存的多处理器系统和单处理器系统中实现。

    sendreceive

    • 同步:

      根据实现的 send 和 receive 方式可分:

      • 阻塞 send, 阻塞 receive
      • 无阻塞 send, 阻塞 receive
      • 无阻塞 send, 无阻塞 receive
    • 寻址:

      • 直接寻址:send 原语包含目标进程的标识号,即直接发给 receiver

      • 间接寻址:消息不直接从发送者发送到接收者,而是发送到一种共享数据结构,称之为信箱。

        几种常见的结构:

        • 一对一:允许两个进程间建立专用的通信链接
        • 多对一:客户-服务器的交互非常有用,这时信箱称为一个端口(port)
        • 一对多:一个发送者,多个接收者,广播消息非常适用
        • 多对多:多个服务进程对多个客户进程提供服务
  6. 生产者和消费者问题 & 读者和写者问题

并发:死锁和饥饿

参考

死锁是什么?产生的条件?如何处理死锁?

定义:如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件,那么该进程组就是死锁的。

产生死锁的必要条件:

  • 互斥条件:资源不能被共享,只能由一个进程使用
  • 请求和保持条件:已经得到资源的进程可以再次申请获取新的资源
  • 非抢占条件:已经分配的资源不能从相应的进程中被强制地剥夺
  • 循环等待条件:系统中若干进程形成环路,该环路中每个进程都在等待相邻进程正占用的资源

如何处理死锁问题

  • 忽略该问题。例如鸵鸟算法,该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢,因为传说中鸵鸟看到危险就把头埋在地底下,可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。
  • 检测死锁并且恢复。
  • 仔细地对资源进行动态分配,使系统始终处于安全状态以避免死锁
  • 通过破除死锁四个必要条件之一,来防止死锁产生。

Linux 内核并发机制

UNIX 为进程间的通信和同步提供了各种机制。

  • 管道
  • 信号量
  • 消息
  • 信号
  • 共享内存

管道、消息和共享内存提供了进程间传递数据的方法,而信号量和信号则用于触发其他进程的行为。

管道

管道是一个环形缓冲区,它允许两个进程以生产者/消费者的模型进行通信。FIFO,由一个进程写,另一个进程读。

  • 匿名管道:父子关系的进程才能共享匿名管道
  • 命名管道:不相关的进程只能共享命名管道

消息

消息是有类型的一段文本。每个进程都有一个与之相关联的消息队列,其功能类似于信箱。

共享内存

共享内存是进程间通信手段速度最快的一种。虚存中由多个进程共享一个公共内存块

信号量

信号

信号是用于向一个进程停止发生异步事件的机制。信号类似于硬件中断,没有优先级,即内核公平地对待所有信号。对于同时发生的信号,一次只给进程一个信号,而没有特定的次序。

信号的传递:通过修改信号发送到的进程所对应的进程表一个域来完成的。即修改目标进程的进程表的某个域。

比如 Linux 下按下 ctrl + c,就是发送了一个中断 SIGNIT 信号给进程,然后中断。

实时信号(Linux 额外提供的)

与普通信号不同的是:

  • 支持按优先级顺序排列的信号进行传递
  • 多个信号进行排队
  • 实时信号机制可以将数值随信号一起发送过去

Linux 的屏障操作:

  • 保证指令的执行顺序,提供内存屏障(memory barrier) 设施。rmb() 操作保证代码中 rmb 之前的代码没有任何读操作穿过屏障,rmb 之后的代码中读操作也没有任何机会穿过屏障。

内存管理

内存管理是:操作系统动态分配内存给多个进程。