进程调度 时间片轮转算法

简介: 进程调度 时间片轮转算法

实验一进程调度


实验性质:设计


建议学时:6学时


实验目的:


通过这次实验,加深对进程概念的理解,进一步掌握进程状态的转变、进程调度的策略及对系统 性能的评价方法。


实验内容;


设计程序模拟进程的轮转法调度过程。假设初始状态为:有n个进程处于就绪状态,有m个进 程处于阻塞状态。釆用轮转法进程调度算法进行调度。调度过程中,假设处于执行状态的进程不会阻 塞,且每过t个时间片系统释放资源,唤醒处于阻塞队列队首的进程。


程序要求如下:


1) 输出系统中进程的调度次序;


2) 计算CPU利用率。


实现提示:


用C语言实现提示:


1) 程序中进程可用PCB表示,其类型描述如下:

struct PCB_type {
char name ; 〃进程名
int state ; //进程状态
2 表示“执行"状态
1——表示“就绪”状态
0——表示“阻塞”状态
int cpu_time ; 〃运行需要的CPU时间(需运行的时间片个数)
}


2) 设置两个队列,将处于“就绪”状态的进程PCB挂在队列ready中;将处于“阻塞”状态的 进程PCB挂在队列blocked中。队列类型描述如下:

struct QueueNode{
struct PCB_type PCB;
Struct QueueNode *next;
}


并设全程量:

struct QueueNode ready_head=NULL, //ready队列队首指针
*ready_tail=NULL,    //ready队列队尾指针
*blocked_head=NULL,  //blocked队列队首指针
*blocked_tail=NULL;  //blocked队列队尾指针


3)设计子程序

start_stateO; 〃读入假设的数据,设置系统初始状态
dispathO; 〃模拟调度
calculate。; //计算 CPU 利用率


实验要求:


1) 上机前仔细编好程序;


2) 上机时独立调试程序;


3) 提交实验报告,包括纸质稿和电子稿两部分。实验报告要求详见实验报告模板。


测试用数据:


n=2 (处于就绪状态的进程的个数)


m=3 (处于阻塞状态的进程的个数)


t=5 (每过t个时间片系统释放资源,唤醒处于阻塞队列队首的进程)




测试用例:



代码展示

#include <iostream>
#include <fstream>
using namespace std;
struct PCB_type
{
    char name;
    /* 0:阻塞 1:就绪 2:执行 */
    int state;
    /* 需要的CPU时间,即运行的时间片个数 */
    double cpu_time;
};
struct QueueNode
{
    PCB_type PCB;
    QueueNode *next;
};
QueueNode *ready_head = NULL,
          *ready_tail = NULL,
          *blocked_head = NULL,
          *blocked_tail = NULL;
int all_time = 0;
int free_time = 0;
double time_slice_len = 1;
// 函数声明
void start_state();
void dispath();
void calculate();
void ready_Enqueue(QueueNode *p);
void blocked_Enqueue(QueueNode *p);
void ready_Dequeue();
void blocked_Dequeue();
QueueNode *ready_Front();
QueueNode *blocked_Front();
int main()
{
    start_state();
    dispath();
    calculate();
    system("pause");
    return 0;
}
void start_state()
{
    ifstream f;
    f.open("OS\\test1.txt");
    int ready_pcb_num, blocked_pcb_num;
    f >> ready_pcb_num;
    f >> blocked_pcb_num;
    // 就绪队列初始化
    for (int i = 0; i < ready_pcb_num; i++)
    {
        QueueNode *p = new QueueNode;
        f >> p->PCB.name >> p->PCB.cpu_time;
        p->PCB.state = 1;
        p->next = NULL;
        ready_Enqueue(p);
    }
    // 阻塞队列初始化
    for (int i = 0; i < blocked_pcb_num; i++)
    {
        QueueNode *p = new QueueNode;
        f >> p->PCB.name >> p->PCB.cpu_time;
        p->PCB.state = 0;
        p->next = NULL;
        blocked_Enqueue(p);
    }
    cout << "The processes in the ready queue are:" << endl;
    if (ready_head == NULL)
    {
        cout << "The ready queue is empty";
    }
    else
    {
        QueueNode *p = ready_head;
        while (p)
        {
            cout << p->PCB.name << " " << p->PCB.state << " " << p->PCB.cpu_time << endl;
            p = p->next;
        }
    }
    // 输入t
    int t;
    f >> t;
}
void dispath()
{
    cout << "Start scheduling" << endl;
    while (ready_head != NULL || blocked_head != NULL)
    {
        if (ready_head != NULL)
        {
            QueueNode *tmp = ready_Front();
            ready_Dequeue();
            tmp->PCB.state = 2;
            tmp->PCB.cpu_time -= time_slice_len;
            all_time++;
            printf("Time slice %d: process %c scheduling\n", all_time, tmp->PCB.name);
            if (tmp->PCB.cpu_time < time_slice_len)
            {
                printf("process %c over!\n", tmp->PCB.name);
            }
            else
            {
                ready_Enqueue(tmp);
            }
        }
        else
        {
            all_time++;
            free_time++;
            printf("Time slice %d: Free a slice of time\n", all_time);
        }
        if (blocked_head != NULL && all_time % 5 == 0)
        {
            QueueNode *tmp = blocked_Front();
            blocked_Dequeue();
            ready_Enqueue(tmp);
        }
    }
}
void calculate()
{
    cout << "CPU Utilization rate: " << ((all_time - free_time) / (double)all_time) * 100 << "%" << endl;
}
// 队列实现
void ready_Enqueue(QueueNode *p)
{
    if (ready_head == NULL)
    {
        ready_head = ready_tail = p;
    }
    else
    {
        ready_tail->next = p;
        ready_tail = p;
    }
}
void blocked_Enqueue(QueueNode *p)
{
    if (blocked_head == NULL)
    {
        blocked_head = blocked_tail = p;
    }
    else
    {
        blocked_tail->next = p;
        blocked_tail = p;
    }
}
void ready_Dequeue()
{
    QueueNode *temp = ready_head;
    if (ready_head == NULL)
    {
        printf("ready Queue is Empty\n");
        return;
    }
    if (ready_head == ready_tail)
    {
        ready_head = ready_tail = NULL;
    }
    else
    {
        ready_head = ready_head->next;
    }
}
void blocked_Dequeue()
{
    QueueNode *temp = blocked_head;
    if (blocked_head == NULL)
    {
        printf("blocked Queue is Empty\n");
        return;
    }
    if (blocked_head == blocked_tail)
    {
        blocked_head = blocked_tail = NULL;
    }
    else
    {
        blocked_head = blocked_head->next;
    }
}
QueueNode *ready_Front()
{
    return ready_head;
}
QueueNode *blocked_Front()
{
    return blocked_head;
}
目录
相关文章
|
4天前
|
算法 调度 UED
深入理解操作系统:进程调度与优先级队列
【10月更文挑战第31天】在计算机科学的广阔天地中,操作系统扮演着枢纽的角色,它不仅管理着硬件资源,还为应用程序提供了运行的环境。本文将深入浅出地探讨操作系统的核心概念之一——进程调度,以及如何通过优先级队列来优化资源分配。我们将从基础理论出发,逐步过渡到实际应用,最终以代码示例巩固知识点,旨在为读者揭开操作系统高效管理的神秘面纱。
|
3天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
1天前
|
算法 调度 UED
深入理解操作系统:进程管理与调度策略
【10月更文挑战第34天】本文旨在探讨操作系统中至关重要的一环——进程管理及其调度策略。我们将从基础概念入手,逐步揭示进程的生命周期、状态转换以及调度算法的核心原理。文章将通过浅显易懂的语言和具体实例,引导读者理解操作系统如何高效地管理和调度进程,保证系统资源的合理分配和利用。无论你是初学者还是有一定经验的开发者,这篇文章都能为你提供新的视角和深入的理解。
12 3
|
4天前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###
|
6天前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
30 4
|
7天前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
7天前
|
消息中间件 算法 调度
深入理解操作系统:进程管理与调度策略
【10月更文挑战第29天】本文将带领读者深入探讨操作系统中的核心组件之一——进程,并分析进程管理的重要性。我们将从进程的生命周期入手,逐步揭示进程状态转换、进程调度算法以及优先级调度等关键概念。通过理论讲解与代码演示相结合的方式,本文旨在为读者提供对进程调度机制的全面理解,从而帮助读者更好地掌握操作系统的精髓。
19 1
|
7天前
|
算法 调度 UED
深入理解操作系统中的进程调度
【10月更文挑战第29天】探索进程调度的奥秘,本文将带你深入了解在操作系统中如何管理和控制多个并发执行的程序。从简单的调度算法到复杂的多级反馈队列,我们将逐步揭示如何优化系统性能和提高资源利用率。准备好一起揭开进程调度的神秘面纱吧!
|
12天前
|
算法 大数据 Linux
深入理解操作系统之进程调度算法
【10月更文挑战第24天】本文旨在通过浅显易懂的语言,带领读者深入了解操作系统中的进程调度算法。我们将从进程的基本概念出发,逐步解析进程调度的目的、重要性以及常见的几种调度算法。文章将通过比喻和实例,使复杂的技术内容变得生动有趣,帮助读者建立对操作系统进程调度机制的清晰认识。最后,我们还将探讨这些调度算法在现代操作系统中的应用和发展趋势。
|
4天前
|
算法 Linux 调度
深入理解操作系统之进程调度
【10月更文挑战第31天】在操作系统的心脏跳动中,进程调度扮演着关键角色。本文将深入浅出地探讨进程调度的机制和策略,通过比喻和实例让读者轻松理解这一复杂主题。我们将一起探索不同类型的调度算法,并了解它们如何影响系统性能和用户体验。无论你是初学者还是资深开发者,这篇文章都将为你打开一扇理解操作系统深层工作机制的大门。
11 0
下一篇
无影云桌面