操作系统-进程与线程
操作系统-进程与线程
L8 操作系统如何管理CPU
CPU上电后经过了取址，译码，执行这几步。给CPU一个初始地址（PC寄存器），然后CPU就开始依次的取址执行。
高级语言中的IO指令和直接用计算指令相比效率低很多，因为IO需要用到磁盘等机械设备，比电子设备速度慢很多。
由于IO指令效率很低，这就导致了在运行程序时CPU的利用率很低。
以烧水为例，前期运行程序就相当于为烧水做准备，IO就相当于烧水的过程，在烧水的时候可以干其他事，当水烧开时水壶会有提醒，也就相当于IO结束，也就是中断，然后可以继续执行程序。
为了提高CPU的效率，可以多个程序一起执行，如果遇到IO就去运行其他程序。
多道程序和单道程序的比较，其中DEV就表示输入输出，比如打印机什么的。
并发的概念：一个CPU交替的执行多个程序。并发的实现需要靠不断的修改PC寄存器
当需要执行其他程序时，需要记录下当前程序的一些信息，以便之后再切回来执行。
引入进程的概念：进程就是执行中的程序，运行的程序，为了提高效率，就要多进程。
运行的程序和静态程序的差异就表现在PCB中。
PCB：Process Control Block。它是进程实体的一部分，是操作系统中最重要的记录性数据结构。它是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。
L9 多进程图像
多进程在用户端的感受：设备正在运行多个程序，每个程序对应一个PID，根据不同的PID号区分不同进程。
操作系统在多个进程使用CPU中的作用：将进程记录好，(每个进程创建一个PCB)然后按照合理的顺序推进(分配资源，进行调度)。
- 操作系统中的main函数在最后创建了一个进程,init就执行了shell，(windows桌面)，shell还可以继续启动另外的进程，然后返回shell再启动其他进程。(比如ls)
1 | if(!fork()){init();} |
用户使用，管理计算机实际上就是管理计算机的进程。
操作系统组织，管理多进程的实貌：一个进程在执行，一些进程处于排队状态，一些进程还有些操作没处理完(可能是需要读写磁盘等)，处理完了才能去排队。
由此可以根据进程的状态进行分类：运行态，就绪态，阻塞态。
进程状态图是进程生存期的详细描述，是认识操作系统进程管理的窗口。
关键问题1：多进程之间是如何进行交替的
当启动磁盘读写时，首先将当前的进程的状态调整为阻塞态，然后把这个进程放在磁盘等待队列上，然后执行schedule()，也就是切换进程的状态。schedule()首先找到可以执行的下一个进程，(选择哪一个作为下一个执行的进程也很有讲究)，然后交换当前进程和下一个进程的PCB。
交替的三个步骤：队列操作+调度+切换
队列操作就是采取FIFO的方式处理等待的进程；调度和切换就是将当前CPU正在执行的进程的信息存在PCB中，然后将CPU下一个要处理的进程的PCB信息传入到CPU中。
关键问题2：如何防止多进程之间的相互干扰
一个想法：利用之前讲过的DPL = 0；这种想法不可行，因为DPL，CPL机制是为了保护操作系统内核的。然而进程本身就是用户态的东西，因此这个想法不可取。
实际的解决方法：利用映射表，通过内存管理，地址映射实现多个进程的分离。每个进程相同的偏移地址对应内存中不同的实际物理地址。
关键问题3：多进程之间的相互合作
考虑打印问题，有的进程负责提交打印任务，有的进程专门负责打印，他们之间如果不能很好的协作就会出错。
再比如一个生产者和消费者的例子，生产者向管道里放数据，消费者从管道中取数据，如果这两个进程一起执行的话，就很有可能出错。
解决这个问题的方法就是当生产者向管道中放数据的时候避免其他进程访问管道，形象点说就是上个锁，选择合理的进程推进顺序。
L10 用户级线程
可以参考：【操作系统】用户级线程（协程）执行原理（程序计数器PC，寄存器EBP、ESP，线程控制块TCB的变化）_The Gao的博客-CSDN博客_线程esp
【Golang】函数调用栈（上）栈帧布局与函数跳转~_哔哩哔哩_bilibili
线程(thread)的特点：保留了并发的优点，同时避免了进程切换的代价。只需要指令进行切换，资源不需要变化(不需要切换映射表)，实际上就是映射表不变而PC指针变化。
线程的切换：把一段指令转移接到另外一段指令上，线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。线程的切换是进程的切换的重要的组成部分。
一个进程里面多个线程：(多个执行程序+一个地址空间)这种方式很实用，比如打开一个网页就是一个进程，网页中显示文字，图片，从服务器接收数据等等这些各自都是一个线程，他们不互相影响。再比如显示文字都是从服务器获取一段文字，然后切换线程将文字显示出来，然后再切换到服务器获取文字。
线程和进程不同的一点：线程不想进程那样需要进行地址的隔离，不同的线程共享一套地址。
比如上面就是一个打开浏览器的线程的程序框架。包括URL，缓存区，通过pthread_create() 创建一些线程，每个线程又包括一些参数或者函数，一步步向下走。yield方法可以暂停当前的线程并且去执行其他的线程，当前线程让出CPU。
TCB：（Thread Control Block），叫做线程控制模块，控制着线程的运行和调度，存储着与该线程有关的信息，如寄存器ESP等的值。
每个线程通过一个TCB来控制，线程之间的切换，两个线程需要两个TCB，两个栈，每个线程需要一个栈来进行存储。
多用户级线程程序执行原理：
如图所示，包含左、右两个线程，先执行左线程。
1.左线程在执行过程中，在执行Yield()函数之前的过程与第四章所述过程一致，即执行A函数，A函数调用了B函数，并将104压入左线程的栈帧。
2.左线程调用Yield()函数，并将返回地址204压入左线程的栈帧中（特别注意：每个线程独享一个栈帧！【这里可以深入想一下两个线程如果使用同一个栈帧会发生什么情况】）。Yield()函数将左线程栈帧的ESP寄存器的值存入左线程的TCB，并将右线程栈帧ESP寄存器的值赋予ESP。这样就实现了线程的交替，切换到右线程。
3.右线程的栈帧为空栈，因此从右线程的第一行指令开始执行，C函数调用D函数，并将304压入右线程的栈帧中。在D函数中调用Yield()函数，并将返回地址404压入右线程的栈帧中。此时切换线程，左线程栈帧弹出204返回地址，即PC=204，从204地址开始执行指令。（【为什么只修改ESP寄存器的值而不修改PC？】因为PC已经压栈了，弹出即可）
4.遇到B函数的右括号，即B函数执行完毕，弹出104，PC=104，从104地址开始执行指令。
5.遇到A函数的右括号，A函数执行完毕，整个进程结束。
扩展：函数调用的思想
本质上就是利用堆栈的思想，当运行一个函数时，首先将函数置于栈中，然后当调用某个函数时，将这个函数按照一定顺序置于栈顶，然后执行这个函数，这时候转换为机器码就是一个call指令。当执行完这个函数之后，通过ret将这个函数弹出栈，再接着执行刚才的函数。
用户级线程存在的一个问题：
如果进程的某个线程进入内核并阻塞的话，会跳出当前的进程，跳转到其他的进程执行，这样用户级线程就体现不出其并发的优势了，操作系统不能为其分配硬件。
而核心级线程是一个系统调用，会进入内核。不存在用户级线程的问题，并发性要更好。
L11 内核级线程
进程必须在内核中，没有用户级进程这一说法，线程分为用户级线程和内核级线程。
MMU：内存管理单元，它是一种负责处理中央处理器（CPU）的内存访问请求的计算机硬件。
多处理器指的是有多个CPU和MMU，多核指的是有多个CPU，但是只有一个MMU；
多核就类似于线程，多个线程可以使用多个核。
并行和并发的区别：
并发是共同出发，交替执行；并行是同时出发，同时执行(线程)。
用户级线程到核心级线程的转变：因为要进入操作系统内核，所以从一个栈变成一套栈。
用户栈和内核栈之间的关系：
所谓的内核级线程实际上也是用户创建的，只不过线程在运行的过程中需要执行内核中的函数，比如一些输入输出等等，进入内核的实现方式就是中断。通过中断进入内核之后，找到相应的TCB，就完成TCB的切换，也就是在内核栈的切换，然后再用IRET指令切换到用户栈。
内核线程switch_to的五段论：
L12 内核级代码实现
本质：用户态通过INT进入内核态，找到TCB表，然后通过switch_to切换TCB，最后通过IRET切换回用户态。
L13 操作系统的那棵树
操作系统的内核kernel：将CPU管理(进程管理)和内存管理合在一起
L14 CPU调度策略
也就是CPU把资源分配给哪个进程的策略。
CPU调度的直观想法：
- FIFO ；谁先进入，先调度谁，但是这样对占用时间特别短的进程好像不太公平。如果进程越短优先级越高的话，可以使系统的周转时间最小。(短作业优先，SJF)
- Priority；任务短的可以适当优先，但是如果有进程虽然时间长，但是大部分时间都在进行IO，这似乎也不是很公平。
设计调度算法的目标：让所有进程都满意。
评价的标准：执行任务时尽快结束任务(周转时间短)；用户操作尽快相应(响应时间短)；系统内耗时间少：(吞吐量高)
不同类型的任务的关注点不同
比如前台任务(比如PPT)更关注响应时间，后台任务(比如压缩文件)更关注周转时间。
不同的关注点之间有矛盾：响应时间小—>切换次数多—>系统内耗大—>吞吐量小
IO约束性任务和CPU约束性任务共存先执行IO约束型比较合理，因为这样只需要一小段时间执行IO约束性运算，其余大部分时间都能进行IO，同时切换到CPU约束性任务，这样效率比较好。
适当的进程切换可以提高效率，但是切换的实现应该尽可能简单，切换的时间过长效率反而会降低。
为了减小响应时间，引入了时间片的思想
不同的进程根据时间片来轮转调度，这样可以减小响应时间。(RR)
前台任务和后台任务共存的方法
前台采取RR调度，执行完了再调度后台任务，后台采取SJF调度方法。
L15 一个实际的schedule函数
while循环的作用就是找到最大的counter，如果找到了，就跳转到next；counter就代表优先级
后面的循环负责counter的修改，counter越大优先级越高，c == 0 代表所有的时间片都用完了。
counter承担了时间片和优先级的作用。最大的counter即阻塞时间最长的进程(IO进程)。
这也使得IO约束性进程比CPU约束性进程的优先级高，符合我们的需求。时间片的设计满足了IO约束性进程的需求，由于具有时间片，时间片时间很短，因此短的进程一定比长的进程先执行完，近似实现了SJF
同时每个为每个进程分配的时间片会随着阻塞的时间而延长，但是有一定的界限。
L16 进程同步与信号量
进程合作：多进程共同完成一个任务。
进程不是一直在执行的，有时候需要停下来等待一个指令，其他进程执行了之后会给出这个指令，然后这个进程再执行。
进程同步指的就是多个进程合理有序的执行，信号是为了告诉进程该执行了。
(1) 缓冲区满以后生产者P1生产一个item放入，会sleep信号
(2) 又一个生产者P2生产一个item放入，会sleep
(3) 消费者C执行1次循环，counter==BUFFER_SIZE-1，发信号给P1，P1 wakeup
(4) 消费者C再执行1次循环，counter==BUFFER_SIZE - 2，P2不能被唤醒
这就是信号存在的问题。首先生产者共享缓存区，缓存区满了，消费者只能唤醒一个生产者P1，而不能唤醒P2。消费者必须知道有几个生产者在睡觉，因此引入了信号量的概念。
从信号到信号量：
不应该只有等待信号，发信号，对应睡眠和唤醒，还应该记录一些信号的状态，sem表示信号量。
(1) 缓冲区满，P1执行，P1 sleep，sem = -1
(2) P2执行，P2 sleep sem = -2
(3) C执行1次循环，wakeup P1 sem = -1
(4) C再执行1次循环，wakeup P2 sem = 0
(5) C再执行1次循环，sem = 1
生产者生产就要空闲内存就减少1，消费者消费空闲内存就加上1；mutex代表互斥锁，当生产者工作时将数据写入文件中，这时候mutex值就是0了，如果其他进程再调用，mutex变成-1这时进程就进入休眠状态了。
L17 信号量临界区保护
如果不对信号量进行保护的话，当生产者和消费者同时修改信号量时，就会出错。
比如上面这个例子，第j次执行是正确的，第i次执行是错误的。
解决这种竞争关系的直接想法：加锁。p1对empty进行操作时上锁，操作完了再把锁去掉。
临界区代码的保护原则：互斥，如果一个进程在临界区执行，其他进程不允许进入。
好的临界区保护规则：有空让进，有限等待。
两个进程的方法：Peterson算法，结合了标记和轮转的思想，flag为标记，turn为轮转.
Peterson算法的简单分析_醋姑娘的博客-CSDN博客_peterson算法
flag[0] = true;表示进程P0想进入临界区, turn = 1表示现在轮到进程1进入临界区了.
L18 信号量的代码实现
L19 死锁处理
死锁的产生，出现了环路的现象，多个进程之间需要互相等待导致谁也无法执行的情况。1号进程要执行需要2号进程先执行，2号进程执行又需要1号进程，例子如下：
假如生产者先上锁，再改变信号量。首先mutex变成0，如果信号量为0，执行后变为-1，进程进入阻塞态，这时候执行Consumer，也是首先mutex变为 -1，不能执行，这时候就进入了死锁。如果想增加信号量必须Consumer执行，之后Producer才能执行同时解锁。因此这就造成了死锁现象。
死锁的成因：
进程占有了一些资源，又不释放，同时再去申请其他资源。各自占有的资源和互相占有的资源形成了环路等待。
死锁的四个必要条件：
互斥占用，不可抢占，请求和保持，循环等待。
死锁的处理方法概述：
- 死锁预防：
- 在进程执行前，一次申请所有需要的资源
- 资源申请必须按序进行
- 死锁避免：
- 银行家算法，所有进程存在一个可完成的执行序列P1, …Pn，则称系统为安全状态。
死锁检测 + 恢复
- 发现哪里出现了死锁，就进行回滚，直到解决死锁。
死锁忽略
- 实际中最常用的，因为死锁的概率很低，重启电脑就行了。
信号量相关：
P操作顺序执行下述两个动作:
①信号量的值减1，即S=S-1;
②如果S≥0，则该进程继续执行;
如果S＜0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待(直至其它进程在S上执行V操作，把它释放出来为止)。
V操作顺序执行下述两个动作:
①S值加1，即S=S+1;
②如果S＞0，则该进程继续运行;
如果S≤0，则释放信号量队列上的第一个PCB(即信号量指量指针项所指向的PCB)所对应的进程(把阻塞态改为就绪态)，执行V操作的进程继续运行。
1.PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：
P（S）：①将信号量S的值减1，即S=S-1；
②如果S>0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。
V（S）：①将信号量S的值加1，即S=S+1；
②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。
2.PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。
什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。