抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

ひと結び、人を結んで

操作系统原理的上机实验的报告一共有四个,其他的报告的地址是:

第一次:https://shiraha.cn/2020/class-FoDOS-experiment-1/
第二次:https://shiraha.cn/2020/class-FoDOS-experiment-2/
第三次:https://shiraha.cn/2020/class-FoDOS-experiment-3/
第四次:https://shiraha.cn/2020/class-FoDOS-experiment-4/

Front-matter

本次实验的所有源代码可以在https://dev.azure.com/Pure-Asahi/_git/2020_Spring_In_Class_Job?path=%2Fosnmb%2Fexp 查看到。

实验要求

本次上机实验的实验要求如下:

#####
《操作系统原理》第三次上机实验

一、实验目的

  1. 理解线程/进程的通信机制和编程;
  2. 理解线程/进程的死锁概念和如何解决死锁;

二、实验内容

  1. 在 Ubuntu 或 Fedora 环境创建一对父子进程,使用共享内存的方式实现进程间的通信。父进程提供数据(1-100,递增),子进程读出来并显示
  2. (考虑信号通信机制)在 Ubuntu 或 Fedora 环境创建父子 2 个进程 A,B。进程 A 不断获取用户从键盘输入的字符串或整数,通过信号机制传给进程 B。如果输入的是字符串,进程 B 将其打印出来;如果输入的是整数,进程 B 将其累加起来,并输出该数和累加和。当累加和大于 100 时结束子进程,子进程输出“My work done!”后结束,然后父进程也结束。
  3. 在 windows 环境使用创建一对父子进程,使用管道(pipe)的方式实现进程间的通信。父进程提供数据(1-100,递增),子进程读出来并显示。
  4. (考虑匿名管道通信)在 windows 环境下创建将 CMD 控制台程序封装为标准的 windows 窗口程序。
  5. 在 windows 环境下,利用高级语言编程环境(限定为 VS 环境或 VC 环境或QT)调用 CreateThread 函数哲学家就餐问题的演示。要求:
    1. 提供死锁的解法和非死锁的解法;
    2. 有图形界面直观显示哲学家取筷子,吃饭,放筷子,思考等状态。
    3. 为增强结果的随机性,各个状态之间的维持时间采用随机时间,例如100ms-500ms 之间。

在上述任务中: [1,3,4]中任意 1 题和第2,5 题,共计 3 道题。

我选择了 1、2、5 三个题目。

实验内容

  1. 在 Ubuntu 或 Fedora 环境创建一对父子进程,使用共享内存的方式实现进程间的通信。父进程提供数据(1-100,递增),子进程读出来并显示
  2. (考虑信号通信机制)在 Ubuntu 或 Fedora 环境创建父子 2 个进程 A,B。进程 A 不断获取用户从键盘输入的字符串或整数,通过信号机制传给进程 B。如果输入的是字符串,进程 B 将其打印出来;如果输入的是整数,进程 B 将其累加起来,并输出该数和累加和。当累加和大于 100 时结束子进程,子进程输出“My work done!”后结束,然后父进程也结束。
  3. 在 windows 环境下,利用高级语言编程环境(限定为 VS 环境或 VC 环境或QT)调用 CreateThread 函数哲学家就餐问题的演示。要求:
    1. 提供死锁的解法和非死锁的解法;
    2. 有图形界面直观显示哲学家取筷子,吃饭,放筷子,思考等状态。
    3. 为增强结果的随机性,各个状态之间的维持时间采用随机时间,例如100ms-500ms 之间。

实验过程

下面是对于每一个任务的原理和过程的简述:

共享内存

共享内存就是允许两个不相关的进程访问的同一个逻辑内存,是在两个正在运行的进程之间共享和传递数据的一种方式。进程之间共享的内存通常为同一段物理内存,并且可以将同一段共享内存连接到进程自己的地址空间中,所有进程都可以访问共享内存中的数据,并且可以进行修改;所做的改动将立即影响到可访问该共享内存的所有的其他进程。

共享内存并未提供同步机制;如果需要,可以配合其他机制(如信号量机制,需要使用 sem 家族的函数)来控制其他进程对于共享内存的同步访问。

在 Linux 下创建一个区域作为共享内存,需要用到 shm 系列函数;它们定义在sys/shm.h中,可以直接引入。在本次实验中,需要使用的这个系列的函数有:

shmget函数:可以用来创建共享内存区域;声明式如下:

1
int shmget(key_t key, size_t size, int shmflg);

它所接受的参数的含义如下:

  1. 标识共享内存的键值;当它取IPC_PRIVATE,或取 0 但是在第三个参数中设置了IPC_PRIVATE标志的时候,会创建一块新共享内存;当然也可以指定一个其他值,作为该 IPC 对象的名字,存储在ipc_perm结构中。因为在实际生产环境中难以约定一个唯一的键值,所以可以设置为IPC_PRIVATE让操作系统指定。
  2. 指定了共享内存的长度;实际获得的空间总是系统页面大小的倍数,因为 Linux 总是以页作为内存分配调度的最小单位。
  3. 是共享内存读写权限的标志;和在 Linux 中打开文件的权限标志是一样的,例如:当地一个参数指定的内存不存在的时候创建并打开,需要设置IPC_CREAT位;对应的还有IPC_EXCL,它仅在第一个参数指定的内存不存在时才可以正常创建打开;对于读写指定的标志时SHM_RSHM_W,当然也可以直接用数字,比如 0660、0666、0644 等。

这个函数如果出现错误会返回 -1,并且设置errno位;否则返回与第一个参数key相关的共享内存标识符,可以用于后续对于这块共享内存的处理。

创建共享内存之后,还需要对它进行访问,这需要shmat函数;at 是 attach 的意思;它的声明如下:

1
void *shmat(int shm_id, const void *shm_addr, int shmflg);

它所接受的参数的含义如下:

  1. 共享内存的标识符,是shmget的返回值;
  2. 指定当前进程下映射到共享内存的地址;当这个值取 0,表示让操作系统选择共享内存所在的地址,这样操作系统将会自动为映射分配一块内存;如果这里制定了地址,还需要预先处理分配内存。映射地址可能不是整页,将根据第三个参数的值决定内存是否取整页。
  3. 标志位参数;如果指定了SHM_RDONLY,共享内存将被映射为只读的;如果指定SHM_RND,则将内存大小设定为页面的尺寸。

如果成功,该函数将返回在当前进程的内存空间中,共享内存的映射地址;否则返回 -1,并且设置errno

如果当前进程不再需要访问共享内存,则可以使用shmdt函数,dt 指 detach;该函数会使得共享内存和当前进程分离,但并不删除共享内存,只是当前进程无法访问;它的声明是:

1
int shmdt(const void *shmaddr);

接受的参数是共享内存映射到当前进程的指针地址,也就是shmat函数调用成功的返回值;该函数调用成功返回 0,否则返回 -1.

shmctl可以用来控制共享内存,ctl 指的是control,和semctl一样;它的声明式是这样的:

1
int shmctl(int shm_id, int command, struct shmid_ds *buf);

它接受的参数的意义是这样的:

  1. 是共享内存的标识符;是shmget的返回值;

  2. 代表将要采取的操作:取IPC_STAT代表尝试获得共享内存当前的关联值,将该值存入第三个参数指向的shmid_ds结构中;取IPC_SET代表尝试设置共享内存当前的关联值,当线程有足够的权限操作时就将第三个参数指向的结构中的值设置为当前共享内存的关联值;取IPC_RMID代表删除当前共享内存段,但是并不是立即删除,只是给它加上待删标志,直到所有的进程都和它断开连接后才会真正的删除。

  3. 指向shmid_ds结构的指针;它包含了共享内存模式和访问权限。它至少包含了下面的这些成员:

    1
    2
    3
    4
    5
    6
    struct shmid_ds
    {
    uid_t shm_perm.uid;
    uid_t shm_perm.gid;
    mode_t shm_perm.mode;
    };

    返回 0 表示执行成功,否则返回 -1 并设置errno值。

这样,我们就可以通过使用这些函数建立共享内存供两个进程使用了。进程随时修改内存,并设置标志供其他进程读取;若另一个进程正在操作内存,那么可以设置标志位,让另一个进程进入阻塞状态直到标志位被放开。

多线程传递数据

考虑使用管道在进程之间通信;进程之间的管道通信具有下面的特点:

  • 管道只允许有血缘关系的进程之间通信——比如父子进程
  • 管道的通信是单向的——如果需要双向通信,可以开设多个管道
  • 管道内部保证同步机制——这保证了访问数据的一致性
  • 管道和进程共存——进程关闭则端口关闭,所有进程关闭则管道销毁
  • 管道通信是字节流——可以用来传输字节流数据

管道包含两端,一个是读端,一个是写端;如果要创建的管道是匿名管道pipe(除此之外还有有名管道FIFO),则可以使用定义在unistd.h中的pipe函数创建。pipe函数的声明是这样的:

1
int pipe(int pipefd[2]);

接受的参数是一个包含两个整数的数组,是一个out参数:如果函数调用成功,将会在这个数组中存入两个文件标识符,表示了新创建的通道的读端和写端——[0]是读端,[1]是写端。管道对于进程而言就是一个打开的文件,可以使用readwrite函数进行文件操作。如果函数成功执行将返回 0,否则返回 -1.

一般创建父子进程之间的匿名管道的步骤是:

  • 父进程创建一个匿名管道,得到管道两端的文件标识符
  • 父进程使用fork创建子进程,子进程复制了父亲的文件标识符变量
  • 父进程关闭一段,子进程关闭另一端(使用close

管道的实现是一个环形队列:数据从管道的一端流入,另一端流出,就实现了进程之间的通信

不论是什么方式进行的进程间通信,本质上都是不同进程可以看到一份同样的资源——在内核中开辟的一块缓冲区。不同的通信方式的区别只是这份公共资源提供的方式。既然管道本质是内核空间的缓冲区,它就有一个容量上限:这可以通过写端持续写入,读端不读取且不关闭读端来获得。

管道信息传输还存在特殊情况:

  1. 读端开启,但是不读取;写端持续写入——当缓冲区被写满之后再次write会导致管道阻塞,直到管道有空位置时才可以继续写入;
  2. 写端开启,但是不写入;读端持续读入——当缓冲区无数据可读的时候再次read会导致管道阻塞,直到管道有新数据时才可以继续读取;
  3. 写端关闭,读端持续读入——当缓冲区无数据可读的时候会读取到EOF
  4. 读端关闭,写端持续写入——当缓冲区写满之后会产生信号SIGPIPE,导致进程中止;

简单地说,就是缓冲区占满会导致异常。

这样,我们就可以使用管道来进行进程间的通信,并且按照要求实现了。传输数据时可以在传输前判断输入的字符串的性质,随后提前通过管道传递一个信号给另一个进程说明数据类型,再传递数据。

在这个任务里,我在父亲进程中首先尝试对于读入的字符串进行转换:若不能完全转换为数字,则输入是字符串,先传递信号 0,再传递字符串占用的空间((strlen(s)+1)*sizeof(char))和字符串;否则,传递信号 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
82
83
84
85
86
87
if (id > 0)                 // 這是父親進程
{
close(fd[0]);
close(rt[1]);
int cnt = 0, msg;
char s[BUF_SIZE];
char *sign;
int flag, res;
write(fd[1], &cnt, sizeof(cnt));
while (cnt ++ < 100)
{
cout << "正在等待用戶的輸入……(輸入不要超過 "
<< BUF_SIZE - 1 << " 個字符)" << endl;
cin >> s;
cout << "父親進程收到了用戶輸入: " << s << flush;
msg = (int)strtol(s, &sign, 10);
if (sign - s == strlen(s))
{
cout << ",您輸入的是一個數字" << endl;
flag = 1;
write(fd[1], &flag, sizeof(flag));
write(fd[1], &INT, sizeof(INT));
write(fd[1], &msg, sizeof(msg));
}
else
{
cout << ",您輸入的是一個字符串" << endl;
int SIZE = CHAR * strlen(s) + CHAR;
flag = 0;
write(fd[1], &flag, sizeof(flag));
write(fd[1], &SIZE, sizeof(SIZE));
write(fd[1], s, SIZE);
}
sleep(SLEEP_TIME);
ssize_t siz = read(rt[0], &res, sizeof(res));
cerr << "收到子進程的信號: " << res << '(' << siz << ")\n";
if (~res && res <= TIME_MAX) continue;
else if (res == -1)
{
cout << "收到來自子進程的信號,父親進程即將退出……" << endl;
exit(EXIT_SUCCESS);
} else break;
}
cout << "父親進程的工作完成了,即將退出……" << endl;
exit(EXIT_SUCCESS);
}
else if (id == 0) // 如果這是子進程
{
close(fd[1]);
close(rt[0]);
int msg, j = 0, size, flag, sum = 0;
char ss[BUF_SIZE];
read(fd[0], &msg, sizeof(msg));
const int offset = msg;
cerr << "子進程已經初始化,offset值是: " << offset << endl;
while (j < TIME_MAX)
{
read(fd[0], &flag, sizeof(flag));
ssize_t s = read(fd[0], &size, sizeof(size));
cerr << "消息的大小是: " << s << ",消息的類型是 "
<< (flag ? "int(" : "string(") << size
<< ")" << endl;
if (flag)
{
read(fd[0], &msg, sizeof(msg));
cout << "收到了來自父親進程的消息: " << msg << endl;
sum += msg;
cout << "纍加值當前已經纍計了: " << sum
<< '/' << SUM_MAX << endl;
if (sum >= SUM_MAX)
{
cout << "纍加值達到要求,程序子進程退出……" << endl;
j = -1;
write(rt[1], &j, sizeof(j));
exit(EXIT_SUCCESS);
}
}
else
{
read(fd[0], ss, size);
cout << "收到了來自父親進程的消息: " << ss << endl;
}
++ j;
cerr << "這是子進程處理的第 " << j << " 條消息" << endl;
write(rt[1], &j, sizeof(j));
}
}

上面的是关于功能的具体实现的片段。包括了关闭管道的端口,缓冲区字符串类型判断和字节流信息传递。

哲学家问题

因为没有合适的素材,所以没有做图形界面,改用文件输出了。

实现的伪代码已经在幻灯片里提到了,这里就不再展开详述了。

关于这个问题导致的死锁情况的分析:当一个哲学家已经拿起了左手边的筷子,准备拿起右手边筷子的时候,发现右手边的筷子被占用了,就会陷入阻塞,等待右手边的筷子释放后才能活动;但是于此同时,左边的那位哲学家可能也因为缺少右手边的筷子而陷入阻塞;这样推导下去就可能导致所有的哲学家陷入阻塞,即所谓死锁。

分析问题,发现该问题满足了死锁产生的四个条件:

  1. 互斥条件:一个资源每次只能被一个线程/进程使用。
  2. 请求与保持条件:一个线程/进程因请求资源而阻塞时,对已获得的资源保持不放。
  3. 不剥夺条件:线程/进程已获得的资源,在未使用完之前,不能强行剥夺。
  4. 循环等待条件:若干线程/进程之间形成一种头尾相接的循环等待资源关系。

解决死锁通常的思路是预防-避免-检测:具体的做法就是设置资源获取的协议,动态决定是否赋予资源,并且设定专门的机构来外力破坏死锁,使进程回复。

对于这种情况,避免死锁可以使用资源有序分配的方法来解决:首先我们通过交换第 0 号哲学家的左右手筷子的编码,这样就可以导致所有的哲学家左手的筷子编号都比右手的筷子编号大,破坏了上述死锁发生条件的循环等待条件,就通过预防的方式避免了死锁。

除此之外,当然可以从其他角度入手:使用信号量限制同时吃面条的人数,或者让哲学家等待之前先释放已经拿到的筷子,都可以解决这个死锁的问题。

至于程序的实现,可以采用 Windows 自带的 CreateThread函数和信号量机制;API 在之前的上机实验报告中已经提到过了,这里就不再赘述。

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
DWORD WINAPI philosopher(LPVOID lpParam)
{
const auto rm = randomMachine(100, 500);
int id = ++ cnt_id;
const string out = FILE_NAME + to_string(id) + TXT;
ofstream fout((PATH + out).c_str());
if (!fout)
{
cerr << "哲學家 " << id << ": 文件打開失敗!程序即將退出……" << endl;
exit(EXIT_FAILURE);
}
int time, cnt = 0;
HANDLE right, left;
left = OpenSemaphore(SEMAPHORE_ALL_ACCESS, FALSE, chop[LeftHand]);
right = OpenSemaphore(SEMAPHORE_ALL_ACCESS, FALSE, chop[RightHand]);
while (cnt ++ <= TIME_MAX)
{
time = rm();
fout << getNowTime() << ": 哲學家 " << id
<< " 思考了 " << time << " ms." << endl;
Sleep(time);
time = rm();
fout << getNowTime() << ": 哲學家 " << id
<< " 休息了 " << time << " ms." << endl;
Sleep(time);
WaitForSingleObject(left, INFINITE);
fout << getNowTime() << ": 哲學家 " << id
<< " 拿起了左手邊的筷子 " << LeftHand << endl;
WaitForSingleObject(right, INFINITE);
fout << getNowTime() << ": 哲學家 " << id
<< " 拿起了右手邊的筷子 " << RightHand << endl;
time = rm();
fout << getNowTime() << ": 哲學家 " << id
<< " 用餐了 " << time << " ms." << endl;
Sleep(time);
ReleaseSemaphore(left, 1, NULL);
fout << getNowTime() << ": 哲學家 " << id
<< " 放下了左手邊的筷子 " << LeftHand << endl;
ReleaseSemaphore(right, 1, NULL);
fout << getNowTime() << ": 哲學家 " << id
<< " 放下了右手邊的筷子 " << RightHand << endl;
}
cout << "模擬測試達到最大次數,進程將要退出……" << endl;
fout.close();
exit(EXIT_SUCCESS);
}

上面是单个哲学家进程的进程函数,被CreateThread函数创建多个同样的进程。

实验结果

这里是任务完成后的截图或其他证明。

任务一:共享内存

下面是在 WSL 终端下执行代码的部分输出:

3_1.png

编译源代码并执行之后,终端会先输出父亲进程的输出,随后自动输出儿子进程的输出。效果如上图所示。

任务二:管道通信

在 WSL-CLion 环境下执行源代码可以获得以下输出:绿色代表stdin,白色代表stdout,红色代表stderr

3_2.png

子进程受到信息之后可以对于数字进行累加,并且正常输出父进程传入的字符串;当达到累加目标后,通过另一个管道向父亲进程发送终止信号,程序父进程退出而不是继续等待输入。

任务三:哲学家就餐

这是五个哲学家向不同文件输出日志中的一个的部分:

3_5.png

每条日志之前包含了时间轴,可以使用其他程序处理成一个文件。

体会

通过本次操作系统原理的上机实验,我更加熟练了在之前的实验中使用的在 Windows / Linux 平台上的多线程编程的能力。并了解到了使用一些方法可以实现在进程之中通信,对于内存空间和通信机制有了更加深刻的理解。可以使用所学的 API 完成在进程之间的简单通信。

哲学家就餐问题的模拟过程,让我亲身体会了从死锁产生的原因入手想方设法避免死锁产生的过程,更加深了我对于死锁产生的条件以及针对于这些条件的一些解决措施的理解和感受。

评论