哈工大操作系统-2-进程与线程

本文最后更新于289 天前，其中的信息可能已经过时，如有错误请发送邮件到cishaxiatian@gmail.com

CPU管理的直观想法

fprintf是一条IO指令，这个例子说明如果把IO指令换成一个计算指令后，两者的速度差距相当大，IO指令时间长，说明了执行一条IO指令的时间分为计算一大堆指令得到一条IO指令，但是如果以后的结果要依赖于多个IO指令的时候，此时CPU并不能得到充分的利用，最好是把等待的时间取消掉，用来做其他的事情(中断的引出，多线程等)，此时CPU利用率高，至此管理好了CPU

注意紫色阴影内容！！！

多进程图像

PCB(Process Control Block): 用来记录进程信息的数据结构

switch_to具体实现如下：

进程的调度有 FIFO(公平) 和 Priority(优先级)

这里用一个结构体来存储一些reg的信息，且这里选择用汇编来编写，而非c语言汇编能用来进行精细的操作，c语言不好实现

通过对物理储存地址的重映射地址，解决上述问题：

所以引出了锁这个概念，使进程不能随意切换，需要有一定的规则！！！

用户级线程

线程在进程的内部，其中切换线程只需要PC值的跳转即可，无非切换映射表，达到资源的高效利用(可以理解为简单的中断，映射表在内存中不用切换)

pthread_create函数:创建多个线程

Yield函数：进行线程的交替执行

达到了同时触发多个线程交替执行

如果这里使用的是一个栈来管理两个线程，则在执行完蓝色Yield后的执行红色Yield,则会跳转到204去执行，然后在执行204后，执行 } ret 又触发弹栈，弹出404执行404处，！！！进行了跨线程操作！！！违规！！！，只有Yield可以跨线程

解决该问题就是一个线程对应一个栈，各自管理自己的，避免出现违规操作

名词解释

TCB简介 操作系统中一个线程对应着一个TCB（Thread Control Block），叫做线程控制模块，控制着线程的运行和调度。

TCB组成 1、threadID：线程的唯一标识。 2、status：线程的运行状态 3、register：线程关于CPU中寄存器的情况 4、PC程序计数器：线程执行的下一条指令的地址 5、优先级：线程在操作系统调度的时候的优先级 6、线程的专属存储区：线程单独的存储区域 7、用户栈：线程执行的用户方法栈，用来保存线程当前执行的用户方法的信息 8、内核栈：线程执行的内核方法栈，用来保存线程当前执行的内核方法信息。

也就是通过esp指针来确定出栈的值，进行赋值给TCB x ,进行跳转

错误结果：

如果红色部分不去掉，则会跳到204去执行，204执行完后会执行 } 也就是ret，进行弹栈，弹出204后又执行204，导致红色Yield的 } 不能执行

正确结果：

返回的Yield中的jmp不跳转，则弹出204，204执行完后执行 } 后进行弹栈，弹出104顺利执行！

用户级线程在用户态中如果切换了线程，原线程需等待，经过内核的响应再返回去，如果发生操作则无响应，也就是卡住了。

核心级线程中的TCB在内核中，如果原线程等待，则直接在内核中切换，无需等待。

并发性：核心级线程 > 用户级线程

Yield(用户级)在核心级线程中为Schedule(核心级)

内核级线程

多处理器 ：多个CPU，一个CPU一个MMU(映射表)

多核：一个CPU，处理多个线程，用的

用户级切换：首先TCB切换，随后根据TCB切换用户栈

核心级切换：首先TCB切换,随后根据TCB切换一套栈，内核栈切换的同时用户栈也要切

INT 中断进内核栈

IRET 出内核栈回到用户栈

在线程切换时，先找到下一个线程(next),随后执行switch_to函数，将当前线程的esp和下一个线程的esp代入，TCB在内核态中，switch_to函数作用如图。

？？？？：代表的作用尤为重要

五段论很重要

左边代码就是为了实现右边的图，先申请一段内存给TCB，将内核态线程建立好，传入参数后使得用户态线程和内核态线程进行联系。

内核级线程实现

五段论 == 数字标出的五段

利用一个函数中嵌套fork()函数进行用户态切换到内核态的解释

将_NR_fork这个系统调用号存到 eax 中
执行 INT 0x80 后 PC 值自加1

注意:

在执行INT 0x80这个中断的时，没有进入内核态，是执行完后才进入内核态，

先把当前的栈 ss:sp 压入栈中，且ss:sp指向的是用户栈,其中ss为用户栈的栈首，sp指向用户栈的尾部

随后把当前的cs:sp压栈，也就是？？表示的

在执行完 0x80 后执行中断处理函数(_system_call)

_system_call ：再进行压栈，即原来用户态的一些寄存器
call sys_call : 调用system_fork表，在内核态中执行产生中断的真正效果
cmpl $0,state(%eax) : 如果是0则表示就绪。非0则表示阻塞了
cmpl $0,counter(%eax) : 查看时间片是否为0，为0则进行切换
je指令 ：判断是否相等

这里五段论的中间三段论只需要ljmp指令即可完成，编程简单，但是是封装好的，把 原tss 暂存，把 新tss 代入 CPU 中

TSS（Task State Segment）概述 作用: TSS 是 x86 架构中的一种数据结构，用于存储任务（任务可以看作是一个线程或进程）在切换时的上下文信息。上下文信息包括处理器寄存器的内容、堆栈指针、任务的状态等。

通过 TSS，处理器可以在任务之间快速切换，而不需要手动保存和恢复任务状态。

TSS 存储的信息通常包括 : CPU 寄存器的内容（如 EAX, EBX, ECX, 等）堆栈指针（SS 和 ESP 寄存器）段寄存器内容（CS、DS、ES、FS、GS、SS） I/O 权限位图和其他任务相关的控制信息任务链接字段，用于多任务嵌套（某任务切换到另一个任务时使用）

红色方框就是创建一个子进程，copy父进程的reg信息，基本一模一样，而且参数非常多，也就是父进程reg信息

这里不能使用malloc函数，应为该函数在用户态中,在copy_process中需要使用的是内核态的创建内存空间函数，即get_free_page() (创建页)

get_free_page()具体实现是mem_map

第一行代码的结果：申请的内存空间就是我们的PCB

解释：

get_free_page 是一个常见的函数名，用于操作系统内存管理子系统中分配一个空闲的物理页面（通常是 4KB 大小）。在 Linux 内核中，mem_map 是一个用于跟踪物理内存页面的结构

get_free_page函数可以通过 mem_map 来找到并分配一个空闲的页面。

随后就是初始化内核栈，黄色部分为PCB，上面的白色部分就是内核栈

父进程 和 子进程 怎么区分：通过eax, eax == 0 ？子进程：父进程

总结：

操作系统的那棵“树”

从打印一个A后打印一个B的代码开始了解

main()
{
    if(!fork()){while(1)printf("A");}
    if(!fork()){while(1)printf("B");}
    wait();
}

在进入内核时,int 0x80 对应的是 system_call() ，执行 system_call() 就要执行 sys_fork,执行sys_fork就要执行 copy_process ，而在copy_process 就要执行 reg 的保存，以及 tss 的切换。

p = (PCB *)get_free_page();   //创建一个新的PCB
p -> tss.esp0 = p+4k; //创建一个新的栈
p -> tss.esp = esp;
p -> tss.eax=0; p -> tss.eip =eip;...   //eip是父进程的
    //也就是创建子进程的 eip 和父进程在执行时候的一样，与父进程共同执行

目前打印A的进程可以执行了，但是没有开始执行，需要在返回的时候调用reschedule 让其开始执行。

注意！！！

此时父进程没有被打断，时间片还有很长，致使进行执行下一行代码，即创建 打印B 的子进程的栈。

目前打印A 和打印B 的子进程都创建好了，已经形成了队列。随后执行代码 wait() 等待父进程跑完

红色 —- 选择进程的算法
蓝色 —- 切换到下一个进程(这里是父进程切换到打印A的进程)

目前的情况是一直打印A，我们需要一个时钟中断进入内核态中去执行schedule() 去切换到打印B的进程

利用时间片等于 0 的时候进行 时间片流转 达到利用 schedule 和 switch_to 进行 A 和 B 的子进程来回切换。

CPU调度策略

如果io约束和cpu约束要分优先级的话，则io约束的优先级高

SJF(短作业优先) ： 保证了平均周转时间最小

RR(时间片流转) : 使得各个任务平等，控制响应时间

取 RR 和 SJF 算法的精华诞生的算法用来解决这个问题在下一章给出！！！

一个实际的schedule函数

把PCB设置为一个数组，利用从后往前遍历找到最大的counter,且该进程为就绪态，随后跳出直接执行 switch_to(next)

counter 既可以作为优先级调度，也可以作为时间片流转进行调度，两个东西用的一个变量

for( p=&LAST_TASK ; P>&FIRST_TASK;--P)
    (*p)->counter=((*p)->counter>>1)
                    +(*p)->priority;}

这里代码表示控制所有的进程的counter

((*p)->counter>>1) 也就是 counter 除以2

(p)->counter=((p)->counter>>1)+(*p)->priority;这里表示就绪态的counter重置，并且使阻塞态进程(IO进程)将要进入就绪态时的优先级比原来的就绪态的优先级高

下一次阻塞态的进程的 counter 是原来进程counter + counter / 2，做出优先级越来越大的效果，实现动态的优先级功能

功能：将一个进程的时间片自减并且到 0 时自动进行中断跳转，使得做出时间片轮转的效果

counter >> 1,也就是除以2不是随便写的，除3也可以但是没有除2快

假设一个进程一开始的 counter = p ,也就是最大优先级无线接近于 2p,这是一个收敛的过程

$$ S = p + \frac{p}{2} + \frac{p}{4} + \frac{p}{8} + \dots $$

进程同步与信号量

通过一个例子来表示进程之间的合作

这里提出一个小问题，当生产者的速度大于消费者的时候，也就是当内存缓冲区满了，有新进程的加入需要阻塞等待，但是每次检查的时候只能测试出是否阻塞，其只能控制一个销售者和生产者的关系，多余的生产者进程会一直阻塞等不到唤醒提示

什么是信号量?

记录一些信息(量)，并根据这个信息决定睡眠还是唤醒(信号)。

这里的 sem 表示内存缓冲区的量

负数 (-1) -> 表示此时缓冲区满，欠一个进程，表示一个进程睡眠

0 -> 表示此时缓冲区刚刚好， 不多不少

正数 (1) -> 表示此时缓冲区还能再来一个进程，进行执行

这里补充V 函数的代码

V (semaphore s){
    s.value ++;
    if(s.value <= 0)
        wakeup(s.queue); 
}

补充一个易于理解的办法：

令牌桶： 限流：计数器、漏桶、令牌桶三大算法的原理与实战（史上最全）_漏桶算法-CSDN博客

互斥锁： 多线程的同步与互斥（互斥锁、条件变量、读写锁、自旋锁、信号量）_线程和互斥-CSDN博客

信号量临界区保护

给进程的信号量上锁，使其在某一刻时，信号量进行原子操作，上锁就是为了保护信号量正常修改

现在要解决的问题是规则有了，但是怎么实现好的保护原则很重要

总结：

轮换法的缺点：把turn交给对方后，对方迟迟不肯使用，导致我方也无法使用

标记法的缺点：在对方标记的同时，我方也进行了标记，导致二者进入僵持状态

将二者中和一下，就是Peterson算法

利用turn的二值化进行能否进入临界区的判定，临界区只有一个进程可以进入，此时还需要一个flag来判定另一个进程的标记是否有效，有效则当前进程不进入临界区

turn是用来限制自己的(当前进程)。如果对方打标记了，并且tuen也符合自己的规则，则自己一直空转

在进程切换的时候需要调度，也就是时间片用尽，进行schedlue()中断函数调度，如果我们选择关闭中断了，也就是不进入schedule()函数调度，不进入中断。实现保护进程的功能

TestAndSet ：这个函数是硬件函数实现的，具有原子性，即一次执行完毕

总结：临界区用来保护信号量，临界区可以用、面包店算法，开关中断法，硬件原子指令，使信号量的语义正确，通过信号量的正确来实现进程同步

信号量的代码实现

(2)是一个生产者往 文件(fd)中写入 i 个数(这里为五个)，每个数字 四个字节

sem_wait() 是找到有没有空的缓冲区

如上图最后所示

首先是cli(),关闭中断

随后计算出缓冲区value–是否小于0，如果小于0，证明缓冲区满了，自己需要阻塞，把自己放入队列中，随后切换schedule()到别的进程去

最后是sti()，打开中断。实现原子操作

bh -> 申请的内存空间，用来读磁盘上的数据

b_lock -> 是一个信号量，相当于一个锁

**p : 指向队首

tem = *p : 图示中空白方块表示 tem

*p current：表示当前进程放入这个阻塞队列中，且tmp是存储在内核栈中的

总结：通过 tmp 作为中间变量的保存值，有点像交换两个数中的t的功能

if –> 是将阻塞队列中第一个唤醒的机制

while –> 是将阻塞队列中所有的进程唤醒的机制

死锁处理

执行完成后，Available是累加的过程，即Available + Allocation

实例：

总结: