研究本文前建议先看看，我的另一篇，《Linux0.11内核–进程的调度(运行态(就绪态)和睡眠态之间的转换)》
链接https://blog.csdn.net/weixin_55255438/article/details/122254467
struct tms {
time_t tms_utime;//用户使用的CPU时间。
time_t tms_stime;//系统（内核）CPU时间。
time_t tms_cutime;//己终止的子进程使用的用户CPU时间。
time_t tms_cstime; //己终止的子进程使用的系统CPU时间
};
#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)
{
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;
}
}
int main(void)
{
pid_t a,b,son1,son2,e,father;
a=fork();
if(a==0){
//子进程1代码
son1=getpid();
printf("process1(%d) is runing!\n",son1);
cpuio_bound(10, 3, 2);
printf("process1 is finished\n");
}
else if(a>0)//此时a为fork在父进程中返回的子进程1的ID
{
son1=a;
b=fork();
if(b==0){
//子进程2代码
son2=getpid();
printf("process2(%d) is runing!\n",son2);
cpuio_bound(10, 3, 2);
printf("process1 is finished\n");
}
else if(b>0)//此时a为fork在父进程中返回的子进程2的ID
{
son2=b;
//父进程部分代码
father=getpid();
printf("father process run again\n");
printf("process1ID: %d process2ID: %d\n",a,b);
wait((int *)NULL);
wait((int *)NULL);
printf("father process ID:%d\n",father);
}
else
printf("creat son2 failed");
}
else
printf("creat son1 failed");
return 0;
}
参考
https://blog.csdn.net/weixin_41761478
https://blog.csdn.net/a634238158/article/details/100081197?spm=1001.2014.3001.5501
实验基本内容：
1.基于模板 process.c编写多进程的样本程序，实现如下功能：
所有子进程都并行运行，每个子进程的实际运行时间一般不超过 30 秒；
父进程向标准输出打印所有子进程的 id，并在所有子进程都退出后才退出；
2.在 Linux0.11上实现进程运行轨迹的跟踪：
基本任务是在内核中维护一个日志文件 /var/process.log，把从操作系统启动到系统关机过程中所有进程的运行轨迹都记录在这一 log 文件中。
3.在修改过的 0.11 上统计进程时间：
运行样本程序，通过分析 log 文件，统计该程序建立的所有进程的等待时间、完成时间（周转时间）和运行时间，然后计算平均等待时间，平均完成时间和吞吐量。可以自己编写统计程序，也可以使用 python 脚本程序—— stat_log.py（在 /home/teacher/ 目录下） ——进行统计。
4.修改0.11进程调度时间片，再次统计：
修改 0.11 进程调度的时间片，然后再运行同样的样本程序，统计同样的时间数据，和原有的情况对比，体会不同时间片带来的差异。
/var/process.log 文件的格式必须为：pid X time
其中：
pid 是进程的 ID；
X 可以是 N、J、R、W 和 E 中的任意一个，分别表示进程新建(N)、进入就绪态(J)、进入运行态®、进入阻塞态(W) 和退出(E)；
time 表示 X 发生的时间。这个时间不是物理时间，而是系统的滴答时间(tick)；三个字段之间用制表符分割。
5.实验报告问题
结合自己的体会，谈谈从程序设计者的角度看，单进程编程和多进程编程最大的区别是什么？
你是如何修改时间片的？仅针对样本程序建立的进程，在修改时间片前后，log 文件的统计结果（不包括 Graphic）都是什么样？结合你的修改分析一下为什么会这样变化，或者为什么没变化？
二、实验2.1：日志文件建立成功，5%
操作系统启动后先要打开 /var/process.log，然后在每个进程发生状态切换的时候向 log 文件内写入一条记录，其过程和用户态的应用程序没什么两样。然而，因为内核状态的存在，使过程中的很多细节变得完全不一样
每一个文件描述符会与一个打开文件相对应，同时，不同的文件描述符也会指向同一个文件。相同的文件可以被不同的进程打开也可以在同一个进程中被多次打开。系统为每一个进程维护了一个文件描述符表，该表的值都是从0开始的，所以在不同的进程中你会看到相同的文件描述符，这种情况下相同文件描述符有可能指向同一个文件，也有可能指向不同的文件。具体情况要具体分析，要理解具体其概况如何，需要查看由内核维护的3个数据结构。
一般我们讲，都说进程有文件描述符表，文件描述符表中的指针指向某个inode，这中间省略了file，dentry对象，对准确理解VFS结构无益，本文结合网络所查，并根据APUE8.3和LKD13.11章节校对,总结在下，希望有用。
内核中，对应于每个进程都有一个文件描述符表，表示这个进程打开的所有文件。文件描述表中每一项都是一个指针，指向一个用于描述打开的文件的数据块———file对象，file对象中描述了文件的打开模式，读写位置等重要信息，当进程打开一个文件时，内核就会创建一个新的file对象。需要注意的是，file对象不是专属于某个进程的，不同进程的文件描述符表中的指针可以指向相同的file对象，从而共享这个打开的文件。file对象有引用计数，记录了引用这个对象的文件描述符个数，只有当引用计数为0时，内核才销毁file对象，因此某个进程关闭文件，不影响与之共享同一个file对象的进程.
file对象中包含一个指针，指向dentry对象。dentry对象代表一个独立的文件路径，如果一个文件路径被打开多次，那么会建立多个file对象，但它们都指向同一个dentry对象。
dentry对象中又包含一个指向inode对象的指针。inode对象代表一个独立文件。因为存在硬链接与符号链接，因此不同的dentry对象可以指向相同的inode对象.inode 对象包含了最终对文件进行操作所需的所有信息，如文件系统类型、文件的操作方法、文件的权限、访问日期等。
打开文件后，进程得到的文件描述符实质上就是文件描述符表的下标，内核根据这个下标值去访问相应的文件对象，从而实现对文件的操作。（inode n.索引节点entry进入disk磁盘 route路径，也许dir_entry是进入磁盘路径）
0️⃣
进程控制块
struct task_struct {
long state; state状态; 国家 // 进程运行状态（-1不可运行，0可运行，>0以停止）
....
unsigned long close_on_exec; // 执行时关闭文件句柄位图标志 exec .n经理
struct file * filp[NR_OPEN]; // 进程使用的文件
....
struct tss_struct tss; // 本任务的tss段
}
1️⃣struct m_inode inode_table[NR_INODE]={{0,},};
2️⃣file_table.c定义了一个文件描述符(句柄)的结构数组:struct file file_table [NR_FILE];
3️⃣
open是在填file_ table数组空闲项，即管理文件表，还调用open_namei(文件名，文件名文件打开标志组合，指定文件许可属性，返回对应文件路径名的i节点指针)文件打开函数。参数3返回对应文件路径名的i节点指针，实际上参数3只是预先定义一个空间，open_namei()执行是填入对应文件路径名的i节点指针。
dup针对进程结构中的两成员，管理filp[x]和unsigned long close_on_exec;
filp[x]与file_table[x]的x都是文件句柄（文件描述符）
4️⃣
i节点磁盘i节点；内存i节点
内存i节点比磁盘i节点管理的变化更多更复杂，所以内存i节点结构成员更多。
从机构上感觉是以磁盘为树根，树叶是进程，枝干是各种结构指针
5️⃣在unsitd.h中宏定义了：
#define STDIN_FILENO 0
#define STDOUT_FILENO 1
#define STDERR_FILENO 2
这3个可以称为终端（Terminal）的标准输入（standard input），标准输出（ standard out）和标准错误输出（standard error）
每个进程的filp[0~2]都指向文件dve/tty0(tty0是个字符文件)
;open();move_to_user_mode();init()的定义）
(a)
在unsitd.h中#define __NR_dup 41和 int dup(int fildes);
dup.c中_syscall1(int,dup,int,fd);
在fcntl.c中定义
int sys_dup(unsigned int fildes)
{
return dupfd(fildes,0);
}
fn_ptr sys_call_table[] = { sys_setup, sys_exit, sys_fork, sys_read,
sys_write, sys_open, sys_close, sys_waitpid, sys_creat, sys_link,
sys_unlink, sys_execve, sys_chdir, sys_time, sys_mknod, sys_chmod,
sys_chown, sys_break, sys_stat, sys_lseek, sys_getpid, sys_mount,
sys_umount, sys_setuid, sys_getuid, sys_stime, sys_ptrace, sys_alarm,
sys_fstat, sys_pause, sys_utime, sys_stty, sys_gtty, sys_access,
sys_nice, sys_ftime, sys_sync, sys_kill, sys_rename, sys_mkdir,
sys_rmdir, sys_dup, sys_pipe, sys_times, sys_prof, sys_brk, sys_setgid,
sys_getgid, sys_signal, sys_geteuid, sys_getegid, sys_acct, sys_phys,
sys_lock, sys_ioctl, sys_fcntl, sys_mpx, sys_setpgid, sys_ulimit,
sys_uname, sys_umask, sys_chroot, sys_ustat, sys_dup2, sys_getppid,
sys_getpgrp, sys_setsid, sys_sigaction, sys_sgetmask, sys_ssetmask,
sys_setreuid,sys_setregid };
dup()是41号系统调用
(b)
在unsitd.h中#define __NR_open 5和extern int open(const char * filename, int flags, …);
在open.c中int open(const char * filename, int flag, …) {… … … … … … … … …}（open.c是直接定义接口函数，dup.c是宏定义接口函数）
int open(const char * filename, int flag, ...)
{
register int res;
va_list arg;
va_start(arg,flag);
__asm__("int $0x80"
:"=a" (res)
:"0" (__NR_open),"b" (filename),"c" (flag),
"d" (va_arg(arg,int)));
if (res>=0)
return res;
errno = -res;
return -1;
}
在linux/fs/open.c中定义sys_open()
( c )
main()中在调用move_to_user_mode();前调用了sched init ();所以内核调度进程运行时次序是随机的。
sched init ();//调度程序初始化（加载任务0的tr, ldtr)
shell程序是bin/sh(更详细翻书)
为了能尽早开始记录，应当在内核启动时就打开 log 文件。内核的入口是 init/main.c 中的 main()。细节在main()的一端代码中：
//……
move_to_user_mode();//此条代码之前进行了初始化，包括初始化进程0.此条代码执行完后进入进程0（进程0在linux/kernel/sched.c的sched_init()中定义）
if (!fork()) { //fork在子进程中返回0，
init();//进程1代码
}
//……
```c
这段代码在进程 0 中运行，先切换到用户模式，然后全系统第一次调用 fork() 建立进程 1。进程 1 调用 init()。在init()中：
// ……
setup((void *) &drive_info); //加载文件系统
(void) open("/dev/tty0",O_RDWR,0);// 打开/dev/tty0，建立文件描述符0和/dev/tty0的关联 (文件描述符是filp[x]中的变量x,即进程文件结构指针数组项的索引号)
(void) dup(0);// 让文件描述符1也和/dev/tty0关联
(void) dup(0);// 让文件描述符2也和/dev/tty0关联
// ……
这段代码建立了文件描述符 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();//此条代码之前进行了初始化，包括初始化进程0.此条代码执行完后进入进程0
/***************添加开始***************/
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()) { //fork在子进程中返回0
init();
}
//……
打开 log 文件的参数的含义是建立只写文件，如果文件已存在则清空已有内容。文件的权限是所有人可读可写。
dupfd()针对找到的空闲文件句柄，关闭标志位图close_on_exec中复位该句柄。即在运行exce()类函数时，不会关闭用函数dup()创建的句柄。
这样，文件描述符 0、1、2 和 3 就在进程 0 中建立了。根据 fork() 的原理，进程 1 会继承这些文件描述符，所以 init() 中就不必再 open() 它们。此后所有新建的进程都是进程 1 的子孙，也会继承它们。但实际上，init() 的后续代码和 /bin/sh 都会重新初始化它们。所以只有进程 0 和进程 1 的文件描述符肯定关联着 log 文件，这一点在接下来的写 log 中很重要。
2.写log文件（需要先理解 fprintk() ）
log 文件将被用来记录进程的状态转移轨迹。所有的状态转移都是在内核进行的。
在内核状态下，write() 功能失效，其原理等同于《系统调用》实验中不能在内核状态调用 printf()，只能调用 printk()。编写可在内核调用的 write() 的难度较大，所以这里直接给出源码。它主要参考了 printk() 和 sys_write() 而写成的：因为和 printk 的功能近似，建议将此函数放入到 kernel/printk.c 中。
#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;
}
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);
3.log文件中的时间参数jiffies，滴答
jiffies 表示从开机时到现在发生的时钟中断次数，这个数也被称为 “滴答数”。由代码知，jiffies 实际上记录了从开机以来共经过了多少个 10ms(1/100秒)。
4.寻找状态切换点（需要先理解？）
必须找到所有发生进程状态切换的代码点，并在这些点添加适当的代码，来输出进程状态变化的情况到 log 文件中。
此处要面对的情况比较复杂，需要对 kernel 下的 fork.c、sched.c 有通盘的了解，而 exit.c 也会涉及到。
在linux 0.11中进程状态其实只有就绪（运行）、等待、退出，处于就绪态的进程一旦得到CPU就进入到运行态。这也是系统调度的基础，就是看所有就绪态的进程哪个应该被运行（看时间片）。生成的进程状态有两种改变情形，一种是被抢占（时间片调度），一种是主动让出（等待）。其中抢占只发生在调度时，等待则有以下几种情形，sys_pause（主动暂停），sys_waitpid（等待子进程结束），sleep_on（睡眠） 以及 不可中断睡眠，而睡眠的进程被唤醒则有主动唤醒及信号唤醒。被唤醒的进程则参与调度，会再一次使用CPU。进程运行结束或被手工杀死后，进程状态会变为僵尸进程，会在调度过程中被释放。
僵尸进程是当子进程比父进程先结束，而父进程又没有回收子进程，释放子进程占用的资源，此时子进程将成为一个僵尸进程。
如果父进程先退出 ，子进程被init接管，子进程退出后init会回收其占用的相关资源
例子 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 中定义为：
因此要完成进程运行轨迹的记录就要在 copy_process() 中添加输出语句。
这里要输出两种状态，分别是“N（新建）”和“J（就绪）”。
int copy_process(int nr,……)
{
struct task_struct *p;
// ……
// 获得一个 task_struct 结构体空间
p = (struct task_struct *) get_free_page();
// ……
p->pid = last_pid;//pid是进程控制块（task_struct）的成员表示进程号，在linux/kernel/fork.c中定义long last_pid=0;表示最新进程号，其值由get_empty_process()生成。get_empty_process()会查看数组task[NR_TASKS]
// ……
// 设置 start_time 为 jiffies，start_time是进程控制块（task_struct）的成员表示进程开始运行时刻
p->start_time = jiffies;//jiffies 实际上记录了从开机以来共经过了多少个 10ms(0.01秒)。
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", p->pid, 'N', jiffies); //记录新建的进程
// ……
/* 设置进程状态为就绪。所有就绪进程的状态都是
TASK_RUNNING(0），被全局变量 current 指向的
是正在运行的进程。*/
p->state = TASK_RUNNING;
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", p->pid, 'J', jiffies); //记录就绪态进程，是一种可以运行的状态
return last_pid;
}
例子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; //TASK_UNINTERRUPTIBLE不可中断等待状态
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies); //记录阻塞态进程
// 让出 CPU
schedule(); //调度就是从就绪队列中选择一个让它来执行,所以schedule()的最后一条语句是switch_to(next);//切换到Next任务并运行。
{ //这样下面的if语句只有“当前进程"被wake_up()唤醒后才执行，当然这个"当前进程"是执行witch_to(next)中相当于crrent=next的语句，即没有被置为next前的“当前进程"
// 唤醒队列中的上一个（tmp）睡眠进程。0 换作 TASK_RUNNING 更好
// 在记录进程被唤醒时一定要考虑到这种情况，实验者一定要注意!!!
if (tmp)
{
tmp->state=0;
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", tmp->pid, 'J', jiffies);//记录就绪态进程
}
}
/* 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;//可中断等待状态
// @yyf change
/*0号进程是守护进程，cpu空闲的时候一直在waiting，输出它的话是不会通过脚本检查的哦*/
if(current->pid != 0)
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies); //记录阻塞态进程
schedule();
// 如果队列头进程和刚唤醒的进程 current 不是一个，
// 说明从队列中间唤醒了一个进程，需要处理
if (*p && *p != current) {
// 将队列头唤醒，并通过 goto repeat 让自己再去睡眠
(**p).state=0;
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", (*p)->pid, 'J', jiffies); //记录就绪态进程
goto repeat;
}
*p=NULL;
//作用和 sleep_on 函数中的一样
if (tmp){
tmp->state=0;
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", tmp->pid, 'J', jiffies);//记录就绪态进程
}
}
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE;//可中断等待状态
// @yyf change
if(current->pid != 0)
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies);//记录阻塞态进程
schedule();
return 0;
}
//exit.c中
int sys_waitpid(pid_t pid,unsigned long * stat_addr, int options)
{
int flag, code;
struct task_struct ** p;
verify_area(stat_addr,4);
repeat:
flag=0;
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) {
if (!*p || *p == current)
continue;
if ((*p)->father != current->pid)
continue;
if (pid>0) {
if ((*p)->pid != pid)
continue;
} else if (!pid) {
if ((*p)->pgrp != current->pgrp)
continue;
} else if (pid != -1) {
if ((*p)->pgrp != -pid)
continue;
}
switch ((*p)->state) {
case TASK_STOPPED:
if (!(options & WUNTRACED))
continue;
put_fs_long(0x7f,stat_addr);
return (*p)->pid;
case TASK_ZOMBIE:
current->cutime += (*p)->utime;
current->cstime += (*p)->stime;
flag = (*p)->pid;
code = (*p)->exit_code;
release(*p);
put_fs_long(code,stat_addr);
return flag;
default:
flag=1;
continue;
}
}
if (flag) {
if (options & WNOHANG)
return 0;
current->state=TASK_INTERRUPTIBLE;//可中断等待状态#define TASK_INTERRUPTIBLE 1 //进程处于可中断等待状态。
// @yyf change
/*0号进程是守护进程，cpu空闲的时候一直在waiting，输出它的话是不会通过脚本检查的哦*/
if(current->pid != 0)
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies); //记录阻塞态进程
schedule();
if (!(current->signal &= ~(1<<(SIGCHLD-1))))
goto repeat;
else
return -EINTR;
}
return -ECHILD;
}
例子3：调度算法
调度程序：为所有处于TASK_RUNNING状态的进程分配CPU运行时间的管理代码。在 Linux 0.11 中采用了基于优先级排队的调度策略。
TASK_RUNNING不只是运行，还有就绪状态。
Linux 进程虽然是抢占式的，但被抢占的进程仍然处于TASK_RUNNING 状态，只是暂时没有被 CPU 运行。
算法细节
基于优先级的排队策略。通过比较每个TASK_RUNNING任务的 运行时间 递减滴答计数 counter 的值来确定当前哪个进程运行的时间最少。 若counter=0，重新计算所有进程(包括睡眠)，counter = counter / 2 + priority。
根据上述原则选择出一个进程，最后调用 switch_to()执行实际的进程切换操作。
schedule() 找到的 next 进程是接下来要运行的进程（注意，一定要分析清楚 next 是什么）。如果 next 恰好是当前正处于运行态的进程，switch_to(next) 也会被调用。这种情况下相当于当前进程的状态没变。
如果不一样，则将当前进程状态置为就绪，而next进程状态置为运行。
//后文有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; #define TASK_RUNNING 0 //进程正在运行或已准备就绪。
fprintk(3, "%ld\t%c\t%ld\n", (*p)->pid, 'J', 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;
}
//@yyf change 切换到相同的进程不输出
if(current != task[next]){
if(current->state == TASK_RUNNING){ //#define TASK_RUNNING 0 //进程正在运行或已准备就绪。
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'J', jiffies);
}
fprintk(3, "%ld\t%c\t%ld\n", task[next]->pid, 'R', jiffies);
}
// 切换到 next 进程
switch_to(next);
例子4：睡眠到就绪
void wake_up(struct task_struct **p)
{
if (p && *p) {
if((**p).state != TASK_RUNNING){
(**p).state=TASK_RUNNING;
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", (*p)->pid, 'J', jiffies);
}
}
}
例子5：进程退出
当一个进程结束了运行或在半途中终止了运行，那么内核就需要释放该进程所占用的系统资源。这包括进程运行时打开的文件、申请的内存等。
当一个用户程序调用exit()系统调用时，就会执行内核函数do_exit()。该函数会首先释放进程代码段和数据段占用的内存页面，关闭进程打开着的所有文件，对进程使用的当前工作目录、根目录和运行程序的i节点进行同步操作。如果进程有子进程，则让init进程作为其所有子进程的父进程。如果进程是一个会话头进程并且有控制终端，则释放控制终端(如果按照实验的数据，此时就应该打印了)，并向属于该会话的所有进程发送挂断信号 SIGHUP，这通常会终止该会话中的所有进程。然后把进程状态置为僵死状态 TASK_ZOMBIE。并向其原父进程发送 SIGCHLD 信号，通知其某个子进程已经终止。最后 do_exit()调用调度函数去执行其他进程。由此可见在进程被终止时，它的任务数据结构仍然保留着。因为其父进程还需要使用其中的信息。
在子进程在执行期间，父进程通常使用wait()或 waitpid()函数等待其某个子进程终止。当等待的子进程被终止并处于僵死状态时，父进程就会把子进程运行所使用的时间累加到自己进程中。最终释放已终止子进程任务数据结构所占用的内存页面，并置空子进程在任务数组中占用的指针项。
//改动exit.c
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));
for (i=0 ; i<NR_TASKS ; i++)
if (task[i] && task[i]->father == current->pid) {
task[i]->father = 1;
if (task[i]->state == TASK_ZOMBIE)
/* assumption task[1] is always init */
(void) send_sig(SIGCHLD, task[1], 1);
}
for (i=0 ; i<NR_OPEN ; i++)
if (current->filp[i])
sys_close(i);
iput(current->pwd);
current->pwd=NULL;
iput(current->root);
current->root=NULL;
iput(current->executable);
current->executable=NULL;
if (current->leader && current->tty >= 0)
tty_table[current->tty].pgrp = 0;
if (last_task_used_math == current)
last_task_used_math = NULL;
if (current->leader)
kill_session();
current->state = TASK_ZOMBIE;//#define TASK_ZOMBIE 3 //进程处于僵死状态，已经停止运行，但父进程还没发信号。
// @yyf change
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'E', jiffies);
current->exit_code = code;
tell_father(current->father);
schedule();
return (-1); /* just to suppress warnings */
}
int sys_exit(int error_code)
{
return do_exit((error_code&0xff)<<8);
}
总的来说，Linux 0.11 支持四种进程状态的转移：就绪到运行、运行到就绪、运行到睡眠和睡眠到就绪，此外还有新建和退出两种情况。其中就绪与运行间的状态转移是通过 schedule()（它亦是调度算法所在）完成的；运行到睡眠依靠的是 sleep_on() 和 interruptible_sleep_on()，还有进程主动睡觉的系统调用 sys_pause() 和 sys_waitpid()；睡眠到就绪的转移依靠的是 wake_up()。所以只要在这些函数的适当位置插入适当的处理语句就能完成进程运行轨迹的全面跟踪了。
为了让生成的 log 文件更精准，以下几点请注意：
进程退出的最后一步是通知父进程自己的退出，目的是唤醒正在等待此事件的父进程。从时序上来说，应该是子进程先退出，父进程才醒来。
系统无事可做的时候，进程 0 会不停地调用 sys_pause()，以激活调度算法。此时它的状态可以是等待态，等待有其它可运行的进程；也可以叫运行态，因为它是唯一一个在 CPU 上运行的进程，只不过运行的效果是等待。
实验结果如下：
三、实验2.2：能向日志文件输出信息，5%。5种状态都能输出，10%
日志文件的管理与代码编写无关，有几个要点要注意：
每次关闭 bochs 前都要执行一下 sync 命令，它会刷新 cache，确保文件确实写入了磁盘。
在 0.11 下，可以用 ls -l /var 或 ll /var 查看 process.log 是否建立，及它的属性和长度。
一定要实践《实验环境的搭建与使用》一章中关于文件交换的部分。最终肯定要把 process.log 文件拷贝到主机环境下处理。
在 0.11 下，可以用 vi /var/process.log 或 more /var/process.log 查看整个 log 文件。不过，还是拷贝到 Ubuntu 下看，会更舒服。
在 0.11 下，可以用 tail -n NUM /var/process.log 查看 log 文件的最后 NUM 行。
一种可能的情况下，得到的 process.log 文件的前几行是：
1 N 48 //进程1新建（init()）。此前是进程0建立和运行，但为什么没出现在log文件里？
1 J 49 //新建后进入就绪队列
0 J 49 //进程0从运行->就绪，让出CPU
1 R 49 //进程1运行
2 N 49 //进程1建立进程2。2会运行/etc/rc脚本，然后退出
2 J 49
1 W 49 //进程1开始等待（等待进程2退出）
2 R 49 //进程2运行
3 N 64 //进程2建立进程3。3是/bin/sh建立的运行脚本的子进程
3 J 64
2 E 68 //进程2不等进程3退出，就先走一步了
1 J 68 //进程1此前在等待进程2退出，被阻塞。进程2退出后，重新进入就绪队列
1 R 68
4 N 69 //进程1建立进程4，即shell
4 J 69
1 W 69 //进程1等待shell退出（除非执行exit命令，否则shell不会退出）
3 R 69 //进程3开始运行
3 W 75
4 R 75
5 N 107 //进程5是shell建立的不知道做什么的进程
5 J 108
4 W 108
5 R 108
4 J 110
5 E 111 //进程5很快退出
4 R 111
4 W 116 //shell等待用户输入命令。
0 R 116 //因为无事可做，所以进程0重出江湖
4 J 239 //用户输入命令了，唤醒了shell
4 R 239
4 W 240
0 R 240
……
四、实验3和4：统计时间与调度算法修改，10%
为展示实验结果，需要编写一个数据统计程序，它从 log 文件读入原始数据，然后计算平均周转时间、平均等待时间和吞吐率。
任何语言都可以编写这样的程序，实验者可自行设计。我们用 python 语言编写了一个——stat_log.py（这是 python 源程序，可以用任意文本编辑器打开）。
python 是一种跨平台的脚本语言，号称 “可执行的伪代码”，非常强大，非常好用，也非常有用，建议闲着的时候学习一下。
其解释器免费且开源，Ubuntu 下这样安装：
# 在实验楼的环境中已经安装了 python，可以不必进行此操作
$ sudo apt-get install python
然后只要给 stat_log.py 加上执行权限（使用的命令为 chmod +x stat_log.py）就可以直接运行它。
此程序必须在命令行下加参数执行，直接运行会打印使用说明。
Usage:
./stat_log.py /path/to/process.log [PID1] [PID2] ... [-x PID1 [PID2] ... ] [-m] [-g]
Example:
# Include process 6, 7, 8 and 9 in statistics only. (Unit: tick)
./stat_log.py /path/to/process.log 6 7 8 9
# Exclude process 0 and 1 from statistics. (Unit: tick)
./stat_log.py /path/to/process.log -x 0 1
# Include process 6 and 7 only. (Unit: millisecond)
./stat_log.py /path/to/process.log 6 7 -m
# Include all processes and print a COOL "graphic"! (Unit: tick)
./stat_log.py /path/to/process.log -g
运行 ./stat_log.py process.log 0 1 2 3 4 5 -g（只统计 PID 为 0、1、2、3、4 和 5 的进程）的输出示例：
(Unit: tick)
Process Turnaround Waiting CPU Burst I/O Burst
0 75 67 8 0
1 2518 0 1 2517
2 25 4 21 0
3 3003 0 4 2999
4 5317 6 51 5260
5 3 0 3 0
Average: 1823.50 12.83
Throughout: 0.11/s
-----===< COOL GRAPHIC OF SCHEDULER >===-----
[Symbol] [Meaning]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
number PID or tick
"-" New or Exit
"#" Running
"|" Ready
":" Waiting
/ Running with
"+" -| Ready
\and/or Waiting
-----===< !!!!!!!!!!!!!!!!!!!!!!!!! >===-----
40 -0
41 #0
42 #
43 #
44 #
45 #
46 #
47 #
48 |0 -1
49 | :1 -2
50 | : #2
51 | : #
52 | : #
53 | : #
54 | : #
55 | : #
56 | : #
57 | : #
58 | : #
59 | : #
60 | : #
61 | : #
62 | : #
63 | : #
64 | : |2 -3
65 | : | #3
66 | : | #
67 | : | #
…………
小技巧：如果命令行程序输出过多，可以用 command arguments | more （command arguments 需要替换为脚本执行的命令）的方式运行，结果会一屏一屏地显示。
“more” 在 Linux 和 Windows 下都有。Linux 下还有一个 “less”，和 “more” 类似，但功能更强，可以上下翻页、搜索。
修改时间片：
下面是 0.11 的调度函数 schedule，在文件kernel/sched.c 中定义为：
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;
}
// 切换到 next 进程
switch_to(next);
分析代码可知，0.11 的调度算法是选取 counter 值最大的就绪进程进行调度。
其中运行态进程（即 current）的 counter 数值会随着时钟中断而不断减 1（时钟中断 10ms 一次），所以是一种比较典型的时间片轮转调度算法。
另外，由上面的程序可以看出，当没有 counter 值大于 0 的就绪进程时，要对所有的进程做 (*p)->counter = ((*p)->counter >> 1) + (*p)->priority。其效果是对所有的进程（包括阻塞态进程）都进行 counter 的衰减，并再累加 priority 值。这样，对正被阻塞的进程来说，一个进程在阻塞队列中停留的时间越长，其优先级越大，被分配的时间片也就会越大。
所以总的来说，Linux 0.11 的进程调度是一种综合考虑进程优先级并能动态反馈调整时间片的轮转调度算法。
此处要求实验者对现有的调度算法进行时间片大小的修改，并进行实验验证。
为完成此工作，我们需要知道两件事情：
进程 counter 是如何初始化的
当进程的时间片用完时，被重新赋成何值？
首先回答第一个问题，显然这个值是在 fork() 中设定的。Linux 0.11 的 fork() 会调用 copy_process() 来完成从父进程信息拷贝（所以才称其为 fork），看看 copy_process() 的实现（也在 kernel/fork.c 文件中），会发现其中有下面两条语句：
// 用来复制父进程的PCB数据信息，包括 priority 和 counter
*p = *current;
// 初始化 counter
p->counter = p->priority;
// 因为父进程的counter数值已发生变化，而 priority 不会，所以上面的第二句代码将p->counter 设置成 p->priority。
// 每个进程的 priority 都是继承自父亲进程的，除非它自己改变优先级。
// 查找所有的代码，只有一个地方修改过 priority，那就是 nice 系统调用。
int sys_nice(long increment)
{
if (current->priority-increment>0)
current->priority -= increment;
return 0;
}
本实验假定没有人调用过 nice 系统调用，时间片的初值就是进程 0 的 priority，即宏 INIT_TASK 中定义的：
#define INIT_TASK \
{ 0,15,15,
// 上述三个值分别对应 state、counter 和 priority;
接下来回答第二个问题，当就绪进程的 counter 为 0 时，不会被调度（schedule 要选取 counter 最大的，大于 0 的进程），而当所有的就绪态进程的 counter 都变成 0 时，会执行下面的语句：
(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
显然算出的新的 counter 值也等于 priority，即初始时间片的大小。
提示就到这里。如何修改时间片，自己思考、尝试吧。
实验结果如下：时间片priority=15
时间片priority=150
五、实验5：实验报告，20%
单进程编程和多进程编程有多种区别。
1）执行方式：
单进程是一个进程按设计好的流程从上到下顺序执行，程序设计者需要在该进程内合理安排执行顺序；而多进程是多个进程同时执行的，是并行的（实际上是高速切换着运行这多个进程），程序设计者除了考虑每个进程内的执行顺序，还要合理安排每个进程的流程。
2）数据同步：
单进程的数据是同步的，在该进程中改变数据，影响是全局的。
而多进程中，子进程数据是父进程数据在内存另一位置的拷贝，是相互独立的，互不影响对父进程数据的操作不会影响子进程数据，子进程同样。
3）CPU利用率：
单进程在等待io时，cpu是空闲的；因此，CPU利用率低。
多进程在某一进程等待io时，通过各种复杂而灵活的调度算法，运行另一个进程，所以CPU利用率高。
4）单进程的用途较为单一，而多进程的用途广泛。
修改include/linux/sched.h/INIT_TASK中的priority就可以改变时间片大小。
变化不大的原因是，子进程连续占用cpu的时间要比时间片大很多。
仅针对样本程序建立的进程，在修改时间片前后，log文件的统计结果（不包括Graphic）都是什么样？结合你的修改分析一下为什么会这样变化，或者为什么没变化？
依次将时间偏设为1，5，10，15，20，25，50，100，150后，经统计分析log文件可以发现：
1）在一定的范围内，平均等待时间，平均完成时间的变化随着时间片的增大而减小。这是因为在时间片小的情况下，cpu将时间耗费在调度切换上，所以平均等待时间增加。
2）超过一定的范围之后，这些参数将不再有明显的变化，这是因为在这种情况下，RR轮转调度就变成了FCFS先来先服务了。随着时间片的修改，吞吐量始终没有明显的变化，这是因为在单位时间内，系统所能完成的进程数量是不会变的。
最后补番外链接：
1.实验楼（操作系统原理与实践）
https://www.shiyanlou.com/courses/115
2.网易云课堂：哈尔滨工业大学，国家级精品课程，操作系统
https://mooc.study.163.com/course/1000002004#/info
3.推荐markdown神器，本文由此写成
https://typora.io/
(完)