NUAA操作系统OS实验及上机考试记录

记录nuaa操作系统实验题目

将代码分享出来是为了学弟学妹更好的学习复习，并不是为copy提供便利。里边包含了平时的job及近几年的考试题，我已将代码上传至github：
https://github.com/changyan-maker/NUAA_OS

最后参加机考我拿了90+，来源于平时认真完成job以及考前认真刷题准备，所以平时不要copy代码投机取巧哦，要理解其中的思路，在机考的过程中才能游刃有余！

exam

往年考试题的题目和代码已上传至github，建议考前多刷两遍，
https://github.com/changyan-maker/NUAA_OS
毕竟考试相对综合，个人觉得考前时间充裕的话，先刷一遍作业的job，最后再刷往年考试题会很有感觉。我们19级也就是2022年考的特别难，基本没有几个同学完全运行出正确结果，老师最后都是按照过程给分，这里将题目分享出来只是为了长长见识，毕竟在考试前我也没太见过这种题，考试过程中基本全靠临场发挥。不过前几年的题目还是很简单的，听说拿满分的人也有，所以对于2018、2019、2021年的题目，学弟学妹一定要自己写出来，拿下那些题型！

job3

1. myecho.c

myecho.c的功能与系统echo程序相同
接受命令行参数，并将参数打印出来，例子如下：
$ ./myecho x
x
$ ./myecho a b c
a b c

#include<stdio.h>
int main(int argc, char *argv[])
{
	int i;
	printf("argc=%d\n",argc);
	for(i=1;i<argc;i++)
		printf("%s ",argv[i]);
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10

2. mycat.c

mycat.c的功能与系统cat程序相同
mycat将指定的文件内容输出到屏幕，例子如下：
要求使用系统调用open/read/write/close实现
$ cat /etc/passwd
root：x:0:0:root:/root:/bin/bash
daemon：x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin：x:2:2:bin:/bin:/usr/sbin/nologin
…
$ ./mycat /etc/passwd
root：x:0:0:root:/root:/bin/bash
daemon：x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin：x:2:2:bin:/bin:/usr/sbin/nologin
…

#include<stdio.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<unistd.h>

int main(int argc, char *argv[])
{
	int fd;
	mode_t mode = 0777;
	fd = open(argv[1],O_RDONLY,mode);
	char ch;
	int count = read(fd, &ch, sizeof(ch));
	while(count)
	{
		printf("%c", ch);
		count = read(fd, &ch, sizeof(ch));
	}
	close(fd);
	return 0;
}

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

3. mycp.c

mycp.c的功能与系统cp程序相同
将源文件复制到目标文件，例子如下：
要求使用系统调用open/read/write/close实现
$ cat /etc/passwd
root：x:0:0:root:/root:/bin/bash
daemon：x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin：x:2:2:bin:/bin:/usr/sbin/nologin
…
$ ./mycp /etc/passwd passwd.bak
$ cat passwd.bak
root：x:0:0:root:/root:/bin/bash
daemon：x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin：x:2:2:bin:/bin:/usr/sbin/nologin
…

#include<stdio.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<unistd.h>

int main(int argc, char *argv[])
{
	mode_t mode = 0777;
	int fd1 = open(argv[1], O_RDONLY, mode);
	int fd2 = creat(argv[2],mode);
	char ch;
	int count = read(fd1, &ch, sizeof(ch));
	int count2;
	while(count)
	{
		count2 = write(fd2, &ch, sizeof(ch));
		count = read(fd1, &ch, sizeof(ch));
	}
	close(fd1);
	close(fd2);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. mysys.c

mysys的功能与系统函数system相同，要求用进程管理相关系统调用自己实现一遍
使用fork/exec/wait系统调用实现mysys
不能通过调用系统函数system实现mysys
测试程序
#include <stdio.h>

void mysys(char *command)
{
 实现该函数，该函数执行一条命令，并等待该命令执行结束
}

int main()
{
 printf(“--------------------------------------------------\n”);
 mysys(“echo HELLO WORLD”);
 printf(“--------------------------------------------------\n”);
 mysys(“ls /”);
 printf(“--------------------------------------------------\n”);
 return 0;
}
测试程序的输出结果
--------------------------------------------------
HELLO WORLD
--------------------------------------------------
bin core home lib mnt root snap tmp vmlinuz
boot dev initrd.img lost+found opt run srv usr vmlinuz.old
cdrom etc initrd.img.old media proc sbin sys var
--------------------------------------------------

#include<stdio.h>
#include<unistd.h>
#include<string.h>
#include<sys/wait.h>
#include<stdlib.h>

void mysys(char *command)
{
	int pid;
	pid = fork();
	if(pid==0){
		int i=0;
		char a[5][20];
		int num = 0;
		int j=0;
		while(command[i]!='\0')
		{
			if(command[i]!=' '){
				a[num][j++] = command[i];
			}		
			else{
				a[num++][j++] = '\0';
				j=0;
			}
			i++;
		}
		a[num][j++] = '\0';
		int error;

		char *argv[5];
		for(i=0;i<=num;i++){
			argv[i] = (char *)malloc(sizeof(char)*20);
			strcpy(argv[i],a[i]);
		}
		argv[i] = NULL;
		error = execvp(argv[0],argv);
		if(error<0)
			perror("execv");
	}
	wait(NULL);
}

int main()
{
	printf("--------------------------------------------------\n");
	mysys("echo HELLO WORLD");	
	printf("--------------------------------------------------\n");
	mysys("ls /");
	printf("--------------------------------------------------\n");
	return 0;
}

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

5. sh1.c

该程序读取用户输入的命令，调用函数mysys(上一个作业)执行用户的命令，示例如下
# 编译sh1.c
$ cc -o sh1 sh1.c

# 执行sh1
$ ./sh

# sh1打印提示符>，同时读取用户输入的命令echo，并执行输出结果
> echo a b c
a b c

# sh1打印提示符>，同时读取用户输入的命令cat，并执行输出结果
> cat /etc/passwd
root：x:0:0:root:/root:/bin/bash
daemon：x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin：x:2:2:bin:/bin:/usr/sbin/nologin
实现内置命令cd、pwd、exit

#include<stdio.h>
#include<unistd.h>
#include<string.h>
#include<sys/wait.h>
#include<stdlib.h>

int main()
{
	while(1){
		printf("%s","> ");
		char str[105];
		fgets(str,100,stdin);
		int i=0;
		while(str[i]!='\n')
			i++;
		str[i] = '\0';
		
		i=0;
		char a[5][20];
		int num = 0;
		int j=0;
		while(str[i]!='\0')
		{
			if(str[i]!=' '){
				a[num][j++] = str[i];
			}		
			else{
				a[num++][j++] = '\0';
				j=0;
			}
			i++;
		}
		a[num][j++] = '\0';
		int error;
		char *argv[5];
		for(i=0;i<=num;i++){
			argv[i] = (char *)malloc(sizeof(char)*20);
			strcpy(argv[i],a[i]);
		}
		argv[i] = NULL;

		if(strcmp(argv[0],"cd")==0){
			chdir(argv[1]);
		}
		else if(strcmp(argv[0],"exit")==0){
			exit(0);
		}
		else if(strcmp(argv[0],"pwd")==0){
			char work_dir[80];

			getcwd(work_dir,sizeof(work_dir));
			printf("%s\n",work_dir);
		}
		else{
			int pid;
			pid = fork();
			if(pid==0){
				error = execvp(argv[0],argv);
				if(error<0)
					perror("execv");
			}
			wait(NULL);
		}
	}
	return 0;
}	

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

job4

1. myls.c

myls.c的功能与系统ls程序相同
opendir readdir closedir
在命令行中输入 man opendir 获取帮助
列出指定目录下的文件，例子如下：
$ ./myls job4/test
a
b
c
列出当前目录下的文件，例子如下：
$ cd job4/test
$ ./myls
a
b
c

#include<stdio.h>
#include<dirent.h>
#include<unistd.h>
#include<string.h>

int main(int argc, char *argv[]){
	DIR *dir;
	if(argc >= 2)
		dir = opendir(argv[1]);
	else
		dir = opendir(getcwd(NULL,0));
	while(1){
		struct dirent *de = readdir(dir);
		if(de == NULL)	break;
		if(strcmp(de->d_name,"..")!=0 && strcmp(de->d_name,".")!=0){
					
			printf("%s\n",de->d_name);

		}
	}
	closedir(dir);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2. mytree.c

mytree.c的功能与系统tree程序相同
使用空格作为缩进，表示层次
$ ./mytree job4/test
test
 a
 b
 x
 y
 z
c

#include<stdio.h>
#include<dirent.h>
#include<unistd.h>
#include<string.h>
#include<stdlib.h>

void mytree(int k_num, char *work_dir){
	char k[80] = "";
	for(int i=0;i<k_num;i++)
		strcat(k," ");
	DIR *dir = opendir(work_dir);
	if(dir == NULL){
		perror("opendir");
		exit(0);
	}
	while(1){
		struct dirent *de = readdir(dir);
		if(de == NULL)	break;
		if(strcmp(de->d_name,"..")!=0 && strcmp(de->d_name,".")!=0){
			printf("%s",k);
			printf("%s\n", de->d_name);
			if(de->d_type == DT_DIR){
				strcat(work_dir,"/");
				strcat(work_dir,de->d_name);
				mytree(k_num+1,work_dir);
			}
		}
	}
	closedir(dir);
}


int main(int argc, char *argv[]){
	if(argc >= 2){	
		printf("%s\n",argv[1]);
		mytree(1, argv[1]);
	}
	else{
		printf("%s\n",getcwd(NULL,0));
		mytree(1, getcwd(NULL,0));
	}
	return 0;
}

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

job5

1.sh2.c

实现shell程序，要求在第1版的基础上，增加文件重定向功能
重定向输入
重定向输出
重定向追加

#include<stdio.h>
#include<unistd.h>
#include<string.h>
#include<sys/wait.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<stdlib.h>

void child(char *argv[]){
	int num=0;
	int i = 0;
	while(argv[i]){
		i++;
		num++;
	}

	char str1[80];
	char str2[80];
	if(argv[1]!=NULL && argv[1][0] == '<'){
		memcpy(str1, argv[1]+1,sizeof(argv[1]-1));
		int fd1 = open(str1,O_CREAT|O_RDWR,0666);
		dup2(fd1,0);		//input from fd1;
		close(fd1);
		argv[1] = NULL;		//for cat
	}
	if(argv[2]!= NULL && argv[2][0] ==  '>'){
		int fd2;
		if(argv[2][1]=='>'){		// >>
			memcpy(str2,argv[2]+2,sizeof(argv[2]-2));
			fd2 = open(str2,O_CREAT|O_RDWR|O_APPEND,0666);		
		}
		else{				// >	
			memcpy(str2,argv[2]+1,sizeof(argv[2]-1));
			fd2 = open(str2,O_CREAT|O_RDWR|O_TRUNC,0666);
		}
		dup2(fd2,1);	//output into fd2;
		close(fd2);
		argv[2] = NULL;		//for echo
	}

	int error = execvp(argv[0],argv);
	if(error<0)
		perror("execv");
}

int main()
{
	while(1){
		printf("%s","> ");
		char str[105];
		fgets(str,100,stdin);
		int i=0;
		while(str[i]!='\n')
			i++;
		str[i] = '\0';
		
		i=0;
		char a[5][20];
		int num = 0;
		int j=0;
		while(str[i]!='\0')
		{
			if(str[i]!=' '){
				a[num][j++] = str[i];
			}		
			else{
				a[num++][j++] = '\0';
				j=0;
			}
			i++;
		}
		a[num][j++] = '\0';
		int error;
		char *argv[5];
		for(i=0;i<=num;i++){
			argv[i] = (char *)malloc(sizeof(char)*20);
			strcpy(argv[i],a[i]);
		}
		argv[i] = NULL;

		if(strcmp(argv[0],"cd")==0){
			chdir(argv[1]);
		}
		else if(strcmp(argv[0],"exit")==0){
			exit(0);
		}
		else if(strcmp(argv[0],"pwd")==0){
			char work_dir[80];
			getcwd(work_dir,sizeof(work_dir));
			printf("%s\n",work_dir);
		}
		else{
			int pid;
			pid = fork();
			if(pid==0){
				child(argv);
			}
			wait(NULL);
		}
	}
	return 0;
}	

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

job7

1. pi1.c

使用2个线程根据莱布尼兹级数计算PI

莱布尼兹级数公式: 1 - 1/3 + 1/5 - 1/7 + 1/9 - … = PI/4
主线程创建1个辅助线程
主线程计算级数的前半部分
辅助线程计算级数的后半部分
主线程等待辅助线程运行結束后,将前半部分和后半部分相加

#include<stdio.h>
#include<pthread.h>
#include<stdlib.h>

int count = 1e7;

typedef struct{
	double sum;
}result;

void *compute(){
	double sum = 0;
	for(int i=count/2;i<count;i++){
		if(i&1)		//sub
			sum -= (1.0/(i*2+1));
		else 		//sub
			sum += (1.0/(i*2+1));
	}
	result *res;
	res = malloc(sizeof(result));
	res->sum = sum;
	return res;
}

int main(){
	pthread_t compute_tid;
	pthread_create(&compute_tid, NULL, compute, NULL);
	double sum=0;
	for(int i=0;i<count/2;i++){
		if(i&1)		//sub
			sum -= (1.0/(i*2+1));
		else		//add
			sum += (1.0/(i*2+1));
	}
	result *res;
	pthread_join(compute_tid, (void **)&res);	//wait compute finished
	sum = (sum + res->sum)*4;
	printf("%.7lf\n",sum);
	return 0;
}

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

2. pi2.c

使用N个线程根据莱布尼兹级数计算PI

与上一题类似，但本题更加通用化，能适应N个核心
主线程创建N个辅助线程
每个辅助线程计算一部分任务，并将结果返回
主线程等待N个辅助线程运行结束，将所有辅助线程的结果累加
本题要求 1: 使用线程参数，消除程序中的代码重复
本题要求 2: 不能使用全局变量存储线程返回值

解决思路：
该题主要考查N个线程的创建与运行，首先需要在主线程中创建N个辅助线程，需要通过结构体完成主线程与子线程之间的数值交互，由于需要每个线程完成一部分计算任务，所以需要确定计算的开始和结束位置。主线程等待所有子线程都计算完后将其返回值累加。

#include<stdio.h>
#include<pthread.h>
#include<stdlib.h>
int N = 4;
int count = 1e7;

typedef struct{		//return the result
	double sum;
}result;

typedef struct{		//connect main_thread and child_thread
	int start;
	int end;
}param;

void *compute(void *arg){
	double sum=0;
	param *par;
	par = (param *)arg;
	for(int i=par->start;i<par->end;i++){
		if(i&1)		//sub
			sum -= (1.0/(i*2+1));
		else		//add
			sum += (1.0/(i*2+1));
	}
	result *res;		// return the result
	res = malloc(sizeof(result));
	res->sum = sum;
	return res;
}

int main(){
	pthread_t computers[N];
	int i;
	param pars[N];
	for(i=0;i<N;i++){		// create the child threads
		param *par;
		par = &pars[i];
		par->start = (count/N) * i;
		par->end = (count/N) * (i+1);
		pthread_create(&computers[i], NULL, compute, par);
	}
	result *res[N];
	for(i=0;i<N;i++)		// wait the child threads
		pthread_join(computers[i], (void**)&res[i]);
	double sum = 0;
	for(i=0;i<N;i++)
		sum += res[i]->sum;		// add the result
	printf("%.7lf\n",sum*4);
	return 0;
}

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

3. sort.c

多线程排序
主线程创建两个辅助线程
辅助线程1使用选择排序算法对数组的前半部分排序
辅助线程2使用选择排序算法对数组的后半部分排序
主线程等待辅助线程运行結束后,使用归并排序算法归并子线程的计算结果
本题要求 1: 使用线程参数，消除程序中的代码重复

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>

int array[] = {5, 9, 1, 3, 6, 7, 2, 10, 4, 8};
#define N 2
#define num 10
int temp[num];

struct param {
	int *array;
	int start;
	int end;
};

struct result {
	int *array;
};

void *selection_sort(void *arg){
	struct param *param;
	struct result *result;
	int sum = 0;
	param = (struct param *)arg;
	int i,j,min,temp;
	for(i=param->start;i<param->end-1;i++){	
		min = i;
		for(j=i+1;j<param->end;j++){
			if(param->array[j]<param->array[min])
				min = j;
		}
		if(min!=i){
			temp = param->array[min];
			param->array[min] = param->array[i];
			param->array[i] = temp;
		}
	}
	result = malloc(sizeof(struct result));
	result->array = param->array;
	return result;
}

void merge_sort(int a[], int l, int r){
	int mid;
	if( l >= r)	return;
	mid = (l+r)/2;
	merge_sort(a,l,mid);
	merge_sort(a,mid+1,r);
	int i = l, j = mid + 1;
	int k = 0;
	while(i<=mid && j<=r) {
		if(a[i]<=a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	while(i<=mid) temp[k++] = a[i++];
	while(j<=r) temp[k++] = a[j++];
	for(i=l,j=0;i<=r;i++,j++)
		a[i] = temp[j];
}

int main(){
	pthread_t workers[N];
	struct param params[N];
	for(int i=0;i<N;i++){
		struct param *param;
		param  = &params[i];
		param->array = array;
		param->start = i * (num/N);
	        param->end = (i+1) * (num/N);
		pthread_create(&workers[i], NULL, selection_sort, param);	
	}
	for(int i=0;i<N;i++){
		struct result *result;
		pthread_join(workers[i], (void **)&result);
		free(result);
	}
	// finish selection_sort
	merge_sort(array,0,num-1);
	for(int i=0;i<num;i++)
		printf("%d ",array[i]);
	printf("\n");
	return 0;
}

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

job8

1. pc.c

使用条件变量解决生产者、计算者、消费者问题

系统中有3个线程：生产者、计算者、消费者
系统中有2个容量为4的缓冲区：buffer1、buffer2
生产者
- 生产’a’、‘b’、‘c’、‘d’、‘e’、‘f’、‘g’、'h’八个字符
- 放入到buffer1
- 打印生产的字符
计算者
- 从buffer1取出字符
- 将小写字符转换为大写字符，按照 input:OUTPUT 的格式打印
- 放入到buffer2
消费者
- 从buffer2取出字符
- 打印取出的字符
程序输出结果(实际输出结果是交织的)
a
b
c
…
a:A
b:B
c:C
…
A
B
C
…

解决思路：
此题为课上讲的生产者消费者例子的扩充，等于完成2次生产消费关系。我在第一次做的时候直接将所有的函数及变量都区别了1和2，produce和compute对应为1，compute和consume对应为2，直接照搬课上的例子就可以实现，但是在最后复习的时候搞懂了其中的原理，发现这么写有很多相同的代码片段，一点儿都不简洁，所以用数组和下标实现了相对简洁的代码。
此题首先要创建3个线程，分别代表生产者、计算者、消费者，在生产者中存存数据到第一个buffer里，在计算者中取出生产者存放的数据，并将变化后的结构存入第二个buffer里，在消费者从第二个buffer里取出数据。这里的存取数据中封装了条件变量，实现存取的原子性，减少不必要的控制错误。

#include<stdio.h>
#include<pthread.h>

#define CAPACITY 4
#define ITEM_COUNT (CAPACITY*2)

int buffer1[CAPACITY];
int buffer2[CAPACITY];
int in[2],out[2];

pthread_mutex_t mutex[2];
pthread_cond_t wait_empty_buffer[2];
pthread_cond_t wait_full_buffer[2];

int buffer_is_empty(int i){
	return (in[i]==out[i]);
}

int buffer_is_full(int i){
	return (((in[i]+1)% CAPACITY) == out[i]);
}

void put_item(int i,int item){
	pthread_mutex_lock(&mutex[i]);
	while(buffer_is_full(i))
		pthread_cond_wait(&wait_empty_buffer[i], &mutex[i]);

	if(i==0){				//put item
		buffer1[in[i]] = item;	
	}
	else
		buffer2[in[i]] = item;
	in[i] = (in[i]+1)%CAPACITY;

	pthread_cond_signal(&wait_full_buffer[i]);
	pthread_mutex_unlock(&mutex[i]);
}

int get_item(int i){	
	int item;
	pthread_mutex_lock(&mutex[i]);	 	//let the mutex and cond in the get_item
	while(buffer_is_empty(i))		//prevent some errors
		pthread_cond_wait(&wait_full_buffer[i], &mutex[i]);

	if(i==0)
		item = buffer1[out[i]];		//get item
	else
		item = buffer2[out[i]];

	out[i] = (out[i]+1)% CAPACITY;

	pthread_cond_signal(&wait_empty_buffer[i]);
	pthread_mutex_unlock(&mutex[i]);	
	
	return item;
}

void *produce(){
	int item = 'a';
	for(int i=0;i<ITEM_COUNT;i++){
		printf("%c\n",item);
		put_item(0,item);
		item++;
	}
}

void *compute(){
	int item;
	for(int i=0;i<ITEM_COUNT;i++){
		item = get_item(0);
		printf("    %c:",item);
		item = item - 32;
		put_item(1,item);
		printf("%c\n",item);
	}
}

void *consume(){
	int item;
	for(int i=0;i<ITEM_COUNT;i++){
		item = get_item(1);
		printf("         %c\n",item);
	}
}


int main(){
	pthread_t producer,computer,consumer;

	int i;
	for(i=0;i<2;i++){			//init
		pthread_mutex_init(&mutex[i], NULL);
		pthread_cond_init(&wait_empty_buffer[i], NULL);
		pthread_cond_init(&wait_full_buffer[i], NULL);
	}
	
	//create the sub threads
	pthread_create(&producer, NULL, produce, NULL);		
	pthread_create(&computer, NULL, compute, NULL);
	pthread_create(&consumer, NULL, consume, NULL);

	//wait the sub threads finished
	pthread_join(producer, NULL);
	pthread_join(computer, NULL);
	pthread_join(consumer, NULL);

	return 0;
}

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

2. pp.c

使用条件变量实现 ping-pong 问题

系统中有2个线程：ping 线程和 pong 线程
ping 线程先执行
ping 线程执行流程如下
1. 打印输出 ping
2. 等待 pong 线程输出
3. 执行第 1 步
pong 线程执行流程如下
1. 打印输出 pong
2. 等待 ping 线程输出
3. 执行第 1 步
程序输出结果
ping
pong
ping
pong
…

#include<stdio.h>
#include<pthread.h>

pthread_mutex_t mutex;
pthread_cond_t wait_ping,wait_pong;

int state = 1;

void *ping(){
	int count=0;
	while(count++ < 20){
		pthread_mutex_lock(&mutex);
		while(state!=1)
			pthread_cond_wait(&wait_ping, &mutex);
		printf("ping\n");
		state = 0;
		pthread_cond_signal(&wait_pong);
		pthread_mutex_unlock(&mutex);
	}
}

void *pong(){
	int count=0;
	while(count++ < 20){
		pthread_mutex_lock(&mutex);
		while(state!=0)	
			pthread_cond_wait(&wait_pong, &mutex);
		printf("pong\n");
		state = 1;
		pthread_cond_signal(&wait_ping);
		pthread_mutex_unlock(&mutex);
	}
}

int main(){
	pthread_t ping_tid,pong_tid;
	
	pthread_mutex_init(&mutex, NULL);
	pthread_cond_init(&wait_ping, NULL);
	pthread_cond_init(&wait_pong, NULL);

	pthread_create(&ping_tid, NULL, ping, NULL);
	pthread_create(&pong_tid, NULL, pong, NULL);

	pthread_join(ping_tid, NULL);
	pthread_join(pong_tid, NULL);

	return 0;
}

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

job9

1. pc.c

使用信号量解决生产者、计算者、消费者问题
功能与 job8/pc.c 相同

解决思路：
使用信号量达到封装的效果，定义信号量的等待和释放函数，等待的过程将信号量的值减一，释放的过程将信号量的值加一，用来判断当前状态是否可用，如果该值小于等于0，那需要一直等待信号量才可以进行下一步操作。
对于此题需要先初始化信号量，创建生产者、计算者、消费者线程。在子线程里，需要先等待信号量，在执行完相应的操作后再释放信号量，允许其它线程进行执行。

#include<stdio.h>
#include<pthread.h>
#include<unistd.h>

#define CAPACITY 4
int buffer1[CAPACITY];
int in1;
int out1;
int buffer2[CAPACITY];
int in2;
int out2;

int buffer1_is_empty(){
	return in1 == out1;
}

int buffer1_is_full(){
	return (in1 + 1) % CAPACITY == out1;
}

int buffer2_is_empty(){
	return in2 == out2;
}

int buffer2_is_full(){
	return (in2 + 1) % CAPACITY == out2;
}

int get_item1(){
	int item1;
	item1 = buffer1[out1];
	out1 = (out1 + 1) % CAPACITY;
	return item1;
}

int get_item2(){
	int item2;
	item2 = buffer2[out2];
	out2 = (out2 + 1) % CAPACITY;
	return item2;
}

void put_item1(int item1){
	buffer1[in1] = item1;
	in1 = (in1 + 1)% CAPACITY;
}

void put_item2(int item2){
	buffer2[in2] = item2;
	in2 = (in2 + 1)% CAPACITY;
}

typedef struct {
	int value;
	pthread_mutex_t mutex;
	pthread_cond_t cond;
} sema_t;

void sema_init(sema_t *sema, int value){
	sema->value = value;
	pthread_mutex_init(&sema->mutex, NULL);
	pthread_cond_init(&sema->cond, NULL);
}

void sema_wait(sema_t *sema){
	pthread_mutex_lock(&sema->mutex);
	while(sema->value <= 0)
		pthread_cond_wait(&sema->cond, &sema->mutex);
	sema->value --;
	pthread_mutex_unlock(&sema->mutex);
}

void sema_signal(sema_t *sema){
	pthread_mutex_lock(&sema->mutex);
	++ sema->value;
	pthread_cond_signal(&sema->cond);
	pthread_mutex_unlock(&sema->mutex);
}

sema_t mutex1_sema;
sema_t empty_buffer1_sema;
sema_t full_buffer1_sema;
sema_t mutex2_sema;
sema_t empty_buffer2_sema;
sema_t full_buffer2_sema;

#define ITEM_COUNT (CAPACITY*2)

void *consume(void *arg){
	int i;
	int item2;
	for(i=0;i<ITEM_COUNT;i++){
		sema_wait(&full_buffer2_sema);
		sema_wait(&mutex2_sema);

		item2 = get_item2();
		printf("        %c\n", item2);

		sema_signal(&mutex2_sema);
		sema_signal(&empty_buffer2_sema);
	}
	return NULL;
}

void *compute(){
	int i;
	int item1;
	int item2;

	for(i=0;i<ITEM_COUNT;i++){
		//read
		sema_wait(&full_buffer1_sema);
		sema_wait(&mutex1_sema);

		item1 = get_item1();
		item2 = item1 - 32;
		printf("    %c:%c\n",item1,item2);

		sema_signal(&mutex1_sema);
		sema_signal(&empty_buffer1_sema);

		//write
		sema_wait(&empty_buffer2_sema);
		sema_wait(&mutex2_sema);

		
		put_item2(item2);
		
		sema_signal(&mutex2_sema);
		sema_signal(&full_buffer2_sema);
	}
	return NULL;
}

void *produce(){
	int i;
	int item1;

	for(i=0;i<ITEM_COUNT;i++){
		sema_wait(&empty_buffer1_sema);
		sema_wait(&mutex1_sema);

		item1 = i + 'a';
		put_item1(item1);
		printf("%c\n", item1);

		sema_signal(&mutex1_sema);
		sema_signal(&full_buffer1_sema);
	}
	return NULL;
}

int main(){
	pthread_t consumer_tid;
	pthread_t computer_tid;

	sema_init(&mutex1_sema,1);
	sema_init(&empty_buffer1_sema, CAPACITY-1);
	sema_init(&full_buffer1_sema, 0);

	sema_init(&mutex2_sema, 1);
	sema_init(&empty_buffer2_sema, CAPACITY-1);
	sema_init(&full_buffer2_sema, 0);

	pthread_create(&computer_tid, NULL, compute, NULL);
	pthread_create(&consumer_tid, NULL, consume, NULL);
	produce();
	pthread_join(consumer_tid, NULL);
	pthread_join(computer_tid, NULL);
	return 0;
}

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

2. pp.c

使用信号量实现 ping-pong 问题
功能与 job8/pp.c 相同

#include<stdio.h>
#include<pthread.h>

#define CAPACITY 4
#define ITEM_COUNT (CAPACITY*2)

int in[2],out[2];
int buffer[2][CAPACITY];

typedef struct{
	int value;
	pthread_mutex_t mutex;
	pthread_cond_t cond;
}sema_t;

void sema_init(sema_t* sema, int value){
	sema->value = value;
	pthread_mutex_init(&sema->mutex, NULL);
	pthread_cond_init(&sema->cond, NULL);
}

void sema_wait(sema_t *sema){
	pthread_mutex_lock(&sema->mutex);
	while(sema->value<=0)
		pthread_cond_wait(&sema->cond, &sema->mutex);
	sema->value--;
	pthread_mutex_unlock(&sema->mutex);
}

void sema_signal(sema_t *sema){
	pthread_mutex_lock(&sema->mutex);
	sema->value++;
	pthread_cond_signal(&sema->cond);
	pthread_mutex_unlock(&sema->mutex);
}

sema_t mutex_sema[2];
sema_t full_buffer[2];
sema_t empty_buffer[2];

int buffer_is_empty(int i){
	return (in[i]==out[i]);
}

int buffer_is_full(int i){
	return ((in[i]+1)%CAPACITY == out[i]);
}

void put_item(int i,int item){
	sema_wait(&mutex_sema[i]);
	sema_wait(&empty_buffer[i]);

	buffer[i][in[i]] = item;
	in[i] = (in[i]+1) % CAPACITY;

	sema_signal(&full_buffer[i]);
	sema_signal(&mutex_sema[i]);
}

int get_item(int i){
	int item;
	sema_wait(&mutex_sema[i]);
	sema_wait(&full_buffer[i]);

	item = buffer[i][out[i]];
	out[i] = (out[i]+1)% CAPACITY;

	sema_signal(&empty_buffer[i]);
	sema_signal(&mutex_sema[i]);

	return item;
}

void *produce(){
	int item = 'a';
	for(int i=0;i<ITEM_COUNT;i++){
		printf("%c\n",item);
		put_item(0,item);
		item++;
	}
}

void *compute(){
	int item;
	for(int i=0;i<ITEM_COUNT;i++){
		item = get_item(0);
		printf("    %c:",item);
		item = item - 32;
		put_item(1, item);
		printf("%c\n", item);
	}
}

void *consume(){
	int item;
	for(int i=0;i<ITEM_COUNT;i++){
		item = get_item(1);
		printf("         %c\n",item);
	}
}

int main(){
	pthread_t producer,computer,consumer;
	int i;
	for(i=0;i<2;i++){
		sema_t *sema;
		sema = &mutex_sema[i];
		sema_init(sema,1);
		sema = &empty_buffer[i];
		sema_init(sema, CAPACITY-1);
		sema = &full_buffer[i];
		sema_init(sema, 0);
	}

	pthread_create(&producer, NULL, produce, NULL);
	pthread_create(&computer, NULL, compute, NULL);
	pthread_create(&consumer, NULL, consume, NULL);

	pthread_join(producer, NULL);
	pthread_join(computer, NULL);
	pthread_join(consumer, NULL);

	return 0;
}

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

job10

1. sfind.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<dirent.h>
#include<sys/stat.h>
#include<unistd.h>

void find_file(char *path, char *target){
	FILE *file = fopen(path, "r");

	char line[256];
	while(fgets(line, sizeof(line), file)){
		if(strstr(line, target))
			printf("%s: %s",path, line);
	}
	fclose(file);
}

void find_dir(char *path, char *target){
	DIR *dir = opendir(path);
	struct dirent *entry;
	while(entry = readdir(dir)){
		char name[256];
		strcpy(name, path);
		if(strcmp(entry->d_name, ".") == 0)
			continue;
		if(strcmp(entry->d_name, "..") == 0)
			continue;
		if(entry->d_type == DT_DIR){
			strcat(name,"/");
			strcat(name,entry->d_name);
	//		printf("%s\n", name);
			find_dir(name, target);
		}
		if(entry->d_type == DT_REG){
			strcat(name,"/");
			strcat(name,entry->d_name);
	//		printf("111%s\n",name);
			find_file(name, target);
		//	printf("file  %s\n", entry->d_name);
		}
	}
	closedir(dir);
}

int main(int argc, char *argv[]){
	if(argc != 3){
		puts("Usage: sfind file string");
		return 0;
	}


	char *path = argv[1];
	char *string = argv[2];


	struct stat info;
	stat(path, &info);

	if(S_ISDIR(info.st_mode))
		find_dir(path, string);
	else
		find_file(path, string);
	return 0;
}

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

2. pfind.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<dirent.h>
#include<sys/stat.h>
#include<unistd.h>
#include<pthread.h>

#define WORKER_NUMBER 4
#define CAPACITY 4

typedef struct{
	int is_end;
	char path[128];
	char string[128];
}task;

task buffer[CAPACITY];
int in;
int out;


int buffer_is_empty(){
	return in==out;
}

int buffer_is_full(){
	return (in+1)%CAPACITY == out;
}

pthread_mutex_t mutex;
pthread_cond_t wait_empty_buffer;
pthread_cond_t wait_full_buffer;

task get_task()
{
	task item;
//	task *buffer;
//	buffer = &buffer[out];
	pthread_mutex_lock(&mutex);
	while(buffer_is_empty())
		pthread_cond_wait(&wait_full_buffer, &mutex);

	item.is_end = buffer[out].is_end;
	strcpy(item.path,buffer[out].path);
	strcpy(item.string, buffer[out].string);
	out = (out + 1) % CAPACITY;

	pthread_cond_signal(&wait_empty_buffer);
	pthread_mutex_unlock(&mutex);
	
	return item;
}

void put_task(task *item){
//	task *buffer;
//	buffer = &buffer[in];
	pthread_mutex_lock(&mutex);
	while(buffer_is_full())
		pthread_cond_wait(&wait_empty_buffer, &mutex);

	buffer[in].is_end = item->is_end;
	strcpy(buffer[in].path, item->path);
	strcpy(buffer[in].string, item->string);
	in = (in + 1) % CAPACITY;

	pthread_cond_signal(&wait_full_buffer);
	pthread_mutex_unlock(&mutex);
}

void find_file(char *path, char *target){
	FILE *file = fopen(path, "r");

	char line[256];
	while(fgets(line, sizeof(line), file)){
		if(strstr(line, target))
			printf("%s: %s",path, line);
	}
	fclose(file);
}

void *worker_entry(){
	while(1){
		task t;
		t = get_task();
		if(t.is_end)
			break;
		find_file(t.path, t.string);
	}
	return NULL;
}
void find_dir(char *path, char *target){
	DIR *dir = opendir(path);
	struct dirent *entry;
	while(entry = readdir(dir)){
		char name[256];
		strcpy(name, path);
		if(strcmp(entry->d_name, ".") == 0)
			continue;
		if(strcmp(entry->d_name, "..") == 0)
			continue;
		if(entry->d_type == DT_DIR){
			strcat(name,"/");
			strcat(name,entry->d_name);
		//	printf("%s\n", name);
			find_dir(name, target);
		}
		if(entry->d_type == DT_REG){
			strcat(name,"/");
			strcat(name,entry->d_name);
			task item;
			item.is_end = 0;
			strcpy(item.path, name);
			strcpy(item.string, target);
			put_task(&item);
		}
	}
	closedir(dir);
}

int main(int argc, char *argv[]){
	if(argc != 3){
		puts("Usage: sfind file string");
		return 0;
	}


	char *path = argv[1];
	char *string = argv[2];

	pthread_mutex_init(&mutex, NULL);
	pthread_cond_init(&wait_empty_buffer, NULL);
	pthread_cond_init(&wait_full_buffer, NULL);


	struct stat info;
	stat(path, &info);

	pthread_t workers[WORKER_NUMBER];
	for(int i=0;i<WORKER_NUMBER;i++){
		pthread_create(&workers[i], NULL, worker_entry, NULL);
	}


	if(S_ISDIR(info.st_mode)){
		find_dir(path, string);
		for(int i=0;i<WORKER_NUMBER;i++){
			task item;
			item.is_end = 1;
			put_task(&item);
		}
	}
	else
		find_file(path, string);
	for(int i=0;i<WORKER_NUMBER;i++){
		pthread_join(workers[i], NULL);
	}
	return 0;
}

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

相关阅读:
C语言操作符详解
 支付交易-交易分发器(二)
Docker-compose安装
 C语言程序设计笔记（浙大翁恺版）第十二周：程序结构
 Open3D(C++) 计算点云的法向量
 图像处理用什么神经网络,神经网络如何识别图像
 关于联想笔记本插上有线耳机没有声音的经历（一）
TCP套接字【网络】
25. Python 字符串的切片方法
 【HMS core】【IAP Kit】【FAQ】华为支付典型问题集
原文地址：https://blog.csdn.net/changyana/article/details/125566527

NUAA操作系统OS实验及上机考试记录

文章目录

exam

job3

1. myecho.c

2. mycat.c

3. mycp.c

4. mysys.c

5. sh1.c

job4

1. myls.c

2. mytree.c

job5

1.sh2.c

job7

1. pi1.c

2. pi2.c

3. sort.c

job8

1. pc.c

2. pp.c

job9

1. pc.c

2. pp.c

job10

1. sfind.c

2. pfind.c