操作系统实验1：时间片轮转和存储管理动态分区分配及回收

#include<stdio.h>
#include<stdlib.h>
#include<stdlib.h>
#include <iostream>
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1    //完成
#define ERROR 0 //出错
#define MAX_length 32767 //最大内存空间为32767KB
using namespace std;
typedef struct PCB {
    int PID;//进程标识符
    char state;//状态
    int CPUTIME;//总共占用的时间片数
    int runTime;//运行需要的时间时间片数
    int NeedTime;//还需要的时间片数
    int proitity;//优先数
    struct PCB* next;//指向下一个的地址的指针
}*process, ptr;

PCB* ready = NULL, * p;
int num;

void PCBsort() {
    PCB* first, * second;
    int flag = 0;
    if ((ready == NULL) || ((p->proitity) >(ready->proitity))) {
        //如果当前优先级大于就绪优先级，将当前节点前移
        p->next = ready;
        ready = p;
    }
    else {
        first = ready;
        second = first->next;
        while (second != NULL) {
            if ((p->proitity) > (second->proitity)) {
                p->next = second;
                first->next = p;
                second = NULL;
                flag = 1;
            }
            else {
                first = first->next;
                second = second->next;
            }
        }
        if (flag == 0)first->next = p;
    }
}

void inputProcess()
{
    int i;
    printf("输入%d个进程的信息（PID、NeedTime）
", num);
    for (i = 0; i < num; i++) {
        p = (PCB*)malloc(sizeof(PCB));
        scanf_s("%d %d", &p->PID, &p->NeedTime);
        p->runTime = 0;//运行时间默认值为2
        p->state = 'w';
        p->CPUTIME = 0;//初始值为0；
        p->proitity = 50;//优先级默认值为50
        p->next = NULL;
        PCBsort();
    }
}

int space()
{
    int k = 0;
    PCB* pr = ready;
    while (pr != NULL) {
        k++;
        pr = pr->next;
    }
    return k;
}

void showInfo(ptr* pr) {
    printf("
PID	状态	总共占用时间片数	运行时间	剩余时间	优先级
");
    printf("————————————————————————————
");
    printf(" %d	", pr->PID);
    printf(" %c		", pr->state);
    printf("%d		", pr->CPUTIME);
    printf("%d		", pr->runTime);
    printf("%d		",pr->NeedTime);
    printf("%d	", pr->proitity);
    printf("
");
}

void priorityRun()
{
    int len, h = 0;
    char ch;
    inputProcess();
    len = space();
    while ((len != 0) && (ready != NULL))
    {
        ch = getchar();
        h++;
        printf("
 运行次数:%d 
", h);
        p = ready;
        ready = p->next;
        p->next = NULL;
        p->state = 'R';
        p->CPUTIME = p->CPUTIME + 2;//占用时间片数+2；
        p->NeedTime = p->NeedTime - 2;//还需时间片数-2；
        p->proitity = p->proitity - 1;//优先级数-1；
        p->runTime = 2;
        PCB* pr;
        showInfo(p);
        pr = ready;
        while (pr != NULL) {
            showInfo(pr);
            pr = pr->next;
        }
        if (p->NeedTime<=0) {
            p->NeedTime = 0;
            printf("
 进程%d 已结束。
", p->PID);
            free(p);
        }
        else {
            p->state = 'w';
            p->runTime = 0;
            PCBsort();
        }
        printf("
 按任一键继续 ......");
    }
    printf("

 进程已经完成 .
");
    ch = getchar();
}


void choice1()
{
    printf("—————————————————优先级调度算法—————————————————
");
    printf("输入进程数目：");
    scanf_s("%d", &num);
    priorityRun();
}



typedef int Status;
int n = 0;
typedef struct freearea//定义一个空闲区说明表结构
{
    int ID;   //分区号
    long size;   //分区大小
    long address; //分区地址
    int state;   //状态
}ElemType;

//---------- 线性表的双向链表存储结构 ------------
typedef struct DuLNode //double linked list
{
    ElemType data;
    struct DuLNode* prior; //前趋指针
    struct DuLNode* next; //后继指针
}DuLNode, * DuLinkList;

DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点

Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int, int);//首次适应算法
Status Best_fit(int, int); //最佳适应算法
void show();//查看分配
Status Initblock();//开创空间表

Status Initblock()//开创带头结点的内存空间链表
{
    block_first = (DuLinkList)malloc(sizeof(DuLNode));
    block_last = (DuLinkList)malloc(sizeof(DuLNode));
    block_first->prior = NULL;
    block_first->next = block_last;
    block_last->prior = block_first;
    block_last->next = NULL;
    block_last->data.address = 0;
    block_last->data.size = MAX_length;
    block_last->data.ID = 0;
    block_last->data.state = Free;

    return OK;
}

//----------------------- 分 配 主 存 -------------------------
Status alloc(int ch)
{
    int ID, request;
    cout << "请输入作业(分区号)：";
    cout<<endl;
    cin >> ID;
    cout << "请输入需要分配的主存大小(单位:KB)："<<endl;
    cin >> request;
    if (request < 0 || request == 0)
    {
        cout << "分配大小不合适，请重试!" << endl;
        return ERROR;
    }

    if (ch == 2) //选择最佳适应算法
    {
        if (Best_fit(ID, request) == OK) cout << "分配成功!" << endl;
        else cout << "内存不足，分配失败!" << endl;
        return OK;
    }
    else //默认首次适应算法
    {
        if (First_fit(ID, request) == OK) cout << "分配成功!" << endl;
        else cout << "内存不足，分配失败!" << endl;
        return OK;
    }
}
//------------------ 首次适应算法 -----------------------
Status First_fit(int ID, int request)//传入作业名及申请量
{
    //为申请作业开辟新空间且初始化
    DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));
    temp->data.ID = ID;
    temp->data.size = request;
    temp->data.state = Busy;

    DuLNode* p = block_first->next;
    while (p)
    {
        if (p->data.state == Free && p->data.size == request)
        {//有大小恰好合适的空闲块
            p->data.state = Busy;
            p->data.ID = ID;
            return OK;
            break;
        }
        if (p->data.state == Free && p->data.size > request)
        {//有空闲块能满足需求且有剩余"
            temp->prior = p->prior;
            temp->next = p;
            temp->data.address = p->data.address;
            p->prior->next = temp;
            p->prior = temp;
            p->data.address = temp->data.address + temp->data.size;
            p->data.size -= request;
            return OK;
            break;
        }
        p = p->next;
    }
    return ERROR;
}

//-------------------- 最佳适应算法 ------------------------

Status Best_fit(int ID, int request)

{

    int ch; //记录最小剩余空间

    DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));

    temp->data.ID = ID;

    temp->data.size = request;

    temp->data.state = Busy;

    DuLNode* p = block_first->next;

    DuLNode* q = NULL; //记录最佳插入位置

    while (p) //初始化最小空间和最佳位置

    {

        if (p->data.state == Free &&

            (p->data.size > request || p->data.size == request))

        {

            q = p;

            ch = p->data.size - request;

            break;

        }

        p = p->next;

    }

    while (p)

    {

        if (p->data.state == Free && p->data.size == request)

        {//空闲块大小恰好合适

            p->data.ID = ID;

            p->data.state = Busy;

            return OK;

            break;

        }

        if (p->data.state == Free && p->data.size > request)

        {//空闲块大于分配需求

            if (p->data.size - request < ch)//剩余空间比初值还小

            {

                ch = p->data.size - request;//更新剩余最小值

                q = p;//更新最佳位置指向

            }

        }

        p = p->next;

    }

    if (q == NULL) return ERROR;//没有找到空闲块

    else

    {//找到了最佳位置并实现分配

        temp->prior = q->prior;

        temp->next = q;

        temp->data.address = q->data.address;

        q->prior->next = temp;

        q->prior = temp;

        q->data.address += request;

        q->data.size = ch;

        return OK;

    }

}

//-----------------------   主 存 回 收   --------------------

Status free(int ID)

{

    DuLNode* p = block_first;

    while (p)

    {

        if (p->data.ID == ID)

        {

            p->data.state = Free;

            p->data.ID = Free;

            if (p->prior->data.state == Free)//与前面的空闲块相连

            {

                p->prior->data.size += p->data.size;

                p->prior->next = p->next;

                p->next->prior = p->prior;
                free(p);
            }

            if (p->next->data.state == Free)//与后面的空闲块相连

            {
                    //空闲块的后继指针并不为0
                    p->next->data.size = p->data.size;
                    p->next->prior = p->prior;
                    p->prior->next = p->next;
                    free(p);
                    //p->next->next->prior = p;

                    //p->next = p->next->next;
            }

            break;

        }

        p = p->next;

    }

    return OK;

}

//--------------- 显示主存分配情况 ------------------

void show()

{
    cout << "***********-----------------************"<<endl;

    cout << "****       主 存 分 配 情 况        ****"<<endl;

    cout << "***********-----------------************"<<endl;

    DuLNode* p = block_first->next;

    while (p)
    {

        cout << "分 区 号：";

        if (p->data.ID == Free) cout << "Free" << endl;

        else cout << p->data.ID << endl;

        cout << "起始地址：" << p->data.address << endl;

        cout << "分区大小：" << p->data.size << " KB" << endl;

        cout << "状    态：";

        if (p->data.state == Free) cout << "空 闲" << endl;

        else cout << "已分配!" << endl;

        cout << "-----------------------" << endl;

        p = p->next;

    }

}

//----------------------- 主 函 数---------------------------

void choice2()

{

    int ch, d = 0;//算法选择标记

    cout << "1.首次适应算法 2.最佳适应算法 0.退出"<<endl;

    cout << "请选择分配算法："<<endl;

    cin >> ch;

    if (ch == 0 || ch == 1 || ch == 2) d++;

    while (d == 0)

    {

        cout << "请选择正确的数字0 ,1 或2" << endl;

        cin >> ch;

        if (ch == 0 || ch == 1 || ch == 2) d++;

    }

    if (ch == 0) exit(0);

    if (n == 0) Initblock(); //开创空间表

    int choice; //操作选择标记

    while (1)

    {

        cout << "********************************************"<<endl;

        cout << "**    1: 分配内存        2: 回收内存      **"<<endl;

        cout << "**    3: 查看分配        0: 返    回      **"<<endl;

        cout << "********************************************"<<endl;

        cout << "请输入您的操作 ："<<endl;

        cin >> choice;

        if (choice == 1)

        {

            alloc(ch); // 分配内存

            n++;

        }

        else if (choice == 2) // 内存回收

        {

            int ID;

            cout << "请输入您要释放的分区号：";

            cin >> ID;

            free(ID);

            n++;

        }

        else if (choice == 3)

        {

            show();//显示主存

            n++;

        }

        else if (choice == 0)

        {

            choice2();
            n++;

        }

        else //输入操作有误

        {

            cout << "输入有误，请重试!" << endl;

            continue;

        }

    }
    
}

void menu() {
    cout << "1.时间片轮转算法" << endl;
    cout << "2.存储管理动态分区分配及回收算法" << endl;
    cout << "请输入您想要选择的算法" << endl;
    int choice;
    cin >> choice;
    switch (choice) {
    case 1:{
        //调用时间片轮转算法
        choice1();
        menu();
        break;
        }
    case 2: {
        //调用存储管理动态分区分配及回收算法
        choice2();
        menu();
        break;
         }
    }
}

int main() {
    menu();
}