AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

进程调度预备开发

2024-01-17 43
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 进程调度预备开发

引言

  • 前面我们仅实现了两个任务的切换，现在我们要考虑 n 个任务该怎么处理

多任务设计

  • 面对 n 个任务的情况，我们自然就想到了下图这种多任务设计方式，每个任务执行一定的时间，然后切换到下一个任务，当所有任务都执行过后，再回到第一个任务执行

循环链表

  • 根据上图这种多任务设计方式，很显然，我们会采用循环链表这种数据结构来实现
  • 嗯~，先来实现链表
  • 创建一个 “utility” 文件夹，之后我们可以把一些公用的功能性代码放到这个文件夹下，就比如现在我们就把将要实现的链表操作的源文件放到其中
  • 创建 “list.c” 和 “list.h” 这两个文件，不用说，“list.h” 要放到 “include” 文件夹下，“list.c” 要放到 “utility” 文件夹下
  • 注意：由于新增文件夹和源文件，对应的 “BUILD.json” 文件别忘记修改
  • 关于链表的具体实现我就不细说了，通用的东西网上到处都是，我就不详细介绍代码实现了。下面是我实现的链表相关代码：list.c、list.h
  • 链表代码中涉及到 offsetof 宏和 container_of 宏，这两个宏在 linux 内核中也是被大量使用的，这里就简单说一下
  • 先来看 offsetof 宏，用来计算 type 结构体类型的数据结构中成员 member 的偏移量，把地址 0 强转成 type 类型，再取元素地址就得到了这个元素相对于 0 地址的偏移量，即该元素在结构体中的偏移量。其原型如下

#define offsetof(type, member) ((unsigned) &((type *)0)->member)

  • container_of 宏，用到了 offsetof 宏，其作用是在已知某结构体数据结构中元素的地址，求该结构体数据结构的起始地址。其原理就是取当前元素的地址，再减去该元素的偏移量（由 offsetof 宏得到）。其原型如下

#define container_of(ptr, type, member) ({                  \

   const typeof( ((type *)0)->member ) *__mptr = (ptr);    \

   (type *)( (char *)__mptr - offsetof(type, member) );})

链表相关函数接口设计

  • 链表初始化
  • 函数名称: void ListInit(LIST* list)
  • 输入参数: LIST* list --链表
  • 输出参数: 无
  • 函数返回: 无
  • 在链表头插入一个节点
  • 函数名称: void ListAddHead(LIST* list, LIST_NODE* node)
  • 输入参数: LIST* list --链表; LIST_NODE* node --节点
  • 输出参数: 无
  • 函数返回: 无
  • 在链表尾插入一个节点
  • 函数名称: void ListAddTail(LIST* list, LIST_NODE* node)
  • 输入参数: LIST* list --链表; LIST_NODE* node --节点
  • 输出参数: 无
  • 函数返回: 无
  • 在 before 节点前插入一个 node 节点
  • 函数名称: void ListAddBefore(LIST_NODE* before, LIST* node)
  • 输入参数: LIST* before --链表; LIST_NODE* node --节点
  • 输出参数: 无
  • 函数返回: 无
  • 在 after 节点后插入一个 node 节点
  • 函数名称: void ListAddAfter(LIST_NODE* after, LIST_NODE* node)
  • 输入参数: LIST* after --链表; LIST_NODE* node --节点
  • 输出参数: 无
  • 函数返回: 无
  • 删除 node 节点
  • 函数名称: void ListDelNode(LIST_NODE* node)
  • 输入参数: LIST_NODE* node --节点
  • 输出参数: 无
  • 函数返回: 无
  • 把 old 节点替换成 new 节点
  • 函数名称: void ListReplaceNode(LIST_NODE* old, LIST_NODE* new)
  • 输入参数: LIST_NODE* old --节点; LIST_NODE* new --节点
  • 输出参数: 无
  • 函数返回: 无
  • 判断 node 节点是否是链表最后的节点
  • 函数名称: BOOL ListIsLast(LIST* list, LIST_NODE* node)
  • 输入参数: LIST* list --链表; LIST_NODE* node --节点
  • 输出参数: 无
  • 函数返回: 0:否; 1:是
  • 判断链表是否为空
  • 函数名称: BOOL ListIsLast(LIST* list, LIST_NODE* node)
  • 输入参数: LIST* list --链表
  • 输出参数: 无
  • 函数返回: 0:否; 1:是

队列

  • 有了链表了，干脆把队列也实现一下吧
  • 队列依托于链表，特点先进先出，具体实现也不详细介绍了，都是通用的东西，代码见：queue.c、queue.h
  • 记得修改 “BUILD.json”

队列相关函数接口设计

  • 队列初始化
  • 函数名称: void QueueInit(QUEUE* queue)
  • 输入参数: QUEUE* queue --队列
  • 输出参数: 无
  • 函数返回: 无
  • 在队列尾插入一个节点
  • 函数名称: void QueueAdd(QUEUE* queue, QUEUE_NODE* node)
  • 输入参数: QUEUE* queue --队列; QUEUE_NODE* node --节点
  • 输出参数: 无
  • 函数返回: 无
  • 从队列头取出一个节点
  • 函数名称: QUEUE_NODE* QueueRemove(QUEUE* queue)
  • 输入参数: QUEUE* queue --队列
  • 输出参数: 无
  • 函数返回: 取出的节点
  • 队列是否为空
  • 函数名称: BOOL QueueIsEmpty(QUEUE* queue)
  • 输入参数: QUEUE* queue --队列
  • 输出参数: 无
  • 函数返回: 0:否; 1:是
  • 队列是否为空
  • 函数名称: BOOL QueueIsEmpty(QUEUE* queue)
  • 输入参数: QUEUE* queue --队列
  • 输出参数: 无
  • 函数返回: 队列长度

测试链表与队列

  • 已就绪，开始实现进程调度吧
  • 先别急着直接实现调度，分步实现，先测试一下链表及队列的功能，测试代码见：main.c
  • 先参照 TASK A 多创建几个任务，就 4 个吧
// TASK A
TASK taskA = {0};     // 任务对象
U08 taskA_stack[512];   // 任务私有栈
void TaskAFunc(void)    // 任务执行函数
{
    static U32 count = 0;
    while(1)
    {
        if(count++ % 100000 == 0)
        {
            static U32 j = 0;
            asm volatile("cli");
            SetCursorPos(0, 6);
            printk("TASK A: %d\n", j++); 
            asm volatile("sti");
        }  
    }
}
// TASK B
...(省略)
// TASK C
...(省略)
// TASK D
...(省略)
  • 有了这 4 个任务对象，接下来创建一个任务链表以及实现一个任务链表节点的结构体类型
typedef struct TASK_LIST_NODE
{
    LIST_NODE     listNode;
    TASK*         task;
} TASK_LIST_NODE;
LIST TASK_LIST;
• 创建 4 个任务链表节点对象并插入任务链表
// 任务节点 A
static TASK_LIST_NODE taskListNodeA;
taskListNodeA.task = &taskA;
ListAddHead(&TASK_LIST, (LIST_NODE *)&taskListNodeA);
// 任务节点 B
static TASK_LIST_NODE taskListNodeB;
taskListNodeB.task = &taskB;
ListAddHead(&TASK_LIST, (LIST_NODE *)&taskListNodeB);
// 任务节点 C
...(省略)
// 任务节点 D
...(省略)
  • 遍历任务节点，打印每个任务节点中的任务名
LIST_NODE* pListNode = NULL;
LIST_FOR_EACH(&TASK_LIST, pListNode)
{
    TASK_LIST_NODE* nodeTmp = (TASK_LIST_NODE *)LIST_NODE(pListNode,  TASK_LIST_NODE, listNode);
    printk("%s\n", nodeTmp->task->name);
}
  • 删除最后一个节点，然后再遍历打印任务节点中的任务名
ListDelNode(TASK_LIST.prev);   // 删掉最后一个
LIST_FOR_EACH(&TASK_LIST, pListNode)
{
    TASK_LIST_NODE* nodeTmp = (TASK_LIST_NODE *)LIST_NODE(pListNode,  TASK_LIST_NODE, listNode);
    printk("%s\n", nodeTmp->task->name);
}
  • 链表测试就到这里，下面测试队列
  • 依旧使用上面创建的 4 个任务对象 A B C D，创建一个任务队列以及实现一个任务队列节点的结构体类型
typedef struct TASK_QUEUE_NODE
{
    LIST_NODE     listNode;
    TASK*         task;
} TASK_QUEUE_NODE;
QUEUE TASK_QUEUE;
  • 创建 4 个任务队列节点对象并插入任务队列
// 任务节点 A
static TASK_QUEUE_NODE taskQueueNodeA;
taskQueueNodeA.task = &taskA;
QueueAdd(&TASK_QUEUE, (QUEUE_NODE *)&taskQueueNodeA);
// 任务节点 B
static TASK_QUEUE_NODE taskQueueNodeB;
taskQueueNodeB.task = &taskB;
QueueAdd(&TASK_QUEUE, (QUEUE_NODE *)&taskQueueNodeB);
// 任务节点
...(省略)
// 任务节点 D
...(省略)
  • 从任务队列中获取任务节点并打印任务名
QUEUE_NODE* pQueueNode = NULL;
while(TASK_QUEUE.length)
{
    QUEUE_NODE* nodeTmp = QueueRemove(&TASK_QUEUE);
    TASK_QUEUE_NODE* queueNodeTmp = (TASK_QUEUE_NODE *)QUEUE_NODE(nodeTmp, TASK_QUEUE_NODE, listNode);
    printk("%s\n", queueNodeTmp->task->name);
}
•

看一下测试效果

进程调度实现

  • 该准备的都准备了，现在就直接实现进程调度吧
  • 首先我们创建 “schedule.c” 和 “schedule.h” 文件专门用于调度代码，新增工程文件时对应的 “BUILD.json” 文件也要跟着修改
  • 使用相关代码见：schedule.c、schedule.h、main.c、task.c、task.h
  • 我们把 0x20 号中断服务程序的逻辑函数 Int0x20Handle 放到 “schedule.c” 中，优化一下这个函数，把调度具体实现单独放到 schedule 函数中实现
void Int0x20Handle(void)
{
    static U32 count = 0;
    if(count++ % 5 == 4)
    {
        schedule();
    }
    write_m_EOI();  
}
  • 进程调度函数接口设计
  • 函数名称: void schedule(void)
  • 输入参数: 无
  • 输出参数: 无
  • 函数返回: 无
  • 其它说明：从任务链表尾取一个节点，找到绑定的任务对象，删除该节点，然后再次插入任务链表头，这样就形成了循环
  • schedule 函数实现如下，其实现原理是从任务链表 TASK_LIST 的末尾取出一个节点然后从链表中删除该节点，再将该节点插入链表头。current_task 指向到这个节点中的 task 对象，待中断返回恢复上下文时将跳转到 current_task 指向的任务执行
void schedule(void)
{
    if(!ListIsEmpty(&TASK_LIST))
    {
        // 取出任务链表 TASK_LIST 的末尾节点
        LIST_NODE* pListNode = TASK_LIST.prev;
        TASK_LIST_NODE* nodeTmp = (TASK_LIST_NODE *)LIST_NODE(pListNode,  TASK_LIST_NODE, listNode);
        current_task = nodeTmp->task;
        // 删除 TASK_LIST 链表的末尾节点
        ListDelNode(TASK_LIST.prev);
        // 在 TASK_LIST 链表头插入节点
        ListAddHead(&TASK_LIST, pListNode);
        TSS* tss = (TSS*)(*(U32*)TSS_ENTRY_ADDR);                           // 找到 TSS
        tss->esp0 = (U32)(&(current_task->reg)) + sizeof(current_task->reg);    // TSS.esp0 指向任务上下文数据结构 reg 的末尾
        current_reg = (U32)(&current_task->reg);                                // current_reg 指向任务上下文数据结构 reg 的起始位置
    }
}
  • 结束，展示一下最终执行效果

  • 最后补充一点，虽然实现了想要的结果，但是仍有很多需要优化的地方，比如我们并没有考虑效率，不过呢，本章节就暂时只实现功能，后面章节我们再对调度实现进行优化

一个优化

  • 目前程序有个小 bug，那就是当第一个任务还没有创建时，此时如果发生了 0x20 号时钟中断，中断服务程序依然会保存上下文和恢复上下文，而此时没有任何任务，上下文也是不存在的，那么程序就会运行崩溃
  • 有关代码见：8259A.asm、8259A.h、task.c、
  • 我们在 8259A 驱动初始化时把 0x20 号中断屏蔽掉
pic_init:
    ...
    ; 默认屏蔽 0x20 号时钟中断
    call read_m_IMR
    or al, 00000001b
    call write_m_IMR
    ...
  • 等到启动任务时再取消屏蔽
; 取消屏蔽 0x20 号时钟中断（在 8259A.asm 中）
enable_int0x20:
    push ebp
    mov ebp, esp
    call read_m_IMR
    and al, 11111110b
    call write_m_IMR
    leave
    ret
E_RET TaskStart(TASK* task0)
{
    ...

   

   enable_int0x20();       // 取消屏蔽 0x20 号时钟中断

   asmvolatile("sti");    // 开中断

   SWITCH_TO(task0);       // 切换到 TASK0 执行

   ...

}

  • 注意在启动任务的代码中有 asm volatile("sti") 这条命令，跳转到任务前必须开外部中断，不然系统会死在任务 0 中


文章标签：
调度
测试技术
Linux
稀风
目录
相关文章
我不是游客20240119
|
15天前
|
算法 调度 Python
深入理解操作系统：进程调度的奥秘
【8月更文挑战第4天】操作系统是计算机系统的核心，其中进程调度是其重要的组成部分。本文将深入探讨进程调度的原理和实现，包括进程调度的目标、常用的调度算法以及如何在实际中应用这些知识。我们将通过代码示例来展示进程调度的具体实现，帮助读者更好地理解和掌握这一关键技术。
我不是游客20240119
28 3
历年考试不作弊
|
5天前
|
算法 调度
操作系统中的进程管理与调度
【8月更文挑战第14天】在现代计算机系统中，操作系统扮演着至关重要的角色。它不仅负责管理硬件资源，还提供了进程管理的机制来协调多个程序的执行。本文将深入探讨操作系统如何通过进程管理与调度来优化资源使用和提高系统响应性。我们将从进程的概念出发，分析进程状态转换、进程调度算法及其对系统性能的影响。通过理解这些概念，读者将能够更好地把握操作系统的核心原理及其在实际场景中的应用。
历年考试不作弊
4 1
历年考试不作弊
|
17天前
|
算法 Linux 调度
探索进程调度：Linux内核中的完全公平调度器
【8月更文挑战第2天】在操作系统的心脏——内核中，进程调度算法扮演着至关重要的角色。本文将深入探讨Linux内核中的完全公平调度器（Completely Fair Scheduler, CFS），一个旨在提供公平时间分配给所有进程的调度器。我们将通过代码示例，理解CFS如何管理运行队列、选择下一个运行进程以及如何对实时负载进行响应。文章将揭示CFS的设计哲学，并展示其如何在现代多任务计算环境中实现高效的资源分配。
历年考试不作弊
24 8
历年考试不作弊
|
18天前
|
算法 调度 Python
探索操作系统的心脏：深入理解进程调度
【8月更文挑战第1天】在数字世界的每一次跳动中，有一个不可见的手在操纵着一切——那就是进程调度。本文将带你穿梭于现代操作系统的核心，揭开进程调度机制的神秘面纱。通过直观的代码示例和详细的分析，我们将共同见证这一技术如何在微观层面影响宏观世界的运行。让我们开始这场深入操作系统内核的探险之旅吧！
历年考试不作弊
27 9
shuj
|
19天前
|
算法 调度
探索操作系统的心脏：深入理解进程调度
【7月更文挑战第31天】在数字世界的脉络中，操作系统扮演着至关重要的角色，它如同一台精密的时钟，确保了计算资源的高效与有序。本文将通过浅显的语言和实例代码，带领读者走进操作系统的核心——进程调度。我们将一起探索它是如何在多任务环境中协调资源、管理进程，并保证系统的流畅运行。文章不仅阐释进程调度的基本概念，还将通过实际代码示例揭示其背后的原理，使读者对这一复杂机制有一个清晰的认识。
shuj
27 10
请看我回答~
|
17天前
|
算法 调度 UED
深入理解操作系统：进程调度与优先级反转
【8月更文挑战第2天】在操作系统的心脏中，进程调度是维持多任务并发执行的关键机制。本文将通过一个简化的Python代码示例，揭示进程调度背后的逻辑，并探讨优先级反转现象及其对系统性能的影响。我们将从基础概念出发，逐步深入到进程调度算法的实现，最终讨论如何优化调度策略以提升系统响应性和效率。
请看我回答~
15 3
shuj
|
19天前
|
算法 Linux 调度
深入理解操作系统：进程调度与优先级
【7月更文挑战第31天】在计算机科学中，操作系统是连接用户和硬件的桥梁。它管理着计算机的资源，并确保资源的公平分配。本文将深入探讨操作系统的一个重要组成部分——进程调度，以及如何通过优先级来优化系统性能。我们将通过代码示例，展示如何在Linux系统中实现一个简单的优先级调度算法。
shuj
24 4
shuj
|
19天前
|
算法 大数据 调度
探索操作系统的心脏：进程调度算法
【7月更文挑战第31天】在数字世界的复杂编织中，操作系统扮演着枢纽的角色，而进程调度则是其跳动的心脏。本文将深入探讨几种常见的进程调度算法，通过代码示例揭示它们对系统性能的影响，并讨论如何根据应用场景选择恰当的调度策略。
shuj
16 1
叫个什么名字
|
25天前
|
算法 调度 UED
操作系统中的进程调度策略及其对系统性能的影响
本文深入探讨了操作系统中进程调度的多种策略，包括先来先服务、短作业优先、优先级调度、轮转与多级队列等，并分析了它们对系统性能的具体影响。通过比较不同调度算法的效率和公平性，本文旨在为系统管理员提供选择合适调度策略的依据，以优化系统的整体表现。
叫个什么名字
21 2
呆呆宝
|
26天前
|
Java 运维
开发与运维命令问题之使用jstack命令查看Java进程的线程栈如何解决
开发与运维命令问题之使用jstack命令查看Java进程的线程栈如何解决
呆呆宝
28 2