BUAA-OS

「BUAA OS Lab3-1-Extra」模拟PV操作

Posted by saltyfishyjk on 2022-04-29
Words 3.1k and Reading Time 12 Minutes
Viewed Times

「BUAA OS Lab3-1-Extra」模拟PV操作

Part 0 前言

本篇博客记录Lab3-1-Extra模拟PV操作的实现，Part 1为题目描述，Part 2为设计分析，Part 3为课上源码（已AC并开源）参考，读者可自取所需。

同时，本博客系统已支持评论区，欢迎您参考 Gitment评论区配置与使用中Part2开通您在本博客的权限，留下您的想法。

Part 1 题目描述

在理论课中，我们学习到了 PV 操作，它是一种实现进程同步和互斥的方法。本次题目我们将模拟 PV 操作。 下面对 PV 操作相关知识进行回顾，若自信理论课学习充分，可以跳过。

PV 操作与信号量处理相关。对于一个信号量（将其记为 S ），在物理意义上其表示一种资源的个数，必须且只 能设置一次初值。信号量的数值只能通过 P、V 操作改变。

P 操作：物理意义上表示消耗资源。具体行为是检查信号量初值，若大于 0，表示有空闲资源，并分配一个资 源；若等于 0，表示没有空闲资源，此时进程阻塞等待；资源的语义下，信号量值不会出现小于 0 的情况，但理论课中，我们用其相反数表示正在等待的进程个数。
V 操作：物理意义上表示增加资源。具体行为是首先将信号量 S 加一，之后随机唤醒一个进程，也就是使其进入 就绪队列准备被调度运行。

一个信号量维护一种资源，一个信号量对应一个等待队列，不同信号量维护的资源之间不能共享。 等待表示进程进入阻塞状态，除非得到自己想要的资源，否则不能进行任何其他活动。

一种资源可以有多个，一个进程也可以同时占有多个资源、多种资源。

由于 lab3-1 阶段进程无法运行与调度，因此我们将通过模拟的方式来完成。模拟的行为与实际运行有一定的差异，因 此请认真阅读下面对本题机制的具体描述。
S_init

初始化信号量

在全局维护两个信号量，通过在所有 PV 操作前调用指定的初始化函数，将相关信号量初值设置为特定值 x ，在物理 意义上其表示目前共有 x 个资源可供使用。
以下机制描述均针对某一个信号量及其维护的某一种资源。

P操作

物理意义上表示消耗资源。具体行为：检查信号量，若大于 0，表示有空闲资源，因此申请成功，进程获得资源，更 新信号量大小并更新进程状态；若等于 0，表示没有空闲资源可供使用，此时进程更新状态，进入等待队列并排在队尾等待资源；资源的语义下，信号量值不会出现小于 0的情况。你可能维护进程持有的资源个数，需要在 P 操作执行 时一并更新：若成功获得资源，则进程拥有资源个数加一。

V操作

物理意义上表示释放资源。具体行为：检查等待队列，若此时有进程在等待资源，则将资源分配给队首进程，本进程 与获得资源的进程均更新状态；若此时无进程等待资源，则信号量加一并更新本进程状态。你可能维护进程持有的资源个数，需要在 V 操作执行时一并更新：若成功释放资源，则进程拥有资源个数减一，此处有一种未定义行为，当进 程持有资源个数为 0 时，不继续减一，即保持进程持有资源个数非负。

错误检查

与实际运行不同，在模拟中，P、V 操作由顶层函数统一发出，但从实际运行逻辑看，进程可能无法执行这一操作。具 体地，当进程处于等待资源状态时，其无法主动执行 P、V 的任何操作，若此时对此进程发出操作命令，将不按前述 逻辑执行，而是直接返回错误码。

题目要求

你需要在 lib/env.c中完成以下函数：

全局初始化信号量 S_init

  • 函数原型： void S_init(int s, int num)
  • 测试时此函数仅会被调用两次，且调用时间在所有 PV 操作前，用于将编号为 s 的信号量初始值设置为 num 数 值。两次调用时 s 的值分别为 1 和 2 ，表示两个不同信号量。

注意：函数名中 S 为大写字母，传入参数 s 为小写字母。

P操作 P

  • 函数原型：int P(struct Env* e, int s)
  • 调用此函数后，e 所指向的进程申请获得一个由 s 信号量管理的资源，这里 s 取值仅限于 1 和 2 ，具体逻辑见上述。

若操作能够执行（不论是否成功得到资源，都算能够执行），函数返回 0；反之（进程在执行此操作时已处于等 待队列中），不执行操作，并返回 -1.

V操作 V

  • 函数原型：int V(struct Env* e, int s)
  • 调用此函数后，e 所指向的进程释放一个由s信号量管理的资源，这里 s 取值仅限于 1 和 2 ，具体逻辑见上述。
  • 由于评测截取实际应用中的一部分PV操作，其中可能出现一种未定义行为，即在进程手中没有此资源时仍执行了 V 操作，我们约定此时仍按照释放一个资源执行，但进程自己维护的本资源个数保持为 0，不再减一。

进程状态查看 get_status

  • 函数原型： int get_status(struct Env* e)
  • 调用此函数，返回进程状态对应的数值（表述方便，记为b）：
    • 若进程正在队列中等待资源分配，b = 1
    • 若进程未处于等待状态且占有任一资源，b = 2
    • 若进程未处于等待状态且未占有任何资源，b = 3

进程创建函数 my_env_create

  • 函数原型：int my_env_create()
  • 调用此函数，功能类似于env_create_priority，由于本题目下进程不实际运行，无需加载二进制镜像，也无 需设置进程优先级，因此本函数没有参数。为便于评测，请返回创建进程的 env_id，若创建失败，请返回 -1. 在 此基础上你可以根据自己的实现机制增添其他初始化内容。

评测中此函数可能在任何时刻调用。

提示

PV操作及信号量机制的实现所依赖的数据结构一般为：一个整数（信号量）+ 一个队列（等待队列）。 等待队列的实现方法可自行选择，一种方法可以参考 env_free_list 的实现机制。
再次强调，不同信号量维护的资源不能共用，比如，若一个进程在等待2 信号量的资源，1信号量所维护的资源的释放不能解除此进程的等待状态。

注意

  • 对于所有在 lib/env.c 中新增的函数，请在include/env.h中添加相应的函数声明。
  • 由于评测指令数较多，请务必在提交评测前注释掉所有新增函数内的 printf代码，以免超时。
  • 如果你需要在进程控制块中维护相应内容，请在Env结构体中新增字段，不要借用其他 lab 的字段。同时，你需要保证sizeof(struct Env)不超过256.
  • PV 操作部分我们不对算法复杂度有严格要求，但评测中 get_status大量调用，此函数请务必使用 O(1) 算法，否则可能超时。

评测逻辑

在评测中，我们会替换init.c 文件，在初始化操作系统后，首先调用S_init函数初始化信号量，之后按一定的顺序
调用 P，V 两个函数，并在其中穿插my_env_create创建进程以及get_status检查特定进程的状态。

Part 2 设计分析

主要设计思路为模拟，以下针对可能的坑点做简要介绍。

资源维护

修正后的指导书明确指出，一个进程可能得到多种资源，对每种资源可能获得多个。

因此，我们一方面需要对两种资源的等待队列分别维护，另一方面也需要利用计数器等更精确地保存进程的资源获得情况。

Env结构体

新增status变量表示状态；新增has1,wait1,cnt1分别表示是否持有1资源，是否正在等待1资源，持有1资源数量，对于资源2同理新增对应变量。

P操作

注意当申请到资源的时候给对应的资源计数器自增1。如果申请资源失败，加入对应资源的等待队列并修改状态。

V操作

注意当释放资源的时候，只释放1个，释放后有可能仍持有资源。如果当前并不持有该资源，需要注意资源计数器不能为负数。

Part 3 课上源码

Env结构体

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
struct Env {
	struct Trapframe env_tf;        // Saved registers
	LIST_ENTRY(Env) env_link;       // Free list
	u_int env_id;                   // Unique environment identifier
	u_int env_parent_id;            // env_id of this env's parent
	u_int env_status;               // Status of the environment
	Pde  *env_pgdir;                // Kernel virtual address of page dir
	u_int env_cr3;
	LIST_ENTRY(Env) env_sched_link;
        u_int env_pri;
	// Lab 4 IPC
	u_int env_ipc_value;            // data value sent to us 
	u_int env_ipc_from;             // envid of the sender  
	u_int env_ipc_recving;          // env is blocked receiving
	u_int env_ipc_dstva;		// va at which to map received page
	u_int env_ipc_perm;		// perm of page mapping received

	// Lab 4 fault handling
	u_int env_pgfault_handler;      // page fault state
	u_int env_xstacktop;            // top of exception stack

	// Lab 6 scheduler counts
	u_int env_runs;			// number of times been env_run'ed
	u_int env_nop;                  // align to avoid mul instruction
	
	/* alter for lab3-1-Extra */
	int status;
	int has1;
	int has2;
	int wait1;
	int wait2;
	int cnt1;
	int cnt2;
    /* alter for lab3-1-Extra finished */
};

资源等待队列

1
2
3
4
5
/* alter for lab3-1-Extra */
static int sig[10] = {0};
static struct Env_list env_wait1_list;
static struct Env_list env_wait2_list;
/* alter for lab3-1-Extra finished*/

S_init

1
2
3
4
5
void S_init(int s, int num) {
	sig[s] = num;
	LIST_INIT(&env_wait1_list);
	LIST_INIT(&env_wait2_list);
}

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
int P(struct Env *e, int s) {
	//printf("env_id = %d s = %d s left : %d \n", e->env_id, s, sig[s]);
	if (e->wait1 == 1 || e->wait2 == 1) {
		return -1;
	}
	if (sig[s] > 0) {
		sig[s]--;
		e->status = 2;
		if (s == 1) {
			e->cnt1 = e->cnt1 + 1;
			e->has1 = 1;
		} else {
			e->cnt2 = e->cnt2 + 1;
			e->has2 = 1;
		}
		return 0;
	} else {
		e->status = 1;
		if (s == 1) { 
			LIST_INSERT_TAIL(&env_wait1_list, e, env_link);
			e->wait1 = 1;
		} else {
			LIST_INSERT_TAIL(&env_wait2_list, e, env_link);
			e->wait2 = 1;
		}
		//return -1;
	}
	return 0;
}

V操作

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
int V(struct Env* e, int s) {
	struct Env *eNow;
	if (e->wait1 == 1 || e->wait2 == 1) {
		return -1;
	}
	if (s == 1) {
		if (LIST_EMPTY(&env_wait1_list)) { 
			sig[s]++;
		} else {
			eNow = LIST_FIRST(&env_wait1_list);
			//eNow->status = 2;
			eNow->wait1 = 0;
			eNow->cnt1 = eNow->cnt1 + 1;
			eNow->has1 = 1;
			if (eNow->wait1 == 1 || eNow->wait2 == 1) {
				eNow->status = 1;
			} else if (eNow->has1 == 1 || eNow->has2 == 1) {
				eNow->status = 2;
			} else {
				eNow->status = 3;
			}
			LIST_REMOVE(eNow, env_link);
		}
		e->cnt1 = e->cnt1 - 1;
		if (e->cnt1 <= 0) {
			e->cnt1 = 0;
			e->has1 = 0;
		} else {
			e->has1 = 1;
		}
		//e->has1 = 0;
	} else {
		if (LIST_EMPTY(&env_wait2_list)) {
			sig[s]++;
		} else {
			eNow = LIST_FIRST(&env_wait2_list);
			//eNow->status = 2;
			eNow->wait2 = 0;
			eNow->cnt2 = eNow->cnt2 + 1;
			eNow->has2 = 1;
			if (eNow->wait1 == 1 || eNow->wait2 == 1) {	
				eNow->status = 1;
			} else if (eNow->has1 == 1 || eNow->has2 == 1) {
				eNow->status = 2;
			} else {
				eNow->status = 3;
			}
			LIST_REMOVE(eNow, env_link);
		}
		e->cnt2 = e->cnt2 - 1;
		if (e->cnt2 <= 0) {
			e->cnt2 = 0;
			e->has2 = 0;
		} else {
			e->has2 = 1;
		}
		//e->has2 = 0;
	}
	if (e->wait1 == 1 || e->wait2 == 1) {
		e->status = 1;
	} else if (e->has1 == 1 || e->has2 == 1) {
		e->status = 2;
	} else {
		e->status = 3;
	}
	return 0;
}

my_env_create()

1
2
3
4
5
6
7
int my_env_create() {
	struct Env *e;
	if (env_alloc(&e, 0) != 0) {
		return -1;
	}
	return e->env_id;
}

get_status()

1
2
3
int get_status(struct Env *e) {
	return e->status;
}

Part 4 后记

由于上机时评测姬咕咕咕了20min，这次的Extra写得十分仓促，很可能有冗余设计（比如有了cnt变量就应当可以用cnt为0表示不持有资源而无需has变量），欢迎大家批评指正。

This is copyright.

FEATURED TAGS
BUAA-OS
FRIENDS