OS-Lab4-challenge

实现思路

实现线程运行与信号量机制的一个基础就是正确定义好线程控制块(TCB)与信号量(sem)结构,然后其他所有的函数都围绕这两个数据结构中的对应内容进行编写。

下述以部分重点内容为例，结合代码分析所做的工作

1.include/env.h

（1）定义线程，信号量相关宏

1
2
3
4
5
6
7
8
9
例如：
#define THREAD_MAX	8
#define THREAD_CAN_BE_CANCELED 		1
#define THREAD_CANNOT_BE_CANCELED	0
#define THREAD_CANCEL_IMI		0
#define THREAD_CANCEL_POINT		1

#define SEM_FREE	0
#define SEM_VALID	1

（2）定义线程控制块与信号量的结构

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
线程控制块的编写主要依据是我们要实现的四个线程功能：创建、终止、撤销和阻塞至线程结束，依据这四个要实现的功能定义我们的线程控制块。
struct Tcb {
	// 基础信息
	struct Trapframe tcb_tf;
	u_int thread_id;
	u_int tcb_status;
	u_int tcb_pri;

	// 阻塞相关信息
	LIST_ENTRY(Tcb) tcb_sched_link;
	LIST_ENTRY(Tcb) tcb_joined_link;
	LIST_HEAD(Tcb_joined_list,Tcb);
	struct Tcb_joined_list tcb_joined_list;
	void **tcb_join_value_ptr;
	u_int tcb_detach;

	// 线程终止
	void *tcb_exit_ptr;
	int tcb_exit_value;

	// 撤销线程
	int tcb_cancelstate;
	int tcb_canceltype;
	u_int tcb_canceled;

	// 留白
	u_int tcb_nop[10];
};

其中需要特别注意的部分就是`tcb_nop`这个变量。这个变量在实际的线程控制中不起到任何作用，添加这个变量是为了页对齐。在我们的设计中，一个线程最多可以创建8个线程，设计上我们让一个进程控制块占据一个页表大小(4KB)，一个线程控制块占据256B。这样的设计让我们在之后创建线程号以及分配线程栈的时候有很多的方便之处。为了达到这个大小要求，我们在线程控制块和进程控制块中均进行了留白。

线程中的留白
struct Env {
    ......
	// 留白
	u_int env_nop[496];

	// 线程控制块
	struct Tcb env_threads[8];
};

信号量的整个结构体相较线程较为简单，没有特别的难点。使用以下结构体便可以实现信号量的初始化、销毁、阻塞P操作、非阻塞P操作、V操作和取值。这里不过多叙述。
struct sem {
	u_int sem_envid;
	u_int sem_head_index;
	u_int sem_tail_index;
	char sem_name[16];
	int sem_value;
	int sem_status;
	int sem_shared;
	int sem_wait_count;
	struct Tcb *sem_wait_list[10];
};

（3）定义实现线程与信号量机制的相关函数与数据结构

1
2
3
4
5
类似于进程的创建，线程也需要一些全局的变量去控制。
LIST_HEAD(Tcb_list, Tcb);
extern struct Tcb *curtcb;
extern struct Tcb_list tcb_sched_list[2];
int thread_alloc(struct Env *e, struct Tcb **t);

（4）修改引入线程信号量前体系下的逻辑冲突

1
2
3
在挑战性任务的实现中，任何任务的运行都是以线程为单位的，所以很多如下的函数都要修改：
struct env的定义
void env_run(struct Tcb *e)的定义

2.include/error.h

定义线程与信号量机制相关的错误

1
2
3
4
5
6
7
8
9
#define E_THREAD_MAX	13
#define E_THREAD_NOTFOUND 14
#define E_THREAD_CANNOTCANCEL 15

#define E_SEM_ERROR	16
#define E_SEM_NOTFOUND	17
#define E_SEM_EAGAIN	18

#define MAXERROR 18

3.lib/env.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1.新函数的实现
u_int mktcbid(struct Tcb *t)
int threadid2tcb(u_int threadid, struct Tcb **ptcb)
int thread_alloc(struct Env *e, struct Tcb **new)
void thread_free(struct Tcb *t) 
void thread_destroy(struct Tcb *t) 

2.修改新体系下的逻辑冲突
int envid2env(u_int envid, struct Env **penv, int checkperm)
int env_alloc(struct Env **new, u_int parent_id)
static void load_icode(struct Env *e, u_char *binary, u_int size)
void env_create_priority(u_char *binary, int size, int priority)
void env_create(u_char *binary, int size)
void env_free(struct Env *e)
void env_destroy(struct Env *e)
void env_run(struct Tcb *t)

重点函数解析：

（1）创建进程的ID

如前文所说，一个进程控制块占据一页的大小，可以容纳8个线程控制块，所以这里可以直接根据偏移量来生成线程的控制号。

1
2
3
4
5
u_int mktcbid(struct Tcb *t) {
	struct Env *e = ROUNDDOWN(t,BY2PG);
	u_int tcb_no = ((u_int)t - (u_int)e - BY2PG/2)/(BY2PG/16);
	return ((e->env_id << 3) | tcb_no);
}

（2）创建线程

这个函数其实就是将之前env_alloc函数初始化的东西移入了线程的创建，因为现在运行的最小单位变成了线程 。下面列出来的部分是线程控制块的选择逻辑。我们会从上一次创建线程的位置开始往下找，直到找到一个可用的空间，这样可以让每一个存储位置都有机会被使用。省略号部分是初始化内容。

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
int thread_alloc(struct Env *e, struct Tcb **new) {
	if (e->env_thread_count >= THREAD_MAX) 
		return E_THREAD_MAX;
	u_int thread_no = e->env_thread_count;
	u_int i = 0;
	while (e->env_threads[thread_no].tcb_status != ENV_FREE) {
		++thread_no;
		thread_no = thread_no % THREAD_MAX;
		++i; 
		if (i >= THREAD_MAX)
			return E_THREAD_MAX;
	}
	++(e->env_thread_count);
	struct Tcb *t = &e->env_threads[thread_no];
	t->thread_id = mktcbid(t);
	printf("thread id is 2'b%b\n",t->thread_id);
	t->tcb_status = ENV_RUNNABLE;
	t->tcb_tf.cp0_status = 0x10001004;
	t->tcb_exit_ptr = (void *)0;
	t->tcb_tf.regs[29] = USTACKTOP - 4*BY2PG*(t->thread_id & 0x7);
	t->tcb_cancelstate = THREAD_CANNOT_BE_CANCELED;
	t->tcb_canceltype = THREAD_CANCEL_IMI;
	t->tcb_canceled = 0;
	t->tcb_exit_value = 0;
	t->tcb_exit_ptr = (void *)&t->tcb_exit_value;
	t->tcb_detach = 0;
	LIST_INIT(&t->tcb_joined_list);
	*new = t;
	return 0;
}

（3）线程的销毁

类似于进程的销毁，在进行时钟中断的时候要将当前的 KERNEL_SP 内容拷贝到 TIMESTACK 中，并且当一个进程的所有线程都被销毁后要将这个进程控制块释放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void thread_free(struct Tcb *t) 
{
	struct Env *e = ROUNDDOWN(t,BY2PG);
	printf("[%08x] free tcb %08x\n", e->env_id, t->thread_id);
	--e->env_thread_count;
	if (e->env_thread_count <= 0) {
		env_free(e);
	}
	t->tcb_status = ENV_FREE;
}

void thread_destroy(struct Tcb *t) {
	if (t->tcb_status == ENV_RUNNABLE)
		LIST_REMOVE(t,tcb_sched_link);
	thread_free(t);
	if (curtcb == t) {
		curtcb = NULL;
		bcopy((void *)KERNEL_SP - sizeof(struct Trapframe),
			(void *)TIMESTACK - sizeof(struct Trapframe),
			sizeof(struct Trapframe));
		printf("i am thread, i am killed ... \n");
		sched_yield();
	}
}

4.lib/sched.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
以线程为单位进行调度
void sched_yield(void)
{
	static int times = 0;
	struct Env *e = curenv;
	struct Tcb *t = curtcb;
	static int sched_i = 0;
	if (!t) {
		while (LIST_EMPTY(&tcb_sched_list[sched_i])) {
			sched_i ^= 1;
		}
		t = LIST_FIRST(&tcb_sched_list[sched_i]);
		times = t->tcb_pri;
		times -= 1;
		env_run(t);
	} else if (t->tcb_status != ENV_RUNNABLE) {
		while (LIST_EMPTY(&tcb_sched_list[sched_i])) {
			sched_i ^= 1;
		}
		t = LIST_FIRST(&tcb_sched_list[sched_i]);
		times = t->tcb_pri;
		times -= 1;
		env_run(t);
	}
	if (times <= 0) {
		LIST_REMOVE(t,tcb_sched_link);
		LIST_INSERT_HEAD(&tcb_sched_list[sched_i^1],t,tcb_sched_link);
		while (LIST_EMPTY(&tcb_sched_list[sched_i])) {
			sched_i ^= 1;
		}
		t = LIST_FIRST(&tcb_sched_list[sched_i]);
		times = t->tcb_pri;
		times -= 1;
		env_run(t);
	} else {
		times -= 1;
		env_run(t);
	}
}

5.系统调用的新增与修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1.新增的系统调用
u_int sys_getthreadid(void)
int sys_thread_destroy(int sysno, u_int threadid)
int sys_thread_alloc(void)
int sys_set_thread_status(int sysno, u_int threadid, u_int status)
int sys_thread_join(int sysno, u_int threadid, void **value_ptr)

int sys_sem_destroy(int sysno,sem_t *sem)
int sys_sem_wait(int sysno,sem_t *sem)
int sys_sem_trywait(int sysno, sem_t *sem)
int sys_sem_post(int sysno, sem_t *sem)
int sys_sem_getvalue(int sysno, sem_t *sem, int *valp)

2.修改的系统调用
int sys_env_alloc(void)
int sys_set_env_status(int sysno, u_int envid, u_int status)
void sys_ipc_recv(int sysno, u_int dstva)
int sys_ipc_can_send(int sysno, u_int envid, u_int value, u_int srcva, u_int perm)

重点函数解析：

（1）设置线程的状态

进行这个系统调用可以改变线程的状态，这在线程的阻塞和调度中起到了十分重要的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int sys_set_env_status(int sysno, u_int envid, u_int status)
{
	// Your code here.
	struct Env *env;
	struct Tcb *tcb;
	int ret;

	if ((status != ENV_RUNNABLE)&&(status != ENV_NOT_RUNNABLE)&&(status != ENV_FREE))
		return -E_INVAL;
	ret = envid2env(envid,&env,0);
	tcb = &env->env_threads[0];
	if (ret < 0)
		return ret;
	if ((status == ENV_RUNNABLE)&&(tcb->tcb_status != ENV_RUNNABLE)) {
		LIST_INSERT_HEAD(tcb_sched_list,tcb,tcb_sched_link);	
	} else if((tcb->tcb_status == ENV_RUNNABLE)&&(status != ENV_RUNNABLE)) {
		LIST_REMOVE(tcb,tcb_sched_link);
	}
	env->env_threads[0].tcb_status = status;
	return 0;
	//	panic("sys_env_set_status not implemented");
}

（2）线程的阻塞等待

一个进程可以主动等待一个指定的线程完成后才继续往下执行。这个系统调用可以保证一些执行的顺序。

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
int sys_thread_join(int sysno, u_int threadid, void **value_ptr)
{
	struct Tcb *t;
	int r;
	//printf("here id is 0x%x\n",threadid);
	r = threadid2tcb(threadid,&t);
	//printf("find id is 0x%x\n",t->thread_id);
	if (r < 0)
		return r;
	if (t->tcb_detach) {
		return -E_THREAD_JOIN_FAIL;
	}
	if (t->tcb_status == ENV_FREE) {
		if (value_ptr != 0) {
			*value_ptr = t->tcb_exit_ptr;
		}
		return 0;
	}
	//printf("father id is 0x%x\n",t->thread_id);
	LIST_INSERT_HEAD(&t->tcb_joined_list,curtcb,tcb_joined_link);
	curtcb->tcb_join_value_ptr = value_ptr;
	sys_set_thread_status(0,curtcb->thread_id,ENV_NOT_RUNNABLE);
	struct Trapframe *trap = (struct Trapframe *)(KERNEL_SP - sizeof(struct Trapframe));
	trap->regs[2] = 0;
	trap->pc = trap->cp0_epc;
	sys_yield();
	return 0;
}

（3）信号量的P操作(阻塞和非阻塞)

当一个线程想要申请一个信号量的时候就会调用一下两个函数之一。如果是进行的阻塞申请，并且当前没有可用的信号量，那么信号量结构体就会将当前申请的进程加入到等待队列中。等待队列的实现逻辑本质上是一个循环列表，当超过最大等待上线的时候便会报错。

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
//阻塞
int sys_sem_wait(int sysno,sem_t *sem)
{
	if (sem->sem_status == SEM_FREE) {
		return -E_SEM_ERROR;
	}
	int i;
	if (sem->sem_value > 0) {
		--sem->sem_value;
		return 0;
	}
	if (sem->sem_wait_count >= 10) {
		return -E_SEM_ERROR;
	}
	sem->sem_wait_list[sem->sem_head_index] = curtcb;
	sem->sem_head_index = (sem->sem_head_index + 1) % 10;
	++sem->sem_wait_count;
	sys_set_thread_status(0,0,ENV_NOT_RUNNABLE);
	struct Trapframe *trap = (struct Trapframe *)(KERNEL_SP - sizeof(struct Trapframe));
	trap->regs[2] = 0;
	trap->pc = trap->cp0_epc;
	//printf("wait thread is 0x%x\n",curtcb->thread_id);
	sys_yield();
	return -E_SEM_ERROR;
}

//非阻塞
int sys_sem_trywait(int sysno, sem_t *sem)
{
	if (sem->sem_status == SEM_FREE) {
		return -E_SEM_ERROR;
	}
	if (sem->sem_value > 0) {
		--sem->sem_value;
		return 0;
	}
	return -E_SEM_EAGAIN;
}

（4）信号量的V操作

实现了基本的V操作，对当前有无等待进行了分别的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int sys_sem_post(int sysno, sem_t *sem)
{
	if (sem->sem_status == SEM_FREE) {
		return -E_SEM_ERROR;
	}
	if (sem->sem_value > 0) {
		++sem->sem_value;
	} else {
		if (sem->sem_wait_count == 0) {
			++sem->sem_value;
		}
		else {
			struct Tcb *t;
			--sem->sem_wait_count;
			t = sem->sem_wait_list[sem->sem_tail_index];
			sem->sem_wait_list[sem->sem_tail_index] = 0;
			sem->sem_tail_index = (sem->sem_tail_index + 1) % 10;
			sys_set_thread_status(0,t->thread_id,ENV_RUNNABLE);
		}
	}
	return 0;
}

6.用户态函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1.user/pthread.c
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void * (*start_rountine)(void *), void *arg)
void pthread_exit(void *value_ptr)
int pthread_setcancelstate(int state, int *oldvalue) 
int pthread_setcanceltype(int type, int *oldvalue) 
void pthread_testcancel() 
int pthread_cancel(pthread_t thread)
int pthread_detach(pthread_t thread)
int pthread_join(pthread_t thread, void **value_ptr)

2.user/sem.c
int sem_init(sem_t *sem,int shared,unsigned int value)
int sem_destroy(sem_t *sem)
int sem_wait(sem_t *sem) 
int sem_trywait(sem_t *sem)
int sem_post(sem_t *sem)
int sem_getvalue(sem_t *sem,int *valp)

遇到的困难及解决方案

1.线程控制块的位置及查找

我们采用了填充对齐的方法去布局线程和进程。这样实现简单，其次创建进程、线程的时候可以很快的生产ID，快速查找，并且空余的空间还可以添加未来可能的功能。这种结构比较适合OS课程这种小型操作系统，但是其缺点也很明显：空间浪费。如果还想要节约空间的话可能就需要使用链表之类的结构，但是那样实现繁琐，并且链表等操作速度肯定是慢于直接查找，所以没有采用链表的实现方式。

2.join阻塞的实现

join阻塞机制的实现利用了TCB结构体中的 Tcb_joined_list 的链表结构，利用链表储存被阻塞的线程ID，从而在线程结束时可以定位到被阻塞的进程，进行进程状态的恢复。

3.线程栈的实现

1
t->tcb_tf.regs[29] = USTACKTOP - 4*BY2PG*(t->thread_id & 0x7);

在上述语句中为每一个线程分配了不同的栈区，从而保证了不同线程中运行栈的地址不能重合，实现了同一进程的不同线程可以相互访问栈内数据。

OS
#OS
OS-Lab4-challenge
http://example.com/2022/07/17/OS-Lab4-challenge/
作者
Wei Xia
发布于
2022年7月17日
许可协议