备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

进程调度预备开发

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

引言

  • 前面我们仅实现了两个任务的切换，现在我们要考虑 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
稀风
目录
相关文章
请看我回答~
|
10天前
|
算法 大数据 调度
深入理解操作系统：进程管理与调度策略
【4月更文挑战第27天】 在现代计算机系统的核心，操作系统扮演着至关重要的角色。它不仅管理硬件资源，还为应用程序提供必要的服务。其中，进程管理是操作系统的一个关键组成部分，它负责创建、执行以及终止进程。而进程调度策略则是确保系统高效运行的基石。本文将探讨操作系统中的进程管理机制及其调度策略，分析它们如何影响系统性能，并讨论当前的挑战及未来可能的发展方向。
请看我回答~
19 3
请看我回答~
|
7天前
|
算法 大数据 Linux
深入理解Linux内核的进程调度机制
【4月更文挑战第30天】操作系统的核心职能之一是有效地管理和调度进程，确保系统资源的合理分配和高效利用。在众多操作系统中，Linux因其开源和高度可定制的特点，在进程调度机制上展现出独特优势。本文将深入探讨Linux内核中的进程调度器——完全公平调度器（CFS），分析其设计理念、实现原理及面临的挑战，并探索未来可能的改进方向。
请看我回答~
20 0
请看我回答~
|
7天前
|
算法 Linux 调度
探索Linux内核：进程调度的奥秘
【4月更文挑战第30天】 在多任务操作系统中，进程调度是核心功能之一，它决定了处理器资源的分配。本文深入分析了Linux操作系统的进程调度机制，从调度器的基本原理到复杂的调度策略，以及它们如何影响系统性能和用户体验。通过剖析进程优先级、时间片分配以及实时性要求等方面，揭示了Linux如何在众多运行着的进程中做出快速而公平的决策，确保系统的高效与稳定运行。
请看我回答~
24 0
请看我回答~
|
7天前
|
算法 安全 大数据
深入理解操作系统之进程管理与调度
【4月更文挑战第30天】 在现代计算机系统中，操作系统的核心职能之一是高效地管理和调度进程，确保系统的稳定运行和资源利用的最优化。本文将深入探讨操作系统中的进程管理机制、进程调度算法以及它们在多核处理器环境下的实现。通过对不同操作系统中进程调度策略的比较，我们将揭示进程管理的关键技术和性能权衡，同时对未来操作系统设计中可能面临的挑战进行展望。
请看我回答~
10 0
请看我回答~
|
8天前
|
算法 Linux 调度
深入理解操作系统之进程调度策略
【4月更文挑战第29天】 在多任务操作系统中，进程调度策略是核心组件之一，它决定了处理器资源的分配。不同于常规的摘要重述内容，本文将通过分析不同的进程调度算法，揭示它们对系统性能的影响，以及在不同应用场景下的适用性。文章首先概述了操作系统中的进程概念和调度的重要性，然后详细探讨了几种主流的调度策略，包括先来先服务（FCFS）、短作业优先（SJF）、轮转调度（RR）及多级反馈队列（MFQ）。最后，文章评估了这些策略在现代操作系统中的应用，并提出了未来可能的发展趋势。
请看我回答~
12 0
mrq4nk6ni2neg
|
8天前
|
机器学习/深度学习 人工智能 算法
深入理解操作系统的进程调度策略
【4月更文挑战第29天】 本文旨在探讨操作系统中的核心机制之一——进程调度。通过对不同进程调度算法的比较分析，我们不仅揭示了各种算法背后的原理和设计理念，还讨论了它们在现代多核处理器环境下的性能表现和适用场景。文章首先回顾了进程调度的基本概念，随后详细阐述了几种经典调度策略，包括先来先服务、短作业优先以及时间片轮转等。接着，本文通过模拟实验对比了这些策略在不同工作负载下的表现，并提出了改进的调度方案。最后，文章展望了未来进程调度研究的方向，特别是在人工智能和机器学习领域的应用前景。
mrq4nk6ni2neg
10 3
请看我回答~
|
8天前
|
算法 安全 调度
深入理解操作系统：进程管理与调度策略
【4月更文挑战第29天】 在本文中，我们将深入探讨操作系统的核心组件之一——进程管理。首先，我们将解释进程的概念以及它们在操作系统中的作用。接着，我们将详细讨论不同的进程调度策略，包括先来先服务、短作业优先和轮转调度等。此外，我们还将分析这些调度策略的优缺点，并探讨它们在不同场景下的应用。最后，我们将展望操作系统进程管理的未来发展趋势。
请看我回答~
9 1
请看我回答~
|
9天前
|
算法 Linux 调度
深入理解操作系统的进程调度策略
【4月更文挑战第29天】 在多任务操作系统中，进程调度策略是核心组件之一，它直接关系到系统资源的利用效率及用户体验。本文将探讨现代操作系统中的几种主要进程调度算法——从简单的先来先服务（FCFS）到复杂的多级反馈队列（MLFQ）和公平共享调度（Fair Share Scheduling, FSS）。我们将剖析每种策略的工作原理、优势、局限性以及它们在实际操作系统中的应用实例。通过比较分析，文章旨在为读者提供一个全面的视角，以理解不同调度策略如何影响操作系统的性能和行为。
请看我回答~
9 0
历年考试不作弊
|
9天前
|
算法 调度 UED
深入理解操作系统中的进程调度策略
【4月更文挑战第28天】 在多任务操作系统中，进程调度策略是决定系统性能和响应能力的关键因素。本文将探讨操作系统中进程调度的基本原理、不同调度算法的特点及其适用场景，并通过分析比较它们的优缺点，提供一个全面的视角来理解操作系统如何管理运行中的进程。通过深入了解这些调度策略，读者可以更好地把握操作系统的行为模式，以及如何在特定应用中选择合适的调度策略以优化系统表现。
历年考试不作弊
8 1
历年考试不作弊
|
9天前
|
资源调度 算法 Linux
深入理解操作系统之进程管理与调度
【4月更文挑战第28天】 在现代计算机系统的核心，操作系统承担着资源管理和任务协调的重要职责。本文将深入探讨操作系统的心脏——进程管理及其调度机制。我们将剖析进程的概念、生命周期以及它们如何在多任务环境中被操作系统有效调度。文中不仅涉及理论模型，更通过实际案例分析现代操作系统如Linux和Windows在进程管理上的异同。此外，还将讨论如何通过优化调度算法来提升系统性能和响应速度，以及这些方法对未来操作系统设计的启示。
历年考试不作弊
6 1