实验一、进程创建、调度与撤消

实验一、进程创建、调度与撤消

一、目的

通过进程的创建和调度的设计来达到如下目的：

1. 加深对进程概念的理解，明确进程和程序的区别；
2. 进一步认识并发执行的概念，区别顺序执行和并发执行；
3. 深入了解系统如何组织进程，创建进程；
4. 进一步认识如何实现处理机调度。

二、内容

????????在WINDOWS环境下模拟实验：

1. 编写一程序，来模拟进程的创建和撤消，要求通过终端键盘输入几个作业的名称、大小、优先级等。系统为它创建进程，并把进程控制块PCB（进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、程序大小、已用CPU时间、进程状态等等）的内容送到终端显示器上输出。
2. 同时模拟内存空间为作业分配内存空间，并把结果用图形形象地表示出来，同样通过终端输出。
3. 从下面四个调度算法中，选择一个调度算法来实现进程调度：

????????a、先来先服务调度算法；

????????b、短进程优先调度算法；

????????c、优先数调度算法；

????????d、时间片轮法调度算法；

三、详细设计

该模拟系统主要，主要使用结构体存储PCB的基本信息和就绪队列链队LinkQueue，写了6个关键的函数，具体实现如下：

?---PCB结构体、就绪队列LinkQueue（采用链队的存储方式）如下：

（1）//控制块PCB的信息
struct PCB
{
? ? char name[10];
? ? int id;
? ? int atime; //进程到达时间
? ? int stime; //服务时间，运行时间
? ? int ftime; //进程完成时间
? ? int size;
? ? int prior; //进程优先级
};

//使用链队进行存储

（2）//就绪队列
typedef struct Tnode *T; // struct Tnode的别名为*T
struct Tnode
{
? ? int data; //?什么数据/存储当前创建的进程数
? ? T next; ? //指向就绪队列的下一位置
};

（3）//消息缓冲队列
struct Linkqueue
{
? ? T front, rear; //头指针和尾指针分别指向就绪队列的头部和尾部
};
?

?

---主要函数如下：

（1）InitQueue()：初始化就绪队列,主要将指向就绪队列的头指针和尾指针初始化，方便后面进程的创建。

（2）EnterQueue() ——将PCB插入到链队L中。

（3）create_PCB()——创建进程，首先申请一个空的PCB，然后为该进程分配空间资源，然后初始化PCB，填入进程参数，最后通过调用EnterQueue（）函数将该PCB插入到就绪链队L中。若内存不够则申请失败。

（4）sort_FCFS() ——采用先来先服务算法对就绪队列进行排序，遍历pcb，如果当前进程比后一个进程的到达时间长，就交换。

（5）Finish_Time()——计算经过sort_FCFS排序后的每个PCB进程的完成时间。

（6）kill_PCB( )——终止进程，将指定的就绪进程移出就绪队列中，并清除PCB中的信息。

（7）display_PCB() —— 显示已经在就绪队列中的进程。

四、源代码

详细源代码如下：

#include <stdio.h>
#include <stdlib.h>
// #define MAX_size 200 //表示最大内存
#define MAX_num 20 //单次最大进程数

//控制块PCB的信息
struct PCB
{
    char name[10];
    int id;
    int atime; //进程到达时间
    int stime; //服务时间，运行时间
    int ftime; //进程完成时间
    int size;
    int prior; //进程优先级
};

//使用链队进行存储

//就绪队列
typedef struct Tnode *T; // struct Tnode的别名为*T
struct Tnode
{
    int data; //?什么数据/存储当前创建的进程数
    T next;   //指向就绪队列的下一位置
};

//消息缓冲队列
struct Linkqueue
{
    T front, rear; //头指针和尾指针分别指向就绪队列的头部和尾部
};

//定义全局变量
Linkqueue L;      //消息缓冲队列结构体
PCB pcb[MAX_num]; //结构体PCB数组，MAX_num最大进程数
int numpcb = 0;   /当前已经创建的进程数目
int ram_size;     //内存大小

//就绪队列的初始化
void InitQueue()
{
    L.rear = L.front = (T)malloc(sizeof(T));
    if (!L.front)
        exit(-2);
    L.front->next = NULL;
}

//判断链队是否为空
bool EmptyQueue()
{
    if (L.front == L.rear)
        return true;
    else
        return false;
}

//（2）将PCB插入就绪队列中
void EnterQueue(Linkqueue &L, int x)
{
    T s = (T)malloc(sizeof(T)); //创建一个新结点s
    s->data = x;                //传入新结点s的数据域x值，此时x的值就是结构体数组的下标
    s->next = NULL;             //设置新结点s的指针域为空
    L.rear->next = s;           //将新结点s插入至当前链队末尾
    L.rear = s;                 //队尾指针指向新结点s
}

//（3）先来先服务，即 先到达，先服务 进行排序
void sort_FCFS(PCB *q, int num)
{
    for (int i = 0; i < num - 1; i++)
    {
        struct PCB temp;                  //临时变量，用于交换的中间量
        for (int j = i + 1; j < num; j++) //按先到达的排序
        {
            if (q[i].atime > q[j].atime)
            //如果前面的PCB比后面的更晚到达，就往后移
            {
                temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }
    }
}

//（3）优先数调度算法排序(1为优先级最高)
void sort_Priority(PCB *q, int num)
{
    for (int i = 0; i < num - 1; i++)
    {
        struct PCB temp;                  //临时变量，用于交换的中间量
        for (int j = i + 1; j < num; j++) //按先到达的排序
        {
            if (q[i].prior > q[j].prior)
            //如果前面的PCB比后面的更晚到达，就往后移
            {
                temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
            if (q[i].prior == q[j].prior)
            {
                if (q[i].atime > q[j].atime)
                {
                    temp = q[i];
                    q[i] = q[j];
                    q[j] = temp;
                }
            }
        }
    }
}

//（4）计算PCB的完成时间
void finish_Time(PCB *pcb, int numpcb)
{
    //先使用先来先服务进行排序
    // sort_FCFS(pcb, numpcb);
    //优先级调度算法
    sort_Priority(pcb, numpcb);

    for (int i = 0; i <= numpcb; i++)
    {
        //计算第一个进程的完成时间:达到时间+服务时间
        if (i == 0)

            pcb[0].ftime = pcb[0].atime + pcb[0].stime;
        else
        {
            if (pcb[i].atime > pcb[i - 1].ftime) //当前的到达时间比上一个的完成时间大的话，直接
                pcb[i].ftime = pcb[i].atime + pcb[i].stime;
            else
            {
                pcb[i].ftime = pcb[i - 1].ftime + pcb[i].stime;
                // printf("%d", pcb[i].ftime);
            }
        }
        // ram_size=ram_size+pcb[i].size;
    }
}

//（1）创建进程：申请PCB
void create_PCB()
{
    int num; //要创建的进程数目
    printf("\n--请输入要创建的进程数目：");
    scanf("%d", &num);

    while (num > MAX_num)
    {
        printf("*提示：进程数太大了，请重新输入！");
        scanf("%d", &num);
    };
    // 1、输入数据
    for (int i = 0; i < num; i++)
    {
        printf("*请输入进程id：");
        scanf("%d", &pcb[numpcb].id);
        printf("*请输入进程名：");
        scanf("%s", &pcb[numpcb].name);
        printf("请输入进程的优先级：");
        scanf("%d", &pcb[numpcb].prior);
        printf("*请输入进程到达时间：");
        scanf("%d", &pcb[numpcb].atime);
        printf("*请输入进程服务时间：");
        scanf("%d", &pcb[numpcb].stime);
        printf("*请输入进程大小：");
        scanf("%d", &pcb[numpcb].size);

        //判断一下内存还够不够
        if (pcb[numpcb].size > ram_size)
        {
            printf("*提示：内存不足，创建失败！\n");
            //结束创建
            break;
        }
        else
        {
            //将PCB插入到就绪队列中
            EnterQueue(L, numpcb);
            //提示用户
            printf("-----%d\n", pcb[numpcb].size);
            ram_size = ram_size - pcb[numpcb].size; //创建成功后，为该进程分配了空间，计算剩下的内存空间
            printf("剩下内存%d\n", ram_size);
            printf("*提示：恭喜%s进程创建成功！\n", pcb[numpcb].name);
            numpcb++; //创建成功后，进程数加一
            printf("_____________________________");
        }
        printf("\n");
    }
    printf("\n---共成功创建了%d个进程", numpcb);
    printf("\n---还剩下%d的内存空间！", ram_size);
}

//（6）终止进程，删除进程
void kill_PCB()
{
    int id;
    T p;
    p = L.front; //指向链队的第一个结点
    if (L.front == L.rear)
        printf("*提示：当前无进程！\n\n");
    else
    {
        printf("请输入要终止的进程id：");
        scanf("%d", &id);

        while (pcb[p->next->data].id != id)
        {
            if (p->next == NULL) //到最后没有找到改进程
                printf("*提示：进程不存在！\n\n");
            p = p->next; //往后移动
        }
        //找到了id
        if (pcb[p->next->data].id == id)
        {
            //归还内存
            ram_size = ram_size + pcb[p->next->data].size;
            numpcb--;                //总的进程数-1
            p->next = p->next->next; //删除该结点p->next
            /*当L.front->next==NULL时，说明当前杀死的进程是系统中最后一个进程，此时首位指针指向同一个位置*/
            if (L.front->next == NULL)
                L.front = L.rear;
            /*当p->next==NULL时，说明当前杀死的进程是队尾进程，此时尾指针指向p*/
            if (p->next == NULL)
                L.rear = p;
            while (p->next != NULL)
            {
                p->next->data--;
                pcb[p->next->data] = pcb[p->next->data + 1];
                p = p->next;
            }
        }

        printf("*提示：成功杀死进程！\n");
        printf("--当前内存剩余：%d！\n", ram_size);
        printf("--当前进程数为：%d\n", numpcb);
    }
}

void print(PCB *pcb, int numpcb)
{
    sort_FCFS(pcb, numpcb);
    for (int i = 0; i < numpcb; i++)
    {
        printf("-----第%d个：\n", i + 1);
        printf("进程ID:%d\n 进程名: %s\n 到达时间: %d\n 服务时间: %d\n 完成时间:%d\n", pcb[i].id, pcb[i].name, pcb[i].atime, pcb[i].stime, pcb[i].ftime);
    }
}

//（5）显示已经就绪的进程
void display_PCB()
{
    printf("\n当前numpcb：%d\n", numpcb);
    sort_FCFS(pcb, numpcb);
    // print(pcb, numpcb);
    // printf("计算时间\n");
    finish_Time(pcb, numpcb); //计算完成时间

    if (L.front == L.rear)
        printf("*提示：当前无进程！");
    else
    {
        T p;
        p = L.front->next;
        printf("-----就绪进程如下：------\n");
        printf("进程ID  进程名  优先级  到达时间 服务时间 完成时间 内存大小\n");
        while (p != NULL)
        {
            printf("%5d\t", pcb[p->data].id);
            printf("%4s\t", pcb[p->data].name);
            printf("%4d\t", pcb[p->data].prior);
            printf("%5d\t", pcb[p->data].atime);
            printf("%5d\t", pcb[p->data].stime);
            printf("%5d\t", pcb[p->data].ftime);
            printf("%5d\t", pcb[p->data].size);
            p = p->next;
            printf("\n");
        }
    }
}

//菜单
void menu()
{
    int n;
    while (1)
    {
        printf("\n*************进程演示系统*************\n");
        printf("             1.创建进程\n");
        printf("             2.查看进程\n");
        printf("             3.杀死进程\n");
        printf("             4.退出程序\n");
        printf("***************************************\n\n");
        printf("请输入你的选择（1-4）：");

        scanf("%d", &n);
        switch (n)
        {
        case 1:
            create_PCB();
            break;
        case 2:
            display_PCB();
            break;
        case 3:
            kill_PCB();
            break;
        case 4:
            //退出
            break;
        default:
            printf("没有这个选项！");
            break;
        }
    }
}

int main()
{
    printf("\n请输入可用的内存大小：");
    scanf("%d", &ram_size);
    InitQueue(); //初始化就绪队列
    menu();
    return 0;
}

?

五、运行效果图

（1）界面初始图

?

（2）创建进程：

?

（3）显示已经在就绪队列中的进程（按照先来先服务进行排序输出）：

?

（4）终止某进程

?

六、结果分析

????????此次实验采用c语言模拟进程的创建与撤销，一方面，回忆和复习了原先学习过的链队的创建、插入、遍历等知识点，另一方面，通过写代码更加清楚的理解了PCB进程的创建的基本过程：（1）申请空白PCB；（2）为新进程分配资源；（3）初始化PCB；（4）将新进程插入到就绪队列中。

????????本次实验还采用了先来先服务算法对PCB进程排序之后，再计算出每个PCB进程的完成时间，加深了对先来先服务进程的理解。