目录补充前置知识重新设计双链表为什么要这么设计在OS角度怎么做的优点是什么Linux2.6内核进程调度队列进程组织Linux内核里面的内核结构Linux采用链表结构补充前置知识C语言中任何变量的地址数字是开辟众多字节中地址数据最小的那个structA{inta;intb;intc;doubled;}我只知道结构体中C成员的地址怎么知道所在结构体变量的其它地址呢((structA*)0-c)//是c变量在结构体中的偏移量c语言提供了宏offsetof获得结构体内变量偏移量https://legacy.cplusplus.com/reference/cstddef/offsetof/因此可以使用变量地址 - 偏移量 结构体地址获得结构体地址重新设计双链表structlink{structlink*next;structlink*prev;}structtask_struct{//进程的属性structlinknode;//...}因此这个结构体中的链表next与prev指向的也是下一个结构体中node的地址而不是结构体的地址但是我们可以利用上面补充的前置知识获取task_struct的地址为什么要这么设计增加链式管理的扩展性代码只需要维护一份即可举头插链表为例insert_head(head,structlink*);structtask_struct*tnewXXX;insert_head(head,(t-node));在OS角度怎么做的优点是什么Linux内核会将所有的进程task_struct统一放在一张双链表中进程不是也有运行队列吗阻塞队列吗为什么一个节点既在队列里又在链表里structtask_struct{//...structlist_headtasks;//...structlist_headrun;}一个结构体里可以有多个链式结构这样tasks队列交给OS管理run队列用于给cpu调度队列甚至如果有更多的数据结构也可以通过这种方式让一个进程同时属于多个数据结构这就是内核设计数据结构的思路Linux2.6内核进程调度队列时间复杂度为O(1)每一个CPU都有一个调度队列structrunqueue{//...structtask_structqueue[140];//...};其中queue[140]可以理解为structtask_struct*queue[140]这是一个140块空间的队列其中普通优先级100~139我们都是普通的优先级想想nice值的取值范围可与之对应实时优先级0~99不关心其中100139这40个位置就是我们前面讲优先级的6099的40个位置结论1优先级数字本质是数组下标结论2则优先级相同的进程在同一个队列中这140个位置的每一个位置都是一个队列优先级相同则遵循FIFO原则进行调度那么根据优先级选择进程的时候本质是一个hash的过程结论3一旦确认是哪个队列剩下的就是FIFO可是每次想要找到一个不为空的队列最多需要遍历40次我们可以使用位图——每一个比特位对应一个下标0表示空队列1表示非空队列为什么使用位图因为位图的检测效率更高比直接检测效率更高。如果运行队列里一个进程都没有呢使用一个变量nr_active记录进程的总数structprio_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系统既有分时操作系统也有实时操作系统但是目前基本都是用分时操作系统
