设计一个有N个进程共行的进程调度程序

jingchendiaoducpp

#include "stdioh"

#include <stdlibh>

#include <conioh>

#define getpch(type) (type)malloc(sizeof(type))

#define NULL 0

struct pcb { / 定义进程控制块PCB /

char name[10];

char state;

int super;

int ntime;

int rtime;

struct pcb link;

}ready=NULL,p;

typedef struct pcb PCB;

sort() / 建立对进程进行优先级排列函数/

{

PCB first, second;

int insert=0;

if((ready==NULL)||((p->super)>(ready->super))) /优先级最大者,插入队首/

{

p->link=ready;

ready=p;

}

else / 进程比较优先级,插入适当的位置中/

{

first=ready;

second=first->link;

while(second!=NULL)

{

if((p->super)>(second->super)) /若插入进程比当前进程优先数大,/

{ /插入到当前进程前面/

p->link=second;

first->link=p;

second=NULL;

insert=1;

}

else / 插入进程优先数最低,则插入到队尾/

{

first=first->link;

second=second->link;

}

}

if(insert==0) first->link=p;

}

}

input() / 建立进程控制块函数/

{

int i,num;

clrscr(); /清屏/

printf("\n 请输入进程号");

scanf("%d",&num);

for(i=0;i<num;i++)

{

printf("\n 进程号No%d:\n",i);

p=getpch(PCB);

printf("\n 输入进程名:");

scanf("%s",p->name);

printf("\n 输入进程优先数:");

scanf("%d",&p->super);

printf("\n 输入进程运行时间:");

scanf("%d",&p->ntime);

printf("\n");

p->rtime=0;p->state='w';

p->link=NULL;

sort(); / 调用sort函数/

}

}

int space()

{

int l=0; PCB pr=ready;

while(pr!=NULL)

{

l++;

pr=pr->link;

}

return(l);

}

disp(PCB pr) /建立进程显示函数,用于显示当前进程/

{

printf("\n qname \t state \t super \t ndtime \t runtime \n");

printf("|%s\t",pr->name);

printf("|%c\t",pr->state);

printf("|%d\t",pr->super);

printf("|%d\t",pr->ntime);

printf("|%d\t",pr->rtime);

printf("\n");

}

check() / 建立进程查看函数 /

{

PCB pr;

printf("\n 当前正在运行的进程是:%s",p->name); /显示当前运行进程/

disp(p);

pr=ready;

printf("\n 当前就绪队列状态为:\n"); /显示就绪队列状态/

while(pr!=NULL)

{

disp(pr);

pr=pr->link;

}

}

destroy() /建立进程撤消函数(进程运行结束,撤消进程)/

{

printf("\n 进程 [%s] 已完成\n",p->name);

free(p);

}

running() / 建立进程就绪函数(进程运行时间到,置就绪状态/

{

(p->rtime)++;

if(p->rtime==p->ntime)

destroy(); / 调用destroy函数/

else

{

(p->super)--;

p->state='w';

sort(); /调用sort函数/

}

}

main() /主函数/

{

int len,h=0;

char ch;

input();

len=space();

while((len!=0)&&(ready!=NULL))

{

ch=getchar();

h++;

printf("\n The execute number:%d \n",h);

p=ready;

ready=p->link;

p->link=NULL;

p->state='R';

check();

running();

printf("\n 按任一键继续");

ch=getchar();

}

printf("\n\n 进程已经完成\n");

ch=getchar();

}

分类: 电脑/网络 >> *** 作系统/系统故障

问题描述:

请问各位大虾

Windows进程调度的方式有那几种？

谢谢了

解析:

高级调度：又称作业调度。其主要功能是根据一定的算法，从输人的一批作业中选出若干个作业，分配必要的资源，如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输人、输出进程），最后把它们的程序和数据调人内存，等待进程调度程序对其执行调度，并在作业完成后作善后处理工作。

低级调度：又称进程调度。其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。执行低级调度功能的程序称做进程调度程序，由它实现CPU在进程间的切换。进程调度的运行频率很高，在分时系统中往往几十毫秒就要运行一次。进程调度是 *** 作系统中最基本的一种调度。在一般类型的 *** 作系统中都必须有进程调度，而且它的策略的优劣直接影响整个系统的计能。

中级调度：又称交换调度。为了使内存中同时存放的进程数目不至于太多，有时就需要把某些进程从内存中移到外存上，以减少多道程序的数目，为此设立了中级调度。特别在采用虚拟存储技术的系统或分时系统中，往往增加中级调度这一级。所以中级调度的功能是在内存使用情况紧张时，将一些暂时不能运行的讲程从内存对换到外存上等待。当以后内存有足够的空闲空间时，再将合适的进程重新换人内存，等待进程调度。引人中级调度的主要目的是为了提高内存的利用率和系统吞吐量。它实际上就是存储器管理中的对换功能

下面说说进程调度的策略问题（引用参考资料内容）：

首先硬件机制上如何保证 *** 作系统的内核调度进程可以一定的时机可以获得CPU,来进行进程调度

通常我们会在软件层次上找答案其实,是通过在CPU的硬件处理机制上实现的CPU在执行完每个指令的周期后回扫描CPU的内部的一个中断寄存器,查询是否存在中断发生,若没有,则继续执行指令;若有,则保存当前的CPU工作环境,跳转到中断服务列程,CPU执行中断服务程序,在推出中断后,跳转到内核调度程序(这是个内核程序,但是是对所有的进程共享的,包括用户进程);此时,内核调度程序占据CPU,进行进程的调度,以决定下个将占用CPU的进程

接下来就要谈谈什么时候会需要进行进程调度

在教科书书说到的有几种情况:1时间片到,即每个进程所分配的时间片用完后,要跳转到调度程序; 2 占用CPU的当前运行进程提出I/O *** 作,发起对内核的系统调用时,在系统调用结束后,跳转到调度程序; 3 我自己的想法: 当前运行进程对所有内核系统调用的结束时都要跳转到调度程序,根据当前的调度信息来决定下一个可以占用CPU的进程 我所指的系统调用也包括中断列程不过对与具体的调度时机,很多书上都写的不清不楚,真不知道他们不懂,还是不屑于写出来告诉我们 其实除了在大多数硬件中断的触发后跳转到调度程序, 每个时钟中断发生的时候,我觉得都需要跳转到调度程序(在进入时钟中断列程中,要对进程表中的所有的进程的调度信息进行更新和对各个进程队列的处理),对更新后的进程信息进行处理以决定调度哪个进程 通常的教科书中都将硬件物理的处理机制和软件的调度处理机制分开,在物理和逻辑两个层次上分开谈,不利于我们理解最好是把这两个结合起来理解进程调度的工作机制目前需要解决的是:在什么时候需要内核调度程序占据CPU来调度 至于调度的算法那就是逻辑层次上要考虑的东西

其实看了这么多,我也有了些小论文的想法, 因为做的方向是应用在电子电力电路上的嵌入系统控制该应用对嵌入 *** 作系统的性能就有些特殊的需求:首先体积要小,速度快;内核就要小,进程调度要实现抢占式任务调度,且调度切换要快它的进程调度与通用 *** 作系统的进程调度不同,这是因为它们的要求不一样,嵌入式通常是要求是实时,且严格的讲在电路上的控制系统应该是硬实时,而不象通用系统是非实时,或者是软实时这跟它们对实时性的要求不同所以我初步定个题目 "嵌入式系统和通用系统在进程调度上比较和分析,并针对特定的电路控制嵌入实时系统提出一个调度策略" 我想我从明天开始就要准备这方面的资料,分析分析,比较比较,弄篇小论文出来,,不然我都快给它凡死了

*** 作系统-----进程调度

[/color][color=Gray][/color][color=Blue][/color][color=Lime] 要求：实现按优先级与时间片相结合的进程调度算法

内容：

1：设计进程控制快，进程队列结构（包括：就绪队列，等待队列，运行队列）等必要的数据结构。

2：模拟 *** 作系统进程调度的功能，编写进程调度程序，模拟的处理机分派程序，进程等待函数和进程唤醒函数。

3：编写用户程序，创建6个用户进程。

进程调度的设计方法

1。数据结构

（1）优先级与时间片的设计

◆进程因等待放弃CPU时，优先级置为1（高优先级）

◆进程因时间片到放弃CPU时，优先级置为0（低优先级）

◆优先1对应时间片4；优先级0对应时间片10。

（2）进程控制块（PCB）的内容

进程标识3---9

进程优先级 0，1

进程优先级 0，1

进程等待时间 20

链接指针

2：程序算法

（1）PCB结构，变量与主程序

struct PCB

{

int pname;

int pri;

int runtime;

int waitting;

struct PCBnext;

}

pcb[7];

struct PCBrunning,ready,wait;

int sin=0;

main()

{ 创建PCB[3]--PCB[9]并插入ready队列；／pname分别为3--9,

pri=0,runtime=10,waittime=0 /

for(;;)/系统程序，完成初始化和处理机分派功能 /

{cast{sig=0:swtch;

sig=1:waiter;

sig=3:proc3;

sig=4:proc4;

sig=5:proc5;

sig=6:proc6;

sig=7:proc7;

sig=8:proc8;

sig=9:proc9;}

}

}

(2) 进程调度程序

swtch()

{

while(ready==NULL)wakeup();

移出就绪队列第一个PCB;

送running指针；

若pri=1,则runntime=4,否则runtime=10;

将running→pname 送sig

}

(3) 将进程等待函数

wait()

{将运行进程插入wait队列，优先数置1；

sig=0;

}

(4) 进程唤醒函数

wakeup()

{

将wait队列中所有的PCB中waittime减1；

将wait队列中的所有的waittime=0的PCB揭除；

插入到ready队列中第一个优先级为0的PCB前面

｝

我们知道，进程运行需要各种各样的系统资源，如内存、文件、打印机和最

宝贵的 CPU 等，所以说，调度的实质就是资源的分配。系统通过不同的调度算法（Scheduling Algorithm）来实现这种资源的分配。通常来说，选择什么样的调度算法取决于资源分配的策略（Scheduling Policy）。

有关调度相关的结构保存在 task_struct 中，如下：

active_mm 是为内核线程而引入的，因为内核线程没有自己的地址空间，为了让内核线程与普通进程具有统一的上下文切换方式，当内核线程进行上下文切换时，让切换进来的线程的 active_mm 指向刚被调度出去的进程的 active_mm（如果进程的mm 域不为空，则其 active_mm 域与 mm 域相同）。

在 linux 26 中 sched_class 表示该进程所属的调度器类有3种：

进程的调度策略有5种，用户可以调用调度器里不同的调度策略：

在每个 CPU 中都有一个自身的运行队列 rq，每个活动进程只出现在一个运行队列中，在多个 CPU 上同时运行一个进程是不可能的。

运行队列是使用如下结构实现的：

tast 作为调度实体加入到 CPU 中的调度队列中。

系统中所有的运行队列都在 runqueues 数组中，该数组的每个元素分别对应于系统中的一个 CPU。在单处理器系统中，由于只需要一个就绪队列，因此数组只有一个元素。

内核也定义了一下便利的宏，其含义很明显。

Linux、c/c++服务器开发篇-------我们来聊聊进程的那些事

Linux内核 进程间通信组件的实现

学习地址：C/C++Linux服务器开发/后台架构师零声教育-学习视频教程-腾讯课堂

需要C/C++ Linux服务器架构师学习资料加qun812855908获取（资料包括 C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg 等），免费分享

在分析调度流程之前，我们先来看在什么情况下要执行调度程序，我们把这种情况叫做调度时机。

Linux 调度时机主要有。

时机1，进程要调用 sleep() 或 exit() 等函数进行状态转换，这些函数会主动调用调度程序进行进程调度。

时机2，由于进程的时间片是由时钟中断来更新的，因此，这种情况和时机4 是一样的。

时机3，当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查 need_resched 的值，如果必要，则调用调度程序 schedule() 主动放弃 CPU。

时机4 ， 如前所述， 不管是从中断、异常还是系统调用返回， 最终都调用 ret_from_sys_call()，由这个函数进行调度标志的检测，如果必要，则调用调用调度程序。那么，为什么从系统调用返回时要调用调度程序呢？这当然是从效率考虑。从系统调用返回意味着要离开内核态而返回到用户态，而状态的转换要花费一定的时间，因此，在返回到用户态前，系统把在内核态该处理的事全部做完。

Linux 的调度程序是一个叫 Schedule() 的函数，这个函数来决定是否要进行进程的切换，如果要切换的话，切换到哪个进程等。

从代码分析来看，Schedule 主要完成了2个功能：

进程上下文切换包括进程的地址空间的切换和执行环境的切换。

对于 switch_mm 处理，关键的一步就是它将新进程页面目录的起始物理地址装入到寄存器 CR3 中。CR3 寄存器总是指向当前进程的页面目录。

switch_to 把寄存器中的值比如esp等存放到进程thread结构中，保存现场一边后续恢复，同时调用 __switch_to 完成了堆栈的切换。

在进程的 task_struct 结构中有个重要的成分 thread，它本身是一个数据结构 thread_struct, 里面记录着进程在切换时的（系统空间）堆栈指针，取指令地址（也就是“返回地址”）等关键性的信息。

关于__switch_to 的工作就是处理 TSS （任务状态段）。

TSS 全称task state segment，是指在 *** 作系统进程管理的过程中，任务（进程）切换时的任务现场信息。

linux 为每一个 CPU 提供一个 TSS 段，并且在 TR 寄存器中保存该段。

linux 中之所以为每一个 CPU 提供一个 TSS 段，而不是为每个进程提供一个TSS 段，主要原因是 TR 寄存器永远指向它，在任务切换的适合不必切换 TR 寄存器，从而减小开销。

在从用户态切换到内核态时，可以通过获取 TSS 段中的 esp0 来获取当前进程的内核栈 栈顶指针，从而可以保存用户态的 cs,esp,eip 等上下文。

TSS 在任务切换过程中起着重要作用，通过它实现任务的挂起和恢复。所谓任务切换是指，挂起当前正在执行的任务，恢复或启动另一任务的执行。

在任务切换过程中，首先，处理器中各寄存器的当前值被自动保存到 TR（任务寄存器）所指定的任务的 TSS 中；然后，下一任务的 TSS 被装入 TR；最后，从 TR 所指定的 TSS 中取出各寄存器的值送到处理器的各寄存器中。由此可见，通过在 TSS 中保存任务现场各寄存器状态的完整映象，实现任务的切换。

因此，__switch_to 核心内容就是将 TSS 中的内核空间（0级）堆栈指针换成 next->esp0。这是因为 CPU 在穿越中断门或者陷阱门时要根据新的运行级别从TSS中取得进程在系统空间的堆栈指针。

thread_structesp0 指向进程的系统空间堆栈的顶端。当一个进程被调度运行时，内核会将这个变量写入 TSS 的 esp0 字段，表示这个进程进入0级运行时其堆栈的位置。换句话说，进程的 thread_struct 结构中的 esp0 保存着其系统空间堆栈指针。当进程穿过中断门、陷阱门或者调用门进入系统空间时，处理器会从这里恢复期系统空间栈。

由于栈中变量的访问依赖的是段、页、和 esp、ebp 等这些寄存器，所以当段、页、寄存器切换完以后，栈中的变量就可以被访问了。

因此 switch_to 完成了进程堆栈的切换，由于被切进的进程各个寄存器的信息已完成切换，因此 next 进程得以执行指令运行。

由于 A 进程在调用 switch_to 完成了与 B 进程堆栈的切换，也即是寄存器中的值都是 B 的，所以 A 进程在 switch_to 执行完后，A停止运行，B开始运行，当过一段时间又把 A 进程切进去后，A 开始从switch_to 后面的代码开始执行。

schedule 的调用流程如下：

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统，是像Linux这样的多任务 *** 作系统的基础。

多任务 *** 作系统就是能同时并发地交互执行多个进程的 *** 作系统。可以分为两类：

进程可以分为I/O消耗型和处理器消耗型（进程可以同时展示这两种行为）。

调度策略通常要在两个矛盾的目标中寻找平衡：进程响应迅速和最大系统利用率。Linux为了保证交互式应用和桌面系统的性能，对进程的响应做了优化（缩短响应时间），更倾向于优先调度I/O消耗型进程。

Linux采用了两种不同的优先级范围：

实时优先级和nice值处于互不相交的两个范畴，任何实时进程的优先级都高于普通进程。

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。

Linux自26内核系统开始引入新的进程调度算法，其中最著名的是“反转楼梯最后期限调度算法（rotating staircase deadline scheduler，RSDL）”，被称为“完成公平调度算法（CFS）”。

Linux的CFS调度器并没有直接分配时间片到进程，而是将处理器的使用比例划分给进程，也就是说，进程所获得的处理器时间和系统负载密切相关的。当一个进程进入可运行状态，他就被准许投入运行。Linux的CFS调度器，其抢占时机取决于新的可运行进程消耗了多少处理器使用比。如果消耗的使用比例比当前进程小，则新的进程立刻投入运行，抢占当前进程，否则推迟运行。

Linux调度器是以模块方式提供的，以允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础调度器会按照优先级顺序进程遍历调度类，拥有一个可执行进程的最高优先级的调度类胜出，去选择接下来要执行的程序。

CFS允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行的进程。nice值作为进程获得的处理器运行比的权重，nice值越低权重越高。每个进程都按照其权重在全部可行进程中所占比例的“时间片”来运行，任何进程所获的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标，称为目标延迟。

CFS调度算法的实现，主要关注：

所有的调度器都必须对进程运行时间做记账。CFS通过时间记账确保每个进程只在公平分配给它的处理器时间内运行。

CFS使用调度器实体结构来追踪进程运行记账，该结构为进程描述符（struct task_struct的成员变量）：

vruntime变量存放进程的虚拟运行时间，经过了所有可运行进程总数的标准化（被加权的）。以ns为单位，和定时器节拍不相关。CFS使用vruntime来记录一个程序到底运行了多长时间以及它还应该再运行多久。

update_curr()函数实现了记账功能。是由系统定时器周期性调用的，无论进程处于可运行态，还是不可运行态。因此，vruntime可以准确地测量给定进程的运行时间，而且知道谁是应该被下一个运行的进程。

CFS算法的核心：选择具有最小的vruntime任务。

CFS使用红黑树（rbtree）来组织可运行进程队列，其节点的键值为可运行进程的虚拟运行时间vruntime，有利于迅速找到最小vruntime的进程（可通过__pick_next_entity()函数来访问红黑树最左的叶子即可，当然最左的叶子可能被缓存在rb_left_most字段中，可直接读取）。

另外，可通过enqueue_entity/dequeue_entity函数从红黑树中增加/删除进程。这两个函数都会调用update_curr()函数来更新所处理任务的运行时统计数据。

进程调度的主要入口点是schedule()函数，是内核其他部分用于调用进程调度器的入口：选择哪个进程运行，何时将其投入运行。schedule()函数会通过pick_next_task()函数遍历调度类，找出优先级最高的调度类（struct sched_class），再通过调度类的pick_next_entity()函数（会调用__pick_next_entity()函数）来选择要执行的进程。

休眠（被阻塞）的进程处于不可运行的状态。内核对其 *** 作是：进程把自己标记称休眠状态，从可执行红黑树中删除，放入等待队列，然后调用schedule()选择和执行下一个进程。

唤醒：进程被设置为可执行状态，然后从等待队列中移到可执行红黑树中。

其中，等待队列是由等待某些事件发生的进程组成的简单链表。

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由context_switch函数处理。

用户抢占：

Linux完整地支持内核抢占，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。只要没有持有锁，内核就可以进行抢占。内核抢占主要发生在：

普通的、非实时的调度策略是SCHED_NORMAL。

Linux提供两种实时调度策略：

Linux为实时调度策略提供一种软实时工作方式。也就是内核调度进程，尽力使进程在它的限定时间内运行，但内核不保证总能满足这些进程的要求。

对应的，硬实时系统保证在一定条件下，可以满足任何调度的要求。

七、与调度相关的系统调用

作业调度和进程调度属于处理机管理。

处理机调度是 *** 作系统的主要功能之一，它的实现策略决定了 *** 作系统的类型，其调度算法的优劣直接影响整个系统的性能。处理机调度的任务是选出待分派的作业或进程，为之分配处理机。

一般来说，处理机调度可分为三个级别，分别是高级调度、中级调度和低级调度。

高级调度又称作业调度，作业就是用户程序及其所需的数据和命令的集合，作业管理就是对作业的执行情况进行系统管理的程序的集合。作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法来选取作业。

引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量，使得暂时不运行的进程从内存对换到外存上。

低级调度又称进程调度，其主要功能是根据一定的算法将cpu分派给就绪队列中的一个进程。进程调度是 *** 作系统中最基本的一种调度，其调度策略的优劣直接影响整个系统的性能。

以上就是关于设计一个有N个进程共行的进程调度程序全部的内容，包括:设计一个有N个进程共行的进程调度程序、Windows进程调度的方式、Linux 进程管理之进程调度与切换等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！