1. 關于程序
1.1. 程序的定義
程序：指在系統中能獨立運作并作為資源配置設定的基本機關，它是由一組機器指令、資料和堆棧等組成的，是一個能獨立運作的活動實體。
程序是程式的一次執行
程序是可以和别的計算并行執行
程序是程式在一個資料集合上運作的過程，它是系統進行資源配置設定和排程的一個獨立機關
1.2. 程序的特征
1.動态性：程序的實質是程式的一次執行過程，程序是動态産生，動态消亡的。
2.并發性：任何程序都可以同其他程序一起并發執行。
3.獨立性：程序是一個能獨立運作的基本機關，同時也是系統配置設定資源和排程的獨立機關。
4.異步性：由于程序間的互相制約，使程序具有執行的間斷性，即程序按各自獨立的、不可預知的速度向前推進。
2. 關于程序的組織
task_struct 是Linux核心的一種資料結構，它被裝在到RAM裡并且包含着程序的資訊。每個程序都把它的資訊放在 task_struct 這個資料結構中， task_struct 包含了以下内容：
辨別符：描述本程序的唯一辨別符，用來差別其他程序。
狀态：任務狀态，退出代碼，退出信号等。
優先級：相對于其他程序的優先級。
程式計數器：程式中即将被執行的下一條指令的位址。
記憶體指針：包括程式代碼和程序相關資料的指針，還有和其他程序共享的記憶體塊的指針。
上下文資料：程序執行時處理器的寄存器中的資料。
I/O狀态資訊：包括顯示的I/O請求，配置設定給程序的I/O裝置和被程序使用的檔案清單。
記賬資訊：可以包括處理器時間總和，使用的時鐘數總和，時間限制，記賬号等。
儲存程序資訊的資料結構叫做 task_struct ，并且可以在 include/linux/sched.h 裡找到它。是以運作在系統裡的程序都以 task_struct 連結清單的形式存在于核心中。
2.1. 程序狀态
2.1.1. 程序狀态
volatile longstate;int exit_state;
2.1.2. state成員的可能取值
#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2
#define __TASK_STOPPED 4
#define __TASK_TRACED 8
#define EXIT_ZOMBIE 16
#define EXIT_DEAD 32
#define TASK_DEAD 64
#define TASK_WAKEKILL 128
#define TASK_WAKING 256
2.1.3. 程序的各個狀态
TASK_RUNNING
表示程序正在執行或者處于準備執行的狀态
TASK_INTERRUPTIBLE
程序因為等待某些條件處于阻塞(挂起的狀态)，一旦等待的條件成立，程序便會從該狀态轉化成就緒狀态
TASK_UNINTERRUPTIBLE
意思與TASK_INTERRUPTIBLE類似，但是我們傳遞任意信号等不能喚醒他們，隻有它所等待的資源可用的時候，他才會被喚醒。
TASK_STOPPED
程序被停止執行
TASK_TRACED
程序被debugger等程序所監視。
EXIT_ZOMBIE
程序的執行被終止，但是其父程序還沒有使用wait()等系統調用來獲知它的終止資訊，此時程序成為僵屍程序
EXIT_DEAD
程序被殺死，即程序的最終狀态。
TASK_KILLABLE
當程序處于這種可以終止的新睡眠狀态中，它的運作原理類似于 TASK_UNINTERRUPTIBLE，隻不過可以響應緻命信号
2.1.4. 狀态轉換圖
2.2. 程序辨別符(pid)
2.2.1. 辨別符定義
pid_t pid; //程序的辨別符
2.2.2. 關于辨別符
pid是 Linux 中在其命名空間中唯一辨別程序而配置設定給它的一個号碼，稱做程序ID号，簡稱PID。
程式一運作系統就會自動配置設定給程序一個獨一無二的PID。程序中止後PID被系統回收，可能會被繼續配置設定給新運作的程式。
是暫時唯一的：程序中止後，這個号碼就會被回收，并可能被配置設定給另一個新程序。
2.3. 程序标記符
2.3.1. 标記符
unsigned int flags;
flags反應程序的狀态資訊，用于核心識别目前程序的狀态。
2.3.2. flags的取值範圍
#define PF_EXITING 0x00000004
#define PF_EXITPIDONE 0x00000008
#define PF_VCPU 0x00000010
#define PF_WQ_WORKER 0x00000020
#define PF_FORKNOEXEC 0x00000040
#define PF_MCE_PROCESS 0x00000080
#define PF_SUPERPRIV 0x00000100
#define PF_DUMPCORE 0x00000200
#define PF_SIGNALED 0x00000400
#define PF_MEMALLOC 0x00000800
#define PF_NPROC_EXCEEDED 0x00001000
#define PF_USED_MATH 0x00002000
#define PF_USED_ASYNC 0x00004000
#define PF_NOFREEZE 0x00008000
#define PF_FROZEN 0x00010000
#define PF_FSTRANS 0x00020000
#define PF_KSWAPD 0x00040000
#define PF_MEMALLOC_NOIO 0x00080000
#define PF_LESS_THROTTLE 0x00100000
#define PF_KTHREAD 0x00200000
#define PF_RANDOMIZE 0x00400000
#define PF_SWAPWRITE 0x00800000
#define PF_NO_SETAFFINITY 0x04000000
#define PF_MCE_EARLY 0x08000000
#define PF_MUTEX_TESTER 0x20000000
#define PF_FREEZER_SKIP 0x40000000
#define PF_SUSPEND_TASK 0x80000000
struct task_struct __rcu *parent;
struct list_head children;
struct list_head sibling;
struct task_struct *group_leader;
可以用下面這些通俗的關系來了解它們：real_parent是該程序的”親生父親“，不管其是否被“寄養”；parent是該程序現在的父程序，有可能是”繼父“；這裡children指的是該程序孩子的連結清單，可以得到所有孩子的程序描述符，但是需使用list_for_each和list_entry，list_entry其實直接使用了container_of，同理，sibling該程序兄弟的連結清單，也就是其父親的所有孩子的連結清單。用法與children相似；struct task_struct *group_leader這個是主線程的程序描述符，也許你會奇怪，為什麼線程用程序描述符表示，因為linux并沒有單獨實作線程的相關結構體，隻是用一個程序來代替線程，然後對其做一些特殊的處理；struct list_head thread_group;這個是該程序所有線程的連結清單。
3. 程序的排程
3.1. 完全公平的排程器CFS
CFS(完全公平排程器)是Linux核心2.6.23版本開始采用的程序排程器，它從RSDL/SD中吸取了完全公平的思想，不再跟蹤程序的睡眠時間，也不再企圖區分互動式程序。它将所有的程序都統一對待，這就是公平的含義。它的基本原理如下：設定一個排程周期( sched_latency_ns)，目标是為了讓每個程序在這個周期内至少有機會運作一次，也可以說就是每個程序等待CPU的時間最長不超過這個排程周期；然後根據程序的數量，所有程序平分這個排程周期内的CPU使用權，由于程序的優先級即nice值不同，分割排程周期的時候要權重；每個程序的累計運作時間儲存在自己的vruntime字段裡，哪個程序的vruntime最小就獲得本輪運作的權利。CFS的算法和實作都相當簡單，衆多的測試表明其性能也非常優越。
宏 SCHED_NOMAL 和 SCHED_BATCH 主要用于CFS排程。這幾個宏的定義可以在 include/linux/sched.h 中找到。檔案 kernel/sched.c 包含了核心排程器及相關系統調用的實作。排程的核心函數為 sched.c 中的 schedule() ， schedule 函數封裝了核心排程的架構。細節實作上調用具體的排程算法類中的函數實作，如 kernel/sched_fair.c 或 kernel/sched_rt.c 中的實作。
3.2. 程序排程的算法
在CFS中，當産生時鐘tick中斷時，sched.c中scheduler_tick()函數會被時鐘中斷(定時器timer的代碼)直接調用，我們調用它則是在禁用中斷時。注意在fork的代碼中，當修改父程序的時間片時，也會導緻sched_tick的調用。sched_tick函數首先更新排程資訊，然後調整目前程序在紅黑樹中的位置。調整完成後如果發現目前程序不再是最左邊的葉子，就标記need_resched标志，中斷傳回時就會調用scheduler()完成程序切換，否則目前程序繼續占用CPU。注意這與以前的排程器不同，以前是tick中斷導緻時間片遞減，當時間片被用完時才觸發優先級調整并重新排程。sched_tick函數的代碼如下：
void scheduler_tick(void)
{int cpu =smp_processor_id();struct rq *rq =cpu_rq(cpu);struct task_struct *curr = rq->curr;
sched_clock_tick();
spin_lock(&rq->lock);
update_rq_clock(rq);
update_cpu_load(rq);
curr->sched_class->task_tick(rq, curr, 0);
spin_unlock(&rq->lock);
perf_event_task_tick(curr, cpu);
#ifdef CONFIG_SMP
rq->idle_at_tick =idle_cpu(cpu);
trigger_load_balance(rq, cpu);#endif }
它先擷取目前CPU上的運作隊列中的目前運作程序，更新runqueue級變量clock，然後通過sched_class中的接口名task_tick，調用CFS的tick處理函數task_tick_fair()，以處理時鐘中斷。我們看kernel/sched_fair.c中的CFS算法實作。
具體的排程類如下：
static const struct sched_class fair_sched_class ={
.next= &idle_sched_class,
.enqueue_task=enqueue_task_fair,
.dequeue_task=dequeue_task_fair,
.yield_task=yield_task_fair,
.check_preempt_curr=check_preempt_wakeup,
.pick_next_task=pick_next_task_fair,
.put_prev_task=put_prev_task_fair,
#ifdef CONFIG_SMP
.select_task_rq=select_task_rq_fair,
.load_balance=load_balance_fair,
.move_one_task=move_one_task_fair,
.rq_online=rq_online_fair,
.rq_offline=rq_offline_fair,
.task_waking=task_waking_fair,#endif .set_curr_task=set_curr_task_fair,
.task_tick=task_tick_fair,
.task_fork=task_fork_fair,
.prio_changed=prio_changed_fair,
.switched_to=switched_to_fair,
.get_rr_interval=get_rr_interval_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.task_move_group=task_move_group_fair,#endif };
task_tick_fair函數用于輪詢排程類的中一個程序。實作如下：
static void task_tick_fair(struct rq *rq, struct task_struct *curr, intqueued)
{struct cfs_rq *cfs_rq;struct sched_entity *se = &curr->se;
for_each_sched_entity(se) {cfs_rq=cfs_rq_of(se);
entity_tick(cfs_rq, se, queued);
}
}
該函數擷取各層的排程實體，對每個排程實體擷取CFS運作隊列，調用entity_tick程序進行處理。kernel/sched_fair.c中的函數entity_tick源代碼如下：
static voidentity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, intqueued)
{update_curr(cfs_rq);
#ifdef CONFIG_SCHED_HRTICK
if(queued) {
resched_task(rq_of(cfs_rq)->curr);return;
}
if (!sched_feat(DOUBLE_TICK) &&hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))return;#endif
if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
check_preempt_tick(cfs_rq, curr);
}
該函數用kernel/sched_fair.c:update_curr()更新目前程序的運作時統計資訊，然後調用kernel/sched_fair.c:check_preempt_tick()，檢測是否需要重新排程，用下一個程序來搶占目前程序。update_curr()實作記賬功能,由系統定時器周期調用，實作如下：
static inline void__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
unsignedlongdelta_exec)
{
unsignedlongdelta_exec_weighted;
schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
curr->sum_exec_runtime += delta_exec; schedstat_add(cfs_rq, exec_clock, delta_exec);
delta_exec_weighted= calc_delta_fair(delta_exec, curr);
4. 對作業系統程序模型的看法
作業系統(Operation System)從本質上說，并不是指我們平時看到的那些視窗、菜單、應用程式。那些隻是天邊的浮雲。作業系統其實是隐藏後面，我們根本看不到的部分。作業系統一般來說，工作就是：程序管理、記憶體管理、檔案管理、裝置管理等等。作業系統中最核心的概念是程序， 程序也是并發程式設計中的一個最重要、 最基本的概念。程序是一個動态的過程， 即程序有生命周期， 它擁有資源， 是程式的執行過程， 其狀态是變化的。所謂的排程器，就是程序管理的一部分。
Linux一開始的排程器是複雜度為O(n)的始排程算法, 這個算法的缺點是當核心中有很多任務時，排程器本身就耗費不少時間，是以，從linux2.5開始引入赫赫有名的O(1)排程器。然而，O(1)排程器又被另一個更優秀的排程器取代了，它就是CFS排程器Completely Fair Scheduler. 這個也是在2.6核心中引入的，具體為2.6.23，即從此版本開始，核心使用CFS作為它的預設排程器，O(1)排程器被抛棄了。但其實目前任何排程器算法都還無法滿足所有應用的需要，CFS也有一些負面的測試報告。相信随着Linux的發展，還會有新的排程算法，我們拭目以待。
轉載于:https://www..com/cloudbai/p/8973180.html