第一次作業

1.摘要

本文主要針對Linux Kernel 2.6.28核心版本，描述了程序的概念以及調用過程。

Linux Kernel源碼查閱位址：https://elixir.bootlin.com/linux/v4.6/source/include/linux/types.h

2. 何謂程序

2.1 程序的概念

程序的一種官方定義：

程序是一個具有一定獨立功能的程式關于某個資料集合的一次運作活動，也是作業系統進行資源配置設定和排程的一個獨立機關。

簡而言之，程序是作業系統為正在運作的程式所建立的一個管理執行個體。

而一個程序包括五個實體部：

（OS管理運作程式的）資料結構P
（運作程式的）記憶體代碼C
（運作程式的）記憶體資料D
（運作程式的）通用寄存器資訊R
（OS控制程式執行的）程式狀态字資訊PSW

2.2 看得見的程序

2.2.1 Windows上的程序：

第一次作業：Linux 2.6.28程式模型與CFS排程器分析第一次作業

2.2.2 Ubuntu上的程序

第一次作業：Linux 2.6.28程式模型與CFS排程器分析第一次作業

3.程序是如何組織的

在Linux 核心中，有一種結構體用來描述與關聯程序：

task_struct

，該資料結構在

/include/linux/sched.h

中被定義，它的代碼量足有400行之多。

3.1 程序ID

程序ID的定義儲存在

include/linux/pid.h

中：

enum pid_type
{
    PIDTYPE_PID,
    PIDTYPE_PGID,
    PIDTYPE_SID,
    PIDTYPE_MAX
};

在此我們對其中最重要的PID進行詳解。

3.1.1 程序辨別符（PID）

Linux中會給程序配置設定一個唯一的程序ID，即PID。他是程序在系統中的唯一代号，但一個程序ID并非永久被一個程序所擁有，不同時刻運作程序所獲得的PID不盡相同，使用 fork 或 clone 系統調用時産生的程序均會由核心配置設定一個新的唯一的PID值。

pid_t pid;

如上述代碼所示，PID在

task_struct

中的定義為

pid_t

,而它究其根本其實就是

int

型，故PID的實質就是一個數字。

3.1.2 PID的範圍

在

include/linux/threads.h

中，系統對PID數值的最大值作出了限制。

#define PID_MAX_DEFAULT (CONFIG_BASE_SMALL ? 0x1000 : 0x8000)

由此可見，一般情況下Linux系統中的程序最大數為32768個。

3.1.3 PID的産生

那麼PID又從何而來？

kernel/pidc

中給出了這個問題的答案：

static int alloc_pidmap(struct pid_namespace *pid_ns)
{
    int i, offset, max_scan, pid, last = pid_ns->last_pid;
    struct pidmap *map;

    pid = last + 1;
    if (pid >= pid_max)
        pid = RESERVED_PIDS;
    offset = pid & BITS_PER_PAGE_MASK;
    map = &pid_ns->pidmap[pid/BITS_PER_PAGE];
    max_scan = (pid_max + BITS_PER_PAGE - 1)/BITS_PER_PAGE - !offset;
    for (i = 0; i <= max_scan; ++i) {
        if (unlikely(!map->page)) {
            void *page = kzalloc(PAGE_SIZE, GFP_KERNEL);
            /*
             * Free the page if someone raced with us
             * installing it:
             */
            spin_lock_irq(&pidmap_lock);
            if (map->page)
                kfree(page);
            else
                map->page = page;
            spin_unlock_irq(&pidmap_lock);
            if (unlikely(!map->page))
                break;
        }
        if (likely(atomic_read(&map->nr_free))) {
            do {
                if (!test_and_set_bit(offset, map->page)) {
                    atomic_dec(&map->nr_free);
                    pid_ns->last_pid = pid;
                    return pid;
                }
                offset = find_next_offset(map, offset);
                pid = mk_pid(pid_ns, map, offset);
            /*
             * find_next_offset() found a bit, the pid from it
             * is in-bounds, and if we fell back to the last
             * bitmap block and the final block was the same
             * as the starting point, pid is before last_pid.
             */
            } while (offset < BITS_PER_PAGE && pid < pid_max &&
                    (i != max_scan || pid < last ||
                        !((last+1) & BITS_PER_PAGE_MASK)));
        }
        if (map < &pid_ns->pidmap[(pid_max-1)/BITS_PER_PAGE]) {
            ++map;
            offset = 0;
        } else {
            map = &pid_ns->pidmap[0];
            offset = RESERVED_PIDS;
            if (unlikely(last == offset))
                break;
        }
        pid = mk_pid(pid_ns, map, offset);
    }
    return -1;
}

alloc_pidmap

函數用以配置設定PID，而同樣的，

kernel/pid.h

中同樣定義的回收PID的方法：

static void free_pidmap(struct upid *upid)
{
    int nr = upid->nr;
    struct pidmap *map = upid->ns->pidmap + nr / BITS_PER_PAGE;
    int offset = nr & BITS_PER_PAGE_MASK;

    clear_bit(offset, map->page);
    atomic_inc(&map->nr_free);
}

3.2程序的狀态

3.2.1 程序狀态定義

在Linux中，主要有6種程序狀态：

代号	名稱	描述
R	TASK_RUNNING	可執行狀态
S	TASK_INTERRUPTIBLE	可中斷的睡眠狀态
D	TASK_UNINTERRUPTIBLE	不可中斷的睡眠狀态
T	TASK_STOPPED or TASK_TRACED	暫停狀态或跟蹤狀态
Z	TASK_DEAD - EXIT_ZOMBIE	退出狀态，程序成為僵屍程序
X	TASK_DEAD - EXIT_DEAD	退出狀态，程序即将被銷毀

它們在

include/linux/sched.h

中被定義：

#define TASK_RUNNING            0
#define TASK_INTERRUPTIBLE      1
#define TASK_UNINTERRUPTIBLE    2
#define TASK_STOPPED            4
#define EXIT_ZOMBIE            16
#define EXIT_DEAD              32

在一些作業系統教科書中，RUNNING狀态意指正在CPU中執行的程序，而将可執行但尚未被調用的狀态定義為READY（就緒）狀态，上述兩種狀态在Linux中被統一定義為TASK_RUNNING狀态。
在機器正常運作的情況下，系統中的大部分程序都處于TASK_INTERRUPTIBLE狀态，而既要保持快速調動又不能過多占用CPU資源的原則使其顯得理所當然。
睡眠狀态為何又分為可中斷與不可中斷兩種呢？其意義大概在于避免在程序與裝置互動的過程中被打斷，進而導緻機器陷入不可控的狀态。
程序在退出的過程中處于TASK_DEAD狀态，此時程序占用的絕大部分資源将會被回收，除了 task_struct 等少數特殊資源，故此時這種欲去還留的狀态被稱為僵屍（ZOMBIE）。

3.2.2 程序狀态轉換

以下這張圖對系統中程序狀态的轉換作了簡要概述：

第一次作業：Linux 2.6.28程式模型與CFS排程器分析第一次作業

盡管系統中存在6種不同的程序狀态，但程序狀态的轉換實質上隻有TASK_RUNNING與非TASK_RUNNING之間的互相轉變。

例如當一個TASK_INTERRUPTIBLE狀态程序收到結束指令時，并非直接轉變為TASK_DEAD狀态，而是先被喚醒進入TASK_RUNNING狀态，再由TASK_RUNNING狀态進入TASK_DEAD狀态。而當一個程序正處于TASK_RUNNING狀态時，它僅有兩種選擇：響應信号進入TASK_STOPED或TASK_DEAD狀态，否則即為執行系統調用進入TASK_INTERRUPTIBLE狀态。

4.程序是如何排程的

4.1 CFS排程器

随着核心版本的更疊，O(1)排程器在Linux Kernel 2.6.23版本之後被CFS（完全公平排程器）所取代。

CFS使用

vruntime

以衡量程序的優先程度。它的計算公式如下

vruntime = 程序被配置設定的運作時間 * NICE_0_LOAD / 程序權重

其中

NICE_0_LOAD

代表nice為0的程序的權重，其值為1024，而程序權重則與nice值一一對應，借由全局數組

prio_to_weight

轉換。

static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

但程序運作時間又從何得知呢?

它的計算公式為

程序實際運作時間 = 排程周期 * 程序權重 / 所有程序權重之和

其中排程周期是将所有處于TASK_RUNNING狀态的程序都排程一遍的時間。

如若将程序運作理想化，即将程序實際運作時間當做系統配置設定給它的運作時間，再聯系上兩式可得

vruntime = （排程周期 * 程序權重 / 所有程序權重之和）* 1024 / 程序權重 = 排程周期 * 1024 / 所有程序總權重

借由上式我們可以發現：即使不同程序的權重不盡相同，但理想情況下

vruntime

理當相同，故如若一個程序的

vruntime

值較小，也就說明它沒有得到它應得的運作時間，此時作業系統理應優先選擇它運作。

以上即是CFS的主要思想。

vruntime

與程序權重等儲存在

sched_entity

資料結構中，它是一個排程實體，在

include/linux/sched.h

中被定義：

struct sched_entity {
    struct load_weight  load;       /* for load-balancing */
    struct rb_node      run_node;
    struct list_head    group_node;
    unsigned int        on_rq;
    u64         exec_start;
    u64         sum_exec_runtime;
    u64         vruntime;
    u64         prev_sum_exec_runtime;
    u64         last_wakeup;
    u64         avg_overlap;
#ifdef CONFIG_SCHEDSTATS
    u64         wait_start;
    u64         wait_max;
    u64         wait_count;
    u64         wait_sum;
    u64         sleep_start;
    u64         sleep_max;
    s64         sum_sleep_runtime;
    u64         block_start;
    u64         block_max;
    u64         exec_max;
    u64         slice_max;
    u64         nr_migrations;
    u64         nr_migrations_cold;
    u64         nr_failed_migrations_affine;
    u64         nr_failed_migrations_running;
    u64         nr_failed_migrations_hot;
    u64         nr_forced_migrations;
    u64         nr_forced2_migrations;
    u64         nr_wakeups;
    u64         nr_wakeups_sync;
    u64         nr_wakeups_migrate;
    u64         nr_wakeups_local;
    u64         nr_wakeups_remote;
    u64         nr_wakeups_affine;
    u64         nr_wakeups_affine_attempts;
    u64         nr_wakeups_passive;
    u64         nr_wakeups_idle;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity *parent;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq       *cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq       *my_q;
#endif
};

4.2 紅黑樹

不同的

sched_entity

由一個以時間為順序的紅黑樹組織在一起：

第一次作業：Linux 2.6.28程式模型與CFS排程器分析第一次作業

vurtime

值最小的程序儲存在樹的左側，如此便可以迅速選中

vruntime

值最小的程序。

5.對作業系統程序模型的看法

長久以來，作業系統都試圖對公平下定義，是否互動式程序就一定具有絕對話語權？CFS給出了他的答案，它不再企圖區分互動式程序，而是對所有程序都一視同仁，就如它的名字一樣，Completely Fair。它的出現令赫赫有名的O(1)排程器也僅是昙花一現，Linux發展至今已跨越諸多版本，而CFS始終沒有被取代，它用自己獨特的優越性宣示着自己的主權。

6.參考資料

程序的狀态--CSDN部落格

程序ID--CSDN部落格

CFS排程器--CSDN部落格

轉載于:https://www.cnblogs.com/xeathens/p/8955052.html

第一次作業：Linux 2.6.28程序模型與CFS排程器分析第一次作業

第一次作業

1.摘要

2. 何謂程序

2.1 程序的概念

2.2 看得見的程序

2.2.1 Windows上的程序：

2.2.2 Ubuntu上的程序

3.程序是如何組織的

3.1 程序ID

3.1.1 程序辨別符（PID）

3.1.2 PID的範圍

3.1.3 PID的産生

3.2程序的狀态

3.2.1 程序狀态定義

3.2.2 程序狀态轉換

4.程序是如何排程的

4.1 CFS排程器

4.2 紅黑樹

5.對作業系統程序模型的看法

6.參考資料

繼續閱讀

Storm編譯打包過程中遇到的一些問題及解決方法

ansible配置檔案說明及ad hoc指令

vsftpd dead but subsys locked 的解決方法

作業系統（python）多程序學習

Shell程式設計——sort排序、uniq忽略重複、tr替換壓縮删除、cut指定删除字段、正規表達式元字元sort 指令uniq 指令tr 指令cut 指令正規表達式

Linxu常用指令技巧彙總

httpd服務的部署、啟動、配置和簡單優化一、部署二、啟動三、配置檔案

PAT 1089 Insert or Merge[難]

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

ACS基本配置-權限等級管理

nginx 安裝錯誤資訊解決

傳說FreeBSD等比Linux更穩定，更“健壯”

無人機--飛控科普

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Ambari介紹和架構原理