在操作系统中，如果一个新的进程就绪的时候的优先级比正在运行的进程的优先级更高，那么就会发生抢占，通过抢占，打断正在执行的进程，让高优先级的进程得到机会运行。

# 抢占图示
对于早期的linux内核，默认是不开启抢占模式，当一个进程高优先级进程需要运行的时候，必须等到当前正在运行的较低优先级的进程运行完毕后才能运行，在这里，等待低优先级进程的时间也会算在高优先级进程的响应时间中去。这对一些具有实时性要求的业务来说是不可接受的。（排队的时间为什么要算成自己运行的时间）

![image.png](/static/img/3da47ddd686cae4003d35d6ea130ba4f.image.webp)

现代的linux版本内核默认都是开启抢占的，也就意味着，一个高优先级进程进来的时候，系统会在预设的抢占点上，尽可能的让高优先级任务得到运行，这样就最小化了高优先级任务的排队时间，从而提高了高优先级进程的响应能力

![image.png](/static/img/e71f1003f06c1af3a71aeb521b1ffecd.image.webp)

从整体的运行视角上来看，假设正在运行的任务是A，高优先级任务是B，那么状态就是B抢占了A，如下

![image.png](/static/img/bc4a9f0f753c9206d6f6fbe9d0777181.image.webp)

# 何时抢占
操作系统的操作并不是代表着高优先级任务B就绪就立马发生的抢占行为，而是正在运行的任务A主动提供了被抢占时机。通俗的说法是任务A让出(yield)了cpu。在linux中，实际上是置为了`TIF_NEED_RESCHED`标志
## tick
操作系统在调度器分配给自己的时间片运行完毕之后，主动由定时器检查并调用`scheduler_tick`函数，然后调用`task_tick`，`entity_tick`。`entity_tick`会调用`check_preempt_tick`来触发抢占，简单代码流程如下
```
update_process_times
  scheduler_tick
    task_tick
      task_tick_fair
        entity_tick
          update_curr
            curr->vruntime += calc_delta_fair(delta_exec, curr);
          check_preempt_tick
            resched_curr
              set_tsk_need_resched
                set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
```
我们关注`check_preempt_tick`函数
```
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
        ideal_runtime = sched_slice(cfs_rq, curr);
        delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
        if (delta_exec > ideal_runtime) {
                resched_curr(rq_of(cfs_rq));
                return;
        }
        delta = curr->vruntime - se->vruntime;
        if (delta > ideal_runtime)
                resched_curr(rq_of(cfs_rq));
}
```
检查vruntime是不是超过granularity太久，发生抢占
## wake up
新唤醒的进程优先级高于正在运行的进程时，通过`wake_up_new_task`/`wake_up_process`/`wake_up_state`三类接口来唤醒正在运行的任务让它触发抢占。代码流程如下
```
wake_up_new_task--->check_preempt_curr--->resched_curr
wake_up_process
wake_up_state
  try_to_wake_up
    ttwu_queue
      ttwu_do_activate
        ttwu_do_wakeup
          check_preempt_curr
            resched_curr
```
我们关注`check_preempt_curr`函数
```
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
        if (unlikely(task_has_idle_policy(curr)) &&
            likely(!task_has_idle_policy(p)))
                goto preempt;
preempt:
        resched_curr(rq);
}
```
如果处于idle则发生抢占
## 其他场景
上面已经是大部分场景了，还有负载均衡，进程优先级修改，中断，系统调用等时机都是调度的时机，这里就不一一举例了。代码很容易查到
# preempt_count 
当抢占发生的时候，`preempt_count`会自加，同时解除抢占的时候`preempt_count`自减。`preempt_count`维持平衡，同时也是调试抢占的关键变量
```
#define preempt_count_add(val)  __preempt_count_add(val)
#define preempt_count_sub(val)  __preempt_count_sub(val)
#define preempt_count_dec_and_test() __preempt_count_dec_and_test()
#endif

#define __preempt_count_inc() __preempt_count_add(1)
#define __preempt_count_dec() __preempt_count_sub(1)

#define preempt_count_inc() preempt_count_add(1)
#define preempt_count_dec() preempt_count_sub(1)

#ifdef CONFIG_PREEMPT_COUNT

#define preempt_disable() \
do { \
        preempt_count_inc(); \
        barrier(); \
} while (0)

#define sched_preempt_enable_no_resched() \
do { \
        barrier(); \
        preempt_count_dec(); \
} while (0)

#define preempt_enable_no_resched() sched_preempt_enable_no_resched()

#define preemptible()   (preempt_count() == 0 && !irqs_disabled())

#ifdef CONFIG_PREEMPTION
#define preempt_enable() \
do { \
        barrier(); \
        if (unlikely(preempt_count_dec_and_test())) \
                __preempt_schedule(); \
} while (0)

#define preempt_enable_notrace() \
do { \
        barrier(); \
        if (unlikely(__preempt_count_dec_and_test())) \
                __preempt_schedule_notrace(); \
} while (0)

#define preempt_check_resched() \
do { \
        if (should_resched(0)) \
                __preempt_schedule(); \
} while (0)
```
在这里`preempt_disable`和`preempt_enable`经常和spinlock搭配，这样可以使得每次spinlock结束的时候，也是一次调度时机
# 执行抢占
执行抢占就是调用schedule函数，下面列出来几个时机
## syscall
系统调用完成之后，主动调用schedule，代码流程如下
```
syscall_exit_to_user_mode
  exit_to_user_mode_prepare
    exit_to_user_mode_loop
      schedule()
```
## 中断结束
中断结束也会主动调用schedule(
```
irqentry_exit
  irqentry_exit_cond_resched
    preempt_schedule_irq
      __schedule(True)
```
## 等待队列
```
wait_event
  __wait_event
    ___wait_event
       schedule()
```
## 其他
其他常见都是少见常见了，可以通过代码找出来，这里就不一一介绍了。


Linux抢占简介

RCU是一种基于无锁的设计， 对于多个读者来说，几乎可以等效为无锁情况，特别适合于像文件系统目录查询，DNS resolution这样的场景。   
使用RCU的场景必须要满足如下两点
* 频繁的读取，很少的写入
* 对资源的数据没有强一致性要求

# 原理介绍
RCU管理的成员通常是一个内核的list或link-list。主要原理如下
## 删除
当对RCU的一个list的成员进行删除，这个删除不是立即删除，而是先标记为释放，等所有的读端执行所有读请求之后，再统一进行实际删除操作。 在这里，RCU将一个删除操作开始，到删除操作真的完成中间耗费的实际叫做宽限期(grace period)

![image.png](/static/img/bd4a469ac5069f69df1db3b47ad92ba4.image.webp)

## 插入
当对RCU的一个list的成员进行插入的时候，RCU需要保证任何时候对这个list的读取是完整的，非中间态的。也就是其他的读端，要么是未插入的状态，要么是已插入的状态，绝不能是中间状态

![image.png](/static/img/07a6e117525cdaf8020b413806305b75.image.webp)

## 完整性
任何时候对list的操作，无论是删除还是插入，RCU都需要保证任何时候的读端对list的遍历都是正常的，不会出现断链问题。不过同插入一样，rcu不保证一定能够读到新增的元素，或不读到要被删除的元素。

# 宽限期

![image.png](/static/img/7f7d6aaac01a5d1fcae171433d4345ba.image.webp)

顾名思义，只要任务在宽限期做的任何事情，都相当于有免死金牌，中间发生的错误可以忽略。对于RCU而言，具体表达的意思就是在宽限期内的list的成员，读到旧值也是没有问题的。

换个角度，如果等待宽限期过了之后，一切需要按照原本预期发生。   
所以在linux中，`synchronize_rcu()`执行的这段时间就是宽限期。

所以使用RCU的范式如下：

![image.png](/static/img/70c2e4a73357806737c87e39f3e724d6.image.webp)

对于读端，引用一个指针,触发rcu read
```
   rcu_read_lock();
   p = rcu_dereference(gptr);
   if (p) {
      printk(KERN_INFO "Reader: val = %d\n", p->val);
   }
   rcu_read_unlock();   
```
对于写端
```
   old = rcu_dereference_protected(gptr, lockdep_is_held(&some_lock)); 
   rcu_assign_pointer(gptr, new);
   if (old) {
        synchronize_rcu();
        kfree(old);
    }
```
关于rcu使用的实际图示如下

![image.png](/static/img/baa80a2880bdd8f3c53976ab23078231.image.webp)

当写线程要将指针 p 从指向 data1 改为指向 data2 时，需考虑读线程可能仍在使用 data1。因此，写线程会先“发布”新数据（即更新指针），然后进入等待期，直到所有读线程都退出当前的 RCU 临界区。

在此期间，不同读线程可能看到不同版本的数据：有的仍看到旧的 data1（记为 p1），有的已看到新的 data2（记为 p2）。只有当所有读线程都完成本次临界区访问后，才能确保它们全部看到 data2，此时 data1 才可安全释放。

# 删除操作
在linux中，通过`list_del_rcu`删除了一个元素，那么它整个周期的步骤如下   
1. 初始状态

假设想要删除节点5,6,7的位置

![image.png](/static/img/491a371aeb35d9c85b3158e65447f2b2.image.webp)

2. 伪删除操作

为了满足RCU宽限期的要求，所有的读端可能读到两个版本，一个是删除前的版本，一个是删除后的版本，代码发生在list_del_rcu后 synchronize_rcu 前，如下

![image.png](/static/img/2c0e53700254708293503704af2c4115.image.webp)

3. 宽限期后

到宽限期后，读端只能看到一个版本，这样代码可以安全的删除节点5,6,7的位置，此时代码在 synchronize_rcu 后


![image.png](/static/img/607f969368dbc2de25e15c5a0150e320.image.webp)

# 插入操作
在linux中，通过`list_replace_rcu`替换了一个元素，那么它整个周期的步骤如下   
1. 初始状态

假设想要替换节点5,6,7的位置

![image.png](/static/img/2e113654f29059a978a9ffdf50405767.image.webp)

2. 伪更新

此时q元素携带值5，2，3想要替换p元素的5，6，7。伪更新操作会让代码在宽限期内看到两个版本，一个是123，567,1148。另一个是123,525,1148。对应代码为 list_replace_rcu 后， synchronize_rcu 前

![image.png](/static/img/a97b386bd10443289b23d32320ed1425.image.webp)

3. 宽限期后

等待宽限期完成之后，整个视角都变成一个唯一的版本，元素5，6，7可以被安全的删除了。此时代码在 执行synchronize_rcu 之后。 

![image.png](/static/img/5e6b9fc8f555abddf2655869805ac743.image.webp)

# 总结
本文简单介绍了rcu，在用户层面上为了支持高性能的开发，可以使用用户态的rcu库，例如liburcu。

rcu在内核中设计的知识比较庞大，这里只是简单将基础知识介绍一下。详细的可以参考 《深入理解RCU》 的系列文章

# 参考
> https://gitee.com/xiebaoyou/documents/blob/master/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3RCU.zip








RCU同步简介

在linux系统中，默认可以通过创建进程和线程运行程序，而在内核中，被调度的实体单位是进程(task)，而线程是只是创建的时候没有独立的分配地址空间。但无论如何，进程和线程是被调度的最小单元。  
假设我们要设计一个极高性能的软件程序，能不能通过一些软件的技巧，尽可能少的创建线程或者进程，从而可以减少系统调度器的调度负载，同时如果一个任务不经过系统的上下文切换，自然其整体性能是高于线程和进程的。   
在C语言中，可以通过自己实现协程来做到这一点，协程在操作系统层面上是看不到的，它只能看到进程和线程，但是在代码层面，他是“多任务并发”的。本文简单介绍一下协程
# 无栈协程
开源软件putty就使用了无栈协程，它是基于goto的特性实现，switch case就是一种goto的体现。详细可以如下了解
> https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

以一个例子说明
```
#define crBegin static int state=0; switch(state) { case 0:
#define crReturn(i,x) do { state=i; return x; case i:; } while (0)
#define crFinish }
int main(void) {
    static int i;
    crBegin;
    for (i = 0; i < 10; i++)
        crReturn(1, i);
    crFinish;
}
```
此函数通过宏展开其实就是简单的0，9的循环体，如下
```
# gcc test.c -E -o test.E
int main(void) {
    static int i;
    static int state=0; switch(state) { case 0:;
    for (i = 0; i < 10; i++)
        do { state=1; return i; case 1:; } while (0);
    };
}
```
接下来事情就简单了，如果实现一个yield函数，此函数在switch里面如果能够动态的修改case的值，那么它就好像是多线程一样运行，yield的实现如下
```
#define cr_yield                 \
    {                            \
        __s = __LINE__;          \
        usleep(THREAD_INTERVAL); \
        return;                  \
    case __LINE__:;              \
    }
```
那么这句yield的语义就是将当前任务让出，由其他协程来继续运行。同操作系统调度的yield语义一致。   
下面提供一个完整的无栈协程的例子
```
#include <stdio.h>
#include <unistd.h>

#define THREAD_INTERVAL 1000 * 500
#define cr_start()      \
    static int __s = 0; \
    switch (__s) {      \
    case 0:

#define cr_yield                 \
    {                            \
        __s = __LINE__;          \
        usleep(THREAD_INTERVAL); \
        return;                  \
    case __LINE__:;              \
    }
#define cr_end() \
    }            \
    __s = 0;

static int condition = 1;

static void coroutine_1() {
    cr_start();

    for (;;) {
        /* do something */
        printf("Run %s\n", __FUNCTION__);
        cr_yield;
    }

    cr_end();
}

static void coroutine_2() {
    cr_start();

    for (;;) {
        if (condition) {
            /* do something conditional */
            printf("Run %s - Action(1)\n", __FUNCTION__);
            cr_yield;
        }

        /* do something */
        printf("Run %s - Action(2)\n", __FUNCTION__);
        condition = !condition;
        cr_yield;
    }

    cr_end();
}

int main() {
    for (;;) {
        coroutine_1();
        coroutine_2();
    }
    return 0;
}
```
编译并运行，日志如下
```
Run coroutine_1
Run coroutine_2 - Action(1)
Run coroutine_1
Run coroutine_2 - Action(2)
Run coroutine_1
Run coroutine_2 - Action(2)
Run coroutine_1
Run coroutine_2 - Action(1)
Run coroutine_1
Run coroutine_2 - Action(2)
Run coroutine_1
Run coroutine_2 - Action(2)
```
可以看到，通过switch和case以及__LINE的动态更新，让代码好像是两个线程在运行一样。但实际上，此段代码是在一个线程内顺序执行的。  
论文 Protothreads 实现了更成熟的无栈协程。下面基于通过例子演示一下基于Protothreads的co-routine
首先需要Protothreads实现的头文件，如下
提供lc-switch.h文件
```
#ifndef LC_SWITCH_H_
#define LC_SWITCH_H_

/** \hideinitializer */
typedef unsigned short lc_t;

#define LC_INIT(s) s = 0;

#define LC_RESUME(s) switch(s) { case 0:

#define LC_SET(s) s = __LINE__; case __LINE__:

#define LC_END(s) }

#endif /* LC_SWITCH_H_ */

/** @} */
```
提供lc.h文件
```
#ifndef LC_H_
#define LC_H_

#ifdef LC_CONF_INCLUDE
#include LC_CONF_INCLUDE
#else /* LC_CONF_INCLUDE */
#include "lc-switch.h"
#endif /* LC_CONF_INCLUDE */

#endif /* LC_H_ */

/** @} */
/** @} */
```
提供pt.h文件
```
#ifndef PT_H_
#define PT_H_

#include "lc.h"

struct pt {
  lc_t lc;
};

#define PT_WAITING 0
#define PT_YIELDED 1
#define PT_EXITED  2
#define PT_ENDED   3

#define PT_INIT(pt)   LC_INIT((pt)->lc)

#define PT_THREAD(name_args) char name_args

#define PT_BEGIN(pt) { char PT_YIELD_FLAG = 1; if (PT_YIELD_FLAG) {;} LC_RESUME((pt)->lc)

#define PT_END(pt) LC_END((pt)->lc); PT_YIELD_FLAG = 0; \
                   PT_INIT(pt); return PT_ENDED; }

#define PT_WAIT_UNTIL(pt, condition)            \
  do {                                          \
    LC_SET((pt)->lc);                           \
    if(!(condition)) {                          \
      return PT_WAITING;                        \
    }                                           \
  } while(0)

#define PT_WAIT_WHILE(pt, cond)  PT_WAIT_UNTIL((pt), !(cond))

#define PT_WAIT_THREAD(pt, thread) PT_WAIT_WHILE((pt), PT_SCHEDULE(thread))

#define PT_SPAWN(pt, child, thread)             \
  do {                                          \
    PT_INIT((child));                           \
    PT_WAIT_THREAD((pt), (thread));             \
  } while(0)

#define PT_RESTART(pt)                          \
  do {                                          \
    PT_INIT(pt);                                \
    return PT_WAITING;                  \
  } while(0)

#define PT_EXIT(pt)                             \
  do {                                          \
    PT_INIT(pt);                                \
    return PT_EXITED;                   \
  } while(0)

/** @} */

#define PT_SCHEDULE(f) ((f) < PT_EXITED)

/** @} */

#define PT_YIELD(pt)                            \
  do {                                          \
    PT_YIELD_FLAG = 0;                          \
    LC_SET((pt)->lc);                           \
    if(PT_YIELD_FLAG == 0) {                    \
      return PT_YIELDED;                        \
    }                                           \
  } while(0)

#define PT_YIELD_UNTIL(pt, cond)                \
  do {                                          \
    PT_YIELD_FLAG = 0;                          \
    LC_SET((pt)->lc);                           \
    if((PT_YIELD_FLAG == 0) || !(cond)) {       \
      return PT_YIELDED;                        \
    }                                           \
  } while(0)

/** @} */

#endif /* PT_H_ */

/**
 * @}
 * @}
 */
```
上面是全部Protothreads的实现了，下面编写测试程序
```
#include <stdio.h>
#include "pt.h"

static struct pt co_pt;

static int coroutine(struct pt *pt) {
    PT_BEGIN(pt);
    printf("[%s]: Start\n", __func__);
    PT_YIELD(pt);
    printf("[%s]: After yield\n", __func__);
    PT_END(pt);
}

int main() {
    PT_INIT(&co_pt);
    coroutine(&co_pt);
    coroutine(&co_pt);
    return 0;
}
```
编译运行日志如下
```
tf@tf:# ./test
[coroutine]: Start
[coroutine]: After yield
```
到这里，无栈协程完全说清楚了。
# 有栈协程
无栈协程的特点是简单，但是正因为没有栈的实现，所以局部变量无法保持。同时，有栈协程的体验会更像线程，对于无栈协程，错误的开发可能导致内存泄漏无法察觉。而开辟栈区的协程，可以清晰的管理这些事情。  

开源的有栈协程库为 neco 。下面基于此简单说明一下
```
git clone https://github.com/tidwall/neco.git
```
根据仓库的README.md的指示，测试程序如下
```
#include <stdio.h>
#include "neco.h"

void ticker(int argc, void *argv[]) {
    while (1) {
        neco_sleep(NECO_SECOND);
        printf("tick\n");
    }
}

void tocker(int argc, void *argv[]) {
    while (1) {
        neco_sleep(NECO_SECOND*2);
        printf("tock\n");
    }
}

int neco_main(int argc, char *argv[]) {
    neco_start(ticker, 0);
    neco_start(tocker, 0);

    // Keep the program alive for an hour.
    neco_sleep(NECO_HOUR);
    return 0;
}
```
编译运行后，日志如下
```
tf@tf:# ./test
tick
tock
tick
tick
tock
tick
tick
tock
tick
```
# 总结
本文简单介绍了C语言的协程，协程对于高性能应用开发来说必不可少。



C语言协程

早期的操作系统只需要关心CPU的调度策略，从而提高通用程序的运行效率，但是随着NPU和其他ASIC的普及，每个SOC下都支持了多个NPU和ASIC芯片。面对这样芯片的设计趋势，操作系统调度变得至关重要。调度不再只关心CPU内部，而是需要对所有资源进行有效调度。本文先简单讨论XPU调度的几个关注点
# XPU调度的必要性
在没有XPU调度的环境下，其资源需要长期待命，一方面功耗无法降低，另一方面性能无法完全利用。
## 功耗问题
假设CPU下发一个需要CPU，DSP，GPU，NPU同时运行的任务，当CPU开始运行任务的时候，需要同时将DSP，GPU，NPU都上去启动到就绪状态，等待CPU将任务下发给不同的执行单元。这种情况下，假设SOC环境具备两个DSP单元，那么两个DSP单元都会同时启动，那么整个SOC环境下的功耗一直是以最大运行状态运行。    
那么是不是可以让CPU在使用DSP的时候，尽可能调度在同一个DSP上，这样可以让另一个空闲的DSP得到关闭，降低功耗

## 性能问题
假设CPU下发多个需要CPU，DSP，GPU，NPU同时运行的任务，当CPU开始运行多个任务的时候，因为在DSP/GPU/NPU的视角是谁来就运行谁的任务处于一种无序状态，所以无法有效的将DSP，GPU，NPU的利用率提升到100%。

# XPU调度测量指标
为了有效的开发和设计XPU调度策略，需要统一的从如下几个维度进行分析和决策，如下
## 利用率
XPU完成任务的工作量。利用率根据管理的计算任务的数量和性质而变化。通过利用率可以看到设备的运行时间，空闲时间。 而调度策略的目的是降低设备的空闲时间。如果可降低的空闲时间为100%，那么将节省一个设备的核心
## 吞吐量
它是指每单位时间内完成的进程数量。通过有效地优先级排序和调度进程来提高吞吐量，从而在给定的时间范围内完成更多的任务。   
假设XPU的利用率是100%，但是无序争用和有序的编排不同的是，有序的编排可以让某一段时间内的XPU吞吐量很高（因为运行短任务），同时让某一段时间内的吞吐量降低（此时可以通过降低设备频率获取功耗收益）
## 周转时间
这指从进程开始到完成所经过的时间。周转时间是总等待时间，它包括进程在CPU，DSP,NPU,GPU，以及内存，IO，和调度算法内等待的总时间。   
一方面，调度策略内应该保证所有任务在就绪队列中等待的时间都得到减少   
另一方面，良好的调度策略可以降低单进程维度下的任务等待时间，从而满足具备实时特征的任务能够长期的保证其响应效果
## 等待时间
在周转时间内已经提到，一个进程在就绪队列中花费的总时间称为等待时间。因此，调度算法决定了进程在获得XPU设备资源前的所有停留时间的长短
## 响应时间
它是提交请求和收到第一个响应之间的时间。调度策略确保高优先级进程能够及时获得XPU设备资源，有助于减少响应时间并提升整体用户体验。

# 常规调度策略
如果仅从调度本身来看，其实XPU的调度策略和通用CPU的调度策略是相通的。因为都是按照一定的指标选出最合适的任务。只不过CPU的调度面向的资源设备是CPU本身，而XPU的调度面向的资源设备是加入调度管理的多种多样的设备。   
目前市场上XPU的调度策略都比较简单，本文先从简单调度策略说起

## FCFS
FCFS（先来先服务）算法根据进程就绪顺序，即基于任务的到达时间

## SJF
SJF（最短作业优先）算法根据进程的预算时间分配资源，也就是说，运行时间短的进程会先获得访问权

## PRIO
SP（静态优先级）算法根据特定的数值表示更高的或更低的优先级，高优先级的进程会比低优先级的进程更早获得设备访问权   
注意，一些系统上的设计，可能Priority越高，优先级越高，但是另一些系统上，可能Priority越低，优先级越高。为什么会有后者呢？主要还是因为红黑树的原因，红黑树找最小值的效率最高。所以设计系统时出现了常人认为的反直觉，也就是Priority越低，优先级越高。对红黑树兴趣的可以查看我其他文章《rb-tree实现》系列

## RR
RR（轮转调度）算法根据时间片周期的运行任务，这使得所有进入就绪的任务都能周期性的得到运行，体现了调度的公平性

## 弊端
* FCFS 会遭受“车队效应”的困扰，队列前面的长进程会延迟短进程。
* SJF 的缺点是无法高效处理动态负载。优先级调度可能导致饥饿，如果高优先级进程持续到达，会阻止低优先级进程执行。
* 轮转调度（RR）具有高上下文切换开销，可能对长进程导致性能不佳。
* 基于优先级的算法可能会忽视低优先级进程，造成不公平。

# 下一代XPU调度策略
根据上面可以看到，常规调度目前已经应用在各种XPU的中间件上，首先，他们是单独维护和服务于某一类型的设备，例如GPU，那么对应就是GPU驱动，例如NPU，那么就对于cuda库（以nvidia为例）。   
这里再提供一些新的调度策略可用于XPU上。
## 自适应调度策略
常规的自适应调度策略例如动态优先级，动态时间片，基于负载均衡的调度都属于自适应调度策略。
这种调度策略会动态的修改任务的整体优先级排序情况，从而让任务更具备公平性，不被饿死。

在NPU领域，Shockwave也提出了基于市场调控的调度策略。也属于自适应调度策略的一种。

## 实时调度策略
实时调度算法在通常应用在具备强实时环境中，例如硬实时操作系统中调度策略，或者确保具有严格时间约束的中间件，例如常规的速率单调调度（RMS）、最早截止日期优先（EDF）和截止日期单调调度（DMS）。

在XPU的调度中，我们更关心的是任务的实时性，可以牺牲不具备实时要求的任务的响应效果。

# 抢占
对于XPU环境下的调度策略，抢占是维系任务实时系的重要功能，抢占分两种
* 调度器抢占
* 用户抢占

调度器抢占很好理解，例如实时调度算法EDF根据deadline来实施对任务的抢占，RR调度在时间片完成后，默认的轮转可以任务是抢占点

而用户抢占指的是提供了用户的接口，让用户执行任务前决定是否可以抢占设备。通过用户主动实施的任务抢占，可以让设备被抢占后保存上下文，从而运行下一个任务。

不过抢占都是具备开销的，过多的抢占会给系统带来很强的调度器负载，例如低时间片下的RR调度算法。过少的抢占又会影响XPU调度的实时效果。这里面要从实际情况中获取经验值。反哺到XPU调度算法的设计中去。

# 总结
随着AI的逐步普及，目前的SOC设计都会带有NPU核心，同时带有多个DSP单元和其他的ASIC设计。这些设计不再像以前一样，只要用起来就行。我们需要关注整体实时性响应，性能效果，和功耗输出。所以将SOC中以这种XPU维度的调度策略越来越重要。 









异构(XPU)计算中的任务调度

使用vscode来进行服务器ssh连接在win10上会出现权限问题，需要几条命令设置一下。
# 报错
```
[13:14:15.845] > Bad permissions. Try removing permissions for user: \\Everyone (S-1-1-0) on file C:/Users/Administrator/.ssh/config.
> Bad owner or permissions on C:\\Users\\Administrator/.ssh/config
> 过程试图写入的管道不存在。
> ]0;C:\WINDOWS\System32\cmd.exe
[13:14:15.845] Got some output, clearing connection timeout
[13:14:17.122] "install" terminal command done
[13:14:17.122] Install terminal quit with output: ]0;C:\WINDOWS\System32\cmd.exe
[13:14:17.122] Received install output: ]0;C:\WINDOWS\System32\cmd.exe
[13:14:17.123] Failed to parse remote port from server output
[13:14:17.124] Resolver error: Error: 
	at g.Create (c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:499181)
	at t.handleInstallOutput (c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:496503)
	at t.tryInstall (c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:620043)
	at async c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:579901
	at async t.withShowDetailsEvent (c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:583207)
	at async k (c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:576866)
	at async t.resolve (c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:580578)
	at async c:\Users\Administrator\.vscode-insiders\extensions\ms-vscode-remote.remote-ssh-0.111.2024040515\out\extension.js:2:846696
[13:14:17.126] ------
```
# 解决方案
直接命令解决即可
```
icacls "C:\Users\Administrator\.ssh\config" /remove "Everyone"
icacls "C:\Users\Administrator\.ssh\config" /inheritance:r
icacls "C:\Users\Administrator\.ssh\config" /grant "Everyone:R"
```
为windows下的config文件移除everyone用户的权限，并禁用权限继承后，并设置everyone的读权限
