操作系统-进程

进程

进程概念

狭义定义：进程是正在运行的程序的实例（an instance of a computer program that is being executed）。
广义定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。

进程创建 - 程序如何转化为进程

操作系统运行程序必须做的第一件事是将代码和所有静态数据加载（load）到内存中，加载到进程的地址空间中。程序最初以某种可执行格式驻留在磁盘上。因此，将程序和静态数据加载到内存中的过程，需要操作系统从磁盘读取这些字节，并将它们放在内存中的某处。在早期的操作系统中，加载过程尽早完成，即在运行程序之前全部完成。现代操作系统惰性（lazily）执行该过程，即仅在程序执行期间需要加载的代码或数据片段，才会加载。
将代码和静态数据加载到内存后，操作系统应当为运行时栈（run-time stack）分配一些内存。C程序使用栈存放局部变量、函数参数和返回地址。操作系统分配这些内存，并提供给进程。操作系统也可能会用参数初始化栈。具体来说，它会将参数填入main()函数，即argc和argv数组。
操作系统也可能为程序的堆（heap）分配一些内存。在C程序中，堆用于显式请求的动态分配数据。程序通过调用malloc()来请求这样的空间，并通过调用free()来明确地释放它。数据结构（如链表、散列表、树和其他有趣的数据结构）需要堆。起初堆会很小。随着程序运行，通过malloc()库API请求更多内存，操作系统可能会参与分配更多内存给进程，以满足这些调用。
操作系统还将执行一些其他初始化任务，特别是与输入/输出（I/O）相关的任务。例如，在UNIX系统中，默认情况下每个进程都有3个打开的文件描述符（file descriptor），用于标准输入、输出和错误。这些描述符让程序轻松读取来自终端的输入以及打印输出到屏幕。
通过创建和初始化栈以及执行与I/O设置相关的其他工作，OS执行最后一项任务：启动程序，在入口处运行，即main()。OS将CPU的控制权转移到新创建的进程中，从而程序开始执行。

进程状态

创建状态：进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态。
就绪状态：进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行。
执行状态：进程处于就绪状态被调度后，进程进入执行状态。
阻塞状态：正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用。
终止状态：进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行。

从就绪到运行意味着该进程已经被调度（scheduled）。从运行转移到就绪意味着该进程已经取消调度（descheduled）。一旦进程被阻塞（例如I/O操作），OS将保持进程的这种状态，直到发生某种事件（例如I/O完成）。此时，进程再次转入就绪状态（也可能立即再次运行，如果操作系统这样决定）。

进程API

创建（create）：操作系统必须包含一些创建新进程的方法。在shell中键入命令或双击应用程序图标时，会调用操作系统来创建新进程，运行指定的程序。
销毁（destroy）：由于存在创建进程的接口，因此系统还提供了一个强制销毁进程的接口。当然，很多进程会在运行完成后自行退出。但是，如果它们不退出，用户可能希望终止它们，因此停止失控进程的接口非常有用。
等待（wait）：有时等待进程停止运行是有用的，因此经常提供某种等待接口。
其他控制（miscellaneous control）：除了杀死或等待进程外，有时还可能有其他控制。例如，大多数操作系统提供某种方法来暂停进程（停止运行一段时间），然后恢复（继续运行）。
状态（statu）：通常也有一些接口可以获得有关进程的状态信息，例如运行了多长时间，或者处于什么状态。

linux 进程API

fork()：为调用进程创建一个一模一样的新进程，fork后的两个进程均为独立进程(调用进程为父进程，新进程为子进程)。
```
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
 printf("hello, i am main process (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 process (pid:%d)\n", (int) getpid());
 } else {
     printf("hello, I am main process and the father of %d (pid:%d)\n", rc, (int) getpid());
 }
 return 0;
}
```
```
/home/ronie/CLionProjects/process/cmake-build-debug/process
hello, i am main process (pid: 5843)
hello, I am main process and the father of 5844 (pid:5843)
hello, I am child process (pid:5844)
```
- 进程调用了fork()，这是操作系统提供的创建新进程的方法。新创建的进程几乎与调用进程完全一样，对操作系统来说，这时看起来有两个完全一样的程序在运行，并都从fork()系统调用中返回。新创建的进程称为子进程（child），原来的进程称为父进程（parent）。子进程不会从main()函数开始执行，而是直接从fork()系统调用返回。
- 子进程并不是完全拷贝了父进程。虽然它拥有自己的地址空间、寄存器、程序计数器等，但是它从fork()返回的值是不同的。父进程获得的返回值是新创建子进程的PID，而子进程获得的返回值是0。
- 子进程与父进程的输出是不确定的。

wait()：等待子进程终止或停止。可以使用 wait()系统调用(或者更完整的兄弟接口 waitpid())。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
int main(int argc, char *argv[])
{
 printf("hello, i am main process (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 process (pid:%d)\n", (int) getpid());
 } else {
     int w = wait(NULL);
     printf("hello, I am main process and i am waiting process %d to complete\n", (int) w);
     printf("hello, I am main process and the father of %d (pid:%d)\n", rc, (int) getpid());
 }
 return 0;
}

/home/ronie/CLionProjects/process/cmake-build-debug/process
hello, i am main process (pid: 6145)
hello, I am child process (pid:6146)
hello, I am main process and i am waiting process 6146 to complete
hello, I am main process and the father of 6146 (pid:6145)

Process finished with exit code 0

当父进程调用wait()函数时，父进程便立即阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个已经变成僵尸的子进程，wait就会收集这个子进程的信息，并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个出现为止。
当父进程调用waitpid()函数时，当指定等待的子进程已经停止运行或结束了，则waitpid()会立即返回；但是如果子进程还没有停止运行或结束，则调用waitpid()函数的父进程则会被阻塞，暂停运行。

exec()：为进程指定可执行文件和参数。在fork之后调用exec，可以在载入可执行文件后会重置地址空间。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
int main(int argc, char *argv[])
{
 printf("hello, i am main process (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 process (pid:%d)\n", (int) getpid());
     char *argv[]={"ls","-al","/home/ronie/Desktop", NULL};
     char *envp[]={NULL};
     execve("/bin/ls",argv,envp);
     printf("should not be printed");
 } else {
     int w = wait(NULL);
     printf("hello, I am main process and i am waiting process %d to complete\n", (int) w);
     printf("hello, I am main process and the father of %d (pid:%d)\n", rc, (int) getpid());
 }
 return 0;
}

/home/ronie/CLionProjects/process/cmake-build-debug/process
hello, i am main process (pid: 6379)
hello, I am child process (pid:6380)
total 16
drwxr-xr-x  3 ronie ronie 4096 Oct 15 10:22 .
drwxr-x--- 16 ronie ronie 4096 Oct 15 10:36 ..
drwxrwxr-x  2 ronie ronie 4096 Oct  7 23:00 docker
-rw-rw-r--  1 ronie ronie  368 Oct  7 18:38 docker-compose.yml
hello, I am main process and i am waiting process 6380 to complete
hello, I am main process and the father of 6380 (pid:6379)

Process finished with exit code 0

execve()执行程序由 filename决定。filename必须是一个二进制的可执行文件，或者是一个脚本以#！格式开头的解释器参数参数。如果是后者，这个解释器必须是一个可执行的有效的路径名，但是不是脚本本身，它将调用解释器作为文件名。argv是要调用的程序执行的参数序列，也就是我们要调用的程序需要传入的参数。envp 同样也是参数序列，作为我们是新程序的环境。argv 和envp都必须以null指针结束。
exec()会从可执行程序中加载代码和静态数据，并用它覆写自己的代码段（以及静态数据），堆、栈及其他内存空间也会被重新初始化。然后操作系统就执行该程序，将参数通过argv传递给该进程。因此，它并没有创建新进程，而是直接将当前运行的程序替换为不同的运行程序，由于是直接将当前运行的程序替换为不同的运行程序，所以printf("should not be printed");代码未被执行。

数据结构 - 跟踪进程相关的信息

linux 0.11版本中内核源码进程表项

struct task_struct {
    /* these are hardcoded - don't touch */
    long state;    // 任务的运行状态(-1不可运行，0可运行(就绪)，>0已停止)
    long counter;   // 任务运行时间计数(递减) (滴答数)，运行时间片。
    long priority;  // counter=priority,越大运行越长。
    long signal;    // 信号。是位图，每个比特位代表一 种信号，信号值=位偏移值+1。
    struct sigaction sigaction[32];
    long blocked;    

    /* various fields */
    int exit_code; // 任务执行停止的退出码，其父进程会取。
    unsigned long start_code,end_code,end_data,brk,start_stack; // 代码段地址。代码长度(字节数)。代码长度+数据长度(字节数)。总长度(字节数)。堆栈段地址。
    long pid,father,pgrp,session,leader;
    unsigned short uid,euid,suid;
    unsigned short gid,egid,sgid;
    long alarm;
    long utime,stime,cutime,cstime,start_time;
    unsigned short used_math;

    /* file system info */
    int tty;        
    unsigned short umask;
    struct m_inode * pwd;
    struct m_inode * root;
    struct m_inode * executable;
    unsigned long close_on_exec;
    struct file * filp[NR_OPEN];

    /* ldt for this task 0 - zero 1 - cs 2 - ds&ss */
    struct desc_struct ldt[3];

    /* tss for this task */
    struct tss_struct tss;
};

进程调度策略

调度指标

CPU利用率：忙碌时间 / 总时间。
系统吞吐量：表示单位时间内完成多少作业。
周转时间：作业完成时间 - 作业提交时间。
响应时间：用户从提交请求到回应请求的时间。

抢占与非抢占

抢占式调度程序：通过将CPU的时隙划分给给定的进程来工作。给定的时间间隔可能能够完成整个过程，也可能无法完成。当进程的区间时间大于CPU周期时，它将被放回到就绪队列中，并在下一个时机执行。
非抢占式调度程序：进程获取资源(CPU时间)并持有它，直到进程终止或推送到等待状态。进程不会被中断，直到它完成，然后处理器切换到另一个进程。即系统会将每项工作做完，再考虑是否运行新工作。

调度策略

先进先出（FIFO）：
也称为先到先服务（First Come First Served 或FCFS）。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
- 优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平
- 缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程
最短任务优先（SJF）
而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
- 优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。
- 缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。
最高响应比优先法
FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，SJF方式只考虑执行时间而未考虑等待时间的长短。此调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。这样，即使是长作业，随着它等待时间的增加，响应比也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。
- 优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF 法时的吞吐量。
- 缺点：由于每次调度前要计算响应比，系统开销也要相应增加。
时间片轮转
让就绪进程以FCFS的方式按时间片轮流使用CPU的调度方式，即将系统中所有的就绪进程按照FCFS原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。
- 优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。
- 缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大。
优先级进程调度算法
把处理机分配给就绪队列中优先级最高的进程。这时，又可进一步把该算法分成非抢占式优先级调度算法，抢占式优先级调度算法。
- 静态优先级：静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如0～255中的某一整数，把该整数称为优先数。
- 动态优先级：动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。

进程

进程概念

进程创建 - 程序如何转化为进程

进程状态

进程API

数据结构 - 跟踪进程相关的信息

进程调度策略

调度指标

抢占与非抢占

调度策略

LeetCode（2022-10-20）

LeetCode（2022-10-26）

Ronie

Comments | NOTHING

进程

进程概念

进程创建 - 程序如何转化为进程

进程状态

进程API

数据结构 - 跟踪进程相关的信息

进程调度策略

调度指标

抢占与非抢占

调度策略

LeetCode（2022-10-20）

LeetCode（2022-10-26）

Ronie

Comments | NOTHING

你想搜索什么...