投稿
  1. 首页
  2. CMS教程

优先级调度算法

北京科技大学分数线 • 2023-5-5 • CMS教程 • 阅读 0

优先级调度算法,第1张

优先级调度算法的原理是给每个进程赋予一个优先级，每次需要进程切换时，找一个优先级最高的进程进行调度。这样，如果赋予长进程一个高优先级，则该进程就不会再“饥饿”。事实上，STCF算法本身就是一种优先级调度，只不过它给予短进程高优先级而已。

优先级调度的优点是可以赋予重要的进程以高优先级以确保重要任务能够得到CPU时间。其缺点则与STCF算法一样，低优先级的进程可能会“饥饿”。不过，这个问题在优先级调度算法里比在STCF里好解决：只要动态地调节优先级即可。例如，在一个进程执行特定CPU时间后将其优先级降低一个级别，或者将处于等待进程的优先级提高一个级别。这样，一个进程如果等待时间很长，其优先级将因持续提升而超越其他进程的优先级，从而得到CPU时间。这样，“饥饿”现象就可以防止。

不过，优先级调度还有一个缺点，就是响应时间不能保证，除非将一个进程的优先级设置为最高。即使将优先级设置为最高，但如果每个人都将自己进程的优先级设为最高，则响应时间还是无法保证。

只帮你写点开头，后面你应该会的

#include <stdioh>

#include <stdlibh>

#include <stringh>

#include <iostreamh>

typedef struct node

{

char name[10];

int prio;

int round;

int cputime;

int needtime;

int count;

char state;

struct node next;

}PCB;

PCB finish,ready,tail,run,; //队列指针

int N; //进程数

void zhunbei()

{

run=ready; //就绪队列头指针赋值给运行头指针

run->state='G'; //进程状态变为运行态]

ready=ready->next; //就绪队列头指针后移到下一进程

}

//输出标题函数

void output1(char a)

{

if(toupper(a)=='P') //优先级法

cout<<" "<<endl;

cout<<"进程名 占用CPU时间 已运行时间 还要的时间 轮转时间片 状态"<<endl;

}

下面是一段delphi代码：

算法核心代码，为增强算法通用性，将窗体的一个treeview和ADOQuery引用到局部变量中，作为对象引用，不创建，也不释放，相当于别名

procedure TfrmFmtTree();

var

i,j :integer;

leafList,leafListPlus: TList;

leaf,subNode: TTreeNode;

tv: TTreeView;//引用窗体控件

qry: TADOQuery;//引用窗体控件

begin

//初始化

leafList:=TListCreate;

leafListPlus:=TListCreate;

tv:=tvw1;

tvItemsClear;

qry:=qry1;

subNode:=tvItemsAddChild(nil,'月夜风筝(我)的公司');

leafListAdd(subNode);

//处理

while leafListCount > 0 do

begin

leafListPlusClear;

for i:=0 to leafListCount-1 do

begin

leaf:=leafList[i];

if leafLevel = 0 then

qrySQLText:=Format('select code,name,belong from TB where belong = ''%s''',['--'])

else

qrySQLText:=Format('select code,Name,belong from TB where belong = ''%d''',[leafStateIndex]);

qryOpen;

for j:= 0 to qryRecordCount-1 do

begin

subNode:=tvItemsAddChild(leaf,qryFieldByName('name')AsString);

subNodeImageIndex:=subNodeLevel;

subNodeStateIndex:=StrToInt(qryFieldByName('code')AsString);

leafListPlusAdd(subNode);

qryNext;

end;

end;

leafListAssign(leafListPlus);

end;

//清理

tvFullExpand;

leafListPlusFree;

leafListFree;

end;

说明：

用TList类型模拟实现了广度优先算法的队列－－先进先出－－实际上，本算法不需要那么严格，只要按批先进先出就行了。leafList用于当前循环，leafListPlus用于下一轮循环，其中保存的都是树节点类型，以方便在treeview上直接插入子节点，就省了查找父结点的算法，节点的编号缓存在节点的StateIndex属性中，编号可转为整数型这是最方便的，如果编号不能保证可转为整数，可以使用data属性，可保万无一失

希望对你有帮助~

以人为本。

存在的缺陷是读者管理范围大，辅以人性化的变通管理，着力体现以人为本的管理思想。

写-写互斥，即不能有两个写者同时进行写 *** 作；读-写互斥，即不能同时有一个线程在读，而另一个线程在写；读-读允许，读者和读者之间没有关系，即可以有一个或多个读者同时读。

FIFO的方法用下边的Queue改写一下。

///////////////////// Queueh //////////////////////////////

#ifndef QUEUE_H

#define QUEUE_H

namespace MyLibrary

{

#define MYLIBRARY_DEBUG

// MYLIBRARY_DEBUG 为测试而用

#ifdef MYLIBRARY_DEBUG

#include <iostream>

using std::ostream;

#endif

/// type def

#ifndef FALSE

#define FALSE false

#endif

#ifndef TRUE

#define TRUE true

#endif

typedef size_t size_type;

typedef bool BOOL;

/// 声明

template <typename _Ty> class Queue;

#ifdef MYLIBRARY_DEBUG

template <typename _Ty>

ostream & operator << ( ostream & , const Queue<_Ty> & );

#endif

//////////////////////// class ////////////////////////////

template <typename _Ty>

class Queue

{

//友元声明

#ifdef MYLIBRARY_DEBUG

friend ostream & operator << <> ( ostream &, const Queue<_Ty> & );

#endif

private:

//嵌套类定义

class QueueItem

{

public:

QueueItem( _Ty data ):_prior(0),_next(0),_data(data){}

public:

QueueItem _prior; //前向指针

QueueItem _next; //后向指针

_Ty _data; //数据

};

private:

//数据集

typename Queue<_Ty>::QueueItem _head; //头结点指针

typename Queue<_Ty>::QueueItem _tail; //尾结点指针

size_type _size; //长度

static const _Ty _temp; //只做空数据

public:

//构造析构集

inline Queue():_head(0),_tail(0),_size(0){}

inline Queue( const Queue<_Ty> & );

inline ~Queue(){ while( !empty() )del(); }

public:

//外部 *** 作接口集

inline const size_type size ( void ) const;

inline const BOOL empty ( void ) const;

inline const Queue & add ( const _Ty & );

inline const BOOL del ( void );

inline const BOOL del ( _Ty & );

inline const _Ty & get ( void )const;

public:

//重载 *** 作符集

inline const Queue<_Ty> & operator = ( const Queue<_Ty> & );

inline const Queue<_Ty> & operator += ( const Queue<_Ty> & );

inline const Queue<_Ty> & operator += ( const _Ty & );

inline const Queue<_Ty> operator + ( const Queue<_Ty> & );

inline const Queue<_Ty> operator + ( const _Ty & );

inline const BOOL operator == ( const Queue<_Ty> & )const;

inline const BOOL operator != ( const Queue<_Ty> & )const;

};

template <typename _Ty>

inline const Queue<_Ty>

Queue<_Ty>::operator + ( const _Ty & value )

{

Queue<_Ty> temp = this;

return temp+=value;

}

template <typename _Ty>

inline const Queue<_Ty> &

Queue<_Ty>::operator += ( const _Ty & value )

{

this->add( value );

return this;

}

template <typename _Ty>

inline const Queue<_Ty>

Queue<_Ty>::operator + ( const Queue<_Ty> & queue )

{

// q=q1+q2;

if( queueempty() )

{

return this;

}

else

{

Queue<_Ty> temp = this;

return temp += queue;

}

}

template <typename _Ty>

inline const Queue<_Ty> &

Queue<_Ty>::operator += ( const Queue<_Ty> & queue )

{

if( ! queueempty() )

{

for( const typename Queue<_Ty>::QueueItem it = queue_head;

it != queue_tail;

it = it->_prior )

{

this->add( it->_data );

}

this->add( queue_tail->_data );

}

return this;

}

template <typename _Ty>

inline const BOOL

Queue<_Ty>::operator != ( const Queue<_Ty> & queue )const

{

if( queuesize() != this->size() )

{

return TRUE;

}

else

{

const typename Queue<_Ty>::QueueItem youit = queue_tail;

const typename Queue<_Ty>::QueueItem myit = this->_tail;

for(; myit != this->_head; myit=myit->_next,youit=youit->_next)

{

if( myit->_data != youit->_data )

{

return TRUE;

}

}

return (queue_head->_data != this->_head->_data)TRUE:FALSE;

}

}

template <typename _Ty>

inline const BOOL

Queue<_Ty>::operator == ( const Queue<_Ty> & queue )const

{

if( queuesize() != this->size() )

{

return FALSE;

}

else

{

const typename Queue<_Ty>::QueueItem youit = queue_tail;

const typename Queue<_Ty>::QueueItem myit = this->_tail;

for(; myit != this->_head; myit=myit->_next,youit=youit->_next)

{

if( myit->_data != youit->_data )

{

return FALSE;

}

}

return (queue_head->_data != this->_head->_data)FALSE:TRUE;

}

}

template <typename _Ty>

inline const Queue<_Ty> &

Queue<_Ty>::operator = ( const Queue<_Ty> & queue )

{

if( &queue == this )

{

return this;

}

else

{

while( ! this->empty() )

{

this->del();

}

for( const typename Queue<_Ty>::QueueItem it = queue_head;

it != queue_tail;

it = it->_prior )

{

this->add( it->_data );

}

this->add( queue_tail->_data );

return this;

}

}

template <typename _Ty>

const _Ty Queue<_Ty>::_temp = _Ty();

template <typename _Ty>

inline const _Ty &

Queue<_Ty>::get( void )const

{

if( this->empty() )

return _temp; //返回表的空数据

else

{

return this->_head->_data;

}

}

template <typename _Ty>

inline const BOOL

Queue<_Ty>::del( void )

{

if( this->empty() )

return FALSE;

else

{

const typename Queue<_Ty>::QueueItem temp = _head;

_head = _head->_prior;

--_size;

delete temp;

return TRUE;

}

}

template <typename _Ty>

inline const BOOL

Queue<_Ty>::del( _Ty & value )

{

if( this->empty() )

return FALSE;

else

{

const typename Queue<_Ty>::QueueItem temp = _head;

value = temp->_data;

_head = _head->_prior;

--_size;

delete temp;

return TRUE;

}

}

template <typename _Ty>

inline const size_type

Queue<_Ty>::size(void)const

{

return _size;

}

template <typename _Ty>

inline const BOOL

Queue<_Ty>::empty( void )const

{

return (_size)FALSE:TRUE;

}

template <typename _Ty>

inline const Queue<_Ty> &

Queue<_Ty>::add( const _Ty & value )

{

typename Queue<_Ty>::QueueItem temp =

new typename Queue<_Ty>::QueueItem( value );

if( empty() )

{

_head = _tail = temp;

++_size;

}

else

{

temp->_next = _tail;

_tail->_prior = temp;

_tail = temp;

++_size;

}

return this;

}

template <typename _Ty>

inline Queue<_Ty>::Queue( const Queue<_Ty> & queue )

:_head(0),_tail(0),_size(0)

{

if( this == &queue )

return;

for( const typename Queue<_Ty>::QueueItem iter = queue_head;

iter != queue_tail;

iter = iter->_prior )

{

this->add( iter->_data );

}

this->add( queue_tail->_data );

return;

}

#ifdef MYLIBRARY_DEBUG

template <typename _Ty>

inline ostream & operator << ( ostream & os, const Queue<_Ty> & queue )

{

os<<"Queue("<<queuesize()<<"):\n";

os<<"head--->";

if( !queueempty() )

{

for( const typename Queue<_Ty>::QueueItem it = queue_head;

it != queue_tail;

it = it->_prior )

{

os<<it->_data<<" ";

}

os<<queue_tail->_data;

}

os<<"<---tail\n";

return os;

}

#endif

}////////// end namespace MyLibrary

#endif

真不容易啊，怕是没人弄了!

优先级调度算法程序:

#include "stdioh"

#include "stdlibh"

#include "stringh"

typedef struct node

{

char name[10]; /进程标识符/

int prio; /进程优先数/

int round; /进程时间轮转时间片/

int cputime; /进程占用CPU时间/

int needtime; /进程到完成还要的时间/

int count; /计数器/

char state; /进程的状态/

struct node next; /链指针/

}PCB;

PCB finish,ready,tail,run; /队列指针/

int N; /进程数/

/将就绪队列中的第一个进程投入运行/

firstin()

{

run=ready; /就绪队列头指针赋值给运行头指针/

run->state='R'; /进程状态变为运行态/

ready=ready->next; /就绪对列头指针后移到下一进程/

}

/标题输出函数/

void prt1(char a)

{

if(toupper(a)=='P') /优先数法/

printf(" name cputime needtime priority state\n");

else

printf(" name cputime needtime count round state\n");

}

/进程PCB输出/

void prt2(char a,PCB q)

{

if(toupper(a)=='P') /优先数法的输出/

printf(" %-10s%-10d%-10d%-10d %c\n",q->name,

q->cputime,q->needtime,q->prio,q->state);

else/轮转法的输出/

printf(" %-10s%-10d%-10d%-10d%-10d %-c\n",q->name,

q->cputime,q->needtime,q->count,q->round,q->state);

}

/输出函数/

void prt(char algo)

{

PCB p;

prt1(algo); /输出标题/

if(run!=NULL) /如果运行指针不空/

prt2(algo,run); /输出当前正在运行的PCB/

p=ready; /输出就绪队列PCB/

while(p!=NULL)

{

prt2(algo,p);

p=p->next;

}

p=finish; /输出完成队列的PCB/

while(p!=NULL)

{

prt2(algo,p);

p=p->next;

}

getch(); /压任意键继续/

}

/优先数的插入算法/

insert1(PCB q)

{

PCB p1,s,r;

int b;

s=q; /待插入的PCB指针/

p1=ready; /就绪队列头指针/

r=p1; /r做p1的前驱指针/

b=1;

while((p1!=NULL)&&b) /根据优先数确定插入位置/

if(p1->prio>=s->prio)

{

r=p1;

p1=p1->next;

}

else

b=0;

if(r!=p1) /如果条件成立说明插入在r与p1之间/

{

r->next=s;

s->next=p1;

}

else

{

s->next=p1; /否则插入在就绪队列的头/

ready=s;

}

}

/轮转法插入函数/

insert2(PCB p2)

{

tail->next=p2; /将新的PCB插入在当前就绪队列的尾/

tail=p2;

p2->next=NULL;

}

/优先数创建初始PCB信息/

void create1(char alg)

{

PCB p;

int i,time;

char na[10];

ready=NULL; /就绪队列头指针/

finish=NULL; /完成队列头指针/

run=NULL; /运行队列指针/

printf("Enter name and time of process\n"); /输入进程标识和所需时间创建PCB/

for(i=1;i<=N;i++)

{

p=malloc(sizeof(PCB));

scanf("%s",na);

scanf("%d",&time);

strcpy(p->name,na);

p->cputime=0;

p->needtime=time;

p->state='w';

p->prio=50-time;

if(ready!=NULL) /就绪队列不空调用插入函数插入/

insert1(p);

else

{

p->next=ready; /创建就绪队列的第一个PCB/

ready=p;

}

}

clrscr();

printf(" output of priority:\n");

printf("\n");

prt(alg); /输出进程PCB信息/

run=ready; /将就绪队列的第一个进程投入运行/

ready=ready->next;

run->state='R';

}

/轮转法创建进程PCB/

void create2(char alg)

{

PCB p;

int i,time;

char na[10];

ready=NULL;

finish=NULL;

run=NULL;

printf("Enter name and time of round process\n");

for(i=1;i<=N;i++)

{

p=malloc(sizeof(PCB));

scanf("%s",na);

scanf("%d",&time);

strcpy(p->name,na);

p->cputime=0;

p->needtime=time;

p->count=0; /计数器/

p->state='w';

p->round=2; /时间片/

if(ready!=NULL)

insert2(p);

else

{

p->next=ready;

ready=p;

tail=p;

}

}

clrscr();

printf(" output of round\n");

printf("\n");

prt(alg); /输出进程PCB信息/

run=ready; /将就绪队列的第一个进程投入运行/

ready=ready->next;

run->state='R';

}

/优先数调度算法/

priority(char alg)

{

while(run!=NULL) /当运行队列不空时，有进程正在运行/

{

run->cputime=run->cputime+1;

run->needtime=run->needtime-1;

run->prio=run->prio-3; /每运行一次优先数降低3个单位/

if(run->needtime==0) /如所需时间为0将其插入完成队列/

{

run->next=finish;

finish=run;

run->state='F'; /置状态为完成态/

run=NULL; /运行队列头指针为空/

if(ready!=NULL) /如就绪队列不空/

firstin(); /将就绪对列的第一个进程投入运行/

}

else /没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列/

if((ready!=NULL)&&(run->prio<ready->prio))

{

run->state='W';

insert1(run);

firstin(); /将就绪队列的第一个进程投入运行/

}

prt(alg); /输出进程PCB信息/

}

}

/时间片轮转法/

roundrun(char alg)

{

while(run!=NULL)

{

run->cputime=run->cputime+1;

run->needtime=run->needtime-1;

run->count=run->count+1;

if(run->needtime==0)/运行完将其变为完成态，插入完成队列/

{

run->next=finish;

finish=run;

run->state='F';

run=NULL;

if(ready!=NULL)

firstin(); /就绪对列不空，将第一个进程投入运行/

}

else

if(run->count==run->round) /如果时间片到/

{

run->count=0; /计数器置0/

if(ready!=NULL) /如就绪队列不空/

{

run->state='W'; /将进程插入到就绪队列中等待轮转/

insert2(run);

firstin(); /将就绪对列的第一个进程投入运行/

}

}

prt(alg); /输出进程信息/

}

}

/主函数/

main()

{

char algo; /算法标记/

clrscr();

printf("type the algorithm:P/R(priority/roundrobin)\n");

scanf("%c",&algo); /输入字符确定算法/

printf("Enter process number\n");

scanf("%d",&N); /输入进程数/

if(algo=='P'||algo=='p')

{

create1(algo); /优先数法/

priority(algo);

}

else

if(algo=='R'||algo=='r')

{

create2(algo); /轮转法/

roundrun(algo);

}

}

以上就是关于优先级调度算法全部的内容，包括:优先级调度算法、设计一个按响应比高者优先调度算法实现进程调度的程序。、广度优先算法（宽搜）pascal等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zz/10115396.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
北京科技大学分数线 北京科技大学分数线 一级用户组
0 0
上一篇 2023-05-05
下一篇 2023-05-05

发表评论

登录后才能评论

评论列表（0条）

保存