[关闭]
@JunQiu 2019-03-06T06:34:01.000000Z 字数 7160 阅读 473

操作系统概述

pocc(计组) summary_2018/11


1、常见的基本概念

1.1、并发/并行
1.2、共享
1.3、虚拟技术
1.4、异步

2、功能模块

2.1、进程管理
2.2、内存管理
2.3、文件管理
2.4、设备管理

3、进程管理

3.1、进程与线程
3.2、进程生命周期
3.3、进程调度
3.3、进程同步
3.3.1、互斥、同步、临界区
  1. entry section // 检查并标志
  2. critical section // 执行临界区代码
  3. exit section // 清除设置的标志
3.3.2、实现方式
  1. // 伪代码
  2. var semaphore;
  3. while(true){
  4. down(semaphore);
  5. //临界区
  6. up(semaphore);
  7. }
  1. // 伪代码
  2. // Monitor 管程
  3. // enter()函数检查能否获得管程
  4. // leave()释放管程
  5. while(true)
  6. {
  7. Monitor. enter();
  8. // 临界区
  9. Monitor. leave();
  10. }
3.3.3、经典同步问题(信号量)
  1. 思路:
  2. 1、首先对于互斥资源缓冲区设置一个信号量mutex=1
  3. 2、缓冲区的大小:empty=n,生产者使用;full=0,消费者使用
  4. // 伪代码
  5. producer(){
  6. while(true){
  7. down(empty);
  8. down(mutex);
  9. // 生产 empty-n
  10. up(mutex);
  11. up(empty);
  12. }
  13. }
  14. comsumer(){
  15. while(true){
  16. down(full);
  17. down(mutex);
  18. // 消费 full-n
  19. up(mutex);
  20. up(full);
  21. }
  22. }
  23. mian(){
  24. comsumer(),producer();
  25. }
  26. Tips:
  27. 1、这里不能先对缓冲加锁,再测试emptyfull,因为比如当生产者获取到缓冲区资源时,此时empty为空,生产者进入睡眠,而消费者也无法获得缓冲区,永远等待下去。
  28. 2、更复杂的情况,比如多个消费者,多个生产者,大家也可以思考一下
  1. 思路:写优先,当一直有读者读,写者可能产生饥饿
  2. 1、读写不能同时进行,设置一个变量mutex,表示数据库互斥
  3. 2、当一个读者时,需要获取数据库,用rcount计数,rcount=1表示第一个读者,当recount>1,表示有读者在进行,可以直接读,但由于不能让两个进程同时操作rcount,因此也是互斥的
  4. // mutex 表示数据库互斥
  5. // rcount 表示当前正在读的人数
  6. // 伪代码
  7. writer(){
  8. while (true){
  9. down(mutex)
  10. // write
  11. up(mutex)
  12. }
  13. }
  14. reader(){
  15. while (true){
  16. // 防止多个进程同时操作recount变量
  17. down(rcount)
  18. rcount++
  19. if(rcount==0) // 当第一个读者时,需要获取数据库资源
  20. down(mutex)
  21. up(rcount)
  22. // read
  23. down(rcount)
  24. rcount--
  25. if(rcount==0)
  26. up(mutex)
  27. up(rcount)
  28. }
  29. }
3.4、进程通信

4、死锁

4.1、死锁、活锁、饥饿
4.2、死锁的条件
4.3、死锁的处理方案
4.3.1、驼鸟算法
4.3.2、死锁检测与死锁恢复
  1. // 1.1、每种资源只有一个的情况,如上图所示:方块表示进程、圆圈表示资源
  2. 思路:这种情况我们可以通过查找资源形成的有向图,通过深度遍历,查找有向图中是否有环,如果存在环则形成了死锁。

  1. // 1.2、每种资源有多个的情况
  2. E:每种资源总量
  3. A:每种资源剩余量
  4. C:进程已经占有的资源
  5. R:进程执行还需要的资源
  6. 思路:通过依次检查每个进程还需要的资源,如果能够从A中取出足够的资源,则让进程获取资源执行,并释放资源让其它进程获取并执行完所有的进程,则没有发生死锁;如果不满足,则进程无法获得资源执行完成,说明造成了死锁(若无进程获得资源则是资源不足)
  1. 1、杀死进程,释放部分资源
  2. 2、通过抢占资源实现
  3. 3、回滚进程,回滚到没有发生死锁前
4.3.3、死锁避免
  1. 上图矩阵的含义:
  2. 矩阵第一列:进程名
  3. 矩阵第二列:进程已经拥有的资源
  4. 矩阵第三列:进程执行总共需要的资源
  5. free:表示还可以分配尚未分配的资源
  6. 是否安全的定义:如果能够找到一种分配顺序,让进程依次获得资源,并完成执行,我们说这个状态是安全的;如果找不到,则不安全。
  7. 比如a图可以按照B->C->A的顺序执行完,则说明是安全的。
  8. 因此:若需要避免死锁的发生,则需要在分配资源时避免进入这种不安全的的状态。
  1. 一个银行家承诺向他的客户发放一定贷款的额度,为避免进入死锁,如果请求会导致进入不安全状态,则拒绝请求,等待其它请求。
  2. 比如按照上图的方式发放,银行家将进入C状态,而C是不安全状态;因此,银行家会拒绝C之前的请求,避免进入C的状态。
  1. 多个银行家算法与单个银行家算法相似,只是发放的不只是贷款,可能还有食物等其它资源;
  2. E:表示总资源
  3. P:表示已经分配分资源
  4. A:还可以分配的资源
  5. 算法:每次分配时,检测分配该资源后是否会进入不安全状态;如果会进入不安全状态,则拒绝分配;否则则分配资源。
4.3.4、死锁预防
  1. 1、互斥条件:一般无法,因此资源互斥本身无法改变
  2. 2、不可抢占条件:可以抢占,比如高优先级抢占低优先级
  3. 3、请求与保持条件:获取资源时,要么一次性获取,要么一个也不获取
  4. 4、循环等待条件:对资源编号,按顺序获取资源,从而不会形成环

5、内存管理

5.1、分页式存储
5.1.1、概述
5.1.2、页面置换算法
  1. 即把最长时间不会访问的页换出,只是一种理论上的算法,因为无法知道一个页多长时间不再不再被访问。
  2. 比如页的访问序列:7012105231517
  3. 物理内存页只有三个:7017最长不会不会使用,因此应该把7换出
  1. 虽然无法知道将来的使用情况,但是可以却可以知道过去的使用情况,一般来说很长时间未使用的页将来使用的概率的也不大,我们可以换出这些页;
  2. 实现方式:如下图所示:通过维护一个链表实现,每次使用的页放在表头或者移动到表头,这样就可以保证在链表尾部的页即是最近最少使用的页。但需要每次更新链表,代价比较大。

  1. 为每个页设置两个状态位,R(0,访问时置为1),M(0,修改时置为1),R位会定时清0
  2. 页面1:R:0,M:0
  3. 页面2:R:0,M:1
  4. 页面3:R:1,M:0
  5. 页面4:R:1,M:1
  6. 每次替换时,换出编号最小的页。比如上述的编号的为00的页面1替换出去,该页既没有被访问也未修改,被换出。而以页面2编号01为例,修改了但最近没访问,可能会被再次访问,相比与页面3编号10访问了还未修改,更有可能被换出。
  1. 即维护一个队列,换出那些先进入的页。而频繁使用的页也会被换出。
  1. 为了避免FIFO算法将频繁使用的页换出去,第二机会算法会检查页的R位,如果为0,那么这个最早进来又没有使用的页将会被换出;如果R位为1,那么R位将置0,并放入队列尾。
  2. 思路:每次替换只需从队列头查找R=0的页换出即可。

  1. 第二次机会算法还有一个缺点就是需要在链表中移动页面,而时钟算法通过形成一个环,通过移动指针来避免移动,当遇到需要移动的情况,只需要指针前移即可。(即指针指向的是队列头)

5.2、分段式存储
5.3、段页式存储

6、磁盘

6.1、概述
  1. 1、盘面(Platter):一个磁盘可以由多个盘面组成。
  2. 2、磁道(Track):一个盘面由多个磁道组成,即盘面上不同半径的环道。
  3. 3、柱面(Cylinder):在由多个盘面构成的磁盘中,多个盘面同一半径磁道构成的圆柱面。
  4. 4、扇区(Track Sector):磁道上的一个弧段,是最小的存储单元。
  5. 5、磁头(Head):从盘面上读取、写入信息的部分,能够将磁信息转化为电信息(读)、或者将电信息转换为磁信息(写)。
  6. 6、制动手臂(Actuator arm):移动磁头的手臂。
  7. 7、主轴(Spindle):旋转整个盘面。
6.2、磁盘调度算法
  1. 1、寻道时间:将磁头移到数据所在的磁道。
  2. 2、旋转时间:将磁头移到数据所在的扇区。
  3. 3、数据的传输时间。
  4. 其中:寻道时间占用时间最长,而磁盘调度算法的目标是使平均寻到时间最短。
6.2.1、先来先服务(FCFS, First Come First Served)
6.2.2、最短寻道时间优先(SSTF, Shortest Seek Time First)
6.2.3、电梯算法(扫描算法,SCAN)
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注