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

0%

操作系统实验一：模拟进程的创建

发表于 更新于 阅读次数：

前言

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

实验目的

  • 理解进程创建的相关理论
  • 掌握进程创建的方法
  • 掌握进程相关数据结构

实验内容

本实验针对操作系统中进程创建相关理论进行实验。要求实验者输入实验指导书提供的代码并进行测试。代码简化了进程创建的多个步骤和内容。进程的树形结构采用广义二叉树的方式进行储存

实验过程

定义进程控制块PCB(Process Control Block)

为了描述和控制进程的运行，系统为每个进程定义了一个进程控制块（PCB）。它是进程实体的一部分，是操作系统进程管理中最重要的数据结构，其主要包含以下信息：

  1. 进程标识符：在系统中唯一地标识一个进程。通常包括：
    • 进程号pid
    • 父进程号ppid
    • 用户号uid。
  2. 处理机状态：处理器的状态通常由处理机的各种寄存器中的内容组成。PCB负责存放中断/阻塞/挂起时各个寄存器的值，当进程恢复执行时，进程可以从断点处恢复并继续运行。其数据结构包括：
    • 通用寄存器
    • 指令计数器
    • 程序状态字PSW
    • 用户栈指针。
  3. 进程调度信息：进程在调度过程中，系统需要记录进程的执行信息，以管理进程的运行，为进程分配CPU时间片。调度需要用到以下的信息：
    • 进程状态（就绪/阻塞/挂起）
    • 进程优先级（用于描述优先获得CPU时间片的级别的整数，高优先级的进程优先获得CPU时间片。通常情况下，该值越小优先级越高）
    • 其他信息（等待时间、运行总时间等。用于记录进程执行的相关信息）
    • 事件（描述进程挂起/阻塞的原因）
  4. 进程控制信息：用于记录进程执行所需要的资源信息，创建执行进程的程序信息以及进程锁和进程之间的通信信息。其数据结构包括：
    • 程序和数据的地址（程序在内存和外存中的首地址）
    • 进程同步和通信机制
    • 资源列表（进程除CPU以外的所有资源）
    • 链接指针（进程队列中指向下一个进程的PCB首地址）

定义进程控制块的代码如下：

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
// 基础进程控制块（PCB）
struct pcb
{
    // 进程ID
    int pid;
    // 进程父ID
    int ppid;
    // 进程优先级
    int prio;
    // 进程状态
    int state;
    // 上次运行时间
    int lasttime;
    // 进程运行总时间
    int totaltime;
};

// 进程组织结构：进程在广义二叉树或者进程链表中的节点结构
struct pnode
{
    // 当前节点对应的进程控制块
    pcb *node;
    // 进程树中，当前节点的子节点
    pnode *sub;
    // 进程树中，当前节点的兄弟节点
    pnode *brother;
    // 进程链表中，当前节点的下一节点
    pnode *next;
};

// 信号量机制，进程的资源分配
struct semaphore
{
    // 信号量资源名称
    char name[5];
    // 计数值
    int count;
    // 当前进程ID
    int curpid;
    // 等待进程链表
    pnode *wlist;
};

进程的创建

  1. 进程创建首先需要申请一个空白的PCB，获得唯一的进程ID，装载进程运行所需要的信息

  2. 为新进程分配内存和栈空间

  3. 初始化进程控制块：

    • 初始化标识信息
    • 初始化处理机状态信息
    • 初始化处理机控制信息

  4. 将新进程插入就绪队列

  5. 将新进程插入进程树中，进程树用于用于描述进程家族关系。如下图1-1中可以看出，进程P1创建了进程P2、P3、P4、P5，而P2创建了P6、P7、P8。在进程的创建过程中，我们需要将每一个新进程都插入到进程树中，有了清晰的父子关系，资源继承、进程删除等操作将会十分方便

    进程树

  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
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
// 进程树根节点
pnode *proot;
// 进程链表头节点
pnode *plink;

/**
 * 创建进程
 * para[0]: 要创建的新进程的pid
 * para[1]: 新进程的父进程pid
 * para[2]: 新进程的优先级
 **/
int createpc(int *para)
{
    /**
	 * p: 操作指针
	 * p1: 新进程的指针
	 * pp: 新进程p1的父节点
	 **/
    pnode *p, *p1, *pp;
    int pflag = 0;
    for (p=plink; p; p=p->next)
    {
        // 检查当前进程是否已创建
        if (p->node->pid == para[0])
        {
            printf("pid %d is already exist!\n", para[0]);
            return -1;
        }
        // 找到进程父节点的进程控制块
        if (p->node->pid == para[1])
        {
            pflag = 1;
            pp = p;
        }
    }
    if (!pflag)
    {
        printf("Parent id %d is not exist!\n", para[1]);
        return -2;
    }

    // 创建新的进程控制块
    p1 = new pnode;
    p1->node = new pcb;
    p1->node->pid = para[0];
    p1->node->ppid = para[1];
    p1->node->prio = para[2];
    p1->sub = NULL;
    p1->next = NULL;
    p1->brother = NULL;

    // 将新进程添加到进程树中
    if(!pp->sub)
        pp->sub = p1;
    else
    {
        // 循环遍历至兄弟子进程的最后一个
        for (p=pp->sub; p->brother; p=p->brother);
        p->brother = p1;
    }

    // 将新进程添加到进程链表中
    for (p=plink; p->next; p=p->next);
    p->next = p1;

    return 0;
}

代码汇总

PCB头文件

我们将PCB整理为一个头文件basicpcb.h，并添加如下常用工具函数，也可以使用C++标准库中的函数

函数名称 作用介绍
geterror 获取错误信息
initerror 初始化错误信息
substr 获取字串
instr 查找字符C在Str中的位置
strtoarray 将Str字符串按照格式转化为string数组

basicpcb.h代码如下：

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
// 进程控制块PCB头文件
# ifndef basicpcb_h
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define basicpcb_h

char *errormsg[256];

// 进程控制块
struct pcb
{
    // 进程ID
    int pid;
    // 进程父ID
    int ppid;
    // 进程优先级
    int prio;
    // 进程状态
    int state;
    // 上次运行时间
    int lasttime;
    // 进程运行总时间
    int totaltime;
};

// 进程在广义二叉树或者进程链表的节点结构
struct pnode
{
    // 当前节点对应的进程控制块
    pcb *node;
    // 进程链树中，当前节点的子节点
    pnode *sub;
    // 进程树中，当前节点的兄弟节点
    pnode *brother;
    // 进程链表中，当前节点的下一节点
    pnode *next;
};

// 信号量机制
struct semaphore
{
    // 信号量资源名称
    char name[5];
    // 计数值
    int count;
    // 当前进程ID
    int curpid;
    // 等待进程链表
    pnode *wlist;
};

// 获取错误信息
# define geterror(eno) printf("%s\n", errormsg[eno]);

// 生成错误信息
void initerror() 
{
    errormsg[0] = (char *) malloc(20);
    strcpy(errormsg[0], "Error command!");
    // errormsg[0] = "Error command!";
    errormsg[1] = (char *) malloc(20);
    // errormsg[1] = "Error parameter!";
    strcpy(errormsg[1], "Error parameter!");
}

// 获取子字符串
char *substr(char *s, int start, int end)
{
    char *s1;
    int len = strlen(s);
    if (start<0 || end>=len || start>end)
        return NULL;
    s1 = (char *) malloc(end - start + 2);

    int pos = 0;
    for (; pos <= end-start; pos++)
    {
        s1[pos] = s[pos+start];
    }
    s1[pos] = '\0';

    return s1;
}

// 查找字符C在Str中的位置
int instr(char *s, char c)
{
    unsigned int i;
    for (i = 0; i < strlen(s); i++)
    {
        if (s[i] == c)
        {
            return i;
        }
    }
    return -1;
}

// 将Str字符串转为string数组
int *strtoarray(char *s)
{
    /**
	 * str: XXX,XXX,XXX
	 * a: 用于记录每个字符的下标
	 * count: 用于记录字符串中','出现的次数
	 * x1: 储存','在字符串s1中出现的位置
	 * s1: 记录截取字符串后的s
	 * s2: 储存每个子字符串的指针
	 * c: 储存','
	 **/
    int *a, count, x1;
    unsigned int i;
    char c, *s1, *s2;
    if (!s)
    {
        printf("String can't be NULL!\n");
        return NULL;
    }

    count = 0;
    s1 = s;
    for (i = 0; i < strlen(s1); i++)
    {
        if (s1[i] == ',')
            count++;
    }
    count++;

    a = (int *) malloc(count);
    c = ',';
    for (i = 0; i < count; i++)
    {
        x1 = instr(s1, c);
        if (x1 >= 0)
            s2 = substr(s1, 0, x1-1);
        else
            s2 = s1;
        // 将string转为int
        a[i] = atoi(s2);
        s1 = substr(s1, x1+1, strlen(s1)-1);
    }
    return a;
}

# endif

进程创建具体实现

我们在process.cpp文件中实现进程的创建，并编写了main函数进行测试

process.cpp代码如下：

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
# include "basicpcb.h"

// 进程树根节点
pnode *proot;
// 进程链表头节点
pnode *plink;

/**
 * 创建进程
 * para[0]: 要创建的新进程的pid
 * para[1]: 新进程的父进程pid
 * para[2]: 新进程的优先级
 **/
int createpc(int *para)
{
    /**
	 * p: 操作指针
	 * p1: 新进程的指针
	 * pp: 新进程p1的父节点
	 **/
    pnode *p, *p1, *pp;
    int pflag = 0;
    for (p=plink; p; p=p->next)
    {
        // 检查当前进程是否已创建
        if (p->node->pid == para[0])
        {
            printf("pid %d is already exist!\n", para[0]);
            return -1;
        }
        // 找到进程父节点的进程控制块
        if (p->node->pid == para[1])
        {
            pflag = 1;
            pp = p;
        }
    }
    if (!pflag)
    {
        printf("Parent id %d is not exist!\n", para[1]);
        return -2;
    }

    // 创建新的进程控制块
    p1 = new pnode;
    p1->node = new pcb;
    p1->node->pid = para[0];
    p1->node->ppid = para[1];
    p1->node->prio = para[2];
    p1->sub = NULL;
    p1->next = NULL;
    p1->brother = NULL;

    // 将新进程添加到进程树中
    if(!pp->sub)
        pp->sub = p1;
    else
    {
        // 循环遍历至兄弟子进程的最后一个
        for (p=pp->sub; p->brother; p=p->brother);
        p->brother = p1;
    }

    // 将新进程添加到进程链表中
    for (p=plink; p->next; p=p->next);
    p->next = p1;

    return 0;
}

// 显示进程信息
void showdetail()
{
    pnode *p, *p1;
    p = plink;
    // 将所有进程信息打印
    while (p != NULL)
    {
        printf("(pid: %d - prio: %d): ", p->node->pid, p->node->prio);
        p1 = p->sub;
        // 打印子进程信息
        while (p1 != NULL)
        {
            printf("   (pid: %d - prio: %d)", p1->node->pid, p1->node->prio);
            p1 = p1->brother;
        }
        printf("\n");
        p = p->next;
    }
    printf("\n");
}

// 初始化根节点
void initprocess() {
    proot = new pnode;
    proot->node = new pcb;
    proot->node->pid = 0;
    proot->node->ppid = -1;
    proot->node->prio = 0;
    proot->next = NULL;
    proot->sub = NULL;
    proot->brother = NULL;

    plink = proot;
}

// 命令控制台
void processterminal() {
    short cflag, pflag;
    char cmdstr[32];

    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;
            printf("\n=================================================\n");
            printf("pid: 当前进程ID  ppid: 父进程ID  prio: 进程优先级\n");
            printf("创建新进程: createpc(pid,ppid,prio)\n");
            printf("查看当前进程信息: showdetail\n");
            printf("获取帮助: help\n");
            printf("退出: exit\n");
            printf("=================================================\n\n");
        }

        // 创建新进程，判断createpc是否为cmdstr字串
        if (strstr(cmdstr, "createpc"))
        {
            int *para;
            char *s;
            
            cflag = 1;

            // 获取创建新进程的参数 -> pid,ppid,prio
            int start = instr(cmdstr, '(');
            int end = instr(cmdstr, ')');
            s = substr(cmdstr, start+1, end-1);

            para = (int *) malloc(3);
            para = strtoarray(s);
            createpc(para);

            pflag = 1;
        }

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

int main(int argc, char const *argv[])
{
    initerror();

    initprocess();

    processterminal();

    return 0;
}

实验测试

  1. 编译并运行程序

    g++ process.cpp -o process

    编译并运行

  2. 使用help命令查看帮助

    help命令

  3. 使用createpc命令创建进程，使用showdetail命令查看进程信息

    创建进程

总结

本次实验我们模拟了一次进程的创建，在模拟创建的过程中，我们了解了进程控制块的定义，进程之间的组织方式，如何将进程添加到进程树和进程总链中。在现在的操作系统中，进程的创建还需要加载静态和计算机硬件资源，这比我们自己做的实验要复杂的多。