初始Linux(7)：认识进程（下）

1. 进程优先级

    cpu 资源分配的先后顺序，就是指进程的优先权（ priority ）。

    优先权高的进程有优先执行权利。配置进程优先权对多任务环境的 linux 很有用，可以改善系统性能。

    还可以把进程运行到指定的CPU 上，这样一来，把不重要的进程安排到某个 CPU ，可以大大改善系统整体性能

根本原因：每种设备的可用资源（磁盘/显示器/键盘..........）相比进程的数量还是太少了

注意区分优先级和权限的概念，优先级是前与后的问题，权限是能不能的问题。

 1.1 ps -al（查看优先级）

可以用ps -al来查看优先级

PRI（priority）用来看优先级，NI即nice值，是对优先级的修正数据。

PRI是一种存在task_struct中的对优先级属性的描写，通过[60,99]共计40个数字来描写优先级。 

一般来说，各个进程竞争的都是CPU资源

NI：优先级的NICE数据，nice数据是一种优先级的修正数据。

使用者通过修改nice值来改变最终优先级。

优先级数字越小（排名越靠前），优先级越高

最终显示在PRI下面的最终优先级=pri(default)+nice。

 每次优先级的调整都是一次 重置

1.2 如何调整优先级

使用top指令，r一下进入以下界面，此时希望你输入一个你想改的PID值，假设我们想修改的是18957

输入后PID：

修改之后再查看：

NI只有[-20,19]的值，保证最终的PRI只会在[60,99]

每次通过ps -al展示的PRI和NI，都满足PRI-NI=原优先级

每次都是从原优先级开始变化。

 引进一个概念：UID

UID: 在ps -al时观察到的UID，即user id

类似于文件权限处的r u o等名字，用于记录是谁启动的该进程，一般来说1000是root，1001是第一个用户。

                               

   修改优先级是一种少见的操作，不建议多使用，OS自主安排的一般就是合理的优先顺序          OS本来的安排更能适合公平合理的安排进程           

2. 进程切换（基于分时操作系统的大背景）

        CPU上下⽂切换：其实际含义是任务切换, 或者CPU寄存器切换。当多任务内核决定运⾏另外的任务时, 它保存正在运⾏任务的当前状态, 也就是CPU寄存器中的全部内容。这些内容被保存在任务⾃⼰的堆栈中, ⼊栈⼯作完成后就把下⼀个将要运⾏的任务的当前状况从该任务的栈中重新装⼊CPU寄存器, 并开始下⼀个任务的运⾏, 这⼀过程就是context switch。

是什么 

       每次时间片到了，都需要保存上下文数据再离开（切换进程），回来的时候要恢复上下文数据

时间片到了100次，就要被保存/恢复数据一百次。

那么OS如何知道你的程序运行到哪里了呢？

cpu在运行时，会将很多临时数据放进寄存器里

计算机中的pc指针（point code）, 即eip，会进行这项工作：指向下一条指令的位置

我们先重点研究两种寄存器：eip和ir（下图表示CPU中除了EIP和IR,还有其他多种多样的寄存器）

以及对应的处理部分： 

                 

假设内存中加载进来一个进程，其中有描述他的PCB

CPU内部维护一个寄存器EIP，来记录接下来该怎么去执行

比如当前EIP告诉CPU该去处理code3，那么code3的代码就会被读到ir里去，ir寄存器再将数据拿给CPU，此时EIP就会更新成4。因此，IR保存的就是当前正在处理的代码。

                                                        

寄存器就是EIP，EIP里的数据就叫做上下文数据

为什么 

       如果不保留上下文数据，新切换的进程的运行数据就会进入寄存器，覆盖掉原来的上下文数据，所以每次切换时必须保留上下文数据。保留上下文数据不是目的，是手段，目的依然是恢复上下文数据，让CPU进行新一轮的处理。CPU内部随时都在高速保留，恢复上下文数据。也就是说，上述EIP和IR的过程是一直在持续发生的。注意：CPU读取的其实是汇编代码，以上的前提都是在汇编的基础上进行的，所有语言都会最后变成汇编语言。

怎么做

计算机如何保留上下文数据：

基于上文，我们知道进程切换的本质就是1.取指令到ir;2.更新EIP；3.从IR中拿指令来分析和处理

如果只有mov eax 10;mov ebx 20,ret三条指令，我们模拟一下这个过程。

根据上述的过程，假设我们已经到了即将执行ret的一步：此时进来一个要执行sub的task_struct2

如果不保护：

原来的task_struct的数据会被抹除，再次调度回来时只能从main开始执行，根本无法进行多进程的调度和切换。

但是真实的保存方法不仅是简单的放入PCB。

每次的临时数据一定都是保存在内存里的tss_struct中。（Task State Segment，任务状态段）

• 内核会为每个 CPU 分配一个 tss_struct 结构，并将其存储在内核分配的内存中。这些内存通常是从内核的动态内存分配器（如 slab 分配器）中分配的。

• 每个 CPU 的 TSS：在多核系统中，每个 CPU 核心都有自己的 tss_struct，并且存储在独立的内存区域中，以避免多核之间的冲突。

所以我们也可以说，task_struct中是存储了以下信息的： 

3. Linux下进程切换的调度算法

3.1 CPU的均衡负载

首先需要知道的是，接下来的讨论都是基于单核CPU；如果是多核CPU，就要考虑每一个CPU均衡负载的问题。其次，每个CPU上不会是FIFO算法，太蠢了,失去了算法的意义。

3.2 rqueue的大概结构

首先，每一个CPU都有一个自己的rqueue

    其中的active*(活跃进程)和expired*(过期进程)，分别指向下面的蓝色框和红色框。 

两个框中的结构是完全一样的，将他们封装成一个prio_arry_t的类型（每个类型是一个框），然后创建一个array[]数组，里面有两个元素，分别是红框和蓝框，active*和expired*就是prio_arry_t类型的指针。

每个prio_arry_t里面有一个queue[140]，存储的是task_struct*

前一百个是实时操作系统的位置，后40个是分时操作系统：

因此我们不考虑前100个位置，只研究后四十个位置。

3.3 本质是2个HashBucket

queue[140]中下标（应该是100-139）与哈希值（右边是PRI值,PRI就看作是此处的哈希值）：

这样，每次查询都是O(1)。

3.4 如何调度

CPU只会从active*指向的队列中去调度。

由此延伸出来的问题：

都是高优先级，那怎么均衡调度（如何调度优先级较低的进程）？——饥饿问题(比如你是一个89号，65号的刚刚调度完回到队列中，由于优先级高，又该调度他。除非65号的退出，否则永远轮不到这个89号的)，或者用户一直在添加高优先级的新进程，也无法调度低优先级进程（PRI越高优先级越低）

为了解决新建进程加剧饥饿问题的情况，新建的进程一般都不直接添加到active中，而是添加到expired，刚刚调度过的高优先级进程也不能放回active，而是直接放到expired中去（刚刚括号中的问题）。

因此：

                                

active是会为空的，当active为空的时候，操作系统只需要交换一下两个指针的内容。

这样，一个简单的时间窗口（即一次调度周期）能调度所有的进程

nr_active表示当前结构里有多少进程，用于判断是否等于0，等于0的时候就需要进行swap

                                                 

active指向原来的expired，而原来的expired全是进程，从此可以开始新一轮的调度。

3.5 位图优化

但是，目前为止的queue[140]（其中的后40位）还是需要我们遍历和维护的，全部遍历一遍任然有一丢丢的成本，因此采用了位图的设计来进一步优化

bitmap：

整形是32位的,32*5 = 160，每一个位置用1和0来表示是否有进程

                                 

这样，最多遍历五次，然后每次如果是0就可以直接跳过该32种优先级，如果不是0就进去，进去寻找每次也最多是32次，同时每当找到了有进程的哈希桶，对每个桶里的头删也是O(1)的算法

4. 进程在各种队列中的连接方式

之前提到过，进程连接都是通过队列链接。

不过之前学习到的链接方式太不优雅，可扩展性也很弱，我们建议使用下述新的方法。

每一个队列当中只放入向前和向后的指针。 

队列当中只链接一个struct link。

意义：

操作系统中有太多的队列需要进程进入，同一个进程，可能既需要放在整体管理队列中，又需要放到活跃队列中，如果单独封装一层link，就能很好的实现这一功能。这样的作法同样存在于STL中。

现在的问题是，怎么在遍历一种队列的时候，去访问当前被遍历的link结构体所对应的进程属性？

通过偏移量解决访问的问题：

复习两个概念：

栈的增长方向 与 结构体（或类）的增长方向是反的。

而对于结构体和类的存储：在大多数现代计算机系统中，结构体（struct）或类（class）中的数据成员通常是从低地址到高地址依次存储的。

假设我们知道了A结构体中C的地址，只需要通过(struct A*) (&C - 偏移量)，就能获得obj的指针。 

(先对C取地址，再减去c元素相对于结构体首元素的地址偏移量，获得首元素地址，再将该地址强转为struct A*，就能自由访问了。)

并且，此处的偏移量的单位是字节。

那么，如何获得该偏移量呢？

由前置知识，一个结构体中，数据是从低地址存向高地址的，假设起始地址是0

那么C的偏移量就是C地址的本身——数轴上大于0的数和零点的距离等于其数字大小本身。

将0强转为一个struct A结构体，然后访问其对应的c，再取地址，这就是偏移量。

结合刚刚的得到首元素的办法：

(struct A*) (&c - &((struct A*)0)->c)

那么，可以用一个宏函数来解决这个问题：

#define Who(type,x)  (struct type*)(&x - (&((struct type*)0) -> x))

补充：库中的offset宏

宏函数复习：