操作系统1：导论，进程和线程

RandomStar in 2020.09

Chapter 1. Introduction

1.1 什么是操作系统

• 用户和计算机硬件之间的中间程序
  • 执行用户程序
  • 使计算机易于使用
  • 充分调用计算机资源
• 计算机系统可以分为四个部分
  • 硬件：CPU，内存和I/O设备
  • 操作系统
    • 用户视角：操作系统是用户和计算机硬件之间的接口
      • 计算机硬件
      • 操作系统提供了命令级接口(鼠标和键盘)和程序级接口(system calls)
    • 系统视角：操作系统是计算机系统资源的管理者
      • 控制程序，分配资源
    • 软件分层的观点：是扩充裸机的第一层系统软件
    • 一直在运行的程序就是kernel(内核)
  • 应用程序
  • 用户 user，包含人、机器和其他计算机，不单指人
• 中文书上对操作系统的定义：
  • 操作系统是一组有效控制和管理计算机各种硬件和软件资源，合理组织计算机的工作流程，方便用户的程序的集合
  • 有效：系统效率高，资源的利用率高
  • 合理：公平，不公平的时候会产生死锁和饥荒
  • 方便：用户接口，图形界面

1.2 计算机组成

• 主机型计算机系统：以存储器为中心，CPU和数据通道都和存储器相连
• 中断：指系统发生某个异步/同步事件后，处理机暂停正在执行的程序，转去执行处理该事件程序的过程
  • 通过中断向量来实现，中断向量记录了所有服务例程的地址
  • 中断的分类
    • 中断(外中断)：I/O中断，时钟中断
      • 外部设备发出的I/O请求，分为可屏蔽和不可屏蔽两类
      • 可以在指令执行的任意时期产生
    • 异常(内中断)：系统调用，缺页异常，断点指令，其他异常
      • 由CPU产生，一条指令中止之后才会发出中断
  • 操作系统是中断驱动的

1.3 计算机系统结构

• 单处理器系统：core是执行指令和存储本地数据的组件

• 多处理器系统

  • 也被称为并行系统，分为同步和异步两种
  • 优点包括：规模经济的，吞吐量增加
  • NUMA——非同一内存访问

• 集群系统cluster

  • 是由一组互联的主机（节点）构成统一的计算机资源，通过相应软件协调工作的计算机机群
  • 分为对称集群和非对称集群
  • HPC(high-performance computing) 高性能计算
  • DLM(distributed lock manager) 分布式锁管理器，用于避免集群中的冲突操作

1.4 操作系统的运行

• 何时运行操作系统？

  • 操作系统是硬件中断驱动的，此时先启动中断处理程序
  • 软件出错，或者产生异常exception和陷入trap
  • 其他的进程问题，比如死循环

• Dual-mode operation 双模式操作

  • user mode 用户态

  • 执行用户程序的时候的模式

    • 只能访问属于它的存储空间和普通寄存器，只能执行普通指令
    • 用户程序和操作系统以外的服务程序运行在用户态中，使用用户栈

  • kernel mode 内核态

    • 执行操作系统程序的时候的模式
    • 可以访问所有系统资源，执行特权指令(I/O指令、设置时钟、置控制寄存器等)，可以直接操作和管理硬件设备
    • 操作系统内核的程序运行处于内核态，使用内核栈

  • 上课讲过的几个习题

    • 三种从用户态切换到内核态的方式：

      • 系统调用、异常、外围设备的中断

    • 中断处理一定会保存而子程序调用不需要保存的内容是：程序状态字寄存器

    • 不可能发生在用户态的事件是：进程切换，需要调度处理器和系统资源，为保证系统安全

      • 缺页是用户态到内核态
      • 系统调用和中断既可以发生在用户态，也可以发生在内核态

1.5 资源管理，虚拟化

后面会细讲，这里就看了几个标题

1.6 计算环境

• 几种不同的计算环境
  • 传统计算：
    • 大型机系统：批处理系统和分时系统
      • 批处理系统：分为单道批处理系统/多道批处理系统，多道批处理系统中，内存同时进行若干工作，CPU被多路复用
      • 分时系统：多个用户分时间共享同一台计算机
        • 响应时间：分时系统的重要指标，假设分时系统中进程数为n，每个进程的运行时间片为q，则S=nq
    • 桌面系统——PC个人电脑
  • 移动计算：“再过几年可能是鸿蒙”
  • C/S结构计算，P2P计算——区块链技术，虚拟化计算，云计算(SaaS, PaaS, IaaS)

Chapter 2. 操作系统结构

2.1 操作系统服务

• 操作系统提供如下服务
  • 用户接口：包括命令行CLI和图形用户界面GUI
  • 程序执行：把程序载入内存中执行，
  • I/O操作：操作文件和IO设备
  • 文件系统的操作
  • 交流：不同的进程之间交流信息
  • 错误检测：检测CPU，内存，IO设备出现的错误
  • 资源的分配，用户操作的记录
  • 安全性保护

2.2 用户操作系统接口 UOSI

• 操作系统的接口
  • 命令接口
    • 命令行用户接口，文本界面
    • 图形用户接口
    • 触摸屏接口、语音接口……
  • 程序接口：比如system call

2.3 系统调用system call

• 系统调用：提供操作系统服务的程序接口

  • 是进程和OS内核的程序接口，使用高级语言来编写
  • API封装了一系列的系统调用，比如win32 API， POSIX API和Java API(JVM)
  • 每个系统调用对应了一个封装例程(wrapper routine)，一些API应用了封装例程，API还包括各类编程接口，比如C语言库函数
  • 系统调用是在内核完成的，用户态的函数是在函数库中实现的

  

  image-20200921143335057

  • 注意区别系统调用和库函数的调用
    • 像printf，fopen，malloc这些都是C语言的库函数，而不是系统调用
  • 执行系统调用的几个过程：
    • 执行trap指令
    • 传递系统调用操作
    • 执行相关操作
    • 返回用户态
  • 系统调用的种类：进程控制，文件/设备的管理，信息的维护，通信，保护

• 系统调用的参数传递

  • 最简单的方法：通过寄存器传递参数
  • 用内存中的block和table存储参数，并在系统调用中把块地址放在寄存器中传递
    • Linux系统使用这种方法实现的
  • 通过栈来传递参数

2.4 系统服务

• 操作系统提供的服务，比如shell中的各种命令
• 操作系统中运行程序的步骤：
  • 将程序装入内存中
  • 确定起始地址，并从这个地址开始执行
  • 用控制台监控程序执行的过程
  • 不需要向操作系统预约运行时间
    • 只有实时的操作系统才需要预定CPU时间
• 操作系统提供的功能中，需要特定硬件支持的有：
  • 时钟管理
  • 地址映射
  • 中断
  • 进程调度不需要特定的硬件支持

2.5 Linker和Loader

• 程序编译之后变成了relocatable object file浮动对象文件
  • 链接器会将这些文件变成可执行的二进制文件
  • Loader将程序装载入内存执行，将最终地址分配给程序部件，并调整程序中的代码和数据以匹配这些地址
  • 动态链接库 (Windows系统中的后缀是dll) 通过接口的形式实现链接，而不是直接和库文件进行链接

2.6 操作系统结构

• 常见的结构

  • 简单结构：比如MS-DOS系统，不划分模块

    

  • 层次结构：操作系统分成了若干层次，最外层是用户接口，最内层是硬件

  • 单/宏内核结构(Monolithic Kernels)：内核的全部代码打包在一个文件中

    • 优点是效率很高，缺点是维护和修改非常困难，容易出bug，随着OS变复杂内核的规模会爆炸

  • 微内核结构(Microkernel System Structure)

    • 最基本的功能直接由中央内核实现，其他的功能都委托给独立的进程，这些进程和内核通过通信接口进行通信

    

  • 内核的模块：在需要的时候才进行调用，模块之间互相独立，通过接口互相通信

2.7 虚拟机VM

• 虚拟机技术：
  • 硬件和操作系统内核都看成硬件来使用，和宿主机共享操作系统资源
  • 提供了一个独立于底层硬件的接口

Chapter3：Linux系统概述和Linux内核

3.1 Linux操作系统

• Linux操作系统指的是GNU/Linux系统
  • Linux系统的组成：内核，C语言库，编译器，工具集和系统的基本工具，Shell，各种应用软件包等等
  • Linux是一种类Unix的操作系统，遵守GNU的GPL/LGPL/AGPL
  • Linux 是一个可供多人使用的抢占式多任务操作系统
• GPL: 公用版权协议General Public Lisence
  • Linux采用该条款发行
• 开放源代码：Open Source=代码+许可证+管理机制
  • 基于社区开发的、非私有的代码，可令成本更低、开发效率更高、商业应用更加灵活
• Linux版本有两种表现形式
  • 内核版：Kernel
  • 发行版：Distribution
• Linux成长的五个重要支柱
  • UNIX操作系统
  • MINIX操作系统
  • GNU
  • POSIX
  • INTERNET

3.2 Linux内核

• Linux内核是单一体系结构的
  • 使用了一种全新的内核模块机制，用户可以根据需要，在不需要对内核重新编译的情况下，动态地装入/移除内核的模块
  • 模块在内核态运行，实际上是一种目标对象文件，没有链接，不能独立运行，但是内核的代码可以在运行的时候链接到系统中作为内核的一部分运行或者取出，从而实现了动态扩充内核的功能
  • 这种目标代码通常由一系列函数和数据结构组成
    • 编译相应的模块，用insmod 指令插入就可以
      • insmod 内核加载模块
      • lsmod 查看内核模块
      • rmmod 卸载内核模块
      • ksyms 显示内核符号和模块符号表的信息，可以读取/proc/kallsyms 中的文件
      • modprobe 是自动根据模块之间的依赖性插入模块的程序，比如A依赖于B，那么插入A的时候modprobe命令就会把B也加载进入内核之中
    • 模块不依赖某个固定的硬件平台
    • 被链接到内核之后，模块的作用域和静态链接的内核目标代码完全等价
  • 模块的全称是动态可加载内核模块 Loadable Kernel Module
• 引入内核会带来的问题
  • 内核所占用的内存是不会被换出来的，所以把新的模块链接进去会给整个系统带来一定的性能和内存利用方面的损失
  • 装入内核的模块会成为内核的一部分，模块使用不当会导致系统崩溃
  • 为了让内核的模块能够访问所有的内核资源，必须维护一个符号表，并且在装入和卸载模块的时候修改这个符号表
    • 模块之间可能会相互依赖，因此内核需要维护模块之间的依赖性

操作系统2：进程/线程

Chapter 3. Process 进程

3.1 进程的定义

• 进程是一个在执行中的程序

  • 放在外存的程序就不是进程，进程可以理解为进行中的程序
  • 是计算机工作的基本单位，和job，task，user program等概念相同
  • 是一个包含了一系列指令和一些资源的容器
    • 是一个抽象实体，执行任务的时候，将要分配和释放各类资源

• 进程包括以下内容：

  • 程序代码(text section)

  • 程序计数器 PC

  • 寄存器

  • 数据区，存储全局变量

  • 栈区，存储临时变量

  • 堆，动态分配的内存(C语言中的malloc)

  • 在内存中的示例图

    

• 进程的状态：

  • 几种状态
    • new 新建，创建一个新进程
    • running 运行、执行：执行指令的状态
    • ready 就绪，准备好被分配给一个CPU执行
    • waiting 等待，等待一些事件结束后再执行
    • terminated 中止，执行结束
  • 会引起状态变化的操作：
    • 程序中的操作，比如系统调用
    • OS操作，比如调度的决策
    • 外部操作，比如中断
  • 状态迁移的图解：

  

  • 假设一个单CPU的计算机，OS进程有运行就绪等待三个状态，假设某个时刻该系统有10个进程并发执行：
    • 处于执行状态的最多有1个，处于就绪/等待状态的最多有9个

3.1.1 进程控制块 PCB

• 每个进程在操作系统内用进程控制块来表示
  • 进程控制块PCB包含如下信息：进程状态，PC，CPU寄存器，调度信息，内存管理信息，accounting信息，文件管理，I/O统计信息
  • 在Linux内核中，进程的信息用一个C语言中的结构task_struct 来表示，定义在头文件<linux/sched.h> 中，各个进程之间构成一个双向链表

3.2 进程调度 Scheduling

• 调度队列：

  • 作业队列：系统中所有进程的队列
  • 就绪队列：在内存中处于就绪状态得进程的队列
  • 设备队列：等待I/O设备的进程的队列

• 三种scheduler

  • (作业题)进程调度需要将进程在ready、running、blocked三种状态之间切换

  • 长程调用/作业调度：现代操作系统已经没有使用长程调度了
  • 短程调度：又叫CPU调度，选择下一个将要被CPU执行的进程
  • 中程调度

• 另一种分类方式：

  • I/O型进程：主要事件花在IO上
  • CPU型进程：主要时间花在CPU处理上

• 上下文切换：

  • 当切换到另一个进程的时候，系统必须要保留上一个进程的状态，同时又载入新进程的状态

  • 在PCB中表示

  • 耗时取决于硬件的支持

    

  • A context switch occurs when the CPU switches from one process to another.

3.3 进程操作 Process Operation

3.3.1 进程的创建

• 父进程可以创建子进程，并可以形成一棵进程树，每个进程有唯一标识号pid

  • pstree命令可以查看进程树

• fork：创建进程的系统调用

  • int pid1 = fork();
    • 事实上就是把当前进程分出了一个新的子进程，一个程序变成了两个进程，其中一个是父进程一个是子进程
    • 一个进程调用fork()函数后，系统先给新的进程分配资源，例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的新进程中，只有少数值与原来的进程的值不同。相当于克隆了一个自己
  • 返回值是一个pid1，从系统调用fork中返回的时候，两个进程除了返回值pid1不同以外具有完全相同的用户级上下文，子进程中pid1为0，父进程中pid1的值就是子进程的pid

  int main() {
      int pid1 = fork();
      if(pid1 < 0) {
          cout << "Failed!" << endl;
      } else if(pid1 == 0) {
          // chidren proccess
      } else {
          // parant process
      }
  }

3.3.2 进程的终止

• 引起进程终止的事件：
  • 正常结束、异常结束、外界干预
  • exit(0) 退出进程
• 系统调用wait()
  • 通过wait父进程可以等待子进程结束，wait调用会返回进程的状态信息和结束进程的pid
    • 这使得父进程可以等待并回收子进程的资源
    • 父进程一旦调用了wait()就立即阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个已经变成僵尸的子进程，wait就会收集这个子进程的信息，并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个子进程出现并结束为止
  • 子进程中止而父进程尚未调用wait就会使得子进程变成一个僵尸进程(zombie process)
  • 父进程中止而没有调用wait就会产生一个孤立进程(orphan process)

安卓操作系统的进程重要度分级架构——优先中止最不重要的进程

• Foreground process 正在运行的进程
• Visible process 可视化的UI组件等等
• Service process 后台提供服务的进程
• Background process
• Empty process 空进程

3.4 进程间通信 Interprocess Communication

• 进程的分类

  • 独立进程：不能被其他进程影响，也不能跟其他进程交互
  • 合作进程：进程之间可以进行通信
    • 信息共享、方便性
    • 计算加速

• 进程间通信 IPC

  • 通信分为直接通信和间接通信
    • 直接通信就是进程之间直接发送信息，间接就是还有中介，比如内存、邮箱共享等
  • 两种通信的模型：共享内存模型和消息模型

  

  • 常用的通信机制：
    • 信号 signal
    • 共享存储区 shared memory
    • 管道 pipe
    • 消息 message
    • 套接字 socket
    • 是个操作系统都有的通信机制：信号量、消息队列、共享内存
    • 在Linux操作系统中，还有：
      • 文件锁 file lock 问题是速度很慢，因为文件是磁盘I/O
      • POSIX线程：互斥锁(mutex)，条件变量

• Windows 的进程间通信

  • 信号：一系列Windows API
  • 文件映射机制：可以将整个文件映射为进程虚拟地址空间的一部分来加以访问
  • 无名管道：类似于UNIX的管道，与此相对的Windows还有命名管道
  • 邮件槽 mailslot
  • 剪贴板 Clipboard：暂时保存了一些文本

具体的栗子

• 有限缓冲区Bounded-Buffer，缓冲区的大小有上限
  • 生产者-消费者问题：生产者进程制造出新信息，消费者使用新的信息
  • 用类似于循环队列的数据结构控制内存的访问
• 消息传送：分为阻塞的和非阻塞的(block & unblock)
  • 阻塞的消息传递：同步的
    • send需要发送方阻塞直到消息被接收
    • receive需要接收方阻塞直到有消息送到
  • 非阻塞的消息传递：异步的
    • 发送方发送之后直接继续，接收方不断接受到有效/无效的消息
• Socket 作为交流的endpoint
  • Socket中包含了IP地址和端口，端口是一个包含了数据包起点的数字
    • 标号为1024以下的端口是常用端口，用来提供标准服务
    • 特殊的IP地址127.0.0.1表示正在运行进程的系统
  • 交流需要通过一系列的Socket来实现

Chapter 4：Thread & Concurrency 线程和并发

4.1 Overview

• 进程是资源的拥有单位和调度(Dispatching)单位

  • 进程由虚拟地址空间，控制一些资源，有状态、优先级和调度
  • 进程是由一个或者多个程序的一次支持，可以和其他进程交替执行

• 线程thread

  • 资源拥有单元称为进程，调度的单位称为线程，也叫做轻型进程LWP

    • 一个传统进程，或者叫重型进程HWP和线程中的一个任务等价
    • 线城市进程内的一个执行单元或者一个可调度的实体

  • 线程只拥有必要的资源，但是可以和同一个进程下的其他线程共享进程拥有的全部资源

  • 线程的特点：

    • 有执行状态
    • 不运行时，保存上下文
    • 有一个执行栈
    • 有局部变量的静态存储
    • 可以取所在进程的资源，但是不拥有系统资源
      • 同一个进程下面的进程还共享代码段和数据段
    • 可以创建、撤销另一个进程
    • 一个进程中的多个线程可以并发执行，系统开销小，切换快

  

  • 线程带来的benifits
    • 创建线程、线程之间切换的时间比较少
    • 共享了内存和文件，线程之间的通信不需要经过内核
  • 多核情况下的线程并行

  

4.2 多线程模型

• 用户级线程和内核级线程

  • 用户级线程
    • 不依赖于OS内核，应用进程利用线程库提供创建、同步、调度和管理的函数来控制用户线程
      • 即用户线程的维护由应用进程来完成
      • 内核不了解用户线程的存在
      • 用户线程切换不需要内核特权
      • 一个线程发起系统调用而阻塞，则整个进程在等待
    • 常见的线程库：POSIX pthreads库， win32 threads， Java threads
  • 内核级线程
    • 依赖于OS内核，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。一个线程发起系统调用而阻塞，不会影响其他线程。时间片分配给线程，所以多线程的进程获得更多CPU时间
      • 内核维护进程和线程的上下文信息
      • 线程的切换由内核完成
      • 时间片分配给线程，所以多线程的进程获得更过CPU时间
      • 一个线程发起系统调用而阻塞，不会影响其他线程

• 线程模型

  • 多对一模型：内核一个线程，用户多个线程，好处是不需要OS的支持

    • 可以使用调度策略来优化，但是在多处理器中不适用

    

  • 一对一模型：每个用户线程对应一个内核线程

    • 每个内核线程独自调度，由OS进行一系列线程操作

    

  • 多对多模型：每个用户线程对应多个内核线程

4.3 Implicit Threading（隐私多线程）

• 隐私线程：将线程的创建和管理交给编译器和运行时库来完成
  • 常见的方法有：Thread Pools 线程池
    • 创建一系列线程等待工作
  • 这里好像讲的比较随意，估计是不太重要

练习题

• process scheduler可以切换ready running和blocked三种状态
• 线程控制块 TCB 存储的内容包括machine states，包括寄存器和程序计数器，实际上就是存储了线程拥有的资源
• 抢占式多任务系统 preemptive multitasking system
  • 一个进程在运行随时可能被另一个进程抢占
  • running到ready是有效的切换