操作系统实践课作业（南航）
文章目录
- 操作系统实践课作业（南航）
- 1. job2
- 1.1 main.c
- 1.2 math.c
- 1.3 Makefile
- 2. job3
- 2.1 myecho.c
- 2.2 mycat.c
- 2.3 mycp.c
- 2.4 mysys.c
- 2.5 sh1.c
- 3. job4
-
- 4. job5
-
- 5. job7
- 5.1 pi1.c
- 5.2 pi2.c
- 5.3 sort.c
- 6. job8
-
- 7. job9
-
实验环境：从Docker Hub中拉取了一个GCC的镜像，并基于该镜像创建了linux系统的容器。
1. job2
1.1 main.c
int min(int a, int b)
{
if(a < b)
return a;
else
return b;
}
int max(int a, int b)
{
if(a > b)
return a;
else
return b;
}
1.2 math.c
#include<stdio.h>
extern int max(int a, int b);
extern int min(int a, int b);
int main()
{
printf("min = %d\n", min(1, 2));
printf("max = %d\n", max(1, 2));
return 0;
}
1.3 Makefile
exe:main.o math.o
cc -o exe main.o math.o
main.o:main.c
cc -c main.c
math.o:math.c
cc -c math.c
clean:
rm exe *.o
2. job3
2.1 myecho.c
实现功能：
- myecho.c的功能与系统echo程序相同，接受命令行参数，并将参数打印出来
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
if (argc == 1)
{
printf("Error!\n");
exit(0);
}
for (int i = 1; i < argc; i++)
{
printf("%s ", argv[i]);
}
printf("\n");
}
输出如下：
root@12144f68020b:/os-practice/job3
Kint
root@12144f68020b:/os-practice/job3
aviod bananas close
2.2 mycat.c
实现功能：
- mycat.c的功能与系统cat程序相同
- mycat将指定的文件内容输出到屏幕
- 要求使用系统调用open/read/write/close实现
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
int fd;
if (argc != 2)
{
printf("There must be only one source path!\n");
return 0;
}
char *path = argv[1];
fd = open(path, O_RDONLY);
if (fd < 0)
{
printf("Open Error!\n");
}
char *content[1024];
fd = read(fd, content, 1024);
if (fd >= 0)
{
printf("%s", content);
}
else
{
printf("Read Error!\n");
}
close(fd);
return 0;
}
考虑到读取内容如果大于1024字节的话，该程序会存在一定的问题，故更改后的代码如下：
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
int fd;
if (argc != 2)
{
printf("There must be only one source path!\n");
return 0;
}
char *path = argv[1];
fd = open(path, O_RDONLY);
if (fd < 0)
{
printf("Open File Error!\n");
}
char *content[128];
int flag;
while ((flag = read(fd, content, 128)) > 0)
{
write(STDOUT_FILENO, content, flag);
}
close(fd);
return 0;
}
2.3 mycp.c
实现功能：
- mycp.c的功能与系统cp程序相同
- 将源文件复制到目标文件
- 要求使用系统调用open/read/write/close实现
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
int fd;
if (argc != 3)
{
printf("There must be only one source path and one destination path!\n");
return 0;
}
char *path = argv[1];
fd = open(path, O_RDONLY);
if (fd < 0)
{
printf("Open Error!\n");
}
char *content[1024];
fd = read(fd, content, 1024);
if (fd >= 0)
{
int cp_fd = open(argv[2], O_CREAT | O_RDWR | O_TRUNC);
cp_fd = write(cp_fd, content, fd);
if (cp_fd < 0)
{
printf("Write Error!\n");
}
close(cp_fd);
}
else
{
printf("Read Error!\n");
}
close(fd);
return 0;
}
对程序进行修改，修改后的程序如下：
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
int fd;
if (argc != 3)
{
printf("There must be only one source path and one destination path!\n");
return 0;
}
char *path = argv[1];
fd = open(path, O_RDONLY);
if (fd < 0)
{
printf("Open Error!\n");
}
char *content[128];
int flag;
int cp_fd = open(argv[2], O_CREAT | O_RDWR | O_TRUNC);
while ((flag = read(fd, content, 128)) > 0)
{
int cp_flag = write(cp_fd, content, flag);
if (cp_flag < 0)
{
printf("Write Error!\n");
}
}
close(fd);
close(cp_fd);
return 0;
}
2.4 mysys.c
实现功能：
- mysys的功能与系统函数system相同，要求用进程管理相关系统调用自己实现一遍
- 使用fork/exec/wait系统调用实现mysys
- 不能通过调用系统函数system实现mysys
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <string.h>
void mysys(char *command)
{
char c[100];
strcpy(c, command);
pid_t pid;
pid = fork();
char *argv[10];
int i = 0;
char *s;
if (pid == 0)
{
s = strtok(c, " ");
argv[i] = s;
while (s != NULL)
{
i++;
s = strtok(NULL, " ");
argv[i] = s;
}
argv[i] = NULL;
int error = execvp(argv[0], argv);
if (error < 0)
perror("execvp");
printf("End!!!\n");
}
wait(NULL);
}
int main()
{
printf("---------------------------------------\n");
mysys("echo HELLO WORLD");
printf("---------------------------------------\n");
mysys("ls /");
printf("---------------------------------------\n");
mysys("ls");
printf("---------------------------------------\n");
return 0;
}
这里我规定了命令长度不超过100字符，健壮性不佳，修改后的代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <string.h>
void mysys(char *command)
{
pid_t pid;
if (command == NULL)
{
printf("Error: wrong command!");
exit(0);
}
pid = fork();
if (pid == 0)
{
int error = execl("/bin/sh", "sh", "-c", command, NULL);
if (error < 0)
{
perror("execl");
}
}
wait(NULL);
}
int main()
{
printf("---------------------------------------\n");
mysys("echo HELLO WORLD");
printf("---------------------------------------\n");
mysys("ls /");
printf("---------------------------------------\n");
mysys("ls");
printf("---------------------------------------\n");
return 0;
}
输出如下：
root@12144f68020b:/os-practice/job3
---------------------------------------
HELLO WORLD
---------------------------------------
bin boot dev etc home lib lib64 media mnt opt os-practice proc root run sbin srv sys tmp usr var
---------------------------------------
mycat mycat.c mycp mycp.c myecho myecho.c mysys mysys.c mysys1 mysys1.c passwd.bak sh1 sh1.c
---------------------------------------
2.5 sh1.c
实现功能：
- 该程序读取用户输入的命令，调用函数mysys(上一个作业)执行用户的命令
- 实现内置命令cd、pwd、exit
#include <unistd.h>
int chdir(const char *path);
char *getcwd( char *buffer, int maxlen );
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/types.h>
#include <string.h>
void mysys(char *command)
{
char c[100];
strcpy(c, command);
char *argv[10];
int i = 0;
char *s;
s = strtok(c, " ");
argv[i] = s;
while (s != NULL)
{
i++;
s = strtok(NULL, " ");
argv[i] = s;
}
argv[i] = NULL;
for (int j = 0; j < strlen(argv[i - 1]); j++)
{
if (argv[i - 1][j] == '\n')
{
argv[i - 1][j] = '\0';
break;
}
}
if (argv[0][0] == '\0')
{
return;
}
if (strcmp(argv[0], "exit") == 0)
{
exit(0);
}
if (strcmp(argv[0], "cd") == 0)
{
if (chdir(argv[1]))
{
printf("sh1=>cd:no such directory %s\n", argv[1]);
}
return;
}
if (strcmp(argv[0], "pwd") == 0)
{
char buf[100];
printf("%s\n", getcwd(buf, sizeof(buf)));
return;
}
pid_t pid;
pid = fork();
if (pid == 0)
{
int error = execvp(argv[0], argv);
if (error < 0)
perror("execvp");
printf("End!!!\n");
return;
}
wait(NULL);
}
int main()
{
while (1)
{
printf("> ");
char command[100];
fgets(command, 100, stdin);
mysys(command);
}
return 0;
}
存在的问题：如果输入的指令格式正确没问题，但是如果在输入错误命令后执行exit不会马上退出。修改后代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/types.h>
#include <string.h>
extern void mysys(char *command);
int main(int argc, char *argv[])
{
while (1)
{
printf("> ");
char command[100] = {0};
int i = 0;
char c;
do
{
c = getchar();
command[i] = c;
i++;
} while (c != '\n');
command[i - 1] = '\0';
if (command[0] == '\0')
{
continue;
}
char c1[100];
strcpy(c1, command);
char *order = strtok(c1, " ");
if (!strcmp(order, "exit"))
{
exit(0);
}
else if (!strcmp(order, "pwd"))
{
char *path = getcwd(NULL, 0);
printf("%s\n", path);
free(path);
}
else if (command[0] == 'c' && command[1] == 'd' && command[2] == ' ')
{
char cd_path[100]={0};
strcpy(cd_path,command+3);
if (chdir(cd_path))
{
printf("sh1=>cd:no such directory %s\n", argv[1]);
}else{
perror("cd");
}
}else{
mysys(command);
}
}
return 0;
}
调用mysys.c中的mysys函数，首先将其主函数注释掉。需要进行重定位，用extern引用外部函数mysys，并进行静态库链接。
cc -c mysys.c
cc -c sh1.c
cc -o sh1 sh1.o mysys.o
输出如下：
root@12144f68020b:/os-practice/job3
> echo a b c
a b c
> 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
sys:x:3:3:sys:/dev:/usr/sbin/nologin
sync:x:4:65534:sync:/bin:/bin/sync
games:x:5:60:games:/usr/games:/usr/sbin/nologin
man:x:6:12:man:/var/cache/man:/usr/sbin/nologin
lp:x:7:7:lp:/var/spool/lpd:/usr/sbin/nologin
mail:x:8:8:mail:/var/mail:/usr/sbin/nologin
news:x:9:9:news:/var/spool/news:/usr/sbin/nologin
uucp:x:10:10:uucp:/var/spool/uucp:/usr/sbin/nologin
proxy:x:13:13:proxy:/bin:/usr/sbin/nologin
www-data:x:33:33:www-data:/var/www:/usr/sbin/nologin
backup:x:34:34:backup:/var/backups:/usr/sbin/nologin
list:x:38:38:Mailing List Manager:/var/list:/usr/sbin/nologin
irc:x:39:39:ircd:/run/ircd:/usr/sbin/nologin
gnats:x:41:41:Gnats Bug-Reporting System (admin):/var/lib/gnats:/usr/sbin/nologin
nobody:x:65534:65534:nobody:/nonexistent:/usr/sbin/nologin
_apt:x:100:65534::/nonexistent:/usr/sbin/nologin
> pwd
/os-practice/job3
> cd ..
> pwd
/os-practice
> exit
root@12144f68020b:/os-practice/job3
3. job4
3.1 myls.c
DIR *dp;
struct dirent *dirp;
struct __dirstream
{
void *__fd;
char *__data;
int __entry_data;
char *__ptr;
int __entry_ptr;
size_t __allocation;
size_t __size;
__libc_lock_define (, __lock)
};
typedef struct __dirstream DIR;
struct dirent
{
long d_ino;
off_t d_off;
unsigned short d_reclen;
unsigned char d_type;
char d_name [NAME_MAX+1];
}
了解三个函数的功能：
- opendir(name)：用来打开参数
name指定的目录，打开成功则返回DIR*形态的目录流，和open()类似，接下来对目录的读取和搜索都要使用此返回值；打开失败则返回NULL。
#include<dirent.h>
DIR * opendir(const char * name);
- readdir(dir)：返回参数dir目录流的下个目录进入点。
#include<dirent.h>
struct dirent * readdir(DIR * dir);
- closedir(dir)：关闭参数dir所指的目录流。关闭成功则返回0，失败返回-1。
#include <sys/types.h>
#include <dirent.h>
int closedir(DIR *dir);
实现代码如下：
#include <stdio.h>
#include <dirent.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
void myls(DIR *dp)
{
struct dirent *dirp;
while ((dirp = readdir(dp)) != NULL)
{
if (!strcmp(dirp->d_name, ".") || !strcmp(dirp->d_name, ".."))
{
continue;
}
printf("%s ", dirp->d_name);
}
printf("\n");
closedir(dp);
}
int main(int argc, char *argv[])
{
DIR *dp;
if (argc == 1)
{
char path[100];
getcwd(path, sizeof(path));
dp = opendir(path);
myls(dp);
}
else if (argc == 2)
{
dp = opendir(argv[1]);
if (dp == NULL)
{
char *str1 = "myls: cannot access '";
char *str2 = "'";
char *message = (char *)malloc(strlen(str1) + strlen(str2) + strlen(argv[1]));
strcpy(message, str1);
strcat(message, argv[1]);
strcat(message, str2);
perror(message);
exit(1);
}
myls(dp);
}
else
{
for (int i = 1; i < argc; i++)
{
printf("%s:\n", argv[i]);
dp = opendir(argv[i]);
if (dp == NULL)
{
char *str1 = "myls: cannot access '";
char *str2 = "'";
char *message = (char *)malloc(strlen(str1) + strlen(str2) + strlen(argv[i]));
strcpy(message, str1);
strcat(message, argv[i]);
strcat(message, str2);
perror(message);
exit(1);
}
myls(dp);
if (i != argc - 1)
{
printf("\n");
}
}
}
return 0;
}
输出如下：
root@8596f4026c53:/os-practice/job4
myls test myls.c
root@8596f4026c53:/os-practice/job4
myls myls.c test
root@8596f4026c53:/os-practice/job4
.:
myls test myls.c
test:
a b c
root@8596f4026c53:/os-practice/job4
.:
myls myls.c test
test:
a b c
root@8596f4026c53:/os-practice/job4
3.2 mytree.c
思路：
认识stat函数和stat结构体：
- stat函数：用来获取指定路径的文件或者文件夹的信息。
#include <sys/types.h>
#include <sys/stat.h>
int stat(const char *filename, struct stat *buf);
- stat结构体：文件（夹）信息结构体，可以通过stat函数获取的所有相关信息。
struct stat
{
mode_t st_mode;
ino_t st_ino;
dev_t st_dev;
dev_t st_rdev;
nlink_t st_nlink;
uid_t st_uid;
gid_t st_gid;
off_t st_size;
time_t st_atime;
time_t st_mtime;
time_t st_ctime;
blksize_t st_blksize;
blkcnt_t st_blocks;
};
S_ISREG(st_mode)
S_ISDIR(st_mode)
S_ISLINGK(st_mode)
S_ISCHR(st_mode)
S_ISBLK(s3e)
S_ISSOCK(st_mode)
#include <iostream>
#include <ctime>
#include <sys/types.h>
#include <sys/stat.h>
using namespace std;
int main()
{
struct stat buf;
int result;
result = stat("./Makefile", &buf);
if (result != 0)
{
perror("Failed");
}
else
{
cout << "size of the file in bytes: " << buf.st_size << endl;
cout << "time of creation of the file: " << ctime(&buf.st_ctime) << endl;
cout << "time of last modification of the file: " << ctime(&buf.st_mtime) << endl;
cout << "time of last access of the file: " << ctime(&buf.st_atime) << endl;
}
return 0;
}
再了解一下sprintf函数的用法：
int sprintf(char *str, const char *format, ...)
首先输入路径，缺省即获取当前路径。类似DFS深度搜索：
- 打开输入路径，获取路径下的文件列表，依次打印文件名；
- 对文件名进行判断，如果是目录类型继续深搜，深度+1，并格式化输出文件名；
- deep深度参数用于打印缩进；
- files，dirs变量分别标识文件数和目录数。
代码中并没有使用到stat函数和stat结构体，就当是额外学习了。
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <dirent.h>
#include <stdlib.h>
int dirs = 0, files = 0;
void mytree(char *path, int deep)
{
DIR *dp;
struct dirent *dirp;
char sub_dir[1024];
dp = opendir(path);
if (dp == NULL)
{
char *str1 = " [error opening dir]";
char *message = (char *)malloc(strlen(str1) + strlen(path));
strcpy(message, path);
strcat(message, str1);
perror(message);
return ;
}
while ((dirp = readdir(dp)) != NULL)
{
if (!strcmp(dirp->d_name, ".") || !strcmp(dirp->d_name, ".."))
{
continue;
}
for (int i = 0; i < deep; i++)
{
printf(" ");
}
if (dirp->d_type == DT_DIR)
{
dirs++;
printf("|-- %s\n", dirp->d_name);
sprintf(sub_dir, "%s/%s", path, dirp->d_name);
mytree(sub_dir, deep + 1);
}
else
{
files++;
printf("|-- %s\n", dirp->d_name);
}
}
closedir(dp);
}
int main(int argc, char *argv[])
{
if (argc == 1)
{
char path[1024];
getcwd(path, sizeof(path));
printf(".\n");
mytree(path, 0);
}
else
{
for (int i = 1; i < argc; i++)
{
printf("%s\n", argv[i]);
mytree(argv[i], 0);
}
}
printf("\n%d directories, %d files.\n", dirs, files);
return 0;
}
输出如下：
root@8596f4026c53:/os-practice/job4
.
|-- myls
|-- mytree
|-- test
|-- a
|-- b
|-- z
|-- y
|-- x
|-- c
|-- myls.c
|-- mytree.c
2 directories, 9 files.
root@8596f4026c53:/os-practice/job4
.
|-- myls
|-- myls.c
|-- mytree
|-- mytree.c
`-- test
|-- a
|-- b
| |-- x
| |-- y
| `-- z
`-- c
2 directories, 9 files
root@8596f4026c53:/os-practice/job4
.
|-- myls
|-- mytree
|-- test
|-- a
|-- b
|-- z
|-- y
|-- x
|-- c
|-- myls.c
|-- mytree.c
test
|-- a
|-- b
|-- z
|-- y
|-- x
|-- c
3 directories, 14 files.
root@8596f4026c53:/os-practice/job4
.
|-- myls
|-- myls.c
|-- mytree
|-- mytree.c
`-- test
|-- a
|-- b
| |-- x
| |-- y
| `-- z
`-- c
test
|-- a
|-- b
| |-- x
| |-- y
| `-- z
`-- c
3 directories, 14 files
4. job5
4.1 sh2.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>
#include <string.h>
int redirect(int i, char command[], int flag)
{
char file[100];
int k = 0, j, fd;
for (j = i; command[j] != ' ' && command[j] != '\0'; j++)
{
file[k++] = command[j];
}
file[k] = 0;
if (flag == 0)
{
fd = open(file, O_CREAT | O_RDWR, 0666);
dup2(fd, 1);
}
else if (flag == 1)
{
fd = open(file, O_CREAT | O_RDWR, 0666);
dup2(fd, 0);
}
else if (flag == 2)
{
fd = open(file, O_CREAT | O_APPEND, 0666);
dup2(fd, 1);
}
close(fd);
return j - 1;
}
void check(char *command)
{
for (int i = 0; command[i] != '\0'; i++)
{
if (command[i] == '>' && command[i + 1] != ' ' && command[i + 1] != '>')
{
i = redirect(i + 1, command, 0);
}
else if (command[i] == '>' && command[i + 1] == ' ')
{
i = redirect(i + 2, command, 0);
}
else if (command[i] == '<' && command[i + 1] != ' ')
{
i = redirect(i + 1, command, 1);
}
else if (command[i] == '<' && command[i + 1] == ' ')
{
i = redirect(i + 2, command, 1);
}
else if (command[i] == '>' && command[i + 1] == '>' && command[i + 1] != ' ')
{
i = redirect(i + 2, command, 2);
}
else if (command[i] == '>' && command[i + 1] == '>' && command[i + 2] == ' ')
{
i = redirect(i + 3, command, 2);
}
}
int error = execl("/bin/sh", "sh", "-c", command, NULL);
if (error < 0)
{
perror("execl");
}
}
void mysh2(char *command)
{
char c1[100];
strcpy(c1, command);
char *order = strtok(c1, " ");
if (!strcmp(order, "exit"))
{
exit(0);
}
else if (!strcmp(order, "pwd"))
{
char *path = getcwd(NULL, 0);
printf("%s\n", path);
free(path);
}
else if (command[0] == 'c' && command[1] == 'd' && command[2] == ' ')
{
char cd_path[100] = {0};
strcpy(cd_path, command + 3);
if (chdir(cd_path) == -1)
{
printf("sh1: cd: %s No such file or directory\n", cd_path);
}
}
else
{
pid_t pid;
pid = fork();
if (pid == 0)
{
check(command);
}
wait(NULL);
}
}
int main(int argc, char *argv[])
{
while (1)
{
printf("> ");
char command[100] = {0};
int i = 0;
char c;
do
{
c = getchar();
command[i] = c;
i++;
} while (c != '\n');
command[i - 1] = '\0';
if (command[0] == '\0')
{
continue;
}
mysh2(command);
}
return 0;
}
需要注意的是strtok的函数使用，下面对字符串的写法会导致内存错误，因为在C语言中字符串常量不可以修改。
char *line="echo abc xyz >log"
char *word;
word=strtok(line," ")
修改可以这样写。
char line[]="echo abc xyz >log";
int len=strlen("echo abc xyz >log")+1;
char line[len+1];
strcpy(line,"echo abc xyz >log");
strtok的标准用法，
word=strtok(line," ");
while(word!=NULL){
printf("[%s]\n",word);
word=strtok(NULL," ");
}
5. job7
5.1 pi1.c
使用2个线程根据莱布尼兹级数计算PI：
- 莱布尼兹级数公式: 1 - 1/3 + 1/5 - 1/7 + 1/9 - … = PI/4
- 主线程创建1个辅助线程
- 主线程计算级数的前半部分
- 辅助线程计算级数的后半部分
- 主线程等待辅助线程运行結束后,将前半部分和后半部分相加
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#define HALF 300
double worker_output;
double master_output;
void *worker(void *arg)
{
double j;
worker_output = 0;
for (int i = 1; i <= HALF; i++)
{
j = i;
if (i % 2 == 0)
worker_output -= 1 / (2 * j - 1);
else
worker_output += 1 / (2 * j - 1);
}
return NULL;
}
void master()
{
double j;
master_output = 0;
for (int i = HALF + 1; i <= 2 * HALF; i++)
{
j = i;
if (i % 2 == 0)
master_output -= 1 / (2 * j - 1);
else
master_output += 1 / (2 * j - 1);
}
}
int main()
{
pthread_t worker_tid;
pthread_create(&worker_tid, NULL, worker, NULL);
master();
pthread_join(worker_tid, NULL);
double PI = (worker_output + master_output) * 4;
printf("master_output = %f, worker_output = %f, PI= %f\n", master_output, worker_output, PI);
return 0;
}
5.2 pi2.c
使用N个线程根据莱布尼兹级数计算PI：
- 与上一题类似，但本题更加通用化，能适应N个核心
- 主线程创建N个辅助线程
- 每个辅助线程计算一部分任务，并将结果返回
- 主线程等待N个辅助线程运行结束，将所有辅助线程的结果累加
- 本题要求 1: 使用线程参数，消除程序中的代码重复
- 本题要求 2: 不能使用全局变量存储线程返回值
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <stdlib.h>
#define NR_TOTAL 600
#define NR_CPU 20
#define NR_SIZE (NR_TOTAL / NR_CPU)
double PI;
struct parameter
{
int start;
int end;
};
struct result
{
double sum;
};
void *compute(void *arg)
{
struct parameter *param = (struct parameter *)arg;
struct result *result;
double output;
double j;
for (int i = param->start; i < param->end; i++)
{
j = i;
if (i % 2 == 0)
{
output -= 1 / (2 * j - 1);
}
else
{
output += 1 / (2 * j - 1);
}
}
result = malloc(sizeof(struct result));
result->sum = output;
}
int main()
{
pthread_t workers[NR_CPU];
struct parameter params[NR_CPU];
for (int i = 0; i < NR_CPU; i++)
{
struct parameter *param;
param = ¶ms[i];
param->start = i * NR_SIZE + 1;
param->end = (i + 1) * NR_SIZE + 1;
pthread_create(&workers[i], NULL, compute, param);
}
double sum = 0;
for (int i = 0; i < NR_CPU; i++)
{
struct result *result;
pthread_join(workers[i], (void **)&result);
sum += result->sum;
free(result);
}
PI = 4 * sum;
printf("PI = %f\n", PI);
return 0;
}
5.3 sort.c
多线程排序：
- 主线程创建两个辅助线程
- 辅助线程1使用选择排序算法对数组的前半部分排序
- 辅助线程2使用选择排序算法对数组的后半部分排序
- 主线程等待辅助线程运行結束后,使用归并排序算法归并子线程的计算结果
- 本题要求 1: 使用线程参数，消除程序中的代码重复
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
int array[10] = {41, 67, 34, 58, 69, 24, 78, 58, 62, 64};
int sorted[10];
#define NR_TOTAL 10
#define NR_CPU 2
#define NR_SIZE (NR_TOTAL / NR_CPU)
struct parameter
{
int *array;
int start;
int end;
};
void *sort(void *arg)
{
struct parameter *param = (struct parameter *)arg;
int tmp;
int min;
for (int i = param->start; i < param->end; i++)
{
min = i;
for (int j = i + 1; j < param->end; j++)
{
if (param->array[min] > param->array[j])
min = j;
}
if (min != i)
{
tmp = param->array[i];
param->array[i] = param->array[min];
param->array[min] = tmp;
}
}
return 0;
}
void Merge(int *array)
{
int i = 0, j = NR_TOTAL / 2, k = 0;
while (i < NR_TOTAL / 2 && j < NR_TOTAL)
{
if (array[i] < array[j])
sorted[k++] = array[i++];
else
sorted[k++] = array[j++];
}
while (i < NR_TOTAL / 2)
sorted[k++] = array[i++];
while (j < NR_TOTAL)
sorted[k++] = array[j++];
}
int main()
{
pthread_t workers[NR_CPU];
struct parameter params[NR_CPU];
struct parameter *param;
for (int i = 0; i < NR_CPU; i++)
{
param = ¶ms[i];
param->array = array;
param->start = i * NR_SIZE;
param->end = (i + 1) * NR_SIZE;
pthread_create(&workers[i], NULL, sort, param);
}
for (int i = 0; i < NR_CPU; i++)
{
pthread_join(workers[i], NULL);
}
Merge(array);
for (int i = 0; i < NR_TOTAL; i++)
printf("%d ", sorted[i]);
printf("\n");
return 0;
}
6. job8
6.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
..
设置两个缓冲区buffer1和buffer2，同时对两个缓冲区设置互斥变量mutex1和mutex2，以及条件变量wait_empty_buffer1、wait_full_buffer1、wait_empty_buffer2、wait_full_buffer2。
计算者线程需要对buffer1和buffer2进行操作，前半部分参考消费者，后半部分参考生产者。
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#define CAPACITY 4
int buffer1[CAPACITY];
int buffer2[CAPACITY];
int in1, in2;
int out1, out2;
int buffer_is_empty(int *in, int *out)
{
return *in == *out;
}
int buffer_is_full(int *in, int *out)
{
return (*in + 1) % CAPACITY == *out;
}
int get_item(int *out, int type)
{
int item;
if (type == 1)
{
item = buffer1[*out];
}
else
{
item = buffer2[*out];
}
*out = (*out + 1) % CAPACITY;
return item;
}
void put_item(int item, int *in, int type)
{
if (type == 1)
{
buffer1[*in] = item;
}
else
{
buffer2[*in] = item;
}
*in = (*in + 1) % CAPACITY;
}
pthread_mutex_t mutex1;
pthread_mutex_t mutex2;
pthread_cond_t wait_empty_buffer1;
pthread_cond_t wait_full_buffer1;
pthread_cond_t wait_empty_buffer2;
pthread_cond_t wait_full_buffer2;
#define ITEM_COUNT (CAPACITY * 2)
void *produce(void *arg)
{
int i, item, type = 1;
for (i = 0; i < ITEM_COUNT; i++)
{
pthread_mutex_lock(&mutex1);
while (buffer_is_full(&in1, &out1))
pthread_cond_wait(&wait_empty_buffer1, &mutex1);
item = 'a' + i;
put_item(item, &in1, type);
printf("produce item: %c\n", item);
pthread_cond_signal(&wait_full_buffer1);
pthread_mutex_unlock(&mutex1);
}
return NULL;
}
void *compute(void *arg)
{
int i, item, type;
for (i = 0; i < ITEM_COUNT; i++)
{
type = 1;
pthread_mutex_lock(&mutex1);
while (buffer_is_empty(&in1, &out1))
pthread_cond_wait(&wait_full_buffer1, &mutex1);
item = get_item(&out1, type);
pthread_cond_signal(&wait_empty_buffer1);
pthread_mutex_unlock(&mutex1);
type = 2;
pthread_mutex_lock(&mutex2);
while (buffer_is_full(&in2, &out2))
pthread_cond_wait(&wait_empty_buffer2, &mutex2);
item -= 32;
put_item(item, &in2, type);
printf("\tcompute item: %c:%c\n", item + 32, item);
pthread_cond_signal(&wait_full_buffer2);
pthread_mutex_unlock(&mutex2);
}
}
void *consume(void *arg)
{
int i, item, type = 2;
for (i = 0; i < ITEM_COUNT; i++)
{
pthread_mutex_lock(&mutex2);
while (buffer_is_empty(&in2, &out2))
pthread_cond_wait(&wait_full_buffer2, &mutex2);
item = get_item(&out2, type);
printf("\t\tconsume item: %c\n", item);
pthread_cond_signal(&wait_empty_buffer2);
pthread_mutex_unlock(&mutex2);
}
}
int main()
{
pthread_t compute_tid;
pthread_t consume_tid;
pthread_mutex_init(&mutex1, NULL);
pthread_mutex_init(&mutex2, NULL);
pthread_cond_init(&wait_empty_buffer1, NULL);
pthread_cond_init(&wait_full_buffer1, NULL);
pthread_cond_init(&wait_empty_buffer2, NULL);
pthread_cond_init(&wait_full_buffer2, NULL);
pthread_create(&compute_tid, NULL, compute, NULL);
pthread_create(&consume_tid, NULL, consume, NULL);
produce(NULL);
pthread_join(consume_tid, NULL);
pthread_join(compute_tid, NULL);
return 0;
}
6.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
...
定义一个状态变量status，为1表示ping进程正在运行，为0表示pong进程正在运行。ping线程和pong线程是一个相互协作的关系，ping线程执行之后，才执行pong线程，反之也是如此。
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
int status = 1;
#define COUNT 10
pthread_mutex_t mutex;
pthread_cond_t wait_ping;
pthread_cond_t wait_pong;
void *ping(void *arg)
{
int i = COUNT;
while (i--)
{
pthread_mutex_lock(&mutex);
while (status == 0)
pthread_cond_wait(&wait_pong, &mutex);
printf("ping\n");
p = 0;
pthread_cond_signal(&wait_ping);
pthread_mutex_unlock(&mutex);
}
return NULL;
}
void *pong(void *arg)
{
int i = COUNT;
while (i--)
{
pthread_mutex_lock(&mutex);
while (status == 1)
pthread_cond_wait(&wait_ping, &mutex);
printf("pong\n");
p = 1;
pthread_cond_signal(&wait_pong);
pthread_mutex_unlock(&mutex);
}
return NULL;
}
int main()
{
pthread_t pong_tid;
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&wait_ping, NULL);
pthread_cond_init(&wait_pong, NULL);
pthread_create(&pong_tid, NULL, pong, NULL);
ping(NULL);
pthread_join(pong_tid, NULL);
return 0;
}
7. job9
7.1 pc.c
使用信号量解决生产者、计算者、消费者问题，功能同6.1
同步关系：
- 生产者、计算者共享一个初始为空、大小为n的缓冲区1。
- 计算者、消费者共享一个初始为空、大小为n的缓冲区2。
- 只有缓冲区没满时，生产者（计算者）才能把产品放入缓冲区，否则必须等待。
- 只有缓冲区不空时，消费者（计算者）才能从中取出产品，否则必须等待。
互斥关系：
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#define CAPACITY 4
int buffer1[CAPACITY];
int buffer2[CAPACITY];
int in1, in2;
int out1, out2;
int get_item(int *out, int type)
{
int item;
if (type == 1)
item = buffer1[*out];
else
item = buffer2[*out];
*out = (*out + 1) % CAPACITY;
return item;
}
void put_item(int item, int *in, int type)
{
if (type == 1)
buffer1[*in] = item;
else
buffer2[*in] = item;
*in = (*in + 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 mutex_sema1;
sema_t mutex_sema2;
sema_t empty_buffer1_sema;
sema_t empty_buffer2_sema;
sema_t full_buffer1_sema;
sema_t full_buffer2_sema;
#define ITEM_COUNT (CAPACITY * 2)
void *produce()
{
int i, item, type = 1;
for (i = 0; i < ITEM_COUNT; i++)
{
sema_wait(&empty_buffer1_sema);
sema_wait(&mutex_sema1);
item = i + 'a';
put_item(item, &in1, type);
printf("produce item: %c\n", item);
sema_signal(&mutex_sema1);
sema_signal(&full_buffer1_sema);
}
}
void *compute(void *arg)
{
int i, item, type;
for (i = 0; i < ITEM_COUNT; i++)
{
type = 1;
sema_wait(&full_buffer1_sema);
sema_wait(&mutex_sema1);
item = get_item(&out1, type);
sema_signal(&mutex_sema1);
sema_signal(&empty_buffer1_sema);
type = 2;
sema_wait(&empty_buffer2_sema);
sema_wait(&mutex_sema2);
item -= 32;
put_item(item, &in2, type);
printf("\tcompute item: %c:%c\n", item + 32, item);
sema_signal(&mutex_sema2);
sema_signal(&full_buffer2_sema);
}
return NULL;
}
void *consume(void *arg)
{
int i, item, type = 2;
for (i = 0; i < ITEM_COUNT; i++)
{
sema_wait(&full_buffer2_sema);
sema_wait(&mutex_sema2);
item = get_item(&out2, type);
printf("\t\tconsume item: %c\n", item);
sema_signal(&mutex_sema2);
sema_signal(&empty_buffer2_sema);
}
return NULL;
}
int main()
{
pthread_t consumer_tid;
pthread_t computer_tid;
sema_init(&mutex_sema1, 1);
sema_init(&mutex_sema2, 1);
sema_init(&empty_buffer1_sema, CAPACITY);
sema_init(&empty_buffer2_sema, CAPACITY);
sema_init(&full_buffer1_sema, 0);
sema_init(&full_buffer2_sema, 0);
pthread_create(&consumer_tid, NULL, consume, NULL);
pthread_create(&computer_tid, NULL, compute, NULL);
produce(NULL);
pthread_join(consumer_tid, NULL);
pthread_join(computer_tid, NULL);
return 0;
}
7.2 pp.c
使用信号量实现 ping-pong 问题，功能同6.2
不需要访问临界区，而是进行状态的转化。故设置一个状态变量status，为1表示ping进程，为0表示pong进程。
#include <stdio.h>
#include <pthread.h>
#define COUNT 100
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, int status)
{
pthread_mutex_lock(&sema->mutex);
while (sema->value != status)
{
pthread_cond_wait(&sema->cond, &sema->mutex);
}
pthread_mutex_unlock(&sema->mutex);
}
void sema_signal(sema_t *sema, int status)
{
pthread_mutex_lock(&sema->mutex);
sema->value = status;
pthread_cond_signal(&sema->cond);
pthread_mutex_unlock(&sema->mutex);
}
sema_t mutex_sema;
void *ping(void *arg)
{
int i = COUNT;
while (i--)
{
sema_wait(&mutex_sema, 1);
printf("ping\n");
sema_signal(&mutex_sema, 0);
}
}
void *pong(void *arg)
{
int i = COUNT;
while (i--)
{
sema_wait(&mutex_sema, 0);
printf("pong\n");
sema_signal(&mutex_sema, 1);
}
}
int main()
{
pthread_t pong_tid;
sema_init(&mutex_sema, 0);
pthread_create(&pong_tid, NULL, pong, NULL);
ping(NULL);
pthread_join(pong_tid, NULL);
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
