从零到一手写操作系统（五、同步 2）linux的实现）
如果追忆会荡起涟漪，那么今天的秋红落叶和晴空万里都归你
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）读写锁
- 获取读锁时，锁值变量 lock 计数减去 1，判断结果的符号位是否为 1。若结果符号位为 0 时，获取读锁成功，即表示 lock 大于 0。
- 获取读锁时，锁值变量 lock 计数减去 1，判断结果的符号位是否为 1。若结果符号位为 1 时，获取读锁失败，表示此时读写锁被修改数据的进程占有，此时调用 read_lock_failed 失败处理函数，循环测试 lock+1 的值，直到结果的值大于等于 1。
- 获取写锁时，锁值变量 lock 计数减去 RW_LOCK_BIAS_STR，即 lock-0x01000000，判断结果是否为 0。若结果为 0 时，表示获取写锁成功。
- 获取写锁时，锁值变量 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 评论
