自由尋覓快樂別人從沒法感受

0%

操作系统实验三：模拟P、V操作

发表于 阅读次数：

前言

操作系统系列博客的所有实验源自于课程"操作系统原理与实践检验"，代码是参考老师给的"软件工程专业操作系统实验指导书"文档后的改进版本。操作系统是计算机系统的核心，因此了解操作系统的设计和实现思路是必不可少的。了解操作系统的基本要求是：理解进程的概念，理解死锁，掌握银行家算法；掌握页式储存管理的实现原理以及页面置换法

实验目的

  1. 理解信号量相关理论
  2. 掌握记录型信号量结构
  3. 掌握 P、V 原语实现机制

实验内容

本实验针对操作系统中信号量的相关理论进行实验，要求实验者输入实验指导书提供的代码并进行测试。代码主要模拟信号量的P（down）、V（up）操作

  • 信号量

    信号量也称为信号锁，主要应用于进程间的同步和互斥，在用于互斥时，信号量通常作为资源锁。信号量通过两个原子操作P（down）和V（up）来访问。down操作使信号量的值-1，up操作使信号量的值+1

  • 记录型信号量

    记录型信号量采用了“让权等待”的策略，当存在多个资源访问同一个临界资源的情况时，记录型信号量可以使用一个等待链来存放等待使用资源的进程。在本次实验中，我们使用的是记录型信号量

实验过程

  • 对于P（down）操作。首先我们需要判断申请的临界资源是否存在。若该资源存在，接下来我们要判断该资源是否被其他进程使用中。如果其他进程使用中，我们将申请使用该资源的进程添加到等待链表中，并且信号量-1。如果没有其他进程使用中，则信号量-1，并将该资源标识为该进程使用中
  • 对于V（up）操作。首先我们需要判断释放的临界资源是否存在。若该资源存在，接下来我们可以释放该资源，并查看等待链表中是否有正在等待使用资源的进程。如果没有等待使用资源的进程，则该资源的信号量+1，如果有等待使用资源的进程，我们将其从等待链表移入到正在使用的列表中，同时信号量+1

代码汇总

basicpcb.h已经定义了关于信号量的结构体，我们只需要创建semaphore.cpp，并实现P、V操作

P操作

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
// 申请资源 -> P操作
void down(char *sname, int pid)
{
    /**
	 * sflag: 信号量找到标志
	 * pflag: 进程找到标志
	 * p: 找到的进程节点
	 * s: 找到的信号量节点
	 **/
    int sflag = 0, pflag = 0;
    pnode *p;
    semaphore *s;

    // 根据名字查找信号量
    for (int i = 0; i < SEMAPHORE_NUMBER; i++)
    {
        if (!strcmp(sem[i].name, sname))
        {
            s = &sem[i];
            sflag = 1;
            break;
        }
    }

    // 根据进程ID查找进程
    for (int i = 0; i < PROCESS_NUMBER; i++)
    {
        if (pr[i]->node->pid == pid)
        {
            p = pr[i];
            pflag = 1;
            break;
        }
    }

    // 目标信号量或进程未找到
    if (!sflag || !pflag)
    {
        printf("Semaphore %s not exist or Process %d not exist.\n", sname, pid);
        printf("Semaphore find result: %d. Process find result: %d\n", sflag, pflag);
        return;
    }

    // 信号量-1
    s->count--;
    // 临界资源仍足够
    if (s->count >= 0)
    {
        s->curpid = p->node->pid;
    }
    // 临界资源不足
    else
    {
        // 添加到等待列表
        if (s->wlist != NULL)
        {
            pnode *tmp = s->wlist;
            while (tmp->next != NULL)
                tmp = tmp->next;
            tmp->next = p;
        }
        else
        {
            s->wlist = p;
        }
    }
}

V操作

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
// 释放资源 -> V操作
void up(char *sname)
{
    /**
	 * sflag: 信号量找到标志
	 * spos: 信号量位置
	 **/
    int sflag = 0, spos;

    // 查找信号量
    for (int i = 0; i < SEMAPHORE_NUMBER; i++)
    {
        if (!strcmp(sem[i].name, sname))
        {
            sflag = 1;
            spos = i;
            break;
        }
    }

    // 信号量未找到
    if (!sflag)
    {
        printf("Semaphore %s not found\n", sname);
        return;
    }

    /**
	 * 释放资源
	 * 如果等待列表中有进程，count数量不变，等待列表入队
	 * 如果等待列表中无进程，count数量++
	 **/
    if (sem[spos].wlist != NULL)
    {
        sem[spos].curpid = sem[spos].wlist->node->pid;
        sem[spos].wlist = sem[spos].wlist->next;
    }
    else
    {
        sem[spos].count++;
    }
}

其他完善程序的函数

我们需要完善showdetail()，help()，init()，terminal()函数来让整个程序跑起来

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
// 在程序的最开始定义宏
# define SEMAPHORE_NUMBER 5
# define PROCESS_NUMBER 20

// 定义5个信号量
semaphore sem[SEMAPHORE_NUMBER];
// 定义0-19一共20个进程
pnode *pr[PROCESS_NUMBER];

// 查看临界资源使用状态
void showdetail()
{
    printf("\n===================================================\n");
    for (int i = 0; i < SEMAPHORE_NUMBER; i++)
    {
        if (sem[i].count <= 0)
        {
            printf("%s (Current process id: %d) | Wait list: ", sem[i].name, sem[i].curpid);
            pnode *p = sem[i].wlist;
            while (p != NULL)
            {
                printf("%5d ->", p->node->pid);
                p = p->next;
            }
            printf("   List end\n");
        }
        else
        {
            printf("%s now avaliable\n", sem[i].name);
        }
    }
    printf("===================================================\n\n");
}

// 帮助命令
void help()
{
    printf("\n===================================================\n");
    printf("sname: 临界资源名称  pid: 进程ID\n");
    printf("申请资源: down(sname,pid)\n");
    printf("释放资源: up(sname)\n");
    printf("查看当前资源使用情况: showdetail\n");
    printf("获取帮助: help\n");
    printf("退出: exit\n");
    printf("===================================================\n\n");
}

void init()
{
    // 初始化信号量semaphore
    for (int i = 0; i < SEMAPHORE_NUMBER; i++)
    {
        char sname[] = {'s', i+48, '\0'};
        strcat(sem[i].name, sname);
        sem[i].wlist = NULL;
        sem[i].count = 1;
    }

    // 初始化进程
    for (int i = 0; i < PROCESS_NUMBER; i++)
    {
        pr[i] = new pnode;
        pr[i]->node = new pcb;
        pr[i]->node->pid = i;
        pr[i]->brother = NULL;
        pr[i]->next = NULL;
        pr[i]->sub = NULL;
    }
}

void terminal()
{
    short cflag, pflag;
    char cmdstr[32];

    initerror();
    init();

    while (1)
    {
        cflag = 0;
        pflag = 0;
        printf("cmd: ");
        scanf("%s", cmdstr);

        if (!strcmp(cmdstr, "exit"))
        {
            break;
        }

        if (!strcmp(cmdstr, "showdetail"))
        {
            cflag = 1;
            pflag = 1;
            showdetail();
        }

        if (!strcmp(cmdstr, "help"))
        {
            cflag = 1;
            pflag = 1;
            help();
        }

        if (strstr(cmdstr, "down"))
        {
            cflag = 1;

            char *sname = substr(cmdstr, instr(cmdstr, '(')+1, instr(cmdstr, ',')-1);
            char *pid = substr(cmdstr, instr(cmdstr, ',')+1, instr(cmdstr, ')')-1);

            if (sname && pid)
            {
                down(sname, atoi(pid));
                pflag = 1;
            }
        }

        if (strstr(cmdstr, "up"))
        {
            cflag = 1;

            char *sname = substr(cmdstr, instr(cmdstr, '(')+1, instr(cmdstr, ')')-1);
            
            if (sname)
            {
                up(sname);
                pflag = 1;
            }
        }

        // 输入错误或参数错误
        if (!cflag)
            geterror(0);
        if (!pflag)
            geterror(1);
    }
}

// 整个semaphore.cpp程序的入口
int main(int argc, char const *argv[])
{
    terminal();
    return 0;
}

实验测试

  1. 编译并运行程序

    g++ semaphore.cpp -o semaphore && ./semaphore

    编译运行

  2. 使用help命令查看帮助

    查看帮助

  3. 使用down命令申请资源，使用up命令释放资源，使用showdetail查看资源使用情况

    PV操作

    从上图中可以看到，我们申请了临界资源，程序会判断临界资源和进程是否同时存在，再进行P操作，释放资源也是如此。但是我们的程序有一个缺点，就是PV操作必须要成对地进行，而且一个进程不能多次申请同一个临界资源，因为我们没有对其进行限制。这是程序不完美的地方

    总结

    在本次的实验中，我们模拟进行了进程的P、V操作。PV操作解决了临界资源的分配问题，进程可以通过一个等待列表来先后使用需要的资源，但是PV操作存在一个问题就是：如果A进程占用了1号资源，需要再申请占用2号资源才能运行；而B进程占用了2号资源，需要再申请占用1号资源才能运行。这就造成了死锁的问题，对于该问题的解决方案，人们提出了“银行家算法”，在计算进程申请资源后是否会造成死锁问题后，选择不会形成死锁的解决方案来分配进程，破坏进程死锁产生的条件。该算法虽然会影响系统的性能，但与死锁造成的资源浪费、产生死锁后再解决问题相比，“银行家算法”显然是一个比较好的解决方案

    课后思考

    1. 如何修改down操作，使之能一次申请多个信号量？

      将down函数的信号量参数改为一个信号量数组之后，进程能一次申请多个信号量。这会同时带来进程的死锁问题，为了避免该问题，其中一个解决方案：将信号量的申请改为&&关系，即该进程的一次申请中，所有要申请的临界资源都能使用，才能正式分配资源

    2. 在某个时刻，一个进程最多可以等待多少个信号量？

      从理论上来说，一个进程最多可以等待很多个信号量。但是如果等待的信号量越多，产生死锁的可能性就越来越大，为了避免死锁的产生，进程最好是不需要等待信号量，或者在可控范围下等待信号量