多处理器系统进程分配

多处理器系统 (MPS) 的类型

紧密耦合型：共享内存和 I/O，通过高速总线连接。
松弛耦合型：独立内存和 I/O，通信线路或通道连接。
对称多处理器系统 (SMPS) 和非对称多处理器系统

非对称多处理器系统中进程分配方式

进程调度在主处理器上执行。
有潜在的不可靠性（主机故障造成系统崩溃）。
对称多处理器系统中进程分配方式

静态分配 

每个 CPU 设立一个就绪队列，进程从开始执行到完成， 

都在同一个 CPU 上。
动态分配 

各个 CPU 采用一个公共就绪队列，队首进程每次分派 

到当前空闲的 CPU 上执行。可防止系统中多个处理器 

忙闲不均。
多处理器系统中的进程调度方式：

自调度
专用处理器分配
成组调度
动态调度
自调度

各个处理机自行在就绪队列中取任务。

优点：不需要专门的处理机从事任务分派工作。
缺点: 当处理机个数较多（如十几个或上百个）时，对就绪队列的访问可能成为系统的瓶颈。
专用处理器分配

每个进（线）程分配一个专用处理机。

优点：切换少，效率高。

主要用于超级计算系统，实时系统。



成组调度

将一组相关的进程同时分派到多台处理机上运行，以减少进程之间相互等待而引起的进程切换，降低系统开销。

优点：对相互合作的进（线）程成组调度，可以减小切换，减小系统开销。

每次分配一组 CPU，减少了调度频率。

分配时间

面向所有应用程序平均分配处理器时间。
面向所有线程平均分配处理器时间。


动态调度

基本思想：由操作系统和应用进程共同完成调度。

操作系统负责在应用进程之间划分处理器。

应用进程在分配给它的处理器上执行可运行线程的子集，哪一些线程应该执行，哪一些线程应该挂起完全是应用进程自己的事。

分配原则

空闲则分配、新作业优先、保持等待（忙则等待）、释放即分配



UNIX 的进程调度



调度类型

UNIX 是单纯的分时系统，无作业调度，只设置有中级调度和低级调度。

调度算法

采用多级反馈队列轮转调度。 

动态优先数轮转调度算法



进程优先级的计算

操作系统算法模拟实例之单处理机系统进程调度
1.实验目的
在多道程序或多任务系统中，系统回时处于就绪态的进程有若干个，为使系统中

的各进程能有条不素地运行，必须选择某种调度策略，以选择一进程占用处理机。

要求学生设计一个模拟单处理机调度算法，以巩固和加探对进念和进程调度算法的理解。
2.实验内容
编写程序完成单处理机系统中的进程调度，要求采用最高优先级优先调度算法。具体内容包括

确定进程控制块的内容和组织方式；
完成进程创建原语和进调度原语：
编写主函数井对所做的工作进行测试

3.实验指导
进程调度算法：
采用最高优先级优先调度算法(即把处理机分配给优先级最高的进程)和先来先服务调度算法，每个进程用一个进程控制块(PCB)表示，进程控制块可以包含以下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间，进程状态等。进程的优先数(表示优先级别)及需要的运行时间可以事先人为描定(也可以随机数产生)，进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位。
每个进程的状态可以是就绪W(Wait)，运行R(Run)或完成F( Finish)三种状态之就绪进程获得CPU后都只能运行一个时间片，用已占用CPU时间加1来表示，如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则激销该进程，如果运行一个时间片后进程的已占用CPU时间还未达到所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1(即降低一级)，然后把它插入就绪队列等待CPU。
每进行一次，调度程序都打印一次运行进程，就绪队列以及各个进程的PCB，以假进

行检查。重复以上过程，直到所有进程都完成为止。
4.程序实例
#include"stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type)(type *)malloc(sizeof(type))

struct pcb               //定义进程控制块
{
    char name[10];
    char state;
    int super;
    int ntime;
    int rtime;
    struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
int 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;
    }
}
/*
    说明：上述程序首先定义进程控制块结构，然后对每个进程的优先级赋初值，完成
    优先级的排序过程，把优先级大的进程插入就绪队首，等待cup调度，该实验完成了
    优先级大者优先调度的原则，从而对进程调度过程加深理解和掌握
*/
int input() //建立进程控制块函数
{
    int i,num;

    system("cls");       //清屏
    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();
    }
}
int space()
{
    int l = 0;
    PCB *pr = ready;
    while(pr!=NULL)
    {
        l++;
        pr = pr->link;

    }
    return(l);
}
int 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");

}
int check()         //进程查看函数
{
    PCB *pr;
    printf("\n****当前正在运行的程序是：%s",p->name );     //显示当前运行进程
    disp(p);
    pr=ready;
    printf("\n****当前就绪队列状态为：\n");                //显示就绪队列状态
    while (pr!=NULL)
    {
        disp(pr);
        pr=pr->link;
    }
}
int destroy()                      //建立进程撤销函数（进程运行结束，撤销进程）
{
    printf("\n进程{%s}已完成.\n",p->name );
    free(p);

}
int running()                  //建立进程就绪函数（进程运行时间到，置就绪状态）
{
    (p->rtime )++;
    if(p->rtime ==p->ntime )
        destroy();
    else
    {
        (p->super )--;
        p->state ='w';
        sort();
    }
}
int 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();
}

操作系统3——处理机调度（作业调度+进程调度）

目录

操作系统3——处理机调度（作业调度+进程调度）

1、处理机的调度层次和目标

2、作业调度——先来先服务调度算法（FCFS）

3、作业调度——短作业优先调度算法（SJF）short job first

3、作业调度——优先级调度算法（PSA）priority-scheduling algorithm first

4、作业调度——高响应比优先调度算法（HRRF）

5、进程调度——时间片轮转调度算法(RR—Round Robin)

6、进程调度——优先级调度算法

7、进程调度——多队列调度算法

1、处理机的调度层次和目标

（1）什么是处理及调度？

在多道程序环境下，进程数目通常多于处理机的数目，系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程。

（2）什么是作业？

作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等，作业是用户提交给系统的一项相对独立的工作。

（3）什么是作业步？

    每个作业会配置一个作业说明书，作业的每个步骤称为一个作业步。每个作业设置一个JCB（作业控制块）是作业唯一的符号标识，包含作业标识，用户名称，用户账号，作业类型，作业状态，调度信息等。

（4）作业状态间转换：



处理机调度的层次：

 


			
处理机调度层次
			
			

			
高级调度
			
			

			
也称作业调度或长程调度，调度对象是作业，吧后备状态的作业调入到内存
			
		

			
中级调度
			
			

			
也称中程调度，调度对象是暂时不能运行的进程，调至外存
			
		

			
低级调度
			
			

			
也称进程调度或短程调度，调度对象是进程
			
		
（5）处理机调度算法的目标：


			
对于处理机调度算法目标
			
			

			
资源利用率高（CPU利用率）；

			
公平性；

			
平衡性
			
		

			
批处理系统目标
			
			

			
平均周转时间；

			
平均带权周转时间短；（周转时间/服务时间）

			
吞吐量；

			
处理机利用率
			
		

			
分时系统的目标
			
			

			
响应时间快；

			
均衡性；
			
		

			
实时系统目标
			
			

			
截止时间保证；

			
可预测性；
			
		
（6）进程的调度方式分类：

进程调度的任务：保存处理机的现场信息；按照某种算法选取进程；分配处理机给进程。

调度方式：

1.抢占式：当某一进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成或阻塞状态时。

2.非抢占式：当某一进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行的进程。

 

2、作业调度——先来先服务调度算法（FCFS）

（1）算法思想：按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度，

（2）优缺点：

有利于长作业（进程），而不利于短作业（进程）
	
有利于CPU繁忙型作业（进程） ，而不利于I/O繁忙型作业（进程）
	
用于批处理系统
	
可用于作业调度，也可用于进程调度
（3）调度算法的评价标准

周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。

平均周转时间：



带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS 



（4）FCFS算法实例



 

3、作业调度——短作业优先调度算法（SJF）short job first

（1）算法思想：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

（2）优缺点：

降低作业的平均等待时间，提高系统吞吐量；
	
对长作业不利，长作业长期不被调度——饥饿；
	
必须预知作业的运行时间；
	
完全未考虑作业的紧迫程度；
	
人机无法交互；
（3）SJF算法实例



 

3、作业调度——优先级调度算法（PSA）priority-scheduling algorithm first

算法思想：基于作业的紧迫程度，外部赋予作业优先级，调度算法根据优先级调度。

 

4、作业调度——高响应比优先调度算法（HRRF）

（1）算法思想：HRRF是FCFS和SJF的结合，克服了两种算法的缺点，设置响应比最高的作业优先启动。等待时间+服务时间=该作业的响应时间。

（2）调度策略

响应比最高的作业优先启动：



因等待时间+服务时间=该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为：



（3）HRRF的小结：

等待时间相同的作业，则要求服务的时间愈短，其优先级愈高；
	
要求服务的时间相同的作业，则等待时间愈长，其优先级愈高；
	
是FCFS和SJF的结合，克服了两种算法的缺点；
	
长作业，优先级随等待时间的增加而提高，其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机；
	
缺点：要进行响应比计算，增加了系统开销；
 

5、进程调度——时间片轮转调度算法(RR—Round Robin)

进程调度的任务：是控制、协调进程对CPU的竞争

（1）保存处理机的现场信息
	
（2）按算法调度进程
	
（3）处理机分配给进程
（1）时间片轮转调度算法的原理：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首。

（2）时间片大小的确定：与时间片大小有关的因素：系统响应时间；就绪进程个数；CPU能力



（3）算法的特点：

采用比FCFS更加公平的处理机分配方式，每个进程大约获得1/n的处理及时间 ；
	
进程上下文切换，增加系统开销；
	
没有考虑到进程的紧急程度；
	
既可以是抢占式的，也可以是非抢占式的；
	
缺点：紧迫任务响应慢。
 

6、进程调度——优先级调度算法

（1）抢占式优先级调度算法

把处理机分配给优先级最高的进程，但在执行期间，只要出现另一个优先级更高的进程，则进程调度程序就立即停止当前进程的执行，并将处理机分配给新到的优先级最高的进程。只要系统中出现一个新的就绪进程，就进行优先级比较

（2）非抢占式优先级调度算法

系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去，直至完成。

（3）静态优先级调度算法

静态优先级在创建进程时确定，且在进程的整个运行期间保持不变。

（4）动态优先级调度算法

优先级随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能。



 

7、进程调度——多队列调度算法

原理：设置多个就绪队列，并为各个队列赋予不同的优先级。

第一个队列的优先级最高，第二个队列次之，其余各队列的优先级逐个降低。

各个队列中时间片的大小也各不相同，队列优先级愈高，时间片就愈小。



队列的转换：

（1）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；

（2）仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行

（3）如果处理机正在第i队列中为某进程服务时，又有新进程进入优先级较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先级进程

题目要求

一、	实验目的

多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。

二、	实验内容

1．	优先权法、轮转法

简化假设

1）	进程为计算型的（无I/O）

2）	进程状态：ready、running、finish

3）	进程需要的CPU时间以时间片为单位确定

2．	算法描述

1）	优先权法——动态优先权

当前运行进程用完时间片后，其优先权减去一个常数。

2）	轮转法

三、	流程图





四、实验要求

1．	产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在1~20之间。

2．	进程数n不要太大通常取4~8个

3．	使用动态数据结构

4．	独立编程

5．	两种调度算法

实验报告
1.实验目的
多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。
2.实验内容与要求
①实验内容

1．	优先权法、轮转法

简化假设

1）	进程为计算型的（无I/O）

2）	进程状态：ready、running、finish

3）	进程需要的CPU时间以时间片为单位确定

2．	算法描述

1）	优先权法——动态优先权

当前运行进程用完时间片后，其优先权减去一个常数。

2）	轮转法
②实验要求

1．	产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在1~20之间。

2．	进程数n不要太大通常取4~8个

3．	使用动态数据结构

4．	独立编程

5．	两种调度算法
3.流程图与模块调用



4.实验分析
想要完成操作系统算法，首先要弄清楚操作系统相关的专业术语。弄清各个算法的流程和目的要求。才能模拟出相关算法的过程。

在我的理解中，

优先权算法：

①所有线程的先后序列核心是围绕优先权的权值大小。并且该优先权的大小会动态的变化，即每随着进程被调用了一次，权值减3。所以用队列（First In First Out）这种数据结构非常好。能够有效的节省空间，算法复杂度。

②优先权算法中某个线程的结束标识是还需要的时间needTime是否变为了0。所以在随机选取线程的时候要判断该线程还需不需要资源，即needTime是否为0。

③至于状态还有一点很重要的是要即使转换。当进行下一个操作要即使转换上一个线程的状态和下一个线程的状态防止状态混淆。

轮转法

①轮转法强调先进先出的拉链式顺序，而不以其他的权值作为开始/调度的先后顺序，所以普通先进先出的普通队列是解决该算法的最好方法。

②轮转法和优先权法不一样的是优先权法每次只进一个线程只执行一次。而轮转法是进一个可以执行最多是该线程可轮转的次数/轮转值（可能在中间就完成线程的释放），所以在写程序的时候每次都要判断是否已经轮转。并且到最后还要判断还是否需要调度。如果需要，再抛入队尾。
5.运行情况
①优先权算法：





②轮转法：


6.实验体会
通过本次实验，我深刻的理解了操作系统中线程资源的分配方式和进程的调度方式。操作系统实验重在理解每一个算法的意图和目的，那么就选择适当的数据结构模拟过程就可以完成相关算法了。

本次实验采用python完成，IDE是pycharm，python的queue库文件很好的支持了我在优先权算法中对队列的相关操作，python的operator库文件，很好的提供了基于类的属性按值排序的功能，这些在算法的编写过程中否起到了很大的作用。
【附】实验代码
import operator
import random
import queue

Q = queue.Queue()  # 定义队列

class PCB:
    def __init__(self, id, status, weight, needTime, rotelTimes):
        self.id = id  # 进程的id
        self.status = status  # 进程状态
        self.weight = weight  # 进程状态优先权重
        self.needTime = needTime  # 进程需要的时间片
        self.rotelTimes = rotelTimes    # 轮转次数


def emptyQueue(Q):  # 辅助函数-清空队列
    while not Q.empty():
        Q.get()


def priority():  # 优先权算法
    emptyQueue(Q)
    weight = operator.attrgetter('weight')
    arr_pcb.sort(key=weight, reverse=True)  # 按照状态优先权重的值降序排列
    for index,item in enumerate(arr_pcb):
        if item.needTime > 0:
            Q.put(item)  # 压入队列
        if index>0:
            if item.status!='finish':
                item.status='ready'
    node = Q.get()
    node.needTime -= 1
    node.weight -= 3

    if node.needTime>0:
        node.status='running'
    elif node.needTime==0:
        node.status = 'finish'

    print('**********时间片到达**********')
    for i in arr_pcb:
        print(i.id, i.status, i.weight, i.needTime)

def rotel():
    for a,item in enumerate(arr_pcb):
        if item.needTime>0:
            item.status='running'
            for b,item2 in enumerate(arr_pcb):
                if a!=b :
                    if item2.status=='running':
                        item2.status = 'ready'
            for j in range(0,item.rotelTimes):
                if item.needTime > 0:
                    item.needTime-=1
                    if item.needTime==0:
                        item.status='finish'
                    print('**********开始轮转**********')
                    for i in arr_pcb:
                        print(i.id, i.status, i.rotelTimes, i.needTime)


N = int(input('请输入需要创建的进程数目（4-8个）：'))

arr_pcb = []
for i in range(0, N):
    status = random.randint(1, 10)  # 随机生成状态优先权重
    needTime = random.randint(1, 4)  # 随机生成需要的时间片
    rotelTimes = random.randint(1, 3)  # 轮转次数
    arr_pcb.append(PCB(i, 'ready', status, needTime, rotelTimes))  # 创建进程

key = input('是否采用优先权？Y/N')
if key == 'Y':
    print('**********进程初始化**********')
    for i in arr_pcb:
        print('进程:', i.id, i.status, '状态优先权重：', i.weight, '需要时间片数：', i.needTime)
    priority()
    while not Q.empty():
        priority()
elif key =='N':
    print('**********进程初始化**********')
    for i in arr_pcb:
        print('进程:', i.id, i.status, '轮转次数：', i.rotelTimes, '需要时间片数：', i.needTime)

    flag=0

    for item in arr_pcb:
        if item.needTime>0:
            flag=1
    while flag:
        rotel()