Menu

二状态进程模型

发表于 06 May 2019 总计 12025字 阅读时间 41分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

实验题目

二状态进程模型

实验目的

  1. 学习进程模型知识，掌握进程模型的实现方法。
  2. 利用时钟中断，设计时钟中断处理进行进程交替执行
  3. 扩展 MyOS，实现多进程模型的原型操作系统。

实验内容

在实验五的基础上，进化你的原型操作系统，原型保留原有特征的基础上，设计满足下列要求的新原型操作系统：

  1. 内核实现简单进程模型，进程具有就绪、运行两种基本状态。建议在 c 程序中定义进程表，进程数量最多 4 个。
  2. 内核可以一次性加载最多 4 个用户程序。用户进程采用时间片轮转调度进程。由你设计有个性的用户程序，它们的输出各占 1/4 屏幕区域，信息输出有动感，以便观察程序是否在执行。
  3. 在原型中保证原有的系统调用服务可用。再编写 4 个用户程序，展示系统调用服务还能工作。

实验方案

实验环境

软件

  • Windows 10, 64-bit (Build 17763) 10.0.17763
  • Windows Subsystem for Linux [Ubuntu 18.04.2 LTS]：WSL 是以软件的形式运行在 Windows 下的 Linux 子系统，是近些年微软推出来的新工具，可以在 Windows 系统上原生运行 Linux。
  • gcc version 7.3.0 (Ubuntu 7.3.0-27ubuntu1~18.04)：C 语言程序编译器，Ubuntu 自带。
  • NASM version 2.13.02：汇编程序编译器，通过sudo apt install nasm安装在 WSL 上。
  • Oracle VM VirtualBox 6.0.6 r130049 (Qt5.6.2)：轻量开源的虚拟机软件。
  • VSCode - Insiders v1.33.0：好用的文本编辑器，有丰富的插件。
  • hexdump for VSCode 1.7.2: VSCode 中一个好用的十六进制显示插件。
  • GNU Make 4.1：安装在 Ubuntu 下，一键编译并连接代码，生成最终的文件。

大部分开发环境安装在 WSL 上，较之于双系统、虚拟机等其他开发方案，更加方便，也方便直接使用 Linux 下的一些指令。

硬件

开发环境配置

所用机器型号为 VAIO Z Flip 2016

  • Intel(R) Core(TM) i7-6567U CPU @3.30GHZ 3.31GHz
  • 8.00GB RAM
虚拟机配置
  • 处理器内核总数：1
  • RAM：4MB

实验原理

时钟中断响应后，保存当前进程 A 的寄存器状态；寻找下一个进程 B ；还原进程 B 的寄存器状态。

设计进程控制块和schedule过程

首先要明确：需要保存多少个寄存器。

8086 计算机有以下寄存器：

  • 指令指针寄存器：ip
  • 段寄存器：cs, es, ds, ss
  • 主寄存器：di, si, bp, sp, ax, bx, cx, dx
  • 标志寄存器

我使用如下的 C 语言代码来作为进程控制和调度的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define SCHEDULE_QUEUE_LEN 9
#define NEW 0
#define RUNNING 1
struct PCB
{
	int ip, cs, es, ds, ss, di, si, bp, sp, ax, bx, cx, dx, flags, pid;
} q[SCHEDULE_QUEUE_LEN], *qb = q, *qe = q + 1;
int statues[SCHEDULE_QUEUE_LEN] = {RUNNING, NEW}, pidStack[SCHEDULE_QUEUE_LEN], *top = pidStack;
void schedule()
{
	do
		if (++qb == q + SCHEDULE_QUEUE_LEN)
			qb = q;
	while (statues[qb->pid] != RUNNING);
	if (++qe == q + SCHEDULE_QUEUE_LEN)
		qe = q;
}

在老师给我们的原型中是为每个程序创建一张表，这样做的缺点有两个：一个是每个程序至多只能同时运行一个；另一个是在调度时如果只加载了少数进程，也仍然需要遍历检查所有的程序，会拖慢操作系统运行的速度。因此我在这里实现了一个循环队列，每次保存进程时写入队尾，进程恢复时从队首取一个「有效」的进程块即可。所谓「有效」将在下面「关闭进程」中解释。

这里使用 0 号 pid 代表内核进程。

创建进程

首先创建进程控制块，将cs,ds等寄存器设置为合适的值，然后设置该进程为「就绪」状态。考虑到进程结束后应返回内核并将该进程的statues属性设置为NEW，操作系统应事先在其用户栈内写入返回cs和返回ip。用户程序返回内核后，将alive属性设置为 0，死循环等待时钟中断发生。时钟中断发生后，该进程结束，下一次时间片轮转将不再轮到它。

我实现了一个栈用来分配当前进程的 pid，即当前进程的标识。这样做的好处和上面使用循环队列的好处一样，可以减少分配时候的空转问题。此外，当栈为空的时候，我的操作系统可以重新分配 pid，从而实现杀进程的效果，防止进程资源被用户程序过多占用而不能新开进程。当然，0 号 pid 代表操作系统内核，因此不会被重新分配。

关闭进程

我这里使用了伪关闭的方法，不是直接将进程的控制块移出队列，而是先在状态表中将其置为关闭，等待调度程序来判断当前进程队列首的进程是否已被关闭，如果是的话直接出队检查下一个进程，直到找到一个有效的进程。由于内核进程是不可以被杀死的，因此进程队列永远不为空。

1

statues[pid] = NEW, *++top = pid;

关闭进程时将其pid重新压回栈中，供下一次创建进程时分配。

当然，在当前版本的内核中检测键盘中断没有用多进程实现，因此在多进程运行的时候实际上是没有办法退回到内核的，也就是说这个关闭进程的功能虽然实现是正确的，但是暂时没办法去测试。等待后续版本实现多进程响应键盘中断之后吧。

save和restart过程

中断发生时，由 CPU 将标志寄存器flags、代码段寄存器cs、指令指针寄存器ip依次压入堆栈（被中断的程序的堆栈）；中断返回时（即执行iret指令时），CPU 将堆栈中的指令指针寄存器ip、代码段寄存器cs、标志寄存器flags依次弹出堆栈，并转到CS:IP继续原程序的执行。照着文档，我读懂了老师提供的「现场保护」：save过程（旧版）代码和现场恢复restart过 程（旧版）代码。我计划schedule过程由 C 实现，故save过程只需将寄存器保存在外部变量（C 语言的变量）， 然后restore过程需要将外部变量还原到寄存器中。如此安排，schedule过程要做的事情是：将 C 语言的变量保存到 A 进程控制块中，然后调度另一进程 B，将B进程控制块中的寄存器写入 C 语言的变量。

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

	call save
	pusha
	push ds
	push es

	push 0
	call schedule
restart:
	pop es
	pop ds
	popa

	mov si,[qb]
	mov es,word[si+12];es
	mov ss,word[si+20];ss
	mov ax,word[si+24];ax
	mov bx,word[si+28];bx
	mov cx,word[si+32];cx
	mov dx,word[si+36];dx
	mov di,word[si+40];di
	mov bp,word[si+44];bp
	mov sp,word[si+48];sp

	push word[si+8]
	push word[si+4]
	push word[si]

	push word[si+52]
	push word[si+16];ds
	pop ds
	pop si

	push ax
	mov al,20h
	out 20h,al
	out 0A0h,al
	pop ax
	iret
save:
	push ds
	push cs
	pop ds
	pop word[save_ds]
	pop word[save_cs]

	mov word[save_si],si
	mov si,word[qe]

	pop word [si]
	pop word [si+4]
	pop word [si+8]

	mov word [si+12],es
	push word [save_ds]
	pop word [si+16]

	mov word[si+20],ss
	mov word[si+24],ax
	mov word[si+28],bx
	mov word[si+32],cx
	mov word[si+36],dx
	mov word[si+40],di
	mov word[si+44],bp
	mov word[si+48],sp
	push word[save_pid]
	push word[save_si]
	pop word[si+52]
	pop word[si+56]
	jmp word[save_cs]

这里保存变量直接保存在 C 代码中的队尾qe，并在调度后从 C 代码中的队首qb中取出变量恢复即可。

实验过程

实验代码

bootloader.asm

和上一个实验中的代码完全相同，不再放出。

kernel.asm

实现系统中断和时钟中断。

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

%macro setIVT 2
	push es
	push ds
	push si
	pusha
	xor ax, ax
	mov es, ax
	mov ax, %1
	mov bx, 4
	mul bx
	mov si, ax
	mov ax, %2
	mov [es:si], ax
	add si, 2
	mov ax, cs
	mov [es:si], ax
	popa
	pop si
	pop ds
	pop es
%endmacro
	bits 16
	extern qb,qe,schedule,terminal,prgCall
	global _start
_start:
	setIVT 33,int33
	setIVT 8,int8
	push 0
	call terminal
	ret
int8:
	cli
	call save
	pusha
	push ds
	push es

	push 0
	call schedule
restart:
	pop es
	pop ds
	popa

	mov si,[qb]
	mov es,word[si+12];es
	mov ss,word[si+20];ss
	mov ax,word[si+24];ax
	mov bx,word[si+28];bx
	mov cx,word[si+32];cx
	mov dx,word[si+36];dx
	mov di,word[si+40];di
	mov bp,word[si+44];bp
	mov sp,word[si+48];sp

	push word[si+8]
	push word[si+4]
	push word[si]

	push word[si+52]
	push word[si+16];ds
	pop ds
	pop si

	push ax
	mov al,20h
	out 20h,al
	out 0A0h,al
	pop ax
	sti
	iret
save:
	push ds
	push cs
	pop ds
	pop word[save_ds]
	pop word[save_cs]

	mov word[save_si],si
	mov si,word[qe]

	pop word [si]
	pop word [si+4]
	pop word [si+8]

	mov word [si+12],es
	push word [save_ds]
	pop word [si+16]

	mov word[si+20],ss
	mov word[si+24],ax
	mov word[si+28],bx
	mov word[si+32],cx
	mov word[si+36],dx
	mov word[si+40],di
	mov word[si+44],bp
	mov word[si+48],sp
	push word[save_pid]
	push word[save_si]
	pop word[si+52]
	pop word[si+56]
	jmp word[save_cs]

int33:
	cli
	mov al,ah
	xor ah,ah
	push eax
	push 0
	call prgCall
	pop eax
	sti
	iret
datadef:
	save_cs dw 0
	save_si dw 0
	save_ds dw 0
	save_pid dw 0

kernel.c

实现二状态进程调度功能，前面已经解释过了。

此外，修复了滚屏的时候有时会出现灰屏的问题（忘记给bh寄存器赋值了）。 

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

#define SCREEN_WIDTH 80
#define SCREEN_HEIGHT 25
#define BUF_LEN (SCREEN_WIDTH * SCREEN_HEIGHT)
#define PROGRAM_NUM 4
#define SCHEDULE_QUEUE_LEN 5
#define NEW 0
#define RUNNING 1
struct PCB
{
	int ip, cs, es, ds, ss, di, si, bp, sp, ax, bx, cx, dx, flags, pid;
} q[SCHEDULE_QUEUE_LEN], *qb = q, *qe = q + 1;
int statues[SCHEDULE_QUEUE_LEN] = {RUNNING, NEW}, pidStack[SCHEDULE_QUEUE_LEN], *top = pidStack;
void schedule()
{
	do
		if (++qb == q + SCHEDULE_QUEUE_LEN)
			qb = q;
	while (statues[qb->pid] != RUNNING);
	if (++qe == q + SCHEDULE_QUEUE_LEN)
		qe = q;
}
const struct
{
	const char *name, *size, *command;
	int address;
} prg[PROGRAM_NUM] =
	{{"prg1", "    156 bytes", "prg1", 1},
	 {"prg2", "    158 bytes", "prg2", 2},
	 {"prg3", "    168 bytes", "prg3", 3},
	 {"prg4", "    174 bytes", "prg4", 4}};
void loadProgram(int PrgSectorOffset, int UserPrgOffset)
{
	asm("int 0x13"
		:
		: "a"(2 << 8 | 1), "b"(UserPrgOffset), "c"(PrgSectorOffset), "d"(1 << 8));
}
void call(int UserPrgOffset)
{
	asm("call bx"
		:
		: "b"(UserPrgOffset));
}
void prgCall(int i)
{
	loadProgram(prg[i].address, 0x0a100 + i * 0x100), call(0x0a100 + i * 0x100);
}
int getCursor()
{
	int p;
	asm("int 0x10"
		: "=d"(p)
		: "a"(0x0300), "b"(0));
	return p;
}
void setCursor(int pos)
{
	asm("int 0x10"
		:
		: "a"(0x0200), "b"(0), "d"(pos));
}
void pageUP(int p)
{
	asm("push bx\n"
		"mov bh,0\n"
		"int 0x10\n"
		"pop bx\n"
		:
		: "a"(1536 + p), "c"(0), "d"(0x184F));
}
void putC(int ch, int color)
{
	asm("int 0x10"
		:
		: "a"(9 << 8 | ch), "b"(color), "c"(1));
}
int getch()
{
	int ch;
	asm("getch_loop:\n"
		"mov ah, 0x01\n"
		"int 0x16\n"
		"jz getch_loop\n"
		"mov ah, 0x00\n"
		"int 0x16\n"
		"xor ah, ah\n"
		: "=a"(ch)
		:);
	return ch;
}
void putchar(char c)
{
	int cur = getCursor(), curX = cur >> 8, curY = cur - (curX << 8);
	if (c == '\r' || c == '\n')
	{
		if (++curX >= SCREEN_HEIGHT)
			--curX, pageUP(1);
		return setCursor(curX << 8);
	}
	putC(c, 0x07);
	if (++curY >= SCREEN_WIDTH)
		putchar('\n');
	else
		setCursor(curX << 8 | curY);
}
void gets(char *s)
{
	for (;; ++s)
	{
		putchar(*s = getch());
		if (*s == '\r' || *s == '\n')
			break;
	}
	*s = 0;
}
void printf(const char *s)
{
	for (; *s; ++s)
		putchar(*s);
}
int strcmp(const char *s1, const char *s2)
{
	while (*s1 && (*s1 == *s2))
		++s1, ++s2;
	return (int)*s1 - (int)*s2;
}
void terminal()
{
	char str[BUF_LEN] = "$ ";
	printf(str), gets(str);
	const char
		*CLEAR_COM = "clear",
		*HELP_COM = "help",
		*EXEC_COM = "exec",
		*EXECPRO_COM = "execpro",
		*EXIT_COM = "exit",
		*KILL_COM = "kill",
		*LS_COM = "ls",
		*PS_COM = "ps";
	if (!strcmp(str, CLEAR_COM))
		pageUP(SCREEN_HEIGHT), setCursor(0);
	else if (!strcmp(str, HELP_COM))
	{
		const char
			*HELP_INFO =
				"WuK-shell v0.0.3\n"
				"These shell commands are defined internally.\n"
				"Command         Description\n"
				"clear        -- Clean the screen\n"
				"help         -- Show this list\n"
				"exec         -- Execute all the user programs\n"
				"execpro      -- Execute all the user programs by mutiprocess\n"
				"exit         -- Exit OS\n"
				"kill         -- kill process\n"
				"ls           -- Show existing programs\n"
				"prg[num]     -- Execute the num-th program\n"
				"ps           -- Show running programs with their pid\n";
		printf(HELP_INFO);
	}
	else if (!strcmp(str, EXEC_COM))
		for (int i = 0; i < PROGRAM_NUM; ++i)
			prgCall(i);
	else if (!strcmp(str, EXECPRO_COM))
		for (int i = 0; i < PROGRAM_NUM; ++i)
		{
			if (top == pidStack)
				for (int j = 1; j < SCHEDULE_QUEUE_LEN; ++j)
					*++top = j;

			qe->flags = 512;
			qe->ip = 0x000;
			qe->sp = qe->ip - 8;
			qe->ss = qe->es = qe->ds = qe->cs = 0xa100 + i * 0x100;

			loadProgram(prg[i].address, 0x0a100 + i * 0x100);
			statues[qe->pid = *(top--)] = RUNNING;
			if (++qe == q + SCHEDULE_QUEUE_LEN)
				qe = q;
		}
	else if (!strcmp(str, EXIT_COM))
		return pageUP(SCREEN_HEIGHT);
	else if (!strcmp(str, KILL_COM))
	{
		const char *INFO = "Input the pid to kill: ";
		printf(INFO);
		gets(str);
		int pid = str[0] - '0';
		if (pid <= 0)
		{
			const char *INFO = "Can not kill process 0.\n";
			printf(INFO);
		}
		else if (pid >= SCHEDULE_QUEUE_LEN || statues[pid] != RUNNING)
		{
			const char *INFO = "Invalid pid.\n";
			printf(INFO);
		}
		else
			statues[pid] = NEW, *++top = pid;
	}
	else if (!strcmp(str, LS_COM))
		for (int i = 0; i < PROGRAM_NUM; ++i)
			printf(prg[i].name), printf(prg[i].size), putchar('\n');
	else if (!strcmp(str, PS_COM))
	{
		const char
			*INFO = "pid statues\n",
			*RUNNING_INFO = "   RUNNING\n",
			*NEW_INFO = "   NEW\n";
		printf(INFO);
		for (int i = 0; i < SCHEDULE_QUEUE_LEN; ++i)
		{
			putchar('0' + i);
			printf(statues[i] == RUNNING ? RUNNING_INFO : NEW_INFO);
		}
	}
	else
		for (int i = 0;; ++i)
		{
			if (i == PROGRAM_NUM)
			{
				printf(str);
				const char
					*COMM_NOT_FOUND =
						" : command not found, type \'help\' for available commands list.\n";
				printf(COMM_NOT_FOUND);
				break;
			}
			if (!strcmp(str, prg[i].command))
			{
				asm("int 33" ::"a"(i << 8));
				break;
			}
		}
	terminal();
}

link.ld

将wukos.asm和kernel.c两个文件编译出来的内容连接起来。和上一个实验中的完全相同，不再放出。

prg1.asm~prg4.asm

由于多进程调用时会同时访问变量，因此每个用户程序需要重新维护自己的运行变量，而不能像之前一样通过系统调用提供唯一个入口了。

这里在实验二中实现的用户程序上修改、完善一下。

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

%macro print 5 ; string, length, x, y, color
	pusha
	push ax
	push bx
	push cx
	push dx
	push bp
	push ds
	push es
	mov ax, 0b800H
	mov gs, ax
	mov ax, cs
	mov ds, ax
	mov bp, %1
	mov ax, ds
	mov es, ax
	mov cx, %2
	mov ax, 1300H
	mov dh, %3
	mov dl, %4
	mov bx, %5
	int 10H
	pop es
	pop ds
	pop bp
	pop dx
	pop cx
	pop bx
	pop ax
	popa
%endmacro
N equ 12	;显示区域高度
M equ 32	;显示区域宽度减去字符串长度
TOP equ 2	;显示区域上端点
LEFT equ 40	;显示区域左端点
LENGTH equ 8	;字符串的长度
DELAY equ 99999999
org 0A100h
myLoop:
	dec dword[count]	; 递减计数变量
	jnz myLoop	; >0：跳转
	mov dword[count], DELAY

	mov word ax, [t]	; ax = t
	mov word bx,2*N-2
	xor dx, dx	; clear dx and prepare for division
	div bx  ; dx = t mod (2N - 2)
	cmp dx, N ; compare dx and n
	jb xok  ; if (dx < n) jump xok
	sub bx, dx
	mov dx, bx ; dx = 2n - 2 - dx
xok:
	mov word[x], dx
	add word[x], TOP

	mov word ax, [t]
	mov word bx, 2*M-2
	xor dx, dx
	div bx
	cmp dx, M
	jb yok
	sub bx, dx
	mov dx, bx
yok:
	mov word [y],dx
	add word [y],LEFT

	print message,LENGTH,[x],[y],07H
	inc word[t]
	mov word ax,[t]
	cmp ax, 63
	jne myLoop
	ret
datadef:
	count dd 1
	t dw 0
	x dw 1
	y dw 0
	message db ' wu-kan '

上面是 prg1.asm 的内容，其余同理，不再放出。

Makefile

和上一个实验完全相同，不再放出。

运行结果

输入prg4，通过系统中断打开一个用户程序。可以看到系统中断服务仍然可以工作。

1

输入ps，显示当前进程的状态。当前只有一个进程，即内核，在运行。

2

输入kill后输入0，杀掉 pid 为 0 的内核。可以看到无法杀掉内核进程。

3

输入execpro，多进程的打开四个用户程序。可以看到，成功文体四开花了，而且四个象限的运行速度不一样。

4

实验总结

这次实验让我深入了解了多进程时间片轮转的工作原理。原理很简单，就是save,schedule和restart，但实现起来可不简单。

在save过程和restart过程中，最容易出错是栈。当前栈内元素是什么，这个一定要非常清楚。当使用call操作和ret操作时，会修改堆栈。所以应尽量避免使用call和ret操作，避免出错。另外，ss和sp的保存时机也是非常关键的。ss和sp必须在最后保存，这样做是为了保存弹出flags,cs,ip之后的栈指针。

在schedule过程中，更容易在栈的问题上出错。schedule的栈要与kernel的栈以及用户程序的栈都不一样，否则会覆盖原有的数据。一旦踩进这个坑，就很难跳出来，因为你会发现寄存器之类的全部都是对的，只有栈内元素是错的。

另外在汇编代码调用 C 函数之前要push 0，传参数的时候也有很多细节，感谢我的室友添伦大哥对我的帮助！