Skip to content

Latest commit

 

History

History
176 lines (113 loc) · 10.5 KB

process.md

File metadata and controls

176 lines (113 loc) · 10.5 KB

进程调度

协作式调度在实际应用中存在一些问题，如进程无限循环、进程死锁等情况(系统不信任用户)，因此抢占式调度更为常见和广泛使用

静态调度算法（Static Scheduling）是在进程开始执行之前就确定了进程的调度顺序。这种算法主要基于进程的固定属性，如优先级、任务类型等，来进行进程的调度。常见的静态调度算法包括先来先服务（First-Come, First-Served）、最短作业优先

除了 Event-driven Scheduling 其余调度算法都是抢占式调度

tokio/goroutinue 协程调度以抢占式为主，但是也支持 yield 这样协作式调度 API

现在多核处理器基本是对称多处理机(核心数是二的倍数，多核之间有共享的三级缓存)

量化调度算法性能

  • CPU 使用率: CPU busy 状态的时间百分比
  • 吞吐量: 单位时间内完成的 task
  • 能耗(嵌入式场景): 根据进程能耗调整时间片大小和优先级?

从用户角度关心的是: 周转时间(进程执行时间)、等待时间、响应时间

异构调度、多机调度

FCFS 先来先服务

优点: 实现简单，缺点: 如果前面长执行时间的任务陷入 IO 等待，则 CPU 利用率极低

Shortest Process Next 短进程优先

从就绪进程队列中拿一个执行时间最短的执行，缺点: 难以准确预估任务执行时间，对长时间作业不公平会饥饿

算法的变种是 SRN 短剩余时间优先

最高响应优先比算法

短进程优先的改进，关注进程等待时间，避免进程无限等待饥饿

Round-Robin 时间片轮转

如果时间片过小，上下文切换过于频繁，如果时间片过大，就退化成先来线服务算法

多级反馈队列调度算法

根据进程的优先级和历史执行情况将其放入不同的队列，并根据队列优先级调度进程。如果进程在过去一段时间是I/O密集型特征，就调高进程的优先级；如果进程在过去一段时间是CPU密集型特征，就降低进程的优先级

不同就绪队列可以用不同的调度算法，例如前台 UI 交互进程用一些低延迟的调度算法

比例份额调度(彩票)

时间片过后每个进程进行彩票抽奖，优先级越高的越容易中奖获得调度

实时操作系统调度之速率单调算法

每20ms运行一次（每秒要执行50次）的进程的优先级为50，必须每50ms运行一次（每秒20次）的进程的优先级为20

多核调度的问题

单队列多处理机调度(SQMS)缺乏可扩展性、缓存亲和性差。如何提高缓存利用率，尽量让同一个任务在同一个处理器运行，类似于分布式一致性哈希，任务 id 对处理器核心总数取模，保证例如 id=1 就一定会调度在处理器核心 1 上面执行

另一个解决思路是每个处理器一个队列(有点像 tokio 工作窃取法)，但是任务不断在不同处理器切换导致 cache 利用率低，要是某些任务能 pin to core 固定在某个核心执行就好

公平调度算法

Completely Fair Scheduler

动态调整时间片长度，红黑树存储就绪队列，根据优先级调整时间片的长度

Linux 默认进程调度算法，属于多处理机调度，缺点是

  1. CFS 频繁切换上下文开销大
  2. 不适用于实时操作系统
  3. 没有考虑 IO 密集型应用，应用有大量 IO 操作会导致 CPU 利用效率降低(所以就引入了协程来解决?)
  4. 低优先级任务等待时间太久，长尾延迟现象
Linux 2.3版本引入了一种称为O(1)时间复杂度调度算法的进程调度器。这是一种基于优先级数组和时间片轮转的算法，它在任何给定时间都可以在常数时间内选择下一个要运行的进程。它的目标是提高调度器的效率，并更好地支持多处理器系统。
O(1) 而且还需要硬件指令支持

然而，随着时间的推移，随着计算机系统的发展和演进，O(1)调度算法逐渐暴露出一些问题。其中一个主要问题是，当系统负载增加时，O(1)调度算法的性能会下降。这是因为它通过遍历整个优先级数组来选择下一个进程，而数组的大小是固定的。因此，在高负载情况下，调度器需要更多的时间来选择下一个进程，从而导致调度延迟的增加。

为了解决这个问题，Linux在2.6版本中引入了完全公平调度器

Brain Fuck 调度算法

Round-Robin 的变种，适合手机个人电脑进程少需要低延迟的，国内有大厂尝试将手机操作系统调度器改成 BFS 达到更好性能

/sys/kernel/debug/sched/debug /proc/sched_debug

抢占式调度 tokio 工作窃取法

线程池中没活干的线程，窃取全局队列或者其他线程等待中的任务，提高 CPU 利用率和负载均衡

空闲线程如果过于频繁检查其他队列，就会带来性能开销；如果检查间隔过长，又会带来负载不均衡

task_struct 的 状态

线程实际上是一种特殊的进程(一个轻量级进程背后有一个内核线程)，它们共享相同的地址空间和其他进程资源。因此，内核中对线程和进程的表示方式是一致的

  • 进程状态: Terminated,Running,Sleeping,stopped,zombie
  • 线程状态: Terminated,Running,Blocked,Runnable,Suspended

更细粒度来说来说，进程挂起状态下还有一种更细的状态是进程缺页等待数据从外存置换过来

不要去背诵进程状态啦，建立一个索引/印象，在源码的 include/linux/sched.h struct task_struct 部分的 state 字段就是所有状态

/* Used in tsk->state: */
#define TASK_RUNNING			0x0000
#define TASK_INTERRUPTIBLE		0x0001
// 为什么会有不可中断的状态——正在做原子操作例如释放锁的过程中就是不可中断
#define TASK_UNINTERRUPTIBLE		0x0002
#define __TASK_STOPPED			0x0004
#define __TASK_TRACED			0x0008
/* Used in tsk->exit_state: */
#define EXIT_DEAD			0x0010
#define EXIT_ZOMBIE			0x0020
#define EXIT_TRACE			(EXIT_ZOMBIE | EXIT_DEAD)
/* Used in tsk->state again: */
#define TASK_PARKED			0x0040
#define TASK_DEAD			0x0080
#define TASK_WAKEKILL			0x0100
#define TASK_WAKING			0x0200
#define TASK_NOLOAD			0x0400
#define TASK_NEW			0x0800
#define TASK_STATE_MAX			0x1000

线程是为了提高进程并发能力，进程的多个线程共用地址空间(.data 等, 环境变量和入参在栈上)和资源(fd 等)

线程的三种实现方法: 用户线程、内核线程、轻量级线程(Linux)，Linux 一个进程的多个线程(轻量级线程)共用一个内核线程

临界区

临界区指的是访问资源需要互斥执行的代码

三种实现: 禁用中断 irq(没有中断没有上下文切换也就没有并发)、软件方法、原子操作指令

DBus 图形界面进程间通信

有 session/system bus 区分，类似于消息队列，但是扩展了 rpc 等功能，gnome/kde 属于 session bus

类比 ipcs 看消息队列，dbus 可用 dbus-monitor 或者 QtDbusViewer 工具查看

为什么广泛应用于图形界面通信，为什么 freedesktop 要造一个消息队列轮子

早期 IPC 机制不方便用于图形化，dbus 建立在 socket 抽象之上

意味着可以像 X display server 一样跨机器通信

通过 policy 设置消息队列安全机制和访问权限

Binder 安卓进程间通信

类似 grpc 用 .proto, binder 用 .aidl 文件定义 rpc 接口。Zygote 进程是 Android 操作系统中的一个特殊进程，它在系统启动时被创建，并负责孵化（fork）其他应用进程

Peterson 算法

int turn 表示谁进入了临界区、boolean flag[] 表示准备好进入临界区的进程

进入时 while(flag[pid] && turn == pid); 退出时 flag[pid]=false

但是不适用于多线程，多线程安全的修改 turn 需要很复杂的代码多层判断，缺点是 busy-wait 且需要大量状态变量实现复杂

环境变量共享 每个线程都有自己的栈帧，但是它们共享相同的栈空间。因此，所有线程都可以通过相同的栈空间来访问环境变量和命令行参数。

需要注意的是，如果一个线程修改了环境变量或命令行参数的值，那么其他线程也能看到这些修改。因此，在多线程编程中，对于共享的环境变量和命令行参数的访问，需要进行相应的同步措施，以避免数据竞争或不一致的结果

Hoare管程和Mesa管程相比，条件变量的释放之后需要重新检查条件。这个说法正确吗

Hoare管程在条件变量的释放之后，不需要重新检查条件。相反，Mesa管程需要在条件变量的释放之后重新检查条件，以防止虚假唤醒（spurious wake-up）的发生

在Hoare管程中，当一个线程调用条件变量的释放操作后，它将会放弃对该条件变量的控制权，并唤醒等待在该条件变量上的其他线程。被唤醒的线程会立即尝试重新获取对条件变量的控制权，并检查条件是否满足。如果条件满足，等待线程会继续执行。如果条件不满足，等待线程会再次等待条件变量被释放。

相比之下，在Mesa管程中，当一个线程调用条件变量的释放操作后，它将继续执行，并不释放对条件变量的控制权。其他等待线程被唤醒后，会竞争获取对条件变量的控制权。如果获得了对条件变量的控制权，等待线程会重新检查条件是否满足。如果条件满足，等待线程会继续执行。如果条件不满足，等待线程会继续等待。

EAS调度器和CFS调度器相比，更适应采用Big.Little架构的处理器。这个说法正确吗

是的，这个说法是正确的。EAS（Energy-Aware Scheduler）调度器是为了更好地支持Big.Little架构的处理器而引入的。在Big.Little架构中，处理器会结合高性能的"big"核心和低功耗的"little"核心，以实现平衡性能和能效的目标。CFS（Completely Fair Scheduler）调度器是Linux内核默认的调度器，它主要关注公平性和响应性。然而，CFS调度器对于Big.Little架构可能存在一些问题，因为它没有考虑到处理器核心之间的差异和能耗。EAS调度器在CFS调度器的基础上进行了扩展，通过考虑处理器核心的能效特性和任务的能耗需求，优化了调度策略，使得Big.Little架构的处理器能够更加高效地利用其性能和能耗优势。因此，EAS调度器更适应采用Big.Little架构的处理器。

x86 访问某个段的时候，一般要求 DPL(Descriptor Privilege Level) <= max(CPL,RPL), C=current,R=request