需要修改的文件

M 代表修改，C代表新建，D代表删除

  • /src/include/unistd.h (M) ：提供对 POSIX 操作系统 API 的访问功能的头，添加系统调用chrt
  • /src/minix/lib/libc/sys/chrt.c (C)

  • /usr/src/minix/lib/libc/sys/Makefile.inc (M)

  • /src/minix/servers/pm/proto.h (M)
  • /src/minix/servers/pm/chrt.c (C)
  • /src/minix/include/minix/callnr.h (M)
  • /src/minix/servers/pm/Makefile (M)
  • /src/minix/servers/pm/table.c (M) ：定义进程属性相关的变量
  • /src/minix/include/minix/syslib.h (M)
  • /src/minix/lib/libsys/sys_chrt.c (C)

  • /src/minix/lib/libsys/Makefile (M)

  • /src/minix/kernel/system.h (M)
  • /src/minix/kernel/system/do_chrt.c (C)
  • /src/minix/kernel/system/Makefile (M)
  • /src/minix/include/minix/com.h (M) ：定义在服务器和驱动程序设备间通信
  • /src/minix/kernel/config.h(M) ：内核版本收集不太可能更改的定义编号
  • /src/minix/kernel/system.c (M)

  • /src/minix/commands/service/parse.c (M)

  • /src/minix/kernel/proc.h(M) ：定义内核进程表
  • /src/minix/kernel/proc.c(M)

应用层

首先，根据文档要求：

image-20220327143508412

准备工作：先在 /src/include/unistd.h 与 /src/minix/lib/libc/sys/Makefiles.inc 中添加 int chrt(long) 与 chrt.c，并在 /src/minix/lib/libc/sys 中新增文件 chrt.c

image-20220328180759726

image-20220328180820431

随后，根据文档中对函数的说明与要求：

image-20220327140238463

我们知道，函数 int chrt(long) 输入的参数 deadline 是指进程运行的时长，在此函数中，我们需要做的事情有三件：

  1. 设置 alarm
  2. 将 deadline 设置为进程的终止时间
  3. 通过 MINIX 的 IPC 通信机制（通过message结构体来传输信息），将 deadline 传到服务层

按照这个步骤来写 chrt 函数，我们首先需要知道 alarm 的工作原理与调用方法（见《UNIX环境高级编程》10.10）：

#include <unistd.h>

unsigned int alarm(unsigned int seconds);

当调用这个函数开始，可以设置一个定时器，持续 seconds 秒，当超过这个时间时，产生一个 SIGALRM 信号，若忽略或不捕捉这个信号，则默认动作是终止调用 alarm 函数的进程。

而这里 seconds 的类型是 unsigned int ，deadline 类型却是 long，为防止一些类型不匹配而可能带来的错误，我们在一开始就应当对 deadline 的大小进行判断，于是得到代码如下：

/* int chrt(long); */
int chrt(long deadline){
    if(deadline <= 0)
        return 0; /* syscall error */
    alarm((unsigned int)deadline);
    return 1;
}

接下来进行第二步，若想知道进程的实际终止时间，显然，我们必须要得到当前时间，这里用 t 来表示。

我们可以通过系统调用 clock_getttime （ 同目录下的\src\minix\lib\libc\sys\clock_gettime.c）来获得系统的当前时间，并将其加上 deadline 即可得到进程实际的终止时间。

阅读 \src\minix\lib\libc\sys\clock_gettime.c 的源码：

int clock_gettime(clockid_t clock_id, struct timespec *res)
{
  message m;

  memset(&m, 0, sizeof(m));
  m.m_lc_pm_time.clk_id = clock_id;

  if (_syscall(PM_PROC_NR, PM_CLOCK_GETTIME, &m) < 0)
  	return -1;

  res->tv_sec = m.m_pm_lc_time.sec;
  res->tv_nsec = m.m_pm_lc_time.nsec;

  return 0;
}

显然，我们需要找到 timespec 的定义，经过一番查找，发现他在\src\sys\sys\time.h 中，定义描述为：

/*
 * Structure defined by POSIX.1b to be like a timeval.
 */
struct timespec {
	time_t	tv_sec;		/* seconds */
	long	tv_nsec;	/* and nanoseconds */
};

那么回去看 clock_gettime 就能大概明白一些内容，当然还是会有一些不太明白，比如参数 clock_id 的含义，在《UNIX环境高级编程》 P687可以找到定义：

  • CLOCK_REALTIME：系统实时时间，随系统实时时间改变而改变，即从UTC 1970-1-1 0:0:0开始计时，中间时刻如果系统时间被用户改成其他，则对应的时间相应改变。
  • CLOCK_MONOTONIC：从系统启动这一刻起开始计时，不受系统时间被用户改变的影响。
  • CLOCK_PROCESS_CPUTIME_ID：本进程到当前代码系统CPU花费的时间。
  • CLOCK_THREAD_CPUTIME_ID：本线程到当前代码系统CPU花费的时间

可以看看 wiki 来了解这些参数的意义。

由于参数 deadline 表示的是秒，于是我们只需要这里的成员变量 tv_sec，那么可得到代码如下：

/* int chrt(long); */
int chrt(long deadline){
    /* other code omitted */
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    deadline = t.tv_sec + deadline;
}

最后，我们只需要将 deadline 通过信息传递到服务层即可，源码可以发现都使用了 message 这一数据类型，寻找 message 类型的定义：

\src\minix\include\minix\ipc.h

由于定义太长，就不贴出来了。我们知道，现在的 deadline 已经变为表示进程实际结束的时间了，于是我们只需要使 message 中的某个成员等于 deadline，再通过 _syscall() 传递信息即可。

可以在MINIX的wiki上找到关于Message结构体的一些描述，也可以自己硬看(wiki上也有message定义的文件的地址）。这里选择联合体中的一个成员来传递deadline ，为了防止由于类型转换带来的一些可能的问题（一直在说的），最好找类型也是 long 的成员，并且必须在 mess_1 ~mess_10中寻找（后续带有名字的可能有其他作用）。

可以选mess_2,mess_4,mess_10，综合后续还需要传递 endpoint 类型的数据，这里选择mess_2中的m2l1/m2l2。通过2263行开始的宏定义，我们可以简写为m2_l1/m2_l2，于是，代码如下：

/* int chrt(long); */
int chrt(long deadline){
    /* other code omitted */
    message m;
    memset(m, 0, sizeof(m));
    m.m2_l1 = deadline;
    return _syscall(PM_PROC_NR, PM_CHRT, &m);
}

自此，应用层的 chrt 函数就已经结束，仿照源码的代码风格，我们修改后如下：

#include <sys/cdefs.h>
#include "namespace.h"
#include <lib.h>

#include <string.h>
#include <unistd.h>
#include <sys/time.h>

// #ifdef __weak_alias
// __weak_alias(chrt, _chrt)
// #endif

int chrt(long deadline) {
    message m;
    
    memset(&m, 0, sizeof(m));
    if (deadline <= 0)
        return 0;

    alarm((unsigned int)deadline);
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    deadline = t.tv_sec + deadline;
    
    m.m2_l1 = deadline;
    return _syscall(PM_PROC_NR, PM_CHRT, &m);
}

服务层

首先根据文档，修改文件：

image-20220327155949944

添加定义 int do_chrt(void);、 #define PM_CHRT (PM_BASE + 48) 、chrt.c

image-20220328180728048

image-20220404210428765

image-20220328181428566

根据文档说明，添加函数实现：

image-20220327160236668

我们可以在同目录下的 glo.h 文件中找到关于 who_p等类型的定义：

/* The parameters of the call are kept here. */
EXTERN message m_in;		/* the incoming message itself is kept here. */
EXTERN int who_p, who_e;	/* caller's proc number, endpoint */
EXTERN int call_nr;		/* system call number */

由于sys_chrt需要参数deadline，而我们在应用层中将 deadline 放进了 m2_l1中，于是：

#include "pm.h"
#include <signal.h>
#include <sys/time.h>
#include <minix/com.h>
#include <minix/callnr.h>
#include "mproc.h"

int do_chrt(void){
    sys_chrt(who_p, m_in.m2_l1);
    
    return OK;
}

(用OK的原因是因为此目录下其他的.c文件都是这样return的…..)

然后开始对着步骤改文件

image-20220327162046569

image-20220328185632697

image-20220328185934679

image-20220328190909015

sys_chrt.c代码如下：

#include "syslib.h"

int sys_chrt(proc_ep, deadline)
endpoint_t proc_ep;
long deadline;
{
    message m;
    int r;

    m.m2_i1 = proc_ep;
    m.m2_l1 = deadline;
    r = _kernel_call(SYS_CHRT, &m);
    return r;
}

这里使用 m2_i1 是因为 endpoint_t 类型是4字节的数，这在 Message Wiki中详细介绍了，因此这里可以使用int类型的m2_i1来记录此变量

事实上我认为，应该选用unsigned int类型来记录，可惜没有这样的成员，但在MINIX里存在int与unsigned int共用域的情况

内核层

先把要改要加的东西弄完

image-20220327181302463

image-20220328200514352

image-20220328191303025

image-20220328191614036

image-20220404210453240

image-20220328201451522

需要注意的是，由system.h和do_fork.c中的IF USE_CHRT和IF USE_FORK知，应在某一.h文件中定义该条目，在同目录下找寻发现，我们还需要在 config.h 文件中定义 USE_CHRT 为1

image-20220328194610634

修改完后，根据文档说明编写do_chrt函数：

image-20220327181642082

由于我们的参数中含有struct proc，因此我们还需要去阅读 proc.h 中关于 proc 的定义，可以在 proc.h 中找到 proc_addr的的定义，根据文档说明，do_chrt.c文件如下：

#include "kernel/system.h"
#include "kernel/vm.h"
#include <signal.h>
#include <string.h>
#include <assert.h>

#include <minix/endpoint.h>
#include <minix/u64.h>

#if USE_CHRT

/*===========================================================================*
 *				do_chrt				     *
 *===========================================================================*/
int do_chrt(struct proc* caller, message* m_ptr) {
    struct proc* p;

    p = proc_addr(m_ptr->m2_i1);
    p->deadline = m_ptr->m2_l1;

    return OK;
}


#endif /* USE_CHRT */

进程调度

根据文档，我们需要修改几个函数，进而修改判断进程优先级的判定法则：

image-20220327191632025

image-20220328202310510

优先级的判定为：最早deadline的用户进程相对于其它用户进程具有更高的优先级，从而被优先调度运行。

可以发现在 proc.h 中可以找到成员 ` char p_priority; 用于记录优先级，在 \src\minix\include\minix\config.h`中可以找到最高优先级为0，于是，我们便可以开始修改一些函数

首先，进入函数 switch_to_user()，阅读注释可以很好的理解代码

先更改 enqueue_head() 中关于优先级的定义，阅读注释，可知rp为正在运行的进程，需将其按照优先级加入队列

image-20220406122243256

于是我们将所有deadline > 0的进程优先级全部设为5（经尝试，优先级为01234时无法正确实现进程调度，推测应为属于内核层的进程的优先级，经过后续书本的学习，发现分别为内核层驱动层服务层进程）

if (rp->deadline > 0)
    rp->p_priority = 5;
const int q = rp->p_priority;	 		/* scheduling queue to use */

随后更改 enqueue() 中关于优先级的定义，与上面的做法相同

最后更改pick_proc()中对于相同优先级下进程的选择，由于设置了deadline的进程优先级都为5，这些进程组成了一个列表，这里通过proc.h中可以看出来：

struct proc* p_nextready;  /* pointer to next ready process */

于是我们通过遍历优先级为5的进程组成的列表，选择出设置了deadline并且deadline的值最小的进程，过程中需要对这些进程进行判断是否可运行（proc_is_runnable())，最后返回这个选择的进程

for (q=0; q < NR_SCHED_QUEUES; q++) {	
	if(!(rp = rdy_head[q])) {
		TRACE(VF_PICKPROC, printf("cpu %d queue %d empty\n", cpuid, q););
		continue;
	}
	assert(proc_is_runnable(rp));
	struct proc* t;
	if (q == 5) {
    	t = rp->p_nextready;
		while(t){
			if (t->p_deadline > 0 &&
                (!rp->p_deadline || t->p_deadline < rp->p_deadline))
                if (proc_is_runnable(t))
        			rp = t;
    		t = t->p_nextready;
		}
  	}
	if (priv(rp)->s_flags & BILLABLE)	 	
		get_cpulocal_var(bill_ptr) = rp; /* bill for system time */
	return rp;
}