OS Outline

• OS期末复习
  • 1. Introduction
    • OS定义
    • 现代计算机硬件组成
      • 进程（processor）
      • 存储
      • IO
    • 中断
      • 中断的分类
  • 2. 操作系统结构
    • 操作系统服务
    • 用户和程序员接口
    • 系统组件
      • 简单结构
      • 微内核
      • 模块
  • 3. 进程
    • 进程概念
      • 进程
      • 状态
      • 进程表（Process Table）
      • 进程控制块（Prosess Control Block，PCB）
    • 进程调度（Process Scheduling）
      • 调度队列
      • 调度程序
      • 上下文切换（Context Switch）
    • 进程运行
      • 进程创建
      • 进程终止
    • 进程通信（InterProcess Communication，IPC）
      • 共享内存
      • 消息传递
        • 命名
        • 同步
        • 缓存
      • 例子
        • POSIX共享内存
        • Mach
        • Windows
      • 客户机/服务器通信
        • 套接字（socket）
        • 远程过程调用（RPC）
        • 管道（pipe）
          • 普通管道
          • 命名管道
  • 4. 线程
    • 并行与并发
    • 多线程
      • 多对一
      • 一对一
      • 多对多
    • 线程库
    • 隐式多线程（implicit multithreading）
      • 线程池
      • OpenMp
      • 大中央调度（Grand Central Dispatch，GCD）
    • 多线程问题
      • 信号处理
      • 线程撤销（thread cancellation）
      • 线程本地存储（Thread-Local Storage，TLS）
      • 调度程序激活
    • 例子
      • Windows线程
      • Linux线程

OS期末复习

1. Introduction

OS定义

一个操作系统是管理计算机硬件的程序，为应用程序提供基础，充当计算机用户和硬件的中介。

现代计算机硬件组成

进程（processor）

计算机运行：

1. 运行初始程序或引导程序（bootstrap program，一般位于ROM只读内存），定位操作系统内核并加载到内核
2. 系统程序加到内存便成为系统进程/系统后台程序，生命周期与内核一致。
3. 事件发生通过硬件或软件的中断来通知。硬件通过系统总线bus发送信号到CPU，软件通过调用system call与trap触发中断。

存储

1. 内存（main memory）
   1. CPU只能从内存中加载指令，因此执行程序位于内存。
   2. 内存一般称为RAM，通常为动态随机访问内存DRAM，采用半导体技术实现。也存在ROM内存，只能将静态程序（如引导程序）存在ROM只读内存中。
   3. 内存具有易失性（volatile），掉电失去所有内容。
2. 外存（secondary storage）：磁盘、硬盘、固态硬盘、光盘
3. 高速缓存器（Cache）：Cache Coherency (缓存一致性)

IO

1. IO中断驱动：接到I/O请求后，I/O设备传送数据，CPU继续执行用户进程，传送完成后，CPU进行I/O中断处理，处理完成后，再回到用户进程。
2. 直接内存访问（Direct Memory Access，DMA）：外部设备不通过CPU而直接与系统内存交换数据的接口技术。
   1. 对于一个高速I/O设备，以及批量交换数据的情况，只能采用DMA方式，才能解决效率和速度问题。
   2. DMA在外设与内存间直接进行数据交换，而不通过CPU，这样数据传送的速度就取决于存储器和外设的工作速度。
   3. 通常系统的总线是由CPU管理的。在DMA方式时，就希望CPU把这些总线让出来，即CPU连到这些总线上的线处于第三态–高阻状态，而由DMA控制器接管，控制传送的字节数，判断DMA是否结束，以及发出DMA结束信号。

中断

中断指计算机CPU获知某些事，暂停正在执行的程序，转而去执行处理该事件的程序，当这段程序执行完毕后再继续执行之前的程序。整个过程称为中断处理，简称中断，而引起这一过程的事件称为中断事件。

中断是计算机实现并发执行的关键，也是操作系统工作的根本。

中断的分类

1. 内外部
2. 可屏蔽和不可屏蔽
3. 同异步

中断按事件来源分类，可以分为外部中断（external）和内部中断（internal）。中断事件来自于CPU外部的被称为外部中断，来自于CPU内部的则为内部中断。

进一步细分，外部中断还可分为可屏蔽中断（maskable interrupt）和不可屏蔽中断（non-maskable interrupt）两种，而内部中断按事件是否正常来划分可分为软中断和异常两种。

外部中断的中断事件来源于CPU外部，必然是某个硬件产生的，所以外部中断又被称为硬件中断（hardware interrupt）。外部设备的中断信号是通过两根信号线通知CPU的，一根是INTR，另一根是NMI。CPU从INTR收到的中断信号都是不影响系统运行的，CPU可以选择屏蔽（通过设置中断屏蔽寄存器中的IF位），而从NMI中收到的中断信号则是影响中断处理器运行的严重错误，不可屏蔽。

内部中断来自于处理器内部，其中软中断是由软件主动发起的中断，常被用于系统调用（system call）；而异常则是指令执行期间CPU内部产生的错误引起的。异常也和不可屏蔽中断一样不受eflags寄存器的IF位影响，区别在于不可屏蔽中断发生的事件会导致处理器无法运行（如断电、电源故障等），而异常则是影响系统正常运行的中断（如除0、越界访问等）。

中断还可以分为同步中断（被称为异常）和异步中断（被称为中断）。

同步中断是在指令执行时由CPU主动产生的，受到CPU控制，其执行点是可控的。

异步中断是CPU被动接收到的，由外设发出的电信号引起，其发生时间不可预测。

2. 操作系统结构

操作系统服务

用户功能

1. 用户界面（User Interface，UI）：有命令行界面（Command-Line Interface，CLI）、批处理界面（batch interface），图形用户界面（Graphical User Interface，GUI）。
2. 程序执行：系统加载程序到内存并运行。
3. I/O操作
4. 文件系统操作
5. 通信：通信存在于同一台计算机的两个进程，或通过网络连接的不同计算机进程间。实现方式为共享内存（shared memory）和消息交换（message passing）。
6. 错误检测

提高系统效率的功能

1. 资源分配：CPU周期、内存、文件存储、I/O设备
2. 记账：记录用户使用资源的类型和数量
3. 保护与安全：多用户/网络信息安全；独立进程并发执行时，不干预其他进程或操作系统本身；保护外部I/O设备不受非法访问。

用户和程序员接口

系统调用接口

系统调用（system call）提供操作系统服务接口。

开发者一般根据应用编程接口（Application Programming Interface，API）来设计程序。这样做的好处是提高程序的可移植性。

系统调用接口截取API函数的调用，并调用操作系统中的所需系统调用。每个系统调用都有一个相关数字，系统调用接口根据这些数字来建立一个索引列表。

向操作系统传递参数的方法：

1. 通过寄存器传递参数
2. 将参数存在内存的块或表中，将其地址通过寄存器传递，Linux和Solaris就采用这种方法
3. 通过程序放在或压入（push）到堆栈（stack），并通过操作系统弹出（pop）

系统调用类型

1. 进程控制（process control）

   举例：MS-DOS操作系统是单任务系统，不会创建新进程；FreeBSD（源于Berkeley UNIX）是多任务系统，会启动新进程。

   UNIX函数：fork(), exit(), wait()

2. 文件管理（file manipulation）

   UNIX函数：open(), read(), write()

3. 设备管理（device manipulation）

4. 信息维护（information maintenance）

5. 通信（communication）

6. 保护（protection）

系统组件

简单结构

MS-DOS系统利用最小空间提供最多功能，没有被划分为模块，没有很好地区分功能的接口和层次。

UNIX系统由内核和系统程序两个独立部分组成，采用单片结构，系统调用接口之下和物理硬件之上的所有部分可以被视为内核，内核通过系统调用提供操作系统功能。

微内核

Mach操作系统采用微内核技术对内核进行模块化，从内核中删除所有非必须的部件，将其当作系统级与用户级的程序来实现，因此内核较小。

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

微内核的优点之一是便于扩展操作系统，可移植性高。

模块

采用可加载的内核模块（loadable kernel module）：内核提供核心服务，而其它服务可在内核运行时动态实现，动态链接服务优于直接添加新功能到内核。

这种方法与微内核的区别在于：模块无需调用消息传递来进行通信。

举例：Solaris，linux

3. 进程

进程概念

进程

进程是执行的程序，其包括：

1. 程序代码，或称为文本段（text section）、代码段（code section）
2. 当前活动
3. 程序计数器（program counter，PC）
4. 处理器寄存器内容
5. 进程堆栈（stack），包括临时数据（函数参数、返回地址、局部变量）
6. 数据段（data section），包括全局变量
7. 堆（heap），进程运行时动态分配的内存

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

进程本身可以作为一个环境，执行其他代码。例如：python test.py可以运行该python代码。

状态

1. new：进程正在创建。
2. running：进程正在执行。
3. waiting：进程等待发生某个事件（I/O完成或收到信号）。
4. ready：进程等待分配处理器
5. terminated：进程已经完成执行。

一次只有一个进程可在一个处理器上运行；但是许多进程可处于就绪或等待状态。

进程表（Process Table）

进程表是一个内核数据结构，包含用于进程管理、内存管理、文件管理三种数据记录的空间，内核总是有权限访问这三片空间。

进程控制块（Prosess Control Block，PCB）

操作系统使用进程控制块表示每个进程。操作系统根据PCB管理和控制进程，这是进程存在的标志。

进程调度（Process Scheduling）

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

调度队列

1. 作业队列（job queue）：系统中所有的进程
2. 就绪队列（ready queue）：驻留在内存中的、就绪等待运行的进程
3. 设备队列（device queue）：等待特定I/O设备的进程列表

调度程序

无法立即执行的进程会被保存到大容量存储设备（如磁盘）的缓冲池。

1. 长期调度程序/作业调度程序：从缓冲池中选择进程，加载到内存（加入就绪队列）。长期调度进程控制多道程序程度（内存中的进程数量），从I/O密集型进程和CPU密集型进程中选择。
2. 短期调度程序/CPU调度程序：从准备执行的进程（就绪队列）中选择进程，分配CPU
3. 中期调度程序（交换）：将进程从内存中移出，从而降低多道程序程度。此后，进程可被重新调入内存，并从中断处继续执行。

长期与短期调度程序主要区别是执行频率。

上下文切换（Context Switch）

中断发生时，CPU从执行当前任务改变到执行内核程序（从用户到内核），系统需要保存当前运行进程的上下文，以便恢复进程。

进程上下文用PCB表示。内核将旧进程状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。

进程运行

相关函数：

#include <sys/types.h>
#include <unistd.h>
//得到进程的PID
pid_t getpid(void);
//得到进程的PPID
pid_t getppid(void);
//创建进程
pid_t fork(void);//对父进程返回0，对子进程返回一个比大于0的pid，失败则返回小于0的数
pid_t vfork(void);
//替换进程
int execv(const char *path, char *constargv[]); 
//终止进程
exit(1);
//回收子进程
pid_t wait(int);

进程创建

父进程创建新的子进程，每个新进程可以再创建其他进程，从而形成进程树。多数操作系统采用唯一进程标识符（process identifier，PID）来作为进程索引，访问内核中进程的各种属性。

在Linux系统中（相比进程，linux偏爱task这个术语），进程init的PID总是1，作为所有用户进程的根进程或父进程。init进程是linux内核启动后第一个执行的进程，作为引导程序，启动守护进程并且运行必要的程序。

对于UNIX和Linux系统，可以通过ps命令得到进程列表。

当一个进程创建子进程：

1. 子进程可以从两处获取资源（CPU时间、内存、文件、I/O设备等）：
   1. 操作系统
   2. 父进程（除了逻辑资源，子进程从父进程获取参数初始化）
2. 父子进程的执行顺序：
   1. 父进程与子进程并发执行
   2. 父进程等待，直到某个或全部子进程执行完
3. 父子进程的地址空间：
   1. 子进程是父进程的复制品
      1. 子进程拷贝父进程的地址空间，与父进程具有同样的程序和数据副本，虚拟映射地址一致，物理地址不一致
      2. 子进程共享父进程的地址空间，虚拟映射地址一致，物理地址一致
   2. 子进程加载另一个新程序（exec()可进行进程替换）

进程终止

级联终止（Cascading Termination）：有些系统不允许子进程在父进程已经终止的情况下存在。如果一个进程终止，那么它的所有子进程也应终止，这种现象成为级联终止，通常由操作系统启动。

父进程一旦调用了wait，就立即阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个已经变成僵尸的子进程，wait就会收集这个子进程的信息，并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个出现为止。

假如父进程没有调用wait()就终止，子进程会成为孤儿进程，其PCB包含了进程的退出状态，一直被保留在进程表中，无法释放。Linux和UNIX会将init进程作为孤儿进程的父进程。进程init定期调用wait()，收集任何孤儿进程的退出状态，释放PID和进程表条目。

进程通信（InterProcess Communication，IPC）

操作系统内并发执行进程可以是独立或协作的。协作进程需要有一种IPC机制。

进程间通信有两种基本模型：

1. 共享内存。共享内存系统仅需要在建立共享内存区域时需要系统调用，一旦建立共享内存，所有访问无需借助内核。但对于多核系统而言，共享内存具有高速缓存一致性的问题。
2. 消息传递。消息传递的实现经常采用系统调用，需要消耗更多时间使内核介入。但对于多核系统而言，消息传递的性能更高。

共享内存

生产者-消费者

缓冲区分为无界缓冲区和有界缓冲区。

消息传递

命名

1. 直接通信：需要通信的每个进程必须明确指示通信的接收者或发送者。

   1. 对称寻址：发送和接受一对一。
   2. 非对称寻址：发送者指定接收者。

   缺点：生成进程定义的有限模块化。

2. 间接通信：通过邮箱或端口作为中介来发送和接受消息，其可归属于操作系统或进程。

最基本的通信原语有两条,它们是send原语和receive原语。send(M,N)中，M为信箱名

同步

阻塞和非阻塞

同步和异步

缓存

通信进程交换的消息总是驻留在临时队列中。

根据容量分类：

1. 零容量
2. 有限容量
3. 无限容量

例子

POSIX共享内存

Mach

内核通过内核邮箱与任务通信，将事件发生的通知发送到通知邮箱。消息结构：固定大小的头部（消息长度、发送端口、接收端口）和可变大小的数据。

Windows

客户机/服务器通信

客户机/服务器系统除了利用共享内存和消息传递进行通信，还有以下三种策略：

套接字（socket）

每个套接字由一个IP地址和一个端口号组成。

1. 客户进程发出连接请求，其主机为其分配一个端口。这个端口是大于1024的某个数字。
2. 服务器调用accpet()监听端口。
3. 客户端创建一个套接字，连接到服务器监听的端口。

套接字属于分布式进程之间的一种低级形式的通信，其中一个原因是，只允许在通信线程之间交换无结构的字节流。

远程过程调用（RPC）

中介子函数转发

管道（pipe）

普通管道

普通管道是单向无名管道。

1. 对于UNIX系统，子进程自动继承由父进程创建的管道。
2. 对于Windows系统，程序员需要指定子进程继承的属性。
3. 对于Windows和UNIX系统，采用普通管道通信的进程需要有父子关系，这说明这些管道只可用于同一机器的进程间通信。
4. 对于Windows和UNIX系统，一旦进程已经完成通信并终止，普通管道就不存在了。

命名管道

命名管道可以是双向管道，其进程间的父子关系不必须，但必须存在同一机器上；当通信进程完成后，命名管道继续存在。

对于UNIX系统，命名管道为FIFO，一旦创建即表现为文件系统的典型文件，可以通过系统调用读写文件。FIFO一经创建会一直存在，直到被显式删除文件。FIFO只允许半双工传输。

对于Windows系统，允许全双工通信，且通信进程可以位于同一机器或不同机器。

• 单工：简单的说就是一方只能发信息，另一方则只能收信息，通信是单向的。
• 半双工：比单工先进一点，就是双方都能发信息，但同一时间则只能一方发信息。
• 全双工：比半双工再先进一点，就是双方不仅都能发信息，而且能够同时发送。

管道经常用于将一个命令的输出作为另一个命令的输入，例如：ls | more（UNIX命令行）、dir | more（Windows命令行）

4. 线程

每个线程是CPU使用的一个基本单元，其包括线程ID、程序计数器PC，寄存器组和堆栈，与同一进程的其他线程共享代码段、数据段和文件等其他操作系统资源。

代码	数据	文件
线程1的寄存器组	线程2的寄存器组	线程3的寄存器组
线程1的堆栈	线程2的堆栈	线程3的堆栈
线程1的ID、PC及活动内容	线程2的ID、PC及活动内容	线程3的ID、PC及活动内容

传统或重量级进程（Heavy Weight Process，HWP）只有单个控制线程。例如，进程创建是重量级进程，而线程创建是轻量级进程。

进程与线程的关系：

线程的优点：

1. 响应快
2. 线程默认共享他们所属进程的内存和资源
3. 创建和切换线程更加经济
4. 具有可伸缩性，线程可在多处理器核上并行运行

并行与并发

处理核只能同一时间执行单个线程。多核（multicore）系统/多处理器（multiprocessor）系统能够并行运行，因为系统可以为每个核分配一个单独线程。而单处理器系统只能并发运行。

• 并行：同时执行多个任务
  • 数据并行：将数据分布于多个计算核上，并在每个核上执行相同操作
  • 任务并行：将线程而不是数据分配到多个计算核，每个线程并行执行独特的操作。
• 并发：支持多个任务，允许所有任务都取得进展；线程能够交错执行。

CPU调度器通过快速切换进程，以便每个进程取得进展，造成并行的假象。

Amdahl定律：\(加速比 ≤ \frac{1}{S+\frac{1-S}{N}}\)，其中，S为应用程序中串行执行的占比，1-S自然为并行执行的占比，该系统具有N个处理器核。

多线程

用户线程位于内核之上，管理无需内核支持；而内核线程由操作系统直接支持和管理。

多对一

多对一模型映射多个用户级线程到一个内核线程。

优点：线程管理由用户空间的线程库完成，效率较高。

缺点：一个线程阻塞，整个进程阻塞；该线程无法并行运行在多处理核系统上。

一对一

一对一模型映射每个用户线程到一个内核线程。

优点：提供并发性；允许多个线程并行运行在多处理器系统上。

缺点：创建一个用户线程就要创建一个相应的内核线程，开销影响性能，实现需要限制系统支持的线程数量。

多对多

多对多模型多路复用多个用户级线程到同样数量或更少的内核线程。（内核线程数≤用户级线程数）

优点：可以创建任意多的用户线程，且内核线程能在多处理器系统上并发执行。

该模型的亚种是双层模型（tow-level model），允许绑定某个用户线程到一个内核线程。

线程库

线程库（thread library）为程序员提供创建和管理线程的API。

实现方法：

1. 在用户空间内提供一个没有内核支持的库，所有代码和数据结构都位于用户空间，调用库内的函数只是用户空间的本地调用而非系统调用
2. 实现由操作系统直接支持的内核级的一个库，所有代码和数据结构都位于内核空间，调用库内API函数会导致系统调用

目前主要使用的线程库：

1. POSIX Pthreads，可提供用户级或内核级的库；全局声明数据可以为同一进程的所有线程共享
2. Windows，可提供内核级的库；全局声明数据可以为同一进程的所有线程共享
3. Java，采用宿主系统的线程库来实现；线程对共享数据的访问需要显式安排

多线程创建的常用策略

1. 异步线程：父线程创建子线程后即恢复自身运行，与子线程并发执行，相互独立，很少数据共享
2. 同步线程：父线程在回复执行前等待所有子线程的终止，通常涉及大量数据共享，例如由父进程组合输出子线程计算的结果

隐式多线程（implicit multithreading）

将多线程的创建管理交给编译器和运行时的库来完成，这种策略称为隐式线程。

线程池

线程池的主要思想：在进程开始时创建一定数量的线程，并加到池中等待工作。当服务器收到请求，其唤醒池内的可用线程传递请求，一旦线程完成服务，回到池中等待工作。如果池中没有可用线程，那么服务器会等待。

线程池的优点：

1. 高效。用现有程序服务请求比等待创建线程更快。
2. 限制了任何时候可用线程的数量，保障了容量安全
3. 允许采用不同策略运行任务

OpenMp

大中央调度（Grand Central Dispatch，GCD）

多线程问题

信号处理

UNIX信号用于通知进程某个特定事件已发生。其模式为：特定事件的发生产生了信号->信号被传递给某个进程->进程一旦接收到信号就应处理

信号的接收是同步还是异步，取决于事件信号的来源和原因。

1. 当一个信号由运行程序以外的事件产生，该进程就异步接收这一信号。
2. 同步信号发送到由于导致该信号的同一进程。

信号处理程序有：

1. 缺省的信号处理程序
2. 用户定义的信号处理程序

例如ptrhread_kill()

线程撤销（thread cancellation）

线程撤销是在线程完成之前终止线程。

1. 异步撤销：一个线程立即终止目标线程（他杀）；可能会不会释放必要的系统资源。
2. 延迟撤销：目标线程不断检查它是否应终止，这允许目标线程有机会有序终止自己（教唆自杀）

线程本地存储（Thread-Local Storage，TLS）

每个线程独有的本地数据叫线程本地存储。其与局部变量的区别是，局部变量只在单个函数调用时才可见，而TLS数据在多个函数调用时都可见。TLS类似于静态static数据。

调度程序激活

调度器激活（scheduler activation）是用户线程库与内核之间的一种通信方案，内核提供一组虚拟处理器（LWP）给应用程序，而应用程序调度用户线程到任何可用的虚拟处理器。内核将有关特定时间通知应用程序，该步骤称为回调（upcall），由线程库通过回调处理程序（upcall handler）来处理。

例子

Windows线程

线程一般包括：

1. 线程ID，TID
2. 寄存器组
3. 用户堆栈，内核堆栈
4. 私有存储区域，用于各种运行时库和动态链接库（DLL）

后三种部件通常称为线程上下文（context）。

Linux线程

批处理系统、分时系统、实时操作系统的特点和比较_马小超i的博客-CSDN博客_分时系统,实时系统,批处理系统

操作系统考点之PV操作、信号量_guangod的博客-CSDN博客_操作系统信号量pv操作

操作系统进程状态模型__吟游诗人的博客-CSDN博客_进程的七状态模型

操作系统之多道程序设计_莫之的博客-CSDN博客_多道程序设计

最高响应比优先算法（HRRF）及例题详解_EMT00923的博客-CSDN博客_响应比高者优先调度算法例题

进程典型七大调度算法_emcpper的博客-CSDN博客_常见的进程调度算法有哪些