Linux进程控制块

这是操作系统老师布置的一项作业，作业内容如下：

试根据你自己的理解，采用类C语言设计和描述操作系统关于进程控制块的数据结构、组织方式及管理机制。在此基础上，给出进程的创建、终止、阻塞、唤醒、挂起与激活等函数原型及函数代码。注意，对于过于复杂的功能或你无法解决的细节可采用指定功能的函数模块如处理机scheduler()调度来替代。

这篇文章首先介绍了Linux操作系统中的进程控制块task_struct，再根据《操作系统原理》中的描述写了进程调度的伪代码。

进程

​ Linux中的每个进程由一个task_struct数据结构来描述，这个结构体容纳了一个进程的所有信息，是系统对进程进行控制的唯一手段，也是最有效的手段。

​ 我使用PD在电脑中安装了Linux虚拟机，内核版本为4.13.0-37，task_struct结构体定义在sched.h文件中，具体路径如下图：

​ Linux支持两种进程：普通进程和实时进程。实时进程具有一定程度上的紧迫性，要求对外部事件做出非常快的响应；而普通进程则没有这种限制。所以，调度程序要区分对待这两种进程，通常，实时进程比普通进程优先运行。

task_struct成员

• 进程状态(state)

  进程执行时，它会根据具体情况改变状态。进程状态是调度和对换的依据。

  volatile long state;

  state的可能取值如下：

  • 五个互斥状态

    state域能够取的这五个值互为排斥。

  状态	描述
  TASK_RUNNING	可运行状态，要么正在运行、要么准备运行。正在运行的进程就是current指向的进程，准备运行的进程等待CPU片的调度。
  TASK_INTERRUPTIBLE	可中断的等待状态，该状态的进程正在等待某个事件或某个资源，它位于系统中的某个等待队列中，可以被信号唤醒。
  TASK_UNINTERRUPTIBLE	不可中断的等待状态，等待特定的系统资源，不可被打断，只能用特定的方式唤醒，例如唤醒函数wake_up()等。
  __TASK_STOPPED	暂停状态，进程接收到SIGSTOP, SIGTTIN, SIGTSTP或者SIGTTOU信号后进入该状态。
  __TASK_TRACED	表示进程被debugger等进程监视，进程执行被调试程序所停止。

  • 两个终止状态

    int	exit_state;
    int exit_code;
    int exit_signal;

    两个附加的进程状态既可以添加到state域中，又可以添加到exit_state域中。当进程终止时，会达到这两种状态。

  状态	描述
  EXIT_DEAD	进程的最终状态。
  EXIT_ZOMBIE	进程的执行被终止，但是其父进程还未使用wait()等系统调用来获知它的终止信息，此时进程成为僵尸进程。

  • 睡眠状态

    TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE都是睡眠状态。

    内核提供了两种方法将进程置为睡眠状态：

    1. 将进程设置为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，并且调用schedule()函数。将进程从CPU运行队列中移除。

    2. TASK_KILLABLE状态

       状态	描述
       TASK_KILLABLE	当进程处于这种可终止的睡眠状态中时，可以响应致命信号

       #define TASK_WAKEKILL	128
       
       /* Convenience macros for the sake of set_current_state: */
       #define TASK_KILLABLE			(TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
       #define TASK_STOPPED			(TASK_WAKEKILL | __TASK_STOPPED)
       #define TASK_TRACED			(TASK_WAKEKILL | __TASK_TRACED)

       即TASK_KILLABLE = TASK_WAKEKILL + TASK_UNINTERRUPTIBLE。

  参考：https://www.ibm.com/developerworks/cn/linux/l-task-killable/index.html

• 进程标识符(PID)

  pid_t				pid;
  pid_t				tgid;

  每个进程都有一个唯一的标识符，内核通过这个标识符来识别不同的进程，同时，进程标识符PID也是内核提供给用户程序的接口，用户程序通过PID对进程发号施令。PID是32位的无符号整数，顺序编号，新创建的进程通常是前一个进程的PID加1，Linux上允许的最大PID号为32767。

  线程组所有线程与领头线程具有相同的PID，存入tgid字段，getpid()返回当前进程的tgid值。

• 进程内核栈

  void *stack

  对每个进程，Linux内核把两个不同的数据结构紧凑的存放在一个单独为进程分配的内存区域中：

  1. 内核态的进程堆栈
  2. 线程描述符thread_info

  Linux把这两个结构存放在一起，区域通常占8192K。

  esp寄存器是CPU的栈指针，存放栈顶单元地址。

• 内核栈数据结构描述thread_info

  #ifdef CONFIG_THREAD_INFO_IN_TASK
  	/*
  	 * For reasons of header soup (see current_thread_info()), this
  	 * must be the first element of task_struct.
  	 */
  	struct	thread_info	thread_info;
  #endif

  thread_info结构定义在thread_info.h中：

• 进程标记

  /* Per task flags (PF_*), defined further below: */
  unsigned int flags;

  反应进程状态的信息，但不是运行状态，用于内核识别进程当前的状态，以备下一步操作

  flags成员的可能取值如下，这些宏以PF(ProcessFlag)开头。

• 表示进程亲属关系成员

  /*
   * Pointers to the (original) parent process, youngest child, younger sibling,
   * older sibling, respectively.  (p->father can be replaced with
   * p->real_parent->pid)
   */
  
  /* Real parent process: */
  struct task_struct __rcu	*real_parent;
  
  /* Recipient of SIGCHLD, wait4() reports: */
  struct task_struct __rcu	*parent;
  
  /*
   * Children/sibling form the list of natural children:
   */
  struct list_head		children;
  struct list_head		sibling;
  struct task_struct		*group_leader;

  在Linux系统中，每个进程都有其父进程，也可能有零个或多个子进程。拥有同一父进程的所有进程具有兄弟关系。

• 进程调度

  • 优先级

    int	prio;					//保存动态优先级
    int	static_prio;			//保存静态优先级
    int normal_prio;			//取值取决于静态优先级和调度策略
    unsigned int rt_priority;	//保存实时优先级

    实时优先级范围是0至MAX_RT_PRIO-1，普通进程的静态优先级范围是从MAX_RT_PRIO到MAX_PRIO-1。值越大静态优先级越低。

    MAX_RT_PRIO定义在prio.h中：

  • 调度策略相关字段

    const struct sched_class *sched_class;
    struct sched_entity	se;
    struct sched_rt_entity rt;	
    
    unsigned int policy;
    int	nr_cpus_allowed;
    cpumask_t cpus_allowed;

    字段	描述
    policy	调度策略
    sched_class	调度类
    se	普通进程的调用实体，每个进程都有其中之一的实体
    rt	实时进程的调用实体，每个进程都有其中之一的实体
    cpus_allowed	控制进程可以在哪里处理器上运行

• 时间

  一个进程从创建到终止叫做该进程的生存期（lifetime）。进程在其生存期内使用 CPU 的时间，内核都要进行记录，以便进行统计、计费等有关操作。进程耗费 CPU 的时间由两部 分组成：一是在用户模式（或称为用户态）下耗费的时间、一是在系统模式（或称为系统态） 下耗费的时间。每个时钟滴答，也就是每个时钟中断，内核都要更新当前进程耗费 CPU 的时 间信息。

  u64	utime;
  u64	stime;
  #ifdef CONFIG_ARCH_HAS_SCALED_CPUTIME
  	u64	utimescaled;
  	u64	stimescaled;
  #endif
  u64	gtime;
  struct prev_cputime	prev_cputime;
  #ifdef CONFIG_VIRT_CPU_ACCOUNTING_GEN
  	struct vtime vtime;
  #endif
  /* Context switch counts: */
  unsigned long nvcsw;
  unsigned long nivcsw;
  /* Monotonic time in nsecs: */
  u64	start_time;
  /* Boot based time in nsecs: */
  u64	real_start_time;
  /* MM fault and swap info: this can arguably be seen as either mm-specific or thread-specific: */
  unsigned long min_flt;
  unsigned long maj_flt;
  
  #ifdef CONFIG_POSIX_TIMERS
  	struct task_cputime	cputime_expires;
  	struct list_head cpu_timers[3];
  #endif
  /* Process credentials: */
  
  /* Tracer's credentials at attach: */
  const struct cred __rcu	*ptracer_cred;
  
  /* Objective and real subjective task credentials (COW): */
  const struct cred __rcu	*real_cred;
  
  /* Effective (overridable) subjective task credentials (COW): */
  const struct cred __rcu	*cred;
                                
  struct nameidata *nameidata;
  #ifdef CONFIG_SYSVIPC
  	struct sysv_sem	sysvsem;
  	struct sysv_shm	sysvshm;
  #endif
  #ifdef CONFIG_DETECT_HUNG_TASK
  	unsigned long last_switch_count;
  #endif

  字段	描述
  utime/stime	用于记录进程在用户态/内核态下所经过的节拍数
  prev_utime/prev_stime	先前运行时间
  utimescaled/stimescaled	记录进程在用户态/内核态的运行时间
  gtime	用节拍计数的虚拟机运行时间
  nvcsw/nivcsw	是自愿（voluntary）/非自愿（involuntary）上下文切换计数
  last_switch_count	nvcsw和nivcsw总和
  start_time/real_start_time	进程创建时间
  cputime_expires	统计进程或进程组被跟踪的处理器时间

• 信号处理

  /* Signal handlers: */
  struct signal_struct *signal;
  struct sighand_struct *sighand;
  sigset_t blocked;
  sigset_t real_blocked;
  /* Restored if set_restore_sigmask() was used: */
  sigset_t saved_sigmask;
  struct sigpending		pending;
  unsigned long sas_ss_sp;
  size_t sas_ss_size;
  unsigned int sas_ss_flags;

字段	描述
signal	指向进程的信号描述符
sighand	指向进程的信号处理程序描述符
blocked	表示被阻塞信号的掩码
pending	存放私有挂起信号
sas_ss_sp	信号处理程序备用堆栈地址

进程组织方式

• 线性方式

  把所有的task_struct组织在一张线性表中，将该表的首地址存放在内存的一个专用区域中，该方法实现简单、开销小，但每次查找需要扫描全表，适用于系统中进程数目不多的情况。

• 链接方式

  把具有相同状态进程的task_struct分别通过task_struct中的链接字链接成一个队列。形成就绪队列、若干个阻塞队列和空白队列等。

• 索引方式

  根据所有进程状态不同建立索引表，各个索引表在内存单元中的首地址也记录在内存中的专用单元中，用添加索引表的方式记录具有相应状态下的某个PCB在PCB表中的地址。

进程控制函数原型及代码创建、终止、阻塞、唤醒、挂起与激活

• 进程创建

  创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。此外，在撤销父进程时，也必须同时撤销其所有的子进程。

  在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。操作系统创建一个新进程的过程如下（创建原语)：

  1. 分配标识符，并申请空白进程控制块
  2. 为新进程的程序和数据及用户栈分配必要的内存空间
  3. 初始化进程控制块：自身/父进程标识符，处理机状态/调度信息
  4. 将新进程插入到就绪进程队列

  int create(struct task *task_struct, struct preparedQueue *q) {
      task_struct = (struct task *)malloc(sizeof(struct task)); //分配内存空间
      task_struct->pid = getpid();//进程标识符
      ………………						//初始化进程控制块
      insert(q, task_struct);		//把当前控制块插入就绪进程队列
      return pid;
  }

• 进程终止

  引起进程终止的事件主要有：正常结束，表示进程的任务已经完成和准备退出运行。异常结束，指进程在运行时，发生了某种异常事件，使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、I/O故障等。外界干预是指进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止。

  操作系统终止进程的过程如下（撤销原语）：

  1. 根据被终止进程的标识符，检索PCB，从中读出该进程的状态。
  2. 若被终止进程处于执行状态，立即终止该进程的执行，置调度标志为真，用于指示该进程被终止后应重新进行调度。
  3. 若该进程还有子进程，则应将其所有子进程终止。
  4. 将该进程所拥有的全部资源，或归还给其父进程或归还给操作系统。
  5. 将该PCB从所在队列（链表）中删除。

  void Terminate(pid, q, task_struct) {
      volatile long state;	//进程状态
      bool flag;	//调度标志
      //处于运行状态，则终止进程执行，置调度标志为真。
      if(getState(pid) == running){
          kill(pid);
          flag = true;
      }
      //终止所有子进程
      if(isHaveSonNodes(pid)) {
          killAllSonNodes(pid);
      }
      
      free(task_struct);		//归还资源
      delete(q, task_struct); //从队列中删除
  }

• 进程阻塞

  正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作做等，则由系统自动执行阻塞原语(Block)，使自己由运行状态变为阻塞状态。可见，进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU），才可能将其转为阻塞状态。

  阻塞原语的执行过程是：

  1. 找到将要被阻塞进程的标识号对应的PCB。
  2. 若该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行。
  3. 把该PCB插入到相应事件的等待队列中去。

  void Block(task_struct, pid, blockQueue q) {
      task_struct = getRunningTask(pid);		//找到对应的PCB
      stop(task_struct);				//停止运行
      task_struct->state = blocked;	//转为阻塞状态
      insert(q, task_struct);			//插入等待队列
  }

• 进程唤醒

  当被阻塞进程所期待的事件出现时，如它所启动的I/O操作已完成或其所期待的数据已到达，则由有关进程（比如，提供数据的进程）调用唤醒原语(Wakeup)，将等待该事件的进程唤醒。

  唤醒原语的执行过程是：

  1. 在该事件的等待队列中找到相应进程的PCB。
  2. 将其从等待队列中移出，并置其状态为就绪状态。
  3. 把该PCB插入就绪队列中，等待调度程序调度。

  void wakeUp (pid, task_struct, blockedQueue p, preparedQueue q) {
      task_struct = getBlockedTask(pid);	//找到对应的PCB
      remove(p, task_struct);				//从等待队列移出
      tast_struct->state = ready;			//状态改为就绪
      insert(q, task_struct);				//插入就绪队列
  }

• 进程挂起

  1. 检查被挂进程现行状态并修改和插队
  2. 复制PCB到指定区域
  3. 若被挂进程正在执行则转向调度程序重新调度

  void Suspend(pid, task_struct) {
      int state = task_struct->state;
      if(task_struct->state = "running") {
          stop(task_struct);
      }
      copy(task_struct);
      switch(state) {
          case "活动就绪":
              task_struct->state = "静止就绪";
              break;
          case "活动阻塞":
              task_struct->state = "静止阻塞";
              break;
      }
      if(task_struct->state = "running") {
          scheduler();
      }
  }

• 进程激活

  1. 检查进程现行状态并修改和插队
  2. 若有新进程进入就绪队列且采用了抢占式调度策略，则检查和决定是否重新调度

  void Active(pid, task_struct) {
      int state = task_struct->state;
      scheduler();	//将挂起的进程从外存调入内存
      switch(state) {
          case "静止就绪":
              task_struct->state = "活动就绪";
              break;
          case "静止阻塞":
              task_struct->state = "活动阻塞";
              break;
      }
      if(task_struct->state == "ready") {
          scheduler();	//若有新进程进入就绪队列且采用了抢占式调度策略，则检查和决定是否重新调度
      }
  }