Little Kernel 代码走读(二)

作者:张佩】【原始链接:www.yiiyee.cn/blog

任务管理

LK支持多任务,并且也支持多核。多任务和调度,是LK内核最复杂的功能。一般的嵌入是系统,为了实现简单和便利部署的考虑,会把多任务实现得比较简单,比如uos这样的rtos系统便是了。但LK其实有比较丰富而全面的多任务支持的基础。这使得一些功能更全面的微内核系统比如Zircon,会选择基于它进行开发。

线程结构体

每个内核实现都会为线程创建一个结构体,用来管理任务的执行和维护线程状态。由于无受限的多任务支持能力,所以系统中的线程数量和功能,是不受限的。所以要有一种管理设施,能够对所有的任务进行无区别的管理(某些时候是有区别的,比如idle线程、init线程等,但很少)。这个模块就是内核的任务管理器。而它管理这些任务的抓手,就是线程结构体。

下面是LK定义的线程结构体:

typedef struct thread {
   int magic;
   struct list_node thread_list_node;

   /* active bits */
   struct list_node queue_node;
   int priority;
   enum thread_state state;
   int remaining_quantum;
   unsigned int flags;
#if WITH_SMP
   int curr_cpu;
   int pinned_cpu; /* only run on pinned_cpu if >= 0 */
#endif
#if WITH_KERNEL_VM
   vmm_aspace_t *aspace;
#endif

   /* if blocked, a pointer to the wait queue */
   struct wait_queue *blocking_wait_queue;
   status_t wait_queue_block_ret;

   /* architecture stuff */
   struct arch_thread arch;

   /* stack stuff */
   void *stack;
   size_t stack_size;

   /* entry point */
   thread_start_routine entry;
   void *arg;

   /* return code */
   int retcode;
   struct wait_queue retcode_wait_queue;

   /* thread local storage */
   uintptr_t tls[MAX_TLS_ENTRY];

   char name[32];
} thread_t;

成员变量magic

LK内核实现的一个特点是把内核的基本能力,通过一系列的内核对象进行暴露。或者也可以说LK内核是以内核对象为实现方式的。线程对象是这类基本对象之一。LK内核在实现内核对象的时候,有一个有趣的特点,是它:用奇异数作为对象类型的识别标识,同时也用来进行类型验证。

线程对象的奇异数是:#define THREAD_MAGIC (0x74687264) // 'thrd'

成员变量thread_list_node:

内核的任务管理器需要管理一系列的任务,所以需要这些任务能够自动地组织在一起,让内核管理器找到他们。所以线程结构体中包含了一个链表节点,而任务管理器处,也有一个全局节点名为thread_list。它通过这个全局节点,可以索引到系统中的所有线程结构体。

成员变量queue_node

此变量也是一个链表节点,任务管理器用它组成不同状态的执行队列。

成员变量priority/remaining_quantum

线程的优先级priority。这说明LK内核支持内核抢占,有实时调度的能力。

预定义的优先级如下:

/ *  HIGHEST_PRIORITY
*  DPC_PRIORITY
*  HIGH_PRIORITY
*  DEFAULT_PRIORITY
*  LOW_PRIORITY
*  IDLE_PRIORITY
*  LOWEST_PRIORITY */

线程的执行时间片remainging_quantum。这个变量和具体的调度策略有关。一般的调度策略会包含轮训机制,会在同等优先级的任务之间进行轮流调度,这样会有一个轮询时间片,当前任务把自己的预定时间片用完后,就把执行机会让给同等优先级的其他任务。

成员变量 state/flags:

线程状态state。线程的实现符合传统的任务状态机。可能的状态包括:suspend、ready、running、blocked、sleeping、death。

线程标志flags。这是和实现有关的线程标志,用来标注一些特征或者特殊的状态(不在由state表示的状态机之内的状态)。现在支持的标志有:detached、free_stack、free_struct、real_time、idle、debug_stack_bounds_check。

curr_cpu/pinned_cpu:

在支持SMP多核配置的平台上,此两个变量才有意义。否则它们都是0。者两个变量表示任务当前执行的cpu号,和cpu亲和性。

blocking_wait_queue/wait_queue_ret

线程的等待事件,以及等待结果。

stack/stack_size

线程的执行栈和大小。这里注意一点,栈的大小不是固定的,而是可以根据需求来自己设定的。和Linux内核创建内核线程时候的4K或8K的内核栈,以及1M用户栈的固定大小不同。

entry/arg

线程的入口函数和参数。

retcode/retcode_wait_queue

线程函数的返回值retcode,调用者将可以获取到这个值。

如果有外部执行者在等待本线程返回,则retcode_wait_queue是所有这些等待者的休息室,它们在这里侯着。在线程要退出(exit或detach)的时候,会一一地通知到休息室里的等待者。换句话说,线程对象本身是可等待的对象(通过函数thread_join),这两个变量就是LK内核实现线程等待的方法。

tls

和Linux类似,每个任务有一个线程相关的本地存储空间,可以存取若干个任务相关的本地数值。

name

线程是可命名的。

线程创建

线程创建是一件相对简单的操作,在LK中创建一个线程,要传入的参数包括:线程名(可为NULL,则无名),线程函数和参数,优先级,以及栈大小。需要特别注意的是栈大小,它是一个可指定的值,而非固定。但可以通过函数封装,来使用默认的栈大小。LK其实定义了一个默认的栈大小的。

/* stack size */
#ifdef CUSTOM_DEFAULT_STACK_SIZE
#define DEFAULT_STACK_SIZE CUSTOM_DEFAULT_STACK_SIZE
#else
#define DEFAULT_STACK_SIZE ARCH_DEFAULT_STACK_SIZE
#endif

thread_t *thread_create(const char *name, thread_start_routine entry, void *arg, int priority, size_t stack_size)

默认的栈size既可以用户在编译的时候通过编译选项来自定义,也可以使用系统默认的和架构相关的一个默认值,这个值是一个经验值,不同的架构对应的值有所不同,x86是8k,arm的普通版本是4k,arm-m版本(m代表embeded)是1k。

LK定义了一种简单的获取栈空间使用大小的方法,它在为线程创建栈空间的时候,往栈中填充了特征字符0x99。由于栈是从栈顶(高地址)开始使用的,所以在判断栈的使用size的时候,只需从栈低(低地址)开始,逐字节地比对是否等于0x99,如果不是,就表示此处已经用到了,就得到了栈的已使用的大小。

这个方法其实并不正确,因为线程的栈的使用是随时存在伸缩的。子函数返回后,栈空间将向栈顶回缩,但这一点通过特征字符0x99是不能体现出来的。所以thread_stack_used得到的其实是线程执行到目前位置,最多使用到的栈size,而不是当前实际使用的size。

size_t thread_stack_used(thread_t *t)

执行中的线程可以给自己改名字。由于只提供了修改“自己”名字的接口,而其它线程可能修改或设置线程名字的地方,只有创建的时候,其时线程函数是肯定没有执行的,这使得修改名字这个操作天然地不可能存在竞争。所以thread_set_name(const char *name)的实现就非常简单,直接把输入参数name以字符串拷贝的方式设置到线程结构体中去。

实时线程

LK实现的线程是有实时性支持的。实时线程通过flag位THREAD_FLAG_REAL_TIME 来标识。函数thread_is_realtime就通过判断这个标志位来实现的:

static bool thread_is_realtime(thread_t *t)
{
   return (t->flags & THREAD_FLAG_REAL_TIME) && t->priority > DEFAULT_PRIORITY;
}

这个函数除了判断实时标志位,还要求线程的优先级必须大于DEFAULT_PRIORITY。LK一共定义了32个优先级,并将这32个优先级大概地将其分成了4组。其中DEFAULT_PRIORITY恰好地位于最中间值为16。

    0 --------------8 -------------- 16 --------------- 24 -------------- 32
Lowest             Low               Default                 High               Highest

此外,IDLE_PRIORITY等于0,DPC_PRIORITY等于30。所以,如果要称为实时线程,需要其线程的优先级大于16才行。这一点需要创建线程时,创建者自己设置。因为在将线程设置为实时的时候,LK不会调整线程的优先级的。

status thread_set_real_time(thread_t *t)

这个函数只会修改标志位,不会判断线程的当前优先级而作调整。如果在线程创建的时候没有配置恰到的优先级,还可以由线程自己在运行时进行动态调整,这个函数是thread_set_priority

void thread_set_priority(int priority)

这个函数只能为自己调整优先级,不能调整其他的线程,即便父线程也做不到。所以父进程如果确实向把子线程配置为实时任务,就务必在创建的时候,配置正确的参数。

抢占

抢占有三个点会发生。

一个是周期的调度点,由任务调度器主动操作。但LK当前并没有在周期操作中进行优先级判断,表明LK目前的实时支持是不够的。

一个是当前线程的善意,让出执行权并让调度器重调度,这时候调度器会让高优先级的任务抢占当前任务的。这里有两个函数:thread_yieldthread_preempt

一个是当前线程的事件阻塞或满足,则将导致thread_blockthread_unblock被调用,也会导致重新调度。

调度

LK的实时线程实现方式属于FIFO(先到先出)的方式,先者通吃,直到主动放弃为止。这一点在实际使用的时候,需要注意,千万不要陷入到死循环中。后面我们会讲到,当前的lk调度策略起始是没有抢占的。唯有在重调度的时候,优先级才起到作用。

另外,如果一个实时线程在执行,它所在的cpu将被设置为realtime_cpu,这个状态被保存在全局结构体mp中。如果一个cpu属于realtime_cpu,在进行多核(mp)调度的时候会被剔除掉的。

如果处理器1是realtime_cpu,运行的线程为a;这时候我在处理器0上创建一个实时线程b并绑定到处理器1上,此时,如果配置它的优先级高于处理器1上的当前线程会怎么样呢?实时线程b是不能抢占实时线程a的,而要一直等到实时线程a主动放弃执行才有机会。并且b一旦执行,就将一直执行下去,直到主动放弃时线程a才有机会继续。

线程休眠

LK提供了一个典型的休眠函数,它的功能是让当前线程主动放弃执行权,线程状态被设置为SLEEPING;同时,创建一个新的延时计时器,设置其延时时间为休眠时间,让线程在指定的时间后重新被调度。

计时器的执行函数是一个固定的函数名为thread_sleep_handler(timer* timer, lk_time_t now, void* arg)。这个args就是之前进入休眠的线程结构体。

在这个handler函数中,进入休眠的线程将重新被设置为READY状态,并将其插入到调度队列的头部。

thread_t *t = (thread_t *)arg;

THREAD_LOCK(state); // 保护运行队列用
t->state = THREAD_READY;
insert_in_run_queue_head(t);
THREAD_UNLOCK(state);

这里面用到一个全局锁,这是一个大锁,保护全部的每个线程的状态操作,运行队列的操作,以及所有的任务管理的操作。这个锁的粒度比较大,所以一定存在优化的空间。

空闲线程

空闲线程的实现本质上是类似的,进行一些不紧急但不可少的工作,保持相关系统状态一定程度的持续性。比如系统平台的性能参数的收集,内核调度策略的调整,系统资源的管理策略调整等。

如果这些空闲工作都不需要的话,那么至少系统还有一件事情要做:等待中断到来,并且如果可以的话,让自己处于节能状态。对于x86系统而言,它调用hlt指令,让cpu进入节电状态,在中断到来是醒来;对于arm系统而言,它调用wfi指令,在低电状态下等待中断事件。

static void idle_thread_routine(void)
{
   for (;;)
       arch_idle();
}

boot strap线程

在系统启动的时候有一个特殊的boot strap线程,它是从cpu启动开始几代单传下来的执行流,典型的流程是:bios -> kernel loader -> kernel entry。LK也是类似的。它的kernel entry函数叫做lk_main,它是第一个被执行的c函数,此前还都是汇编的天下。

对于boot strap线程,它成立和生长在解放前,户口本都是民国或清朝时候办理的。线程管理的这套设施,确实解放后才有的设施。为了解决好管理这个问题,LK内核的办法是两点:

  1. 在boot strap线程完成了它的必要的系统初始化之工作后,创建了另外一个有新中国户口本的boot strap2线程(线程函数为bootstrap2),继续其工作
  2. boot strap线程本身随后就调用become_idle_thread方法执行idle_thread_routine,让自己闲下来。等到中断来临的时候,就顺理成章地把执行权移交给内核的任务管理器了。因为boot strap线程没有正式的线程身份,它将从此隐没在线程调度的星辰大海之中了,它所代表的boot strap执行绪,再不会出现。

线程等待

前面我们在讲thread结构体时,提到了retcode和retcode_wait_queue这两个变量。它们是用来实现线程等待的。和Linux下面的实现类似,LK实现了一个名为thread_join的线程等待接口。

status_t thread_join(thread_t *t, int *retcode, lk_time_t timeout)

它的三个参数,分别是等待对象t,期望得到的线程返回值retcode,以及超时时间,这个时间可以被设置成无限等待(即:INFINITE_TIME)。

对于被等待,LK实现了和pthread类似的处理方式,即支持“可合(joinable)”与“非合(detached)”两种方式。

第一种是可合线程,就是普通的线程等待方式,当线程结束后,会得到相关的线程返回值。这里要千万注意一点的是,如果线程是可合(joinable)的,则一定要有一个线程调用thread_join()这个合函数去等待它,否则此线程退出后,其相关的线程资源如stack、线程结构体等,就不会被释放,从而变成一个僵尸线程,很是恐怖。

第二种是非合线程,这种线程被认为不必被任何其他线程所等待或依赖,应该是独立存在的,并且要自己在结束的时候释放资源。所以,可通过调用线程方法thread_detach设置其线程状态THREAD_FLAG_DETACHED。如此,当其他线程试图调用thread_join等待此线程时,会立即返回并得到一个错误码ERR_THREAD_DETACHED,即线程不可等待。

每个线程在退出时,要主动地调用函数thread_exit来结束线程。对于非合线程,其资源被此函数释放掉;而可合线程则不会的,必须有一个外部线程通过调用thread_join方可也。

调度管理

我们前面讲过了空闲线程、boot strap线程还有实时线程了。这里再讲讲调度的事情。调度要有一个触发时机,一个天然的触发时机是时钟中断或者所谓的滴答周期。这使得调度管理器的逻辑,可以被周期性地执行。LK定义了一个名为thread_timer_tick的基于时钟的调度函数。LK的内核调度既可以是基于滴答周期的,也可以是动态周期的,即根据当前的调度需求,决定下一次调度的事件并通过一个timer来规划它。下面是这个函数的定义:

enum handler_return thread_timer_tick(struct timer *t, lk_time_t now, void *arg)

这个调度管理函数实现得比较简单。它的策略如下:

  1. 如果当前线程是实时或者idle线程,它是没有时间片限制的,会继续执行下去;除非有外部事件或者中断发生,并触发了重调度,否则当前线程会一直保持执行状态。lk在这里缺少了一些看上去必要的抢占逻辑。
  2. 如果当前线程是普通线程,它的时间片减少1个单位。如果时间片降低到0,就返回INT_RESCHEDULE,这会导致重调度操作。

这里面有一件颇值玩味的地方是,如果当前线程是idle线程,调度函数会持续地为他延长时间片,那么如果空闲线程永远执行的话,这个系统就不可能做任何“有效”的工作了。这看上去好像一个bug,但事实上,系统中只要还有一个线程存在,就不可能出现idle线程一直执行下去的情况。

我们便考虑系统中仅一个普通线程的情况。系统启动时,lk内核创建此普通线程,并主动调用一次重调度,则普通线程将获得执行权。此后,此普通线程如果被block,则执行权将被idle夺去。但block普通线程的时间一旦获得满足,会在时钟中断中处理unblock行为,并激发一次重调度。这样,执行权又将回到普通线程手中。

优先级

在一次重调度发生的时候,会选择一个新的线程执行。它这时候会根据优先级进行判断的。高者先得,低者晚得。实时线程的优先级是高的,且一旦其获得执行权,就没有时间片的概念,会一直执行下去,直到其主动放弃为止。

每个优先级有一个执行队列(run queue)。前者说过一共有32个优先级,这样就有32个执行队列。在实际执行的时候,未必每个执行队列都有有效的任务,这样就可以通过一个bitmap位图来识别之。

在寻找最高优先级的任务时,其过程就是挨个地检查执行队列的位图。如其是有效的运行队列,就检索其队列,看是否有一个运行在当前cpu上的线程(pinned_cpu)。如存在,则找到并返回;否则继续检索。如果最终都没有找到一个有效任务,则最后将返回空闲线程。

static thread_t *get_top_thread(int cpu)
{
   thread_t *newthread;
   uint32_t local_run_queue_bitmap = run_queue_bitmap;

   while (local_run_queue_bitmap) {
       /* find the first (remaining) queue with a thread in it */
       uint next_queue = sizeof(run_queue_bitmap) * 8 - 1 - __builtin_clz(local_run_queue_bitmap);

       list_for_every_entry(&run_queue[next_queue], newthread, thread_t, queue_node) {
#if WITH_SMP
           if (newthread->pinned_cpu < 0 || newthread->pinned_cpu == cpu)
#endif
          {
               list_delete(&newthread->queue_node);

               if (list_is_empty(&run_queue[next_queue]))
                   run_queue_bitmap &= ~(1<<next_queue);

               return newthread;
          }
      }

       local_run_queue_bitmap &= ~(1<<next_queue);
  }
   /* no threads to run, select the idle thread for this cpu */
   return idle_thread(cpu);
}

多核MP

LK是支持多核的。其实现的主干内容包含两方面:

  1. 启动时候,主处理器(BSP)将其它处理器(AP)作为secondary cpu进行硬件初始化,并在线程管理器就绪后,于各secondary cpu上执行一个idle线程;
  2. 运行时候的多核调度支持。线程可以通过设置pinned_cpu来决定让自己执行在哪个cpu上。注意,LK并不支持负载均衡,他的调度策略是简单的。所以开发者在线程创建的时候,要自己考虑负载的问题。为了支持运行时多核调度,lk提供了一个mp_reschedule内核函数。它通过IPI(inter processor interrupt)中断的方式,向目标处理器发送一个MP_IPI_RESCHEDULE消息。目标处理器收到这个中断后,就立刻在本地执行任务调度。

如此而已。

void mp_reschedule(mp_cpu_mask_t target, uint flags)
{
   /* mask out cpus that are not active and the local cpu */
   target &= mp.active_cpus;
   /* mask out cpus that are currently running realtime code */
   if ((flags & MP_RESCHEDULE_FLAG_REALTIME) == 0)
       target &= ~mp.realtime_cpus;
   target &= ~(1U << arch_curr_cpu_num());
   arch_mp_send_ipi(target, MP_IPI_RESCHEDULE);
}

IPI是处理器之间通信的通用方式,也就是a处理器发送一个中断给b处理器,并传递一个简单的消息。

待续…

7,822 total views, 4 views today

发表评论

电子邮件地址不会被公开。