Process Scheduling 進程調(diào)度

進程調(diào)度器(或者簡單地說是調(diào)度程序)是內(nèi)核的組件敢辩，它選擇接下來要運行的進程掘托。在決定哪些進程可以運行娜扇，什么時候運行時邑闺，調(diào)度器負責 支持最大限度地利用處理器泪勒，同時提供多個進程并行和無縫執(zhí)行的錯覺昼蛀。
多任務(wù)操作系統(tǒng)有兩種變體：協(xié)作式cooperative和先發(fā)制人式preemptive。
進程在調(diào)度程序搶占之前允許運行的時間長度圆存，稱為進程的時間間隔timeslice叼旋。

I/O - Versus Processor - Bound Processes

持續(xù)消耗所有可用時間的進程被認為是processor - bound。
最簡單的例子是無限循環(huán)：

//100% processor-bound
while(1)
  ;

其他較不極端的例子包括科學計算沦辙、數(shù)學計算和圖像處理夫植。
與執(zhí)行相比，花費更多時間阻塞等待某些資源的進程被認為是I/O - bound油讯。
許多GUI應(yīng)用程序详民，它們花費大量時間等待用戶輸入。
processor-bound的應(yīng)用程序需要最大的時間點陌兑，允許它們最大限度地緩存hit rate（通過時間局部性）沈跨，并盡可能快地完成他們的作業(yè)。

I/O-bound進程不一定需要大量時間兔综，因為在發(fā)出I/O請求和阻塞某些內(nèi)核資源之前谒出，它們通常只運行很短的時間。
應(yīng)用程序可以在阻塞和調(diào)度更多I/O請求之后重新啟動的更快邻奠，那么就可以更好的是利用系統(tǒng)的硬件笤喳。此外，如果應(yīng)用程序正在等待用戶輸入碌宴， 時間安排得越快杀狡，用戶對無縫執(zhí)行的感知就越強。

Preemptive Scheduling 搶先調(diào)度

在傳統(tǒng)的UNIX進程調(diào)度中贰镣，所有可運行的進程都被分配了一個時間片呜象。當一個進程耗盡它的timeslice時膳凝，內(nèi)核將暫停它，并開始運行一個不同的進程恭陡。
系統(tǒng)上有更高優(yōu)先級的進程-低優(yōu)先級進程只能等待高優(yōu)先級進程耗盡它們的時間或阻塞蹬音。
這種行為制定了Unix調(diào)度的一個重要但默契的規(guī)則：所有進程都必須向前推進。

The Completely Fair Scheduler

完全公平調(diào)度器(CFS)與傳統(tǒng)的Unix進程調(diào)度程序有很大的不同休玩。
在大多數(shù)Unix系統(tǒng)中著淆，包括CFS推出之前的Linux，進程調(diào)度中有兩個基本的進程變量：優(yōu)先級和時間拴疤。
CFS引入了一種完全不同的算法永部，稱為公平調(diào)度fair shecduling，它消除了時間片作為分配給處理器的訪問權(quán)限的單元呐矾。
CFS為每個進程分配處理器時間的一部分苔埋，而不是時間間隔:

1. CFS首先給N個進程分配1/N的處理器時間。
2. CFS然后通過用每個進程的nice value加權(quán)每個進程的占用處理器時間的比重蜒犯。nice value為零的進程的權(quán)重為1组橄，因此它們的比例不變。具有較小的nice value(高優(yōu)先級）的進程接收較大的權(quán)重罚随，增加了占用處理器的時間比重晨炕，而具有較大的nice value(較低優(yōu)先級)的進程則減少了占用處理器的時間比重。
3. 為了確定每個進程運行的實際時間長度毫炉，CFS需要將比重劃分成一個固定時間瓮栗。這個時間被稱為target latency，表示系統(tǒng)調(diào)用的latency瞄勾。
   CFS引入了第二個關(guān)鍵變量费奸，最小粒度the minimum granularity。
   The minimum granularity是任何進程運行的時間長度的最小單元进陡。

Yielding the Processor

雖然linux是一個先發(fā)制人的多任務(wù)操作系統(tǒng)愿阐，但它也提供了一個系統(tǒng)調(diào)用，允許進程顯式地產(chǎn)生執(zhí)行并指示調(diào)度程序選擇一個新進程執(zhí)行趾疚。

#include <sched.h>
int sched_yield(void);

對schedyfield()的調(diào)用導(dǎo)致當前正在運行的進程暫停缨历，之后進程調(diào)度器選擇要運行的新進程，

if (sched_yield ())
perror ("sched_yield");

Legitimate Uses

實際上糙麦，在適當?shù)南劝l(fā)制人多任務(wù)處理系統(tǒng)(如Linux)上辛孵，sched_yield()很少有合法的使用。內(nèi)核完全有能力自己處理這個調(diào)度赡磅，并且性能更好魄缚。
那么為什么POSIX要由這么以分系統(tǒng)調(diào)用呢?
答案在于應(yīng)用程序必須等待外部事件，這些事件可能是由用戶、硬件組件或其他進程引起的冶匹。

/* the consumer... */
do {
        while (producer_not_ready ()){
              sched_yield ();
          }
          process_data ();
} while (!time_to_quit ());

值得慶幸的是习劫，UNIX程序員不傾向于編寫這樣的代碼。UNIX程序通常事件驅(qū)動嚼隘，并傾向于在消費者之間使用某種可阻止的機制（如管道）诽里。 和代替SCHED_LEVENT()的生產(chǎn)者。

Process Priorities

nice value 的范圍是[-20, 19] 默認值是0飞蛹。
nice value 的值越小谤狡， 優(yōu)先級越高，時間片越大桩皿。
nice value 的值越大豌汇， 優(yōu)先級越小幢炸，時間片越小泄隔。
Linux提供了幾個系統(tǒng)調(diào)用，用于檢索和設(shè)置進程的nice value宛徊。
最簡單的是nice():

#include <unistd.h>
int nice(int inc);

對nice()的成功調(diào)用將由inc遞增進程的nice value佛嬉，并返回新更新的值。
也就是如果inc為正,那么就是在降低優(yōu)先級,r如果inc為負闸天，則是在增加優(yōu)先級暖呕。
錯位的時候返回-1。因為-1也是nice的一個成功調(diào)用苞氮，所以要檢測錯誤的話就得像下面這么用湾揽。

int ret;
errno = 0;
ret = nice(10);
if(ret == -1 && errno != 0)
    perror("nice")
else
    printf("nice value is now %d\n", ret);

傳值0給nice()是一個很簡單的獲取當前進程nice value的方法。

printf("nice value is currently %d\n", nice(0));

int ret, val;
/*get current nice value*/
val = nice (0)

/*we want a nice value of 10*/
val = 10 - val;
errno = 0;
rer = nice(val);
if(ret == -1 && errno != 0)
    perror("nice")
else
    printf("nice value is now %d\n", ret)

getpriority() and setpriority()

最好好的解決方案是使用getpriority()和setpriority()系統(tǒng)調(diào)用笼吟，它允許更多的控制库物，但在操作上更復(fù)雜：

#include <sys/time.h>
#include <sys/resource.h>

int getpriority(int which, int who);
int setpriority(int which, int who, int prio);

參數(shù)which有如下參數(shù)選項：

1. PRIO_PROCESS
2. PRIO_PGRP
3. PRIO_USER
   參數(shù)who有就是對相應(yīng)上面which參數(shù)的進程ID， 進程組ID贷帮， 用戶ID戚揭。
   who是0的時候，就表示處理的是當前的進程ID撵枢，進程組ID民晒，或用戶ID
   參數(shù)prio通nice()的參數(shù)。錯誤的處理方式也同nice锄禽。

Processor Affinity

一旦進程被調(diào)度在一個CPU上潜必，進程調(diào)度程序應(yīng)該在將來將它調(diào)度在同一個CPU上。這是有益的沃但，因為將進程從一個處理器遷移到另一個處理器是有代價的刮便。

有時，用戶或應(yīng)用程序希望實施進程到處理器的綁定绽慈。這通常是因為該過程是強緩存敏感的恨旱，并且希望保留在同一處理器上辈毯。
將進程連接到特定處理器并讓內(nèi)核強制執(zhí)行關(guān)系稱為設(shè)置hard affinity。

sched_getaffinity() and sched_setaffinity()

Linux提供了兩個系統(tǒng)調(diào)用搜贤，用于檢索和設(shè)置進程的hard affinity：

#include _GNU_SOURCE
#include <sched.h>
typedef struct cpu_set_t;
size_t CPU_SETSIZE;
void CPU_SET (unsigned long cpu, cpu_set_t *set);
void CPU_CLR (unsigned long cpu, cpu_set_t *set);
int CPU_ISSET (unsigned long cpu, cpu_set_t *set);
void CPU_ZERO (cpu_set_t *set);

int sched_setaffinity (pid_t pid, size_t setsize,
    const cpu_set_t *set);
int sched_getaffinity (pid_t pid, size_t setsize,
      cpu_set_t *set);

如果pid為0時谆沃，調(diào)用將檢索當前進程的affinity。

cpu_set_t set;
int ret , i;
CPU_ZERO(&set);
ret = sched_getaffinity(0, sizeof(cpu_set_t), &set);
if(ret == -1)
     perror("sched_getaffinity");
for(int i = 0; i < CPU_SETSIZE; ++i){
      int cpu;
      cpu = CPU_ISSET(i, &set);
      printf("cpu=%i is %s\n, i , cpu ? "set" : "unset");
}

我們使用CPU_ISSET檢查系統(tǒng)中的給定處理器 i 是否綁定到此進程仪芒。

測試結(jié)果

我們只關(guān)注CPU#0唁影，#1， #2掂名， #3据沈，因為它們是這個系統(tǒng)上唯一的物理處理器。也許我們希望確保我們的進程只在CPU#0上運行饺蔑，而不是在其他三個處理器锌介。

int processBindCpu() {
    cpu_set_t set;
    CPU_ZERO(&set);
    CPU_SET(0, &set);
    CPU_CLR(1, &set);
    CPU_CLR(2, &set);
    CPU_CLR(3, &set);
    int ret = sched_setaffinity(0, sizeof(cpu_set_t), &set);
    if(ret == -1)
        perror("sched_setaffinity");
    for(int i = 0; i < CPU_SETSIZE; ++i){
        int cpu = CPU_ISSET(i, &set);
        printf("cpu=%i is %s\n", i, cpu?"set":"unset");
    }



    return 0;
}

測試結(jié)果

Real-Time Systems

Setting the Linux scheduling policy

#include <sched.h>
struct sched_param {
              /* ... */
              int sched_priority;
              /* ... */
};
int sched_getscheduler (pid_t pid);
int sched_setscheduler (pid_t pid,int policy,
const struct sched_param *sp);

int getProcessScheduler() {
    int policy;
    policy = sched_getscheduler(0);

    switch (policy){
        case SCHED_OTHER:
            printf("Policy is normal\n");
            break;
        case SCHED_RR:
            printf("Policy is round_robin\n");
            break;
        case SCHED_FIFO:
            printf("Policy is first-in, first-out\n");
            break;
        case -1:
            perror("sched_getscheduler");
            break;
        default:
            fprintf(stderr, "Unknown policy!\n");
    }

    return 0;
}

測試結(jié)果

//怎么設(shè)置進程的調(diào)度方式
struct sched_param sp = { .sched_priority = 1 };
int ret;
ret = sched_setscheduler (0, SCHED_RR, &sp);
if (ret == ?1) {
perror ("sched_setscheduler");
return 1; }

Setting Scheduling Parameters

#include <sched.h>
struct sched_param {
/* ... */
int sched_priority;
/* ... */
};
int sched_getparam (pid_t pid, struct sched_param *sp);
int sched_setparam (pid_t pid, const struct sched_param *sp);

struct sched_param sp;
int ret;
ret = sched_getparam (0, &sp);
if (ret == ?1) {
        perror ("sched_getparam");
        return 1; }
printf ("Our priority is %d\n", sp.sched_priority);

struct sched_param sp;
int ret;
sp.sched_priority = 1;
ret = sched_setparam (0, &sp);
if (ret == ?1) {
        perror ("sched_setparam");
return 1; }

Determining the range of valid priority

每個進程都具有靜態(tài)優(yōu)先級，與nice value無關(guān)猾警。對于正常的應(yīng)用程序孔祸，這個優(yōu)先級總是0。對于實時過程发皿，它的范圍從1到99崔慧。
linux調(diào)度程序總是選擇要運行的最高優(yōu)先級進程(即具有最大數(shù)值靜態(tài)優(yōu)先級值的進程)均蜜。

#include <sched.h>
int sched_get_priority_min (int policy);
int sched_get_priority_max (int policy);

int min, max;
min = sched_get_priority_min (SCHED_RR);
if (min == ?1) {
      perror ("sched_get_priority_min");
      return 1; 
}
max = sched_get_priority_max (SCHED_RR);
if (max == ?1) {
      perror ("sched_get_priority_max");
      return 1;
 }
printf ("SCHED_RR priority range is %d - %d\n", min, max);

/*
 * set_highest_priority - set the associated pid's scheduling
 * priority to the highest value allowed by its current
 * scheduling policy. If pid is zero, sets the current
 * process's priority.
 *
 * Returns zero on success.
 */
int set_highest_priority (pid_t pid) {
      struct sched_param sp;
      int policy, max, ret;
      policy = sched_getscheduler (pid);
      if (policy == ?1)
          return ?1;
      max = sched_get_priority_max (policy);
      if (max == ?1)
          return ?1;
      memset (&sp, 0, sizeof (struct sched_param));
      sp.sched_priority = max;
      ret = sched_setparam (pid, &sp);
      return ret;
 }

#include <sched.h>
struct timespec {
time_t tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
int sched_rr_get_interval (pid_t pid, struct timespec *tp);

struct timespec tp;
int ret;
/* get the current task's timeslice length */
ret = sched_rr_get_interval (0, &tp);
if (ret == ?1) {
    perror ("sched_rr_get_interval");
    return 1; 
}
/* convert the seconds and nanoseconds to milliseconds */
printf ("Our time quantum is %.2lf milliseconds\n", (tp.tv_sec * 1000.0f) + (tp.tv_nsec / 1000000.0f));

Resoucre Limits

#include <sys/time.h>
#include <sys/resource.h>
struct rlimit {
rlim_t rlim_cur; /* soft limit */
rlim_t rlim_max; /* hard limit */
};
int getrlimit (int resource, struct rlimit *rlim);
int setrlimit (int resource, const struct rlimit *rlim);

resource參數(shù)有如下：

• RLIMIT_AS
  限制進程地址空間的最大大小(以字節(jié)為單位)须板。試圖增加超過此限制的地址空間的大小(通過調(diào)用mmap()和brk()將失敗并返回ENOMEM匣吊。如果 進程的堆棧体箕，根據(jù)需要自動增長宰僧，擴展超過這個限制考榨，內(nèi)核向進程發(fā)送SIGSEGV信號瘤袖。這個極限通常是RLIM_INFINITY测柠。
• RLIMIT_CORE
  以字節(jié)為單位確定核心文件的最大大小誉结。如果不是零鹅士，則大于此限制的核心文件將被截斷為最大大小。如果為0惩坑，則永遠不會創(chuàng)建核心文件掉盅。
• RLIMIT_CPU
  指示進程可消耗的最大CPU時間(以秒為單位)。如果進程運行的時間超過此限制以舒，內(nèi)核將向它發(fā)送SIGXCPU信號趾痘，進程可能會捕獲和處理該信號。
  但是蔓钟，Linux允許進程繼續(xù)執(zhí)行永票，并以一秒鐘的間隔繼續(xù)發(fā)送SIGXCPU信號。一旦進程達到hard limit，它將被發(fā)送一個SIGKILL并終止侣集。
• RLIMIT_DATA
  控制進程數(shù)據(jù)段和堆的最大大小键俱，以字節(jié)為單位。 試圖通過 brk () 放大超過此限制的數(shù)據(jù)段將失敗并返回 ENOMEM
• RLIMIT_FSIZE
  指定進程可創(chuàng)建的最大文件大小(以字節(jié)為單位)世分。如果進程擴展超過此大小的文件编振，內(nèi)核將向進程發(fā)送SIGXFSZ信號。默認情況下臭埋，此信號終止過程踪央。但是，一個進程可以選擇捕獲和處理這個信號瓢阴，在這種情況下畅蹂，違規(guī)的系統(tǒng)調(diào)用失敗并返回EFBIG。
• RLIMIT_LOCKS
  控制進程可能持有的文件鎖的最大數(shù)量荣恐。一旦達到此限制液斜，進一步嘗試獲取其他文件鎖會失敗并返回ENOLCK。但是募胃，Linux內(nèi)核2.4.25刪除了此功能旗唁。在當前內(nèi)核中畦浓，此限制是可設(shè)置的痹束，但沒有任何效果。
• RLIMIT_MSGQUEUE
  指定用戶可為POSIX消息隊列分配的最大字節(jié)數(shù)讶请。如果新創(chuàng)建的消息隊列將超過此限制祷嘶，mq_open()將失敗并返回ENOMEM；它是在內(nèi)核2.6.8中添加的夺溢，并且是Linux特有的论巍。
• RLIMIT_NICE
• RLIMIT_NOFILE
• RLIMIT_NPROC
• RLIMIT_RTTIME
  Specifies a limit (in microseconds) on CPU time that a real-time process may consume without issuing a blocking system call. Once the process makes a blocking system call, the CPU time is reset to zero.
• RLIMIT_RTPRIO
• RLIMIT_SIGPENDING
  指定可為此用戶排隊的最大信號數(shù)(標準信號和實時信號)
• RLIMIT_STACK
  表示進程的棧的最大大小，單位為字節(jié)风响。超過此限制會導(dǎo)致SIGSEGV的傳遞嘉汰。

Default soft and hard resource limits

struct rlimit rlim;
int ret;
/* get the limit on core sizes */
ret = getrlimit (RLIMIT_CORE, &rlim);
if (ret == ?1) {
    perror ("getrlimit");
    return 1; 
}
printf ("RLIMIT_CORE limits: soft=%ld hard=%ld\n",
rlim.rlim_cur, rlim.rlim_max);

struct rlimit rlim;
int ret;
rlim.rlim_cur = 32 * 1024 * 1024; /* 32 MB */
rlim.rlim_max = RLIM_INFINITY; /* leave it alone */
ret = setrlimit (RLIMIT_CORE, &rlim);
if (ret == ?1) {
perror ("setrlimit");
return 1; }