手写操作系统(三十三)-锁实现
Dreams
|
139
|
0

3146 字
|
46 分钟

代码、内容参考来自于包括《操作系统真象还原》、《一个64位操作系统的设计与实现》以及《ORANGE’S：一个操作系统的实现》。

1.线程阻塞与唤醒

前面由于临界区代码的资源竞争（这里要访问的公共资源是显存），代码会出现问题。

这里我们通过锁来解决，然后锁通过信号量来实现。

对信号量的操作分为两种，up、down：

  • up操作：信号量+1，唤醒在此信号量上等待的线程。
  • down操作：判断信号量是否大于0，大于0则信号量-1，等于0则当前线程将自己堵塞，在此信号量上等待。

在二元信号量中，让线程通过锁进入临界区，大致流程如下：

  • 线程A进入临界区先通过 down 操作获得锁，此时信号量为0
  • 线程B进入临界区也通过 down 操作获得锁，但是信号量是0，则在此信号量上等待
  • 线程A从临界区出来后执行 up 操作释放锁，信号量值变成1，之后线程A将线程B唤醒
  • 线程B醒来后获得了锁，进入临界区

我们用二元信号量来实现锁，信号量down操作中提到了阻塞当前线程的功能，信号量up操作中提到了唤醒线程的功能，因此在实现锁之前，我们必须提前实现这两个功能。 我们用函数 thread_block 实现了线程阻塞，用函数 thread_unblock 实现了线程唤醒。

在/thread/thread.h添加下列函数定义

/* 当前线程将自己阻塞, 标志其状态为 stat. */
void thread_block(enum task_status stat);

/* 将线程 pthread 解除阻塞 */
void thread_unblock(struct task_struct* pthread);

 

在/thread/thread.c添加下列函数

/*当前线程将自己阻塞，标志其状态为stat*/
void thread_block(enum task_status stat){
    /*stat取值为TASK_BLOCKED,TASK_WAITING,TASK_HANGING，只有这三种状态才不会被调度*/
    ASSERT(((stat == TASK_BLOCKED) || (stat == TASK_WAITING) || (stat == TASK_HANGING)));
    enum intr_status old_status = intr_disable();
    struct task_struct* cur_thread = running_thread();
    cur_thread->status = stat;
    schedule();     //将当前线程换下CPU
    intr_set_status(old_status);    //待当前线程被解除阻塞后才能继续运行intr_set_status
}

/*将线程pthread接触阻塞*/
void thread_unblock(struct task_struct* pthread){
    enum intr_status old_status = intr_disable();
    ASSERT(((pthread->status == TASK_BLOCKED) || (pthread->status == TASK_WAITING) || (pthread->status == TASK_HANGING)));
    if(pthread->status != TASK_READY){
        ASSERT(!elem_find(&thread_ready_list,&pthread->general_tag));
        if(elem_find(&thread_ready_list,&pthread->general_tag)){
            PANIC("thread_unblock:blocked thread in ready_list\n");
        }
        list_push(&thread_ready_list,&pthread->general_tag);
        pthread->status = TASK_READY;
    }
    intr_set_status(old_status);
}

thread_block函数：

参数 stat是线程的状态，取值范围是 TASK_BLOCKED，TASK_WAITING 和 TASK_HANGING，它的取值为不可运行态，函数功能是将当前线程的状态置为 stat，从而实现了线程的阻塞。通过ASSERT做限制。

在系统中只有status为 TASK_RUNNING的线程才可以被添加到就绪队列thread_ready_list，才有机会上处理器运行。此状态的线程在调度器中会被重新加到就绪队列中。

在调度器 schedule 函数中，它会对当前线程的 status判断。若当前线程的 status为TASK_RUNNING，这说明当前线程只是时间片到了，此次调度并不是由于阻塞而引发的，因此会将其重新加入到就绪队列中并置其状态为TASK_READY为了不让其再被调度，必须将其status置为非TASK_RUNNING，也就是函数thread_block的参数stat。

于是获取当前线程，并置其 status为stat。之后便调用 schedule 重新调度下一任务。在调用schedule之后，下面的中断状态恢复代码 intr_set_status(old_status)本次便没机会执行了，只有在当前线程被唤醒后才会被执行到。

 

函数thread_block：

被阻塞的线程已无法运行，必须被其他线程唤醒，因此参数pthread指向的是目前已经被阻塞，又希望被唤醒的线程。函数thread_unblock是由当前运行的线程调用的，由它实施唤醒动作。被阻塞的线程，其状态肯定不是TASK_READY，不过还是if (pthread->status != TASK_READY)。为防止已经在就绪队列中的线程再次被添加，通过ASSERT判断。毕竟 ASSERT 只是调试期间用的，最后会把它去掉。但是这个判断我们还是需要的，因此由if结合PANIC宏再次判断这种重复添加的情况。

接着通过list_push将阻塞的线程重新添加到就绪队列，这里用list_push是将线程添加到就绪队列的队首，因此保证这个睡了很久的线程能被优先调度。最后再将线程的status置为TASK_READY，线程重新回到了就绪队列，它有再被调度的机会了，也就是实现了唤醒。

 

2.锁实现

/thread/sync.h代码如下：

#ifndef __THREAD_SYNC_H
#define __THREAD_SYNC_H
#include "list.h"
#include "stdint.h"
#include "thread.h"

/*信号量结构*/
struct semaphore{
    uint8_t value;
    struct list waiters;
};

/*锁结构*/
struct lock{
    struct task_struct* holder;     //锁的持有者
    struct semaphore semaphore;     //用二元信号量实现锁
    uint32_t holder_repeat_nr;      //锁的持有者重复申请锁的次数
};
/*函数声明*/
/*初始化信号量*/
void sema_init(struct semaphore* psema,uint8_t  value);

/*初始化锁plock*/
void lock_init(struct lock* plock);

/*P操作：信号量down操作*/
void sema_down(struct semaphore* psema);

/*V操作：信号量的up操作*/
void sema_up(struct semaphore* psema);

/*获取锁plock*/
void lock_acquire(struct lock* plock);

/*释放锁*/
void lock_release(struct lock* plock);
#endif

上面的代码定义了两个结构struct semaphore和struct lock。

struct semaphore为信号量结构，信号量要有初值，因此该结构中包含了成员value，对信号量进行down操作时，若信号量值为0就会阻塞线程，因此该结构中还包括了成员waiters，用它来记录在此信号量上等待(阻塞)的所有线程。

struct lock是锁结构。谁成功申请了锁，就应该记录锁被谁持有，这是用成员holder记录的，表示锁的持有者，我们的锁是基于信号量来实现的，因此锁结构中必须包含一个信号量成员，这里就是信号量结构体struct semaphore。将来此信号量的初值会被赋值为1,也就是用二元信号量实现锁。成员holder_repeat_nr用来累积锁的持有者重复申请锁的次数，释放锁的时候会参考此变量的值。原因是一般情况下我们应该在进入临界区之前加锁，但有时候可能持有了某临界区的锁后，在未释放锁之前，有可能会再次调用重复申请此锁的函数，这样一来，内外层函数在释放锁时会对同一个锁释放两次，为了避免这种情况的发生，用此变量来累积重复申请的次数，释放锁时会根据变量holder_repeat_nr的值来执行具体动作。

下面是thread/sync.c

#include "sync.h"
#include "list.h"
#include "global.h"
#include "debug.h"
#include "interrupt.h"

/*初始化信号量*/
void sema_init(struct semaphore* psema,uint8_t  value){
    psema->value = value;       //为信号量赋初值
    list_init(&psema->waiters); //初始化信号量的等待队列
}

/*初始化锁plock*/
void lock_init(struct lock* plock){
    plock->holder = NULL;
    plock->holder_repeat_nr = 0;
    sema_init(&plock->semaphore,1);
}

/*P操作：信号量down操作*/
void sema_down(struct semaphore* psema){
    /*关中断来保证原子操作*/
    enum intr_status old_status = intr_disable();        //关中断保证原子操作
    //当semaphore == 1时，down操作才成功返回，否则就阻塞
    while (psema->value == 0){      //若value==0，则表示semaphore已被别人持有
        ASSERT(!elem_find(&psema->waiters,&running_thread()->general_tag));
        if(elem_find(&psema->waiters,&running_thread()->general_tag))       //当前线程不应该已在信号量的waiters队列中
            PANIC("sema_down:thread blocked has been in waiters_list\n");
        //若信号量值 == 0，则当前线程把自己加入该锁的等待队列，然后阻塞自己
        list_append(&psema->waiters,&running_thread()->general_tag);
        thread_block(TASK_BLOCKED);
    }
    //若semaphore == 1或线程被唤醒，则执行下面代码
    psema->value--;
    ASSERT(psema->value == 0);
    intr_set_status(old_status);
}

/*V操作：信号量的up操作*/
void sema_up(struct semaphore* psema){
    enum intr_status old_status = intr_disable();
    ASSERT(psema->value == 0);
    if(!list_empty(&psema->waiters)){
        struct task_struct* thread_blocked = elem2entry(struct task_struct,general_tag,list_pop(&psema->waiters));
        thread_unblock(thread_blocked);
    }
    psema->value++;
    ASSERT(psema->value == 1);
    intr_set_status(old_status);
}

/*获取锁plock*/
void lock_acquire(struct lock* plock){
    //排除曾经自己已经持有锁但未释放的情况
    if(plock->holder != running_thread()){
        sema_down(&plock->semaphore);
        plock->holder = running_thread();
        ASSERT(plock->holder_repeat_nr == 0);
        plock->holder_repeat_nr = 1;
    }else{
        plock->holder_repeat_nr++;
    }
}

/*释放锁*/
void lock_release(struct lock* plock){
    ASSERT(plock->holder == running_thread());
    if(plock->holder_repeat_nr > 1){
        plock->holder_repeat_nr--;
        return;
    }
    ASSERT(plock->holder_repeat_nr == 1);
    plock->holder = NULL;
    plock->holder_repeat_nr = 0;
    sema_up(&plock->semaphore);
}

代码解释：

sema_init函数接受两个参数，psema是待初始化的信号量，value是信号量的初值，函数功能是将信号量psema初值初始化为value。锁是用信号量来实现的，因此锁的初始化中会调用函数sema_init。

函数lock_init接受一个参数，plock是待初始化的锁。 函数功能是将锁的持有者holder置为空，将持有者重复申请次数累积变量holder_repeat_nr置为0，并调用sema_init(&plock->semaphore, 1)将锁使用的信号量初值赋值为1，这样锁中的信号量就成为了二元信号量。

函数sema_down，它接受一个参数，psema是待执行down操作的信号量。 函数功能就是在信号量psema上执行个down操作。 为保证 down操作的原子性，在函数开头便通过 intr_disable关了中断。 信号量的值为1时，down操作才会成功返回，否则就在该信号上阻塞。这里通过while(psema->value==0)判断信号量是否为0，如果为0，就进入while的循环体，将自己添加到该信号量的等待队列中。 将自己阻塞，状态为TASK_BLOCKED。如果信号量不为0，也就是为1，或者之前为0，现在线程被唤醒后已经为1了，则将信号量减1，即psema->value–。 此时value的值应该为0，因此用ASSERT(psema->value==0)做判断。 这是为防止程序出错时，出现value大于 1 的情况。

函数sema_up接受一个参数，psema是待执行up操作的信号量。函数功能是将信号量的值加1，函数内部的操作也要保证原子性，因此在函数的开头也执行了intr_disable函数关中断。sema_up 是使信号量加1，这表示有信号资源可用了，也就是其他线程可以申请锁了，因此在信号量的等待队列 psema->waiters 中通过 list_pop 弹出队首的第一个线程，并通过宏 elem2entry 将其转换成 PCB， 存储到thread_blocked中。然后通过thread_unblock(thread_blocked)将此线程唤醒。在将线程唤醒后，接下来将信号量值加 1，即代码 psema->value++。最后通过 intr_set_status(old_status)恢复之前的中断状态。

函数lock_acquire接受一个参数，plock是所要获得的锁，函数功能是获取锁plock。有时候，线程可能会嵌套申请同一把锁，这种情况下再申请锁，就会形成死锁，即自己在等待自己释放锁。因此，在函数开头先判断自己是否已经是该锁的持有者，即代码if(plock->holder!=running_thread())。如果持有者已经是自己，就将变量holder_repeat_nr++，然后函数返回。如果自己尚未持有此锁的话，通过 sema_down(&plock->semaphore)将锁的信号量减1，当然在sema_down中有可能会阻塞，不过早晚会成功返回的。成功后将当前线程记为锁的持有者，即plock->holder=running_thread()，然后将holder_repeat_nr置为1，表示第1次申请了该锁。

函数lock_release功能是释放锁plock，只接受一个参数，plock指向待释放的锁，当前线程应该是锁的持有者，所以用ASSERT判断了一下。如果持有者的变量holder_repeat_nr大于1，这说明自已多次申请该锁，此时还不能真正将锁释放，因此只是将holder_repeat_nr–，随后返回。如果锁持有者的变量holder_repeat_nr为1，说明现在可以释放锁了，通过代码plock->holder = NULL将持有者置空，随后将holder_repeat_nr置为0，最后通过”sema_up(&plock->semaphore)”将信号量加1，锁被真正释放。

注意，要把持有者置空语句“plock->holder = NULL”放在 sema_up 操作之前。原因是释放锁的操作并不在关中断下进行，有可能会被调度器换下处理器。若sema_up操作在前的话，sema_up会先把value置1，若老线程刚执行完sema_up，还未执行”plock->holder=NULL”便被换下处理器,，新调度上来的进程有可能也申请了这个锁，value为1，因此申请成功，锁的持有者plock->holder将变成这个新进程的PCB，假如这个新线程还未释放锁又被换下了处理器，老线程又被调度上来执行，它会继续执行“plock->holder =NULL”，将持有者置空，这就乱了。

 

3.用锁实现终端输出

在我们的系统中没有复杂的显卡寄存器操作，我们只有一个终端，为了让这一个屏幕上的内容井然有序，我们可以通过锁实现输出互斥。

/device/console.h

#ifndef __DEVICE_CONSOLE_H
#define __DEVICE_CONSOLE_H
#include "stdint.h"
/*初始化终端*/
void console_init(void);

/*获取终端*/
void console_acquire(void);

/*释放终端*/
void console_release(void);

/*在终端输出字符串*/
void console_put_str(char* str);

/*在终端中输出字符*/
void console_put_char(uint8_t char_asci);

/*在终端中输出16进制整数*/
void console_put_int(uint32_t num);
#endif

/device/console.c

#include "console.h"
#include "print.h"
#include "stdint.h"
#include "sync.h"
#include "thread.h"
static struct lock console_lock;    //控制台锁,必须是static的

/*初始化终端*/
void console_init(){
    lock_init(&console_lock);
}

/*获取终端*/
void console_acquire(){
    lock_acquire(&console_lock);
}

/*释放终端*/
void console_release(){
    lock_release(&console_lock);
}

/*在终端输出字符串*/
void console_put_str(char* str){
    console_acquire();
    put_str(str);
    console_release();
}

/*在终端中输出字符*/
void console_put_char(uint8_t char_asci){
    console_acquire();
    put_char(char_asci);
    console_release();
}

/*在终端中输出16进制整数*/
void console_put_int(uint32_t num){
    console_acquire();
    put_int(num);
    console_release();
}

这里就是调用文件中定义的console_lock终端锁。

初始化终端函数console_init、获取终端函数console_acquire和释放终端函数console_release 。

三个输出函数，console_put_str，console_put_char和console_put_int，它们分别是put_str、 put_char和put_int的封装，用于在终端中打印字符串、单个字符和十六进制整数。在输出前后增加了console_acquire去获取终端，console_release去释放终端，以此来实现互斥。

在 init_all中添加了console_init外

/kernel/init.c

#include "init.h"
#include "print.h"
#include "interrupt.h"
#include "../device/timer.h"
#include "memory.h"
#include "../thread/thread.h"
#include "console.h"

/*负责初始化所有模块*/
void init_all(){
    put_str("init_all\n");
    idt_init();     //初始化中断
    mem_init();
    thread_init();
    timer_init();   //初始化PIT
    console_init(); //控制台初始化最好放在开中断之前
}

 

把 main.c 中的字符串输出函数 put_str 统统改为通过终端函数 console_put_str

/kernel/main.c

#include "print.h"
#include "init.h"
#include "thread.h"
#include "interrupt.h"
#include "console.h"

void k_thread_a(void*);
void k_thread_b(void*);

int main(void){
    put_str("I am kernel\n");
    init_all();

    thread_start("k_thread_a",31,k_thread_a,"argA ");
    thread_start("k_thread_b",8,k_thread_b,"argB ");

    intr_enable();  //打开中断，使时钟中断起作用

    while(1){
        console_put_str("Main ");
    }
    return 0;
}

/*在线程中运行函数*/
void k_thread_a(void* arg){
    /*用void来通知表示参数，被调用的函数知道自己需要什么类型的参数，自己转换再用*/
    char* para = arg;
    while (1){
        console_put_str(para);
    }
}

/*在线程中运行函数*/
void k_thread_b(void* arg){
    /*用void来通知表示参数，被调用的函数知道自己需要什么类型的参数，自己转换再用*/
    char* para = arg;
    while (1){
        console_put_str(para);
    }
}

 

修改makefile

BUILD_DIR = ./build
##用来存储生成的所有目标文件
ENTRY_POINT = 0xc0001500
AS = nasm
CC = gcc
LD = ld
LIB = -I lib/ -I lib/kernel/ -I lib/user/ -I kernel/ -I device/ -I thread/
ASFLAGS = -f elf
CFLAGS = -Wall -m32 -fno-stack-protector $(LIB) -c -fno-builtin -W -Wstrict-prototypes -Wmissing-prototypes
##-fno-builtin是告诉编译器不要采用内部函数 -Wstrict-prototypes是要求函数声明中必须有参数类型
## -Wmissing-prototypes要求函数必须有声明
LDFLAGS = -m elf_i386 -Ttext $(ENTRY_POINT) -e main -Map $(BUILD_DIR)/kernel.map


OBJS = $(BUILD_DIR)/main.o $(BUILD_DIR)/init.o $(BUILD_DIR)/interrupt.o \
    $(BUILD_DIR)/timer.o $(BUILD_DIR)/kernel.o $(BUILD_DIR)/print.o $(BUILD_DIR)/debug.o \
    $(BUILD_DIR)/string.o $(BUILD_DIR)/memory.o $(BUILD_DIR)/bitmap.o $(BUILD_DIR)/thread.o \
    $(BUILD_DIR)/switch.o $(BUILD_DIR)/list.o $(BUILD_DIR)/sync.o $(BUILD_DIR)/console.o
## OBJS用来存储所有目标文件名，不要用%.o，因为不能保证链接顺序

########## c代码编译 ##########

$(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h   \
                 lib/stdint.h kernel/init.h lib/string.h kernel/memory.h\
                 thread/thread.h kernel/interrupt.h device/console.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/init.o:kernel/init.c kernel/init.h lib/kernel/print.h lib/stdint.h \
    kernel/interrupt.h device/timer.h kernel/memory.h thread/thread.h device/console.h
    $(CC) $(CFLAGS) $< -o $@


$(BUILD_DIR)/string.o: lib/string.c lib/string.h \
    kernel/debug.h kernel/global.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/memory.o: kernel/memory.c kernel/memory.h \
                   lib/stdint.h lib/kernel/bitmap.h kernel/debug.h lib/string.h
    $(CC) $(CFLAGS) $< -o $@


$(BUILD_DIR)/bitmap.o: lib/kernel/bitmap.c lib/kernel/bitmap.h \
                   lib/string.h kernel/interrupt.h lib/kernel/print.h kernel/debug.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/interrupt.o:kernel/interrupt.c kernel/interrupt.h lib/stdint.h \
    kernel/global.h lib/kernel/io.h lib/kernel/print.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/timer.o:device/timer.c device/timer.h lib/stdint.h lib/kernel/io.h lib/kernel/print.h thread/thread.c \
    kernel/debug.h kernel/interrupt.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/debug.o:kernel/debug.c kernel/debug.h lib/kernel/print.h lib/stdint.h kernel/interrupt.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/thread.o: thread/thread.c thread/thread.h \
                   lib/stdint.h lib/string.h kernel/global.h kernel/memory.h \
                   kernel/debug.h kernel/interrupt.h lib/kernel/print.h lib/kernel/list.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/list.o: lib/kernel/list.c lib/kernel/list.h \
                 kernel/interrupt.h lib/stdint.h kernel/debug.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/sync.o: thread/sync.c thread/sync.h lib/kernel/list.h lib/stdint.h thread/thread.h lib/string.h \
    kernel/interrupt.h kernel/debug.h
    $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/console.o: device/console.c device/console.h lib/kernel/print.h lib/stdint.h thread/sync.h thread/thread.h
    $(CC) $(CFLAGS) $< -o $@

###########汇编代码编译############
$(BUILD_DIR)/kernel.o:kernel/kernel.S
    $(AS) $(ASFLAGS) $< -o $@

$(BUILD_DIR)/print.o:lib/kernel/print.S
    $(AS) $(ASFLAGS) $< -o $@

$(BUILD_DIR)/switch.o: thread/switch.S
    $(AS) $(ASFLAGS) $< -o $@

##########链接所有目标文件#############
$(BUILD_DIR)/kernel.bin:$(OBJS)
    $(LD) $(LDFLAGS) $^ -o $@

.PHONY: mk_dir hd clean all

mk_dir:
    if [ ! -d $(BUILD_DIR) ]; then mkdir $(BUILD_DIR); fi
###fi为终止符

hd:
    dd if=$(BUILD_DIR)/kernel.bin of=/bochs/bin/dreams.img bs=512 count=200 seek=9 conv=notrunc

clean:  ##将build目录下文件清空
    cd $(BUILD_DIR) && rm -f ./*

build:$(BUILD_DIR)/kernel.bin   ##编译kernel.bin，只要执行make build就是编译文件

all:mk_dir build hd
##依次执行伪目标mk_dir build hd，只要执行make all就是完成了编译到写入硬盘的全过程

 

结果如下：

字符串输出顺序如下：

“argA” -> “Main” -> “argB” -> “Main” -> “argA” -> “Main”,

 

4.参考

郑钢著操作系统真象还原

田宇著一个64位操作系统的设计与实现

丁渊著ORANGE’S：一个操作系统的实现

暂无评论

发送评论 编辑评论

 
 
 
 
 
   
 
  
  
   
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
  
上一篇
下一篇 
  推荐文章
手写JVM(二十九)-异常处理
 
手写JVM(二十八)-实现本地方法
 
手写JVM(二十七)-反射实现