---
# System prepended metadata

title: Modified Linux Scheduler

---

# Modified Linux Scheduler

## 編譯 Linux Kernel

1. 從 [Linux 網站](https://www.kernel.org/) 下載 v5.11.11  原始程式碼
2. 使用以下檔案取代 [Modifying the Linux CFS scheduler](https://github.com/arora-ansh/Modified-Linux-Scheduler) 原先 `diff.txt`：
     :::spoiler `diff.txt`
     ```diff
     diff -ruN linux3/linux-5.11.11/arch/x86/entry/syscalls/syscall_64.tbl linux4/linux-5.11.11/arch/x86/entry/syscalls/syscall_64.tbl
    --- linux3/linux-5.11.11/arch/x86/entry/syscalls/syscall_64.tbl	2020-10-27 13:00:09.125164858 -0700
    +++ linux4/linux-5.11.11/arch/x86/entry/syscalls/syscall_64.tbl	2020-11-09 14:43:13.711767973 -0800
    @@ -363,6 +363,7 @@
     439	common	faccessat2			sys_faccessat2
     440	common	process_madvise		sys_process_madvise
     441	common	epoll_pwait2        sys_epoll_pwait2
    +442    common  rtinice			    sys_rtinice

     #
     # x32-specific system call numbers start at 512 to avoid cache impact
    Binary files linux3/linux-5.11.11/certs/signing_key.x509 and linux4/linux-5.11.11/certs/signing_key.x509 differ
    diff -ruN linux3/linux-5.11.11/include/linux/sched.h linux4/linux-5.11.11/include/linux/sched.h
    --- linux3/linux-5.11.11/include/linux/sched.h	2020-10-16 23:31:22.000000000 -0700
    +++ linux4/linux-5.11.11/include/linux/sched.h	2020-11-10 22:19:17.666919549 -0800
    @@ -463,6 +463,7 @@
        u64				prev_sum_exec_runtime;

        u64				nr_migrations;
    +	u64 			rt_val;

        struct sched_statistics		statistics;

    diff -ruN linux3/linux-5.11.11/kernel/sched/core.c linux4/linux-5.11.11/kernel/sched/core.c
    --- linux3/linux-5.11.11/kernel/sched/core.c	2020-10-16 23:31:22.000000000 -0700
    +++ linux4/linux-5.11.11/kernel/sched/core.c	2020-11-10 22:16:56.083024806 -0800
    @@ -3555,6 +3555,7 @@
        p->se.prev_sum_exec_runtime	= 0;
        p->se.nr_migrations		= 0;
        p->se.vruntime			= 0;
    +	p->se.rt_val 			= 0;
        INIT_LIST_HEAD(&p->se.group_node);

     #ifdef CONFIG_FAIR_GROUP_SCHED
    diff -ruN linux3/linux-5.11.11/kernel/sched/fair.c linux4/linux-5.11.11/kernel/sched/fair.c
    --- linux3/linux-5.11.11/kernel/sched/fair.c	2020-10-16 23:31:22.000000000 -0700
    +++ linux4/linux-5.11.11/kernel/sched/fair.c	2020-11-12 01:58:19.030370095 -0800
    @@ -534,6 +534,15 @@
     static inline int entity_before(struct sched_entity *a,
                    struct sched_entity *b)
     {
    +	/* In case both process have rt_vals, the one with lower value will be placed on left in the RB Tree (since higher on priority)
    +	   This is done by returning value of 0 if b is having a lower rt_val, and a value of 1 if a is having a lower rt_val */
    +	if (a->rt_val && b->rt_val)
    +		return b->rt_val > a->rt_val;
    +	else if (a->rt_val)
    +		return 1;
    +	else if (b->rt_val)
    +		return 0;
    +	/* Normal functioning if no two processes has real time soft value given */
        return (s64)(a->vruntime - b->vruntime) < 0;
     }

    @@ -844,6 +864,7 @@
        struct sched_entity *curr = cfs_rq->curr;
        u64 now = rq_clock_task(rq_of(cfs_rq));
        u64 delta_exec;
    +	u64 cur_rt_val;

        if (unlikely(!curr))
            return;
    @@ -860,8 +881,18 @@
        curr->sum_exec_runtime += delta_exec;
        schedstat_add(cfs_rq->exec_clock, delta_exec);

    -	curr->vruntime += calc_delta_fair(delta_exec, curr);
    -	update_min_vruntime(cfs_rq);
    +	cur_rt_val = curr->rt_val;
    +	if (!cur_rt_val) {
    +		curr->vruntime += calc_delta_fair(delta_exec, curr);
    +		update_min_vruntime(cfs_rq);
    +	}
    +	/* Just as in the case of vruntime, we operate on our s_val with delta_exec value. curr stores scheduler entity of the process in operation */
    +	else {
    +		if (delta_exec <= cur_rt_val)
    +			curr->rt_val = cur_rt_val - delta_exec;
    +		else
    +			curr->rt_val = 0;
    +	}

        if (entity_is_task(curr)) {
            struct task_struct *curtask = task_of(curr);
    diff -ruN linux3/linux-5.11.11/Makefile linux4/linux-5.11.11/Makefile
    --- linux3/linux-5.11.11/Makefile	2020-10-27 12:57:13.449981474 -0700
    +++ linux4/linux-5.11.11/Makefile	2020-11-09 14:38:10.538349002 -0800
    @@ -1098,7 +1098,7 @@
     export MODULES_NSDEPS := $(extmod-prefix)modules.nsdeps

     ifeq ($(KBUILD_EXTMOD),)
    -core-y		+= kernel/ certs/ mm/ fs/ ipc/ security/ crypto/ block/
    +core-y		+= kernel/ certs/ mm/ fs/ ipc/ security/ crypto/ block/ rtnice/

     vmlinux-dirs	:= $(patsubst %/,%,$(filter %/, \
                 $(core-y) $(core-m) $(drivers-y) $(drivers-m) \
    diff -ruN linux3/linux-5.11.11/rtnice/Makefile linux4/linux-5.11.11/rtnice/Makefile
    --- linux3/linux-5.11.11/rtnice/Makefile	1969-12-31 16:00:00.000000000 -0800
    +++ linux4/linux-5.11.11/rtnice/Makefile	2020-11-09 14:35:38.107727647 -0800
    @@ -0,0 +1 @@
    +obj-y := rtnice.o
    \ No newline at end of file
    diff -ruN linux3/linux-5.11.11/rtnice/rtnice.c linux4/linux-5.11.11/rtnice/rtnice.c
    --- linux3/linux-5.11.11/rtnice/rtnice.c	1969-12-31 16:00:00.000000000 -0800
    +++ linux4/linux-5.11.11/rtnice/rtnice.c	2020-11-10 22:26:28.780166034 -0800
    @@ -0,0 +1,41 @@
    +#include <linux/kernel.h>
    +#include <linux/init.h>
    +#include <linux/syscalls.h>
    +#include <linux/printk.h>
    +#include <linux/module.h>
    +#include <asm/uaccess.h>
    +#include <linux/fs.h> 
    +#include <linux/cdev.h>
    +#include <linux/proc_fs.h>
    +#include <linux/pid.h>
    +#include <linux/pid_namespace.h>
    +#include <linux/sched.h>
    +#include <linux/string.h>
    +#include <linux/errno.h>
    +#include <linux/uaccess.h>
    +#include <linux/mm.h>
    +
    +SYSCALL_DEFINE2(rtnice, int,pid, long, rt_val) {
    +
    +	struct pid *pid_struct = NULL;
    +	struct task_struct *process;
    +	unsigned long long s_val;
    +	
    +	if (rt_val < 0 || pid < 0) {
    +		return -EINVAL;
    +	}	
    +	
    +	s_val = rt_val * 1000000000;
    +
    +	pid_struct = find_get_pid(pid);
    +	if (pid_struct == NULL) {
    +		return -ESRCH;
    +	}
    +	process = pid_task(pid_struct, PIDTYPE_PID);
    +
    +	process->se.rt_val = s_val;
    +	printk(KERN_ALERT "Value of real time req of PID: %d changed to %llu succesfully\n", pid, process->se.rt_val);
    +
    +	return 0;
    +
    +}
    ```
    :::
3. 將原先 [Modifying the Linux CFS scheduler](https://github.com/arora-ansh/Modified-Linux-Scheduler) 的 `test.c` 與 `test2.c` 內的 syscall 呼叫號碼改為 ==442==
5. 使用 patch 工具變更 Linux 核心原始碼，將 `diff.txt` 與 `linux` 目錄放置在同一層：
    ```
    base
     |--linux-5.11.11
     |--diff.txt
    ```
    在 base 目錄中執行以下命令：
    ```shell
    patch -p1 < diff.txt
    ```

    :::danger
    * 從 github 上下載的 `diff.txt` 必須加上 end of line，否則 patch 時會產生會出錯。 [參考資料](https://unix.stackexchange.com/questions/1395/what-does-patch-unexpectedly-ends-in-middle-of-line-mean)
    * 如有自行新增過 syscall，則在 `syscall_64.tbl` 內添加的 `sys_rtinice` 代號以及 `Makefile` 須自行更改。
    :::


3. 依照 [建構 User-Mode Linux 的實驗環境](https://hackmd.io/@sysprog/user-mode-linux-env#%E5%BB%BA%E6%A7%8B-User-Mode-Linux-%E7%9A%84%E5%AF%A6%E9%A9%97%E7%92%B0%E5%A2%83) 指示建立 User Mode Linux

## 編譯測試程式碼

新增以下 Makefile：
```diff
all:
    gcc -static -fopenmp -o test1 test.c
    gcc -static -fopenmp -o test2 test.c

clear:
    rm test1 test2
```

`-static` 用來指示靜態編譯，以便在 UML 中執行；`-fopenmp` 使用於 `omp_get_wtime` 函式。

將編譯完的執行檔複製到 UML 的 rootfs 下：

```
cp test1 linux-5.11.11/rootfs
cp test2 linux-5.11.11/rootfs
```

啟動 UML，執行 `test1` 與 `test2`。

## 執行結果
```cpp
/ # ./test1
Without Soft Real-Time Values- 
Process finished in 11.104824 seconds 
Process finished in 11.094899 seconds 
Process finished in 11.080569 seconds 
Process finished in 11.177793 seconds 
Process finished in 11.146516 seconds 
Process finished in 11.128278 seconds 
Process finished in 11.210612 seconds 
Process finished in 11.190418 seconds 
Process finished in 11.221518 seconds 
Process finished in 11.246885 seconds 
With Soft Real-Time Values- 
Value of real time req of PID: 59 changed to 25000000000 succesfully
Process with RT finished in 1.139814 seconds 
Value of real time req of PID: 57 changed to 15000000000 succesfully
Process with RT finished in 2.266486 seconds 
Value of real time req of PID: 56 changed to 10000000000 succesfully
Process with RT finished in 3.391552 seconds 
Value of real time req of PID: 55 changed to 5000000000 succesfully
Process with RT finished in 4.531643 seconds 
Value of real time req of PID: 64 changed to 50000000000 succesfully
Process with RT finished in 5.677368 seconds 
Value of real time req of PID: 63 changed to 45000000000 succesfully
Process with RT finished in 6.824231 seconds 
Value of real time req of PID: 62 changed to 40000000000 succesfully
Process with RT finished in 7.972721 seconds 
Value of real time req of PID: 61 changed to 35000000000 succesfully
Process with RT finished in 9.101606 seconds 
Value of real time req of PID: 60 changed to 30000000000 succesfully
Process with RT finished in 10.230780 seconds 
Value of real time req of PID: 58 changed to 20000000000 succesfully
Process with RT finished in 11.382185 seconds 
ERROR CHECK (Y=1 or 2/N=3) 3

/ # ./test2
With Mix of Non Soft-Time and Soft Real-Time Values- 
Value of real time req of PID: 72 changed to 700000000000 succesfully
7. with RT 1.132002 seconds 
Value of real time req of PID: 73 changed to 800000000000 succesfully
8. with RT 2.269580 seconds 
Value of real time req of PID: 67 changed to 200000000000 succesfully
2. with RT 3.458060 seconds 
10. 11.185943 seconds 
4. 11.205015 seconds 
1. 11.215062 seconds 
6. 11.224214 seconds 
3. 11.233990 seconds 
9. 11.235572 seconds 
5. 11.228095 seconds 
```