## 实验步骤
（1）在ubuntu下，利用系统提供的进程控制函数fork、wait系统调用编写多进程程序process.c，编译运行，分析运行结果.
后面开始修改linux0.11内核：
（2）在init/main.c中的main()中添加创建日志文件/var/process.log的语句.
（3）在printk.c中添加日志打印功能。
（4）在fork.c、sched.c和exit.c中，找到正确的状态转换点，并添加合适的状态信息
（5）用（4）中修改后的3个程序分别替换linux0.11中原有的程序，并编译内核。
（6）运行虚拟机，编译并运行process.c.
（7）在虚拟机上运行ls -l /var”或“ll /var”查看process.log是否建立，及它的属性和长度；运行“vi /var/process.log”或“more /var/process.log”查看整个log文件。检查打印出的状态转换信息是否正确。
（8）阅读0.11的[调度](http://cms.hit.edu.cn/mod/quiz/view.php?id=3410 "调度")函数schedule，分析linux的[调度](https://cms.hit.edu.cn/mod/quiz/view.php?id=3410 "调度")算法，思考下面两个问题
a、进程counter是如何初始化的？
b、当进程的时间片用完时，被重新赋成何值？
（9）对现有的[调度](http://cms.hit.edu.cn/mod/quiz/view.php?id=3410 "调度")算法进行时间片大小的修改，并重新编译、运行内核进行验证。
(1)process.c
~~~
#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <sys/times.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <sys/types.h>
#include <errno.h>
#define HZ 100
void cpuio_bound(int last, int cpu_time, int io_time);
int main(int argc, char * argv[])
{
pid_t Pid1;
pid_t Pid2;
pid_t Pid3;
Pid1 = fork();
if (Pid1 < 0) printf("error in fork!");
else if (Pid1 == 0)
{
printf("child process 1:\n");
cpuio_bound(5, 2, 2);
}
Pid2 = fork();
if (Pid2 < 0) printf("error in fork!");
else if (Pid2 == 0)
{
printf("child process 2:\n");
cpuio_bound(5, 4, 0);
}
Pid3 = fork();
if (Pid3 < 0) printf("error in fork!");
else if (Pid3 == 0)
{
printf("child process 3:\n");
cpuio_bound(5, 0, 4);
}
printf("This process's Pid is %d\n", getpid());
printf("Pid of child process 1 is %d\n", Pid1);
printf("Pid of child process 2 is %d\n", Pid2);
printf("Pid of child process 3 is %d\n", Pid3);
wait(NULL);
wait(NULL);
wait(NULL);
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;
}
}
~~~
(2)init/main.c
### 打开log文件
为了能尽早开始记录，应当在内核启动时就打开log文件。内核的入口是init/main.c中的main()（Windows环境下是start()），其中一段代码是：
~~~
……
move_to_user_mode();
if (!fork()) { /* we count on this going ok */
init();
}
……
~~~
这段代码在进程0中运行，先切换到用户模式，然后全系统第一次调用fork()建立进程1。进程1调用init()。在init()中：
~~~
……
setup((void *) &drive_info); //加载文件系统
(void) open("/dev/tty0",O_RDWR,0); //打开/dev/tty0，建立文件描述符0和/dev/tty0的关联
(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();
/***************添加开始***************/
setup((void *) &drive_info);
(void) open("/dev/tty0",O_RDWR,0); //建立文件描述符0和/dev/tty0的关联
(void) dup(0); //文件描述符1也和/dev/tty0关联
(void) dup(0); //文件描述符2也和/dev/tty0关联
(void) open("/var/process.log",O_CREAT|O_TRUNC|O_WRONLY,0666);
/***************添加结束***************/
if (!fork()) { /* we count on this going ok */
init();
}
……
~~~
(3)kernel/printk.c
向printk.c中添加日志打印功能
因为和printk的功能近似，建议将此函数放入到kernel/printk.c中。fprintk()的使用方式类同与C标准库函数fprintf()，唯一的区别是第一个参数是文件描述符，而不是文件指针。例如：
~~~
fprintk(1, "The ID of running process is %ld", current->pid); //向stdout打印正在运行的进程的ID
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'R', jiffies); //向log文件输出
~~~
将下面代码加入到printk.c中
~~~
/*
* linux/kernel/printk.c
*
* (C) 1991 Linus Torvalds
*/
/*
* When in kernel-mode, we cannot use printf, as fs is liable to
* point to 'interesting' things. Make a printf with fs-saving, and
* all is well.
*/
#include <stdarg.h>
#include <stddef.h>
#include <linux/sched.h>
#include <sys/stat.h>
#include <linux/kernel.h>
static char buf[1024];
static char logbuf[1024];
extern int vsprintf(char * buf, const char * fmt, va_list args);
int printk(const char *fmt, ...)
{
va_list args;
int i;
va_start(args, fmt);
i=vsprintf(buf,fmt,args);
va_end(args);
__asm__("push %%fs\n\t"
"push %%ds\n\t"
"pop %%fs\n\t"
"pushl %0\n\t"
"pushl $buf\n\t"
"pushl $0\n\t"
"call tty_write\n\t"
"addl $8,%%esp\n\t"
"popl %0\n\t"
"pop %%fs"
::"r" (i):"ax","cx","dx");
return i;
}
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);
if (fd < 3) /* 如果输出到stdout或stderr，直接调用sys_write即可 */
{
__asm__("push %%fs\n\t"
"push %%ds\n\t"
"pop %%fs\n\t"
"pushl %0\n\t"
"pushl $logbuf\n\t" /* 注意对于Windows环境来说，是_logbuf,下同 */
"pushl %1\n\t"
"call sys_write\n\t" /* 注意对于Windows环境来说，是_sys_write,下同 */
"addl $8,%%esp\n\t"
"popl %0\n\t"
"pop %%fs"
::"r" (count),"r" (fd):"ax","cx","dx");
}
else /* 假定>=3的描述符都与文件关联。事实上，还存在很多其它情况，这里并没有考虑。*/
{
if (!(file=task[0]->filp[fd])) /* 从进程0的文件描述符表中得到文件句柄 */
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;
}
~~~
(4)fork.c
修改下列三个文件参考进程状态表，当状态改变时，向日志输出
| 内核表示 | 含义 |
|-----|-----|
| TASK_RUNNING | 可运行 |
| TASK_INTERRUPTIBLE | 可中断的等待状态 |
| TASK_UNINTERRUPTIBLE | 不可中断的等待状态 |
| TASK_ZOMBIE | 僵死 |
| TASK_STOPPED | 暂停 |
| TASK_SWAPPING | 换入/换出 |
~~~
#include <errno.h>
#include <linux/sched.h>
#include <linux/kernel.h>
#include <asm/segment.h>
#include <asm/system.h>
extern void write_verify(unsigned long address);
long last_pid=0;
void verify_area(void * addr,int size)
{
...
}
int copy_mem(int nr,struct task_struct * p)
{
...
}
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)
{
p->start_time = jiffies;
/*在上面一行初始化了进程的开始时间所以赶快输出一条进程创建的Log*/
fprintk(3,"%ld\t%c\t%ld\n",last_pid,'N',jiffies);
...
p->state = TASK_RUNNING; /* do this last, just in case */
/*在上面一行改变了进程的状态这里输出一个进入就绪队列的Log*/
/*进程中Running表示的是可以运行，并不是正在运行*/
fprintk(3,"%ld\t%c\t%ld\n",last_pid,'J',jiffies);
return last_pid;
}
int find_empty_process(void)
{
...
}
~~~
(5)exit.c
~~~
#include <errno.h>
#include <signal.h>
#include <sys/wait.h>
#include <linux/sched.h>
#include <linux/kernel.h>
#include <linux/tty.h>
#include <asm/segment.h>
int sys_pause(void);
int sys_close(int fd);
void release(struct task_struct * p)
{
...
}
static inline int send_sig(long sig,struct task_struct * p,int priv)
{
...
}
static void kill_session(void)
{
...
}
int sys_kill(int pid,int sig)
{
...
}
static void tell_father(int pid)
{
...
}
int do_exit(long code)
{
...
}
int sys_exit(int error_code)
{
...
}
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;
/*输出一条进程退出的Log*/
/*TASK_STOPED状态只是将当前进程转入睡眠状态，收到SIG_CONT信号时会被唤醒*/
/*TASK_ZOMBIE状态则是当前进程被KILL，并发送信号给父进程*/
fprintk(3,"%ld\t%c\t%ld\n",flag,'E',jiffies);
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;
/*输出一条等待的Log*/
/*这里要注意一下输出wait的时候要判断一下 pid 是不是等于0 如果等于0 就不输出Log*/
/*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;
}
~~~
(6)sched.c
~~~
#include <linux/sched.h>
#include <linux/kernel.h>
#include <linux/sys.h>
#include <linux/fdreg.h>
#include <asm/system.h>
#include <asm/io.h>
#include <asm/segment.h>
#include <signal.h>
#define _S(nr) (1<<((nr)-1))
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))
void show_task(int nr,struct task_struct * p)
{
...
}
void show_stat(void)
{
...
}
#define LATCH (1193180/HZ)
extern void mem_use(void);
extern int timer_interrupt(void);
extern int system_call(void);
union task_union {
struct task_struct task;
char stack[PAGE_SIZE];
};
static union task_union init_task = {INIT_TASK,};
long volatile jiffies=0;
long startup_time=0;
struct task_struct *current = &(init_task.task);
struct task_struct *last_task_used_math = NULL;
struct task_struct * task[NR_TASKS] = {&(init_task.task), };
long user_stack [ PAGE_SIZE>>2 ] ;
struct {
long * a;
short b;
} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
void math_state_restore()
{
...
}
void schedule(void)
{
int i,next,c;
struct task_struct ** p;
/* 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;
/*输出就绪的Log*/
fprintk(3,"%ld\t%c\t%ld\n",(*p)->pid,'J',jiffies);
}
}
/* this is the scheduler proper: */
while (1) {
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
if (c) break;
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
}
if(current->state == TASK_RUNNING && current != task[next])
/*输出就绪的Log*/
fprintk(3,"%ld\t%c\t%ld\n",current->pid,'J',jiffies);
if(current != task[next])
/*输出可运行的Log*/
fprintk(3,"%ld\t%c\t%ld\n",task[next]->pid,'R',jiffies);
switch_to(next);
}
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE;
/*检查并输出等待的Log*/
if (current->pid != 0)
fprintk(3,"%ld\t%c\t%ld\n",current->pid,'W',jiffies);
schedule();
return 0;
}
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;
/*检查并输出等待的Log*/
if (current->pid != 0)
fprintk(3,"%ld\t%c\t%ld\n",current->pid,'W',jiffies);
schedule();
*p = tmp;
if (tmp)
{
tmp->state=TASK_RUNNING;
/*输出就绪的Log*/
fprintk(3,"%ld\t%c\t%ld\n",tmp->pid,'J',jiffies);
}
}
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;
/*检查并输出等待的Log*/
if (current->pid != 0)
fprintk(3,"%ld\t%c\t%ld\n",current->pid,'W',jiffies);
schedule();
if (*p && *p != current) {
(**p).state=TASK_RUNNING;
/*输出就绪的Log*/
fprintk(3,"%ld\t%c\t%ld\n",(**p).pid,'J',jiffies);
goto repeat;
}
*p=tmp;
if (tmp)
{
tmp->state=TASK_RUNNING;
/*输出就绪的Log*/
fprintk(3,"%ld\t%c\t%ld\n",tmp->pid,'J',jiffies);
}
}
void wake_up(struct task_struct **p)
{
if (p && *p) {
if((**p).state != TASK_RUNNING){
/*输出就绪的Log*/
fprintk(3,"%ld\t%c\t%ld\n",(**p).pid,'J',jiffies);
(**p).state=TASK_RUNNING;
}
}
}
...
~~~
附report
1.结合自己的体会，谈谈从程序设计者的角度看，单进程编程和多进程编程最大的区别是什么？
单进程编程较于多进程编程要更简单，因为单进程是顺序执行的，而多进程编程是同步执行的，所以情况要复杂得多。在设计多进程编程时，要考虑资源的分配，时间片的分配等达到系统调度的平衡。要综合考虑所有进程的情况以达到最优的并行执行效果。且多进程编程的功能更为强大，且应用范围较于单进程编程更加广泛。
2.你是如何修改时间片的？
仅针对样本程序建立的进程，在修改时间片前后，log文件的统计结果（不包括Graphic）都是什么样？
结合你的修改分析一下为什么会这样变化，或者为什么没变化？
1）include/sched.h宏INIT_TASK中定义的：
~~~
#define INIT_TASK \
{ 0,15,15, //分别对应state;counter;和priority;
~~~
将priority值修改，即可实现对时间片大小的调整。
2）在修改时间片将priority由15改为150后：
Process 9~20 中Turnaround, Waiting, CPU Burst, I/O Burst变化不大
3）原因可能是程序中I/O操作占用的时间对于总时间影响的权重过大，导致处理时间体现的并不明显。
或者变化不大的原因是，子进程连续占用cpu的时间要比时间片大很多。
