devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

操作系统：先来先服务算法和最高优先数优先的C语言实现_高优先权算法代码c语言

作者：知新_RL | 2024-04-21 00:29:09

赞

踩

高优先权算法代码c语言
最近在复习操作系统，有如下知识点：

1）进程调度算法：采用os的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。
2）每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
3）进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。
4）每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
5）就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。
6）每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。
7）重复以上过程，直到所要进程都完成为止。

根据这些知识点，课程设计报告中有如下需求给出：

1）充分了解各项设计要求。深入理解有关进程控制块、进程队列的概念，并体会和了解最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法的具体实施办法。
2）、按要求对进程调度程序进行分解，根据功能将其分解成多个子模块。
3）、建立主控模块程序流程图及各功能子模块程序流程图，要求条理清楚、简单明了、功能完备。
4）、根据流程图编制主程序代码及子程序代码。要求程序设计结构清晰，简洁，便于修改和调试。
5）、上述设计要求一人单独进行，独立完成设计。
6）、设计完成后，上机进行运行调试。
7）、程序运行成功，然后进行某些功能测试，选择有实用性、特殊性的数据进行录入调试，使设计进一步得到改进并完善。
8）、打印出程序运行结果，并对结果进行分析，验证程序设计的正确性。

针对上述问题进程程序设计和编码
基本知识点如下：

静态优先级，也可以称做静态优先权，静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，0～7 或 0～255 中的某一整数，又把该整数称为优先数，只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。
毫无疑问，最简单的 CPU 调度算法是先来先服务（FCFS）调度箅法。釆用这种方案，先请求 CPU 的进程首先分配到 CPU。

程序流程图如下：

在这里插入图片描述

代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define W 1             //Wait
#define R 2             //Run
#define F 0             //Finsh
#define RAND_FLAG_OPEN  0
#define FALSE 0
#define TRUE 1

struct PCB{
    char* p_name;               //进程名称
    unsigned int priority;      //优先级
    long arrive_time;           //到达时间
    long need_time;             //需要运行时间
    long use_time;              //已经使用的CPU时间
    unsigned int status;        //进程状态

};

struct PCB_SPACE{
    struct PCB data;
    struct PCB_SPACE* next;
};

//链式存储的进程空间初始化
struct PCB_SPACE* head;
struct PCB_SPACE* rear;
struct PCB_SPACE* init_process_space(struct PCB_SPACE* head){
    head = (struct PCB_SPACE*)malloc(sizeof(struct PCB_SPACE));
    rear = (struct PCB_SPACE*)malloc(sizeof(struct PCB_SPACE));
    rear = head;
    return head;
}

//获取当前系统的时间戳
int get_now_time(){
    time_t t;
	t = time(NULL);
	return time(&t);
}

struct PCB init_pcb(char* p_name,long need_time,long use_time,unsigned int status,unsigned int priority){
    struct PCB p;
    p.arrive_time = get_now_time();
    p.p_name = p_name;
    p.need_time = need_time%10 + 1;
    p.use_time = use_time;
    p.status = status;
    if(priority == 0){
        p.priority = rand()%256;
    }else{
        int number = 0;
        printf("请设置进程名为%s的优先级数[0-255]:",p_name);
        scanf("%d",&number);
        p.priority = number%256;
    }
    return p;
}

struct PCB_SPACE* temp;
struct PCB_SPACE* insert_pcb_space(struct PCB p){
    temp = (struct PCB_SPACE*)malloc(sizeof(struct PCB_SPACE));
    temp->data = p;
    temp->next = NULL;
    if(head->next == NULL){
        head->next = temp;
    }else{
        rear->next = temp;
    }
    rear = temp;
    return head;
}

char* itoa(int number){
    char* temp = (char*)malloc(sizeof(char)*256);
    strcpy(temp,"process_");
    char* buffer = (char*)malloc(sizeof(char)*256);
    sprintf(buffer,"%d",number);
    strcat(temp,buffer);
    return temp;
}

void disp(struct PCB_SPACE* head,int len){
    struct PCB_SPACE* p = head->next;
    for(int i =0;i<len;i++){
        printf("\r\n");
        printf("进程名:%s\r\n",p->data.p_name);
        printf("进程优先级:%u\r\n",(p->data).priority);
        printf("进程到达时间戳:%ld\r\n",(p->data).arrive_time);
        printf("进程需要运行的时间:%ld\r\n",(p->data).need_time);
        printf("进程已运行时间:%ld\r\n",(p->data).use_time);
        printf("\r\n");
        p = p->next;
    }
}

//先来先服务算法
void FCFS(struct PCB_SPACE* head,int len){
    int continue_flag = FALSE;
    struct PCB_SPACE* p = head->next;
    int ad_count = 0;
    while(TRUE){
        if(p->data.use_time != p->data.need_time && p->data.status == W){
            printf("[+]先来先服务算法调度%s,运行1秒,剩余运行时间为:%ld秒\r\n",p->data.p_name,p->data.need_time - p->data.use_time);
            p->data.status = R;
            continue_flag = TRUE;
            p->data.use_time = p->data.use_time + 1;
            p->data.status = W;
        }else{
            if(p->data.status != F){
                printf("[+]进程%s已完成\r\n",p->data.p_name);
            }
            p->data.status = F;
        }
        p = p->next;
        ad_count = ad_count + 1;
        if(ad_count%len == 0){
            if(continue_flag == FALSE){
                printf("[+]所有进程全部完成!");
                break;
            }else{
                continue_flag = FALSE;
            }
            printf("\r\n");
        }
    }
}


int main(){
    int process_number = 0;
    printf("=============================\r\n");
    printf("开始创建进程块PCB:\r\n");
    printf("请输入需要创建的进程的数量:");
    scanf("%d",&process_number);
    head = init_process_space(head);

    struct PCB p;
    for(int i = 0;i<process_number;i++){
        char* pcb_name = itoa((i+1));
        long need_time = rand();             //尽量控制时间在10秒内，缩短实验时间
        long use_time = 0;
        unsigned int status = W;
        unsigned int priority = RAND_FLAG_OPEN;
        p = init_pcb(pcb_name,need_time,use_time,status,priority);
        insert_pcb_space(p);
        printf("%s\r\n",p.p_name);
    }
    rear->next = head->next;          //形成循环队列,而且head.data为空,所以指向head->next
    printf("=============================\r\n");
    disp(head,process_number);
    FCFS(head,process_number);                           //先来先服务算法

    return 0;
}

  • 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

FCFS 策略可以通过单向循环链表这种数据结构来实现，而调度算法在逻辑上类似于一个循环队列。当一个进程进入就绪队列时，它的PCB会被链接到队列尾部。当CPU空闲时，它会分配给位于队列头部的进程，然后指针指向队列中的下一个元素。FCFS 调度代码编写简单并且理解容易。
当然我们不能直接认为这就是一种队列数据结构，在具体，逻辑上是循环的单向链表，只是调度算法参考了队列的特性。

而根据上述代码，我们对FCFS进行修改，仍然是循环队列，我们在对队列中的元素进行排序，根据优先级排序后运行FCFS，那么得到的结果就是根据优先级优先调度的优先数最高算法。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define W 1             //Wait
#define R 2             //Run
#define F 0             //Finsh
#define RAND_FLAG_OPEN  0
#define FALSE 0
#define TRUE 1

struct PCB{
    char* p_name;               //进程名称
    unsigned int priority;      //优先级
    long arrive_time;           //到达时间
    long need_time;             //需要运行时间
    long use_time;              //已经使用的CPU时间
    unsigned int status;        //进程状态

};

struct PCB_SPACE{
    struct PCB data;
    struct PCB_SPACE* next;
};

//链式存储的进程空间初始化
struct PCB_SPACE* head;
struct PCB_SPACE* rear;
struct PCB_SPACE* init_process_space(struct PCB_SPACE* head){
    head = (struct PCB_SPACE*)malloc(sizeof(struct PCB_SPACE));
    rear = (struct PCB_SPACE*)malloc(sizeof(struct PCB_SPACE));
    rear = head;
    return head;
}

//获取当前系统的时间戳
int get_now_time(){
    time_t t;
	t = time(NULL);
	return time(&t);
}

struct PCB init_pcb(char* p_name,long need_time,long use_time,unsigned int status,unsigned int priority){
    struct PCB p;
    p.arrive_time = get_now_time();
    p.p_name = p_name;
    p.need_time = need_time%10 + 1;
    p.use_time = use_time;
    p.status = status;
    if(priority == 0){
        p.priority = rand()%256;
    }else{
        int number = 0;
        printf("请设置进程名为%s的优先级数[0-255]:",p_name);
        scanf("%d",&number);
        p.priority = number%256;
    }
    return p;
}

struct PCB_SPACE* temp;
struct PCB_SPACE* insert_pcb_space(struct PCB p){
    temp = (struct PCB_SPACE*)malloc(sizeof(struct PCB_SPACE));
    temp->data = p;
    temp->next = NULL;
    if(head->next == NULL){
        head->next = temp;
    }else{
        rear->next = temp;
    }
    rear = temp;
    return head;
}

char* itoa(int number){
    char* temp = (char*)malloc(sizeof(char)*256);
    strcpy(temp,"process_");
    char* buffer = (char*)malloc(sizeof(char)*256);
    sprintf(buffer,"%d",number);
    strcat(temp,buffer);
    return temp;
}

void disp(struct PCB_SPACE* head,int len){
    struct PCB_SPACE* p = head->next;
    for(int i =0;i<len;i++){
        printf("\r\n");
        printf("进程名:%s\r\n",p->data.p_name);
        printf("进程优先级:%u\r\n",(p->data).priority);
        printf("进程到达时间戳:%ld\r\n",(p->data).arrive_time);
        printf("进程需要运行的时间:%ld\r\n",(p->data).need_time);
        printf("进程已运行时间:%ld\r\n",(p->data).use_time);
        printf("\r\n");
        p = p->next;
    }
}

//先来先服务算法
void FCFS(struct PCB_SPACE* head,int len){
    int continue_flag = FALSE;
    struct PCB_SPACE* p = head->next;
    int ad_count = 0;
    while(TRUE){
        if(p->data.use_time != p->data.need_time && p->data.status == W){
            printf("[+]先来先服务算法调度%s,运行1秒,剩余运行时间为:%ld秒\r\n",p->data.p_name,p->data.need_time - p->data.use_time);
            //disp(head,len);
            p->data.status = R;
            continue_flag = TRUE;
            p->data.use_time = p->data.use_time + 1;
            p->data.status = W;
        }else{
            if(p->data.status != F){
                printf("[+]进程%s已完成\r\n",p->data.p_name);
            }
            p->data.status = F;
        }
        p = p->next;
        ad_count = ad_count + 1;
        if(ad_count%len == 0){
            if(continue_flag == FALSE){
                printf("[+]所有进程全部完成!");
                break;
            }else{
                continue_flag = FALSE;
            }
            printf("\r\n");
        }
    }
}



//因为需要判断优先数，对优先级进行排序
void sort(struct PCB_SPACE* head,int len){
    struct PCB_SPACE* p = head->next;
    for(int i =0;i<len-1;i++){
        for(int j =0;j<len-1;j++){
            struct PCB_SPACE* node1 = p;
            struct PCB_SPACE* node2 = p->next;
            if(node1->data.priority > node2->data.priority){        //优先数越小，优先级越高
                struct PCB temp = node1->data;
                node1->data = node2->data;
                node2->data = temp;
            }
        }
    }
}

void OS_Server(struct PCB_SPACE* head,int len){
    sort(head,len);

    int continue_flag = FALSE;
    struct PCB_SPACE* p = head->next;
    int ad_count = 0;
    while(TRUE){
        if(p->data.use_time != p->data.need_time && p->data.status == W){
            printf("[+]最高优先级服务算法调度%s,运行1秒,剩余运行时间为:%ld秒\r\n",p->data.p_name,p->data.need_time - p->data.use_time);
            //disp(head,len);
            p->data.status = R;
            continue_flag = TRUE;
            p->data.use_time = p->data.use_time + 1;
            p->data.status = W;
        }else{
            if(p->data.status != F){
                printf("[+]进程%s已完成\r\n",p->data.p_name);
            }
            p->data.status = F;
        }
        p = p->next;
        ad_count = ad_count + 1;
        if(ad_count%len == 0){
            if(continue_flag == FALSE){
                printf("[+]所有进程全部完成!");
                break;
            }else{
                continue_flag = FALSE;
            }
            printf("\r\n");
        }
    }
}


int main(){
    int process_number = 0;
    printf("=============================\r\n");
    printf("开始创建进程块PCB:\r\n");
    printf("请输入需要创建的进程的数量:");
    scanf("%d",&process_number);
    head = init_process_space(head);

    struct PCB p;
    for(int i = 0;i<process_number;i++){
        char* pcb_name = itoa((i+1));
        long need_time = rand();             //尽量控制时间在10秒内，缩短实验时间
        long use_time = 0;
        unsigned int status = W;
        unsigned int priority = RAND_FLAG_OPEN;
        p = init_pcb(pcb_name,need_time,use_time,status,priority);
        insert_pcb_space(p);
        printf("%s\r\n",p.p_name);
    }
    rear->next = head->next;          //形成循环队列,而且head.data为空,所以指向head->next
    printf("=============================\r\n");
    disp(head,process_number);
    //FCFS(head,process_number);                           //先来先服务算法
    OS_Server(head,process_number);

    return 0;
}

  • 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
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/460161
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号