认识多任务、多进程、单线程、多线程
 
要认识多线程就要从操作系统的原理说起。
 
现在的操作系统都是多任务操作系统，每个运行的任务就是操作系统所做的一件事情，比如你在听歌的同时还在用MSN和好友聊天。听歌和聊天就是两个任务，这个两个任务是“同时”进行的。一个任务一般对应一个进程，也可能包含好几个进程。比如运行的MSN就对应一个MSN的进程，如果你用的是windows系统，你就可以在任务管理器中看到操作系统正在运行的进程信息。
 
一般来说，当运行一个应用程序的时候，就启动了一个进程，当然有些会启动多个进程。启动进程的时候，操作系统会为进程分配资源，其中最主要的资源是内存空间，因为程序是在内存中运行的。在进程中，有些程序流程块是可以乱序执行的，并且这个代码块可以同时被多次执行。实际上，这样的代码块就是线程体。线程是进程中乱序执行的代码流程。当多个线程同时运行的时候，这样的执行模式成为并发执行。
 
多线程的目的是为了最大限度的利用CPU资源。
 
Java编写程序都运行在在Java虚拟机(JVM)中，在JVM的内部，程序的多任务是通过线程来实现的。每用java命令启动一个java应用程序，就会启动一个JVM进程。在同一个JVM进程中，有且只有一个进程，就是它自己。在这个JVM环境中，所有程序代码的运行都是以线程来运行。
 
一般常见的Java应用程序都是单线程的。比如，用java命令运行一个最简单的HelloWorld的Java应用程序时，就启动了一个JVM进程，JVM找到程序程序的入口点main()，然后运行main()方法，这样就产生了一个线程，这个线程称之为主线程。当main方法结束后，主线程运行完成。JVM进程也随即退出。
 
对于一个进程中的多个线程来说，多个线程共享进程的内存块，当有新的线程产生的时候，操作系统不分配新的内存，而是让新线程共享原有的进程块的内存。因此，线程间的通信很容易，速度也很快。不同的进程因为处于不同的内存块，因此进程之间的通信相对困难。
 
实际上，操作的系统的多进程实现了多任务并发执行，程序的多线程实现了进程的并发执行。多任务、多进程、多线程的前提都是要求操作系统提供多任务、多进程、多线程的支持。
 
在Java程序中，JVM负责线程的调度。线程调度是值按照特定的机制为多个线程分配CPU的使用权。
 
调度的模式有两种：分时调度和抢占式调度。分时调度是所有线程轮流获得CPU使用权，并平均分配每个线程占用CPU的时间;抢占式调度是根据线程的优先级别来获取CPU的使用权。JVM的线程调度模式采用了抢占式模式。
 
所谓的“并发执行”、“同时”其实都不是真正意义上的“同时”。众所周知，CPU都有个时钟频率，表示每秒中能执行cpu指令的次数。在每个时钟周期内，CPU实际上只能去执行一条(也有可能多条)指令。操作系统将进程线程进行管理，轮流(没有固定的顺序)分配每个进程很短的一段是时间(不一定是均分)，然后在每个线程内部，程序代码自己处理该进程内部线程的时间分配，多个线程之间相互的切换去执行，这个切换时间也是非常短的。因此多任务、多进程、多线程都是操作系统给人的一种宏观感受，从微观角度看，程序的运行是异步执行的。

多道程序设计和分时
 
 
 
内容
 
 
简单批处理
 
 
多道程序设计
 
 
分时
 
 
 
简单批处理系统
 
 
最早的操作系统？
 
 
自动作业调度：自动从一个运行完的作业转换到下一个作业
 
常驻监控程序（Monitor）：控制作业传输，调度作业运行
 
单道程序设计
 
 
 
 
批处理系统
 
 
批处理：用户将一批作业提交操作系统后就不再干预，由操作系统控制它们自动运行
 
 
批处理操作系统：采用批量处理作业技术的操作系统，单道批处理系统，多道批处理系统
 
 
批处理操作系统不具有交互性，提高CPU的利用率
 
 
 
多道程序系统
 
单用户通常不能总使得 CPU 和设备在所有时间内都忙碌
 
多道程序设计：在内存中同时存在多道作业，在管理程序控制下相互穿插运行
 
通过作业调度(Job Scheduling)选中一个作业并运行， 当该作业必须等待时 (如等待I/O), 切换到另一个作业
 
目的
 
 提高CPU的利用率，充分发挥计算机系统部件的并行性
 
现代操作系统广泛采用多道程序设计技术
 
多道程序和单道程序运行例子
 
 
并行和并发区别
 
并行：两个或者多个作业在同一时刻运行
 
并发：两个或多个作业在同一时间间隔内依次运行， 一个时间段中，有几个作业在同一个处理机上运行，但任一个时刻点上只有一个作业在处理机上运行
 
随着多核处理器的出现，这两个概念并不严格区分
 
分时系统
 
分时系统(或多任务)是多道程序设计的延伸
 
作业分类：批处理作业，交互作业
 
时间片：把一段CPU时间按照固定单位进行分割，每个分割得到的时间段称为一个时间片，每个任务依次轮流使用时间片
 
分时系统
 
 一种联机的多用户交互式的操作系统
 
 一般采用时间片轮转方式使一台计算机为多个用户服务。在单位时间内，每个用户获得一个时间片并运行， 保证用户获得足够小的响应时间，并提供交互能力
 
原理
 
 若某个作业在分配的时间片用完之前计算还未完成，该作业就暂时中断，等待下一轮；此时，处理机让给另一个作业使用。
 
 每个用户好象独占一台计算机（时间片小的原因）
 
第一个分时系统
 
CTSS(Compatible Time-Sharing System)
1962年
第一个分时系统
MIT开发
运行在IBM 7094机
支持32个交互式用户
分时系统例子
 
 
作业
 
下面关于分时系统的叙述错误的是（）。
 
 
A.分时系统主要用于批处理作业
 
 
B.分时系统中每个任务依次轮流使用时间片
 
 
C.分时系统的响应时间好
 
 
D.分时系统是一种多用户操作系统
 
（多选）可以并行运行2个进程的计算机，必须具备的条件有（）。
 
 
A.操作系统支持多道程序设计技术
 
 
B.程序员实现多进程技术
 
 
C.计算机中安装了多个单核处理器或一个多核处理器
 
 
D.计算机中安装了一个单核处理器
 
单道批处理系统的核心思想是把一批作业一次装入计算机。
 
 
A.✓
 
 
B.×
 
分时系统比多道批处理系统的系统开销大。
 
 
A.✓
 
 
B.×
 
多道批处理系统的CPU利用率比单道批处理系统高，但是设备利用率差不多。
 
 
A.✓
 
 
B.×
 
多道程序设计技术和分时技术的联系和区别
 
请从多道程序设计技术和分时技术的共同点和不同点出发，给出至少4个方面的不同和相同之处。
 
相同之处：1.都可以同时处理和执行多个作业。
 
                  2.都充分利用发挥了计算机系统部件的并行性。
 
                  3.都提高了CPU的利用率。
 
                  4.都需要在内存中同时保存多个作业。
 
                  5.分时技术本身就是多道程序设计技术的延伸。
 
不同之处：1.分时操作系统是给不同用户提供程序的使用，而多道程序系统则是不同程序间的穿插运行。
 
                  2.分时操作系统主要是针对于多用户来说的，而多道程序系统主要是针对于多程序来说的。
 
                  3.分时系统要求计算机系统是可交互的，而多道程序系统没有提供用户与计算机系统的交互。
 
                  4.分时系统中CPU的使用权变更比多道系统中频繁得多，因为分时系统需要保证多个用户同时的使用体验，CPU的切换必须非常快；而多道系统只强调效率，单个程序持续占用CPU的时间会长得多。
 
并行和并发的区别，请结合1-2个实例，讨论并行和并发的区别。
 
从定义上来看，并行指的是两个或多个作业在同一时刻同时运行；
 
并发指的是两个或多个作业在同一时间间隔内依次运行。
 
从实例来看，假设有两条队的人排队买咖啡，如果两条中同一行的人可以在同一时刻打到咖啡，这类似于并行；但如果两条队伍的人轮流从唯一一个咖啡机倒咖啡，则一次只能有一个人买到咖啡，这类似于并发。

 
多道程序设计是指？
 
是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插的运行。 两个或两个以上程序在计算机系统中同处于开始到结束之间的状态。这就称为多道程序设计。
 
多道程序技术运行的特征：多道、宏观上并行、微观上串行。
 
多道程序设计必须有硬件基础作为保证。
 
所谓多道程序设计指的是允许多个程序同时进入一个计算机系统的主存储器并启动进行计算的方法。也就是说，计算机内存中可以同时存放多道(两个以上相互独立的)程序，它们都处于开始和结束之间。从宏观上看是并行的，多道程序都处于运行中，并且都没有运行结束；从微观上看是串行的，各道程序轮流使用cpu，交替执行。引入多道程序设计技术的根本目的是为了提高cpu的利用率，充分发挥计算机系统部件的并行性，现代计算机系统都采用了多道程序设计技术。
 
多道程序设计的出现，加快了os的诞生
 
多道程序设计的基本特征：间断性、共享性、制约性。
 
多道程序设计技术
 
多道程序设计技术是指在内存同时放若干道程序，使它们在系统中并发执行，共享系统中的各种资源。当一道程序暂停执行时，cpu立即转去执行另一道程序。
 
[特点]：多道、宏观上并行(不同的作业分别在cpu和外设上执行)、微观上串行(在单cpu上交叉运行)。
 
[多道批处理系统]：将多道程序设计技术应用于批处理系统，就形成多道批处理系统。
 
多道程序设计技术 对 操作系统的形成起到的作用：
 
操作系统在引入多道程序设计技术后，使得系统具有了多道，宏观上并行，微观上串行的特点。
 
多道程序设计主要是使os能更好地对计算机进行管理 。
 
使计算机的硬件资源得到更充分的利用 。
 
在os中引入多道程序设计技术带来的好处：
 
1.提高cpu的利用率
 
2.提高内存和i/o设备利用率
 
3.增加系统吞吐量

 
 
这是 bilibili-[完结] 2020 南京大学 “操作系统：设计与实现” (蒋炎岩) 的课程笔记
 
 
本讲内容：
- 串行程序的状态机模型
- 状态机模型的应用
- 并发程序的状态机模型
- 理解并发程序的执行
 


 
文章目录
 
串行程序的状态机模型
有限状态机（Finite State Machine）
x86-64的栗子
    
状态机模型：应用
应用(1):Time-Travel Debugging
应用(2):Record & Repaly
    
并发程序的状态机模型
:star:理解并发程序的执行
栗子：实现互斥
   
  
 

 
串行程序的状态机模型
 
有限状态机（Finite State Machine）
 
有向图G（V, E）
 
 
节点->状态
 
 
边->状态转换
 
 
边上的label代表执行某个状态
 
 
操作系统上的程序执行时，状态是有限的，
 
寄存器
内存：代码、数据、堆栈（暂时假设内存静态分配）
 
构造有限状态机
 
每个不同的 configuration 都是状态机的节点 
  
s=(M,R) 属于 V，代表某个时刻程序内存/寄存器的快照
16m的内存就有2的24m次方种不同的状态
 
s=(M,R)的下一个状态是执行 M[R[%rip]] 处的指令得到 s_1 = (M_1, R_1) 
  
取出PC指针处的指令、译码、执行、写回数据
(s, s_1) 属于 E
 
 
大部分状态有唯一的后续状态(deterministic)
 
我们学习的大部分算法都是 deterministic 的
 
程序 = 有限状态机
 
不确定的指令可能有多个状态(non-deterministic)的指令可能有多个后续状态
 
 
(时间)rdtsc/rdtscp
 
  
获取处理器的时间戳用于精确定时
 
 
机器状态 rdrand
 
  
处理器自身提供的随机数指令
读取处理器上的白噪声生成随机数
 
// rdrand.c
#include <stdio.h>
#include <stdint.h>

int main() {
  uint64_t val;
  asm volatile ("rdrand %0": "=r"(val));
  printf("rdrand returns %016lx\n", val);
}
 
❯ vim rdrand.c
❯ gcc rdrand.c
❯ ./a.out
rdrand returns da53e8a19ebdb3d1
❯ ./a.out
rdrand returns cb075a76ba90effd
❯ ./a.out
rdrand returns fde2ddfb5c7a2bf3
❯ ./a.out
rdrand returns 10d0889b7c044cdc
 
 
系统调用 syscall
 
  
一般应用唯一不确定的来源
read(fd, buf, size) 返回值不确定、buf中的数据不确定，比如从键盘输入
 
 
x86-64的栗子
 
运行在 ring3（低特权级）的应用程序
 
通用寄存器 16 个 
  
rax\rbx\rcx\rdx\rsi\rbp\rsp
r8 ~ r15
 
PC 指针/机器状态 
  
rip\rflags\cs\ds\es\fs\gs
 
内存 
  
操作系统分配；通过procfs查看
 
 
 
这些状态都能被gdb观察到
 
info registers 列出所有寄存器
/proc/[pid]/maps 有内存映射信息
 
// minimal.S
.globl foo
foo:
  movl $1,	%eax
  movl $1,	%edi
  movq $s,	%rsi
  movl $(e-s),	%edx
  syscall

  movl $60,	%eax
  movl $1,	%edi
  syscall

s:
  .ascii "\033[01;31mHello World\033[0m\n"
e:

// code
.fill 1 << 20, 1, 0xcc

// data
.section .data
.fill 2 << 20, 1, 0xff

//bss
.section .bss
.fill 3 << 20
 
❯ gcc -c minimal.S
❯ ld minimal.o
ld: warning: cannot find entry symbol _start; defaulting to 0000000000401000
❯ ./a.out
Hello World
 
程序可以执行，我们用gdb调试这个程序
 
❯ gdb a.out
(gdb) starti
Starting program: /tmp/tmp/a.out 

Program stopped.
0x0000000000401000 in foo ()
(gdb) info registers  # 查看寄存器状态 
rax            0x0                 0
rbx            0x0                 0
rcx            0x0                 0
rdx            0x0                 0
rsi            0x0                 0
rdi            0x0                 0
rbp            0x0                 0x0
rsp            0x7fffffffdf00      0x7fffffffdf00
...
...
rip            0x401000            0x401000 <foo>
eflags         0x200               [ IF ]
cs             0x33                51
ss             0x2b                43
ds             0x0                 0
es             0x0                 0
fs             0x0                 0
gs             0x0                 0

(gdb) info inferiors # 查看程序的进程信息
  Num  Description       Executable        
* 1    process 14178     /tmp/tmp/a.out    
(gdb) !cat /proc/14178/maps # 查看进程内存中信息
00400000-00401000 r--p 00000000 103:07 538911                            /tmp/tmp/a.out
00401000-00502000 r-xp 00001000 103:07 538911                            /tmp/tmp/a.out
00502000-00702000 rw-p 00102000 103:07 538911                            /tmp/tmp/a.out
00702000-00a02000 rw-p 00000000 00:00 0                                  [heap]
7ffff7ff9000-7ffff7ffd000 r--p 00000000 00:00 0                          [vvar]
7ffff7ffd000-7ffff7fff000 r-xp 00000000 00:00 0                          [vdso]
7ffffffde000-7ffffffff000 rw-p 00000000 00:00 0                          [stack]
ffffffffff600000-ffffffffff601000 --xp 00000000 00:00 0                  [vsyscall]
(gdb) 
 
状态机模型：应用
 
在计算机硬件上的应用：高性能处理器实现
 
超标量处理器 
  
insight ：允许在状态机上跳跃
 
在计算机系统上的应用：程序分析技术 
  
静态分析：根据程序代码推导出状态机的性质
动态分析：检查运行时观测到状态机的执行
 
 
应用(1):Time-Travel Debugging
 
GDB的隐藏功能
 
target record-full 开始记录（需要程序开始执行）
record stop 结束记录
reverse-step/reverse-stepi 时间旅行调试
 
对syscall指令不适用，因为side-effect难以准确定义
 
应用(2):Record & Repaly
 
在程序执行时记录信息，结束后重现程序的行为
 
确定的程序不必记录
假设s0执行1000000条确定的指令之后得到 s1 
  
那么只需要记录 s0 和 1000000
就能通过“再执行一次”推导出 s1
 
 
Record&Repaly: 只需要记录 non-deterministic 的指令的效果（side-effect）
 
(单线程)应用程序 
  
syscall\rdrand\rdtsc
 
(单处理器)操作系统 
  
mmio\in\out\rdrand\rdtsc\中断
QEMU内置了 record/repaly
 
 
并发程序的状态机模型
 
系统中有n个线程，则并发程序的状态：
 
s= (M,R1,R2,…,Rn)
并发程序执行的每一步都是不确定的
 
多线程程序可以看成是若干个单线程程序。在任意时刻，状态的转换就是 “选择一个线程执行一条指令”：
 
选择线程 1 执行：(M,R1)→(M1′,R1′)，得到状态 (M1′,R1′,R2,…,Rn)；
选择线程 2 执行：(M,R2)→(M2′,R2′)，得到状态 (M2′,R1,R2′,…,Rn)；
…
选择线程 n 执行：(M,Rn)→(Mn′,Rn′)，得到状态 (Mn′,R1,R2,…,Rn′)；
 
 
n 个线程的并发程序，若每个线程执行 m 条指令，就算所有指令都是确定的，不同的执行顺序也多达 n^O(mn)，这个状态机太大了。
 
就算是合并确定的状态，只要有共享内存，状态空间就很难画出了
 
而且还不考虑编译优化、多处理器之间的可见性等问题
 
刚才介绍了各种状态机的应用，都需要为多线程重新设计
 
共享内存是 non-determinism 的重要来源
time-travel debugging/record & replay 需要记录内存访问的数据
自动测试要考虑如何探索线程调度
… …
 
⭐️理解并发程序的执行
 
程序
 
指令序列的静态描述 
  
是非常概括、精简的
所以行为有时候难以理解——循环、递归、分支的组合和不确定的共享内存
 
 
状态机
 
所有动态行为的集合 
  
静态时的分支、循环全部被展开成了顺序结构
大量的冗余和重复(verbose)
行为明确、容易理解
 
 
栗子：实现互斥
 
希望实现 lock/unlock 保证：
 
（顺序）编译优化不能越过 lock/unlock
（原子）lock 返回后，unlock之前，其他线程的lock不能返回
（可见）unlock 之前执行的写操作，在unlock之后对其他线程可见
 
void do_sum(){
    for(int i = 0; i < n; i++){
        lock(); // 保证顺序、原子性、可见性
        // critical section；临界区
        sum++;
        // lock和unlock之间的代码被保护起来了
        unlock();
    }
}
 
Peterson 算法: 代码
 
int turn, x = 0, y = 0;

void thread1() {
  [1] x = 1;
  [2] turn = T2;
  [3] while (y && turn == T2) ;
  [4] // critical section
  [5] x = 0;
}

void thread2() {
  [1] y = 1;
  [2] turn = T1;
  [3] while (x && turn == T1) ;
  [4] // critical section
  [5] y = 0;
}
 
假设：机器每次原子地执行一行代码，内存访问立即可见。
 
证明：
 
Safety: 坏事永远不会发生。
 
不存在一条从初始节点到错误状态的路径。
 
Liveness: 好事永远会发生。
 
不存在无穷长的路径。