目录1 进程状态1.1 进程状态概念1.2 运行阻塞挂起1.2.1 知识点1.3 理解内核链表的话题1.4 僵尸状态 僵尸进程1.5 两个问题1.6 孤儿进程2 进程优先级2.1 进程优先级概念2.2 查看系统进程2.3 PRI和NI2.4 四个概念竞争独立并行并发3 进程切换3.1 死循环进程如何运行3.2 聊聊CPU寄存器3.3 进程如何切换4 Linux真实调度算法O(1)调度算法上一篇说明完进程的概念后本文继续深入理解进程。1 进程状态1.1 进程状态概念进程状态本质是task_struct结构体内的一个整型变量在操作系统内可用#define来表示R S T。进程什么状态整型变量就改什么数字。进程状态就是task_struct内的一个整数。源码定义/* *The task state array is a strange bitmap of *reasons to sleep. Thus running is zero, and *you can test for combinations of others with *simple bit tests. */ static const char *const task_state_array[] { R (running), /*0 */ S (sleeping), /*1 */ D (disk sleep), /*2 */ T (stopped), /*4 */ t (tracing stop), /*8 */ X (dead), /*16 */ Z (zombie), /*32 */ };Linux进程状态R运行状态(running)并不意味着进程一定在运行中它表明进程要么是在运行中要么在运行队列里。S睡眠状态(sleeping)意味着进程在等待时间完成D磁盘休眠状态(Disk sleep)有时候也叫不可中断睡眠状态在这个状态的进程通常会等待IO的结束。T停止状态(stopped)可以通过发送SIGSTOP信号给进程来停止进程。这个被暂停的进程可以通过发送SIGCONT信号让进程继续运行。X死亡状态(dead)这个状态只是一个返回状态你不会在任务列表里看到这个状态。1.2 运行阻塞挂起让CPU选一个进程去运行本质是选择一个进程的PCB来运行一个PCB要有指针指到它代码和数据。一个CPU一个调度队列在Linux内核中名字叫runqueue类型是task_struct*。Linux内核对于PCB的维护采用的做法是一个task_struct节点既可以属于一个全局双向链表又可以把相关进程放相关队列里。也就是说一个进程的PCB节点既可以属于A数据结构又可以属于B数据结构。所以在操作系统内部专门为CPU设计了一个队列。1.2.1 知识点CPU调度就是在这个队列中按照顺序依次选择一个task_struct来进行调度执行。什么叫运行状态只要一个进程在调度队列中就称该进程叫做运行状态。什么叫阻塞状态等待某种设备或资源就绪不就绪就不调度。比如键盘显示器等设备就不一定是就绪的你用了一个scanf函数不按键盘去输入内容就是阻塞。操作系统怎么对软硬件资源进行管理呢以硬件为例先描述再组织。操作系统管理硬件为每个设备构建struct device的节点(实际更复杂)用指针将所有设备连接转化成对链表的增删查改。操作系统内除了有运行队列还有设备队列。然后每个设备都有一个自己的等待队列假设CPU正在运行这个进程发现这个进程要进行scanf读取然后操作系统就去检查键盘的状态(status)发现键盘没有任何按键按下此时操作系统发现这个进程无法再执行了所以操作系统将这个进程从CPU上拿下来将这个进程从运行队列中移除将PCB链入到特定设备这里是键盘每个设备都有自己独立的等待队列的等待队列中。一旦把这个进程链入到其他队列(不在运行队列中)该进程就不会被调度就处于阻塞状态。所以从运行状态到阻塞状态的本质是将PCB链入到不同结构中。当键盘被用户按下时这个进程不知道操作系统作为硬件管理者第一时间知道转而查看就绪设备对应节点将状态设为active检查等待队列发现指针不为空将该等待队列中PCB设为运行状态将该进程链回运行队列CPU调度这个进程就会执行。所以结论进程状态的变化表现之一就是要在不同的队列中进行流动。本质就是数据结构的增删查改。假设内存资源严重不足操作系统要做一件事在磁盘中存在一个特定分区称为swap交换分区这时将等待队列中操作系统让PCB在内存代码和数据换出到磁盘swap分区此时这些进程的状态叫阻塞挂起键盘一旦好了操作系统就会将对应进程曾经换入磁盘中的代码和数据重新加载到内存重新构建指针的映射形成完整进程再到运行队列。这个过程叫swap交换分区的唤出唤入过程挂起是将进程的代码和数据挂到磁盘上。如果内存资源相当吃紧将等待队列中所有进程代码和数据全挂起内存空间还是不够操作系统就将运行队列中末端进程代码和数据唤到swap分区这叫运行挂起。1.3 理解内核链表的话题内核中有一个结构体list_head成员有且只包含nextprev。有了它之后定义任何一个结构体比如task_struct将这个list_head节点类型作为新的目标数据结构成员。那么运行队列中task_struct连接起来就是通过list_head:只指向目标结构体内部的成员list_head。小知识一个结构体a取地址a和取地址a的第一个成员变量地址是一样的。aa.x那么遍历链表访问任何一个结构体的任何成员怎么做呢答案:(struct task_struct*)list-((struct task_struct*)0-links)将0号地址强转后直接访问links再取地址得到links相较于结构体开始位置的偏移量。因为我只知道当前对象对应links地址有了偏移量直接list的地址值减去偏移量就得到链表中头部地址未来这个结构体内部的所有成员就都能访问了。总结已知结构体中某个成员的地址通过计算该成员在结构体中的偏移量就能得到结构体的首地址进而访问所有成员。所以task_struct有了list_head成员就是双向链表将进程们连接起来那么可不可以task_struct内部有非常多的list_head答案是可以的。所以可以在每个字段将list_head连接起来任何对应的struct task_struct一个对象一套属性。让task_struct既属于运行队列又属于全局链表还可以把它放在二叉树中。所以一个PCB可以随便链接这些个PCB既在运行队列里同时又在全局链表中把它从运行队列里断键放到阻塞队列里同时它又在全局链表中这样就能理解了。一个PCB可以同时隶属于多种数据结构Linux内核中很多数据结构其实是网状的。1.4 僵尸状态 僵尸进程Z是僵尸状态目的是为了获取退出信息。在Linux中我们创建子进程的目的是为了让子进程完成某种事情的然后结果相关的信息父进程需要知道一个子进程退出时操作系统可以将其代码和数据释放掉(PCB信息不能释放)。我们需要子进程退出时父进程要从子进程中获取子进程退出的结果所以一个子进程退出要把退出信息暂时维持住让父进程获取在子进程退出之后父进程获取子进程的退出信息之前状态就是Z状态(僵尸状态)。模拟验证Z状态编译然后查看进程运行可执行程序查看进程前面时候父子进程正常运行后来子进程退出肉眼看到子进程的状态是Z状态。如果父进程一直不管不回收僵尸状态是不是一直要维护呢答案是是的如果父进程一直不管不回收不获取子进程的退出信息那么僵尸状态一直存在PCB一直存在因为PID在那么内存一直被占用这叫内存泄漏问题这是不通过newmalloc的内存泄露。僵尸进程就是内存泄漏。1.5 两个问题如果进程结束了曾经因内存泄漏没有被释放的空间会恢复吗或者说进程退出了内存泄漏还在不在答案是不存在的进程退了内存泄漏问题就没有了。什么样的进程具有内存泄漏问题是比较麻烦的真实世界很多软件启动之后不退出的比如windows中自带的杀毒软件这种是常驻内存的进程这样的进程最怕内存泄漏。知识点unuse列表存放进程结束后的task_struct相当于数据结构的缓存进程启动后不用重新建立task_struct而从unuse中获取直接填属性用来加快创建进程和释放进程的速度。1.6 孤儿进程写一个验证孤儿进程的代码父子进程关系中如果父进程先退出子进程要被1号进程领养这个被领养的进程子进程叫做孤儿进程。在Linux系统中1号进程创建的bash。为什么要领养如果不领养子进程就会进入僵尸状态就没人回收它了就会造成内存泄漏无法解决。领养之后新的父进程未来对这种子进程进行统一回收。一个子进程变成孤儿进程后一般就自动变后台内容ctrl c杀不掉只能kill -9 加pid杀掉进程。2 进程优先级2.1 进程优先级概念什么是优先级优先级本质是一种衡量得到某种资源的先后顺序同理对进程是进程得到CPU资源的先后顺序。为什么要有进程优先级因为目标资源稀缺导致要通过优先级确定谁先谁后的问题优先级也是一种数字是task_struct中的一个属性值越低优先级越高反之优先级越低。2.2 查看系统进程当代Linux或大部分操作系统这些操作系统叫做基于时间片的分时操作系统。要考虑公平性优先级先后差别不能太大优先级可能变化但是变化幅度不能太大。使用ps -la可以看到以下内容几个重要信息UID代表执行者的身份PID代表这个进程的代号PPID代表这个进程是由哪个进程发展衍生而来的亦即父进程的代号PRI代表这个进程可被执行的优先级其值越小越早被执行NI代表这个进程的nice值小知识系统怎么会知道我访问文件时是拥有者所属组还是other因为进程启动时会记录UIDLinux系统中访问任何资源都是进程访问进程就代表用户用户和系统打交道只能通过进程来交互所有需求都会变成进程由OS帮你去调度去执行。所以识别权限不是识别用户是识别进程和文件之间的权限。2.3 PRI和NIPRI进程的优先级默认是80。NI进程优先级的修改数据也称nice值调整优先级在Linux下就是调整进程的nice值。所以一个进程的真实优先级PRI(默认)NI。默认这里是80。使用top命令更改已经存在进程的nice进入top后按“r”然后输入进程的PID然后输入nice值即可。nice的取值范围是[-2019]默认的PRI是80所以Linux进程优先级范围是[60,99]。为什么优先级调整范围不能太宽泛答如果优先级跨度太大用户能自己恶意修改自己进程的优先级来尽可能的让自己进程总是优先获得资源此时可能导致进程优先级低的进程长时间得不到CPU资源进而导致进程饥饿。2.4 四个概念竞争独立并行并发多个进程之间存在竞争性系统进程数目众多而CPU资源只有少量甚至只有一个CPU所以进程之间是具有竞争属性的。为了高效完成任务更合理竞争竞争相关资源便具有优先级独立性。多进程运行需要独享各种资源多进程之间互不干扰。并行多个进程在多个CPU下分别同时进行运行称之为并行并发多个进程在一个CPU下采用进程切换的方式在一段时间内让多个进程都得以推进称之为并发。3 进程切换3.1 死循环进程如何运行一旦一个进程占有CPU会把自己的代码跑完吗答案是不会每个进程操作系统都会给它分配一个时间片的东西一个进程不会一直占用CPU时间片到了操作系统就会切换它。死循环进程不会打死操作系统因为有时间片死循环进程不会一直占有CPU。3.2 CPU寄存器CPU调度进程时访问其代码和数据为了处理代码和数据CPU内有很多寄存器这些寄存器在3264位下都有很多。例如ebp/espeax/ebx/acx/adxcs/ds/es/gs等。寄存器内保存的是一个正在运行的进程执行过程中此时刻的临时数据。结论1寄存器就是CPU内部的临时空间2寄存器寄存器里面的数据寄存器是空间只有一份内容数据可以是多份的。3.3 进程如何切换进程切换最核心的的就是保存和恢复当前进程硬件上下文的数据即CPU内寄存器的内容。切换中把寄存器的临时数据叫当前进程的硬件上下文数据保存起来保存到哪里了呢结论是保存到task_struct里面。当代操作系统给每个进程TSS字段。TSS任务状态段也是结构体放上下文能通过task_struct找到TSS。总结一个进程要切换将其硬件上下文保存起来在运行期间CPU寄存器内包含很多临时数据临时数据是进程运行上下文每次运行如果时间片到了操作系统就会把进程切换下去将上下文数据保存起来下个进程再进来运行重复这种流程。4 Linux真实调度算法O(1)调度算法下面的所有内容可以参照上面的图片。调度和切换共同构成调度器。每个CPU有一个运行队列。在Linux内核中运行队列叫做runquenue。里面有一个queue[140]queue的类型是struct task_struct* queue[140]其实是个指针数组有140项。为什么是140呢其实Linux的优先级其实是140个。那么为什么优先级范围是[6099]queue[140]内[0,99]这100个称之为实时优先级(这里我们不考虑)。解释操作系统分为两大类别分时操作系统(按时间片为单位公平调度)。还有一种是实时操作系统一旦我们来了一个进程必须立即响应处理完才能处理下一个进程。为什么很少谈这个呢一般在工业领域制造业领域用的比较多。比如汽车上车载系统控制、刹车控制这种不敢上分时操作系统用实时操作系统。在互联网领域分时操作系统最广泛。那么Linux只做分时操作系统不就行了吗为啥还要加实时操作系统。因为为了让更多人用Liinux操作系统满足更多人需求。所以大部分操作系统既支持实时又支持分时。所以一般不考虑[0,99]一旦不考虑一共140所以还剩40个优先级这就和进程优先级范围[6099]对应起来了。所以优先级 x-60(140-40),将优先级映射下标这40个中保存的都是task_struct*优先级是60就链入到对应100下标就完成了对应按照不同优先级调度局部上采用先进先出。这个表本质就是哈希表哈希函数是x-60(140-40).操作系统层面调度器选一个进程调度在一个确定优先级下找一个进程,时间复杂度是O(1)。如果所有进程优先级都比较低,不还是要遍历这个数组吗?遍历复杂度是O(n)效率还是不高所以调度器如何快速挑选一个进程呢这里在运行队列中有一个bitmap[5]这是位图。这里的类型是unsigned int bitmap[5]一共是32*5160个比特位。为什么是5因为这个位图的比特位和整个queue[140]一一对应覆盖140个所以是5有160个比特位能覆盖这140个。比特位内容1/0表示是否存在内容。假设如果一个比特位是000...00100代表2号下标有进程。所以调度器快速挑选一个进程。1 挑队列 2 挑进程挑队列只要查看位图整体把32个比特位整体查看有不为0的位置再去对应32个比特位具体在哪个下标缓解遍历140个位置的时间复杂度。所以做到了以O(1)时间复杂度挑选一个进程我们把它叫做Linux内核进程调度算法之O(1)调度算法。还有一个是nr_active表示整个队列中一共有多少个进程。所以调度中先查nr_active大于0再查bitmap[5]确认下标直接索引找到目标队列从队列中查找进程找到后将当前进程PCB放入struct task_struct* current指针里然后执行切换算法然后current选择不同进程放CPU上继续运行。这还没完如果这样调度的话假设现在有一个60号进程也有一个99号进程。60号进程是一个死循环60号进程时间片到了此时被切换下去。因为下次还要调度放回队列里。60号进程放到60号下标对应队列的结尾处会发现永远都是将下标100对应队列中的所有进程全跑完才能执行101这就造成了进程饥饿问题。所以runqueue又干了一件事在整个runqueue又弄一个哈希数组和上面的大哈希表一模一样。内核中设计了一个struct rqueue_elem结构体内部有int nr_sctivebitmap[5]queue[140]。然后在rqueue内部定义struct rqueue_elsm prio_array[2]在rqueue包含数组两个元素0号下标是蓝色1号下标是红色(对应图片)从此以后在runqueue内部定义两个active类型是struct rqueue_elem*一个是活跃进程一个是过期进程。struct rqueue_elem* activeprio_array[0]。struct rqueue_elem* expiredprio_arry[1]。CPU在调度进程挑进程首先永远只从active指针找到runqueue60号进程被剥离下来不能放回到原队列必须把这个进程重新链入到rqueue_elem(过期队列中)凡是时间片到了的进程全部放进过期队列中慢慢地active queue中进程越来越少expired queue进程越来越多。规定必须把active队列中进程全部调度完成才能有后续动作然后神之一手swap(active,expired);直接进行指针内容交换。active指向原来的expiredexpired指向的就是原来active的空队列。然后重复调度完成了O(1)调度算法。所以为啥要有NI(nice值)而不是直接改PRI直接改PRI如果这个进程在活跃队列里改优先级进程要不要重新改链入位置在活跃队列中修改和在过期队列中修改都不好。所以有nice值这个进程在活跃队列中时间片到了进入过期队列时根据新的优先级去对应位置就好了。所以这是为了配合O(1)调度算法。以上就是这篇文章的所有内容了如果这篇文章对你有用可以点点赞哦你的支持就是我写下去的动力后续会继续更新其他知识。
【Linux】深入理解进程：进程状态，进程优先级，进程切换与O(1)调度算法
目录1 进程状态1.1 进程状态概念1.2 运行阻塞挂起1.2.1 知识点1.3 理解内核链表的话题1.4 僵尸状态 僵尸进程1.5 两个问题1.6 孤儿进程2 进程优先级2.1 进程优先级概念2.2 查看系统进程2.3 PRI和NI2.4 四个概念竞争独立并行并发3 进程切换3.1 死循环进程如何运行3.2 聊聊CPU寄存器3.3 进程如何切换4 Linux真实调度算法O(1)调度算法上一篇说明完进程的概念后本文继续深入理解进程。1 进程状态1.1 进程状态概念进程状态本质是task_struct结构体内的一个整型变量在操作系统内可用#define来表示R S T。进程什么状态整型变量就改什么数字。进程状态就是task_struct内的一个整数。源码定义/* *The task state array is a strange bitmap of *reasons to sleep. Thus running is zero, and *you can test for combinations of others with *simple bit tests. */ static const char *const task_state_array[] { R (running), /*0 */ S (sleeping), /*1 */ D (disk sleep), /*2 */ T (stopped), /*4 */ t (tracing stop), /*8 */ X (dead), /*16 */ Z (zombie), /*32 */ };Linux进程状态R运行状态(running)并不意味着进程一定在运行中它表明进程要么是在运行中要么在运行队列里。S睡眠状态(sleeping)意味着进程在等待时间完成D磁盘休眠状态(Disk sleep)有时候也叫不可中断睡眠状态在这个状态的进程通常会等待IO的结束。T停止状态(stopped)可以通过发送SIGSTOP信号给进程来停止进程。这个被暂停的进程可以通过发送SIGCONT信号让进程继续运行。X死亡状态(dead)这个状态只是一个返回状态你不会在任务列表里看到这个状态。1.2 运行阻塞挂起让CPU选一个进程去运行本质是选择一个进程的PCB来运行一个PCB要有指针指到它代码和数据。一个CPU一个调度队列在Linux内核中名字叫runqueue类型是task_struct*。Linux内核对于PCB的维护采用的做法是一个task_struct节点既可以属于一个全局双向链表又可以把相关进程放相关队列里。也就是说一个进程的PCB节点既可以属于A数据结构又可以属于B数据结构。所以在操作系统内部专门为CPU设计了一个队列。1.2.1 知识点CPU调度就是在这个队列中按照顺序依次选择一个task_struct来进行调度执行。什么叫运行状态只要一个进程在调度队列中就称该进程叫做运行状态。什么叫阻塞状态等待某种设备或资源就绪不就绪就不调度。比如键盘显示器等设备就不一定是就绪的你用了一个scanf函数不按键盘去输入内容就是阻塞。操作系统怎么对软硬件资源进行管理呢以硬件为例先描述再组织。操作系统管理硬件为每个设备构建struct device的节点(实际更复杂)用指针将所有设备连接转化成对链表的增删查改。操作系统内除了有运行队列还有设备队列。然后每个设备都有一个自己的等待队列假设CPU正在运行这个进程发现这个进程要进行scanf读取然后操作系统就去检查键盘的状态(status)发现键盘没有任何按键按下此时操作系统发现这个进程无法再执行了所以操作系统将这个进程从CPU上拿下来将这个进程从运行队列中移除将PCB链入到特定设备这里是键盘每个设备都有自己独立的等待队列的等待队列中。一旦把这个进程链入到其他队列(不在运行队列中)该进程就不会被调度就处于阻塞状态。所以从运行状态到阻塞状态的本质是将PCB链入到不同结构中。当键盘被用户按下时这个进程不知道操作系统作为硬件管理者第一时间知道转而查看就绪设备对应节点将状态设为active检查等待队列发现指针不为空将该等待队列中PCB设为运行状态将该进程链回运行队列CPU调度这个进程就会执行。所以结论进程状态的变化表现之一就是要在不同的队列中进行流动。本质就是数据结构的增删查改。假设内存资源严重不足操作系统要做一件事在磁盘中存在一个特定分区称为swap交换分区这时将等待队列中操作系统让PCB在内存代码和数据换出到磁盘swap分区此时这些进程的状态叫阻塞挂起键盘一旦好了操作系统就会将对应进程曾经换入磁盘中的代码和数据重新加载到内存重新构建指针的映射形成完整进程再到运行队列。这个过程叫swap交换分区的唤出唤入过程挂起是将进程的代码和数据挂到磁盘上。如果内存资源相当吃紧将等待队列中所有进程代码和数据全挂起内存空间还是不够操作系统就将运行队列中末端进程代码和数据唤到swap分区这叫运行挂起。1.3 理解内核链表的话题内核中有一个结构体list_head成员有且只包含nextprev。有了它之后定义任何一个结构体比如task_struct将这个list_head节点类型作为新的目标数据结构成员。那么运行队列中task_struct连接起来就是通过list_head:只指向目标结构体内部的成员list_head。小知识一个结构体a取地址a和取地址a的第一个成员变量地址是一样的。aa.x那么遍历链表访问任何一个结构体的任何成员怎么做呢答案:(struct task_struct*)list-((struct task_struct*)0-links)将0号地址强转后直接访问links再取地址得到links相较于结构体开始位置的偏移量。因为我只知道当前对象对应links地址有了偏移量直接list的地址值减去偏移量就得到链表中头部地址未来这个结构体内部的所有成员就都能访问了。总结已知结构体中某个成员的地址通过计算该成员在结构体中的偏移量就能得到结构体的首地址进而访问所有成员。所以task_struct有了list_head成员就是双向链表将进程们连接起来那么可不可以task_struct内部有非常多的list_head答案是可以的。所以可以在每个字段将list_head连接起来任何对应的struct task_struct一个对象一套属性。让task_struct既属于运行队列又属于全局链表还可以把它放在二叉树中。所以一个PCB可以随便链接这些个PCB既在运行队列里同时又在全局链表中把它从运行队列里断键放到阻塞队列里同时它又在全局链表中这样就能理解了。一个PCB可以同时隶属于多种数据结构Linux内核中很多数据结构其实是网状的。1.4 僵尸状态 僵尸进程Z是僵尸状态目的是为了获取退出信息。在Linux中我们创建子进程的目的是为了让子进程完成某种事情的然后结果相关的信息父进程需要知道一个子进程退出时操作系统可以将其代码和数据释放掉(PCB信息不能释放)。我们需要子进程退出时父进程要从子进程中获取子进程退出的结果所以一个子进程退出要把退出信息暂时维持住让父进程获取在子进程退出之后父进程获取子进程的退出信息之前状态就是Z状态(僵尸状态)。模拟验证Z状态编译然后查看进程运行可执行程序查看进程前面时候父子进程正常运行后来子进程退出肉眼看到子进程的状态是Z状态。如果父进程一直不管不回收僵尸状态是不是一直要维护呢答案是是的如果父进程一直不管不回收不获取子进程的退出信息那么僵尸状态一直存在PCB一直存在因为PID在那么内存一直被占用这叫内存泄漏问题这是不通过newmalloc的内存泄露。僵尸进程就是内存泄漏。1.5 两个问题如果进程结束了曾经因内存泄漏没有被释放的空间会恢复吗或者说进程退出了内存泄漏还在不在答案是不存在的进程退了内存泄漏问题就没有了。什么样的进程具有内存泄漏问题是比较麻烦的真实世界很多软件启动之后不退出的比如windows中自带的杀毒软件这种是常驻内存的进程这样的进程最怕内存泄漏。知识点unuse列表存放进程结束后的task_struct相当于数据结构的缓存进程启动后不用重新建立task_struct而从unuse中获取直接填属性用来加快创建进程和释放进程的速度。1.6 孤儿进程写一个验证孤儿进程的代码父子进程关系中如果父进程先退出子进程要被1号进程领养这个被领养的进程子进程叫做孤儿进程。在Linux系统中1号进程创建的bash。为什么要领养如果不领养子进程就会进入僵尸状态就没人回收它了就会造成内存泄漏无法解决。领养之后新的父进程未来对这种子进程进行统一回收。一个子进程变成孤儿进程后一般就自动变后台内容ctrl c杀不掉只能kill -9 加pid杀掉进程。2 进程优先级2.1 进程优先级概念什么是优先级优先级本质是一种衡量得到某种资源的先后顺序同理对进程是进程得到CPU资源的先后顺序。为什么要有进程优先级因为目标资源稀缺导致要通过优先级确定谁先谁后的问题优先级也是一种数字是task_struct中的一个属性值越低优先级越高反之优先级越低。2.2 查看系统进程当代Linux或大部分操作系统这些操作系统叫做基于时间片的分时操作系统。要考虑公平性优先级先后差别不能太大优先级可能变化但是变化幅度不能太大。使用ps -la可以看到以下内容几个重要信息UID代表执行者的身份PID代表这个进程的代号PPID代表这个进程是由哪个进程发展衍生而来的亦即父进程的代号PRI代表这个进程可被执行的优先级其值越小越早被执行NI代表这个进程的nice值小知识系统怎么会知道我访问文件时是拥有者所属组还是other因为进程启动时会记录UIDLinux系统中访问任何资源都是进程访问进程就代表用户用户和系统打交道只能通过进程来交互所有需求都会变成进程由OS帮你去调度去执行。所以识别权限不是识别用户是识别进程和文件之间的权限。2.3 PRI和NIPRI进程的优先级默认是80。NI进程优先级的修改数据也称nice值调整优先级在Linux下就是调整进程的nice值。所以一个进程的真实优先级PRI(默认)NI。默认这里是80。使用top命令更改已经存在进程的nice进入top后按“r”然后输入进程的PID然后输入nice值即可。nice的取值范围是[-2019]默认的PRI是80所以Linux进程优先级范围是[60,99]。为什么优先级调整范围不能太宽泛答如果优先级跨度太大用户能自己恶意修改自己进程的优先级来尽可能的让自己进程总是优先获得资源此时可能导致进程优先级低的进程长时间得不到CPU资源进而导致进程饥饿。2.4 四个概念竞争独立并行并发多个进程之间存在竞争性系统进程数目众多而CPU资源只有少量甚至只有一个CPU所以进程之间是具有竞争属性的。为了高效完成任务更合理竞争竞争相关资源便具有优先级独立性。多进程运行需要独享各种资源多进程之间互不干扰。并行多个进程在多个CPU下分别同时进行运行称之为并行并发多个进程在一个CPU下采用进程切换的方式在一段时间内让多个进程都得以推进称之为并发。3 进程切换3.1 死循环进程如何运行一旦一个进程占有CPU会把自己的代码跑完吗答案是不会每个进程操作系统都会给它分配一个时间片的东西一个进程不会一直占用CPU时间片到了操作系统就会切换它。死循环进程不会打死操作系统因为有时间片死循环进程不会一直占有CPU。3.2 CPU寄存器CPU调度进程时访问其代码和数据为了处理代码和数据CPU内有很多寄存器这些寄存器在3264位下都有很多。例如ebp/espeax/ebx/acx/adxcs/ds/es/gs等。寄存器内保存的是一个正在运行的进程执行过程中此时刻的临时数据。结论1寄存器就是CPU内部的临时空间2寄存器寄存器里面的数据寄存器是空间只有一份内容数据可以是多份的。3.3 进程如何切换进程切换最核心的的就是保存和恢复当前进程硬件上下文的数据即CPU内寄存器的内容。切换中把寄存器的临时数据叫当前进程的硬件上下文数据保存起来保存到哪里了呢结论是保存到task_struct里面。当代操作系统给每个进程TSS字段。TSS任务状态段也是结构体放上下文能通过task_struct找到TSS。总结一个进程要切换将其硬件上下文保存起来在运行期间CPU寄存器内包含很多临时数据临时数据是进程运行上下文每次运行如果时间片到了操作系统就会把进程切换下去将上下文数据保存起来下个进程再进来运行重复这种流程。4 Linux真实调度算法O(1)调度算法下面的所有内容可以参照上面的图片。调度和切换共同构成调度器。每个CPU有一个运行队列。在Linux内核中运行队列叫做runquenue。里面有一个queue[140]queue的类型是struct task_struct* queue[140]其实是个指针数组有140项。为什么是140呢其实Linux的优先级其实是140个。那么为什么优先级范围是[6099]queue[140]内[0,99]这100个称之为实时优先级(这里我们不考虑)。解释操作系统分为两大类别分时操作系统(按时间片为单位公平调度)。还有一种是实时操作系统一旦我们来了一个进程必须立即响应处理完才能处理下一个进程。为什么很少谈这个呢一般在工业领域制造业领域用的比较多。比如汽车上车载系统控制、刹车控制这种不敢上分时操作系统用实时操作系统。在互联网领域分时操作系统最广泛。那么Linux只做分时操作系统不就行了吗为啥还要加实时操作系统。因为为了让更多人用Liinux操作系统满足更多人需求。所以大部分操作系统既支持实时又支持分时。所以一般不考虑[0,99]一旦不考虑一共140所以还剩40个优先级这就和进程优先级范围[6099]对应起来了。所以优先级 x-60(140-40),将优先级映射下标这40个中保存的都是task_struct*优先级是60就链入到对应100下标就完成了对应按照不同优先级调度局部上采用先进先出。这个表本质就是哈希表哈希函数是x-60(140-40).操作系统层面调度器选一个进程调度在一个确定优先级下找一个进程,时间复杂度是O(1)。如果所有进程优先级都比较低,不还是要遍历这个数组吗?遍历复杂度是O(n)效率还是不高所以调度器如何快速挑选一个进程呢这里在运行队列中有一个bitmap[5]这是位图。这里的类型是unsigned int bitmap[5]一共是32*5160个比特位。为什么是5因为这个位图的比特位和整个queue[140]一一对应覆盖140个所以是5有160个比特位能覆盖这140个。比特位内容1/0表示是否存在内容。假设如果一个比特位是000...00100代表2号下标有进程。所以调度器快速挑选一个进程。1 挑队列 2 挑进程挑队列只要查看位图整体把32个比特位整体查看有不为0的位置再去对应32个比特位具体在哪个下标缓解遍历140个位置的时间复杂度。所以做到了以O(1)时间复杂度挑选一个进程我们把它叫做Linux内核进程调度算法之O(1)调度算法。还有一个是nr_active表示整个队列中一共有多少个进程。所以调度中先查nr_active大于0再查bitmap[5]确认下标直接索引找到目标队列从队列中查找进程找到后将当前进程PCB放入struct task_struct* current指针里然后执行切换算法然后current选择不同进程放CPU上继续运行。这还没完如果这样调度的话假设现在有一个60号进程也有一个99号进程。60号进程是一个死循环60号进程时间片到了此时被切换下去。因为下次还要调度放回队列里。60号进程放到60号下标对应队列的结尾处会发现永远都是将下标100对应队列中的所有进程全跑完才能执行101这就造成了进程饥饿问题。所以runqueue又干了一件事在整个runqueue又弄一个哈希数组和上面的大哈希表一模一样。内核中设计了一个struct rqueue_elem结构体内部有int nr_sctivebitmap[5]queue[140]。然后在rqueue内部定义struct rqueue_elsm prio_array[2]在rqueue包含数组两个元素0号下标是蓝色1号下标是红色(对应图片)从此以后在runqueue内部定义两个active类型是struct rqueue_elem*一个是活跃进程一个是过期进程。struct rqueue_elem* activeprio_array[0]。struct rqueue_elem* expiredprio_arry[1]。CPU在调度进程挑进程首先永远只从active指针找到runqueue60号进程被剥离下来不能放回到原队列必须把这个进程重新链入到rqueue_elem(过期队列中)凡是时间片到了的进程全部放进过期队列中慢慢地active queue中进程越来越少expired queue进程越来越多。规定必须把active队列中进程全部调度完成才能有后续动作然后神之一手swap(active,expired);直接进行指针内容交换。active指向原来的expiredexpired指向的就是原来active的空队列。然后重复调度完成了O(1)调度算法。所以为啥要有NI(nice值)而不是直接改PRI直接改PRI如果这个进程在活跃队列里改优先级进程要不要重新改链入位置在活跃队列中修改和在过期队列中修改都不好。所以有nice值这个进程在活跃队列中时间片到了进入过期队列时根据新的优先级去对应位置就好了。所以这是为了配合O(1)调度算法。以上就是这篇文章的所有内容了如果这篇文章对你有用可以点点赞哦你的支持就是我写下去的动力后续会继续更新其他知识。
