操作系统之进程

进程概念学习

进程的组成

一个进程应该包括:

程序的代码
程序处理的数据
程序计数器的值，指示吓一跳将运行的指令
一组通用的寄存器的当前值，堆，栈
一组系统资源（如打开的文件）
总之，进程包含了正在运行的一个程序的所有状态信息。

进程与程序的联系

程序是产生进程的基础
程序的每次运行构成不同的进程
进程是程序功能的体现
通过多次执行，一个程序可对应多个进程，通过调用关系，一个进程可包括多个程序。

进程与程序的区别

进程是动态的，程序是静态的，程序是有序代码的集合，进程是程序的执行，进程有内核态/用户态
进程是暂时的，程序是永久的，进程是一个状态变化的过程，程序可以永久保存
进程与程序的组成不同：进程的组成包括程序，数据和进程控制块（即进程状态信息）

进程的特点

动态性：可动态的创建，结束进程；
并发性：进程可以被独立调度并占用处理机运行：并发并行
独立性：不同进程的工作不相互影响（通过页表，使得不同的进程访问不同的地址空间）
制约性：因访问共享数据/资源或进程间同步而产生制约

PCB

描述进程的数据结构：进程控制块

（Process Control Block， PCB）

操作系统为每个进程都维护了一个 PCB，用来保存与该进程有关的各种状态信息。PCB 是进程存在的唯一标志。

进程的创建：为该进程生成一个 PCB

进程的终止：回收它的 PCB

进程的组织管理：通过对 PCB 的组织管理来实现

PCB 构成

pcb 包含以下三大类信息

进程标识信息

如本进程的标识，本进程的产生者标识（父进程标识）用户标识
处理机状态信息保存区：保存进程的运行现场信息
1. 用户可见寄存器：用户程序可以使用的数据，地址等寄存器
2. 控制和状态寄存器：如程序计数器（PC），程序状态字（PSW）
3. 栈指针：过程调用/系统调用/中断处理和返回时需要用到它。
进程控制信息
1. 调度和状态信息：用于操作系统调度进程并占用处理机使用
2. 进程间通信信息：为支持进程间的与通信系统相关的各种标识，信号，信件等这些信息存在接收方的进程控制块中
3. 存储管理信息：包含了有指向本进程映像存储空间的数据结构
4. 进程所有资源：说明由进程打开，使用的系统资源，如打开的文件等
5. 有关数据结构连接信息：进程可以连接到一个进程队列中，或连接到相关的其他进程的 PCB

PCB 的组织方式

链表（性能更好）：同一状态的进程其 PCB 成一链表，多个状态怼用多个不同的链表，各状态的进程形成不同的链表：就绪链表，阻塞链表

方便动态的创建和删除进程
索引表：同一状态的进程归入一个 index 表(由 index 指向 PCB)，多个状态对应多个不同的 index 表，各状态的进程形成不同的索引表：就绪索引表，阻塞索引表

进程的生命周期

进程创建

引起进程创建的三个主要事件：

系统初始化时
用户请求创建一个新进程
正在运行的进程执行了创建进程的系统调用

进程运行

内核选择一个就绪的进程，让它占用 CPU 并执行

进程等待

在以下情况下，进程等待(阻塞)：

需要并等待系统服务，无法马上完成
启动某种操作，无法马上完成
需要的数据没有到达（比如等待读取文件，此时进程等待，将 CPU 让出给其他等待的进程执行）

进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生

进程唤醒

被阻塞进程需要的资源可被满足
被阻塞进程等待的事件到达
将该进程的 PCB 插入到就绪队列

进程只能被别的进程或操作系统唤醒

进程结束

在以下四种情况：

正常退出(自愿的)
错误退出(自愿的)
致命错误(强制的)
被其他进程所杀(强制的)

进程状态变化模型

进程的三种基本状态：

进程在生命结束前处于且仅处于三种基本状态之一

不同系统设置的进程状态数目不同

运行状态(Running)：当一个进程正在处理机上运行时

就绪状态(Ready)：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行

等待(又称阻塞状态 Blocked)：一个进程正在等待某一事件而暂停运行时。如等待某资源，等待输入/输出完成

进程的其他基本状态

创建状态(New):一个进程正在被创建，还没有被转到就绪状态之前的状态

结束状态(Exit): 一个进程正在从系统中消失时的状态，这是因为进程结束或者由于其他原因所导致

进程挂起模型

进程在挂起状态时，意味着进程没有占用内存空间。处于挂起状态的进程映像在磁盘上。

挂起状态

阻塞挂起状态(Blocked-suspoend): 进程在外存并等待某事件的出现
就绪挂起状态(Ready-suspend): 进程在外存，但只要进入内存，即可运行

与挂起相关的状态转换

挂起（Suspend）把一个进程从内存转到外存，可能有以下几种情况：

阻塞到阻塞挂起：没有进程处于就绪状态或者就绪进程要求更多内存资源时，会进行这种转换，腾出内存空间提供给就绪进程使用
就绪到就绪挂起：当有高优先级阻塞(系统认为会很快就绪)进程和低优先就绪进程时，系统会选择挂起低优先级就绪进程
运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态；

在外存的状态转换

阻塞挂起到就绪挂起：当有阻塞挂起进程因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程

状态队列

由操作系统来维护一组队列，用来表示系统当中所有进程的当前状态
不同的状态分别用不同的队列来表示(就绪队列，各种类型的阻塞队列)
每个进程 PCB 都根据它的状态假如到相应的队列中，当一个进程状态发生变化时，它的 PCB 从一个状态队列中脱离出来，加入到另一个队列

上下文切换

当一个进程让出 CPU 资源给另一个进程执行时，被称作进程上下文切换(context-switch)

当一个进程让出 Cpu 资源时进行上下文切换，将 cpu 当前的寄存器里的信息保存到自己的 pcb 当中，然后准备执行的进程会将自己的 pcb 里的信息 load 到寄存器当中，完成上下文切换

线程管理

定义: 进程当中的一条执行流程。

进程是系统进行资源分配和调度的基本单位，而线程则是程序执行的最小单位，线程生活在进程中。

从资源组合的角度: 进程把一组相关的资源组合起来，构成了一个资源平台(环境),包括地址空间(代码段，数据段),打开的文件等资源

从运行的角度: 代码在这个资源平台上的一条执行流程(线程)

相对于进程有 PCB，线程也有 TCB(线程控制块),只负责执行流程相关的一系列信息：

PC(程序计数器)

SP(栈)

Registers(寄存器) 需要寄存器来保存控制流的执行状态

公有的部分:代码，数据，堆

线程的优点

一个进程中可以同时存在多个线程
各个线程之间可以并发地执行
各个线程可以共享地址空间和文件等资源

线程的缺点

一个线程崩溃，会导致其所属进程的所有进程崩溃

进程 API

fork

系统调用 fork() 用于创建子进程

子进程并不是完全拷贝了父进程。具体来说，虽然它拥有自己的地址空间（即拥有自己的私有内存），寄存器，程序计数器等，但是它从 fork()返回的值是不同的，父进程获得的返回值是新创建子进程的 PID，而子进程获得的返回值是 0。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc,char *argv[]){

    printf("hello world (pid:%d)\n",(int)getpid());
    int rc = fork(); 
    if (rc < 0 ) {
        fprintf(stderr,"fork failed\n");
        exit(1);

    } else if (rc == 0){
        printf("hello, I am child (pid:%d)\n",(int)getpid());
    
    } else {
        printf("hello, I am parent of %d (pid:%d)\n",rc,(int)getpid());
    }
    return 0;
}

wait

有时候父进程需要等待子进程执行完毕，这项任务由 wait()系统调用来完成

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc,char *argv[]){

    printf("hello world (pid:%d)\n",(int)getpid());
    int rc = fork();
    if (rc < 0 ) {
        fprintf(stderr,"fork failed\n");
        exit(1);

    } else if (rc == 0){
        printf("hello, I am child (pid:%d)\n",(int)getpid());
    
    } else {
        int wc = wait(NULL);
        printf("hello, I am parent of %d and wait: %d (pid:%d)\n",rc,wc,(int)getpid());
    }
    return 0;
}

exec

由于 fork 只是运行了相同程序的拷贝，如果我们想让子进程运行不同的逻辑代码，exec()正好做这样的事

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc,char *argv[]){

   printf("hello world (pid:%d)\n",(int)getpid());
   int rc = fork();
   if (rc < 0 ) {
       fprintf(stderr,"fork failed\n");
       exit(1);

   } else if (rc == 0){
       printf("hello, I am child (pid:%d)\n",(int)getpid());
       char *myargs[3];
       myargs[0] = strdup("wc"); //调用wc程序
       myargs[1] = strdup("exec.c");
       myargs[2] = NULL;
       execvp(myargs[0],myargs);
       printf("this shouldn't print out");
   
   } else {
       int wc = wait(NULL);
       printf("hello, I am parent of %d and wait: %d (pid:%d)\n",rc,wc,(int)getpid());
   }
   return 0;
}

进程调度

操作系统在进行进程调度的时候，根据什么样的调度指标来进行调度的呢？

T ~~周转时间~~ = T ~~完成时间~~ - T ~~到达时间~~ (周转时间)

T ~~响应时间~~ = T ~~首次运行~~ - T ~~到达时间~~ (响应时间)

先进先出(FIFO)

先到的先执行，优点：简单容易实现，缺点：如果前面的任务执行时间过长，则会导致平均周转时间较高。这个问题被称作护航效应

假设 A 执行完需要 100s, B 需要 10 秒，C 需要 10 秒

(100 +110+120) /3 = 110

最短任务优先(SJF)

先运行最短的任务，然后是次短的任务，如此下去。

这个时候平均周转时长就降低了,最短任务优先算法的调度原则是平均周转时间。

(10+20+120) /3 = 50

似乎在理论上，sjf 确实是一个最优调度算法,但先明确一点，那就是 sjf 是非抢占式的，也就是说，如果 ABC 不同时到达的话，还是会根据先进先出的来。

最短时间完成优先(STCF)

幸运的是，有一个调度程序是这么做的：向 SJF 添加抢占，称为最短时间完成优先 Shortest Time-to-Completion First

每当新工作进入系统时，它就会确定剩余工作和新工作中谁的剩余时间最少，然后调度该程序。

轮转(Round-Robin)

如果使用 STCF 调度算法，则可能面临交互的问题，想象一下，你输入后需要等待 10 秒甚至更多的时间来响应会是一种怎么样的体验。

RR 在一个时间片(time slice，有时称为调度量子,scheduling quantum) 内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务知道结束，它反复执行，直到所有任务完成。

时间片的长度越短，响应时间表现越好，交互越流畅。但带来了频繁切换上下文的开销。

时间片的长度越长，上下文切换的开销越低，但响应时间表现差，所以我们呢可以增加时间片来摊销上下文切换的成本。

调度程序在 A 执行并且进行 IO 操作时，则会阻塞 A，运行 B，A 的 IO 操作完成后在做出决定。这种重叠的机制可以使得 CPU 资源更好的被利用。

操作系统之进程