实验四 进程运行轨迹的跟踪与统计
实验目的
掌握 Linux 下的多进程编程技术；
通过对进程运行轨迹的跟踪来形象化进程的概念；
在进程运行轨迹跟踪的基础上进行相应的数据统计，从而能对进程调度算法进行实际的量化评价，更进一步加深对调度和调度算法的理解，获得能在实际操作系统上对调度算法进行实验数据对比的直接经验。
实验内容
进程从创建（Linux 下调用 fork()）到结束的整个过程就是进程的生命期，进程在其生命期中的运行轨迹实际上就表现为进程状态的多次切换，如进程创建以后会成为就绪态；当该进程被调度以后会切换到运行态；在运行的过程中如果启动了一个文件读写操作，操作系统会将该进程切换到阻塞态（等待态）从而让出 CPU；当文件读写完毕以后，操作系统会在将其切换成就绪态，等待进程调度算法来调度该进程执行……
本次实验包括如下内容：
基于模板 process.c 编写多进程的样本程序，实现如下功能： + 所有子进程都并行运行，每个子进程的实际运行时间一般不超过 30 秒； + 父进程向标准输出打印所有子进程的 id，并在所有子进程都退出后才退出；
在 Linux0.11 上实现进程运行轨迹的跟踪。 + 基本任务是在内核中维护一个日志文件 /var/process.log，把从操作系统启动到系统关机过程中所有进程的运行轨迹都记录在这一 log 文件中。
在修改过的 0.11 上运行样本程序，通过分析 log 文件，统计该程序建立的所有进程的等待时间、完成时间（周转时间）和运行时间，然后计算平均等待时间，平均完成时间和吞吐量。可以自己编写统计程序进行统计。
修改 0.11 进程调度的时间片，然后再运行同样的样本程序，统计同样的时间数据，和原有的情况对比，体会不同时间片带来的差异。
/var/process.log 文件的格式必须为：
pid X time
其中：
pid 是进程的 ID；
X 可以是 N、J、R、W 和 E 中的任意一个，分别表示进程新建(N)、进入就绪态(J)、进入运行态®、进入阻塞态(W) 和退出(E)；
time 表示 X 发生的时间。这个时间不是物理时间，而是系统的滴答时间(tick)；
三个字段之间用制表符分隔。例如：
12 N 1056 12 J 1057 4 W 1057 12 R 1057 13 N 1058 13 J 1059 14 N 1059 14 J 1060 15 N 1060 15 J 1061 12 W 1061 15 R 1061 15 J 1076 14 R 1076 14 E 1076 ......
编写process.c文件
提示
在 Ubuntu 下，top 命令可以监视即时的进程状态。在 top 中，按 u，再输入你的用户名，可以限定只显示以你的身份运行的进程，更方便观察。按 h 可得到帮助。
在 Ubuntu 下，ps 命令可以显示当时各个进程的状态。ps aux 会显示所有进程；ps aux | grep xxxx 将只显示名为 xxxx 的进程。更详细的用法请问 man。
在 Linux 0.11 下，按 F1 可以即时显示当前所有进程的状态。
文件主要作用
process.c文件主要实现了一个函数：
/* * 此函数按照参数占用CPU和I/O时间 * last: 函数实际占用CPU和I/O的总时间，不含在就绪队列中的时间，>=0是必须的 * cpu_time: 一次连续占用CPU的时间，>=0是必须的 * io_time: 一次I/O消耗的时间，>=0是必须的 * 如果last > cpu_time + io_time，则往复多次占用CPU和I/O，直到总运行时间超过last为止 * 所有时间的单位为秒 */ cpuio_bound(int last, int cpu_time, int io_time);
下面是 4 个使用的例子：
// 比如一个进程如果要占用10秒的CPU时间，它可以调用： cpuio_bound(10, 1, 0); // 只要cpu_time>0，io_time=0，效果相同 // 以I/O为主要任务： cpuio_bound(10, 0, 1); // 只要cpu_time=0，io_time>0，效果相同 // CPU和I/O各1秒钟轮回： cpuio_bound(10, 1, 1); // 较多的I/O，较少的CPU： // I/O时间是CPU时间的9倍 cpuio_bound(10, 1, 9);
修改此模板，用 fork() 建立若干个同时运行的子进程，父进程等待所有子进程退出后才退出，每个子进程按照你的意愿做不同或相同的 cpuio_bound()，从而完成一个个性化的样本程序。
它可以用来检验有关 log 文件的修改是否正确，同时还是数据统计工作的基础。
wait() 系统调用可以让父进程等待子进程的退出。
关键函数解释
fork()
这里摘录某位博主的详解操作系统之 fork() 函数详解 - 简书 (jianshu.com)
fork（）函数通过系统调用创建一个与原来进程几乎完全相同的进程，也就是两个进程可以做完全相同的事，但如果初始参数或者传入的变量不同，两个进程也可以做不同的事。
一个进程调用fork（）函数后，系统先给新的进程分配资源，例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的新进程中，只有少数值与原来的进程的值不同。相当于克隆了一个自己。
#include <unistd.h> #include <stdio.h> int main () { pid_t fpid; //fpid表示fork函数返回的值 int count=0; fpid=fork(); if (fpid < 0) printf("error in fork!"); else if (fpid == 0) { printf("i am the child process, my process id is %d/n",getpid()); printf("我是爹的儿子/n");//对某些人来说中文看着更直白。 count++; } else { printf("i am the parent process, my process id is %d/n",getpid()); printf("我是孩子他爹/n"); count++; } printf("统计结果是: %d/n",count); return 0; }
运行结果：
i am the child process, my process id is 5574 我是爹的儿子 统计结果是: 1 i am the parent process, my process id is 5573 我是孩子他爹 统计结果是: 1
在语句fpid=fork()之前，只有一个进程在执行这段代码，但在这条语句之后，就变成两个进程在执行了，这两个进程的几乎完全相同，将要执行的下一条语句都是if(fpid<0)
为什么两个进程的fpid不同呢，这与fork函数的特性有关。fork调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次，它可能有三种不同的返回值：
1）在父进程中，fork返回新创建子进程的进程ID；
2）在子进程中，fork返回0；
3）如果出现错误，fork返回一个负值；
在fork函数执行完毕后，如果创建新进程成功，则出现两个进程，一个是子进程，一个是父进程。在子进程中，fork函数返回0，在父进程中，fork返回新创建子进程的进程ID。我们可以通过fork返回的值来判断当前进程是子进程还是父进程。
引用一位网友的话来解释fpid的值为什么在父子进程中不同。“其实就相当于链表，进程形成了链表，父进程的fpid(p 意味point)指向子进程的进程id, 因为子进程没有子进程，所以其fpid为0.
fork出错可能有两种原因：
1）当前的进程数已经达到了系统规定的上限，这时errno的值被设置为EAGAIN。
2）系统内存不足，这时errno的值被设置为ENOMEM。
创建新进程成功后，系统中出现两个基本完全相同的进程，这两个进程执行没有固定的先后顺序，哪个进程先执行要看系统的进程调度策略。
每个进程都有一个独特（互不相同）的进程标识符（process ID），可以通过getpid（）函数获得，还有一个记录父进程pid的变量，可以通过getppid（）函数获得变量的值。
fork执行完毕后，出现两个进程
有人说两个进程的内容完全一样啊，怎么打印的结果不一样啊，那是因为判断条件的原因，上面列举的只是进程的代码和指令，还有变量啊。
执行完fork后，进程1的变量为count=0，fpid！=0（父进程）。进程2的变量为count=0，fpid=0（子进程），这两个进程的变量都是独立的，存在不同的地址中，不是共用的，这点要注意。可以说，我们就是通过fpid来识别和操作父子进程的。
还有人可能疑惑为什么不是从#include处开始复制代码的，这是因为fork是把进程当前的情况拷贝一份，执行fork时，进程已经执行完了int count=0;fork只拷贝下一个要执行的代码到新的进程。
struct tms 结构体
struct tms 结构体定义在 <sys/times.h> 头文件里，具体定义如下：
引用 /* Structure describing CPU time used by a process and its children. */ struct tms { clock_t tms_utime ; /* User CPU time. 用户程序 CPU 时间*/ clock_t tms_stime ; /* System CPU time. 系统调用所耗费的 CPU 时间 */ clock_t tms_cutime ; /* User CPU time of dead children. 已死掉子进程的 CPU 时间*/ clock_t tms_cstime ; /* System CPU time of dead children. 已死掉子进程所耗费的系统调用 CPU 时间*/ };
用户CPU时间和系统CPU时间之和为CPU时间，即命令占用CPU执行的时间总和。实际时间要大于CPU时间，因为Linux是多任务操作系统，往往在执行一条命令时，系统还要处理其他任务。另一个需要注意的问题是即使每次执行相同的命令，所花费的时间也不一定相同，因为其花费的时间与系统运行相关。
数据类型 clock_t
关于该数据类型的定义如下：
#ifndef _CLOCK_T_DEFINED typedef long clock_t; #define _CLOCK_T_DEFINED #endif
clock_t 是一个长整型数。
在 time.h 文件中，还定义了一个常量 CLOCKS_PER_SEC ，它用来表示一秒钟会有多少个时钟计时单元，其定义如下：
#define CLOCKS_PER_SEC ((clock_t)1000)
下文就模拟cpu操作，定义 H Z = 100 HZ=100HZ=100，内核的标准时间是jiffy,一个jiffy就是一个内部时钟周期,而内部时钟周期是由100HZ的频率所产生中的,也就是一个时钟滴答,间隔时间是10毫秒(ms).计算出来的时间也并非真实时间，而是时钟滴答次数，乘以10ms可以得到真正的时间。
代码实现
下面给出代码：
#include <stdio.h> #include <unistd.h> #include <time.h> #include <sys/times.h> #define HZ 100 void cpuio_bound(int last, int cpu_time, int io_time); int main(int argc, char * argv[]) { pid_t n_proc[10]; /*10个子进程 PID*/ int i; for(i=0;i<10;i++) { n_proc[i] = fork(); /*子进程*/ if(n_proc[i] == 0) { cpuio_bound(20,2*i,20-2*i); /*每个子进程都占用20s*/ return 0; /*执行完cpuio_bound 以后，结束该子进程*/ } /*fork 失败*/ else if(n_proc[i] < 0 ) { printf("Failed to fork child process %d!\n",i+1); return -1; } /*父进程继续fork*/ } /*打印所有子进程PID*/ for(i=0;i<10;i++) printf("Child PID: %d\n",n_proc[i]); /*等待所有子进程完成*/ wait(&i); /*Linux 0.11 上 gcc要求必须有一个参数, gcc3.4+则不需要*/ return 0; } /* * 此函数按照参数占用CPU和I/O时间 * last: 函数实际占用CPU和I/O的总时间，不含在就绪队列中的时间，>=0是必须的 * cpu_time: 一次连续占用CPU的时间，>=0是必须的 * io_time: 一次I/O消耗的时间，>=0是必须的 * 如果last > cpu_time + io_time，则往复多次占用CPU和I/O * 所有时间的单位为秒 */ void cpuio_bound(int last, int cpu_time, int io_time) { struct tms start_time, current_time; clock_t utime, stime; int sleep_time; while (last > 0) { /* CPU Burst */ times(&start_time); /* 其实只有t.tms_utime才是真正的CPU时间。但我们是在模拟一个 * 只在用户状态运行的CPU大户，就像“for(;;);”。所以把t.tms_stime * 加上很合理。*/ do { times(¤t_time); utime = current_time.tms_utime - start_time.tms_utime; stime = current_time.tms_stime - start_time.tms_stime; } while ( ( (utime + stime) / HZ ) < cpu_time ); last -= cpu_time; if (last <= 0 ) break; /* IO Burst */ /* 用sleep(1)模拟1秒钟的I/O操作 */ sleep_time=0; while (sleep_time < io_time) { sleep(1); sleep_time++; } last -= sleep_time; } }
答疑
❓ 为什么说它可以用来检验有关 log 文件的修改是否正确，同时还是数据统计工作的基础？
每个子进程都通过 cpuio_bound 函数实现了占用CPU和I/O时间的操作，并且可以精确的知道每个操作的时间。所以下面的 log 文件（日志文件）正确与否可以借此推算。
尽早打开log文件
操作系统启动后先要打开 /var/process.log，然后在每个进程发生状态切换的时候向 log 文件内写入一条记录，其过程和用户态的应用程序没什么两样。然而，因为内核状态的存在，使过程中的很多细节变得完全不一样。
为了能尽早开始记录，应当在内核启动时就打开 log 文件。内核的入口是 init/main.c 中的 main()，其中一段代码是：
//…… move_to_user_mode(); if (!fork()) { /* we count on this going ok */ init(); } //……
这段代码在进程 0 中运行，先切换到用户模式，然后全系统第一次调用 fork() 建立进程 1。进程 1 调用 init()。
在 init()中：
// …… //加载文件系统 setup((void *) &drive_info); // 打开/dev/tty0，建立文件描述符0和/dev/tty0的关联 (void) open("/dev/tty0",O_RDWR,0); // 让文件描述符1也和/dev/tty0关联 (void) dup(0); // 让文件描述符2也和/dev/tty0关联 (void) dup(0); // ……
这段代码建立了文件描述符 0、1 和 2，它们分别就是 stdin、stdout 和 stderr。这三者的值是系统标准（Windows 也是如此），不可改变。
可以把 log 文件的描述符关联到 3。文件系统初始化，描述符 0、1 和 2 关联之后，才能打开 log 文件，开始记录进程的运行轨迹。
为了能尽早访问 log 文件，我们要让上述工作在进程 0 中就完成。所以把这一段代码从 init() 移动到 main() 中，放在 move_to_user_mode() 之后（不能再靠前了），同时加上打开 log 文件的代码。
修改后的 main() 如下：
//…… move_to_user_mode(); /***************添加开始***************/ setup((void *) &drive_info); // 建立文件描述符0和/dev/tty0的关联 (void) open("/dev/tty0",O_RDWR,0); //文件描述符1也和/dev/tty0关联 (void) dup(0); // 文件描述符2也和/dev/tty0关联 (void) dup(0); (void) open("/var/process.log",O_CREAT|O_TRUNC|O_WRONLY,0666); /***************添加结束***************/ if (!fork()) { /* we count on this going ok */ init(); } //……
打开 log 文件的参数的含义是建立只写文件，如果文件已存在则清空已有内容。文件的权限是所有人可读可写。
这样，文件描述符 0、1、2 和 3 就在进程 0 中建立了。根据 fork() 的原理，进程 1 会继承这些文件描述符，所以 init() 中就不必再 open() 它们。此后所有新建的进程都是进程 1 的子孙，也会继承它们。但实际上，init() 的后续代码和 /bin/sh 都会重新初始化它们。所以只有进程 0 和进程 1 的文件描述符肯定关联着 log 文件，这一点在接下来的写 log 中很重要。
小结
其实就是为了尽早打开log日志文件开始记录，那必须满足在用户模式且可以进行文件读写，因此最前的位置只能在 move_to_user_mode() 之后（不能再靠前了），并且建立文件描述符 0、1 和 2，它们分别就是 stdin、stdout 和 stderr。
编写fprintk()函数
log 文件将被用来记录进程的状态转移轨迹。所有的状态转移都是在内核进行的。
在内核状态下，write() 功能失效，其原理等同于《系统调用》实验中不能在内核状态调用 printf()，只能调用 printk()。编写可在内核调用的 write() 的难度较大，所以这里直接给出源码。它主要参考了 printk() 和 sys_write() 而写成的：
#include "linux/sched.h" #include "sys/stat.h" static char logbuf[1024]; int fprintk(int fd, const char *fmt, ...) { va_list args; int count; struct file * file; struct m_inode * inode; va_start(args, fmt); count=vsprintf(logbuf, fmt, args); va_end(args); /* 如果输出到stdout或stderr，直接调用sys_write即可 */ if (fd < 3) { __asm__("push %%fs\n\t" "push %%ds\n\t" "pop %%fs\n\t" "pushl %0\n\t" /* 注意对于Windows环境来说，是_logbuf,下同 */ "pushl $logbuf\n\t" "pushl %1\n\t" /* 注意对于Windows环境来说，是_sys_write,下同 */ "call sys_write\n\t" "addl $8,%%esp\n\t" "popl %0\n\t" "pop %%fs" ::"r" (count),"r" (fd):"ax","cx","dx"); } else /* 假定>=3的描述符都与文件关联。事实上，还存在很多其它情况，这里并没有考虑。*/ { /* 从进程0的文件描述符表中得到文件句柄 */ if (!(file=task[0]->filp[fd])) return 0; inode=file->f_inode; __asm__("push %%fs\n\t" "push %%ds\n\t" "pop %%fs\n\t" "pushl %0\n\t" "pushl $logbuf\n\t" "pushl %1\n\t" "pushl %2\n\t" "call file_write\n\t" "addl $12,%%esp\n\t" "popl %0\n\t" "pop %%fs" ::"r" (count),"r" (file),"r" (inode):"ax","cx","dx"); } return count; }
因为和 printk 的功能近似，建议将此函数放入到 kernel/printk.c 中。fprintk() 的使用方式类同与 C 标准库函数 fprintf()，唯一的区别是第一个参数是文件描述符，而不是文件指针。
例如：
// 向stdout打印正在运行的进程的ID fprintk(1, "The ID of running process is %ld", current->pid); // 向log文件输出跟踪进程运行轨迹 fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'R', jiffies);
jiffies，滴答
jiffies 在 kernel/sched.c 文件中定义为一个全局变量：
long volatile jiffies=0;
它记录了从开机到当前时间的时钟中断发生次数。在 kernel/sched.c 文件中的 sched_init() 函数中，时钟中断处理函数被设置为：
set_intr_gate(0x20,&timer_interrupt);
而在 kernel/system_call.s 文件中将 timer_interrupt 定义为：
timer_interrupt: ! …… ! 增加jiffies计数值 incl jiffies ! ……
这说明 jiffies 表示从开机时到现在发生的时钟中断次数，这个数也被称为 “滴答数”。
另外，在 kernel/sched.c 中的 sched_init() 中有下面的代码：
// 设置8253模式 outb_p(0x36, 0x43); outb_p(LATCH&0xff, 0x40); outb_p(LATCH>>8, 0x40);
这三条语句用来设置每次时钟中断的间隔，即为 LATCH，而 LATCH 是定义在文件 kernel/sched.c 中的一个宏：
// 在 kernel/sched.c 中 #define LATCH (1193180/HZ) // 在 include/linux/sched.h 中 #define HZ 100
再加上 PC 机 8253 定时芯片的输入时钟频率为 1.193180MHz，即 1193180/每秒，LATCH=1193180/100，时钟每跳 11931.8 下产生一次时钟中断，即每 1/100 秒（10ms）产生一次时钟中断，所以 jiffies 实际上记录了从开机以来共经过了多少个 10ms。
注意这里是 H Z = 100 HZ=100HZ=100 的情况，前文也介绍过。所以时间其实就是近似等于中断次数乘以 1 / H Z 1/HZ1/HZ
寻找状态切换点
必须找到所有发生进程状态切换的代码点，并在这些点添加适当的代码，来输出进程状态变化的情况到 log 文件中。
此处要面对的情况比较复杂，需要对 kernel 下的 fork.c、sched.c 有通盘的了解，而 exit.c 也会涉及到。
例子 1：记录一个进程生命期的开始
第一个例子是看看如何记录一个进程生命期的开始，当然这个事件就是进程的创建函数 fork()，由《系统调用》实验可知，fork() 功能在内核中实现为 sys_fork()，该“函数”在文件 kernel/system_call.s 中实现为：
sys_fork: call find_empty_process ! …… ! 传递一些参数 push %gs pushl %esi pushl %edi pushl %ebp pushl %eax ! 调用 copy_process 实现进程创建 call copy_process addl $20,%esp
所以真正实现进程创建的函数是 copy_process()，它在 kernel/fork.c 中定义为：
int copy_process(int nr,……) { struct task_struct *p; // …… // 获得一个 task_struct 结构体空间 p = (struct task_struct *) get_free_page(); // …… p->pid = last_pid; // …… // 设置 start_time 为 jiffies p->start_time = jiffies; // …… /* 设置进程状态为就绪。所有就绪进程的状态都是 TASK_RUNNING(0），被全局变量 current 指向的 是正在运行的进程。*/ p->state = TASK_RUNNING; return last_pid; }
因此要完成进程运行轨迹的记录就要在 copy_process() 中添加输出语句。
这里要输出两种状态，分别是“N（新建）”和“J（就绪）”。
例子 2：记录进入睡眠态的时间
第二个例子是记录进入睡眠态的时间。sleep_on() 和 interruptible_sleep_on() 让当前进程进入睡眠状态，这两个函数在 kernel/sched.c 文件中定义如下：
void sleep_on(struct task_struct **p) { struct task_struct *tmp; // …… tmp = *p; // 仔细阅读，实际上是将 current 插入“等待队列”头部，tmp 是原来的头部 *p = current; // 切换到睡眠态 current->state = TASK_UNINTERRUPTIBLE; // 让出 CPU schedule(); // 唤醒队列中的上一个（tmp）睡眠进程。0 换作 TASK_RUNNING 更好 // 在记录进程被唤醒时一定要考虑到这种情况，实验者一定要注意!!! if (tmp) tmp->state=0; } /* TASK_UNINTERRUPTIBLE和TASK_INTERRUPTIBLE的区别在于不可中断的睡眠 * 只能由wake_up()显式唤醒，再由上面的 schedule()语句后的 * * if (tmp) tmp->state=0; * * 依次唤醒，所以不可中断的睡眠进程一定是按严格从“队列”（一个依靠 * 放在进程内核栈中的指针变量tmp维护的队列）的首部进行唤醒。而对于可 * 中断的进程，除了用wake_up唤醒以外，也可以用信号（给进程发送一个信 * 号，实际上就是将进程PCB中维护的一个向量的某一位置位，进程需要在合 * 适的时候处理这一位。感兴趣的实验者可以阅读有关代码）来唤醒，如在 * schedule()中： * * for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) * if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) && * (*p)->state==TASK_INTERRUPTIBLE) * (*p)->state=TASK_RUNNING;//唤醒 * * 就是当进程是可中断睡眠时，如果遇到一些信号就将其唤醒。这样的唤醒会 * 出现一个问题，那就是可能会唤醒等待队列中间的某个进程，此时这个链就 * 需要进行适当调整。interruptible_sleep_on和sleep_on函数的主要区别就 * 在这里。 */ void interruptible_sleep_on(struct task_struct **p) { struct task_struct *tmp; … tmp=*p; *p=current; repeat: current->state = TASK_INTERRUPTIBLE; schedule(); // 如果队列头进程和刚唤醒的进程 current 不是一个， // 说明从队列中间唤醒了一个进程，需要处理 if (*p && *p != current) { // 将队列头唤醒，并通过 goto repeat 让自己再去睡眠 (**p).state=0; goto repeat; } *p=NULL; //作用和 sleep_on 函数中的一样 if (tmp) tmp->state=0; }
总的来说，Linux 0.11 支持四种进程状态的转移：就绪到运行、运行到就绪、运行到睡眠和睡眠到就绪，此外还有新建和退出两种情况。其中就绪与运行间的状态转移是通过 schedule()（它亦是调度算法所在）完成的；运行到睡眠依靠的是 sleep_on() 和 interruptible_sleep_on()，还有进程主动睡觉的系统调用 sys_pause() 和 sys_waitpid()；睡眠到就绪的转移依靠的是 wake_up()。所以只要在这些函数的适当位置插入适当的处理语句就能完成进程运行轨迹的全面跟踪了。
修改fork.c文件
fork.c文件在kernel目录下，这里要输出两种状态，分别是“N（新建）”和“J（就绪）”，下面做出两处修改：
int copy_process(int nr,……) { struct task_struct *p; // …… // 获得一个 task_struct 结构体空间 p = (struct task_struct *) get_free_page(); // …… p->pid = last_pid; // …… // 设置 start_time 为 jiffies p->start_time = jiffies; //新增修改,新建进程 fprintk(3,"%d\tN\t%d\n",p->pid,jiffies); // …… /* 设置进程状态为就绪。所有就绪进程的状态都是 TASK_RUNNING(0），被全局变量 current 指向的 是正在运行的进程。*/ p->state = TASK_RUNNING; //新增修改，进程就绪 fprintk(3,"%d\tJ\t%d\n",p->pid,jiffies); return last_pid; }
修改sched.c文件
文件位置：kernel/sched.c
修改schedule函数
//这里仅仅说一下改动了什么 /* check alarm, wake up any interruptible tasks that have got a signal */ for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) if (*p) { if ((*p)->alarm && (*p)->alarm < jiffies) { (*p)->signal |= (1<<(SIGALRM-1)); (*p)->alarm = 0; } if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) && (*p)->state==TASK_INTERRUPTIBLE){ (*p)->state=TASK_RUNNING; fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies); } } while (1) { c = -1; next = 0; i = NR_TASKS; p = &task[NR_TASKS]; // 找到 counter 值最大的就绪态进程 while (--i) { if (!*--p) continue; if ((*p)->state == TASK_RUNNING && (*p)->counter > c) c = (*p)->counter, next = i; } // 如果有 counter 值大于 0 的就绪态进程，则退出 if (c) break; // 如果没有： // 所有进程的 counter 值除以 2 衰减后再和 priority 值相加， // 产生新的时间片 for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) if (*p) (*p)->counter = ((*p)->counter >> 1) + (*p)->priority; } //切换到相同的进程不输出 if(current->pid != task[next] ->pid) { /*新建修改--时间片到时程序 => 就绪*/ if(current->state == TASK_RUNNING) fprintk(3,"%d\tJ\t%d\n",current->pid,jiffies); fprintk(3,"%d\tR\t%d\n",task[next]->pid,jiffies); } // 切换到 next 进程 switch_to(next);
修改sys_pause函数
int sys_pause(void) { current->state = TASK_INTERRUPTIBLE; /* *修改--当前进程 运行 => 可中断睡眠 */ if(current->pid != 0) fprintk(3,"%d\tW\t%d\n",current->pid,jiffies); schedule(); return 0; }
修改sleep_on函数
void sleep_on(struct task_struct **p) { struct task_struct *tmp; if (!p) return; if (current == &(init_task.task)) panic("task[0] trying to sleep"); tmp = *p; *p = current; current->state = TASK_UNINTERRUPTIBLE; /* *修改--当前进程进程 => 不可中断睡眠 */ fprintk(3,"%d\tW\t%d\n",current->pid,jiffies); schedule(); if (tmp) { tmp->state=0; /* *修改--原等待队列 第一个进程 => 唤醒（就绪） */ fprintk(3,"%d\tJ\t%d\n",tmp->pid,jiffies); } }
修改interruptible_sleep_on函数
void interruptible_sleep_on(struct task_struct **p) { struct task_struct *tmp; if (!p) return; if (current == &(init_task.task)) panic("task[0] trying to sleep"); tmp=*p; *p=current; repeat: current->state = TASK_INTERRUPTIBLE; /* *修改--唤醒队列中间进程，过程中使用Wait */ fprintk(3,"%d\tW\t%d\n",current->pid,jiffies); schedule(); if (*p && *p != current) { (**p).state=0; /* *修改--当前进程 => 可中断睡眠 */ fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies); goto repeat; } *p=NULL; if (tmp) { tmp->state=0; /* *修改--原等待队列 第一个进程 => 唤醒（就绪） */ fprintk(3,"%d\tJ\t%d\n",tmp->pid,jiffies); } }
修改wake_up函数
void wake_up(struct task_struct **p) { if (p && *p) { (**p).state=0; /* *修改--唤醒 最后进入等待序列的 进程 */ fprintk(3,"%d\tJ\t%d\n",(*p)->pid,jiffies); *p=NULL; } }
修改exit.c文件
当一个进程结束了运行或在半途中终止了运行，那么内核就需要释放该进程所占用的系统资源。这包括进程运行时打开的文件、申请的内存等。
当一个用户程序调用exit()系统调用时，就会执行内核函数do_exit()。该函数会首先释放进程代码段和数据段占用的内存页面，关闭进程打开着的所有文件，对进程使用的当前工作目录、根目录和运行程序的i节点进行同步操作。如果进程有子进程，则让init进程作为其所有子进程的父进程。如果进程是一个会话头进程并且有控制终端，则释放控制终端(如果按照实验的数据，此时就应该打印了)，并向属于该会话的所有进程发送挂断信号 SIGHUP，这通常会终止该会话中的所有进程。然后把进程状态置为僵死状态 TASK_ZOMBIE。并向其原父进程发送 SIGCHLD 信号，通知其某个子进程已经终止。最后 do_exit()调用调度函数去执行其他进程。由此可见在进程被终止时，它的任务数据结构仍然保留着。因为其父进程还需要使用其中的信息。
在子进程在执行期间，父进程通常使用wait()或 waitpid()函数等待其某个子进程终止。当等待的子进程被终止并处于僵死状态时，父进程就会把子进程运行所使用的时间累加到自己进程中。最终释放已终止子进程任务数据结构所占用的内存页面，并置空子进程在任务数组中占用的指针项。
int do_exit(long code) { int i; free_page_tables(get_base(current->ldt[1]),get_limit(0x0f)); free_page_tables(get_base(current->ldt[2]),get_limit(0x17)); // …… current->state = TASK_ZOMBIE; /* *修改--退出一个进程 */ fprintk(3,"%d\tE\t%d\n",current->pid,jiffies); current->exit_code = code; tell_father(current->father); schedule(); return (-1); /* just to suppress warnings */ } // …… int sys_waitpid(pid_t pid,unsigned long * stat_addr, int options) { int flag, code; struct task_struct ** p; // …… // …… if (flag) { if (options & WNOHANG) return 0; current->state=TASK_INTERRUPTIBLE; /* *修改--当前进程 => 等待 */ fprintk(3,"%d\tW\t%d\n",current->pid,jiffies); schedule(); if (!(current->signal &= ~(1<<(SIGCHLD-1)))) goto repeat; else return -EINTR; } return -ECHILD; }
小结
总的来说，Linux 0.11 支持四种进程状态的转移：就绪到运行、运行到就绪、运行到睡眠和睡眠到就绪，此外还有新建和退出两种情况。其中就绪与运行间的状态转移是通过 schedule()（它亦是调度算法所在）完成的；运行到睡眠依靠的是 sleep_on() 和 interruptible_sleep_on()，还有进程主动睡觉的系统调用 sys_pause() 和 sys_waitpid()；睡眠到就绪的转移依靠的是 wake_up()。所以只要在这些函数的适当位置插入适当的处理语句就能完成进程运行轨迹的全面跟踪了。
为了让生成的 log 文件更精准，以下几点请注意：
进程退出的最后一步是通知父进程自己的退出，目的是唤醒正在等待此事件的父进程。从时序上来说，应该是子进程先退出，父进程才醒来。
系统无事可做的时候，进程 0 会不停地调用 sys_pause()，以激活调度算法。此时它的状态可以是等待态，等待有其它可运行的进程；也可以叫运行态，因为它是唯一一个在 CPU 上运行的进程，只不过运行的效果是等待。
编译
重新编译
make all
编译运行process.c
将process.c拷贝到linux0.11系统中，这个过程需要挂载一下系统硬盘，挂载拷贝成功之后再卸载硬盘，然后启动模拟器进入系统内编译一下process.c文件，过程命令及截图如下：
// oslab目录下运行 sudo ./mount-hdc cp ./test3/process.c ./hdc/usr/root/ sudo umonut hdc
进入linux-0.11
gcc -o process process.c ./process sync
使用./process即可运行目标文件，运行后会生成log文件，生成log文件后一定要记得刷新，然后将其拷贝到oslab/test3目录，命令如下：
sudo ./mount-hdc cp ./hdc/var/process.log ./test3/ sudo umonut hdc
process.log自动化分析
只要给 stat_log.py 加上执行权限（使用的命令为 chmod +x stat_log.py）就可以直接运行它。
在结果中我们可以看到各个进程的周转时间（Turnaround，指作业从提交到完成所用的总时间）、等待时间等，以及平均周转时间和等待时间。
修改时间片
MOOC哈工大操作系统实验3：进程运行轨迹的跟踪与统计_ZhaoTianhao的博客-CSDN博客
这段没有耐心实现了，摘录了一位博主的解释
linux0.11采用的调度算法是一种综合考虑进程优先级并能动态反馈调整时间片的轮转调度算法。 那么什么是轮转调度算法呢？它为每个进程分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程；如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。那什么是综合考虑进程优先级呢？就是说一个进程在阻塞队列中停留的时间越长，它的优先级就越大，下次就会被分配更大的时间片。
进程之间的切换是需要时间的，如果时间片设定得太小的话，就会发生频繁的进程切换，因此会浪费大量时间在进程切换上，影响效率；如果时间片设定得足够大的话，就不会浪费时间在进程切换上，利用率会更高，但是用户交互性会受到影响，举一个很直观的例子：我在银行排队办业务，假设我要办的业务很简单只需要占用1分钟，如果每个人的时间片是30分钟，而我前面的每个人都要用满这30分钟，那我就要等上好几个小时！如果每个人的时间片是2分钟的话，我只需要等十几分钟就可以办理我的业务了，前面没办完的会在我之后轮流地继续去办。所以时间片不能过大或过小，要兼顾CPU利用率和用户交互性。
时间片的初始值是进程0的priority，是在linux-0.11/include/linux/sched.h的宏 INIT_TASK 中定义的，如下：我们只需要修改宏中的第三个值即可，该值即时间片的初始值。
#define INIT_TASK \ { 0,15,15, // 上述三个值分别对应 state、counter 和 priority;
修改完后再次编译make all，进入模拟器后编译运行测试文件process.c，然后运行统计脚本stat_log.py查看结果，与之前的结果进行对比。
问题回答
问题1：单进程编程和多进程编程的区别？
1.执行方式：单进程编程是一个进程从上到下顺序进行；多进程编程可以通过并发执行，即多个进程之间交替执行，如某一个进程正在I/O输入输出而不占用CPU时，可以让CPU去执行另外一个进程，这需要采取某种调度算法。
2.数据是否同步：单进程的数据是同步的，因为单进程只有一个进程，在进程中改变数据的话，是会影响这个进程的；多进程的数据是异步的，因为子进程数据是父进程数据在内存另一个位置的拷贝，因此改变其中一个进程的数据，是不会影响到另一个进程的。
3.CPU利用率：单进程编程的CPU利用率低，因为单进程在等待I/O时，CPU是空闲的；多进程编程的CPU利用率高，因为当某一进程等待I/O时，CPU会去执行另一个进程，因此CPU的利用率高。
4.多进程用途更广泛。
问题2：仅针对样本程序建立的进程，在修改时间片前后，log 文件的统计结果都是什么样？结合你的修改分析一下为什么会这样变化，或者为什么没变化？
依次将时间偏设为1，5，10，15，20，25，50，100，150后，经统计分析log文件可以发现：
1）在一定的范围内，平均等待时间，平均完成时间的变化随着时间片的增大而减小。这是因为在时间片小的情况下，cpu将时间耗费在调度切换上，所以平均等待时间增加。
2）超过一定的范围之后，这些参数将不再有明显的变化，这是因为在这种情况下，RR轮转调度就变成了FCFS先来先服务了。随着时间片的修改，吞吐量始终没有明显的变化，这是因为在单位时间内，系统所能完成的进程数量是不会变的。
警示
编译好后进入linux-0.11
直接报了内核错误，这肯定是之前的代码打错了。那么多代码，我怎么知道错误在哪。但是注意以前正常情况下会打印剩余空间。
而先前改代码的时候发现这段打印的代码就在进程1 init() 函数内，所以推断是修改进程0时出现了错误
好家伙，顺序反了。之前说了，文件系统初始化，描述符 0、1 和 2 关联之后，才能打开 log 文件。这里却直接先打开 log 文件了。😢
天道酬勤
粗略的了解了进程运行的方式，多进程的好处显而易见，大大节省了效率，但其调度算法如何实现可以尽可能缩短浪费的时间还是需要好好思考的。
实验五 基于内核栈切换的进程切换
实验目的
深入理解进程和进程切换的概念；
综合应用进程、CPU 管理、PCB、LDT、内核栈、内核态等知识解决实际问题；
开始建立系统认识。
实验内容
现在的 Linux 0.11 采用 TSS 和一条指令就能完成任务切换，虽然简单，但这指令的执行时间却很长，在实现任务切换时大概需要 200 多个时钟周期。
而通过堆栈实现任务切换可能要更快，而且采用堆栈的切换还可以使用指令流水的并行优化技术，同时又使得 CPU 的设计变得简单。所以无论是 Linux 还是 Windows，进程/线程的切换都没有使用 Intel 提供的这种 TSS 切换手段，而都是通过堆栈实现的。
本次实践项目就是将 Linux 0.11 中采用的 TSS 切换部分去掉，取而代之的是基于堆栈的切换程序。具体的说，就是将 Linux 0.11 中的 switch_to 实现去掉，写成一段基于堆栈切换的代码。
本次实验包括如下内容：
编写汇编程序 switch_to：
完成主体框架；
在主体框架下依次完成 PCB 切换、内核栈切换、LDT 切换等；
修改 fork()，由于是基于内核栈的切换，所以进程需要创建出能完成内核栈切换的样子。
修改 PCB，即 task_struct 结构，增加相应的内容域，同时处理由于修改了 task_struct 所造成的影响。
用修改后的 Linux 0.11 仍然可以启动、可以正常使用。
TSS 切换
在现在的 Linux 0.11 中，真正完成进程切换是依靠任务状态段（Task State Segment，简称 TSS）的切换来完成的。
具体的说，在设计“Intel 架构”（即 x86 系统结构）时，每个任务（进程或线程）都对应一个独立的 TSS，TSS 就是内存中的一个结构体，里面包含了几乎所有的 CPU 寄存器的映像。有一个任务寄存器（Task Register，简称 TR）指向当前进程对应的 TSS 结构体，所谓的 TSS 切换就将 CPU 中几乎所有的寄存器都复制到 TR 指向的那个 TSS 结构体中保存起来，同时找到一个目标 TSS，即要切换到的下一个进程对应的 TSS，将其中存放的寄存器映像“扣在” CPU 上，就完成了执行现场的切换，如下图所示。
Intel 架构不仅提供了 TSS 来实现任务切换，而且只要一条指令就能完成这样的切换，即图中的 ljmp 指令。
具体的工作过程是：
（1）首先用 TR 中存取的段选择符在 GDT 表中找到当前 TSS 的内存位置，由于 TSS 是一个段，所以需要用段表中的一个描述符来表示这个段，和在系统启动时论述的内核代码段是一样的，那个段用 GDT 中的某个表项来描述，还记得是哪项吗？是 8 对应的第 1 项。此处的 TSS 也是用 GDT 中的某个表项描述，而 TR 寄存器是用来表示这个段用 GDT 表中的哪一项来描述，所以 TR 和 CS、DS 等寄存器的功能是完全类似的。
（2）找到了当前的 TSS 段（就是一段内存区域）以后，将 CPU 中的寄存器映像存放到这段内存区域中，即拍了一个快照。
（3）存放了当前进程的执行现场以后，接下来要找到目标进程的现场，并将其扣在 CPU 上，找目标 TSS 段的方法也是一样的，因为找段都要从一个描述符表中找，描述 TSS 的描述符放在 GDT 表中，所以找目标 TSS 段也要靠 GDT 表，当然只要给出目标 TSS 段对应的描述符在 GDT 表中存放的位置——段选择子就可以了，仔细想想系统启动时那条著名的 jmpi 0, 8 指令，这个段选择子就放在 ljmp 的参数中，实际上就 jmpi 0, 8 中的 8。
（4）一旦将目标 TSS 中的全部寄存器映像扣在 CPU 上，就相当于切换到了目标进程的执行现场了，因为那里有目标进程停下时的 CS:EIP，所以此时就开始从目标进程停下时的那个 CS:EIP 处开始执行，现在目标进程就变成了当前进程，所以 TR 需要修改为目标 TSS 段在 GDT 表中的段描述符所在的位置，因为 TR 总是指向当前 TSS 段的段描述符所在的位置。
上面给出的这些工作都是一句长跳转指令 ljmp 段选择子:段内偏移，在段选择子指向的段描述符是 TSS 段时 CPU 解释执行的结果，所以基于 TSS 进行进程/线程切换的 switch_to 实际上就是一句 ljmp 指令：
#define switch_to(n) { struct{long a,b;} tmp; __asm__( "movw %%dx,%1" "ljmp %0" ::"m"(*&tmp.a), "m"(*&tmp.b), "d"(TSS(n) ) } #define FIRST_TSS_ENTRY 4 #define TSS(n) (((unsigned long) n) << 4) + (FIRST_TSS_ENTRY << 3))
GDT 表的结构如下图所示，所以第一个 TSS 表项，即 0 号进程的 TSS 表项在第 4 个位置上，4<<3，即 4 * 8，相当于 TSS 在 GDT 表中开始的位置，TSS（n）找到的是进程 n 的 TSS 位置，所以还要再加上 n<<4，即 n * 16，因为每个进程对应有 1 个 TSS 和 1 个 LDT，每个描述符的长度都是 8 个字节，所以是乘以 16，其中 LDT 的作用就是上面论述的那个映射表，关于这个表的详细论述要等到内存管理一章。TSS(n) = n * 16 + 4 * 8，得到就是进程 n（切换到的目标进程）的 TSS 选择子，将这个值放到 dx 寄存器中，并且又放置到结构体 tmp 中 32 位长整数 b 的前 16 位，现在 64 位 tmp 中的内容是前 32 位为空，这个 32 位数字是段内偏移，就是 jmpi 0, 8 中的 0；接下来的 16 位是 n * 16 + 4 * 8，这个数字是段选择子，就是 jmpi 0, 8 中的 8，再接下来的 16 位也为空。所以 swith_to 的核心实际上就是 ljmp 空, n*16+4*8，现在和前面给出的基于 TSS 的进程切换联系在一起了。
本次实验的内容
虽然用一条指令就能完成任务切换，但这指令的执行时间却很长，这条 ljmp 指令在实现任务切换时大概需要 200 多个时钟周期。而通过堆栈实现任务切换可能要更快，而且采用堆栈的切换还可以使用指令流水的并行优化技术，同时又使得 CPU 的设计变得简单。所以无论是 Linux 还是 Windows，进程/线程的切换都没有使用 Intel 提供的这种 TSS 切换手段，而都是通过堆栈实现的。
本次实践项目就是将 Linux 0.11 中采用的 TSS 切换部分去掉，取而代之的是基于堆栈的切换程序。具体的说，就是将 Linux 0.11 中的 switch_to 实现去掉，写成一段基于堆栈切换的代码。
在现在的 Linux 0.11 中，真正完成进程切换是依靠任务状态段（Task State Segment，简称 TSS）的切换来完成的。具体的说，在设计“Intel 架构”（即 x86 系统结构）时，每个任务（进程或线程）都对应一个独立的 TSS，TSS 就是内存中的一个结构体，里面包含了几乎所有的 CPU 寄存器的映像。有一个任务寄存器（Task Register，简称 TR）指向当前进程对应的 TSS 结构体，所谓的 TSS 切换就将 CPU 中几乎所有的寄存器都复制到 TR 指向的那个 TSS 结构体中保存起来，同时找到一个目标 TSS，即要切换到的下一个进程对应的 TSS，将其中存放的寄存器映像“扣在”CPU 上，就完成了执行现场的切换。
要实现基于内核栈的任务切换，主要完成如下三件工作：
（1）重写 switch_to；
（2）将重写的 switch_to 和 schedule() 函数接在一起；
（3）修改现在的 fork()。
正式修改代码前小结
下面开始正式修改代码。其实主要就修改3个文件，但我不会按照每个文件一次性修改的顺序，而是按照实验逻辑，跳转修改，请保持清晰的逻辑。在截图的右下角有当前位置所在行数，注意观察不要修改错位置。
schedule 与 switch_to
目前 Linux 0.11 中工作的 schedule() 函数是首先找到下一个进程的数组位置 next，而这个 next 就是 GDT 中的 n，所以这个 next 是用来找到切换后目标 TSS 段的段描述符的，一旦获得了这个 next 值，直接调用上面剖析的那个宏展开 switch_to(next);就能完成如图 TSS 切换所示的切换了。
现在，我们不用 TSS 进行切换，而是采用切换内核栈的方式来完成进程切换，所以在新的 switch_to 中将用到当前进程的 PCB、目标进程的 PCB、当前进程的内核栈、目标进程的内核栈等信息。由于 Linux 0.11 进程的内核栈和该进程的 PCB 在同一页内存上（一块 4KB 大小的内存），其中 PCB 位于这页内存的低地址，栈位于这页内存的高地址；另外，由于当前进程的 PCB 是用一个全局变量 current 指向的，所以只要告诉新 switch_to()函数一个指向目标进程 PCB 的指针就可以了。同时还要将 next 也传递进去，虽然 TSS(next)不再需要了，但是 LDT(next)仍然是需要的，也就是说，现在每个进程不用有自己的 TSS 了，因为已经不采用 TSS 进程切换了，但是每个进程需要有自己的 LDT，地址分离地址还是必须要有的，而进程切换必然要涉及到 LDT 的切换。
综上所述，需要将目前的 schedule() 函数（在 kernel/sched.c 中）做稍许修改，即将下面的代码：
if ((*p)->state == TASK_RUNNING && (*p)->counter > c) c = (*p)->counter, next = i; //...... switch_to(next);
修改为：
if ((*p)->state == TASK_RUNNING && (*p)->counter > c) c = (*p)->counter, next = i, pnext = *p; //....... switch_to(pnext,_LDT(next));
注意 pnext 是指向 pcb 的指针
struct tast_struct *pnext = &(init_task.task);
使用 switch_to 需要添加函数声明
extern long switch_to(struct task_struct *p, unsigned long address);
实现 switch_to
实现 switch_to 是本次实践项目中最重要的一部分。
由于要对内核栈进行精细的操作，所以需要用汇编代码来完成函数 switch_to 的编写。
这个函数依次主要完成如下功能：由于是 C 语言调用汇编，所以需要首先在汇编中处理栈帧，即处理 ebp 寄存器；接下来要取出表示下一个进程 PCB 的参数，并和 current 做一个比较，如果等于 current，则什么也不用做；如果不等于 current，就开始进程切换，依次完成 PCB 的切换、TSS 中的内核栈指针的重写、内核栈的切换、LDT 的切换以及 PC 指针（即 CS:EIP）的切换。
可以很明显的看出，该函数是基于TSS进行进程切换的(ljmp指令)，
现在要改写成基于堆栈(内核栈)切换的函数，就需要删除掉该语句，在include/linux/sched.h 文件，我们将它注释掉。
然后新的switch_to()函数将它作为一个系统调用函数，所以要将函数重写在汇编文件kernel/system_call.s:
.align 2 switch_to: //因为该汇编函数要在c语言中调用，所以要先在汇编中处理栈帧 pushl %ebp movl %esp,%ebp pushl %ecx pushl %ebx pushl %eax //先得到目标进程的pcb，然后进行判断 //如果目标进程的pcb(存放在ebp寄存器中) 等于 当前进程的pcb => 不需要进行切换，直接退出函数调用 //如果目标进程的pcb(存放在ebp寄存器中) 不等于 当前进程的pcb => 需要进行切换，直接跳到下面去执行 movl 8(%ebp),%ebx cmpl %ebx,current je 1f /** 执行到此处，就要进行真正的基于堆栈的进程切换了 */ // PCB的切换 movl %ebx,%eax xchgl %eax,current // TSS中内核栈指针的重写 movl tss,%ecx addl $4096,%ebx movl %ebx,ESP0(%ecx) //切换内核栈 movl %esp,KERNEL_STACK(%eax) movl 8(%ebp),%ebx movl KERNEL_STACK(%ebx),%esp //LDT的切换 movl 12(%ebp),%ecx lldt %cx movl $0x17,%ecx mov %cx,%fs cmpl %eax,last_task_used_math jne 1f clts //在到子进程的内核栈开始工作了，接下来做的四次弹栈以及ret处理使用的都是子进程内核栈中的东西 1: popl %eax popl %ebx popl %ecx popl %ebp ret
逐条解释基于堆栈切换的switch_to()函数四段核心代码:
// PCB的切换 movl %ebx,%eax xchgl %eax,current 起始时eax寄存器保存了指向目标进程的指针，current指向了当前进程， 第一条指令执行完毕，使得ebx也指向了目标进程， 然后第二条指令开始执行，也就是将eax的值和current的值进行了交换，最终使得eax指向了当前进程，current就指向了目标进程(当前状态就发生了转移)
// TSS中内核栈指针的重写 movl tss,%ecx addl $4096,%ebx movl %ebx,ESP0(%ecx) 中断处理时需要寻找当前进程的内核栈，否则就不能从用户栈切到内核栈(中断处理没法完成)， 内核栈的寻找是借助当前进程TSS中存放的信息来完成的，(当然，当前进程的TSS还是通过TR寄存器在GDT全局描述符表中找到的)。 虽然此时不使用TSS进行进程切换了，但是Intel的中断处理机制还是要保持。 所以每个进程仍然需要一个TSS，操作系统需要有一个当前TSS。 这里采用的方案是让所有进程共用一个TSS(这里使用0号进程的TSS)， 因此需要定义一个全局指针变量tss(放在system_call.s中)来执行0号进程的TSS: struct tss_struct * tss = &(init_task.task.tss); 此时唯一的tss的目的就是:在中断处理时，能够找到当前进程的内核栈的位置。 在内核栈指针重写指令中有宏定义ESP0，所以在上面需要提前定义好 ESP0 = 4， (定义为4是因为TSS中内核栈指针ESP0就放在偏移为4的地方) 并且需要将: blocked=(33*16) => blocked=(33*16+4)
kernel/system_call.s 文件
重写TSS中的内核栈指针
ESP0 = 4 KERNEL_STACK = 12 state = 0 # these are offsets into the task-struct. counter = 4 priority = 8 kernelstack = 12 signal = 16 sigaction = 20 # MUST be 16 (=len of sigaction) blocked = (37*16)
kernel/sched.c 文件
struct tss_struct * tss = &(init_task.task.tss);
//切换内核栈 movl %esp,KERNEL_STACK(%eax) movl 8(%ebp),%ebx movl KERNEL_STACK(%ebx),%esp 第一行:将cpu寄存器esp的值，保存到当前进程pcb的eax寄存器中(保存当前进程执行信息) 第二行:获取目标进程的pcb放入ebx寄存器中 第三行:将ebx寄存器中的信息，也就是目标进程的信息，放入cpu寄存器esp中 但是之前的进程控制块(pcb)中是没有保存内核栈信息的寄存器的，所以需要在sched.h中的task_struct(也就是pcb)中添加kernelstack， 但是添加的位置就有讲究了，因为在某些汇编文件(主要是systen_call.s中)，有操作这个结构的硬编码， 一旦结构体信息改变，那这些硬编码也要跟着改变， 比如添加kernelstack在第一行，就需要改很多信息了， 但是添加到第四行就不需要改很多信息，所以这里将kernelstack放到第四行的位置： struct task_struct { /* these are hardcoded - don't touch */ long state; /* -1 unrunnable, 0 runnable, >0 stopped */ long counter; long priority; /** add kernelstack */ long kernelstack; ... } 改动位置及信息: 将 #define INIT_TASK \ /* state etc */ { 0,15,15,\ /* signals */ 0,{{},},0, \ ... 改为: #define INIT_TASK \ /* state etc */ { 0,15,15, PAGE_SIZE+(long)&init_task,\ /* signals */ 0,{{},},0, \ ... 在执行上述切换内核栈的代码之前(也就是switch_to()函数前)，要设置栈的大小:KERNEL_STACK = 12 然后就执行上面的三行代码，就可以完成对内核栈的切换了。
include/linux/sched.h 文件
long kernelstack;
由于这里将 PCB 结构体的定义改变了，所以在产生 0 号进程的 PCB 初始化时也要跟着一起变化， 需要修改 #define INIT_TASK，即在 PCB 的第四项中增加关于内核栈栈指针的初始化。代码如下：
将 #define INIT_TASK \ /* state etc */ { 0,15,15,\ /* signals */ 0,{{},},0, \ ... 改为: #define INIT_TASK \ /* state etc */ { 0,15,15, PAGE_SIZE+(long)&init_task,\ /* signals */ 0,{{},},0, \ ...
kernel/system_call.s
KERNEL_STACK = 12
//LDT的切换 movl 12(%ebp),%ecx lldt %cx movl $0x17,%ecx mov %cx,%fs 前两条语句的作用(切换LDT): 第一条:取出参数LDT(next) 第二条:完成对LDTR寄存器的修改 然后就是对PC指针(即CS:EIP)的切换: 后两条语句的含有就是重写设置段寄存器FS的值为0x17 补:FS的作用:通过FS操作系统才能访问进程的用户态内存。 这里LDT切换完成意味着切换到了新的用户态地址空间，所以需要重置FS。
修改fork()系统调用
现在需要将新建进程的用户栈、用户程序地址和其内核栈关联在一起，因为TSS没有做这样的关联fork()要求让父子进程共享用户代码、用户数据和用户堆栈虽然现在是使用内核栈完成任务的切换(基于堆栈的进程切换)，但是fork()的基本含义不应该发生变化。
综合分析:
修改以后的fork()要使得父子进程共享同一块内存空间、堆栈和数据代码块。
fork() 系统调用的代码放在 system_call.s 汇编文件中，先来看看已经写好的代码:
.align 2 sys_fork: call find_empty_process testl %eax,%eax js 1f push %gs pushl %esi pushl %edi pushl %ebp pushl %eax call copy_process//跳转到copy_process()函数 addl $20,%esp 1: ret
可以看到fork()函数的核心就是调用了 copy_process()，接下来去看copy_process()
copy_process()函数定义在kernel/fork.c中，代码和分析见注释:
int copy_process(int nr,long ebp,long edi,long esi,long gs,long none, long ebx,long ecx,long edx, long fs,long es,long ds, long eip,long cs,long eflags,long esp,long ss) { struct task_struct *p; int i; struct file *f; p = (struct task_struct *) get_free_page();//用来完成申请一页内存空间作为子进程的PCB ... /** 很容易看出来下面的部分就是基于tss进程切换机制时的代码，所以将此片段要注释掉 p->tss.back_link = 0; p->tss.esp0 = PAGE_SIZE + (long) p; p->tss.ss0 = 0x10; ... */ /** 然后这里要加上基于堆栈切换的代码(对frok的修改其实就是对子进程内核栈的初始化 */ long *krnstack; krnstack = (long)(PAGE_SIZE +(long)p);//p指针加上页面大小就是子进程的内核栈位置，所以这句话就是krnstack指针指向子进程的内核栈 //初始化内核栈(krnstack)中的内容: //下面的五句话可以完成对书上那个图(4.22)所示的关联效果(父子进程共有同一内存、堆栈和数据代码块) /* 而且很容易可以看到，ss,esp,elags,cs,eip这些参数来自调用该函数的进程的内核栈中， 也就是父进程的内核栈，所以下面的指令就是将父进程内核栈的前五个内容拷贝到了子进程的内核栈中 */ *(--krnstack) = ss & 0xffff; *(--krnstack) = esp; *(--krnstack) = eflags; *(--krnstack) = cs & 0xffff; *(--krnstack) = eip; *(--krnstack) = ds & 0xffff; *(--krnstack) = es & 0xffff; *(--krnstack) = fs & 0xffff; *(--krnstack) = gs & 0xffff; *(--krnstack) = esi; *(--krnstack) = edi; *(--krnstack) = edx; *(--krnstack) = (long) first_return_kernel;//处理switch_to返回的位置 *(--krnstack) = ebp; *(--krnstack) = ecx; *(--krnstack) = ebx; *(--krnstack) = 0; //把switch_to中要的东西存进去 p->kernelstack = krnstack; ...
kernel/fork.c 文件
注释tss进程切换片段
添加代码
long *krnstack; krnstack = (long)(PAGE_SIZE +(long)p); *(--krnstack) = ss & 0xffff; *(--krnstack) = esp; *(--krnstack) = eflags; *(--krnstack) = cs & 0xffff; *(--krnstack) = eip; *(--krnstack) = ds & 0xffff; *(--krnstack) = es & 0xffff; *(--krnstack) = fs & 0xffff; *(--krnstack) = gs & 0xffff; *(--krnstack) = esi; *(--krnstack) = edi; *(--krnstack) = edx; *(--krnstack) = (long) first_return_kernel; *(--krnstack) = ebp; *(--krnstack) = ecx; *(--krnstack) = ebx; *(--krnstack) = 0; p->kernelstack = krnstack;
上面的first_return_kernel(系统调用)的工作:
"内核级线程切换五段论"中的最后一段切换，即完成用户栈和用户代码的切换，依靠的核心指令就是iret，当然在切换之前应该恢复一下执行现场，主要就是eax,ebx,ecx,edx,esi,gs,fs,es,ds这些寄存器的恢复，
要将first_return_kernel(属于系统调用，而且是一段汇编代码)写在kernel/system_call.s头文件里面：
首先需要将first_return_kernel设置在全局可见:
.globl switch_to,first_return_kernel
将具体的函数实现放在system_call.s头文件里面:
.align 2 first_return_kernel: popl %edx popl %edi popl %esi pop %gs pop %fs pop %es pop %ds iret
最后要记得是在 kernel/fork.c 文件里使用了 first_return_kernel 函数，所以要在该文件里添加外部函数声明
extern void first_return_kernel(void);
编译运行
天道酬勤
有些人不会写文章就不要发，参考的几篇全有错误，最后居然还能有运行成功的截图，你们编译怎么通过的？真牛！虽然我文章都是看的别人的，但我至少保证自己独立运行一遍，能保证运行通过。幸好最后碰到一位博主，看了他的文章自惭形秽。写的特别简洁但重点突出，有自己的理解。反观自己废话连篇，文章东拼西凑。
实验六 信号量的实现和应用
实验目的
加深对进程同步与互斥概念的认识；
掌握信号量的使用，并应用它解决生产者——消费者问题；
掌握信号量的实现原理。
实验内容
本次实验的基本内容是：
在 Ubuntu 下编写程序，用信号量解决生产者——消费者问题；
在 0.11 中实现信号量，用生产者—消费者程序检验之。
用信号量解决生产者—消费者问题
在 Ubuntu 上编写应用程序“pc.c”，解决经典的生产者—消费者问题，完成下面的功能：
建立一个生产者进程，N 个消费者进程（N>1）；
用文件建立一个共享缓冲区；
生产者进程依次向缓冲区写入整数 0,1,2,…,M，M>=500；
消费者进程从缓冲区读数，每次读一个，并将读出的数字从缓冲区删除，然后将本进程 ID 和 + 数字输出到标准输出；
缓冲区同时最多只能保存 10 个数。
一种可能的输出效果是：
10: 0 10: 1 10: 2 10: 3 10: 4 11: 5 11: 6 12: 7 10: 8 12: 9 12: 10 12: 11 12: 12 …… 11: 498 11: 499
其中 ID 的顺序会有较大变化，但冒号后的数字一定是从 0 开始递增加一的。
pc.c 中将会用到 sem_open()、sem_close()、sem_wait() 和 sem_post() 等信号量相关的系统调用，请查阅相关文档。
实现信号量
Linux 在 0.11 版还没有实现信号量，Linus 把这件富有挑战的工作留给了你。如果能实现一套山寨版的完全符合 POSIX 规范的信号量，无疑是很有成就感的。但时间暂时不允许我们这么做，所以先弄一套缩水版的类 POSIX 信号量，它的函数原型和标准并不完全相同，而且只包含如下系统调用：
sem_t *sem_open(const char *name, unsigned int value); int sem_wait(sem_t *sem); int sem_post(sem_t *sem); int sem_unlink(const char *name);
sem_open() 的功能是创建一个信号量，或打开一个已经存在的信号量。
sem_t 是信号量类型，根据实现的需要自定义。
name 是信号量的名字。不同的进程可以通过提供同样的 name 而共享同一个信号量。如果该信号量不存在，就创建新的名为 name 的信号量；如果存在，就打开已经存在的名为 name 的信号量。
value 是信号量的初值，仅当新建信号量时，此参数才有效，其余情况下它被忽略。当成功时，返回值是该信号量的唯一标识（比如，在内核的地址、ID 等），由另两个系统调用使用。如失败，返回值是 NULL。
sem_wait() 就是信号量的 P 原子操作。如果继续运行的条件不满足，则令调用进程等待在信号量 sem 上。返回 0 表示成功，返回 -1 表示失败。
sem_post() 就是信号量的 V 原子操作。如果有等待 sem 的进程，它会唤醒其中的一个。返回 0 表示成功，返回 -1 表示失败。
sem_unlink() 的功能是删除名为 name 的信号量。返回 0 表示成功，返回 -1 表示失败。
在 kernel 目录下新建 sem.c 文件实现如上功能。然后将 pc.c 从 Ubuntu 移植到 0.11 下，测试自己实现的信号量。
什么是信号量？
信号量，英文为 semaphore，最早由荷兰科学家、图灵奖获得者 E. W. Dijkstra 设计，任何操作系统教科书的“进程同步”部分都会有详细叙述。
Linux 的信号量秉承 POSIX 规范，用man sem_overview可以查看相关信息。
本次实验涉及到的信号量系统调用包括：sem_open()、sem_wait()、sem_post() 和 sem_unlink()。
生产者—消费者问题
生产者—消费者问题的解法几乎在所有操作系统教科书上都有，其基本结构为：
Producer() { // 生产一个产品 item; // 空闲缓存资源 P(Empty); // 互斥信号量 P(Mutex); // 将item放到空闲缓存中; V(Mutex); // 产品资源 V(Full); } Consumer() { P(Full); P(Mutex); //从缓存区取出一个赋值给item; V(Mutex); // 消费产品item; V(Empty); }
显然在演示这一过程时需要创建两类进程，一类执行函数 Producer()，另一类执行函数 Consumer()。
思路
大家可以参考这个演示视频，先总体梳理一遍。如果实验三系统调用学的不错的话，这里的系统调用编写和编译应该是很清晰的。
通俗的讲，在用户程序中想要使用内核态中的系统调用命令，需要在用户态执行对系统调用命令的调用
通过宏展开
由此通过著名的 int 0x80 中断进入内核态
用户程序 pc.c
知识点
信号量作用
mutex 是保证互斥访问缓存池
empty 是缓冲池里空位的剩余个数，即空缓冲区数，初始值为n
full 是用来记录当前缓冲池中已经占用的缓冲区个数,初始值为0
代码展示
#define __LIBRARY__ #include <unistd.h> #include <linux/sem.h> #include <stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <linux/sched.h> _syscall2(sem_t *,sem_open,const char *,name,unsigned int,value) _syscall1(int,sem_wait,sem_t *,sem) _syscall1(int,sem_post,sem_t *,sem) _syscall1(int,sem_unlink,const char *,name) const char *FILENAME = "/usr/root/buffer_file"; /* 消费生产的产品存放的缓冲文件的路径 */ const int NR_CONSUMERS = 5; /* 消费者的数量 */ const int NR_ITEMS = 50; /* 产品的最大量 */ const int BUFFER_SIZE = 10; /* 缓冲区大小，表示可同时存在的产品数量 */ sem_t *metux, *full, *empty; /* 3个信号量 */ unsigned int item_pro, item_used; /* 刚生产的产品号；刚消费的产品号 */ int fi, fo; /* 供生产者写入或消费者读取的缓冲文件的句柄 */ int main(int argc, char *argv[]) { char *filename; int pid; int i; filename = argc > 1 ? argv[1] : FILENAME; /* O_TRUNC 表示：当文件以只读或只写打开时，若文件存在，则将其长度截为0（即清空文件） * 0222 和 0444 分别表示文件只写和只读（前面的0是八进制标识） */ fi = open(filename, O_CREAT| O_TRUNC| O_WRONLY, 0222); /* 以只写方式打开文件给生产者写入产品编号 */ fo = open(filename, O_TRUNC| O_RDONLY, 0444); /* 以只读方式打开文件给消费者读出产品编号 */ metux = sem_open("METUX", 1); /* 互斥信号量，防止生产消费同时进行 */ full = sem_open("FULL", 0); /* 产品剩余信号量，大于0则可消费 */ empty = sem_open("EMPTY", BUFFER_SIZE); /* 空信号量，它与产品剩余信号量此消彼长，大于0时生产者才能继续生产 */ item_pro = 0; if ((pid = fork())) /* 父进程用来执行消费者动作 */ { printf("pid %d:\tproducer created....\n", pid); /* printf()输出的信息会先保存到输出缓冲区，并没有马上输出到标准输出（通常为终端控制台）。 * 为避免偶然因素的影响，我们每次printf()都调用一下stdio.h中的fflush(stdout) * 来确保将输出立刻输出到标准输出。 */ fflush(stdout); while (item_pro <= NR_ITEMS) /* 生产完所需产品 */ { sem_wait(empty); sem_wait(metux); /* 生产完一轮产品（文件缓冲区只能容纳BUFFER_SIZE个产品编号）后 * 将缓冲文件的位置指针重新定位到文件首部。 */ if(!(item_pro % BUFFER_SIZE)) lseek(fi, 0, 0); write(fi, (char *) &item_pro, sizeof(item_pro)); /* 写入产品编号 */ printf("pid %d:\tproduces item %d\n", pid, item_pro); fflush(stdout); item_pro++; sem_post(full); /* 唤醒消费者进程 */ sem_post(metux); } } else /* 子进程来创建消费者 */ { i = NR_CONSUMERS; while(i--) { if(!(pid=fork())) /* 创建i个消费者进程 */ { pid = getpid(); printf("pid %d:\tconsumer %d created....\n", pid, NR_CONSUMERS-i); fflush(stdout); while(1) { sem_wait(full); sem_wait(metux); /* read()读到文件末尾时返回0，将文件的位置指针重新定位到文件首部 */ if(!read(fo, (char *)&item_used, sizeof(item_used))) { lseek(fo, 0, 0); read(fo, (char *)&item_used, sizeof(item_used)); } printf("pid %d:\tconsumer %d consumes item %d\n", pid, NR_CONSUMERS-i+1, item_used); fflush(stdout); sem_post(empty); /* 唤醒生产者进程 */ sem_post(metux); if(item_used == NR_ITEMS) /* 如果已经消费完最后一个商品，则结束 */ goto OK; } } } } OK: close(fi); close(fo); return 0; }
修改内核
编写 sem.h
文件位置：oslab/linux-0.11/include/linux
#ifndef _SEM_H #define _SEM_H #include <linux/sched.h> #define SEMTABLE_LEN 20 #define SEM_NAME_LEN 20 typedef struct semaphore{ char name[SEM_NAME_LEN]; int value; struct task_struct *queue; } sem_t; extern sem_t semtable[SEMTABLE_LEN]; #endif
编写 sem.c
#include <linux/sem.h> #include <linux/sched.h> #include <unistd.h> #include <asm/segment.h> #include <linux/tty.h> #include <linux/kernel.h> #include <linux/fdreg.h> #include <asm/system.h> #include <asm/io.h> //#include <string.h> sem_t semtable[SEMTABLE_LEN]; int cnt = 0; sem_t *sys_sem_open(const char *name,unsigned int value) { char kernelname[100]; int isExist = 0; int i=0; int name_cnt=0; while( get_fs_byte(name+name_cnt) != '\0') name_cnt++; if(name_cnt>SEM_NAME_LEN) return NULL; for(i=0;i<name_cnt;i++) kernelname[i]=get_fs_byte(name+i); int name_len = strlen(kernelname); int sem_name_len =0; sem_t *p=NULL; for(i=0;i<cnt;i++) { sem_name_len = strlen(semtable[i].name); if(sem_name_len == name_len) { if( !strcmp(kernelname,semtable[i].name) ) { isExist = 1; break; } } } if(isExist == 1) { p=(sem_t*)(&semtable[i]); //printk("find previous name!\n"); } else { i=0; for(i=0;i<name_len;i++) { semtable[cnt].name[i]=kernelname[i]; } semtable[cnt].value = value; p=(sem_t*)(&semtable[cnt]); //printk("creat name!\n"); cnt++; } return p; } int sys_sem_wait(sem_t *sem) { cli(); while( sem->value <= 0 ) sleep_on(&(sem->queue)); sem->value--; sti(); return 0; } int sys_sem_post(sem_t *sem) { cli(); sem->value++; if( (sem->value) <= 1) wake_up(&(sem->queue)); sti(); return 0; } int sys_sem_unlink(const char *name) { char kernelname[100]; int isExist = 0; int i=0; int name_cnt=0; while( get_fs_byte(name+name_cnt) != '\0') name_cnt++; if(name_cnt>SEM_NAME_LEN) return NULL; for(i=0;i<name_cnt;i++) kernelname[i]=get_fs_byte(name+i); int name_len = strlen(name); int sem_name_len =0; for(i=0;i<cnt;i++) { sem_name_len = strlen(semtable[i].name); if(sem_name_len == name_len) { if( !strcmp(kernelname,semtable[i].name)) { isExist = 1; break; } } } if(isExist == 1) { int tmp=0; for(tmp=i;tmp<=cnt;tmp++) { semtable[tmp]=semtable[tmp+1]; } cnt = cnt-1; return 0; } else return -1; }
文件位置：oslab/linux-0.11/kernel
添加系统调用号
/* 添加的系统调用号 */ #define __NR_sem_open 72 #define __NR_sem_wait 73 #define __NR_sem_post 74 #define __NR_sem_unlink 75
文件位置：oslab/linux-0.11/include/unistd.h
改写系统调用数
nr_system_calls = 76
文件位置：oslab/linux-0.11/kernel/system_call.s
添加系统调用的定义
/* ... */ extern int sys_setregid(); /* 添加的系统调用定义 */ #include <linux/sem.h> extern int sys_sem_open(); extern int sys_sem_wait(); extern int sys_sem_post(); extern int sys_sem_unlink(); /* 在sys_call_table数组中添加系统调用的引用: */ fn_ptr sys_call_table[] = { sys_setup, sys_exit, sys_fork, sys_read,……, sys_sem_open, sys_sem_wait, sys_sem_post, sys_sem_unlink}，
文件位置：oslab/linux-0.11/include/linux/sys.h
修改工程文件的编译规则
/* 第一处 */ OBJS = sched.o system_call.o traps.o asm.o fork.o \ panic.o printk.o vsprintf.o sys.o exit.o \ signal.o mktime.o sem.o /* 第二处 */ ### Dependencies: sem.s sem.o: sem.c ../include/linux/kernel.h ../include/unistd.h \ ../include/linux/sem.h ../include/linux/sched.h exit.s exit.o: exit.c ../include/errno.h ../include/signal.h \ ../include/sys/types.h ../include/sys/wait.h ../include/linux/sched.h \ ../include/linux/head.h ../include/linux/fs.h ../include/linux/mm.h \ ../include/linux/kernel.h ../include/linux/tty.h ../include/termios.h \ ../include/asm/segment.h
文件位置：oslab/linux-0.11/kernel/Makefile
Debug
反复查看 sem.h 中的代码，找不到错误。后来看了一下 sem.h 文件，发现拙劣的拼写错误
修改后，编译成功!
挂载文件
将已经修改的 unistd.h 和 sem.h 文件以及用户文件 pc.c 拷贝到linux-0.11系统中，用于测试实现的信号量
sudo ./mount-hdc cp ./linux-0.11/include/unistd.h ./hdc/usr/include/ cp ./linux-0.11/include/linux/sem.h ./hdc/usr/include/linux/ cp ./pc.c ./hdc/usr/root/ sudo umount hdc/
测试
启动新编译的linux-0.11内核，用pc.c测试实现的信号量
gcc -o pc pc.c ./pc > wcf.txt sync
结果展示：
天道酬勤
Debug好几天，也看不出来哪里有问题，索性完全复制了一份别人的，这是做的最失败的一次实验，只能保证运行结果成功。
