大头
Table_bottom

标签云
Table_bottom

分类
Table_bottom

日历
二月
2930311234
567891011
12131415161718
19202122232425
2627281234
Table_bottom

评论
Table_bottom

留言
Table_bottom

微博
Table_bottom

热门文章
Table_bottom

随机文章
Table_bottom

豆瓣上谁关注这里
Table_bottom

链接
Table_bottom

搜索栏
Table_bottom

RSS
RSS Link
Table_bottom

功能
Table_bottom

页面
Table_bottom

计数器
450152
Table_bottom

访客统计
Table_bottom

存档
Table_bottom

信号量和同步互斥

进程的互斥与P、V操作

一、临界资源

什么是临界资源:任何时候只允许一个进程使用的资源为临界资源。

什么是临界区:访问临界资源的代码段为临界区。

例如:
代码段1 
 

  1. a = count;
  2. a--;
  3. count = a;

 代码段2   

  1. b = count;
  2. b++;
  3. count = b;

为临界区,count为临界资源。

对临界资源的访问必须满足以下条件:
一次只能有一个进程进入,其他进程等待。
进入者必须在有限时间内退出。
等待者应该有机会进入。

二、信号量

信号量的结构模型:(S,Q)
在2.4.x内核中,信号量数据结构定义为(include/asm/semaphore.h): 
 

  1. struct semaphore {
  2. atomic_t count;
  3. int sleepers;
  4. wait_queue_head_t wait;
  5. #if WAITQUEUE_DEBUG
  6. long __magic;
  7. #endif
  8. };

信号量操作:
1) 初始化
2) P操作
a) S--
b) if(S < 0) 在Q队列中睡眠
     else 进入
3) V操作
a) S++
b) if(S <= 0) 唤醒一睡眠进程(等待队列中有进程在睡眠)
     else 继续
P操作可以理解为申请资源,V操作可以理解为释放资源,在2.4.x内核semaphore结构中,count是资源计数,为正数或0时表示可用资源数,-1表示没有空闲资源且有等待进程,至于等待进程的数量并不关心,实现中依赖了sleepers,比较复杂,但好处是是up操作非常简单,只需汇编原子地将count加1,如果小于等于0表示有进程等待,调用__up_wakeup() --> __up(),否则返回。linux中的实现可以到arch/i386/kernel/semaphore.c中看到(2.4.x kernel),__down()和__up()。

信号量实现:
用ITRON的一个简单实现<An ITRON Implementation>做为例子。我粗略地看了一下代码,关于信号量(semaphore)的P/V操作,有计数器控制和等待队列。
SEMCB(semaphore control block)结构中有id,队列,计数器等成员。 

  1. OS_AcquireSemaphoreTimeOut()
  2. { ...
  3.         lock()
  4.         semcb->semcnt-- // counter --
  5.         if(semcb->semcnt < 0)
  6.         {
  7.                 make_wait() // make current task in wait state
  8.                 queue_insert_tpri() // insert by priority to the semaphore's
  9.                 //wait queue,which is a circular queue
  10.         }
  11.         unlock()
  12.         ...
  13. }
  14.  
  15. OS_FreeSemaphore()
  16. { ...
  17.         lock()
  18.         if(semcp->semcnt < 0)
  19.         {
  20.                 wait_release_ok()
  21.                 |
  22.                 -> wait_release() // release a task from wait state
  23.         }
  24.         semcb->semcnt++ // counter ++
  25.         unlock()
  26.         ...
  27. }

注:V操作中S先加1再判断是否小于等于0和先判断是否小于0再加1是等价的。
注:在这个实现中,semcnt值不仅正负分别表示资源空闲或有进程等待,其绝对值也是有意义的,为负时值代表等待的进程数,为正或零时值代表空闲的资源数。

三、同步互斥模型

S=1

  1. P(S)
  2. 临界区
  3. V(S)


  1. P(S)
  2. 临界区
  3. V(S)


生产者消费者问题
(生产者计算生成数,消费者打印之。)

1个生产者1个消费者,缓冲buf为1
2个信号量实现模型:put = 1 get = 0

  1. 计算x
  2. P(put)
  3. buf = x
  4. V(get)

  1. P(get)
  2. y = buf
  3. V(put)
  4. 打印y


1个生产者2个消费者,缓冲buf为1(2个消费者一个打印奇数一个打印偶数)
3个信号量实现模型:put = 1 getj = 0 geto = 0

  1. 计算x
  2. P(put)
  3. buf = x
  4. if(x为奇)
  5.     V(getj)
  6. else
  7.     V(geto)

  1. P(getj)
  2. y = buf
  3. V(put)
  4. 打印y

  1. P(geto)
  2. y = buf
  3. V(put)
  4. 打印y

这个模型比较直观,但是用了3个信号量。在计算出x后判断其奇偶再"V"不同的信号量。
如果只使用2个信号量如何实现,生产者计算出x后直接"V"一个信号量,2个消费者取出后判断是否打印还是不于理会。
2个信号量实现模型:put = 1 get = 0

  1. 计算x
  2. P(put)
  3. buf = x
  4. V(get)

  1. P(get)
  2. y = buf
  3. if(y为奇)
  4. {
  5.     V(put)
  6.     打印y
  7. }
  8. else
  9.     V(get)

 C

  1. P(get)
  2. y = buf
  3. if(y为偶)
  4. {
  5.     V(put)
  6.     打印y
  7. }
  8. else
  9.     V(get)


1个生产者1个消费者,缓冲buf为m
2个信号量实现模型:put = m get = 0

  1. 计算x
  2. P(put)
  3. buf[t] = x
  4. t = (++t) % m
  5. V(get)

 B 

  1. P(get)
  2. y = buf[k]
  3. k = (++k) % m
  4. V(put)
  5. 打印y


N个生产者M个消费者,缓冲buf为m
4个信号量实现模型:put = m get = 0 T = 1 K = 1

  1. 计算x
  2. P(put)
  3. P(T)
  4. buf[t] = x
  5. t = (++t) % m
  6. V(T)
  7. V(get)

  1. P(get)
  2. P(K)
  3. y = buf[k]
  4. k = (++k) % m
  5. V(K)
  6. V(put)
  7. 打印y

 
四、删除一个信号量

删除一个信号量,系统应该释放一些资源。如果无进程在等待此信号量,处理比较简单。
如果有进程在等待此信号量,如何处理这些进程,有人说kill,但我看到的一个实现是唤醒。
除进程之外,这个等待队列也需要释放,否则会造成内存泄露。
不仅是删除一个信号量,在系统中当删除某个资源时,会释放等待队列的所有task。

OS_DelFlag --|
OS_DelMessageBuffer --|--> call wait_delete(QUEUE *) --> OS_DelSemaphore --| 

  1. while()
  2. {wait_release();...} // release all tasks blocked on specified wait queue


五、由来

为什么敲打这么个东西。因为有个自主实现的基于ITRON的OS需要测试。在测试其信号量资源时我补充了一个测试用例,即当有进程在等待一个信号量时删除此信号量系统会有如何反应。基于此,先给测试人员做了presentation介绍信号量及同步互斥模型。然后粗略地看了看linux 2.4.x,ITRON和ucLinux三个系统的P/V操作和删除信号量的实现。因工作繁忙没有深入研究,简单整理一下用了两个小时边解bug边偷闲着输入完。然后steedhorse帮忙做了检查,经过了一个小时的讨论,改了一些错误,在此感谢。
有的问题我不是很清楚,希望看了后能提出来大家讨论。

Non-Preemptive Kernel

非抢占(Non-Preemptive)内核中如果任务不主动放弃,就不会被其他的高优先极任务抢掉对于CPU的控制。一个ISR可以使一个更高优先级的任务进入等待运行状态,但ISR总是返回被中断的任务。如图:

①低优先级任务(LPT)执行;
②低优先级任务被中断;
③执行中断服务例程,使高优先级任务(HPT)就绪;
④中断服务例程返回到被中断的低优先级任务;
⑤低优先级任务继续执行;
⑥低优先级任务放弃CPU;
⑦高优先级任务运行。
这个比较简单,而非抢占内核的其他优点也都好理解。可书上有这么一句话:非抢占内核的一个优点是中断等待时间通常比较低。什么是中断等待时间?
往后翻10页,书上又写:中断等待时间=中断被禁止的最长时间量+在ISR中开始执行第一个指令的时间
这个式子我看了大约五分钟。又翻回前面那句话反复默念。然后我决定认为自己理解了。一个任务在执行,收到一个中断,而这时中断有可能是被禁止的,一直到中断重新被打开,CPU保存现场环境到堆栈,跳转到ISR。所谓“中断被禁止的最长时间”的意思是从收到中断到开中断这一段时间。而保存CPU现场后才开始执行ISR,那么保存现场的这个时间是不是包含在中断等待时间内?从上面的式子看是的。
但是又来个式子:中断响应时间=中断等待时间+保存CPU状态的时间(非抢占内核)。

糊涂了,什么是“在ISR中开始执行第一个指令的时间”?
问题出在哪?出在ISR。开中断后,ISR即接管,保存现场的动作是ISR做的,中断等待时间就是从收到中断到ISR接管的时间,然后保存现场,然后开始执行用户代码,到这时是中断响应时间。对于抢占内核,保存完现场后要调用一个内核函数,通知内核一个ISR在处理并允许内核记录中断嵌套的情况,所以前面说,非抢占内核的一个优点是中断等待时间通常比较低。

非抢占内核最大的问题是响应时间。一个就绪的高优先级任务可能要等待不可预期的一段时间才能运行,所以实时内核多是抢占内核。如图是抢占内核的情况:

①低优先级任务执行;
②异步事件使任务中断;
③响应异步事件,运行中断服务例程,使高优先级任务就绪;
④中断服务例程返回到高优先级任务;
⑤高优先级任务执行,直到它被中断转向执行优先级更高的任务;
⑥高优先级任务结束,内核切换到低优先级任务;
⑦低优先级任务继续执行。 

深入理解Linux内核-080327

文件访问权限附加标记(用在可执行文件)。
suid(set user id):进程执行一个文件时通常保持进程拥有者的UID。如果设置了suid标志位,进程就获得了该文件拥有者的UID。
sguid(set group id):进程执行一个文件时保持进程组的GID。如果折纸了sgid标志位,进程就获得了该文件组的ID。
当进程创建一个文件时,文件拥有者的ID就是该进程的UID。其组ID既可以是进程创建者的GID,也可以是父目录的GID,取决于父目录sgid标志位的值。

深入理解Linux内核-080326

Unix的每个进程都有一个当前的工作目录,它属于进程执行上下文(execution context)。

不允许给目录创建hard link,这可能会把目录树变为环形图,从而不能定位文件。

只同一文件系统中的文件间可创建hard link。

MIPS处理器设计透视-080326

MIPS体系结构具有独立的指令缓存和数据缓存。CPU可同时获取指令和读写内存变量。