加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

操作系统实验：动态优先权的进程调度算法

(2011-11-27 13:23:57)
标签：

操作系统

动态优先权

进程调度算法

校园

 分类： 学校的作业

1.   实验目的：

通过动态优先权算法的模拟加深进程概念和进程调度过程的理解，并学习撰写规范的科学研究报告。

2.   实验要求：

任选C高级程序语言编写源程序，在Linux操作系统下调试通过，测试正确。

3.  实验内容：

    (1)．对N个进程采用动态优先权算法的进程调度；

(2)．每个用来标识进程的进程控制块PCB用结构描述，包括以下字段：进程标识数ID，进程优先数PRIORITY，进程以占用的CPU时间CPUTIME，进程还需占用的CPU时间ALLTIME，进程状态STATE等。

(3)．优先数改变的原则：进程在就绪队列中呆一个时间片，优先数增加1，进程每运行一个时间片优先数减3。

(4)．设置调度前的初始状态。

(5)．将每个时间片内的进程情况显示出来。

4.  实验原理：

    动态优先权算法，进程调度过程等。 


源代码（只进行了小规模的数据测验）：

#include<stdio.h>

#include<stdlib.h>
#define N 6

// 待插入就绪队列的进程数据
int id[N]       = { 0,  1,  2,  3,  4,  5 };
int priority[N] = { 9, 38, 17,  2,  7, 18 };
int cpuTime[N]  = { 0,  0,  0,  0,  0,  0 };
int allTime[N]  = { 3,  2,  3,  6,  1,  3 };

//********************************
//
//  模拟进程/PCB数据结构
//
//********************************

// 枚举进程的状态：就绪、执行、阻塞、完成
enum STATE { Ready, Run, Block, Finish };

// 建立PCB结构体
struct PCB {
    int id;                     // 标志数
    int priority;               // 优先数
    int cpuTime;                // 已占CPU时间
    int allTime;                // 还需占CPU时间
    int blockTime;              // 已被阻塞的时间
    STATE state;                // 进程状态
    PCB *pre;                   // PCB的前指针
    PCB *nxt;                   // PCB的后指针
};

//********************************
//
//  模拟进程队列
//
//********************************

// 进程入列
void queQush(PCB *process, PCB *queHead)
{
    process->pre = NULL;
    process->nxt = queHead->nxt;
    if(queHead->nxt != NULL) {
        // 非第一个入列
        queHead->nxt->pre = process;
    }
    queHead->nxt = process;
}

// 进程出列
void quePop(PCB *process, PCB *queHead)
{
    if(process->pre != NULL) {
        // 不是头节点
        process->pre->nxt = process->nxt;
    } else {
        queHead->nxt = process->nxt;
    }
    if(process->nxt != NULL) {
        // 不是尾节点
        process->nxt->pre = process->pre;
    }
    // 清空进程指针
    process->pre = process->nxt = NULL;
}

// 查看队列里进程的信息
void queWalk(PCB *queHead)
{
    PCB *pro = queHead->nxt;
    if(pro == NULL) {
        printf("(无进程)\n");
        return;
    }
    while(pro != NULL) 
    {
        printf("id:%d,  pri:%d,  alltime:%d\n", pro->id, 
            pro->priority, pro->allTime);
        pro = pro->nxt;
    }
}

//********************************
//
//  模拟就绪队列
//
//********************************

int readyQueNum;                // 就绪队列的进程数量
PCB readyQueHead;               // 就绪队列的头部
PCB *readyMaxProcess;           // 就绪队列中优先级最高的进程

// 进程插入到就绪队列
void readyQueQush(PCB *process)
{
    readyQueNum ++;
    process->state = Ready;
    queQush(process, &readyQueHead);
}

// 优先级最高的进程出列
PCB* readyQuePop()
{
    readyQueNum --;
    quePop(readyMaxProcess, &readyQueHead);
    return readyMaxProcess;
}

// 每个时间片，更新就绪队列里进程的信息
void readyQueUpdate()
{
    int maxPriority = -1;
    PCB *pro = readyQueHead.nxt;
    if(pro == NULL){
        // 就绪队列没有进程
        readyMaxProcess = NULL;
        return;
    }
    while(pro != NULL) 
    {
        pro->priority ++;
        if(pro->priority > maxPriority) {
            maxPriority = pro->priority;
            readyMaxProcess = pro;
        }
        pro = pro->nxt;
    }
}

// 返回就绪队列最高优先级的值
int readyMaxPriority()
{
    return readyMaxProcess->priority;
}

// 查看就绪队列里进程的信息
void readyQueWalk()
{
    printf("就绪队列里的进程信息为：\n");
    queWalk(&readyQueHead);
}

//********************************
//
//  模拟阻塞队列
//
//********************************

#define EndBlockTime 3          // 进程最长被阻塞时间

int blockQueNum;                // 阻塞队列的进程数量
PCB blockQueHead;               // 阻塞队列的头部
PCB *blockMaxProcess;           // 阻塞队列中优先级最高的进程

// 进程插入到阻塞队列
void blockQueQush(PCB *process)
{
    blockQueNum ++;
    process->blockTime = 0;
    process->state = Block;
    queQush(process, &blockQueHead);
}

// 优先级最高的进程出列
PCB* blockQuePop()
{
    blockQueNum --;
    quePop(blockMaxProcess, &blockQueHead);
    return blockMaxProcess;
}

// 每个时间片，更新阻塞队列里进程的信息
void blockQueUpdate()
{
    int maxPriority = -1;
    PCB *pro = blockQueHead.nxt;
    while(pro != NULL) 
    {
        pro->blockTime ++;
        if(pro->blockTime >= EndBlockTime) {
            PCB *process = pro;
            pro = pro->nxt;
            // 阻塞时间到，调入就绪队列
            blockQueNum --;
            quePop(process, &blockQueHead);
            readyQueQush(process);
        } else if(pro->priority > maxPriority) {
            // 更新阻塞队列里优先级最高的进程指针
            maxPriority = pro->priority;
            blockMaxProcess = pro;
            pro = pro->nxt;
        }
    }
}

// 查看阻塞队列里进程的信息
void blockQueWalk()
{
    printf("阻塞队列里的进程信息为：\n");
    queWalk(&blockQueHead);
}

//********************************
//
//  模拟动态优先权的进程调度
//
//********************************

// 初始化数据
void initData()
{
    // 初始化就绪队列和阻塞队列
    readyQueNum = blockQueNum = 0;
    readyMaxProcess = blockMaxProcess = NULL;
    readyQueHead.pre = readyQueHead.nxt = NULL;
    blockQueHead.pre = blockQueHead.nxt = NULL;

    // 初始化进程进入就绪队列
    int i, maxPriority = -1;
    for(i = 0; i < N; i ++) 
    {
        // 分配一个PCB的内存空间
        PCB *pro = (PCB *)malloc(sizeof(PCB));
        // 给当前的PCB赋值
        pro->id        = id[i];
        pro->priority  = priority[i];
        pro->cpuTime   = cpuTime[i];
        pro->allTime   = allTime[i];
        pro->blockTime = 0;
        if(pro->allTime > 0) {
            // 插入到就绪队列中
            readyQueQush(pro);
            // 更新就绪队列优先级最高的进程指针
            if(pro->priority > maxPriority) {
                maxPriority = pro->priority;
                readyMaxProcess = pro;
            }
        }
    }
}

// 模拟cpu执行1个时间片的操作
void cpuWord(PCB *cpuProcess)
{
    cpuProcess->priority -= 3;
    if(cpuProcess->priority < 0) {
        cpuProcess->priority = 0;
    }
    cpuProcess->cpuTime ++;
    cpuProcess->allTime --;
    // 显示正执行进程的信息：
    printf("CPU正执行的进程信息为：\n");
    printf("id:M,  pri:M,  alltime:M\n", cpuProcess->id, 
        cpuProcess->priority, cpuProcess->allTime);
}

int main()
{
    int timeSlice   = 0;         // 模拟时间片
    int cpuBusy     = 0;         // 模拟cpu状态
    PCB *cpuProcess = NULL;      // 当前在cpu执行的进程
    // 初始化数据
    initData(); 
    // 模拟进程调度
    while(1)
    {
        if(readyQueNum == 0 && blockQueNum == 0 && cpuBusy == 0) {
            // 就绪队列、阻塞队列和cpu无进程，退出
            break;
        }
        //printf("\n%d %d", readyQueNum, blockQueNum);
        if(cpuBusy == 0) {
            // cpu空闲，选择一个进程进入cpu
            if(readyQueNum > 0) {
                // 选择绪队列优先级最高的进程
                cpuProcess = readyQuePop();
            } else {
                // 就绪队列没有进程，改为选择阻塞队列优先级最高的进程
                cpuProcess = blockQuePop();
            }
            cpuProcess->cpuTime = 0;
            cpuProcess->state = Run;
            cpuBusy = 1;
        }
        timeSlice ++;
        printf("\n第%d个时间片后：\n", timeSlice);
        // 模拟cpu执行1个时间片的操作
        cpuWord(cpuProcess);
        if(cpuProcess->allTime == 0) {
            cpuProcess->state = Finish;
            // 释放已完成进程的PCB
            free(cpuProcess);
            cpuBusy = 0;
        }
        // 更新就绪队列和阻塞队列里的进程信息
        blockQueUpdate();
        readyQueUpdate();
        // 查看就绪队列和阻塞队列的进程信息
        readyQueWalk();
        blockQueWalk();
        if(cpuBusy == 1 && readyQueNum >0 && 
            cpuProcess->priority < readyMaxPriority()) {
            // 需抢占cpu，当前执行的进程调入阻塞队列
            blockQueQush(cpuProcess);
            cpuProcess = readyQuePop();
        }
    }
    printf("\n模拟进程调度算法结束\n");
    return 0;
}


运行结果：

喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有