neu-os-experiments

注意注意一定要看！！！

使用阿里OSS+typora+picgo图床一键自动上传图片的时候，总是会出现复制到md文档里面的图片顺序出现混乱的情况，我的初步猜测是picgo图片上传的时候速度不一样与阿里OSS自动生成的图片ID不一样导致的矛盾。（事实上，我相信有基础的兄弟们就算是看乱序的图片也能对应的上正确的位置）

我想修改来着，但工作量繁琐且收效甚微。（因为我的GitHub仓库有完整的报告，所以直接上我的GitHub仓库吧，

https://github.com/BradTorres/neu-os-experiments

如果想看初步粗略看的话，可以接着往下看）

正文

NEU操作系统实验（共四次）

详情见实验ppt

实验一：三状态转换（五状态，七状态）

实验二：生产者消费者模型

实验三：管道通信与进程同步

实验四：页面置换算法

实验内容说明请参考实验PPT

实验一

一． 实验内容

1.设计并实现一个模拟进程状态转换及其相应PCB组织结构变化的程序。

2.独立设计、编写、调试程序。

3.程序界面应能反映出在模拟条件下，进程之间状态转换及其对应的PCB组织的变化。

4.进程的状态模型（三状态、五状态、七状态或其它）可自行选择。

二． 程序流程图

img

三． 程序描述

使用C++进行开发，实现了一个五状态的进程间状态转移的模型。同时设定了内存的机制，具备一定的运行内存限制（100M），若处理进程内存超过系统内存限制则会先被放入等待队列中。完成了界面功能，可以显示实时的不同队列中的进程的id。

自定义了结构体 pcb，组织方式采用的是链表。结构体 pcb用来存储一个进程的 id和指向下一个节点的指针next。同一状态的进程其PCB成一队列，多个状态对应多个不同的队列；

所以这里形成了不同的队列：新建队列、就绪队列、运行队列、阻塞队列。可以实现初始化新建队列、就绪队列、运行队列、阻塞队列以及下述七个操作。

0:exit

1:Dispatch(ReadyQueue->RunningQueue)

2:Timeout(RunningQueue->ReadyQueue)

3:Event Wait(RunningQueue->BlockedQueue)

4:Event Occurs(BlockedQueue->ReadyQueue)

5:Admit(NewQueue->ReadyQueue)

6:Release(RunningQueue->Exit)

定义了 4 个队列，分别用来储存 Ready,Running,Block,New 队列。同时考虑到了非法的输入，对于不同的非法输入都有处理。同时设定了不同操作之间的在不同情况下的连带关系，例如结束进程后会自动把新的就绪态进程派遣到运行队列中等等。

四． 实验结果（部分截图）

创建进程

img

5:Admit(NewQueue->ReadyQueue)进入就绪队列。其他操作类似，都是实现进程队列的切换。

五． 部分核心代码

结构体定义

1
2
3
4
5
6
7
8
9
10
11

typedef int ElemType;
typedef struct pcb
{
    ElemType id;
    struct pcb *next;
} pcb;

pcb *NewQueue, *ReadyQueue, *RunningQueue, *BlockedQueue, *ExitQueue;


具体函数见我的GitHub仓库

主函数

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

int main()
{
    NewQueue = create();
    ReadyQueue = new pcb;
    ReadyQueue->next = NULL;
    RunningQueue = new pcb;
    RunningQueue->next = NULL;
    BlockedQueue = new pcb;
    BlockedQueue->next = NULL;
    ExitQueue = new pcb;
    ExitQueue->next = NULL;
    // RunningQueue和BlockedQueue没有对第一个结点的id赋值，在insert（）之后，属于带头结点的队列，保持和ReadyQueue一样的结构
    show();
    int ChangeNum;
    cout << "Please choose one of the following actions" << endl;
    cout << "0:exit" << endl;
    cout << "1:Dispatch(ReadyQueue->RunningQueue)" << endl;
    cout << "2:Timeout(RunningQueue->ReadyQueue)" << endl;
    cout << "3:Event Wait(RunningQueue->BlockedQueue)" << endl;
    cout << "4:Event Occurs(BlockedQueue->ReadyQueue)" << endl;
    cout << "5:Admit(NewQueue->ReadyQueue)" << endl;
    cout << "6:Release(RunningQueue->Exit)" << endl;

    while (cin >> ChangeNum)
    {
        if (ChangeNum == 0)
        {
            break;
        }
        else if (ChangeNum == 1)
        {
            if (ReadyQueue->next)
            {
                if (RunningQueue->next)
                {
                    insert(BlockedQueue, RunningQueue->next);
                    del(RunningQueue);
                }
                insert(RunningQueue, ReadyQueue->next);
                del(ReadyQueue);
            }
            else
            {
                if (BlockedQueue->next)
                {
                    insert(BlockedQueue, RunningQueue->next);
                    del(RunningQueue);
                    insert(RunningQueue, BlockedQueue->next);
                    del(BlockedQueue);
                }
            }
        }
        else if (ChangeNum == 2)
        {
            if (RunningQueue->next)
            {
                if (ReadyQueue->next)
                {
                    insert(ReadyQueue, RunningQueue->next);
                    del(RunningQueue);
                    insert(RunningQueue, ReadyQueue->next);
                    del(ReadyQueue);
                }
            }
        }
        else if (ChangeNum == 3)
        {
            if (RunningQueue->next)
            {
                if (ReadyQueue->next)
                {
                    insert(BlockedQueue, RunningQueue->next);
                    del(RunningQueue);
                    insert(RunningQueue, ReadyQueue->next);
                    del(ReadyQueue);
                }
                else
                {
                    insert(BlockedQueue, RunningQueue->next);
                    del(RunningQueue);
                    insert(RunningQueue, BlockedQueue->next);
                    del(BlockedQueue);
                }
            }
        }
        else if (ChangeNum == 4)
        {
            if (BlockedQueue->next)
            {
                insert(ReadyQueue, BlockedQueue->next);
                del(BlockedQueue);
            }
        }
        else if (ChangeNum == 5)
        {
            if (NewQueue->next)
            {
                insert(ReadyQueue, NewQueue->next);
                del(NewQueue);
            }
        }
        else if (ChangeNum == 6)
        {
            if (RunningQueue->next)
            {
                insert(ExitQueue, RunningQueue->next);
                del(RunningQueue);
                // del(ExitQueue);释放处于结束状态的进程结点
                // 也可以直接释放RunnningQueue的结点
                if (ReadyQueue->next)
                {
                    insert(RunningQueue, ReadyQueue->next);
                    del(ReadyQueue);
                }
            }
        }
        else
        {
            cout << "You can only type in numbers in range(0~6)" << endl;
        }
        show();
        cout << "Please choose one of the following actions" << endl;
        cout << "0:exit" << endl;
        cout << "1:Dispatch(ReadyQueue->RunningQueue)" << endl;
        cout << "2:Timeout(RunningQueue->ReadyQueue)" << endl;
        cout << "3:Event Wait(RunningQueue->BlockedQueue)" << endl;
        cout << "4:Event Occurs(BlockedQueue->ReadyQueue)" << endl;
        cout << "5:Admit(NewQueue->ReadyQueue)" << endl;
        cout << "6:Release(RunningQueue->Exit)" << endl;
    }

    return 0;
}

实验二

一． 实验内容

1.调试、运行给出的程序，从操作系统原理的角度验证程序的正确性。

2.发现并修改程序中的原理性错误或不完善的地方。

3.鼓励在程序中增加新的功能。完成基本。

二． 程序流程图

见我的GitHub仓库

三． 程序描述

利用写指针和读指针实现了生产者和消费者对缓冲区按顺序进行生产和消费。同时设定了缓冲区 BUFFER，设定了缓冲区的大小。

当缓冲区已满时，再次创建的生产进程会进入阻塞队列中，而下次消费者消费了一个产品后，会自动将阻塞队列中的生产进程执行并将产品放入缓冲区。同理消费者也有消费者阻塞队列，也能在产品生产后自动执行消费进程。

四． 实验结果（部分截图）

按P创建生产进程，将产出产品放入缓冲区。

img

按C创建消费进程，对缓存区产品进行消费。

img

当缓冲区满时，新创建的生产者进程会被加入生产者阻塞队列。

img

当消费者进程执行后，缓冲区重新获得空间，会自动执行阻塞队列中的生产者进程。

img

消费者进程同样会被阻塞，并放入阻塞队列。

img

img

五． 部分核心代码

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

// 生产
void produce()
{
    if (findEmpty(buffer, BUFFER_SIZE) == -1)
    {
        // 缓冲区满,阻塞
        number = number + 1;
        producer++;
        pQueue.push(number);
    }
    else if (isEmpty(buffer, BUFFER_SIZE))
    {
        // 缓冲区空
        if (cQueue.empty())
        {
            // 消费者等待队列为空,直接写入即可
            number = number + 1;
            buffer[writeptr] = number;
        }
        else
        {
            // 有阻塞的消费者，先写入再读出
            number = number + 1;
            buffer[writeptr] = number;
            show(); // 不仅在produce函数运行全部完成后show，在中间就show一次
            sleep(2);
            buffer[readptr] = 0;
            readptr = (readptr + 1) % BUFFER_SIZE;
            consumer--;
            cQueue.pop();
        }
        writeptr = (writeptr + 1) % BUFFER_SIZE;
    }
    else
    {
        // 缓冲区不空也不满,直接写入即可
        number = number + 1;
        buffer[writeptr] = number;
        writeptr = (writeptr + 1) % BUFFER_SIZE;
    }
}

// 消费
void consume()
{
    if (findDirty(buffer, BUFFER_SIZE) == -1) // buffer里面全都是0
    {
        // 缓冲区空,则阻塞
        // ++number;但事实上不能让number++，不然number的数值就变了，
        consumer++;
        cQueue.push(number);
    }
    else if (isFull(buffer, BUFFER_SIZE))
    {
        // 缓冲区满
        if (!pQueue.empty())
        {
            // 生产者等待队列不空，则先读出再写入
            buffer[readptr] = 0;
            readptr = (readptr + 1) % BUFFER_SIZE;
            show(); // 不仅在consume函数运行全部完成后show，在中间就show一次
            sleep(2);
            buffer[writeptr] = pQueue.front();
            writeptr = (writeptr + 1) % BUFFER_SIZE;
            pQueue.pop();
            producer--;
        }
        else
        {
            // 生产者队列为空
            buffer[readptr] = 0;
            readptr = (readptr + 1) % BUFFER_SIZE;
        }
    }
    else
    {
        // 缓冲区不空也不满,直接读取即可
        buffer[readptr] = 0;
        readptr = (readptr + 1) % BUFFER_SIZE;
    }
}

实验三

一． 实验内容

1.使用系统调用pipe()建立一条管道，系统调用fork()分别创建两个子进程，它们分别向管道写一句话，如：

Child process1 is sending a message!

Child process2 is sending a message!

2.父进程分别从管道读出来自两个子进程的信息，显示在屏幕上。

二． 程序流程图

见我的GitHub仓库

三． 程序描述

在 linux 系 统 的 环 境 下 使 用 C++ 完 成 实 验 ， 使 用 了 系 统 调 用fork(),read(),write(),pipe(),lockf(),wait(),exit(),sleep()等。随机创建了三个子进程，并且按照相关语句进行输出以检查进程执行顺序。过程中通过加锁解锁和wait函数对进程进行控制。（事实上是n个紫荆城

使用系统调用 pipe()建立一条管道，系统调用 fork()分别创建两个子进程，它们分别向管道写一句话，如：Child process1 is sending a message! Child process2 is sending a message!父进程分别从管道读出来自两个子进程的信息，显示在屏幕上

四． 实验结果（部分截图）

img

五． 部分核心代码

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

#define F_ULOCK 0 // 解锁
#define F_LOCK 1  // 互斥锁定区域

int main()
{
    int num, fd[2], result = -1;
    pid_t pid, reid, gtid;
    char outpipe[100], father_str[100];

    // 创建管道, fd[0]读管道，fd[1]写管道
    result = pipe(fd);
    if (result == -1) // 调用失败
    {
        printf("fail to create pipe \n");
        return -1;
    }

    // 创建子进程
    printf("Please input the number of processes: ");
    scanf("%d", &num);
    printf("\n-------------------------分割线----------------------\n");

    while (num > 0)
    {
        pid = fork();
        printf("pid: %d\n", pid);

        if (pid == -1)
        {
            // 创建失败
            printf("creat subprocess failed!\n");
            exit(0);
        }
        else if (pid == 0)
        {
            // 创建子进程，从子进程返回ID
            printf("now I'm writing in subprocess %d\n", gtid = getpid());
            lockf(fd[1], F_LOCK, 0); // 加锁
            sprintf(outpipe, "child process %d is sending message!\n", gtid);
            write(fd[1], outpipe, sizeof(outpipe));
            sleep(1);
            lockf(fd[1], F_ULOCK, 0); // 解锁
            printf("send message successfully and exit subprocess %d\n", gtid);
            exit(0);
        }
        else if (pid > 0)
        {
            // 创建子进程，从父进程返回子进程的ID
            reid = wait(NULL); // 等待一个子线程结束？？？
            if (reid == -1)
            {
                printf("father process calls subprocess failed!\n");
            }
            else
            {
                read(fd[0], father_str, sizeof(father_str));
                printf("\nfather process reads from subprocess %d:\n", reid);
                printf("%s\n", father_str);
            }
        }
        printf("\n-------------------------分割线----------------------\n");

        num--;
    }
    return 0;
}

实验四

一． 实验内容

这是一个综合型实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。

程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series[]中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。要求：

1） 每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。

设缺页的次数为diseffect。总的页面访问次数为total_instruction。

缺页率 = disaffect/total_instruction

命中率 = 1- disaffect/total_instruction

2）将为进程分配的内存页面数mframe作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。

二． 程序流程图

见我的GitHub仓库

三． 程序描述

对生产的随机页面数据，开展了FIFO与LRU的页面置换算法，并对置换效果和命中率等信息进行展示。并对FIFO中的Belady现象进行了检验。

完成了基础点： 程序用父进程创建两个子进程， 父进程产生随机序列并完成初始化，两个子进程分别实现 FIFO 算法和 LRU 算法，并分别输出每个状态的内存中页帧状态，最终输出缺页率。

完成了扩展点一： 可以使用父进程创建了两个子进程,两个子进程分别使用不同大小的驻留集，都是用 FIFO 的置换算法，最终可以观察到驻留集更大的子进程反而缺页率更高。

程序涉及一个父进程和两个子进程。父进程使用 rand()函数随机产生若干随机数，经过处理后，存于一数组 Acess_Series[]中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用 FIFO 和 LRU 两种不同的页面置换算法对内存页面进行调度。同时统计不同的页面调度算法的缺页率。在 linux 系 统 的 环 境 下 使 用 C++ 并 用 g++ 进 行 编 译 完 成 实 验 ， 使 用 了 系 统 调 用fork(),wait(),exit(),sleep(),rand()等。可以随意修改程序序列的长度。

四． 实验结果（部分截图）

对于随机生产的页面序号分别进行FIFO、LRU进行页面置换，对FIFO进行再一次执行以检验是否有Belady现象发生。

若选择要看Belady异常

img

img

img

若选择不要看Belady异常

img

img

五． 部分核心代码

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
// 实现FIFO算法
void FIFO(int memory_blocks_number, int choice = 0)
{
    printf("%d\n",choice);
    printf("\nFIFO的内存块数： %d 块\n", memory_blocks_number);
    // 这里没有随机化数组元素，之后再加
    /*
    total_instructions为总的页面访问次数
    diseffect为缺页数
    pageid为想访问的页面的序号
    */
    int total_instructions = 12;
    srand((unsigned)time(NULL));

    int Acess_Series[total_instructions] = {3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4};
    if (choice == 1)
    {
        for (int i = 0; i < total_instructions; i++)
        {
            Acess_Series[i] = rand() % 10;
        }
    }
    // srand((unsigned)time(NULL));

    // 3
    Page_Frame page_Frame(memory_blocks_number);
    std::deque<int> fifo_queue; // 双段队列
    int diseffect = 0;

    for (int i = 0; i < total_instructions; ++i)
    {
        int pageid = Acess_Series[i];
        printf("访问页面序号：%d ", pageid);
        /*
        对Acess_Series数组里面的数字，判断以下三种情况
        1 内存块中存在此页面,什么都不用做
        2 内存块中无此页面，且内存块未满，直接加入
        3 内存块中无此页面，且内存块已满，取出队列首个元素（FIFO算法）
        */
        // find返回的是指针，指向找序列里面第一个出现的地方
        // 存在此页面
        if (find(page_Frame.pageframe_array.begin(), page_Frame.pageframe_array.end(), pageid) != page_Frame.pageframe_array.end())
        {
            page_Frame.print_info();
        }
        else
        {
            // 无此页面，缺页数先加一
            diseffect++;
            fifo_queue.push_back(pageid);
            // 同时内存快未满
            if (page_Frame.occupied_size < page_Frame.pageframe_size)
            // if (page_Frame.pageframe_array.size() < page_Frame.pageframe_size)
            {
                // 直接加入
                page_Frame.occupied_size++;
                page_Frame.pageframe_array.push_back(pageid);
                page_Frame.print_info();
            }
            else
            {
                // 同时内存块已满
                int be_replaced_pageid = fifo_queue.front();
                fifo_queue.pop_front();
                auto be_replaced_pageid_iter = find(page_Frame.pageframe_array.begin(), page_Frame.pageframe_array.end(), be_replaced_pageid);
                *be_replaced_pageid_iter = pageid;
                page_Frame.print_info();
            }
        }
    }
    printf("缺页数：%d  缺页率：%f  命中率：%f\n", diseffect, (float)diseffect / total_instructions, (1 - (float)diseffect / total_instructions));
    printf("\n--------------------------------分割线-------------------------------\n");
}

void LRU()
{
    int total_instructions = 20;

    int Acess_Series[total_instructions] = {1, 8, 1, 7, 8, 2, 7, 2, 1, 8, 3, 8, 2, 1, 3, 1, 7, 1, 3, 7};
    for (int i = 0; i < total_instructions; i++)
    {
        Acess_Series[i] = rand() % 10;
    }

    Page_Frame page_Frame(4); // 是一个数组
    int diseffect = 0;        // 缺页数
    for (int i = 0; i < total_instructions; i++)
    {
        int pageid = Acess_Series[i];
        printf("访问页面序号：%d ", pageid);
        /*
       对Acess_Series数组里面的数字，判断以下三种情况
       1 内存块中存在此页面,则把其次数置为0即可
       2 内存块中无此页面，且内存块未满，直接加入
       3 内存块中无此页面，且内存块已满，找到最近最久未使用的页面
       */
        std::vector<int>::iterator iter;
        if ((iter = find(page_Frame.pageframe_array.begin(), page_Frame.pageframe_array.end(), pageid)) != page_Frame.pageframe_array.end())
        {
            page_Frame.add_pageframe_array_time();
            int position = std::distance(page_Frame.pageframe_array.begin(), iter);
            page_Frame.pageframe_array_time.at(position) = 0; // 新出现一次，就置成0,越大代表越久没有访问，0代表刚刚访问
            page_Frame.print_info();
        }
        else
        {
            // 内存中无此页面,缺页数加一
            diseffect++;
            // 且内存块未满，直接加入
            if (page_Frame.occupied_size < page_Frame.pageframe_size)
            {
                page_Frame.add_pageframe_array_time();
                page_Frame.occupied_size++;
                page_Frame.pageframe_array.push_back(pageid);
                page_Frame.pageframe_array_time.push_back(0); // 0代表刚刚访问
                page_Frame.print_info();
            }
            else
            {
                // 且内存块已满，找到最近最久未使用的页面,也就之找到times次数最大的数组下标
                page_Frame.add_pageframe_array_time();
                auto max_iter = std::max_element(page_Frame.pageframe_array_time.begin(), page_Frame.pageframe_array_time.end());
                int max_position = std::distance(page_Frame.pageframe_array_time.begin(), max_iter);
                page_Frame.pageframe_array.at(max_position) = pageid;
                page_Frame.pageframe_array_time.at(max_position) = 0;
                page_Frame.print_info();
            }
        }
    }
    printf("缺页数：%d  缺页率：%f  命中率：%f\n", diseffect, (float)diseffect / total_instructions, (1 - (float)diseffect / total_instructions));
    printf("\n--------------------------------分割线-------------------------------\n");
}

源码和其余参考资料见我的github仓库

https://github.com/BradTorres/neu-os-experiments