进程组织

Linux内核里面的内核结构：Linux采用链表结构

---

补充前置知识：

C语言中，任何变量的地址数字，是开辟众多字节中，地址数据最小的那个！

struct A
{
    int a;
    int b;
    int c;
    double d;
}

我只知道结构体中C成员的地址，怎么知道所在结构体变量的其它地址呢？

&((struct A*)0->c)
//是c变量在结构体中的偏移量

c语言提供了宏offsetof获得结构体内变量偏移量

https://legacy.cplusplus.com/reference/cstddef/offsetof/

因此可以使用变量地址 - 偏移量 = 结构体地址获得结构体地址

---

重新设计双链表

struct link
{
    struct link* next;
    struct link* prev;
}
struct task_struct
{
    //进程的属性
    struct link node;
    //...
}

因此，这个结构体中的链表，next与prev指向的也是下一个结构体中node的地址，而不是结构体的地址！

但是我们可以利用上面补充的前置知识获取task_struct的地址

为什么要这么设计？

增加链式管理的扩展性！

代码只需要维护一份即可

举头插链表为例

insert_head(head, struct link*);
struct task_struct *t = new XXX;
insert_head(head, &(t->node));

在OS角度，怎么做的优点是什么？

1. Linux内核会将所有的进程task_struct统一放在一张双链表中

2. 进程不是也有运行队列吗？阻塞队列吗？为什么一个节点既在队列里又在链表里？

struct task_struct
{
    //...
    struct list_head tasks;
    //...
    struct list_head run;
}

一个结构体里可以有多个链式结构，这样tasks队列交给OS管理，run队列用于给cpu调度队列

甚至如果有更多的数据结构，也可以通过这种方式，让一个进程同时属于多个数据结构！

这就是内核设计数据结构的思路

---

Linux2.6内核进程调度队列

时间复杂度为O(1)

每一个CPU都有一个调度队列：

struct runqueue
{
    //...
    struct task_struct queue[140];
    //...
};

其中，queue[140]可以理解为

struct task_struct* queue[140]

这是一个140块空间的队列，其中

• 普通优先级：100~139（我们都是普通的优先级，想想nice值的取值范围，可与之对应！）

• 实时优先级：0~99（不关心）

其中，100_{139这40个位置就是我们前面讲优先级的60}99的40个位置

• 结论1：优先级数字本质是数组下标！

• 结论2：则优先级相同的进程在同一个队列中（这140个位置的每一个位置都是一个队列），优先级相同则遵循FIFO原则进行调度！

  那么，根据优先级选择进程的时候，本质是一个hash的过程

• 结论3：一旦确认是哪个队列，剩下的就是FIFO

---

可是每次想要找到一个不为空的队列，最多需要遍历40次

我们可以使用位图——每一个比特位对应一个下标，0表示空队列，1表示非空队列！

为什么使用位图？

因为位图的检测效率更高，比直接检测效率更高。

如果运行队列里一个进程都没有呢？

使用一个变量nr_active记录进程的总数

struct prio_array_t
{
    nr_active//进程数
    bitmap[5]//位图
    queue[140]//运行队列
}

在多种优化下，查找效率完全逼近O(1)！

---

问题：所有教程优先级都是61，但是不断地有60的教程来，那么61的教程是否无法被调度？

进程饥饿问题！

分时操作系统，会以较为公平的方式选择进程，在一段时间内让所有进程都能得到CPU资源！

因此调度算法没有上面说的这么简单。

---

在runqueue中有两个队列，一个活跃队列，一个过期队列（不代表进程执行完了）

使用两个指针指向这两个队列，*active指针指向活跃队列，*expired指针指向过期队列

当一个进程在一个时间片结束时，无论有没有执行完成，都会被放入过期队列中

那么活跃队列中的pcb会越来越少，过期队列越来越多

当活跃队列为空之后，直接swap(&active, &expired)交换两个指针的内容

成功完成了将过期队列改为活跃队列

---

新进程加入应当先放到过期队列，等待下一轮执行

---

回到上面的问题：所有教程优先级都是61，但是不断地有60的教程来，那么61的教程是否无法被调度？

就是按照上面的两个队列互相切换的方式，那么在每一轮中，所有的进程都会得到调度，不会出现进程饥饿问题！

优先级高只决定该进程在当前轮中的先后！

---

以上就是Linux O(1) 的调度算法！

该方法不存在饥饿问题！

---

Linux2.4之后的内核支持 抢占 —— 如果来了一个高优先级的进程，那么可能会立即把当前的进程剥离或进行其它操作

---

在运行队列的0~99位的进程为实时进程

实时进程相当于分时操作系统的一个子集

实时进程会将进程代码全部执行完后再进行下一个

因此，Linux系统既有分时操作系统也有实时操作系统！

但是目前基本都是用分时操作系统