進(jìn)程調(diào)度是現(xiàn)代操作系統(tǒng)一個(gè)重要的組成部分，理論上它會(huì)為進(jìn)程提供多種不同的運(yùn)行狀態(tài)，以及在CPU核上、核間調(diào)度的策略。因?yàn)轫?xiàng)目實(shí)踐需要，我們需要在一個(gè)CPU核上用自己的調(diào)度器來運(yùn)行多個(gè)進(jìn)程，運(yùn)行策略由用戶態(tài)程序決定，在特定的時(shí)候喚醒特定的進(jìn)程。這次就來分享一下進(jìn)程調(diào)度的一些基本概念和我們的這種純用戶空間進(jìn)程調(diào)度的實(shí)現(xiàn)。

1.進(jìn)程狀態(tài)

在linux操作系統(tǒng)，用top命令我們就能看到有許許多多正在運(yùn)行的進(jìn)程：

top命令輸出.png

在linux系統(tǒng)中，進(jìn)程的運(yùn)行狀態(tài)主要分為5種：

• Running/Runnable：Running進(jìn)程為當(dāng)前正在使用CPU的進(jìn)程，Runnable進(jìn)程是具備運(yùn)行條件且僅在等待CPU的進(jìn)程。進(jìn)程結(jié)構(gòu)體state字段為TASK_RUNNING。

• Sleeping：Sleeping進(jìn)程是等待資源(例如：I/O操作完成)或事件(例如：定時(shí)器，經(jīng)過一定時(shí)間)的進(jìn)程。在linux系統(tǒng)中Sleeping進(jìn)程又分為兩種：可中斷睡眠狀態(tài)(S)與不可中斷睡眠狀態(tài)(D)。它們之間的區(qū)別在于，前者可以用信號(signal)來喚醒，而后者則不能。假設(shè)一個(gè)進(jìn)程在喚醒之前正在等待I/O操作完成。如果在此期間它收到終止信號(SIGKILL)，它將會(huì)在處理I/O請求返回的數(shù)據(jù)前被殺死(喚醒即殺死)。這就是為什么I/O操作通常在等待結(jié)果時(shí)進(jìn)入不可中斷睡眠的原因：操作準(zhǔn)備就緒時(shí)，它們會(huì)喚醒，處理結(jié)果，然后檢查是否有任何待處理的信號。而那些可以在滿足喚醒條件且可以在沒有任何后果之前終止的進(jìn)程通常使用可中斷睡眠。另外睡眠狀態(tài)在真正使用中還有諸多限制，需要結(jié)合實(shí)際情況非常小心，比如不能帶鎖睡眠等?？芍袛嗨郀顟B(tài)的進(jìn)程state字段為TASK_INTERRUPTIBLE，不可中斷睡眠為TASK_UNINTERRUPTIBLE。

• Stopped(T)：當(dāng)進(jìn)程收到SIGSTOP信號時(shí)就停止了(例如，在終端輸入ctrl+z時(shí))。當(dāng)停止時(shí)，進(jìn)程執(zhí)行將被掛起，并且它將處理的唯一信號是SIGKILL和SIGCONT。前者殺死該進(jìn)程，而后者將使該進(jìn)程返回“Running/Runnable”狀態(tài)。其進(jìn)程state字段為TASK_STOPPED。

• Zombie(Z)：當(dāng)進(jìn)程通過exit()系統(tǒng)調(diào)用結(jié)束時(shí)，其狀態(tài)需要由其父進(jìn)程“獲得”(調(diào)用wait())；同時(shí)，子進(jìn)程仍處于僵尸狀態(tài)(沒有生命也沒有死亡)。其進(jìn)程state字段為TASK_ZOMBIE。

進(jìn)程在這些狀態(tài)間來回切換的圖示如下：

進(jìn)程狀態(tài)轉(zhuǎn)換.png

進(jìn)程的這些運(yùn)行狀態(tài)是為了讓眾多進(jìn)程在有限的CPU核上跑起來而提出的。在現(xiàn)代多核處理器上，同一時(shí)間CPU只能被一個(gè)進(jìn)程使用，也就意味著如何，實(shí)際上操作系統(tǒng)做了一些調(diào)度策略，比方說每個(gè)進(jìn)程運(yùn)行一段時(shí)間進(jìn)入sleep狀態(tài)給其他進(jìn)程使用CPU的機(jī)會(huì)。只要這個(gè)周期夠短，就能讓用戶感覺不到自己是在“運(yùn)行-睡眠-運(yùn)行-睡眠”的，這又被稱為“時(shí)間多路復(fù)用”。同時(shí)為了保證同一個(gè)進(jìn)程不會(huì)一直占據(jù)某個(gè)CPU，linux默認(rèn)也是會(huì)將進(jìn)程緩慢地在核間調(diào)度的。

2.調(diào)度

在linux操作系統(tǒng)中調(diào)度策略有三種——SCHED_OTHER、SCHED_FIFO、SCHED_RR，按照傳統(tǒng)分法，它們分成兩大類：

• 普通進(jìn)程調(diào)度

普通進(jìn)程是用于區(qū)分實(shí)時(shí)進(jìn)程的概念，在linux系統(tǒng)中，默認(rèn)的進(jìn)程都是普通進(jìn)程，采用SCHED_OTHER調(diào)度。這是一種CFS（Completely Fair Schedule，完全公平調(diào)度算法）調(diào)度算法，它為每個(gè)進(jìn)程分配一次運(yùn)行的CPU時(shí)間片（slice），時(shí)間片運(yùn)行完即讓出CPU。

在時(shí)間片的確定上，不直接使用優(yōu)先級，將優(yōu)先級換算成基本時(shí)間片：

當(dāng)進(jìn)程靜態(tài)優(yōu)先級<120時(shí)，基本時(shí)間片=(140-靜態(tài)優(yōu)先級)×20；
當(dāng)進(jìn)程靜態(tài)優(yōu)先級>=120時(shí)，基本時(shí)間片=(140-靜態(tài)優(yōu)先級)×5

另外動(dòng)態(tài)優(yōu)先級是用來計(jì)算睡眠時(shí)間的，就不展開講了。
對于用戶而言，可以通過nice系統(tǒng)調(diào)用來調(diào)節(jié)進(jìn)程運(yùn)行的時(shí)間片間隔。

• 實(shí)時(shí)進(jìn)程調(diào)度：

linux系統(tǒng)中的實(shí)時(shí)進(jìn)程調(diào)度有兩種：SCHED_FIFO和SCHED_RR。只要人為設(shè)置進(jìn)程使用這兩種調(diào)度策略的進(jìn)程都是實(shí)時(shí)進(jìn)程，每個(gè)實(shí)時(shí)進(jìn)程都有一個(gè)優(yōu)先級，范圍從1(最高)到99(最低)。調(diào)度程序會(huì)讓優(yōu)先級高的進(jìn)程運(yùn)行，而禁止優(yōu)先級低的進(jìn)程運(yùn)行。這是區(qū)別于普通進(jìn)程調(diào)度的，實(shí)時(shí)進(jìn)程總是被當(dāng)成活動(dòng)進(jìn)程。而當(dāng)有幾個(gè)優(yōu)先級相同的進(jìn)程需要運(yùn)行時(shí)，調(diào)度程序會(huì)選擇本地CPU運(yùn)行隊(duì)列鏈表中的第一個(gè)進(jìn)程來運(yùn)行。

對于兩種調(diào)度策略區(qū)別在于：
使用SCHED_RR策略的進(jìn)程是基于時(shí)間片輪轉(zhuǎn)來調(diào)度，進(jìn)程的時(shí)間片用完，系統(tǒng)將重新分配時(shí)間片，并置于就緒隊(duì)列尾。
使用SCHED_FIFO的進(jìn)程一旦占用cpu則一直運(yùn)行。一直運(yùn)行直到有更高優(yōu)先級任務(wù)到達(dá)或自己放棄。一些系統(tǒng)調(diào)用如sched_yield()可以主動(dòng)讓出CPU。

使用實(shí)時(shí)進(jìn)程調(diào)度時(shí)，該進(jìn)程是不可被搶占的；而一個(gè)核上有一個(gè)普通進(jìn)程正在運(yùn)行，現(xiàn)加入一個(gè)實(shí)時(shí)進(jìn)程，那么該實(shí)時(shí)進(jìn)程將會(huì)搶占普通進(jìn)程。

從用戶角度，既可以在代碼中指定當(dāng)前進(jìn)程的調(diào)度策略和優(yōu)先級，也可以在運(yùn)行的過程中用chrt命令來改變進(jìn)程的調(diào)度策略和優(yōu)先級：

chrt -p $PID         # 可以查看 pid=$PID 的進(jìn)程的 調(diào)度策略, 輸出如下:
      pid $PID's current scheduling policy: SCHED_OTHER
      pid $PID's current scheduling priority: 0

chrt -p -f 10 $PID   # 修改進(jìn)程$PID的調(diào)度策略為 SCHED_FIFO, 并且優(yōu)先級為10
chrt -p $PID         # 再次查看調(diào)度策略
      pid $PID's current scheduling policy: SCHED_FIFO
      pid $PID's current scheduling priority: 10

3.用戶空間實(shí)現(xiàn)喚醒式調(diào)度

重新回到前面，我們的需求：1）多個(gè)worker進(jìn)程在一個(gè)核上工作；2）有一個(gè)單獨(dú)的進(jìn)程做中央調(diào)度進(jìn)程，不定期去喚醒對應(yīng)的worker進(jìn)程；3）每個(gè)worker進(jìn)程執(zhí)行完自己的一輪任務(wù)后主動(dòng)放棄CPU進(jìn)入sleeping狀態(tài)，能且僅能被調(diào)度進(jìn)程喚醒；4）worker進(jìn)程處于運(yùn)行狀態(tài)時(shí)不可被別的進(jìn)程打斷搶占。

注意到這里worker進(jìn)程的調(diào)度是不可搶占的，非時(shí)間片觸發(fā)的，那么只有SCHED_FIFO一種調(diào)度適合。

使用FIFO調(diào)度需要特別注意，因?yàn)樗荒鼙粨屨?，如果一旦由于bug進(jìn)入了不可中斷睡眠狀態(tài)，那么這個(gè)進(jìn)程幾乎是殺不死的，只能重啟；而且它在一個(gè)核上運(yùn)行的時(shí)候會(huì)霸占整個(gè)核，最好的方式是在grub中使用核隔離

進(jìn)入睡眠狀態(tài)的方式有直接調(diào)用sleep、調(diào)用schedule()、等待I/O資源等，但由于我們的進(jìn)程均處于用戶態(tài)，無法直接調(diào)用內(nèi)核未暴露接口的函數(shù)，且sleep和等待I/O這些操作無法做到精確控制。那么只能寫一個(gè)內(nèi)核模塊，調(diào)度程序用ioctl與之通信，把對應(yīng)的worker進(jìn)程從sleeping狀態(tài)置為running狀態(tài)。但是在精確度上還是有所欠缺。

這時(shí)候想到了利用多線程的思路，worker進(jìn)程可以創(chuàng)建一個(gè)pthread來做這個(gè)工作，自己主線程等這個(gè)真正工作的pthread退出才退出。這樣可以使用多線程的條件變量來實(shí)現(xiàn)控制從線程sleeping還是running。

每個(gè)worker進(jìn)程邏輯如下：

#主線程:收到調(diào)度進(jìn)程的信號，就調(diào)用一次cond_signal解除從線程阻塞
      pthread_mutex_lock(&lock);
      pthread_cond_signal(&needProduct);
      pthread_mutex_unlock(&lock);

#從線程:work函數(shù)中沒運(yùn)行一輪workload，調(diào)用cond_wait阻塞進(jìn)入sleeping狀態(tài)
void *work(void *arg)
{
    while(1)
    {
       ... #workload
       pthread_mutex_lock(&lock);
       pthread_cond_wait(&needProduct,NULL);
       pthread_mutex_unlock(&lock);
    }
}

至于調(diào)度進(jìn)程與worker進(jìn)程如何通信，可以使用信號、套接字、管道、消息隊(duì)列、共享內(nèi)存等一系列進(jìn)程間通信的方式。

下面附上一個(gè)demo，這個(gè)例子使用的信號來做進(jìn)程間通信，使用了SIGUSR1信號，直接使用終端命令kill -s 10 $PID也可以實(shí)現(xiàn)調(diào)度器功能，每發(fā)一個(gè)信號執(zhí)行一次loop：

worker.c創(chuàng)建一個(gè)從線程，運(yùn)行work函數(shù)內(nèi)容

//worker.c
#include<stdio.h>
#include<unistd.h>
#define __USE_GNU 
#include<sched.h>
#include<pthread.h>
#include <sys/prctl.h>
#include <sys/syscall.h>
#include <signal.h>
static pthread_mutex_t lock=PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t needProduct=PTHREAD_COND_INITIALIZER;

static void
signal_handler(int signum)
{
        pthread_mutex_lock(&lock);
        pthread_cond_signal(&needProduct);//解除條件變量的阻塞
        pthread_mutex_unlock(&lock);
}

void *work(void *arg)
{
        signal(SIGUSR1, signal_handler); //注冊信號
        prctl(PR_SET_NAME,"slave");
        int a=0;
        int i=0;
        pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, NULL);
        pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED, NULL);
        pthread_detach(pthread_self());
        while(1)
        {
                a+=1;
                a=a%9;
                printf("%d:",syscall(SYS_gettid));
                for(i=0;i<a;i++)
                {
                        printf("*");
                }
                printf("\n");
                pthread_testcancel();
                pthread_mutex_lock(&lock);
                pthread_cond_wait(&needProduct,&lock);
                pthread_mutex_unlock(&lock);
                //放棄CPU自己被阻塞
        }
        return NULL;
}

int main()
{
    signal(SIGUSR1, signal_handler);
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setschedpolicy(&attr,SCHED_FIFO);
    struct sched_param param;
    param.sched_priority=30;
    pthread_attr_setschedparam(&attr,&param);
    pthread_attr_setinheritsched(&attr,PTHREAD_EXPLICIT_SCHED);
    cpu_set_t mask;
    CPU_ZERO(&mask);
    CPU_SET(6,&mask);
    if(pthread_attr_setaffinity_np(&attr,sizeof(mask),&mask)==-1)
    {
        printf("pthread_attr_setaffinity_np erro\n");
    }
    //設(shè)置調(diào)度模式和親和性等，綁定從線程到6號核上，設(shè)置調(diào)度為SCHED_FIFO，優(yōu)先級為30
    pthread_t t;
    int error = pthread_create(&t, &attr, work, NULL);
    if(error!=0)
    {
        printf("can't create thread\n");
    }

    pthread_attr_destroy(&attr);
    pthread_join(t,NULL);
    return 0;
}

編譯gcc worker.c -g -Wall -lpthread -o worker，運(yùn)行./worker。

schedule.c非常簡單，直接調(diào)用kill函數(shù)向worker進(jìn)程發(fā)送SIGUSR1信號。

//schedule.c
#include<stdio.h>
#include <stdlib.h>
#define __USE_GNU
#include<sched.h>
#include<pthread.h>
#include<signal.h>
int main(int argc,char** argv)
{
    int pid=atoi(argv[1]);
    //喚醒對應(yīng)的進(jìn)程
    kill(pid, SIGUSR1);
    return 0;
}

編譯gcc schedule.c -o schedule，運(yùn)行./schedule $PID($PID為worker進(jìn)程的進(jìn)程號)。
效果是每運(yùn)行一次schedule就會(huì)看到輸出來一層*號。

運(yùn)行效果.png

引用：
[1] Linux Process States and Signals, https://medium.com/@cloudchef/linux-process-states-and-signals-a967d18fab64
[2] 《深入理解LINUX內(nèi)核》