宁波h5建站中铁十六门网户登录

当前位置： 首页 > news >正文

宁波h5建站,中铁十六门网户登录,沈阳专业做网站方案,门户网站建设好如何维护前言 在前面我们完成了Sparrow的临界区的代码#xff0c;使用临界区#xff0c;能够解决常见的并发问题#xff0c;现在该完善我们的调度算法了。 调度算法在操作系统领域常常是热门的话题。不同的用途将会使用不同的调度策略。在本节#xff0c;笔者将为大家介绍一些操作…前言 在前面我们完成了Sparrow的临界区的代码使用临界区能够解决常见的并发问题现在该完善我们的调度算法了。 调度算法在操作系统领域常常是热门的话题。不同的用途将会使用不同的调度策略。在本节笔者将为大家介绍一些操作系统中的调度算法的知识加深读者对操作系统的理解。 linux内核中的调度策略 调度策略负责进行任务选择和任务切换linux内核中的调度基于分时技术多个进程以“时间多路复用”的方式运行将时间进行分割不同段时间运行不同的任务这段时间被称之为时间片。 进程的分类 linux内核中通常有三类进程 交互式进程用于和用户发生交互对时间不是很敏感时不时卡一卡也是在用户容许范围内。 批处理进程在后台运行的进程不与用户直接接触例如编译程序和科学计算程序等等。 实时进程对时间要求非常严格的程序例如自动控制程序。 进程的抢占 linux内核是抢占式的也就是说不同的进程有不同的优先级如果响应的进程的优先级比当前运行的进程的优先级要高那么当前的进程就会被响应的进程所抢占。 调度算法 早期linux版本的内核的调度算法比较简单扫描并且计算所有就绪进程的优先级然后选择最佳的进程来运行参考的标准是时间片时间片大的进程往往优先运行。这一算法的缺点非常明显就是时间不固定。 当然到了2.6版本之后linux内核的调度算法已经复杂到不可想象的程度了这跟多处理器的出现也有很大的关系此时调度选择算法会在固定的时间选出任务执行以确保CPU的运行速度。 Linux0.11版本调度算法 让我们先看看linux内核0.11版本的调度算法。 首先是前几行 c其实代表的是保存进程时间片的值 next表示下一个进程的序列 i,p都与挂载进程的任务队列有关i代表数组下标p是指向队列本身的指针。 其实这就是一个很常见的比较大小的算法首先检查这个进程的状态是不是运行状态然后进行比较如果在运行队列里遇到比当前进程时间片大的进程那么就替换成它c更改为这个大的进程的时间片next更改为这个进程的下标。 通过这个比较算法我们筛选出了队列里时间片最大的任务。接下来就是切换了如果要切换的进程的时间片没有用完也就是c0时这个while循环会直接结束程序会跳转到switch这里这就是进程切换的函数。 如果这个优先级高的进程的时间片已经用完了也就是c.0时会进入for循环这是对时间片的重新分配。因为我们从前面的排序已经知道c就是被筛选出来的最大的时间片如果c0意味着所有的进程都没有了时间片。 上面的for循环其实就是根据优先级的大小来调整时间片的大小最后每一个进程counter的值原先值/2 优先级。 可能读者还会疑惑为什么要加上*p-counter1呢位于运行状态的进程的时间片不是都为0了吗 进程不止一种状态显然还在被阻塞的任务时间片肯定不为0啊虽然运行状态的进程最终时间片都等于自身优先级的大小但是阻塞任务就要考虑原先的时间片了对原先时间片除以2这是对平均时间片的综合考虑的结果时间片过短切换的开销会变大时间片过长进程看起来就不会是并行的。 现在让我们来到switch_to函数 在前文笔者简单讨论过进程的上下文切换因为进程之间隔绝了资源这往往意味着切换的步骤会变得简单一些从代码中可以看出主要是TSS一个保存进程状态信息的结构体的切换但是在FreeRTOS中则主要是对arm寄存器的操作因为进程切换是所有的资源都进行了改变而线程的切换则是在原有的资源上修修改改本质是任务栈的切换。 通过schedule和switch_to两个函数我们知道了linux0.11版本是如何进行调度的schedule负责时间片的分配和进程的选择switch_to负责进程的切换。 操作系统的调度器本质就是在进行选择和切换。 现在该来到常见的RTOS内核了 FreeRTOS的调度算法 让我们看看tasks.c文件中的这几行代码 prvAddTaskToReadyList函数在每个任务在添加到就绪列表时都会执行它会与uxTopReadyPriority进行比较然后uxTopReadyPriority记录两者中的较大者不断的对每一个新添加进来的任务优先级进行比较这其实就是在找出最大的优先级。 这样做遍历时就能直接找到优先级最高的线程。 顺便一提FreeRTOS中的任务优先级跟我们在mcu中学习到的中断优先级判断是不一样的也跟RTT和uc/os不一样mcu中的中断优先级是数字越小优先级越大RTT和uc/os的任务优先级也是这样但FreeRTOS中是任务优先级的数字越大优先级越大。 taskSELECT_HIGHEST_PRIORITY_TASK就是通用的选择算法的具体函数了先对uxTopReadyPriority的值进行保存。 configASSERT笔者之前提过是断言用来debug如果uxTopPriority小于0会触发它。 每一个优先级都有一个特定的链表while判断就绪链表的这个优先级是否有任务挂载在上面如果没有就继续找下一个优先级的链表也就是–uxTopPriority。 uxTopPriority被设定为是代表最大优先级的数字自减操作代表从就绪列表最后一个链表优先级最高的链表开始查找直到找到任务链表不为空的优先级任务那么这个任务肯定也是所有任务中优先级最大的任务。 然后获取这个任务的TCB并更新pxCurrentTCB切换的具体函数最后更新uxTopReadyPriority的值。 rt-thread内核的调度算法 rt-thread是一个国产RTOS和sylixOS这些OS一样也是头部RTOS了不过在国内的开源领域确实是当之无愧的第一RTOS。 它是一个偏linux的RTOS而且用面向对象的思想开发的非常有特色。 笔者决定再讲一讲rtt的选择算法因为这种算法很常见用途也非常广泛。 RTT使用的是查表法让笔者简单介绍一下这种策略的思想。 我们要查找一个链表中优先级最高的任务最简便的做法就是for循环一个个遍历比较找到优先级最高的任务这种做法很简便缺点是复杂度过高,达到了o(n)查询的时间很长。那么有没有使复杂度为1的方法呢 于是RTT使用了空间换时间的策略。 假设我们有八个优先级用八个位来表示它们。任务优先级为多少那么就在哪个位置1。 例如task1优先级为5那么优先级的数字就是00010000。 在实时操作系统中优先级数字越小优先级越高那么这个任务代表的1更靠近右侧。 既然知道了这些那么把所有8个位的组合都列出来判断每一个不同的数字最低位的1在哪个位然后直接查询不就可以知道任务的优先级最高是多少吗然后顺着优先级去执行对应的任务。 通过这个函数可以将prioritynum最低位的1的位置打印出来。这个函数比较简单就是循环遍历0到255也就是00000000到11111111让每一个数依次右移最多八位找到最低位的1。prioritynum右移后会与1进行与运算也就是说除非右移后的数最低位是1否则都会进行下一轮循环直到找到最低位的1并且打印随后程序又会跳出内层循环进行下一个prioritynum的运算。 运行结果 通过这个数组我们可以可以将prioritynum作为数组下标查询最高优先级。这其实就是一种哈希算法的思想用特定的数字映射特定的优先级。 这种算法缺点也十分明显就是数组占用空间太大了一个int就要4个字节上面的例子是优先级为8位如果优先级有32位呢那么占用空间将会达到4*2的32次方个字节。 为了解决这个问题RTT内核使用了四个表每个表对应8个位算法也很简洁先读最低八位的值判断是否为0不为0说明优先级肯定在最低八位中然后直接查表即可。可能有读者好奇为什么要加上1其实观察就会发现这个表的第一个0是在循环之前手动打印的否则没有256个数为了避免与32位全为0冲突所以加上了1。 简单来说笔者手动让数组里的所有数向后移动了一位那么相应的把prioritynum作为下标读取表里的数也要往后面移动一位。 如果最低八位没有那就到次八位找同样先判断是否在次八位中如果在那么右移八位然后查表因为进行了右移操作所以返回值要在最低八位的返回值的基础加上8。 剩下两个同理留给读者自己分析了。 总的来说这种基于哈希思想的查表法应用十分广泛采用空间换时间的策略具有一定的学习价值如果某些程序对查询的时间要求比较高可以尝试用查表策略代替之前的遍历策略。 总结 笔者介绍了linux内核、FreeRTOS、RT-Thread的调度策略和算法旨在加深读者对操作系统的理解。当然本来这些内容应该分成几篇不同的文章细细讲解的不过笔者还是决定全部放在一篇。 一方面是考虑到放在同一篇文章里更加全面系统另一方面是考虑到Sparrow的文章数量如果过多了比如更成了四五十篇。 那么笔者相信屏幕前的读者一定没什么兴趣看下去了。所以笔者还是决定追求简洁明了不更那么多废话。 Sparrow的教程更到这里其实已经快接近尾声了。更完调度算法再更完定时器阻塞延时后就结束了。 一步步跟着教程实现Sparrow RTOS的小伙伴们一路看到这里不知道是否有所收获?