4.process

内核3 进程管理

本篇我们主要来讨论一下进程的调度、同步、互斥。关于进程的创建以后再论。我们先来看最简单的情况：人为在内核中添加两个进程（first task和init task），并对这两个进程进行调度。通过这个例子可以让我们对进程的调度、同步以及互斥有一个直观的认识。

TSS段简介

TSS段（任务状态段）是intel cpu中用来描述一个任务的状态的数据结构。关于PCB和TSS的区别我暂时没找到什么相关的资料，应该可以当成一样的来理解。


通过TSS段结构以及第一个图可知，TSS实际上是一块内存区域，储存了一个任务的状态信息（硬件上下文）。
TR寄存器中存储了当前任务TSS段的选择子，通过查找选择子在GDT表中的表项来找到TSS描述符，进而找到TSS段在内存中的位置。因此当操作系统让CPU在多个进程之间切换时，核心工作就是保存上一程序的运行状态到自己的TSS中，再加载新任务的TSS到相应位置中。

typedef struct _tss_t
{
	uint32_t pre_link;
	uint32_t esp0, ss0, esp1, ss1, esp2, ss2;
	uint32_t cr3;
	uint32_t eip, eflags, eax, ecx, edx, ebx, esp, ebp, esi, edi;
	uint32_t es, cs, ss, ds, fs, gs;
	uint32_t ldt;
	uint32_t iomap;
} tss_t;    //tss描述符结构

下面我们以两个进程进行切换为例子来说明一下在进程切换的时候TSS，TSS选择子，TR寄存器发生了什么变化，CPU是怎么从第一个进程切换到第二个进程的。

1.初始化tss。

tss_init函数的作用是初始化一个任务状态段。下面说明这个函数中的一些关键的功能语句。

int tss_sel = gdt_alloc_desc();  //为tss分配一个空闲的GDT表项
task->tss_sel = tss_sel;  //将任务的选择子设置为分配好的表项
segment_desc_set(tss_sel, (uint32_t)&task->tss, sizeof(tss_t),
                     SEG_P_PRESENT | SEG_DPL0 | SEG_TYPE_TSS); //设置GDT表项内容

每个进程在初始化的时候都要初始化自己的TSS，这个函数会给进程分配一个GDT表项来存放任务描述符，任务描述符在进程切换的时候起到了作用。

2.实现任务切换

硬件机制的进程切换使用ljmpl指令。

void switch_to_tss(uint32_t tss_selector)
{
    far_jump(tss_selector, 0);
}

static inline void far_jump(uint32_t selector, uint32_t offset)
{
	uint32_t addr[] = {offset, selector};
	__asm__ __volatile__("ljmpl *(%[a])" ::[a] "r"(addr));
}

向ljmpl指令中传入要切换的任务的选择子，CPU就会根据传入的参数自动跳转到需要运行的任务。

由此可见任务切换的本质就是保存前一任务的运行状态，恢复下一任务的运行状态。当任务切换时，会将下一任务的selector传递给ljmpl指令，ljmpl指令将传入的selector存入TR寄存器，根据selector在GDT表中查找相应表项，根据表项内容定位到下一任务的TSS所在的内存空间，并将TSS的内容传递给CPU，这样就从前一个任务切换到下一个任务了。但是这么做也有一些问题。①TSS硬件切换机制效率不高。所以现代操作系统使用了软件切换机制来进行进程切换。②每次切换进程都需要手动切换，而且目前只能进行两个进程的切换，这时候就需要定时器+进程队列来对进程进行管理了。下面会详细说明一下如何对更多的进程切换进行调度，即进程的延时，同步，互斥。

进程的管理与延时

进程的管理与延时是非常重要的一部分内容，它可以让我们突破只能切换两个进程的限制，也可以方便我们管理所有进程的状态，同时我们也可以为进程添加延时，让进程延时运行。

进程的管理：

我们使用任务管理器对进程进行管理。任务管理器的结构如下图所示：

所以任务管理器可以看作是由三个链表为主体的大结构体，实例化为一个全局变量（一个内核有一个任务管理器就足够）。结构体定义如下：

typedef struct _task_manager_t
{
	task_t *curr_task; // 当前运行的任务

	list_t ready_list; // 就绪队列
	list_t task_list;  // 所有已创建任务的队列
	list_t sleep_list; // 延时队列

	task_t first_task; // 内核任务
	task_t idle_task;  // 空闲任务

	int app_code_sel; // 任务代码段选择子
	int app_data_sel; // 应用任务的数据段选择子
} task_manager_t;

以及相应的操作函数：

void task_manager_init(void);
void task_first_init(void);

初始化任务管理器就是将任务管理器结构体中的变量全部设置为初始值即可。

对于任务节点，我们可以将其定义为以下结构体。

typedef struct _task_t
{
	enum
	{
		TASK_CREATED,
		TASK_RUNNING,
		TASK_SLEEP,
		TASK_READY,
		TASK_WAITING,
		TASK_ZOMBIE,
	} state;

	char name[TASK_NAME_SIZE]; // 任务名字

	int pid;				// 进程的pid
	struct _task_t *parent; // 父进程
	uint32_t heap_start;	// 堆的顶层地址
	uint32_t heap_end;		// 堆结束地址
	int status;				// 进程执行结果

	int sleep_ticks; // 睡眠时间
	int time_slice;	 // 时间片
	int slice_ticks; // 递减时间片计数

	file_t *file_table[TASK_OFILE_NR]; // 任务最多打开的文件数量

	tss_t tss;		  // 任务的TSS段
	uint16_t tss_sel; // tss选择子

	list_node_t run_node;  // 运行相关结点
	list_node_t wait_node; // 等待队列
	list_node_t all_node;  // 所有队列结点
} task_t;

任务管理器的队列里面插入的就是任务结构体中的list_node_t类型变量。

进程的调度

我们使用基本的轮转法（RR）对进程进行调度。关于RR算法的原理，任何一本OS教材都会将其作为最基本的进程调度算法来详细解释。

就绪队列在进程调度的过程中十分重要。根据RR，向就绪队列链表中尾插 list_node_t 类型的任务结构体成员变量 run_node 代表任务已经就绪，加入到了就绪队列中。在结构体中还是用了一个枚举来表示进程当前的状态。比如:

void task_set_ready(task_t *task)
{
    if (task != &task_manager.idle_task)
    {
        list_insert_last(&task_manager.ready_list, &task->run_node);
        task->state = TASK_READY;
    }
}

将一个进程设置到就绪队列中时，它的state就应该改为TASK_READY，表明进程已经就绪。

现在有一个问题，就是就绪队列中的进程也必须要主动调用代码来进行进程的切换，这显然不是我们想看到的，我们要做的是让进程不主动调用切换的函数，也可以自动切换到下一个进程。为了达到这个目的，我们可以分成几步来做。

1.让进程主动放弃CPU

我们可以先让进程主动释放CPU，然后由释放CPU的函数来主动调用任务切换器，由任务切换器统一进行任务切换的工作。

int sys_yield(void)	//让进程主动放弃CPU
{
    irq_state_t state = irq_enter_protection();

    if (list_count(&task_manager.ready_list) > 1)
    {
        task_t *curr_task = task_current();
        task_set_block(curr_task);
        task_set_ready(curr_task);	//将当前进程移至就绪队列尾部

        task_dispatch();	//任务切换器
    }
    irq_leave_protection(state);

    return 0;
}

void task_dispatch(void)	//运行就绪队列中的下一个进程
{
    task_t *to = task_next_run();
    if (to != task_manager.curr_task)
    {
        task_t *from = task_manager.curr_task;

        task_manager.curr_task = to;
        task_switch_from_to(from, to);
    }
}

void task_switch_from_to(task_t *from, task_t *to)	//根据selector切换任务
{
    switch_to_tss(to->tss_sel);
}

void switch_to_tss(uint32_t tss_selector)
{
    far_jump(tss_selector, 0);
}

2.让进程按时间片运行

让进程按时间片运行，就可以让进程不显式释放CPU，通过时间片轮转进行中断，从而释放CPU资源进行进程切换的操作。首先我们要添加与时间有关的字段。

//在task结构体中添加
	int sleep_ticks; // 睡眠时间
	int time_slice;	 // 时间片
//在task_init中添加
    task->time_slice = TASK_TIME_SLICE_DEFAULT;
    task->slice_ticks = task->time_slice;

之后是在定时器中断函数中对当前进程的时间片进行递减操作。

void do_handler_timer(exception_frame_t *frame)
{
    sys_tick++;
    pic_send_eoi(IRQ0_TIMER);

    task_time_tick();
}

void task_time_tick(void)
{
    task_t *curr_task = task_current();
    if (--curr_task->slice_ticks == 0)
    {
        curr_task->slice_ticks = curr_task->time_slice;
        task_set_block(curr_task);
        task_set_ready(curr_task);
    }

    task_dispatch();
}

每次定时器产生中断时都会调用task_time_tick函数，这个函数会获取当前的进程并将其时间片减一，时间片为零之后恢复时间片并进行一次进程切换。这样我们就可以让进程运行特定的时间之后由定时器来自动进行进程的切换，无需进程主动调用切换函数。

3.临界资源及其保护方式

按照RR算法对进程进行调度，会在进程切换的时候出现一些问题。

可以看出，在first main没有打印完成时由于时间片为零，强制进行了进程切换，导致开始打印了init task的结果。这样的输出显然是错误的。关于临界资源和临界区，OS教材中有详细的解释。简单来说，临界资源是同一时刻只能被同一进程使用的资源，如全局变量、硬件资源等。临界区就是使用临界资源的代码。实现打印功能、向屏幕输出信息的串口就属于硬件临界资源，由于上述两个进程在同时访问了这个临界资源，导致输出出现了问题。

对临界资源的保护，OS教材上也提供了许多方法，比如关中断、利用Test-and-Set指令、利用Swap指令，信号量机制等。目前我们先采用最简单最暴力的方式：关中断。在一个进程进入临界区时禁用掉中断保证只有它自己一个进程可以访问临界资源，访问完毕后再开中断实现进程切换等中断操作。

irq_state_t irq_enter_protection(void)
{
    irq_state_t state = read_eflags();	//获取eflags寄存器的值
    irq_disable_global();
    return state;
}

void irq_leave_protection(irq_state_t state)
{
    write_eflags(state);
}

static inline uint32_t read_eflags(void)
{
	uint32_t eflags;

	__asm__ __volatile__("pushfl\n\tpopl %%eax" : "=a"(eflags));
	return eflags;
}

static inline void write_eflags(uint32_t eflags)
{
	__asm__ __volatile__("pushl %%eax\n\tpopfl" ::"a"(eflags));
}

state表示进入临界区前系统中断的开/关。如果系统之前的中断是关闭的，进程访问完临界资源之后也不应该将中断开启，所以要通过state来表示中断开关的状态。中断是否开启则是在eflags寄存器的IF标志位中，所以关中断前将eflags的值保存在state中，访问结束后将eflags的值恢复即可。对串口临界资源进行保护后，我们的输出就变成正常的了。但是关中断存在许多缺点，比如降低系统效率、滥用关中断权力等。之后会采用信号量的方法来代替关中断。

让进程延时运行

如果想要添加睡眠功能，让进程延时运行，就需要添加延时队列。将想要延时的队列添加在延时队列中睡眠，到达指定时间后进行唤醒并重新放回就绪队列中。之前我们已经在任务管理器中添加过延时队列和在任务结构体中添加过睡眠时间了。之后就是定义一些处理函数.

void sys_msleep(uint32_t ms)
{
    if (ms < OS_TICK_MS)
    {
        ms = OS_TICK_MS;
    }

    irq_state_t state = irq_enter_protection();

    // 从就绪队列移除，加入睡眠队列
    task_set_block(task_manager.curr_task);
    task_set_sleep(task_manager.curr_task, (ms + (OS_TICK_MS - 1)) / OS_TICK_MS);
    task_dispatch();
    irq_leave_protection(state);
}


void task_set_sleep(task_t *task, uint32_t ticks)
{
    if (ticks <= 0)
    {
        return;
    }

    task->sleep_ticks = ticks;
    task->state = TASK_SLEEP;
    list_insert_last(&task_manager.sleep_list, &task->run_node);
}

void task_set_wakeup(task_t *task)
{
    list_remove(&task_manager.sleep_list, &task->run_node);
}

我们需要让定时器来唤醒睡眠中的进程。所以完善task_time_tick函数：

void task_time_tick(void)
{
    task_t *curr_task = task_current();

    irq_state_t state = irq_enter_protection();
    if (--curr_task->slice_ticks == 0)
    {
        curr_task->slice_ticks = curr_task->time_slice;
        task_set_block(curr_task);
        task_set_ready(curr_task);
    }

    // 遍历延时队列，对时间片进行处理
    list_node_t *curr = list_first(&task_manager.sleep_list);
    while (curr)
    {
        list_node_t *next = list_node_next(curr);

        task_t *task = list_node_parent(curr, task_t, run_node);
        if (--task->sleep_ticks == 0)
        {
            task_set_wakeup(task);
            task_set_ready(task);
        }
        curr = next;
    }

    task_dispatch();
    irq_leave_protection(state);
}

这样在进程中调用sleep函数就可以让一个进程延时运行了，但是多个进程使用sleep函数还是会出现错误导致系统无法正常运行。当所有进程都在延时队列中时，就绪队列就是空的，进程切换所需要的指针就是一个无效指针，切换的时候就会导致系统崩溃。为了避免这种情况，我们要让指针一直是有效的，所以要添加一个空闲进程，当所有进程都放弃了CPU使用权时运行空闲进程，防止系统崩溃。

static task_t *task_next_run(void)
{
    if (list_count(&task_manager.ready_list) == 0)
    {
        return &task_manager.idle_task;
    }

    list_node_t *task_node = list_first(&task_manager.ready_list);
    return list_node_parent(task_node, task_t, run_node);
}

当进程发生切换，运行到

task_t *to = task_next_run();

时，如果就绪队列中没有进程，则返回空闲进程让指针接收。同时做出这样的修改

/**
 * @brief 将任务插入就绪队列
 */
void task_set_ready(task_t *task)
{
    if (task != &task_manager.idle_task)
    {
        list_insert_last(&task_manager.ready_list, &task->run_node);
        task->state = TASK_READY;
    }
}

/**
 * @brief 将任务从就绪队列移除
 */
void task_set_block(task_t *task)
{
    if (task != &task_manager.idle_task)
    {
        list_remove(&task_manager.ready_list, &task->run_node);
    }
}

保证空闲进程不主动插入到就绪队列，空闲进程不会因为时间片轮转而移出就绪队列。当睡眠的进程被唤醒添加到就绪队列时，任务切换函数就可以判断当前就绪队列非空，将CPU让给下一个排队等待的进程。

进程的同步与互斥

下面我们会实现信号量与互斥锁来完成进程的同步与互斥。同样OS教材上对信号量和互斥锁等概念有详细的解释。

信号量

我们用一个结构体来表示信号量，同样会有一些处理函数。

typedef struct _sem_t
{
    int count;        // 信号量计数
    list_t wait_list; // 等待的进程列表
} sem_t;
/**
 * 信号量初始化
 */
void sem_init(sem_t *sem, int init_count)
{
    sem->count = init_count;
    list_init(&sem->wait_list);
}

/**
 * 申请信号量
 */
void sem_wait(sem_t *sem)
{
    irq_state_t irq_state = irq_enter_protection();

    if (sem->count > 0)
    {
        sem->count--;
    }
    else
    {
        task_t *curr = task_current();
        task_set_block(curr);
        list_insert_last(&sem->wait_list, &curr->wait_node);
        task_dispatch();
    }

    irq_leave_protection(irq_state);
}

/**
 * 释放信号量
 */
void sem_notify(sem_t *sem)
{
    irq_state_t irq_state = irq_enter_protection();

    if (list_count(&sem->wait_list))
    {
        list_node_t *node = list_remove_first(&sem->wait_list);
        task_t *task = list_node_parent(node, task_t, wait_node);
        task_set_ready(task);

        task_dispatch();
    }
    else
    {
        sem->count++;
    }

    irq_leave_protection(irq_state);
}

/**
 * 获取信号量的当前值
 */
int sem_count(sem_t *sem)
{
    irq_state_t irq_state = irq_enter_protection();
    int count = sem->count;
    irq_leave_protection(irq_state);
    return count;
}

等信号时，如果信号计数为零，则进程放置到信号量结构体中的等待队列，否则计数器减一，进程继续执行。发信号时如果有进程等待则唤醒进程继续执行，否则增加信号量的计数（FIFO方式取出进程）。以first task和init task为例来说明一下信号量的用法。

①：两个进程要确定一个信号量sem并初始化，初始信号量为0。

②：first task打印完信息后发一个信号。

③：init task接收到信号才能打印信息。

这样就实现了这两个进程的同步按序运行，而且不会因为访问临界资源而产生冲突。

互斥锁

信号量也可以实现互斥功能，但是使用互斥锁是更好的方法。（但是互斥锁也是信号量的一种，与二元信号量类似）

typedef struct _mutex_t
{
    task_t *owner;
    int locked_count;
    list_t wait_list;
} mutex_t;

/**
 * 锁初始化
 */
void mutex_init(mutex_t *mutex)
{
    mutex->locked_count = 0;
    mutex->owner = (task_t *)0;
    list_init(&mutex->wait_list);
}

/**
 * 申请锁
 */
void mutex_lock(mutex_t *mutex)
{
    irq_state_t irq_state = irq_enter_protection();

    task_t *curr = task_current();
    if (mutex->locked_count == 0)
    {

        mutex->locked_count = 1;
        mutex->owner = curr;
    }
    else if (mutex->owner == curr)
    {

        mutex->locked_count++;
    }
    else
    {

        task_t *curr = task_current();
        task_set_block(curr);
        list_insert_last(&mutex->wait_list, &curr->wait_node);
        task_dispatch();
    }

    irq_leave_protection(irq_state);
}

/**
 * 释放锁
 */
void mutex_unlock(mutex_t *mutex)
{
    irq_state_t irq_state = irq_enter_protection();

    task_t *curr = task_current();
    if (mutex->owner == curr)
    {
        if (--mutex->locked_count == 0)
        {
            mutex->owner = (task_t *)0;
            if (list_count(&mutex->wait_list))
            {
                list_node_t *task_node = list_remove_first(&mutex->wait_list);
                task_t *task = list_node_parent(task_node, task_t, wait_node);
                task_set_ready(task);
                mutex->locked_count = 1;
                mutex->owner = task;

                task_dispatch();
            }
        }
    }

    irq_leave_protection(irq_state);
}

由于多个进程可能同时申请和释放互斥锁，所以要用关中断的方法来进行保护。当现在运行的进程申请互斥锁时，计数器会加一，同时将互斥锁的owner设置为当前进程。如果有重复上锁行为，只需要将计数器自增。如果申请上锁时计数器不为零，则将该进程移入等待队列并切换任务。释放时只有锁的拥有者才能将锁释放，如果等待队列中有进程的话也会将其放入就绪队列防止进程饥饿，同时将锁的权限转让给它。之后对临界资源的保护就可以使用互斥锁了。

到这里进程的大部分知识已经完结。后续关于进程的问题会在接下来的文章中继续讲解。