CPU管理

指令包括特权指令和非特权指令，特权指令涉及资源管理只能由操作系统执行
用户执行：保护中断

于是就涉及到了处理器状态，分为Ring0核心态和Ring3用户态

中断：遇到了紧急需要处理的事情，暂时终止当前执行的程序，转到相应的时间处理程序，然后最后返回到原进程或者是重新调度到其他进程

• 强迫性中断
• 自愿性质中断
• 硬中断
  • 外中断（异步中断）
  • 内中断（同步中断）
• 软中断
  • 信号
  • 软件中断

外中断：外部设备对CPU中断，执行中断处理程序的上半部分
异常：程序执行不正常，转向异常处理程序
软件中断：硬中断服务程序发出软件中断（下半部分）
信号：通知某个事件或者是迫使进程执行信号处理程序
发现中断源->保护现场->异常处理/中断处理->恢复程序

1.进程的堆栈 每个进程都有自己的堆栈，内核在创建一个新的进程时，在创建进程控制块task_struct的同时，也为进程创建自己堆栈。一个进程有2个堆栈，用户堆栈和系统堆栈；用户堆栈的空间指向用户地址空间，内核堆栈的空间指向内核地址空间。当进程在用户态运行时，CPU堆栈指针寄存器指向的 用户堆栈地址，使用用户堆栈；当进程运行在内核态时，CPU堆栈指针寄存器指向的是内核栈空间地址，使用的是内核栈。 2.进程用户栈和内核栈之间的切换 当进程由于中断或系统调用从用户态转换到内核态时，进程所使用的栈也要从用户栈切换到内核栈。系统调用实质就是通过指令产生中断，称为软中断。进程因为中断（软中断或硬件产生中断），使得CPU切换到特权工作模式，此时进程陷入内核态，进程进入内核态后，首先把用户态的堆栈地址保存在内核堆栈中，然后设置堆栈指针寄存器的地址为内核栈地址，这样就完成了用户栈向内核栈的切换。当进程从内核态切换到用户态时，最后把保存在内核栈中的用户栈地址恢复到CPU栈指针寄存器即可，这样就完成了内核栈向用户栈的切换。 3.进程上下文 进程切换现场称为进程上下文(context)，包含了一个进程所具有的全部信息，一般包括：进程控制块（Process Control Block，PCB）、有关程序段和相应的数据集。 进程控制块PCB（任务控制块） 进程控制块一般可以分为进程描述信息、进程控制信息，进程相关的资源信息和CPU现场保护机构。进程控制块是进程在内存中的静态存在方式，Linux内核中用task_struct表示一个进程（相当于进程的人事档案）。进程的静 态描述必须保证一个进程在获得CPU并重新进入运行态时，能够精确的接着上次运行的位置继续进行，相关的程序段，数据以及CPU现场信息必须保存。处理机 现场信息主要包括处理机内部寄存器和堆栈等基本数据。 进程的切换 当一个进程的时间片到时，进程需要让出CPU给其他进程运行，内核需要进行进程切换。 Linux 的进程切换是通过调用函数进程切换函数schedule来实现的。进程切换主要分为2个步骤：

• 调用switch_mm()函数进行进程页表的切换；
• 调用 switch_to() 函数进行 CPU寄存器切换；

中断的优先级
优先处理高优先级的，处理高优先级的时候屏蔽低优先级的中断请求，高优先级的中断处理可以打断低优先级的中断

延迟过程调用：DPC
异步过程调用：APC
DPCvs APC
–DPC队列是系统范围的，APC队列是线程范围的
–DPC优于任何一个线程函数，屏蔽线程调度
-APC特定于一个线程，在这个线程执行前

进程的状态

1. 三态：运行，就绪，等待
2. 五态：新键，就绪，运行，等待，终止
3. 挂起状态：多了挂起就绪，挂起等待

进程上下文：

• 运行环境
• 寄存器
• PSW
• 页表

进程切换：涉及到上下文的切换，会导致修改PCB
CPU模式切换：不一定切换上下文，不涉及PCB的修改

操作系统的调度层次

• 高级调度：多道批处理系统，选择作业进入主存。分时系统通常不需要
• 中级调度：外存与内存中的进程对换。提高主存的利用率
• 低级调度：就绪到运行的调度

调度算法的原则

• CPU利用率：CPU利用率=CPU有效工作时间/CPU总的运行时间。CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间
• 响应时间：从提交请求到接受到相应的事件间隔（实时系统和分时系统的重要指标）
• 周转时间：批处理用户从提交作业到系统开始到作业完成为止的事件间隔成为作业周转事件（批处理系统）、

完成时间-提交时间=周转时间
平均就是累加然后求平均
权重=周转时间/运行时间
带权周转时间就是权重的平均值

选择作业进入（作业调度），然后对应创建进程，然后进入进程调度，最后作业调度

低级调度功能

1. 调度
2. 分配

低级调度有抢占式和非抢占式的

调度算法
FCFS：先来先服务
SJF：最短作业优先算法，预估计算时间，非抢占式
SRTF：最短剩余时间优先算法，SJF改为抢占式
HRRF：相应比=1+已经等待/估计运行，运行最大的相应比进程
静态优先数
动态优先数
时间片轮转调度算法
多级反馈队列：设置多个优先级的队列，高优先级的队列分配的时间片比较短
彩票调度算法，随机的发出彩票，需要多时间的可以多拿几张

实时调度算法
就是一个单位时间里时间发生的次数，然后乘上时间，也就是执行的时间，之和应该是要小于1的

单比率调度算法
–为每个进程分配一个与事件发生频率成正比的优先数
–调度优先数最高的就绪进程
–采取抢占式分配策略

限期调度算法
就绪队列按截止期限排序
采取抢占式分配策略

最少裕度法
裕度=截止时间-(就绪时间+计算时间)
选择裕度最少的进程执行

多处理器调度算法
负载共享调度算法

1. 维护一个全局就绪队列，有CPU空闲了就选择一个执行
2. 避免空闲CPU。
3. 就绪队列需要互斥
4. 高速缓存失效，通信变的复杂

群调度算法
把一组关系比较密切的算法放在一起调度（问题就是关联性难以判断）
专用处理器调度算法
一个进程的一组线程放在一组CPU上一直运行到结束（但是阻塞进程不会让出CPU）
动态调度算法
允许抢占CPU

Linux2.4的调度算法
OTHER：普通任务，非实时进程的调度，基于优先级的时间片轮询
FIFP：先进先出的实时类任务：实时进程，没有时间片的概念
RR：轮转法实时任务，实时抢占进程，时间片

进程切换时机：
时间片用完了，更高优先级的进程被唤醒
自己放弃了，Sleep
执行了处于等待的系统调用

Linux2.6
更好的支持SMP
每一个CPU都有一个运行队列：不需要互斥了
SCHED_NORMAL非实时进程
SCHED_FIFO 实时进程，采用先进先出的调度算法；
SCHED_RR 实时进程，采用轮转法
rt_priority-实时进程的优先级
0~99
不做动态优先级的改变
数值越大优先级越低
static_prio-非实时进程静态优先级
由nice转变而来： static_prio=MAX_RT_PRIO+20-nice
100-139的优先级范围

sleep_avg-进程平均等待时间
体现进程的交互程度，或者说进程需要运行的紧迫程度
该值越大，进程的优先级就越高
睡眠增加，运行减小

prio-进程动态优先级
-5~5的奖惩
主要由sleep_avg决定
创建时子进程继承父进程的动态优先级
prio_array_t *array-进程优先级数组
nr_active:数组中的进程数
Bitmap:优先级位图
Queue:优先级队列
每个可运行队列维持两个优先级数组：活跃数组和过期数组

实时进程具有静态优先级，范围为0到99
非实时任务都有静态优先级对应于100到139的优先级范围，默认值为120
进程的动态优先级，它以nice值为基数，再加上-5到+5之间的进程交互性奖励或罚分
SCHED_NORMAL调度时间片用完，进程移入过期队列
SCHED_RR调度时间片用完后，进程返回原优先级队列，不会移到过期队列
计算算法是O（1）的解决，一个是使用了位图不用遍历整个队列，第二是使用了过期数组，过期数组里是时间片用完的进程，这个进程在进入到过期队列里已经计算了优先级，不需要用O（n）的整个重新计算

负载均衡：执行调度的时候当前队列空或者是计时器调用
基本步骤
找到最繁忙的运行队列
从中选择一个优先级数组（过期数组）
找到非空的其优先级最高的链表
选择一个未运行、可移动、不在高速缓存中的进程，移到当前可运行队列
重复以上步骤直至负载均衡

线程调度
线程调度出现在DPC/dispatch中断优先级
触发事件：
一个新的线程进入就绪态
当前运行线程时间配额用完
当前运行线程阻塞
当前运行线程通过系统调用或者被系统本身改变优先级
当前运行线程改变其亲和处理器集合

线程被调度运行时，可运行一个被称为时间配额（quantum）的时间。
时间配额是允许线程连续运行的最大时间长度，随后系统会中断线程运行，判断是否需要降低该线程的优先级，查找是否有其他高优先级或相同优先级的线程等待运行。
由于抢先式调度特征，一个线程的一次调度执行可能并没有用完它的时间配额就被抢先