操作系统实验

操作系统►基础 评论

考试

  • 多线程+多进程api使用
  • scanf不用，不用格式化输出
  • 时间段提交特定题目
  • 自己电脑

Task 1 熟悉Linux

详见博客 Linux操作手册

Task 2 文件读写

2.1 echo

  • myecho.c的功能与系统echo程序相同
  • 接受命令行参数，并将参数打印出来
  • 运行程序后前面出现./myecho
    • argc 是指传入参数的个数，
    • argv[] 是一个指针数组，指向传递给程序的每个参数。第一个参数就是./myecho，所以从第二个参数开始打印即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main( int argc, char *argv[] ){
    if( argc == 0  ){
        printf("\n");
    }
    else{
        for( int i=1; i<argc; i++ ){
            printf("%s ", argv[i]);
        }
        printf("\n");
    }
    return 0;
}

2.2 cat

  • mycat.c的功能与系统cat程序相同
  • mycat将指定的文件内容输出到屏幕，例子如下：
  • 要求使用系统调用open/read/write/close实现
  • TODO
    • 文件内容超出maxn
    • cat+空格命令
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
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>

int main( int argc, char *argv[] ){
    if( argc == 0  ){
        printf("\n");
    }
    else{
        for( int i=1; i<argc; i++ ){
            int fd = open(argv[i], O_RDONLY);//只读
            if( fd==-1 ){
                printf("mycat: %s: No such file or directory\n", argv[i]);
            }
            else{
                char *buf;
                int maxn = 10000;//接受最大字符数
                buf = (char *)malloc(maxn);
                int rd = read(fd, buf, maxn);
                if( rd==-1 ){//读取失败
                    printf("Read failed!\n");
                    exit(0);
                }
                else if( rd==0 ){//读取到了文件末尾
                    break;
                }
                else{//正常读取
                    printf("%s", buf);
                    close(fd);//关闭文件
                }
            }
        }
    }
    return 0;
}

2.3 cp

  • mycp.c的功能与系统cp程序相同
  • 将源文件复制到目标文件，例子如下：
  • 要求使用系统调用open/read/write/close实现
  • TODO
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
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/fcntl.h>

int main( int argc, char *argv[] ){
    if( argc == 0  ){
        printf("\n");
    }
    else if( argc == 1 ){//无文件参数
        printf("mycp: missing file operand\nTry 'cp --help' for more information.\n");
    }
    else if( argc == 2 ){//只有1个文件参数
        printf("mycp: missing destination file operand after '%s'\n", argv[1]); 
        printf("Try 'cp --help' for more information.\n");
    }
    else if( argc == 3 ){//2个文件参数
        if( strcmp(argv[1], argv[2]) == 0 ){//文件名相同
            printf("mycp: '%s' and '%s' are the same file\n", argv[1], argv[2]);
            exit(0);
        }
        int s_fd = open(argv[1], O_RDONLY);//源文件-只读
        if( s_fd==-1 ){//文件不存在
            printf("mycp: cannot stat '%s': No such file or directory\n", argv[1]);
        }
        else{
            int t_fd = open(argv[2], O_RDWR | O_TRUNC | O_CREAT);//目标文件-创建+截断+读写
            char *buf;
            int maxn = 10000;//接受最大字符数
            buf = (char *)malloc(maxn);
            int s_rd = read(s_fd, buf, maxn);
            if( s_rd==-1 ){
                printf("Read failed!\n");
                exit(0);
            }
            else{
                // printf("%s", buf);
                int t_we = write(t_fd, buf, strlen(buf));//缓冲区大小
                if( t_we==-1 ){
                    printf("Write failed!\n");
                    exit(0);
                }
            }
            //关闭文件
            close(s_fd);
            close(t_fd);
            //新建的文件加权限
            chmod(argv[2], S_IRUSR|S_IWUSR|S_IXUSR|S_IRGRP|S_IWGRP|S_IXGRP|S_IROTH|S_IWOTH|S_IXOTH);
        }
    }
    else{
        printf("TODO\n");
    }
    return 0;
}

Task 3+ 多进程题目

3.1 mysys (Task3)

  • mysys的功能与系统函数system相同，要求用进程管理相关系统调用自己实现一遍
  • 使用fork/exec/wait系统调用实现mysys
  • 不能通过调用系统函数system实现mysys

题外话：vscode直接运行代码的话会出现问题，---------会在最后输出，在命令行运行并没问题。目前原因还不知道

5月15日：在实现Task5时发现功能已经具备，这才察觉到Task3写错了，原来使用execl("/bin/sh", "sh", "-c", command, NULL);，其实这与调用系统函数system无异。第一个参数应该指定可命令的路径，而不是直接指定sh。

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
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <string.h>

const int max_argc = 100;//命令参数最大数量

void mysys(char *command) {
    /* 实现该函数，该函数执行一条命令，并等待该命令执行结束 */
    // 命令为空
    if (command == NULL) {
        printf("Command is a null string!");
        return ; 
    }
    // 命令不为空
    char copy_command[strlen(command) + 1];//command的副本，避免影响传进来的参数
    strcpy(copy_command, command);
    pid_t pid;
    pid = fork();//创建子进程
    char *argv[max_argc];//命令参数列表
    char *tmp_arg;//切割字符串的临时变量
    int argc = 0;//命令参数数量
    if (pid == 0) {
        // execl("/bin/sh", "sh", "-c", command, NULL);
        //分割字符串
        tmp_arg = strtok(copy_command, " ");
        argv[argc++] = tmp_arg;
        while (tmp_arg && argc <= max_argc) {
            tmp_arg = strtok(NULL, " ");
            argv[argc++] = tmp_arg;
        }
        argv[argc] = NULL;//将最后一项设置为NULL指针
        execvp(argv[0], argv);
        exit(EXIT_FAILURE); // exec执行失败返回EXIT_FAILURE，执行成功这句就不执行
    } else {//父进程
        wait(NULL);//等待子进程结束
    }
    return ;
}

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

3.2 sh1.c (Task4)

  • 该程序读取用户输入的命令，调用函数mysys(上一个作业)执行用户的命令
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
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <string.h>

const int max_argc = 100;//命令参数最大数量

/* mysys.c实现的作业 */
void mysys(char *command) {
    /* 实现该函数，该函数执行一条命令，并等待该命令执行结束 */
    // 命令为空
    if (command == NULL) {
        printf("Command is a null string!");
        return ; 
    }
    // 命令不为空
    char copy_command[strlen(command) + 1];//command的副本，避免影响传进来的参数
    strcpy(copy_command, command);
    pid_t pid;
    pid = fork();//创建子进程
    char *argv[max_argc];//命令参数列表
    char *tmp_arg;//切割字符串的临时变量
    int argc = 0;//命令参数数量
    if (pid == 0) {
        // execl("/bin/sh", "sh", "-c", command, NULL);
        //分割字符串
        tmp_arg = strtok(copy_command, " ");
        argv[argc++] = tmp_arg;
        while (tmp_arg && argc <= max_argc) {
            tmp_arg = strtok(NULL, " ");
            argv[argc++] = tmp_arg;
        }
        argv[argc] = NULL;//将最后一项设置为NULL指针
        execvp(argv[0], argv);
        exit(EXIT_FAILURE); // exec执行失败返回EXIT_FAILURE，执行成功这句就不执行
    } else {//父进程
        wait(NULL);//等待子进程结束
    }
    return ;
}

int main() {
    while (1) {//循环输入
        printf("> ");
        const int maxn = 1000;//最长命令字符数
        char cmd[maxn];//命令
        // gets(cmd);
        scanf("%[^\n]%*c", cmd);//替代gets
        if (strcmp(cmd, "exit") == 0) {//终止sh
            break;
        }
        mysys(cmd);
    }
    return 0;
}

3.3 sh2.c (Task5)

  • 实现shell程序，要求在第1版的基础上，添加如下功能：实现文件重定向
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
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <string.h>
#include <sys/stat.h>
#include <fcntl.h>//open

const int max_argc = 100;//命令参数最大数量

void mysys(char *command) {
    /* 实现该函数，该函数执行一条命令，并等待该命令执行结束 */
    // 命令为空
    if (command == NULL) {
        printf("Command is a null string!");
        return ; 
    }
    // 命令不为空，将命令分为两部分
    char *cmd1, *cmd2;
    cmd1 = strtok(command, ">");
    cmd2 = strtok(NULL, ">");
    char copy_command[strlen(cmd1) + 1];//command的副本，避免影响传进来的参数
    strcpy(copy_command, cmd1);
    pid_t pid;
    pid = fork();//创建子进程
    char *argv[max_argc];//命令参数列表
    char *tmp_arg;//切割字符串的临时变量
    int argc = 0;//命令参数数量
    if (pid == 0) {
        // execl("/bin/sh", "sh", "-c", command, NULL);
        // 分割cmd1字符串
        tmp_arg = strtok(copy_command, " ");
        argv[argc++] = tmp_arg;
        while (tmp_arg && argc <= max_argc) {
            tmp_arg = strtok(NULL, " ");
            argv[argc++] = tmp_arg;
        }
        argv[argc] = NULL;//将最后一项设置为NULL指针
        // 重定向至cmd2所指的文件
        if (cmd2) {
            int fd;
            fd = open(cmd2, O_CREAT|O_RDWR, 0666); 
            dup2(fd, 1); 
            close(fd);
        }
        execvp(argv[0], argv);
        exit(EXIT_FAILURE); // exec执行失败返回EXIT_FAILURE，执行成功这句就不执行
    } else {//父进程
        wait(NULL);//等待子进程结束
    }
    return ;
}

int main() {
    while (1) {//循环输入
        printf("> ");
        const int maxn = 1000;//最长命令字符数
        char cmd[maxn];//命令
        // gets(cmd);
        scanf("%[^\n]%*c", cmd);//替代gets
        if (strcmp(cmd, "exit") == 0) {//终止sh
            break;
        }
        mysys(cmd);
    }
    return 0;
}

3.4 sh3.c (Task6)

实现shell程序，要求在第2版的基础上，添加如下功能：

  • 实现管道
  • 只要求连接两个命令，不要求连接多个命令
  • 不要求同时处理管道和重定向
  • 考虑如何实现管道和文件重定向，暂不做强制要求

此次作业遇到诸多问题，消费时间过长，主要是要静下来、沉下来，问题如下：

  1. strtok返回参数问题：返回值无法打印复制等，报segmentation fault错误， 需要加个头文件#include <string.h>
  2. pipe要在fork之前
  3. 初步实现的代码执行完cat /etc/passwd | wc -l后就立马退出程序，不知道是什么原因

为实现进阶功能，后续打算参考MIT6.828 homework2：shell进行实现。参考：

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
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <string.h>
#include <sys/stat.h>
#include <fcntl.h>//open

const int max_argc = 100;//命令参数最大数量
const int maxn = 1000;//最长命令字符数

void mysys(char *command) {
    /* 实现该函数，该函数执行一条命令，并等待该命令执行结束 */
    // 命令为空
    if (command == NULL) {
        printf("Command is a null string!");
        return ; 
    }
    // 命令不为空，将命令分为两部分
    char *cmd1 = NULL, *cmd2 = NULL;
    cmd1 = strtok(command, "|");
    cmd2 = strtok(NULL, "|");
    char copy_cmd1[maxn];//创建副本，避免影响传进来的参数
    char copy_cmd2[maxn];//创建副本，避免影响传进来的参数
    strcpy(copy_cmd1, cmd1);
    if (cmd2)
        strcpy(copy_cmd2, cmd2);
    // printf("%s\n%s\n", copy_cmd1, copy_cmd2);
    int fd[2];//位置在创建子进程之前
    pipe(fd);
    char *argv[max_argc];//命令参数列表
    char *tmp_arg;//切割字符串的临时变量
    int argc = 0;//命令参数数量
    
    pid_t pid;
    pid = fork();//创建子进程
    if (pid == 0) {
        // execl("/bin/sh", "sh", "-c", command, NULL);
        // 分割cmd1字符串
        tmp_arg = strtok(copy_cmd1, " ");
        argv[argc++] = tmp_arg;
        while (tmp_arg && argc <= max_argc) {
            tmp_arg = strtok(NULL, " ");
            argv[argc++] = tmp_arg;
        }
        argv[argc] = NULL;//将最后一项设置为NULL指针
        // 重定向至cmd2所指的文件
        if (cmd2) {
            dup2(fd[1], 1); 
            close(fd[0]);
            close(fd[1]);
        }
        execvp(argv[0], argv);
        exit(EXIT_FAILURE); // exec执行失败返回EXIT_FAILURE，执行成功这句就不执行
    } else {//父进程
        if (cmd2) {
            dup2(fd[0], 0); 
            close(fd[0]);
            close(fd[1]);
            // 分割cmd2字符串
            tmp_arg = strtok(copy_cmd2, " ");
            argv[argc++] = tmp_arg;
            while (tmp_arg && argc <= max_argc) {
                tmp_arg = strtok(NULL, " ");
                argv[argc++] = tmp_arg;
            }
            argv[argc] = NULL;//将最后一项设置为NULL指针
            execvp(argv[0], argv);
        }
        wait(NULL);//等待子进程结束
    }
    return ;
}

int main() {
    while (1) {//循环输入
        printf("> ");
        char cmd[maxn];//命令
        // gets(cmd);
        scanf("%[^\n]%*c", cmd);//替代gets
        if (strcmp(cmd, "exit") == 0) {//终止sh
            break;
        }
        mysys(cmd);
    }
    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
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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
/* MIT6.828 homework2：shell */
#include <assert.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

// Simplifed xv6 shell.

#define MAXARGS 10

// All commands have at least a type. Have looked at the type, the code
// typically casts the *cmd to some specific cmd type.
struct cmd {
  int type;  //  ' ' (exec), | (pipe), '<' or '>' for redirection
};
/* 执行指令 */
struct execcmd {
  int type;             // ' '
  char *argv[MAXARGS];  // arguments to the command to be exec-ed
};
/* 重定向指令 */
struct redircmd {
  int type;         // < or >
  struct cmd *cmd;  // the command to be run (e.g., an execcmd)
  char *file;       // the input/output file
  int flags;        // flags for open() indicating read or write
  int fd;           // the file descriptor number to use for the file
};
/* 管道指令 */
struct pipecmd {
  int type;           // |
  struct cmd *left;   // left side of pipe
  struct cmd *right;  // right side of pipe
};

int fork1(void);  // Fork but exits on failure.
struct cmd *parsecmd(char *);
/* 执行指令 */
// Execute cmd.  Never returns.
void runcmd(struct cmd *cmd) {
  int p[2], r;
  struct execcmd *ecmd;
  struct pipecmd *pcmd;
  struct redircmd *rcmd;

  if (cmd == 0) _exit(0);

  switch (cmd->type) {
    default:
      fprintf(stderr, "unknown runcmd\n");
      _exit(-1);

    case ' ':
      ecmd = (struct execcmd *)cmd;
      if (ecmd->argv[0] == 0) _exit(0);
    //   fprintf(stderr, "exec not implemented\n");
      // Your code here ...
      /* 处理执行失败的指令 */
      if (execv(ecmd->argv[0], ecmd->argv) == -1) {
        char mypath[20] = "/bin/";
        strcat(mypath, ecmd->argv[0]);
        if (execv(mypath, ecmd->argv) == -1) {
          strcpy(mypath, "/usr/bin/"); 
          strcat(mypath, ecmd->argv[0]);
          if (execv(mypath, ecmd->argv) == -1) {
            fprintf(stderr, "Command %s can't find\n", ecmd->argv[0]);
            _exit(0);
          }
        }
      }
      break;

    case '>':
    case '<':
    // 利用fd的顺序增长的特性，使用close()关闭标准I/O的fd，然后open()打开目标文件，
    // 此时文件的fd就会自动替换我们关闭的标准I/O的fd，也就实现了重定向。
      rcmd = (struct redircmd *)cmd;
      close(rcmd->fd);
    //   fprintf(stderr, "redir not implemented\n");
      // Your code here ...
      /* 处理重定向 */
      if (open(rcmd->file, rcmd->flags, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH) <
          0) {
        fprintf(stderr, "file %s can't find\n", rcmd->file);
        _exit(0);
      }
      runcmd(rcmd->cmd);//递归
      break;

    case '|':
      pcmd = (struct pipecmd *)cmd;
    //   fprintf(stderr, "pipe not implemented\n");
      // Your code here ...
      /* 处理管道 */
      if (pipe(p) < 0) {// 建立管道
        fprintf(stderr, "Fail to create a pipe\n");
        _exit(0);
      }
      // 将child 1的标准输出作为child 2的标准输入
      if (fork1() == 0) {
        // child 1:read from stdin(0), write to the right end of pipe(p[1])
        close(1);// 关闭标准输出
        dup(p[1]);// 复制管道中fd
        close(p[0]);
        close(p[1]);
        runcmd(pcmd->left);//递归执行左侧命令
      }

      if (fork1() == 0) {
        // child 2:read from the left end of pipe(p[0]), write to stdout(1)
        close(0);
        dup(p[0]);
        close(p[0]);
        close(p[1]);
        runcmd(pcmd->right);//递归执行右侧命令
      }
      // 关闭不需要的fd
      close(p[0]);
      close(p[1]);
      // 等待两个子进程结束
      wait(&r);
      wait(&r);
      break;
  }
  _exit(0);
}

/* 获取用户输入的命令 */
int getcmd(char *buf, int nbuf) {
  if (isatty(fileno(stdin))) fprintf(stdout, "> ");
  memset(buf, 0, nbuf);
  if (fgets(buf, nbuf, stdin) == 0) return -1;  // EOF
  if (strcmp(buf, "exit\n") == 0) return -1; //添加退出命令
  return 0;
}

int main(void) {
  static char buf[100];
  int fd, r;

  // Read and run input commands.
  while (getcmd(buf, sizeof(buf)) >= 0) {
    if (buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' ') {
      // Clumsy but will have to do for now.
      // Chdir has no effect on the parent if run in the child.
      buf[strlen(buf) - 1] = 0;  // chop \n
      if (chdir(buf + 3) < 0) fprintf(stderr, "cannot cd %s\n", buf + 3);
      continue;
    }
    if (fork1() == 0) runcmd(parsecmd(buf)); //创建一个shell进程的copy，并执行指令
    wait(&r); //shell进入等待状态
  }
  exit(0);
}

/* 新开进程 */
int fork1(void) {
  int pid;

  pid = fork();
  if (pid == -1) perror("fork");
  return pid;
}

struct cmd *execcmd(void) {
  struct execcmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = ' ';
  return (struct cmd *)cmd;
}

struct cmd *redircmd(struct cmd *subcmd, char *file, int type) {
  struct redircmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = type;
  cmd->cmd = subcmd;
  cmd->file = file;
  cmd->flags = (type == '<') ? O_RDONLY : O_WRONLY | O_CREAT | O_TRUNC;
  cmd->fd = (type == '<') ? 0 : 1; //判断重定向方向，方便后续关闭标准I/O的fd
  return (struct cmd *)cmd;
}

struct cmd *pipecmd(struct cmd *left, struct cmd *right) {
  struct pipecmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = '|';
  cmd->left = left;
  cmd->right = right;
  return (struct cmd *)cmd;
}

// Parsing

char whitespace[] = " \t\r\n\v";
char symbols[] = "<|>";

int gettoken(char **ps, char *es, char **q, char **eq) {
  char *s;
  int ret;

  s = *ps;
  while (s < es && strchr(whitespace, *s)) s++;
  if (q) *q = s;
  ret = *s;
  switch (*s) {
    case 0:
      break;
    case '|':
    case '<':
      s++;
      break;
    case '>':
      s++;
      break;
    default:
      ret = 'a';
      while (s < es && !strchr(whitespace, *s) && !strchr(symbols, *s)) s++;
      break;
  }
  if (eq) *eq = s;

  while (s < es && strchr(whitespace, *s)) s++;
  *ps = s;
  return ret;
}

int peek(char **ps, char *es, char *toks) {
  char *s;

  s = *ps;
  while (s < es && strchr(whitespace, *s)) s++;
  *ps = s;
  return *s && strchr(toks, *s);
}

struct cmd *parseline(char **, char *);
struct cmd *parsepipe(char **, char *);
struct cmd *parseexec(char **, char *);

// make a copy of the characters in the input buffer, starting from s through
// es. null-terminate the copy to make it a string.
char *mkcopy(char *s, char *es) {
  int n = es - s;
  char *c = malloc(n + 1);
  assert(c);
  strncpy(c, s, n);
  c[n] = 0;
  return c;
}
/* 解析命令 */
struct cmd *parsecmd(char *s) {
  char *es;
  struct cmd *cmd;

  es = s + strlen(s);
  cmd = parseline(&s, es);
  peek(&s, es, "");
  if (s != es) {
    fprintf(stderr, "leftovers: %s\n", s);
    exit(-1);
  }
  return cmd;
}

struct cmd *parseline(char **ps, char *es) {
  struct cmd *cmd;
  cmd = parsepipe(ps, es);
  return cmd;
}

struct cmd *parsepipe(char **ps, char *es) {
  struct cmd *cmd;

  cmd = parseexec(ps, es);
  if (peek(ps, es, "|")) {
    gettoken(ps, es, 0, 0);
    cmd = pipecmd(cmd, parsepipe(ps, es));
  }
  return cmd;
}

struct cmd *parseredirs(struct cmd *cmd, char **ps, char *es) {
  int tok;
  char *q, *eq;

  while (peek(ps, es, "<>")) {
    tok = gettoken(ps, es, 0, 0);
    if (gettoken(ps, es, &q, &eq) != 'a') {
      fprintf(stderr, "missing file for redirection\n");
      exit(-1);
    }
    switch (tok) {
      case '<':
        cmd = redircmd(cmd, mkcopy(q, eq), '<');
        break;
      case '>':
        cmd = redircmd(cmd, mkcopy(q, eq), '>');
        break;
    }
  }
  return cmd;
}

struct cmd *parseexec(char **ps, char *es) {
  char *q, *eq;
  int tok, argc;
  struct execcmd *cmd;
  struct cmd *ret;

  ret = execcmd();
  cmd = (struct execcmd *)ret;

  argc = 0;
  ret = parseredirs(ret, ps, es);
  while (!peek(ps, es, "|")) {
    if ((tok = gettoken(ps, es, &q, &eq)) == 0) break;
    if (tok != 'a') {
      fprintf(stderr, "syntax error\n");
      exit(-1);
    }
    cmd->argv[argc] = mkcopy(q, eq);
    argc++;
    if (argc >= MAXARGS) {
      fprintf(stderr, "too many args\n");
      exit(-1);
    }
    ret = parseredirs(ret, ps, es);
  }
  cmd->argv[argc] = 0;
  return ret;
}

Task 7+ 多线程题目

7.1 pi1.c (Task7)

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

  • 莱布尼兹级数公式: 1 - 1/3 + 1/5 - 1/7 + 1/9 - … = PI/4
  • 主线程创建1个辅助线程
  • 主线程计算级数的前半部分
  • 辅助线程计算级数的后半部分
  • 主线程等待辅助线程运行結束后,将前半部分和后半部分相加
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
#include <stdio.h>
#include <pthread.h>

#define NUMBER 0x7ffffff  //此值越大，PI越精确

double worker_output;

void *worker(void *arg) {
  for (int i = 1; i < NUMBER / 2; i++) {
    if (i % 2) {
      worker_output += 1.0 / (2 * i - 1);
    } else {
      worker_output -= 1.0 / (2 * i - 1);
    }
  }

  return NULL;
}

double master_output;

void master() {
  for (int i = NUMBER / 2 + 1; i <= NUMBER; i++) {
    if (i % 2) {
      master_output += 1.0 / (2 * i - 1);
    } else {
      master_output -= 1.0 / (2 * i - 1);
    }
  }
}

int main() {
  pthread_t worker_tid;
  double total, PI;

  pthread_create(&worker_tid, NULL, worker, NULL);
  master();
  pthread_join(worker_tid, NULL);
  total = master_output + worker_output;
  PI = total * 4;
  // printf("master_output = %lf, worker_output = %lf, total = %lf\n",
  // master_output, worker_output, total);
  printf("PI: %lf\n", PI);
  return 0;
}

7.2 pi2.c (Task7)

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

  • 与上一题类似，但本题更加通用化，能适应N个核心
  • 主线程创建N个辅助线程
  • 每个辅助线程计算一部分任务，并将结果返回
  • 主线程等待N个辅助线程运行结束，将所有辅助线程的结果累加
  • 本题要求 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
54
55
56
57
58
59
60
61
62
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

// int array[] = {1, 1, 1, 2, 2, 2};
#define NR_TOTAL 0x7ffff
#define NR_CPU 2
#define NR_CHILD (NR_TOTAL / NR_CPU)

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

struct result {
  double sum;
};

void *compute(void *arg) {
  struct param *param;
  struct result *result;
  float sum = 0;
  int i;

  param = (struct param *)arg;
  for (i = param->start; i < param->end; i++)
    if (i % 2)
      sum -= 1.0 / (i * 2 + 1);
    else
      sum += 1.0 / (i * 2 + 1);

  result = malloc(sizeof(struct result));
  result->sum = sum;
  return result;
}

int main() {
  pthread_t workers[NR_CPU];
  struct param params[NR_CPU];
  int i;

  for (i = 0; i < NR_CPU; i++) {
    struct param *param;
    param = &params[i];
    // param->array = array;
    param->start = i * NR_CHILD;
    param->end = (i + 1) * NR_CHILD;
    pthread_create(&workers[i], NULL, compute, param);
  }

  double sum = 0;
  for (i = 0; i < NR_CPU; i++) {
    struct result *result;
    pthread_join(workers[i], (void **)&result);
    sum += result->sum;
    free(result);
  }
  double PI = sum * 4;
  printf("PI: %lf\n", PI);
  return 0;
}

7.3 sort.c(Task 8)

多线程排序

  • 主线程创建两个辅助线程
  • 辅助线程1使用选择排序算法对数组的前半部分排序
  • 辅助线程2使用选择排序算法对数组的后半部分排序
  • 主线程等待辅助线程运行結束后,使用归并排序算法归并子线程的计算结果
  • 本题要求 1: 使用线程参数，消除程序中的代码重复
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
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int array[] = {2, -1, 3, 7, 0, 1};
int sorted_array[] = {2, -1, 3, 7, 0, 1};
#define NR_TOTAL 6
#define NR_CPU 2
#define NR_CHILD (NR_TOTAL / NR_CPU)

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

struct result {
  int sum;
};

void *compute(void *arg) {
  struct param *param;
  param = (struct param *)arg;
  for (int i = param->start; i < param->end - 1; i++) {  //选择排序
    int k = i;                                           //最小值索引
    for (int j = i + 1; j < param->end; j++) {
      if (param->array[j] < param->array[k]) {
        k = j;
      }
    }
    if (k != i) {  //交换
      int temp;
      temp = array[i];
      array[i] = array[k];
      array[k] = temp;
    }
  }
  return NULL;
}

int main() {
  pthread_t workers[NR_CPU];
  struct param params[NR_CPU];
  int i;

  for (i = 0; i < NR_CPU; i++) {
    struct param *param;
    param = &params[i];
    param->array = array;
    param->start = i * NR_CHILD;
    param->end = (i + 1) * NR_CHILD;
    pthread_create(&workers[i], NULL, compute, param);
  }

  for (i = 0; i < NR_CPU; i++) {
    struct result *result;
    pthread_join(workers[i], (void **)&result);
    // sum += result->sum;
    // free(result);
  }
  //归并排序
  int p1 = 0, p2 = NR_CHILD, p3 = 0;
  int cur;
  while (p1 < NR_CHILD || p2 < NR_TOTAL) {
    if (p1 == NR_CHILD) {
      cur = array[p2++];
    } else if (p2 == NR_TOTAL) {
      cur = array[p1++];
    } else if (array[p1] < array[p2]) {
      cur = array[p1++];
    } else {
      cur = array[p2++];
    }
    sorted_array[p3++] = cur;
  }
  //输出结果
  for (int i = 0; i < NR_TOTAL; i++) {
    printf("%d ", sorted_array[i]);
  }
  return 0;
}

7.4 pc1.c(Task 9)

  • 系统中有3个线程：生产者、计算者、消费者
  • 系统中有2个容量为4的缓冲区：buffer1、buffer2
  • 生产者生产’a’、‘b’、‘c’、‘d’、‘e’、‘f’、‘g’、'h’八个字符，放入到buffer1
  • 计算者从buffer1取出字符，将小写字符转换为大写字符，放入到buffer2
  • 消费者从buffer2取出字符，将其打印到屏幕上
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
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <ctype.h>

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

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

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

int get_item1()
{
    int item;

    item = buffer1[out1];
    out1 = (out1 + 1) % CAPACITY;
    return item;
}

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

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

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

int get_item2()
{
    int item;

    item = buffer2[out2];
    out2 = (out2 + 1) % CAPACITY;
    return item;
}

void put_item2(int item)
{
    buffer2[in2] = item;
    in2 = (in2 + 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 *consume(void *arg)
{
    int i;
    int item;

    for (i = 0; i < ITEM_COUNT; i++) { 
        pthread_mutex_lock(&mutex2);
        while (buffer2_is_empty())
            pthread_cond_wait(&wait_full_buffer2, &mutex2);

        item = get_item2(); 

        printf("    consume item: %c\n", item); 

        pthread_cond_signal(&wait_empty_buffer2);
        pthread_mutex_unlock(&mutex2);
    }
    return NULL;
}

void *calculate(void *arg)
{
    int i;
    int item;

    for (i = 0; i < ITEM_COUNT; i++) { 
        pthread_mutex_lock(&mutex1);
        while (buffer1_is_empty())
            pthread_cond_wait(&wait_full_buffer1, &mutex1);

        item = get_item1(); 

        pthread_cond_signal(&wait_empty_buffer1);
        pthread_mutex_unlock(&mutex1);

        pthread_mutex_lock(&mutex2);
        while (buffer2_is_full())
            pthread_cond_wait(&wait_empty_buffer2, &mutex2);
        item = toupper(item);
        put_item2(item);
        // printf("  calculate item: %c\n", item); 

        pthread_cond_signal(&wait_full_buffer2);
        pthread_mutex_unlock(&mutex2);
    }
    return NULL;
}

void *produce(void *arg)
{
    int i;
    int item;

    for (i = 0; i < ITEM_COUNT; i++) { 
        pthread_mutex_lock(&mutex1);
        while (buffer1_is_full()) 
            pthread_cond_wait(&wait_empty_buffer1, &mutex1);

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

        pthread_cond_signal(&wait_full_buffer1);
        pthread_mutex_unlock(&mutex1);
    }
    return NULL;
}

int main()
{ 
    pthread_t consumer_tid;
    pthread_t calculate_tid;
    pthread_t produce_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(&consumer_tid, NULL, consume, NULL);
    pthread_create(&calculate_tid, NULL, calculate, NULL);
    pthread_create(&produce_tid, NULL, produce, NULL);
    // produce(NULL); 
    pthread_join(produce_tid, NULL);
    pthread_join(calculate_tid, NULL);
    pthread_join(consumer_tid, NULL);
    return 0;
}

7.5 pc2.c(Task 10)

  • 功能和前面的实验相同，使用信号量解决
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
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <ctype.h>

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

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

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

int get_item1()
{
    int item;

    item = buffer1[out1];
    out1 = (out1 + 1) % CAPACITY;
    return item;
}

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

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

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

int get_item2()
{
    int item;

    item = buffer2[out2];
    out2 = (out2 + 1) % CAPACITY;
    return item;
}

void put_item2(int item)
{
    buffer2[in2] = item;
    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 mutex_sema1;
sema_t mutex_sema2;
sema_t empty_buffer_sema1;
sema_t empty_buffer_sema2;
sema_t full_buffer_sema1;
sema_t full_buffer_sema2;

#define ITEM_COUNT (CAPACITY * 2)

void *consume(void *arg)
{
    int i;
    int item;

    for (i = 0; i < ITEM_COUNT; i++) { 
        sema_wait(&full_buffer_sema2);
        sema_wait(&mutex_sema2);

        item = get_item2();
        printf("    consume item: %c\n", item); 

        sema_signal(&mutex_sema2);
        sema_signal(&empty_buffer_sema2);
    }

    return NULL;
}

void *calculate(void *arg)
{
    int i;
    int item;

    for (i = 0; i < ITEM_COUNT; i++) { 
        sema_wait(&full_buffer_sema1);
        sema_wait(&mutex_sema1);

        item = get_item1();
        // printf("    consume item: %c\n", item); 

        sema_signal(&mutex_sema1);
        sema_signal(&empty_buffer_sema1);

        sema_wait(&empty_buffer_sema2);
        sema_wait(&mutex_sema2);

        item = toupper(item);
        put_item2(item);
        // printf("  calculate item: %c\n", item); 

        sema_signal(&mutex_sema2);
        sema_signal(&full_buffer_sema2);
    }

    return NULL;
}

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

    for (i = 0; i < ITEM_COUNT; i++) { 
        sema_wait(&empty_buffer_sema1);
        sema_wait(&mutex_sema1);

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

        sema_signal(&mutex_sema1);
        sema_signal(&full_buffer_sema1);
    }

    return NULL;
}

int main()
{ 
    pthread_t consumer_tid;
    pthread_t calculate_tid;
    pthread_t produce_tid;

    sema_init(&mutex_sema1, 1);
    sema_init(&empty_buffer_sema1, CAPACITY - 1);
    sema_init(&full_buffer_sema1, 0);
    sema_init(&mutex_sema2, 1);
    sema_init(&empty_buffer_sema2, CAPACITY - 1);
    sema_init(&full_buffer_sema2, 0);

    pthread_create(&consumer_tid, NULL, consume, NULL);
    pthread_create(&calculate_tid, NULL, calculate, NULL);
    pthread_create(&produce_tid, NULL, produce, NULL);
    // produce(NULL); 
    pthread_join(produce_tid, NULL);
    pthread_join(calculate_tid, NULL);
    pthread_join(consumer_tid, NULL);
    return 0;
}

Task 11+考试

11.2 ring.c

1、实现线循环

2、创建N个线程

N个线程构成一个环

主线程向T1发送数据0

T1收到数据后，将数据加1，向T2发送数据1

T2收到数据后，将数据加1，向T3发送数据2

T3收到数据后，将数据加1，向T4发送数据3

…

3、创建N个缓冲区

4、每个线程有一个输入缓冲和一个输出缓冲

5、最终的系统结构如下

图片名称

6、本程序不能使用任何全局变量，如果使用了全局变量，本题没有得分

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
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>
#define N 10
#define LOOPCOUNT 25

void *add(void *arg){
    int *num = (int *)arg;
    num[1] = num[0] + 1;
    int *result = num;
}
int main()
{
    int buff[N][2];
    int i = 0;
    for(i = 0;i < N;i++)
    {
        buff[i][0]=0;
        buff[i][1]=0;
    }
    pthread_t tids[N];

    i = 0;
    int count = 0;
    while(i < N)
    {
        count++;
        if(count == LOOPCOUNT)
            break;

        printf("from T[%d]",i+1);
        pthread_create(&tids[i],NULL,add,(void *)&buff[i]);
        pthread_join(tids[i],NULL);
        int result = buff[i][1];

        i = (i+1) % N;
        buff[i][0] = result;
        printf("to T[%d] send %d\n",i+1,result);
    }
    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
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define N 100
#define BUFFER_CAPACITY 4
int buffer[BUFFER_CAPACITY] = {0};
int in = 0, out = 0;

struct params {
    int order;
};

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

sema_t thread_mutex[N];
sema_t buffer_mutex;
sema_t buffer_full_sema, buffer_empty_sema;

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);
}

int get_item() {
    int item;
    item = buffer[out];
    out = (out + 1) % BUFFER_CAPACITY;
    return item;
}

void put_item(char item) {
    buffer[in] = item;
    in = (in + 1) % BUFFER_CAPACITY;
}

void *instance (void *args) {
    struct params *param = (struct params *)args;
    int item;
    int i = param->order;
    if (i > 0) {
        sema_wait(&thread_mutex[i]);
        sema_wait(&buffer_full_sema);
        sema_wait(&buffer_mutex);

        item = get_item();
        printf("\033[0;32m%d get item: %d\033[0m\n", i+1, item);

        put_item(++item);
        printf("\033[0;31m%d put item: %d\033[0m\n", i+1, item);

        sema_signal(&buffer_mutex);
        sema_signal(&buffer_full_sema);
        sema_signal(&thread_mutex[(i+1) % N]);
    } else {
        // The first thread
        sema_wait(&buffer_empty_sema);
        sema_wait(&buffer_mutex);
        item = i + 1;
        put_item(item);
        printf("\033[0;31m%d put item: %d\033[0m\n", i+1, item);
        sema_signal(&buffer_mutex);
        sema_signal(&buffer_full_sema);
        sema_signal(&thread_mutex[(i+1) % N]);

        sema_wait(&thread_mutex[i]);
        sema_wait(&buffer_full_sema);
        sema_wait(&buffer_mutex);
        item = get_item();
        printf("\033[0;32m%d get item: %d\033[0m\n", i+1, item);
        sema_signal(&buffer_mutex);
        sema_signal(&buffer_empty_sema);
        sema_signal(&thread_mutex[i]);
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t thread[N];
    int i;
    struct params params[N];
    struct params *param = params;

    sema_init(&buffer_mutex, 1);
    sema_init(&buffer_full_sema, 0);
    sema_init(&buffer_empty_sema, BUFFER_CAPACITY - 1);
    for (i = 0; i < N; i++) {
        sema_init(&thread_mutex[i], 0);
    }
    

    for (i = 0; i < N; i++, param++) {
        param->order = i;
        pthread_create(&thread[i], NULL, instance, param);
    }

    pthread_join(thread[0], NULL);

    return 0;
}

11.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
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
//现有一个水果盘，一次只能放一个水果
//父亲一次向里边放一个苹果，母亲一次向里边放一个橘子
//儿子一次从盘中取出一个苹果，女儿一次从盘中取出一个橘子
//要求只能使用条件变量，不能使用环境变量
//输出结果为
//put apple
//get apple
//put orange
//get orange

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

int plane = 1;//1表示盘子空 0表示盘子满

pthread_mutex_t mutex;
pthread_cond_t wait_apple;
pthread_cond_t wait_empty;
pthread_cond_t wait_orange;

void *father_entry(void *arg)
{
	//while(1){
		pthread_mutex_lock(&mutex);
		while(plane == 0)
			pthread_cond_wait(&wait_empty, &mutex);
		puts("put apple");
		pthread_cond_signal(&wait_apple);
		sleep(1);
		plane = 0;
		
		pthread_mutex_unlock(&mutex);
		
	//}
	return NULL;
}

void *mother_entry(void *arg)
{
	//while(1){
		pthread_mutex_lock(&mutex);
		while(plane == 0)
			pthread_cond_wait(&wait_empty, &mutex);
		
		puts("put orange");
		pthread_cond_signal(&wait_orange);
		sleep(1);
		plane = 0;
		
		pthread_mutex_unlock(&mutex);
		
    
	//}
	return NULL;
}

void *son_entry(void *arg)
{
	//while(1){
		pthread_mutex_lock(&mutex);
		while(plane == 1)
			pthread_cond_wait(&wait_apple, &mutex);

		puts("get apple");
		pthread_cond_signal(&wait_empty);
		sleep(1);
		plane = 1;
		
		pthread_mutex_unlock(&mutex);
		
    
	//}
	return NULL;
}

void *daughter_entry(void *arg)
{
	//while(1){
		pthread_mutex_lock(&mutex);
		while(plane == 1)
			pthread_cond_wait(&wait_orange, &mutex);

		puts("get orange");
		pthread_cond_signal(&wait_empty);
		sleep(1);
		plane = 1;
		
		pthread_mutex_unlock(&mutex);
		
    //}
	return NULL;
}

int main()
{
    pthread_t father_thread;
    pthread_t mother_thread;
    pthread_t son_thread;
    pthread_t daughter_thread;
	
	pthread_mutex_init(&mutex, NULL);
	pthread_cond_init(&wait_empty, NULL);
	pthread_cond_init(&wait_apple, NULL);
	pthread_cond_init(&wait_orange, NULL);

    pthread_create(&father_thread, NULL, &father_entry, NULL);
    pthread_create(&mother_thread, NULL, &mother_entry, NULL);
    pthread_create(&son_thread, NULL, &son_entry, NULL);
    pthread_create(&daughter_thread, NULL, &daughter_entry, NULL);

    pthread_join(father_thread,NULL);
	pthread_join(mother_thread,NULL);
	pthread_join(son_thread,NULL);
	pthread_join(daughter_thread,NULL);
	//while (1);
    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
//现有一个水果盘，一次只能放一个水果
//父亲一次向里边放一个苹果，母亲一次向里边放一个橘子
//儿子一次从盘中取出一个苹果，女儿一次从盘中取出一个橘子
//要求只能使用条件变量，不能使用环境变量
//输出结果为
//put apple
//get apple
//put orange
//get orange

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

// int plane = 1;//1表示盘子空 0表示盘子满
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_t apple;
sema_t plate;
sema_t orange;
  
void *father_entry(void *arg)
{
	//while(1){
    sema_wait(&plate);
    sema_wait(&mutex);

		puts("put apple");
		// pthread_cond_signal(&wait_apple);
		sleep(1);
		sema_signal(&mutex);
    sema_signal(&apple);
		
	//}
	return NULL;
}

void *mother_entry(void *arg)
{
	//while(1){
    sema_wait(&plate);
    sema_wait(&mutex);
    
		puts("put orange");
		sleep(1);
		sema_signal(&mutex);
    sema_signal(&orange);
	//}
	return NULL;
}

void *son_entry(void *arg)
{
	//while(1){
		sema_wait(&apple);
    sema_wait(&mutex);
		puts("get apple");
		sleep(1);
		
    sema_signal(&mutex);
    sema_signal(&plate);
	//}
	return NULL;
}

void *daughter_entry(void *arg)
{
	//while(1){
		sema_wait(&orange);
    sema_wait(&mutex);

		puts("get orange");
		sleep(1);
    sema_signal(&mutex);
    sema_signal(&plate);
		
    //}
	return NULL;
}

int main()
{
    pthread_t father_thread;
    pthread_t mother_thread;
    pthread_t son_thread;
    pthread_t daughter_thread;
	
	sema_init(&mutex, 1);
  sema_init(&apple, 0);
  sema_init(&orange, 0);
  sema_init(&plate, 1);

    pthread_create(&father_thread, NULL, &father_entry, NULL);
    pthread_create(&mother_thread, NULL, &mother_entry, NULL);
    pthread_create(&son_thread, NULL, &son_entry, NULL);
    pthread_create(&daughter_thread, NULL, &daughter_entry, NULL);

    pthread_join(father_thread,NULL);
	pthread_join(mother_thread,NULL);
	pthread_join(son_thread,NULL);
	pthread_join(daughter_thread,NULL);
	//while (1);
    return 0;
}

随堂作业

Todo 1 进程的内存布局

要求

一般操作系统中，进程的每个段内部地址均连续，但段与段的相对次序可能不同。用C/C++语言写一个小程序，探测一个操作系统中进程的各段的相对位置(输出次序即可)。

理论基础

图片名称
栈(stack) 由编译器自动分配、翻译。存放函数的参数值和局部变量值。操作方式类似数据结构中的栈
堆(heap) 由程序员分配释放。程序员不释放，程序结束时有可能由OS释放。与数据结构中的堆不同，操作方式类似于链表
bss 存放未初始化的全局变量和静态变量
数据段data 存放初始化之后的全局变量、静态变量和常量
代码段text 程序代码主体，函数主体等。注意为二进制格式

Linux 为 C 语言编程环境提供了 3 个全局符号（symbol）：etext、 edata 和 end，可在程序内使用这些符号以获取相应程序文本段、初始化数据段和非初始化数据段结尾处下一字节的地址。

源代码

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
#include <stdio.h>
#include <stdlib.h>

#ifdef _WIN32
#include <windows.h>
#endif

#ifdef linux
extern etext, edata, end;
#endif

int bss_var;        //未初始化全局变量存储在BSS段
int data_var = 42;  //初始化全局变量存储在数据段

int main(int argc, char *argv[]) {
#ifdef linux
  printf("etext          address: %p\n", &etext);
  printf("edata          address: %p\n", &edata);
  printf("end            address: %p\n", &end);
#endif

  printf("main(TEXT)     address: %p\n", &main);  //查看代码段main函数位置
  printf("data_var(DATA) address: %p\n", &data_var);  //查看数据段变量地址
  printf("bss_var(BSS)   address: %p\n", &bss_var);  //查看BSS段变量地址
  char *p;
  p = (char *)malloc(32 * sizeof(char));  //从堆中分配空间
  if (p != NULL) {
    printf("p(HEAP)        address: %p\n", p);   //查看堆位置
    printf("&p(STACK)      address: %p\n", &p);  //查看栈位置
  }

#ifdef _WIN32
  auto pHeap = (char *)GetProcessHeap();
  printf("default heap   address: %p\n", pHeap);
  HANDLE hHeap = HeapCreate(HEAP_NO_SERIALIZE, 0, 1024);
  void *pp = HeapAlloc(hHeap, HEAP_NO_SERIALIZE, 1012);
  printf("private heap   address: %p\n", pp);
  auto bRetVal = HeapFree(hHeap, HEAP_NO_SERIALIZE, pp);
  // sleep(1000); //为方便使用VMMap查看Windows的进程地址空间
#endif

  free(p);  //释放申请的空间，以避免内存泄露

  return 0;
}

运行结果

下面分别在Linux、windows、macos系统上测试程序：

Linux(Ubuntu 18.04.2 LTS)

图片名称

从打印结果可知：

  1. TEXT段在地址 0x7f27358008dd 以下，DATA段的地址范围是：0x7f27358008dd - 0x7f2735a01014，BSS段的地址范围是：0x7f2735a01014 - 0x7f2735a01020
  2. main的地址为0x7f273580073a，在TEXT段；初始化全局变量data_var的地址为0x7f2735a01010，在DATA段； 未初始化全局变量bss_var的地址为0x7f2735a01018，在 BSS 段内；
  3. char* 变量 p 的值是 0x7fffc693c470，也就是由 malloc() 分配的一块内存空间的首地址，这块内存就在堆中；但是 p 本身存放在栈里，地址为0x7fffce8516e0
  4. 综上，各段的相对位置(地址由低到高)：TEXT段、DATA段、BSS段、堆、栈。

Windows 10

图片名称 图片名称

从打印结果可知：TEXT段、DATA段、BSS段、栈的相对位置与linux、macos相同，只有堆的位置比较特殊，每次测试结果变化较大。

翻阅《Windows核心编程》：

  • Windows下的堆主要有两种，进程的默认堆和自己创建的私有堆。
  • 在程序启动时，系统在刚刚创建的进程虚拟地址空间中创建一个进程的默认堆，而且程序也可以通过 HeapCreate 函数来调用 ntdll 中的RtlCreateHeap 来创建自己的私有堆，所以一个进程中可以存在多个堆。
  • Windows下的malloc通过Win32 API HeapAlloc来实现，所以申请的堆空间来自私有堆。

推测：

  • 默认堆遵守上面的经典模型，私有堆分配可能比较随意。

  • 通过调用GetProcessHeap()来获取默认堆的位置，可能会出现想要的结果。

但是仍然存在上述问题：

图片名称 图片名称

最后在知乎上找到了答案：

Windows的进程地址空间分布跟上面说的简化的Linux/x86模型颇不一样。
就算在没有ASLR的老Windows上也已经很不一样，有了ASLR之后就更加不一样了。

在Windows上不应该对栈和堆的相对位置做任何假设。

要想看个清楚Windows的进程地址空间长啥样，可以用Sysinternals出品的VMMap看看。

使用VMMap查看：

图片名称

macOS

图片名称

从打印结果可知：各段的相对位置(地址由低到高)：TEXT段、DATA段、BSS段、堆、栈。

总结

在简化的32位Linux/x86进程地址空间模型里，（主线程的）栈空间确实比堆空间的地址要高——它已经占据了用户态地址空间的最高可分配的区域，并且向下（向低地址）增长。借用Gustavo Duarte的Anatomy of a Program in Memory里的图：

图片名称

《程序员的自我修养》也说栈的地址比堆高，栈是向下增长的，堆是向上增长的。 这个说法其实不够严谨。而且上图是简化模型，会有特例：

  1. 虽然传统上，Linux上的malloc实现会使用brk()/sbrk()（这俩构成了上图中Heap所示的部分，这也是Linux自身所认为是heap的地方，用pmap可以看到这里被标记为[heap]），但这并不是必须的；一个malloc()完全可以只用或基本上只用mmap()来实现，此时一般说的“Heap”（malloc-heap）就不一定在上图Heap（Linux heap）所示部分，而会在Memory Mapping Segment部分散布开来。不同版本的Linux在分配未指定起始地址的mmap()时用的顺序不一样，并不保证某种顺序。而且mmap()分配到的空间是有可能出现在低于主可执行程序映射进来的text Segment所在的位置。
  2. Linux上多线程进程中，“线程”其实是一组共享虚拟地址空间的进程。只有主线程的栈是按照上面图示分布，其它线程的栈的位置其实是“随机”的——它们可以由pthread_create()调用mmap()来分配，也可以由程序自己调用mmap()之后把地址传给pthread_create()。既然是mmap()来的，其它线程的栈出现在Memory Mapping Segment的任意位置都不出奇，与用于实现malloc()用的mmap()空间很可能是交错出现的。

至于Windows的进程地址空间分布跟上面说的简化的Linux/x86模型颇不一样。就算在没有ASLR的老Windows上也已经很不一样，有了ASLR之后就更加不一样了。

在Windows上不应该对栈和堆的相对位置做任何假设。

要想看清楚Windows的进程地址空间布局，可以用Sysinternals出品的VMMap看看。

参考

Todo 2 进程相关

一、选择题

  1. 如果操作系统采用了非抢占式进程调度算法，则进程不可能出现以下哪种状态转换? B

    A.执行到阻塞 B. 执行到就绪 C. 阻塞到就绪 D. 就绪到执行

  2. 进程调度算法在选择进程时，只考虑处于哪个状态的进程? A

    A.就绪 B.阻塞 C.执行 D.结束

  3. 子程序的返回地址一般存在 A

    A.栈B.堆C.数据段D.代码段

  4. 哪个调度算法只有抢占式版本? D

    A.先到先服务B. 短作业优先C. 优先级调度D. 轮转调度

二、概念理解及应用

T1(4分)

问题：为了解决能够同时服务多个客户的目的,开发人员设计了多线程程序，每次有新用户连接时创建一个新的服务线程，服务结束时销毁线程;同时，为了防止服务器瘫瘓,限制了服务线程的总数量为100个。但是在运行过程中，不断创建销毁线程引入了不必要的额外开销，你有什么办法避免这个开销?你的办法有什么缺点?

解答如下：

采用线程池，把宝贵的资源放到一个池子中；每次使用都从里面获取，用完之后又放回池子供其他人使用。主要流程图如下：

图片名称

优点：

  1. 降低资源开销：由于线程是反复利用的，降低了创建线程分配资源和销毁线程的开销。
  2. 提高响应速度：由于线程是提前预热的，因此减少了创建线程这段时间的开销。
  3. 提高系统资源可管理性：使用线程池统一分配、管理和监控。

缺点：

  1. 当客户少时浪费资源
  2. 一个根本性的缺陷：连续争用问题。也就是多个线程在申请任务时，为了合理地分配任务要付出锁资源，对比快速的任务执行来说，这部分申请的损耗是巨大的。

参考：https://zhuanlan.zhihu.com/p/161628226

T2(4分)

问题：《Unix编程艺术》提倡使用多进程编程，而不是多线程编程。你觉得可能的原因是什么?

解答如下：

  1. 多进程,本质上就可以避免多线程『共享内存数据』产生的 “corruotped memory” 问题；
  2. 多线程的程序非常难以正确的编写；
  3. 难以调试: 因为 数据依赖，时间依赖
  4. 线程破坏了抽象: 无法设计出模块化的程序
  5. 因为锁导致回调无法完成
  6. 进程隔离性好，一个进程挂了不影响另外一个进程。

参考：

三、计算题

现有3个进程A、B、C到达时间和预计运行时间如下表所示。要求画出不同调度算法下进程运行的甘特图,并计算进程的平均周转时间。

进程编号 到达时间（毫秒） 执行时间（毫秒）
A 0 9
B 1 7
C 2 4
  1. 先到先服务调度算法
  2. 短作业优先(非抢占)
  3. 抢占式短作业优先算法
  4. 时间片轮转算法(时间片为3毫秒)

改错：

T2：A C B 13ms

图片名称

Todo 3

Dragon's BlogsDevelopment

Life is painting a picture, not doing a sum.