精华内容
下载资源
问答
  • /*不可抢占式动态优先级*/ /*若正在运行的进程时间片用完就转为就绪状态,占用一次cpu优先级-1 就绪队列中等待的队列,每等待cpu运行完一个时间片,优先级+1*/ // 枚举进程的状态:就绪、执行、阻塞、...
    #include<stdio.h>
    #include<iostream>
    #include<iomanip>
    using namespace std;
    /*不可抢占式动态优先级*/
    /*若正在运行的进程时间片用完就转为就绪状态,占用一次cpu优先级-1
    就绪队列中等待的队列,每等待cpu运行完一个时间片,优先级+1*/
    
    // 枚举进程的状态:就绪、执行、阻塞、完成
    enum STATE { Ready, Run, Block, Finish };
    struct PCB
    {
        string name;
        int time;//运行需要时间
        int rtime;//还需要运行多长时间才能完成
        int priority;//优先数
        PCB *next;//指向一下个PCB
        STATE   state;//状态(就绪、执行、阻塞、完成)
    };
    PCB *finish,*ready,*run,*tail;//完成,就绪,运行队列
    int num;//实际进程总数,小于10
    int timeslice;//时间片
    
    void input();//输入
    void init();//初始化参数
    void output();//输出
    void insert(PCB *p);//根据优先级将进程插入有序单向链表队列
    void in();//从就绪队列选择队首进程运行
    void running();//进程调度
    
    int main()
    {
        input();
        init();
        output();
        running();
        return 0;
    }
    
    void input()//输入
    {
        ready=NULL;
        finish=NULL;
        run=NULL;
        PCB *p;
        cout<<"请输入进程个数:";
        cin>>num;
        cout<<endl;
        cout<<"请输入时间片大小: ";
        cin>>timeslice;
        cout<<endl;
        for(int i=0;i<num;i++)
        {
            p=new PCB;
            cout<<"请输入进程"<<i+1<<"的信息"<<endl;
            cout<<"名字:";
            cin>>p->name;
            cout<<endl;
            cout<<"运行时间: ";
            cin>>p->time;
            cout<<endl;
            cout<<"优先数: ";
            cin>>p->priority;
            cout<<endl;
            p->next=NULL;//初始化新建进程的下一个都为NULL
          //  cout<<p->name<<" input finish, next is insert"<<endl;
            /*
            if(ready==NULL)
            {
                p->next=ready;
                ready=p;
            }
            else
                */
                insert(p);
        }
    }
    void init()//初始化参数
    {
        PCB *p=ready;
        for(int i=0;i<num;i++)
        {
           //p->wtime=0;
           p->rtime=p->time;
           p->state=Ready;
           p=p->next;
        }
    /*
        tail=ready;
        p=tail->next;
        while(p!=NULL)
        {
           tail=tail->next;
           p=tail->next;
        }
    */
    }
    
    void output()//输出
    {
        PCB *temp=ready;
        cout<<"进程名 "<<"运行时间 "<<"优先数 "<<"剩余时间 "<<"状态 "<<endl;
    
        cout<<"ready队列"<<endl;
        while(temp!=NULL)
        {
            cout<<temp->name<<setw(7)<<temp->time<<setw(9)<<temp->priority
            <<setw(7)<<temp->rtime<<setw(9)<<temp->state<<endl;
            temp=temp->next;
        }
    
     //   if(temp==NULL)
     //       cout<<"运行完成!"<<endl;
    /*
        temp=run;
        cout<<"runing队列"<<endl;
        while(temp!=NULL)
        {
            cout<<temp->name<<setw(5)<<temp->time<<setw(7)<<temp->priority
            <<setw(5)<<temp->rtime<<setw(7)<<temp->state<<endl;
            temp=temp->next;
        }
    */
        temp=finish;
        cout<<"finish队列"<<endl;
        while(temp!=NULL)
        {
            cout<<temp->name<<setw(7)<<temp->time<<setw(9)<<temp->priority
            <<setw(7)<<temp->rtime<<setw(9)<<temp->state<<endl;
            temp=temp->next;
        }
    }
    
    void insert(PCB *p) /* 建立对进程进行优先级排列函数*/
    {
        p->state=Ready;
    	PCB *first, *second;
    	int flag = 0;
    	if((ready==NULL)||((p->priority)>(ready->priority))) /*优先级最大者,插入队首*/
    	{
    		p->next=ready;//插入的数据作为链表头结点
    		ready=p;//头结点指针指向插入数
    	}
    
    	else /* 进程比较优先级,插入适当的位置中*/
        {
    		first = ready;
    		second = first->next;
    		while (second != NULL)
    		{
    			if ((p->priority) > (second->priority)) /*若插入进程比当前进程优先数大,*/
    			{ /*插入到当前进程前面*/
    				p->next = second;
    				first->next = p;
    				second = NULL;
    				flag = 1;
                    break;
    			}
    			else /* 插入进程优先数最低,则插入到队尾*/
    			{
    				first = first->next;
    				second = first->next;
    			}
    		}
    		if (flag == 0)
            {
                first->next=p;
               // p->next=NULL;
            }
    	}
    }
    
    
    void in()//从就绪队列选择队首进程运行
    {
        if(ready==NULL)
        {
            run=NULL;
            return;
        }
        run=ready;
        run->state=Run;
        cout<<"running: "<<run->name<<endl;
        cout<<run->name<<setw(7)<<run->time<<setw(9)<<run->priority
        <<setw(7)<<run->rtime<<setw(9)<<run->state<<endl;
        ready=ready->next;
        run->next=NULL;
    }
    void running()//进程调度
    {
        PCB *temp=ready;
        in();
        while(run!=NULL)
        {
            temp=ready;
            if(run->rtime<=timeslice)
            {
                run->rtime=0;
                run->state=Finish;
                run->next=finish;
                finish=run;
                run=NULL;
            }
            else
            {
                //如果超过规定时间片,则此进程优先级-1,回到就绪队列,就绪队列中其他进程优先级+1
               run->rtime=(run->rtime)-timeslice;
               run->priority=(run->priority)-1;
               while(temp!=NULL)
               {
                   temp->priority++;
                   temp=temp->next;
               }
               insert(run);
              // tail->next=run;
              // tail=tail->next;
              // sort();
            }
            output();
            in();
        }
    }
    
    
    展开全文
  • 即不同类型的负载对应不同的优先级,同时允许集群中的所有负载所需的资源总量超过集群提供的资源,在这种情况下,当发生资源不足的情况时,系统可以选择释 放一些重要的负载(优先级最低的),保障最重要的负载...

    引入


    对于运行各种负载(如Service、Job)的中等规模或者大规模的集 群来说,出于各种原因,我们需要尽可能提高集群的资源利用率。而提 高资源利用率的常规做法是采用优先级方案,即不同类型的负载对应不同的优先级,同时允许集群中的所有负载所需的资源总量超过集群可提供的资源,在这种情况下,当发生资源不足的情况时,系统可以选择释 放一些不重要的负载(优先级最低的),保障最重要的负载能够获取足够的资源稳定运行

    优先级抢占调度策略的核心行为分别是

    • 驱逐 (Eviction):kubelet进程的行为
    • 抢占 (Preemption):Scheduler执行的行为

    驱逐
    即当一个Node发生资源不足(under resource pressure)的情况时,该节点上的kubelet进程会执行驱逐动作,此时 Kubelet会综合考虑Pod的优先级资源申请量与实际使用量等信息来计 算哪些Pod需要被驱逐;当同样优先级的Pod需要被驱逐时,实际使用的 资源量超过申请量最大倍数的高耗能Pod会被首先驱逐。对于QoS等级 为“Best Effort”的Pod来说,由于没有定义资源申请(CPU/Memory Request),所以它们实际使用的资源可能非常大

    抢占
    当一个新的Pod因为资源无法满足而不能被调度 时,Scheduler可能(有权决定)选择驱逐部分低优先级的Pod实例来满 足此Pod的调度目标,这就是Preemption机制

    Pod优先级调度示例如下
    首先,由集群管理员创建PriorityClasses,PriorityClass不属于任何 命名空间:

    apiVersion: scheduling.k8s.io/v1beta1
    kind:  PriorityClass
    metadata: 
      name:
      labels:
        version: v1
    value: 10000
    globalDefault: false
    description: "miao shu xing yu ju"
    

    上述YAML文件定义了一个名为high-priority的优先级类别,优先级
    为100000,数字越大,优先级越高,超过一亿的数字被系统保留,用于 指派给系统组件

    我们可以在任意Pod中引用上述Pod优先级类别:

    apiVersion: v1
    kind: Pod
    metadata:
      labels:
        test: nginx
      name: nginx
    spec:
      containers:
      - name: nginx
        image: nginx
        ports:
        - name: http
          containerPort: 80
      tolerations:
      - key: version
        operator: Exists  
        effect: NoSchedule    
      priorityClassName: high
    

    根据描述可以看到优先级
    在这里插入图片描述

    展开全文
  • 在这种情况下,当发生资源不足的情况时,系统可以选择释放一些重要的负载(优先级最低的),保障最重要的负载能够获取足够的资源稳定运行。 Kubernetes 1.8版本引入了基于Pod优先级抢占(Pod Priority Preemption...

    对于运行各种负载(如Service、Job)的中等规模或者大规模的集群来说,出于各种原因,我们需要尽可能提高集群的资源利用率。
    提高资源利用率的常规做法是采用优先级方案。
    即不同类型的负载对应不同的优先级,同时允许集群中的所有负载所需的资源总量超过集群可提供的资源。
    在这种情况下,当发生资源不足的情况时,系统可以选择释放一些不重要的负载(优先级最低的),保障最重要的负载能够获取足够的资源稳定运行。
    Kubernetes 1.8版本引入了基于Pod优先级抢占(Pod Priority Preemption)的调度策略。
    此时Kubernetes会尝试释放目标节点上低优先级的Pod,以腾出空间(资源)安置高优先级的Pod,这种调度方式被称为“抢占式调度”。
    如何声明一个负载相对其他负载“更重要”?我们可以通过以下几个维度来定义:

    1. Priority,优先级;
    2. QoS,服务质量等级;
    3. 系统定义的其他度量指标。

    优先级抢占调度策略的核心行为分别是驱逐(Eviction)与抢占(Preemption),这两种行为的使用场景不同,效果相同。

    Eviction是kubelet进程的行为,即当一个Node发生资源不足(under resource pressure)的情况时,该节点上的kubelet进程会执行驱逐动作,此时Kubelet会综合考虑Pod的优先级、资源申请量与实际使用量等信息来计算哪些Pod需要被驱逐。
    当同样优先级的Pod需要被驱逐时,实际使用的资源量超过申请量最大倍数的高耗能Pod会被首先驱逐。
    对于QoS等级为“Best Effort”的Pod来说,由于没有定义资源申请(CPU/Memory Request),所以它们实际使用的资源可能非常大。

    Preemption则是Scheduler执行的行为,当一个新的Pod因为资源无法满足而不能被调度时,Scheduler可能(有权决定)选择驱逐部分低优先级的Pod实例来满足此Pod的调度目标,这就是Preemption机制。

    需要注意的是,Schedule可能会驱逐Node A上的一个Pod来满足Node B上的一个新Pod的调度任务。
    比如下面的这个例子:一个低优先级的Pod A在Node A(属于机架R)上运行,此时有一个高优先级的Pod B等待调度,目标节点是同属机架R的Node B,他们中的一个或全部都定义了anti-affinity规则,不允许在同一个机架上运行,此时Scheduler只好“丢车保帅”,驱逐低优先级的Pod A以满足高优先级的Pod B的调度。

    Pod优先级调度实例如下。

    首先,由集群管理员创建PriorityClasses,PriorityClass不属于任何命名空间:

    [root@bogon ~]# vim high-priority.yaml 
    
    apiVersion: scheduling.k8s.io/v1beta1
    kind: PriorityClass
    metadata:
      name: high-priority
    value: 100000
    globalDefault: false
    description: "This priority class should be used for xyz service pods only"
    
    
    [root@bogon ~]# kubectl create -f high-priority.yaml 
    priorityclass.scheduling.k8s.io/high-priority created
    
    
    [root@bogon ~]# kubectl get priorityclass
    NAME                      VALUE        GLOBAL-DEFAULT   AGE
    high-priority             100000       false            3m
    
    

    上述YAML文件定义了一个名为high-priority的优先级类别,优先级为100000,数字越大,优先级越高,超过一亿的数字被系统保留,用于指派给系统组件。
    我们可以在任意Pod中引用上述Pod优先级类别:

    [root@bogon ~]# vim priority-nginx.yaml 
    
    apiVersion: v1
    kind: Pod
    metadata:
      name: nginx
      labels:
        env: test
    spec:
      containers:
      - name: nginx
        image: nginx
        imagePullPolicy: IfNotPresent
      priorityClassName: high-priority
    

    抢占

    如果高优先级pod无法调度成功处于pending状态就会触发抢占。
    高优先级Pod就可能抢占节点N,并将其低优先级Pod驱逐出节点N,高优先级Pod的status信息中的nominatedNodeName字段会记录目标节点N的名称。
    需要注意,高优先级Pod仍然无法保证最终被调度到节点N上,在节点N上低优先级Pod被驱逐的过程中,如果有新的节点满足高优先级Pod的需求,就会把它调度到新的Node上。
    而如果在等待低优先级的Pod退出的过程中,又出现了优先级更高的Pod,调度器将会调度这个更高优先级的Pod到节点N上,并重新调度之前等待的高优先级Pod。

    优先级抢占的调度方式可能会导致调度陷入“死循环”状态。
    当Kubernetes集群配置了多个调度器(Scheduler)时,这一行为可能就会发生,比如下面这个例子:
    Scheduler A为了调度一个(批)Pod,特地驱逐了一些Pod,因此在集群中有了空余的空间可以用来调度,此时Scheduler B恰好抢在Scheduler A之前调度了一个新的Pod,消耗了相应的资源,因此,当Scheduler A清理完资源后正式发起Pod的调度时,却发现资源不足,被目标节点的kubelet进程拒绝了调度请求!这种情况的确无解.
    因此最好的做法是让多个Scheduler相互协作来共同实现一个目标

    最后要指出一点:使用优先级抢占的调度策略可能会导致某些Pod永远无法被成功调度。
    优先级调度不但增加了系统的复杂性,还可能带来额外不稳定的因素。
    一旦发生资源紧张的局面,首先要考虑的是集群扩容,如果无法扩容,则再考虑有监管的优先级调度特性,比如结合基于Namespace的资源配额限制来约束任意优先级抢占行为。

    展开全文
  • 采用非抢占式最高优先级调度算法,当**就绪队列**中某进程的最高优先级高于正在**处理器**中运行的进程的最高优先级时,并会让正在运行的进程退出处理器,而是将高优先数的排在就绪队列的首部。而采用抢占式最高...
    最高优先级调度算法原则上总是调度就绪队列中优先级最高的那个进程。非抢占式和抢占式进程调度都属于最高优先级进程调度。
    采用非抢占式最高优先级调度算法,当**就绪队列**中某进程的最高优先级高于正在**处理器**中运行的进程的最高优先级时,并不会让正在运行的进程退出处理器,而是将高优先数的排在就绪队列的首部。而采用抢占式最高优先级进程调度算法,则高优先数的进程会抢占**处理器**,让**正在处理**的**进程**处于**就绪队列**。
    此外,低级调度和高级调度区别也要明确。
    
    展开全文
  • 调度优先级反转问题

    2019-03-10 22:27:58
    对于rtos 必须要保证优先级顺序执行,这种反转问题导致不可控。 A&gt;B&gt;C 三个调度实体 A优先级最高, C已经优先访问竞争资源。A runing 之后挂起等待C运行结束。B这时候runing 抢占竞争资源。 假如这...
  • java虚拟机采用抢占调度模型,是指优先让运行池中优先级高的线程占用CPU,如果运行池中的线程优先级相同,那么就随机选择一个线程,使其占用CPU。处于运行状态的线程会一直运行,直至它不得放弃CPU。
  • 研究多次抢占式资源受限的项目调度问题,假设任意时间点作为资源抢占节点且抢占次数受限制,建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法(GA)局部搜索能力缺陷,在...
  • 目前市面流行的实时操作系统都是采用可抢占式的基于优先级调度方式,其保证了处于就绪状态的优先级高的任务可以先于优先级低的任务而执行。但这并是绝对的,优先级反转是实时系统中的一个经典特例。其大体流程...
  • 1 调度 Windows不是实时操作系统,它是抢占式多线程操作系统。在如果全部优先级同样的情况下,CPU对线程的调度原则是每隔20m就会切换到... 系统仅仅调用能够调度的线程,事实上系统的大部分线程都是处于不可调度的...
  • 优先级反转

    2019-04-07 20:43:27
    实时操作系统中,在信号量使用过程中,则可能出现优先级反转的合理情况。...当系统高优先级任务正在等待信号量(此信号量被一个低优先级任务持有)时,一个介于高和低之间的中等优先级任务进入执行态,将抢占C...
  • 1. 优先权调度算法 为了照顾紧迫型进程获得优先处理,引入了优先权调度算法。它从就绪队列中选择一个优先权最高的进程,让其获得处理器并执行。...它常用于批处理系统中,也用于某些对时间要求
  • 从linux的调度策略来讲,当一... idle是优先级最低的进程,可以想象在任何情况下都能被别的进程immediately抢占,而实际上,通过ftrace可以看到idle在运行的时候一直是关抢占的(preempt-depth为零),也就是说只有i...
  • 该算法在增加硬件代价的前提条件下通过调度增加了系统的可用性,缩短了任务的平均等待时间,同时该算法抢占式的任务进行有效调度。仿真实验结果表明,该算法有效实现了异构系统可用性和任务等待时间之间的折中...
  • 1、windows是抢占式多线程操作系统    系统可以在任何时刻停止一个线程而另行调度另一个线程。  我们无法保证线程总在运行,线程会获得整个处理器,系统将允许运行其他线程。  系统...
  • 然而,Hadoop的一个缺点是不可预测性。Hadoop不能确保企业的关键任务按时完成,也不能完全发挥集群的性能。YARN(一种新的Hadoop资源管理器)能够实现任务抢占,为队列中的其它任务腾出调度空间。容量调度器与公平...
  • 初始化完成之后,会检查是否有挂起标志,有的话线程就暂停状态,没有则递减暂停计数为0,此时如果线程没有等待其他事情,就处于可调度的状态 除了CREATE_SUSPENDED标志外,还可以使用SuspendThread 暂停线程...
  • 嵌入式之:任务调度

    2014-09-15 11:21:00
    任务调度有三种方式:不可抢占调度、可抢占式调度、时间片轮转调度 1.不可抢占调度: 一个任务一旦获得CPU就独占CPU运行,除非由于某种原因,它决定放弃CPU的使用权。 2.可抢占式调度: 对于有优先级的...
  • 优先让运行池中处于就绪态的线程中优先级高的占用CPU,如果运行池中线程的优先级相同,那么就随机选择一个线程,使其占用CPU,处于运行状态的线程会一直执行,直至它不得放弃CPU,一个线程会因为以下原因放弃...
  • rt-thread线程调度器源码分析

    千次阅读 2013-02-17 18:03:43
    RT-Thread中提供的线程调度器是基于全抢占式优先级调度,在系统中除了中断处理函数、调度器上锁部分的代码和禁止中断的代码是不可抢占的之外,系统的其他部分都是可以抢占的,包括线程调度器自身.系统总共支持256...
  • 抢占式SJF优先级操作系统 操作系统是任何电子小工具的软件和硬件部分之间的接口。 OS(操作系统)在调度中起着重要作用,将进程分配给CPU以执行功能。 最短作业优先算法减少执行时间,从而减少了首先执行的过程...
  • 线程调度

    2018-03-26 22:41:03
    什么是线程调度 ? 线程调度就是按照特定的机制为多个线程分配CPU使用权,有...它是指优先让运行池中优先级高的线程占用CPU,如果线程的优先级相同,就随机选择一个占用CPU。 注意:线程的调度不是跨平台的,它...
  • CPU调度算法

    2020-08-16 19:03:01
    最近在看操作系统,总结一下CPU的调度算法。...方式:顾名思义,按照进程就绪的先后顺序使用CPU,不可抢占 优点:公平,实现简单 缺点:长进程后面的短进程需要等待很长时间,不利于用户体验 改变调度
  • 2.不可抢占调度优先级任务在运行时,即使有高优先级任务就绪,也不能被抢占运行。 3.混合式调度 OSEK-OS可以实现两种调度方式并存,不但不会带来冲突,而且还能达到一些效果。 假设有三个任务 ...
  • 编写程序模拟进程调度过程,能够按照时间片轮转,短进程优先法,可抢占式和不可抢占优先级法,以及先来先服务和高响应比优先法处理输入的数据,运行结果包含界面。
  • 进程调度算法

    2015-08-09 13:22:48
    这是一种不可抢占方式的调度算法,优点是实现简单,缺点是后来的进程等待CPU的时间较长。它现今主要用作辅助调度法;例如结合在优先级调度算法中使用,当有两个最高优先级的进程时,则谁先来,谁就先被调度。   ...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 129
精华内容 51
关键字:

不可抢占优先级调度