Operating System

概论

操作系统课程：

• 最小的
• 原理一致

定义

一个软件体，能让程序运行更加容易（甚至是同时运行多个），能让程序共享内存，能让程序与设备交互，等等

关键词：管理、服务

精准的定义毫无意义

演变

• 硬件
• 软件
• 管理软件的软件（OS）

1946年2月14日

• 逻辑门 —— 真空电子管
• 存储器 —— 延迟线内存（击鼓传花，小丑扔球）
• 输入——打孔纸带，输出——指示灯
• 不需要操作系统 —— 程序用指令操作硬件

1950s

• 逻辑门 —— 晶体管
• 更大的内存 —— 磁芯（小磁针方向代表比特信息）
• 更多IO
• 当IO速度严重低于处理器速度时，中断技术出现（1953）

此时计算机价格十分昂贵，一个学校一台，如何分配给各个院系使用？

需要管理多个程序的执行，操作系统产生（多用户排队共享计算机）

保存结果到卡片里？——文件

一个卡片是什么？——任务

1960s

• 处理器更快（还是一个CPU）
• 内存变大 —— 可以同时载入多个程序
• 多个程序在内存，一个CPU。程序是分为CPU时间和IO时间的，也就是说有一段时间，我不需要CPU，而此时内存里又有另一个程序，那么让CPU去执行另一个程序，是非常自然的。——程序切换、调度；多道程序，进程的概念。
• 有了进程概念，就想让不同进程彼此隔离（程序都有bug）——虚拟地址
• 操作系统要有进程管理的API

当已经能够切换进程了，那如果加上定时切换呢？

之前是进程走了，通知CPU找其他人；现在是OS管理，OS定时每个进程运行多长时间就下去——现代OS雏形（Multics (MIT, 1965)）分时系统

1970s

基本与今日无差别

1970PASCAL，1972C语言

UNIX（Multics是多用户，要分时，而UNIX则是单用户，与其针锋相对）

今日

虚拟化硬件资源（管理），为程序提供服务

程序和编译器

程序

什么是程序？

代码角度

状态机。数字系统是状态机，而所有的程序是运行在数字系统上的，因此程序也是状态机

那C程序的状态是什么？

• 状态 = 栈 + 堆

• 初始状态就是main的第一条语句

• 状态迁移 —— 执行一条语句

stack frame = PC + Args

• 状态 = stack frame + 全局变量
• 初始状态 = 全局变量初始化
• 状态迁移 = 栈顶的stack frame的PC指向的语句，PC++
  • 函数调用：栈顶增加一个stack frame，这个frame的PC就是函数入口
  • 函数返回：去掉这个stack frame

二进制

• 状态 = 内存 + 寄存器

如果确定状态，那么始终拿M[R[PC]]的内容，那么状态是一条直线。但是如果存在不同的状态（随机状态），那么就有分叉。

内存是有限的，因此状态也是有限的，如果一直执行下去，一定会回到之前呆过的某个位置。程序循环了起来，怎么退出？

程序是运行在操作系统上的，但所有的程序可以退出。如果只有计算，程序既不能退出，也无法输出到屏幕上。

特殊指令 - syscall

程序大多数都是计算指令。syscall相当于程序将自身所有都交给操作系统，请求操作系统，修改自己的状态机。因为操作系统可以访问所有资源（软硬件资源），进程的意图在os面前清楚显现。由操作系统去和其他东西交互。比如文件，比如创建销毁自身。

指令分为两种，一种是计算，一种是系统调用

因此程序 = 计算 + syscall

一个没有系统调用的例子：

x86-64 架构，共有16个64位通用寄存器

%rsp 是堆栈指针寄存器，通常会指向栈顶位置，
堆栈的 pop 和push 操作就是通过改变 %rsp 的值即移动堆栈指针的位置来实现的。

%rbp 是栈帧指针，用于标识当前栈帧的起始位置

%rdi, %rsi, %rdx, %rcx,%r8, %r9 六个寄存器用于存储函数调用时的6个参数（如果有6个或6个以上参数的话）。

被标识为 “miscellaneous registers” 的寄存器，属于通用性更为广泛的寄存器，
编译器或汇编程序可以根据需要存储任何数据。

%rax 通常用于存储函数调用的返回结果，同时也用于乘法和除法指令中。

return语句的行为：从rsp寄存器中取出八个字节，然后赋值给rip，
之后rsp自增8，相当于pop一个栈帧

当return出错时，要么取rsp时出错，要么赋值给rip时出错，
最终我们发现一个void _start的函数，如果只有一个while循环，能够被操作系统正确执行，
但如果是空函数，却没有办法返回，问题出在初始状态上，进程的初始状态无法返回。
那怎么让状态机停下来？纯粹的计算是不可以的，想正确退出，必须要有系统调用

视角转换

C语言：变量 + 栈帧

ASM：内存 + 寄存器

汇编代码 = compiler（源代码）

编译器将源代码状态机 转换为 二进制代码状态机

编译正确，编译优化？

C代码里面有一些无法优化，正确编译就是保留所有无法优化的部分，其他的所有都可以去掉，这也是优化

优化：保持观测一致性

一般程序

在应用眼里，操作系统就是syscall，这是操作系统提供给应用的API。有了syscall，操作系统也可以管理多个状态机。

所有的程序都是被另外一个程序加载的，执行execve设置初始状态

• 进程管理：fork, execve, exit
• 文件/设备管理：open, close, read, write
• 存储管理：mmap, brk

多处理器编程

从初始开始，如果一直经历确定的状态，那么一定到达了确定

而并发则天然随机

而操作系统是最早的并发程序之一。

并发

并发的基本单位：线程

共享什么？

• 全局变量
• 堆区

不共享什么？

• 局部变量
• 自己的PC

具体执行时，需要选择线程，然后把全局+某个线程，看成一个线程去执行。由于每次都会选择，因此都是不确定的。人天生就是线性走的，但并发要考虑所有的

从状态机的视角理解进程操作

• 进程创建：
  • 在原本的状态机里面加入一个栈帧的链表
• join
  • 某个线程如果进行了join操作，那么他的形式语义就是：如果其他线程尚未结束，那么当执行本线程时，状态自反，不进行任何操作。只有当轮到其他线程并结束时，本线程的状态才可能改变。因此join等待所有运行线程的函数返回。

使用一个小的线程库，我们就可以写出利用多处理器的程序，而操作系统会自动把线程放在不同的处理器上。

• 一个全局变量即可证明线程确实是共享内存
• 使用函数无限递归的小技巧即可确认不同线程拥有独立堆栈，并且还可以近似确立大小

带来的改变

• 原子性的丧失，甚至一条add指令也无法保证

99%的并发问题都可以用一个队列完成，将大任务分成可以并行的小任务

• 顺序

对于编译器来说，当编译优化时，是按照顺序来的。编译器优化时，对内存拥有最终的统一性权限。如果编译器知道最终要写入n，那么之前那些就可以忽略。

编译器对内存访问 “eventually consistent” 的处理，导致共享内存作为线程同步工具失效

• 可见性

int x = 0, y = 0;

void T1() {
  x = 1;
  asm volatile("" : : "memory"); // compiler barrier
  printf("y = %d\n", y);
}

void T2() {
  y = 1;
  asm volatile("" : : "memory"); // compiler barrier
  printf("x = %d\n", x);
}

如果按照状态机解释，那么我们可以得到1 0，0 1，以及1 1，得不到 0 0。但是输出时会有0 0 ，因为处理器也是一个编译器，也是会对指令的顺序去做一定的调整。无论执行哪个，都容易再另一个线程中发生miss，然后就会先输出。

理解并发

处理器默认不保证原子性的操作

只要是两条指令，原子性就很难保证。除非一个线程在读某个状态的时候能立刻写状态

Peterson算法

共享内存模型

之前的错误算法：先读，再写，最后写收尾

但是先读再写，读的只能是历史阶段（过去），因此后写的时候可能会覆盖一个已经改变的状态

（两个人竞争上厕所，一个人看了一眼没人，然后眨眼进去了，但眨眼的这个阶段，可能有别人进去了）

于是将状态改为：先一起写，所有的写结束后，肯定会有一个状态，此时再去读这个状态，有这个不变的再去决定

前提是走一步就执行一步，即立刻写入共享内存

自动状态机

使用python代码实现，实现原理：

def numbers(init=0, step=1):
    n = init
    while True:
        n += step
        yield n

g会生成一个状态机，当执行碰到yield的时候，会返回yield的值。

并且不同于C的，C函数调用就进去了，而且必须等到函数有返回才能出来

但python可以一直保留这个状态机

那用两个变量去接受numbers函数，就相当于创建了两个状态机，也就是两个线程。

互斥

物理世界中，很难有一种机制完全保证某个资源的原子性

实现互斥的根本困难：不能同时写/读共享内存，即使是数字加1，cpu也会拆分

• load：看一眼把眼睛闭上，但看到的东西立刻过时
• store：闭着眼睛动手，但不知道把什么变成了什么

自旋锁

假设硬件能为我们完成一条“瞬间完成”的读+写指令

exange指令，原子交换，即先读再写，类似于交换

有了原子指令后，算法实现相对简单

首先有一个共享变量，如果某一个进程要进入临界区，那么先使得其他进程停止，然后该进程原子得交换自己的局部变量和共享变量（一个读一个写）；其他进程继续进行，但是其他所有进程都无法获得原来的共享变量，只有有共享变量的才能进入临界区。等该进程完成后，再原子地把共享变量放回去。

int table = YES;

void lock() {
  retry:
  	int got = xchg(&table, NOPE);
  	if(got == NOPE) {
      goto retry;
    }
  	assert(got == YES);
}

void unlock() {
  xchg(&table, YES);
}

Simplify:

void lock() {
  while( xchg(&lock, 1))
    ;
}

void unlock() {
  xchg(&lock, 0);
}

Ref

该图片由OpenClipart-Vectors在Pixabay上发布