从零到一手写操作系统(五、同步 2)linux的实现)

image.png

如果追忆会荡起涟漪,那么今天的秋红落叶和晴空万里都归你
https://aeneag.xyz
微信公众号:技术乱舞
艾恩凝

手写操作系统目录

同步

5.5)linux自旋锁与信号量的实现

5.5.1)原子

https://pic.aeneag.xyz/linux_kernel.pdf 46页

5.5.2)中断

linux中断代码,与前文讲的原理基本相同,就是进行了封装

 1//实际保存eflags寄存器
 2extern __always_inline unsigned long native_save_fl(void){
 3    unsigned long flags;
 4    asm volatile("# __raw_save_flags\n\t"
 5                 "pushf ; pop %0":"=rm"(flags)::"memory");
 6    return flags;
 7}
 8//实际恢复eflags寄存器
 9extern inline void native_restore_fl(unsigned long flags){
10    asm volatile("push %0 ; popf"::"g"(flags):"memory","cc");
11}
12//实际关中断
13static __always_inline void native_irq_disable(void){
14    asm volatile("cli":::"memory");
15}
16//实际开启中断
17static __always_inline void native_irq_enable(void){
18    asm volatile("sti":::"memory");
19}
20//arch层关中断
21static __always_inline void arch_local_irq_disable(void){
22    native_irq_disable();
23}
24//arch层开启中断
25static __always_inline void arch_local_irq_enable(void){ 
26    native_irq_enable();
27}
28//arch层保存eflags寄存器
29static __always_inline unsigned long           arch_local_save_flags(void){
30    return native_save_fl();
31}
32//arch层恢复eflags寄存器
33static  __always_inline void arch_local_irq_restore(unsigned long flags){
34    native_restore_fl(flags);
35}
36//实际保存eflags寄存器并关中断
37static __always_inline unsigned long arch_local_irq_save(void){
38    unsigned long flags = arch_local_save_flags();
39    arch_local_irq_disable();
40    return flags;
41}
42//raw层关闭开启中断宏
43#define raw_local_irq_disable()     arch_local_irq_disable()
44#define raw_local_irq_enable()      arch_local_irq_enable()
45//raw层保存恢复eflags寄存器宏
46#define raw_local_irq_save(flags)           \
47    do {                        \
48        typecheck(unsigned long, flags);    \
49        flags = arch_local_irq_save();      \
50    } while (0)
51    
52#define raw_local_irq_restore(flags)            \
53    do {                        \
54        typecheck(unsigned long, flags);    \
55        arch_local_irq_restore(flags);      \
56    } while (0)
57    
58#define raw_local_save_flags(flags)         \
59    do {                        \
60        typecheck(unsigned long, flags);    \
61        flags = arch_local_save_flags();    \
62    } while (0)
63//通用层接口宏 
64#define local_irq_enable()              \
65    do { \
66        raw_local_irq_enable();         \
67    } while (0)
68
69#define local_irq_disable()             \
70    do {                        \
71        raw_local_irq_disable();        \
72    } while (0)
73
74#define local_irq_save(flags)               \
75    do {                        \
76        raw_local_irq_save(flags);      \
77    } while (0)
78
79#define local_irq_restore(flags)            \
80    do {                        \
81        raw_local_irq_restore(flags);       \
82    } while (0)

5.5.3)自旋锁

linux实现原始自旋锁与前文大同小异

5.5.3.1)排队自旋锁

为什么要排队?搞清这个问题就明白了这个的由来

首先当多个进程获取同一个资源时,有一个获取了,后面的那些在等待,有先来的有后来的,一旦该资源释放了,那么下一个应该是谁获取这个资源呢?这并不确定,有时会造成早来等待的却最后获取资源,这就造成了不公平,排队自旋锁就是解决这个问题了。

 1static inline void __raw_spin_lock(raw_spinlock_t*lock){
 2int inc = 0x00010000;
 3int tmp;
 4__asm__ __volatile__(
 5"lock ; xaddl %0, %1\n" //将inc和slock交换,然后 inc=inc+slock
 6                        //相当于原子读取next和owner并对next+1
 7"movzwl %w0, %2\n\t"//将inc的低16位做0扩展后送tmp tmp=(u16)inc
 8"shrl $16, %0\n\t" //将inc右移16位 inc=inc>>16
 9"1:\t"
10"cmpl %0, %2\n\t" //比较inc和tmp,即比较next和owner 
11"je 2f\n\t" //相等则跳转到标号2处返回
12"rep ; nop\n\t" //空指令
13"movzwl %1, %2\n\t" //将slock的低16位做0扩展后送tmp 即tmp=owner
14"jmp 1b\n" //跳转到标号1处继续比较
15"2:"
16:"+Q"(inc),"+m"(lock->slock),"=r"(tmp)
17::"memory","cc"
18);
19}
20#define UNLOCK_LOCK_PREFIX LOCK_PREFIX
21static inline void __raw_spin_unlock(raw_spinlock_t*lock){
22__asm__ __volatile__(
23UNLOCK_LOCK_PREFIX"incw %0"//将slock的低16位加1 即owner+1
24:"+m"(lock->slock)
25::"memory","cc");
26}

要明白排队自旋锁的原理,一个owner+next 就是 lock 高16低16位,初始化为0,获取锁 next +1 ;并判断当前owner和next 是否相等,相等就获取资源,释放后,owner+1.那么下一个资源的next = 1,实际的next又+1,这时第二个owner = 1 保存的next =1 第二个进程获取资源,就是这样排队下去获取同一个资源。

5.5.3.2)尝试获取锁

当一个进程发现另一个进程已经拥有自己所请求的自旋锁时,就自愿放弃,转而做其它别的工作,并不想在这里循环等待,浪费自己的时间。这就是尝试获取锁。

 1static inline int __raw_spin_trylock(raw_spinlock_t*lock){
 2    int tmp;
 3    int new;
 4    asm volatile(
 5    "movl %2,%0\n\t"//tmp=slock
 6    "movl %0,%1\n\t"//new=tmp
 7    "roll $16, %0\n\t"//tmp循环左移16位,即next和owner交换了
 8    "cmpl %0,%1\n\t"//比较tmp和new即(owner、next)?=(next、owner)
 9    "jne 1f\n\t" //不等则跳转到标号1处 
10    "addl $0x00010000, %1\n\t"//相当于next+1
11    "lock ; cmpxchgl %1,%2\n\t"//new和slock交换比较    
12    "1:"
13    "sete %b1\n\t" //new = eflags.ZF位,ZF取决于前面的判断是否相等
14    "movzbl %b1,%0\n\t" //tmp = new
15    :"=&a"(tmp),"=Q"(new),"+m"(lock->slock)
16    ::"memory","cc");
17    return tmp;
18}
19int __lockfunc _spin_trylock(spinlock_t*lock){ 
20    preempt_disable();
21    if(_raw_spin_trylock(lock)){
22        spin_acquire(&lock->dep_map,0,1,_RET_IP_);
23        return 1;
24    }
25    preempt_enable();
26    return 0;
27}
28#define spin_trylock(lock) __cond_lock(lock, _spin_trylock(lock))

_spin_trylock 返回 1 表示尝试加锁成功,可以安全的地问共享资源了;返回值为 0 则表示尝试加锁失败,不能操作共享资源,应该等一段时间,再次尝试加锁。

5.5.4)信号量

信号量最大的优势是既可以使申请失败的进程睡眠,还可以作为资源计数器使用。

信号量数据结构:

1struct semaphore{
2    raw_spinlock_t lock;//保护信号量自身的自旋锁
3    unsigned int count;//信号量值
4    struct list_head wait_list;//挂载睡眠等待进程的链表
5};

具体实现代码:

 1static inline int __sched __down_common(struct semaphore *sem, long state,long timeout)
 2{
 3    struct semaphore_waiter waiter;
 4    //把waiter加入sem->wait_list的头部
 5    list_add_tail(&waiter.list, &sem->wait_list);
 6    waiter.task = current;//current表示当前进程,即调用该函数的进程
 7    waiter.up = false;
 8    for (;;) {
 9        if (signal_pending_state(state, current))
10            goto interrupted;
11        if (unlikely(timeout <= 0))
12            goto timed_out;
13        __set_current_state(state);//设置当前进程的状态,进程睡眠,即先前__down函数中传入的TASK_UNINTERRUPTIBLE:该状态是等待资源有效时唤醒(比如等待键盘输入、socket连接、信号(signal)等等),但不可以被中断唤醒
14        raw_spin_unlock_irq(&sem->lock);//释放在down函数中加的锁
15        timeout = schedule_timeout(timeout);//真正进入睡眠
16        raw_spin_lock_irq(&sem->lock);//进程下次运行会回到这里,所以要加锁
17        if (waiter.up)
18            return 0;
19    }
20 timed_out:
21    list_del(&waiter.list);
22    return -ETIME;
23 interrupted:
24    list_del(&waiter.list);
25    return -EINTR;
26
27    //为了简单起见处理进程信号(signal)和超时的逻辑代码我已经删除
28}
29//进入睡眠等待
30static noinline void __sched __down(struct semaphore *sem)
31{
32    __down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
33}
34//获取信号量
35void down(struct semaphore *sem)
36{
37    unsigned long flags;
38    //对信号量本身加锁并关中断,也许另一段代码也在操作该信号量
39    raw_spin_lock_irqsave(&sem->lock, flags);
40    if (likely(sem->count > 0))
41        sem->count--;//如果信号量值大于0,则对其减1
42    else
43        __down(sem);//否则让当前进程进入睡眠
44    raw_spin_unlock_irqrestore(&sem->lock, flags);
45}
46//实际唤醒进程 
47static noinline void __sched __up(struct semaphore *sem)
48{
49    struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list, struct semaphore_waiter, list);
50    //获取信号量等待链表中的第一个数据结构semaphore_waiter,它里面保存着睡眠进程的指针
51    list_del(&waiter->list);
52    waiter->up = true;
53    wake_up_process(waiter->task);//唤醒进程重新加入调度队列
54}
55//释放信号量
56void up(struct semaphore *sem)
57{
58    unsigned long flags;
59    //对信号量本身加锁并关中断,必须另一段代码也在操作该信号量
60    raw_spin_lock_irqsave(&sem->lock, flags);
61    if (likely(list_empty(&sem->wait_list)))
62        sem->count++;//如果信号量等待链表中为空,则对信号量值加1
63    else
64        __up(sem);//否则执行唤醒进程相关的操作
65    raw_spin_unlock_irqrestore(&sem->lock, flags);
66}

5.5.5)读写锁

041000.png

  1. 获取读锁时,锁值变量 lock 计数减去 1,判断结果的符号位是否为 1。若结果符号位为 0 时,获取读锁成功,即表示 lock 大于 0。
  2. 获取读锁时,锁值变量 lock 计数减去 1,判断结果的符号位是否为 1。若结果符号位为 1 时,获取读锁失败,表示此时读写锁被修改数据的进程占有,此时调用 read_lock_failed 失败处理函数,循环测试 lock+1 的值,直到结果的值大于等于 1。
  3. 获取写锁时,锁值变量 lock 计数减去 RW_LOCK_BIAS_STR,即 lock-0x01000000,判断结果是否为 0。若结果为 0 时,表示获取写锁成功。
  4. 获取写锁时,锁值变量 lock 计数减去 RW_LOCK_BIAS_STR,即 lock-0x01000000,判断结果是否为 0。若结果不为 0 时,获取写锁失败,表示此时有读取数据的进程占有读锁或有修改数据的进程占有写锁,此时调用 write_lock_failed 失败处理函数,循环测试 lock+0x01000000,直到结果的值等于 0x01000000。
 1//读写锁初始化锁值
 2#define RW_LOCK_BIAS     0x01000000
 3//读写锁的底层数据结构
 4typedef struct{
 5    unsigned int lock;
 6}arch_rwlock_t;
 7//释放读锁 
 8static inline void arch_read_unlock(arch_rwlock_t*rw){ 
 9    asm volatile(
10        LOCK_PREFIX"incl %0" //原子对lock加1
11        :"+m"(rw->lock)::"memory");
12}
13//释放写锁
14static inline void arch_write_unlock(arch_rwlock_t*rw){
15    asm volatile(
16        LOCK_PREFIX"addl %1, %0"//原子对lock加上RW_LOCK_BIAS
17        :"+m"(rw->lock):"i"(RW_LOCK_BIAS):"memory");
18}
19//获取写锁失败时调用
20ENTRY(__write_lock_failed)
21    //(%eax)表示由eax指向的内存空间是调用者传进来的 
22    2:LOCK_PREFIX addl  $ RW_LOCK_BIAS,(%eax)
23    1:rep;nop//空指令
24    cmpl $RW_LOCK_BIAS,(%eax)
25    //不等于初始值则循环比较,相等则表示有进程释放了写锁
26    jne   1b
27    //执行加写锁
28    LOCK_PREFIX subl  $ RW_LOCK_BIAS,(%eax)
29    jnz 2b //不为0则继续测试,为0则表示加写锁成功
30    ret //返回
31ENDPROC(__write_lock_failed)
32//获取读锁失败时调用
33ENTRY(__read_lock_failed)
34    //(%eax)表示由eax指向的内存空间是调用者传进来的 
35    2:LOCK_PREFIX incl(%eax)//原子加1
36    1:  rep; nop//空指令
37    cmpl  $1,(%eax) //和1比较 小于0则
38    js 1b //为负则继续循环比较
39    LOCK_PREFIX decl(%eax) //加读锁
40    js  2b  //为负则继续加1并比较,否则返回
41    ret //返回
42ENDPROC(__read_lock_failed)
43//获取读锁
44static inline void arch_read_lock(arch_rwlock_t*rw){
45    asm volatile(
46        LOCK_PREFIX" subl $1,(%0)\n\t"//原子对lock减1
47        "jns 1f\n"//不为小于0则跳转标号1处,表示获取读锁成功
48        "call __read_lock_failed\n\t"//调用__read_lock_failed
49        "1:\n"
50        ::LOCK_PTR_REG(rw):"memory");
51}
52//获取写锁
53static inline void arch_write_lock(arch_rwlock_t*rw){
54    asm volatile(
55        LOCK_PREFIX"subl %1,(%0)\n\t"//原子对lock减去RW_LOCK_BIAS
56        "jz 1f\n"//为0则跳转标号1处
57        "call __write_lock_failed\n\t"//调用__write_lock_failed
58        "1:\n"
59        ::LOCK_PTR_REG(rw),"i"(RW_LOCK_BIAS):"memory");
60}

手写操作系统目录


    


公众号'艾恩凝'
个人公众号
个人微信
个人微信
    吾心信其可行,
          则移山填海之难,
                  终有成功之日!
                                  ——孙文
    评论
    0 评论
avatar

取消