From fabf1fa1a086408edba946f15929d58e03f6f264 Mon Sep 17 00:00:00 2001 From: acevest Date: Fri, 14 Aug 2026 15:40:47 +0800 Subject: [PATCH] =?utf8?q?=E5=AE=9E=E7=8E=B0=E6=8C=89=E4=BC=98=E5=85=88?= =?utf8?q?=E7=BA=A7=E6=97=B6=E9=97=B4=E7=89=87=E8=BD=AE=E8=BD=AC=E8=B0=83?= =?utf8?q?=E5=BA=A6=E8=BF=9B=E7=A8=8B?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- include/sched.h | 17 +++++ include/task.h | 15 +++-- kernel/ap.c | 23 +++---- kernel/clock.c | 7 +- kernel/fork.c | 3 +- kernel/sched.c | 155 ++++++++++++++++++++++++++++++++++++++------- kernel/task_disk.c | 2 + kernel/task_init.c | 8 +-- kernel/task_root.c | 5 +- kernel/task_user.c | 2 +- kernel/waitq.c | 15 +++-- 11 files changed, 200 insertions(+), 52 deletions(-) diff --git a/include/sched.h b/include/sched.h index edb4945..559223f 100644 --- a/include/sched.h +++ b/include/sched.h @@ -23,6 +23,23 @@ #define FORK_USER 0 #define FORK_KRNL 1 +#define TASK_PRIORITY_LEVEL_KERNEL 0 +#define TASK_PRIORITY_LEVEL_SYSTEM 10 +#define TASK_PRIORITY_LEVEL_DRIVER 20 +#define TASK_PRIORITY_LEVEL_USER 80 + +#define TASK_PRIORITY_CNT 100 +#define TASK_PRIORITY_MIN 0 +#define TASK_PRIORITY_MAX (TASK_PRIORITY_CNT - 1) +#define READYQ_BITS_PER_WORD 32 +#define READYQ_BITMAP_WORD_CNT ((TASK_PRIORITY_CNT + READYQ_BITS_PER_WORD - 1) / READYQ_BITS_PER_WORD) +typedef struct priority_readyq { + list_head_t lists[TASK_PRIORITY_CNT]; + uint32_t bitmap[READYQ_BITMAP_WORD_CNT]; +} priority_readyq_t; + +void task_reset_priority(int priority); + void schedule(); void set_need_schedule(); diff --git a/include/task.h b/include/task.h index 5b1d604..a5887a1 100644 --- a/include/task.h +++ b/include/task.h @@ -38,10 +38,11 @@ enum { #define TASK_NAME_SIZE 32 -#define TASK_MAX_PRIORITY 99 - #define TASK_MAGIC 0xAABBCCDD11223344 +// 每个时间片（quantum）包含的时钟滴答数；任务连续运行的上限 +#define TASK_TICKS_PER_QUANTUM 3 + #define NR_TASK_OPEN_CNT 32 typedef struct task_files { // 暂时先不用bitmap，直接线性搜索 @@ -56,8 +57,8 @@ typedef union task_union { uint32_t esp; uint32_t eip; - int ticks; - + // [0, 100) + // 0 最高 99 最低 int priority; pid_t pid; @@ -84,6 +85,10 @@ typedef union task_union { list_head_t ready_list; // 就绪队列 list_head_t waitq_list; + int ticks_left; // 时间片剩余 + + // 仅用于统计 + uint32_t st_ticks; uint32_t sched_cnt; // 被调度换上CPU的次数 uint32_t sched_keep_cnt; // 时间片到了，但是没有被换出，又重新执行的次数 @@ -114,7 +119,7 @@ static inline pid_t sysc_getpid() { #define get_tsk_from_list(p) list_entry((p), Task, list) #define del_tsk_from_list(tsk) list_del((&tsk->list)) -void task_set_run(task_t* t); +// void task_set_run(task_t* t); void task_set_ready(task_t* t); void task_set_wait(task_t* t); diff --git a/kernel/ap.c b/kernel/ap.c index 36fb6d4..288c2bd 100644 --- a/kernel/ap.c +++ b/kernel/ap.c @@ -312,7 +312,7 @@ const char* task_state(unsigned int state) { void print_all_tasks() { extern task_t* monitor_tasks[]; - ap_printl(MPL_TASK_TITLE, " NAME STATE TK/PI REASON SCHED KEEP"); + ap_printl(MPL_TASK_TITLE, " NAME STATE LT/PI REASON TICKS SCHED KEEP"); for (int i = 0; i < 10; i++) { task_t* p = monitor_tasks[i]; @@ -321,16 +321,17 @@ void print_all_tasks() { continue; } - ap_printl(MPL_TASK_0 + p->pid, "%08x %-6s:%u %s %02d/%02u %-10s %-9u %-9u", - p, // - p->name, // - p->pid, // - task_state(p->state), // - p->ticks, // - p->priority, // - p->reason, // - p->sched_cnt, // - p->sched_keep_cnt // + ap_printl(MPL_TASK_0 + p->pid, "%08x %-6s:%u %s %02d/%02u %-10s %-9u %-9u %-9u", + p, // + p->name, // + p->pid, // + task_state(p->state), // + p->ticks_left, // + p->priority, // + p->reason, // + p->st_ticks, // + p->sched_cnt, // + p->sched_keep_cnt // ); } } diff --git a/kernel/clock.c b/kernel/clock.c index 209deea..7e1e7da 100644 --- a/kernel/clock.c +++ b/kernel/clock.c @@ -32,9 +32,12 @@ void clk_handler(unsigned int irq, pt_regs_t* regs, void* dev_id) { enable_clock_irq_delay = true; #endif - current->ticks--; + if (current->ticks_left > 0) { + current->ticks_left--; + } + current->st_ticks++; - if (current->ticks <= 0) { + if (current->ticks_left <= 0) { set_need_schedule(); } diff --git a/kernel/fork.c b/kernel/fork.c index 5f80536..dd36f00 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -83,8 +83,9 @@ int do_fork(pt_regs_t* regs, unsigned long flags) { tsk->pid = get_next_pid(); tsk->ppid = current->pid; tsk->priority = current->priority; - tsk->ticks = tsk->priority; + tsk->ticks_left = TASK_TICKS_PER_QUANTUM; + tsk->st_ticks = 0; tsk->sched_cnt = 0; tsk->sched_keep_cnt = 0; diff --git a/kernel/sched.c b/kernel/sched.c index bdafccc..1c50dea 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -45,7 +45,7 @@ void load_cr3(task_t* tsk) { extern pde_t __initdata init_pgd[PDECNT_PER_PAGE] __attribute__((__aligned__(PAGE_SIZE))); LIST_HEAD(all_tasks); -LIST_HEAD(ready_tasks); +// LIST_HEAD(ready_tasks); void init_root_task() { int i; @@ -54,8 +54,9 @@ void init_root_task() { root_task.ppid = 0; root_task.state = TASK_RUN; root_task.reason = "root"; - root_task.priority = 7; - root_task.ticks = root_task.priority; + root_task.priority = TASK_PRIORITY_MAX; + root_task.ticks_left = 1; + root_task.st_ticks = 0; root_task.vma_list = NULL; root_task.sched_cnt = 0; root_task.sched_keep_cnt = 0; @@ -84,9 +85,62 @@ void init_root_task() { kmem_cache_t* task_t_cache; +static priority_readyq_t g_priority_readyq; +void priority_readyq_init(priority_readyq_t* readyq) { + for (int i = 0; i < TASK_PRIORITY_CNT; i++) { + list_init(&readyq->lists[i]); + } + + for (int i = 0; i < READYQ_BITMAP_WORD_CNT; i++) { + readyq->bitmap[i] = 0; + } +} + +static void priority_readyq_set_bit(int priority) { + int item_index = priority / READYQ_BITS_PER_WORD; + int bit_index = priority % READYQ_BITS_PER_WORD; + g_priority_readyq.bitmap[item_index] |= (1U << bit_index); +} + +static void priority_readyq_clear_bit(int priority) { + int item_index = priority / READYQ_BITS_PER_WORD; + int bit_index = priority % READYQ_BITS_PER_WORD; + g_priority_readyq.bitmap[item_index] &= ~(1U << bit_index); +} + +void task_reset_priority(int priority) { + assert(priority >= TASK_PRIORITY_MIN); + assert(priority <= TASK_PRIORITY_MAX); + + task_t* task = current; + + if (task->priority == priority) { + return; + } + + // unsigned long eflags; + // irq_save(eflags); + + // 只有当前运行的Task才能调整priority + // 而它在调度器调度运行时已经从队列上取下了 + // 运行时不在任何队列上，所以只需要直接调整 + + current->priority = priority; + + // irq_restore(eflags); + + // 降低优先级应该触发调度 + // 这里简单实现，更复杂的实现，应该是看有没有比priority更高的任务在就绪队列上再决定要不要重新调度 + if (current->priority < priority) { + set_need_schedule(); + } +} + void setup_tasks() { INIT_LIST_HEAD(&all_tasks); - INIT_LIST_HEAD(&ready_tasks); + // INIT_LIST_HEAD(&ready_tasks); + + priority_readyq_init(&g_priority_readyq); init_root_task(); @@ -126,6 +180,40 @@ void context_switch(task_t* prev, task_t* next) { : "memory"); } +task_t* pick_next_task() { + int index = -1; // 代表所有READY队列都为空 + for (int i = 0; i < READYQ_BITMAP_WORD_CNT; i++) { + if (g_priority_readyq.bitmap[i] != 0) { + index = __builtin_ctz(g_priority_readyq.bitmap[i]); + + index += i * READYQ_BITS_PER_WORD; + break; + } + } + + if (index == -1) { + return NULL; + } + + assert(index >= 0); + assert(index < TASK_PRIORITY_CNT); + + // 对应的优先级队列必定不为空 + list_head_t* list = g_priority_readyq.lists + index; + assert(!list_empty(list)); + + // 返回队列头部第一个任务 + task_t* task = list_entry(list->next, task_t, ready_list); + assert(task != NULL); + assert(task->priority == index); + assert(task != &root_task); + assert(task->priority >= TASK_PRIORITY_MIN); + assert(task->priority <= TASK_PRIORITY_MAX); + assert(task->state == TASK_READY); + + return task; +} + void schedule() { task_t* prev = current; task_t* next = NULL; @@ -138,6 +226,23 @@ void schedule() { task_set_ready(prev); } + next = pick_next_task(); + + if (next == NULL) { + next = &root_task; + next->ticks_left = 1; + } else { + list_del_init(&next->ready_list); + next->state = TASK_RUN; + if (next->ticks_left <= 0) { + next->ticks_left = TASK_TICKS_PER_QUANTUM; + } + if (list_empty(g_priority_readyq.lists + next->priority)) { + priority_readyq_clear_bit(next->priority); + } + } + +#if 0 if (list_empty(&ready_tasks)) { next = &root_task; goto end; @@ -151,10 +256,7 @@ void schedule() { end: task_set_run(next); - - if (prev->ticks <= 0) { - prev->ticks = prev->priority; - } +#endif clear_need_schedule(); @@ -175,24 +277,24 @@ void add_task_for_monitor(task_t* tsk) { monitor_tasks[id] = tsk; } -void task_set_run(task_t* t) { - assert(t != NULL); +// void task_set_run(task_t* t) { +// assert(t != NULL); - // if (t == &root_task) { - // t->state = TASK_RUN; - // return; - // } +// // if (t == &root_task) { +// // t->state = TASK_RUN; +// // return; +// // } - assert(t->state == TASK_READY); +// assert(t->state == TASK_READY); - unsigned long eflags; - irq_save(eflags); +// unsigned long eflags; +// irq_save(eflags); - list_del_init(&t->ready_list); - t->state = TASK_RUN; +// list_del_init(&t->ready_list); +// t->state = TASK_RUN; - irq_restore(eflags); -} +// irq_restore(eflags); +// } void task_set_ready(task_t* t) { assert(t != NULL); @@ -203,11 +305,20 @@ void task_set_ready(task_t* t) { unsigned long eflags; irq_save(eflags); + + // if (!list_empty(&t->ready_list)) { list_del_init(&t->ready_list); } - list_add_tail(&t->ready_list, &ready_tasks); + + // + assert(t->priority >= TASK_PRIORITY_MIN); + assert(t->priority <= TASK_PRIORITY_MAX); + list_head_t* list = g_priority_readyq.lists + t->priority; + list_add_tail(&t->ready_list, list); + priority_readyq_set_bit(t->priority); t->state = TASK_READY; + irq_restore(eflags); } diff --git a/kernel/task_disk.c b/kernel/task_disk.c index 6babad7..7e21e3d 100644 --- a/kernel/task_disk.c +++ b/kernel/task_disk.c @@ -10,6 +10,7 @@ #include #include #include +#include // #include disk_request_queue_t disk_request_queue; @@ -66,6 +67,7 @@ void disk_request(disk_request_t* req) { } void disk_task_entry() { + task_reset_priority(TASK_PRIORITY_LEVEL_DRIVER + 7); while (1) { semaphore_down(&disk_request_queue.sem); diff --git a/kernel/task_init.c b/kernel/task_init.c index 985e31c..f5661c7 100644 --- a/kernel/task_init.c +++ b/kernel/task_init.c @@ -57,7 +57,7 @@ u16 disk_buf1[256] __attribute__((__aligned__(512))); u16 disk_buf2[256] __attribute__((__aligned__(512))); void taskA_entry() { - current->priority = 3; + task_reset_priority(97); while (1) { sysc_wait(197); @@ -86,7 +86,7 @@ void taskA_entry() { } void taskB_entry() { - current->priority = 13; + task_reset_priority(87); while (1) { sysc_wait(7); @@ -112,7 +112,7 @@ void taskB_entry() { } void taskC_entry() { - current->priority = 17; + task_reset_priority(83); while (1) { sysc_wait(100); @@ -126,7 +126,7 @@ void taskC_entry() { } void init_task_entry() { - current->priority = 10; + task_reset_priority(TASK_PRIORITY_LEVEL_SYSTEM + 0); // pt_regs_t *child_regs = ((pt_regs_t *)(TASK_SIZE + (unsigned long)current)) - 1; // child_regs->eflags |= 0x200; diff --git a/kernel/task_root.c b/kernel/task_root.c index 6ba709c..d29285a 100644 --- a/kernel/task_root.c +++ b/kernel/task_root.c @@ -62,7 +62,7 @@ void kernel_task(char* name, void* entry, void* arg) { // 从multiboot.S进入这里 void root_task_entry() { - printk("%08x %s %u %u\n", current, current->name, current->ticks, current->priority); + printk("%08x %s %u %u\n", current, current->name, current->ticks_left, current->priority); #if 0 pt_regs_t *regs = ((pt_regs_t *)(TASK_SIZE + (unsigned long)(&root_task))) - 1; @@ -80,7 +80,8 @@ void root_task_entry() { strcpy(current->name, "idle"); - current->priority = 1; + task_reset_priority(TASK_PRIORITY_MAX); + while (1) { asm("hlt;"); } diff --git a/kernel/task_user.c b/kernel/task_user.c index 6400c72..0c9162b 100644 --- a/kernel/task_user.c +++ b/kernel/task_user.c @@ -29,7 +29,7 @@ void flush_tlb() { } void user_task_entry() { - current->priority = 79; + task_reset_priority(TASK_PRIORITY_LEVEL_USER + 9); // ring3只占用一个page，页的起始位置放的是代码，页的末尾当栈用 // ring3的地址直接是物理地址 diff --git a/kernel/waitq.c b/kernel/waitq.c index 1502fe2..a985e61 100644 --- a/kernel/waitq.c +++ b/kernel/waitq.c @@ -32,8 +32,10 @@ void waitq_wakeup(waitq_t* waitq, int cnt) { assert(waitq != NULL); assert(cnt >= 0); - // 是否唤醒了任务，如果唤醒了任务就将当前任务标记为需要调度，以便新任务更快可以被调度 - bool woken_task = false; + // 是否唤醒了优先级更高的任务，如果唤醒就将当前任务标记为需要调度，以便新的高优先级任务更快可以被调度 + bool woken_higher_priority_task = false; + + bool woken = false; for (int i = 0; ((i < cnt) || (cnt == 0)); i++) { if (list_empty(&waitq->list)) { @@ -48,10 +50,15 @@ void waitq_wakeup(waitq_t* waitq, int cnt) { task_set_ready(task); - woken_task = true; + woken = true; + + // 当前任务优先级低于唤醒的任务 + if (current->priority > task->priority) { + woken_higher_priority_task = true; + } } - if (woken_task) { + if (woken_higher_priority_task || (woken && (current == &root_task))) { set_need_schedule(); } } -- 2.47.0