1.操作系统的多进程图像

操作系统main函数中最后 if(!fork()) {init();} ,也就是main函数最后创建了第1个进程,init执行了shell(Windows)桌面。

**操作系统管理和组织进程都使用PCB(Process Control Block)**,不同的程序的PCB放在不同的位置,用于记录该进程运行时的状态。操作系统对进程进行分类,例如等待执行的进程和等待某些事件完成的进程,例如等待磁盘读写。

  1. 新建态:系统完成创建进程的一系列工作。只能转换到就绪态

  2. 就绪态:拥有除CPU之外的其他所需的所有资源。当拥有CPU时就可以转换到运行态

  3. 运行态:用于CPU和所需的所有资源

    1. 当时间片到或者处理机被抢占了,就转换到就绪态;
    2. 当进程用“系统调用”的方式申请某种系统资源或者请求等待某个事件的发生,则进入阻塞态(主动)
  4. 阻塞态:没有所需要的资源。当所需要的资源得到分配时,进入就绪态(被动)

  5. 终止态:进程运行结束或者出现不可修复的错误时,由运行态转到终止态

进程切换的三个部分:队列操作+调度+切换

1
2
3
4
5
6
7
pCur.state = 'W';    // 启动磁盘读写,将当前进程设置为阻塞状态
schedule();    // 将pCur放到DiskWaitQueue
schedule()
{
pNew = getNext(ReadyQueue);  // 从就绪队列找到下一个进程,调度函数算法非常复杂
switch_to(pCur,pNew);  // 保存当前进程的现场,把下一个进程的现场恢复
}

把当前进程的现场保存到pCur中(PCB),把切换程序的pNew(PCB)读取到寄存器中

多个进程同时存在于内存的问题:不同进程的地址可能影响其他进程的代码,这可能导致其他进程的崩溃。操作系统需要维护一张映射表,将内存映射到实际的内存地址中,把不同的进程隔离开来保证进程的安全,下图中同样对内存100的操作分别映射到了内存地址780和内存地址1260。

但实际上多进程之间可能存在合作关系,比如打印机进程需要读取word进程的内容来完成打印的工作,这时可以提交到共享缓冲区。但这里可能存在一个问题,因为进程1和进程2是交替进行的,可能进程1首先读取到空间7是空的,接下来切换到进程2也读取到空间7是空的,开始向空间7写入,接下来切换到进程1继续在这里写入,会导致写入缓冲区的内容是错误的。所以操作系统需要管理一个合理的进程推进顺序。

2.用户级线程

进程 = 资源(映射表) + 指令执行序列

线程是只切换指令,如PC和寄存器,而不切换映射表,这种切换保留了并发了优点,避免了进程切换的代价

举例说明,对于浏览器来说,可以用一个线程接收服务器数据,一个线程显示文本,一个线程处理图片,一个线程显示图片,它们不需要用多个映射表完全分离开,没有必要用多个进程完成这些工作。我们需要的工作主要就是下面看到的两个部分,创建Create线程进行工作处理,使用Yield跳转到另一个线程工作。

1
2
3
4
5
6
7
8
9
10
11
void WebExplorer()
{
char URL[] = "http://cms.hit.edu.cn";
char buffer[1000];
pthread_create(..., GetData, URL, buffer);
pthread_create(..., Show, buffer);
}
void GetData(char *URL, char *p)
{...}
void Show(char *p)
{...}

线程切换的详细过程:每个线程都有自己的栈。线程1执行过程中,首先调用函数B(),保护现场,将上一段程序的帧指针和函数B完成后PC应指向的地址压入栈(参见【深入理解计算机系统】3.程序的机器级表示),接下来调用Yield()函数,保护现场,将之前的帧指针和Yield函数结束后的PC204压入栈,接下来Yield函数将当前栈指针1000保存在TCB1中,并将栈指针切换到TCB2的栈指针2000,完成了线程间的切换。接下来线程2的Yield使得栈指针回到1000处,继续上一个线程对应位置执行。下面给出了用户级线程的Create和Yield核心代码。

1
2
3
4
5
6
7
8
9
10
11
12
void Yield()
{
TCB1.esp = esp;  //Thread Control Block
esp = TCB2.esp;
}
void ThreadCreate(A)
{
TCB *tcb=malloc();   //申请空间保存TCB
*stack=malloc();    //申请空间保存栈
*stack = A;       //向栈中压入数据
tcb.esp=stack;     //将栈和TCB建立联系
}

3.内核级线程

用户级线程存在的问题,用户级线程在请求下载数据的过程中,理想情况是下载了一些后跳转到显示文本的线程执行,但实际上内核级线程不知道这些事情,由于等待网卡IO会阻塞这个进程,最后导致浏览器没有实现我们需要的功能。

所以引入内核级线程,ThreadCreate是系统调用,会进入内核,Yield的调度由系统决定。

接下来看一下多核和多CPU,可以看到多核CPU只有一套MMU(内存映射),也就是多核心CPU在执行进程的时候,也需要切换内存映射再执行,只有多处理器才能并行运行多个进程。但这个时候内核级线程的优势就体现出来了,多核CPU可以并行的执行同一进程不同线程的代码,因为这些代码共用一套内存映射。

对于内核级线程,它与用户级线程的区别是

用户级线程在用户栈执行,多个用户级线程对应了多个用户栈,1个TCB(用户态)关联1个用户栈;

内核级线程在用户栈和内核栈都需要执行和调用函数,所以多内核级线程实际上对应了多套栈(包括用户栈和内核栈),1个TCB(内核态)关联1个用户栈和1个内核栈。

int中断指令会引起内核栈的切换,内核栈中记录了用户栈用户代码两部分内容。SS寄存器(栈顶段地址)和SP寄存器(偏移地址)的值,SS:SP是此时栈顶位置;PC记录了用户代码程序运行的代码位置,CS记录了用户代码段基址

内核级线程的切换包含5个阶段

1.中断入口(进入切换):系统中断线程1从用户态进入内核态,用户态寄存器的值保存到内核栈

2.中断处理(引发切换):调用schedule函数,引起TCB切换。这里有可能启动磁盘读写或时钟中断,内核会调用schedule找到下一个要执行的TCB,然后用next指针指向这个TCB

3.内核栈切换(switch_to):把当前ESP寄存器放在current指向的TCB中,然后把next指向的esp赋给寄存器,完成内核栈指向地址的切换,现在ESP指向了下一个线程的TCB地址

4.中断返回(iret):把TCB存储的内核栈现场恢复出来

5.用户栈切换:切换回用户态PC指针还有对应的用户栈

4.内核级线程实现

首先从这段代码开始,main函数开始,首先遇到函数A,用户栈中压入A的返回地址(也就是B的初始地址),在A函数执行中遇到fork()函数,首先将系统调用号__NR_fork移入%eax寄存器,然后调用INT 0x80中断,执行这条指令时PC自动加1,此时PC指向下一行mov res,%eax。触发INT 0x80中断后,cpu立刻找到用户栈对应的内核栈,将当前时刻的SS和SP压入内核栈,接下来将返回地址CSIP压入内核栈,也就是mov res,%eax这一行。接下来执行system_call

1
2
3
4
5
6
7
8
9
10
11
12
_system_call:
cmpl $nr_system_calls-1,%eax # 调用号超出范围就在eax设置-1并退出
ja bad_sys_call
push %ds %es %fs # 保存原段寄存器值
pushl %edx %ecx %ebx # 一个系统调用最多带3个参数,这里存放了系统对应C语言函数调用的参数
movl $0x10,%edx # 设置ds和es到内核段
mov %dx,%ds
mov %dx,%ex #edx的低16位赋值给ds和es指向内核数据段
movl $0x17,%edx
mov %dx,%fs
call _sys_call_table(,%eax,4)
pushl %eax  #系统调用返回值压入栈

下图为切换5段论的中断入口和中断出口。_system_call首先保护现场,将原段寄存器的值压入栈,然后将调用的参数压入栈,接下来调用sys_fork,他首先判断判断当前程序TCB是不是等于0,等于0说明已经就绪,如果不等于0说明线程阻塞,则应该重新调度reschedule(也就是切换5段论中间3段,切换TCB),完成后进行中断返回ret_from_sys_call

下图为切换5段论的中断出口,对应入口的大量push压入栈,出口把保存在TCB中的数据pop出栈

切换5段论中的switch_to使用的时TSS切换,是一个长跳转。TR表示当前cpu对应的任务段,TR改变时会把寄存器中的内容全部保存到旧的TSS中,然后把新的TSS中所有内容都会加载到寄存器

创建一个线程最重要的就是做出可以切换的样子。_sys_fork首先拷贝父进程的所有参数,这些参数都已经在中断过程压入内核栈,

copy_process的细节:创建栈。申请一页内存用于保存PCB和内核栈,注意这里内核栈重新创建,但ss和esp的栈与父进程一模一样,也就是它可以和父进程用同样的代码同样的栈,eip是int 0x80中断的下一句话。最后如果创建了子进程,会把%eax置为0,所以从子进程返回到mov res,%eax的时候,res是0;但如果从父进程返回到mov res,%eax,res是非0,所以有一段经典代码if(!fork()){子进程代码段}else{父进程代码段},这样就实现了子进程和父进程都返回这个位置,但执行不同的代码

如何让子进程执行我们想要的代码?下面给出了更为详细的代码,如果非fork则执行代码,如果是父进程则执行另一部分代码。

5.CPU调度策略

吞吐量和响应时间之间有矛盾:响应时间小 -> 切换次数多 -> 系统内耗大 -> 吞吐量小

前台任务和后台任务的关注点不同:前台任务关注响应时间(从提交到相应的时间间隔),后台任务关注周转时间(从提交到完成的时间间隔)

需要综合考虑IO约束型任务和CPU约束型任务

应该综合考虑花费时间短的程序优先执行来降低周转时间,划分时间片来降低响应时间,同时也应该为前台和后台应用划分优先级

6.进程同步与信号量

不同进程需要合作,例如打印机的打印队列与word文档之间的合作,这种同步是通过信号量控制的

进程同步就是控制进程交替执行的过程,保证多进程合作合理有序

假设有3个生产者进程P,1个消费者进程C,1个缓冲区,用信号量来表示缓冲区的状态,这些进程就可以通过信号量实现进程同步(也就是进程的等待和唤醒)

(1)缓冲区满,P1执行,P1发现缓冲区满所以sleep,设置sem=-1(有1个进程等待,缓冲区缺少1个位置)

(2)P2执行,P2 sleep,设置sem=-2(有2个进程等待)

(3)C执行,打印1份文件,缓冲区增加1个空间,wakeup P1,设置sem=-1

(4)C再执行,缓冲区又增加1个空间,wakeup P2,设置sem=0

(4)C再执行,不需要唤醒进程,设置sem=1(缓冲区盈余1个位置)

(5)P3执行,因为缓冲区还有内容,直接执行,设置sem=0

信号量的临界区保护

信号量是一个共有的变量,大家一起修改一起使用,多进程切换过程中可能存在问题。下面生产者P1和P2会修改empty信号量,调用生产者P1或P2时,他们都会首先读取现在的信号量,接下来将信号量-1,并把这个值赋回给公共的信号量。接下来右图给出了一种可能的调度,由于生产者P1在信号量-1之后没有将该信号量赋值给公共的信号量,此时发生调度转到了生产者P2,这就导致本来应该两个生产者使信号量-2,但实际上只-1

解决方法:写共享变量empty时阻止其他进程访问,即上锁的思想

临界区:一次只允许一个进程进入的该进程的那一段代码,在这里就是每个进程中修改empty的这段代码,这里最重要的工作就是找到进程临界区的代码。核心思想就是进程进入临界区代码时进行一些操作,退出临界区后再进行一些操作,基本原则互斥进入,其次应该有空让进,并且是有限等待的。

下面是两种临界区控制的尝试,分别为轮换法和标记法。

轮换法: 使用turn变量控制进入。首先看互斥进入,如果P0进入说明turn=0,如果P1进入说明turn=1,满足互斥性,但是可能P0完成后将turn置为1,P1进程又在阻塞状态,就导致P1进程不使用临界区代码,P0进程又无法进入临界区代码,不满足有空让进

标记法:如果进程想要进入自己的临界区,就将自己的标记flag设置为true。首先看互斥性,如果P0进入说明flag[0]=true,flag[1]=false,如果P1进入说明flag[1]=true,flag[0]=false,满足互斥性。接下来看有空让进,两个进程都会检测对方是否想要进入临界区,如果想要进入就谦让,但有可能双方同时调整了自己的标志位,最后导致双方互相谦让,没有人能进入临界区,不满足无限等待

这两种标志太对称了,你也一样我也一样,最后卡死在这个地方

Peterson算法:如果P0想要进入临界区,修改P0的flag为true,并且修改turn下一次应该是进程1运行。

互斥性:

P0进入flag[0]=true,flag[1]=false或turn=0

P1进入flag[1]=true,flag[0]=false或turn=1

连起来看就是如果P0和P1同时进入时一定flag[0]=flag[1]=true,那么只能turn=0=1,矛盾,满足互斥性

有空让进:P1不在临界区时,出临界区设置flag[1]=false,入临界区前turn=0,P0都可以进入

无限等待:turn一定等于0或等于1,所以永远有一个可以进入

多个进程进入临界区的解决办法:

1.面包店算法。仍然是标记和轮转的结合,每个进程都会获得一个序号,序号最小的进入,进程离开时序号为0,不为0的号就是标记。每个进入商店的客户都会获得一个号码,号码小的先得到服务。互斥进入一定满足,因为大家号不一样,有空让进也满足,最小序号的进入,有限等待也满足,他是一个队列。但代码实现很复杂,有可能溢出,排号也很麻烦

2.硬件实现:最简单的办法实际上是阻止调度,临界区出现问题的根本原因是调度,另一个进程操作了一个共有的变量。硬件提供了cli()关中断和sti()开中断,可以在cpu硬件中加一个标记,但多CPU不太好使

3.硬件原子指令法:锁本质上就是一个变量,让其他代码不能同时执行这一段的代码,也就是这段代码不能因为调度被打断。硬件提供了一种一次执行完毕的指令,如果x是true,则该指令返回true,在while处空转;如果x是false,它会把x置为true,接下来返回false,进入临界区执行,但其它代码就无法进入了

7.信号量的代码实现

linux-0.11/include/linux 下定义信号量的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
#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

linux-0.11/kernel 下编写信号量的4个系统调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#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>
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;
// 信号量名字长度不能越界
while(get_fs_byte(name+i) != '\0')
{
if(i<100)
{
kernelname[i]=get_fs_byte(name+i);
i++;
}
else
{
return NULL;
}
}

// 判断信号两是否已经存在
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]);
}
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]);
cnt++;
}
return p;
}

// 信号量P原子操作
int sys_sem_wait(sem_t *sem)
{
cli();
while(sem->value <= 0)
sleep_on(&(sem->queue));
sem->value--;
sti();
return 0;
}

// 信号量V原子操作
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;
}

实际生产者和消费者调用信号量实现的一个简述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
METUX: 互斥信号量, 防止生产消费同时进行
FULL: 产品剩余信号量, 大于0表示可以消费
EMPTY: 空信号量, 大于0时生产者才生产
消费者消费完后程序结束
*/

// 生产者
sem_wait(empty);
sem_wait(metux);
/* 生产者执行代码 */
sem_post(full);
sem_post(metux);

// 消费者
sem_wait(full);
sem_wait(metux);
/* 消费者执行代码 */
sem_post(empty);
sem_post(metux);

8.实验

1.尝试体验使用fork创建进程,main函数中实现了进程创建和执行不同的函数,cpuio_bound模拟了进程使用cpu和进行io

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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]; //子进程的PID号
int i;
for(i=0;i<10;i++)
{
/*
*fork()创建进程
*返回值为0则创建子进程成功并从子进程返回
*返回值为PID则是从父进程返回
*返回值小于0表示进程创建失败
*/
n_proc[i] = fork();
if(n_proc[i] == 0)
{
// 从子进程返回会进入下面该代码区
// 执行函数结束后return0结束子进程
cpuio_bound(20, 2*i, 20-2*i);
return 0;
else if(n_proc[i] < 0)
{
printf("Faild to fork child process %d!\n", i+1);
return -1;
}
}
// 父进程执行完创建子进程后会进入该代码区打印子进程的PID
for(i=0;i<10;i++)
{
printf("Child PID: %d\n", n_proc[i]);
}
wait(&i);
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(&current_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;
}
}

8.1实现进程的内核级切换

内核创建流程:通过 int0x80 中断进入 system_call 汇编函数,根据 __NR_fork 号调用 sys_fork 函数,该函数中调用了 copy_process 函数来创建自己的内核栈并牵手父进程的用户栈

进程切换流程: schedule 函数找到下一进程的PCB(进程控制块)和LDT(局部描述符),调用 switch_to 汇编函数进行PCB和内核栈的切换,并弹出回用户栈

补充:写给之后的计算机内存管理。 fork() 会产生一个和父进程完全相同的子进程,但子进程在此后多会 exec 系统调用,出于效率考虑,linux中引入了“读时共享,写时复制“技术,也就是只有进程空间的各段的内容要发生变化时,才会将父进程的内容复制一份给子进程,而读取的值不需要进行复制

fork之后exec之前两个进程用的是相同的物理内存,子进程的代码段、数据段、堆栈都是指向父进程的物理内存,也就是两者的虚拟内存不同,但其对应的物理空间是同一个,当父子进程中有更改相应段的行为发生时,再为子进程相应的段分配物理空间

如果不是因为exec,内核会给子进程的数据段、堆栈段分配相应的物理空间(至此两者有各自的进程空间,互不影响),而代码段继续共享父进程的物理空间(两者的代码完全相同)

如果是因为exec,由于两者执行的代码不同,子进程的代码段也会分配单独的物理空间

总之,不同进程之间应该是完全隔离开的,进程是操作系统资源分配的基本单位。线程才可以与进程共享物理内存

实验部分: Linux0.11中的 switch_to 是使用Intel提供的 ljmp 指令完成的,它将TSS中保存的寄存器映像完全覆盖到CPU中实现进程切换,但这个指令大约需要200个时钟周期,执行时间很长,本次实验主要目的是:

  • (1)重写 switch_to
  • (2)将重写的 switch_toschedule() 函数接在一起
  • (3)修改 fork()

现在不使用 TSS 进行切换,而是采用切换内核栈的方式来完成进程切换,所以在新的 switch_to 中将用到当前进程的 PCB、目标进程的 PCB、当前进程的内核栈、目标进程的内核栈等信息(内核栈中记录了用户栈和用户代码两部分内容;PCB中记录了进程相关信息,如进程状态,PID,I/O等)。

Linux 0.11 进程的内核栈和该进程的 PCB 在同一页内存上(一块 4KB 大小的内存),其中 PCB 位于这页内存的低地址,栈位于这页内存的高地址;另外,由于当前进程的 PCB 是用一个全局变量 current 指向的,所以只要告诉新 switch_to()函数一个指向目标进程 PCB 的指针就可以了。同时还要将 next 也传递进去,虽然 TSS(next)不再需要了,但是 LDT(next)仍然是需要的,也就是说,现在每个进程不用有自己的 TSS 了,因为已经不采用 TSS 进程切换了,但是每个进程需要有自己的 LDT,地址分离地址还是必须要有的,而进程切换必然要涉及到 LDT 的切换。(整个系统中一个处理器只有一个GDT(全局描述符),每个程序对应一个LDT(局部描述符),包含其代码、数据、堆栈等)

8.1.1修改switch_to汇编代码

把原有的switch_to代码注释

我们的目的是不使用TSS而是使用内核栈完成进程的切换,应该在 switch_to 中完成PCB、内核栈的切换。首先修改 kernel/system_call.s 中的 switch_to 这段汇编代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
switch_to:
// 因为该汇编函数在c语言中调用,所以需要手动处理栈帧
pushl %ebp
movl %esp,%ebp
pushl %ecx
pushl %ebx
pushl %eax
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

1:
popl %eax
popl %ebx
popl %ecx
popl %ebp
ret

switch_to这段代码在 schedule 函数中进行调用,首先将当前ebp指向的帧指针地址压入内核栈,之后将当前esp指向的地址赋值给帧指针,此时ebp指向的内存地址保存的是上一个帧指针的位置

接下来进行了三次压栈操作,分别将三个寄存器的值保存到内核栈中

1
2
pushl %ebp     movl  %esp,%ebp
pushl %ecx pushl %ebc pushl %eax

第一行将ebp+8位置的值放到寄存器ebx中,然后对比ebx和全局变量current的值,如果相同则是同一进程,直接跳出该部分代码(下图第1列)

第二行代码实现了ebx -> eax, eax和current交换,也就是此时ebx和current都指向下一进程的PCB,eax指向当前进程的pcb(下图第2列)

第三行,虽然现在不使用TSS进行进程切换,但这种中断机制还需要保持,我们在 sched.c 中定义了全变量 struct tss_struct *tss=&(init_task.task.tss) ,也就是0号进程的TSS,所有进程共用这个TSS(下图第3列)

ebx指向PCB地址,Linux0.11中进程的内核栈和PCB放在一块大小为4K的内存段中,高地址开始是内核栈,低地址开始是PCB,所以ebx+4096实际上就是内核栈的地址,其中 ESP0=4 ,因为TSS中内核栈指针esp0就放在偏移为4的地方,也就是我们将内核栈的地址赋给了TSS中的内核栈地址,实现了内核栈指针的重写

1
2
3
movl  8(%ebp),%ebx      cmpl  %ebx,current      je   1f
movl %ebx,%eax xchgl %eax,current
movl tss,%ecx addl $4096,%ebx movl %ebx,ESP0(%ecx)
1
2
3
4
5
6
/* linux/sched.h */
struct tss_struct {
long back_link;
long esp0;
/* ...... */
}

第一行完成了内核栈的切换。首先将当前进程esp保存到当前PCB的kernelstack中。此时ebx保存的是下一进程内核栈的地址,应该改成PCB地址,所以重新取ebp+8的位置放入ebx寄存器。接下来将ebx寄存器中保存的kernelstack地址读入esp寄存器,实现内核栈esp的切换,所以这里也需要在 sched.h 中增加一个 kernelstack 变量``

第二行完成了LDT的切换。将下一进程的内核栈地址送入%ecx,加载LDT局部描述符等。

1
2
movl %esp,KERNEL_STACK(%eax)  movl 8(%ebp),%ebx  movl KERNEL_STACK(%ebx),%esp
movl 12(%ebp),%ecx lldt %cx movl $0x17,%ecx mov %cx,%fs
1
2
3
4
5
6
7
8
/* linux/sched.h */
struct task_struct {
long state;
long counter;
long priority;
long kernelstack; // 需要增加变量
/* ...... */
}

至此 switch_to 汇编代码全部写完,我们需要给他添加全局标识符以及定义用到的变量

因为PCB结构增加了kernelstack,所以0号进程的PCB初始化时也应该改变,以及信号量对应的位置需要改变

由于PCB结构体发生变化,所以0号进程初始化的时候也需要相应做出改变

8.1.2 修改fork.c代码

我们修改完swtich_to汇编代码实际上实现了内核级线程的切换,同样我们创建线程的时候也需要构造出相同的样子。第一段代码是sys_fork系统调用函数,下面是fork.c中copy_process()函数的完整代码,调用了一个汇编函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
sys_fork:
call find_empty_process
testl %eax,%eax
js 1f
push %gs
pushl %esi
pushl %edi
pushl %ebp
pushl %eax
call copy_process
addl $20,%esp
1: ret

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 添加外部声明, 这里使用了一段汇编来实现弹出栈信息到寄存器
extern long first_return_from_kernel(void);

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();

if (!p)
return -EAGAIN;
task[nr] = p;

*p = *current; /* NOTE! this doesn't copy the supervisor stack */
p->state = TASK_UNINTERRUPTIBLE;
p->pid = last_pid;
p->father = current->pid;
p->counter = p->priority;
p->signal = 0;
p->alarm = 0;
p->leader = 0; /* process leadership doesn't inherit */
p->utime = p->stime = 0;
p->cutime = p->cstime = 0;
p->start_time = jiffies;

// 初始化内核栈
long* krnstack;
// 这里PAGE_SIZE是4096, p是PCB的地址,PCB地址加上4096就是内核栈地址
krnstack = (long*) (PAGE_SIZE + (long)p);

// ss和sp等都是 copy_process() 函数的参数,来自父进程内核栈
*(--krnstack) = ss & 0xffff;
*(--krnstack) = esp;
*(--krnstack) = eflags;
*(--krnstack) = cs & 0xffff;
*(--krnstack) = eip;

// “内核级线程切换五段论”中的最后一段切换,即完成用户栈和用户代码的切换
// 依靠的核心指令就是 iret,回到用户态程序,当然在切换之前应该恢复一下执行现场,主要就是
// eax,ebx,ecx,edx,esi,edi,gs,fs,es,ds 等寄存器的恢复.
*(--krnstack) = ds & 0xffff;
*(--krnstack) = es & 0xffff;
*(--krnstack) = fs & 0xffff;
*(--krnstack) = gs & 0xffff;
*(--krnstack) = esi;
*(--krnstack) = edi;
*(--krnstack) = edx;

// 处理 switch_to 返回,即结束后 ret 指令要用到的,ret 指令默认弹出一个 EIP 操作
*(--krnstack) = (long)first_return_from_kernel;

// swtich_to 函数中的 “切换内核栈” 后的弹栈操作
*(--krnstack) = ebp;
*(--krnstack) = ecx;
*(--krnstack) = ebx;
*(--krnstack) = 0;

// 存放在 PCB 中的内核栈指针 指向 初始化完成时内核栈的栈顶
p->kernelstack = krnstack;
if (last_task_used_math == current)
__asm__("clts ; fnsave %0"::"m" (p->tss.i387));
if (copy_mem(nr,p)) {
task[nr] = NULL;
free_page((long) p);
return -EAGAIN;
}
for (i=0; i<NR_OPEN;i++)
if ((f=p->filp[i]))
f->f_count++;
if (current->pwd)
current->pwd->i_count++;
if (current->root)
current->root->i_count++;
if (current->executable)
current->executable->i_count++;
set_tss_desc(gdt+(nr<<1)+FIRST_TSS_ENTRY,&(p->tss));
set_ldt_desc(gdt+(nr<<1)+FIRST_LDT_ENTRY,&(p->ldt));
p->state = TASK_RUNNING; /* do this last, just in case */
return last_pid;
}

8.1.3 修改sched.c函数

我们已经完成了关键的switch_to汇编代码编写,使得系统可以不使用TSS而是用内核级线程切换;同时我们也完成了fork.c函数的修改,使得我们创建的内核级线程对应了我们switch_to需要的样子。

最后我们对sched.c进行修改,首先声明外部函数switch_to,需要传入当前PCB地址以及LDT地址,然后声明我们在switch_to中需要的全局变量tss地址,最后修改schedule函数中的句子。