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

操作系统概述

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. }
  15. comsumer(){
  16.   while(true){
  17.     down(full);
  18.     down(mutex);
  19.     // 消费 full-n
  20.     up(mutex);
  21.     up(full);
  22.   }
  23. }
  25. mian(){
  26. comsumer(),producer();
  27. }
  29. Tips:
  30. 1、这里不能先对缓冲加锁，再测试empty、full,因为比如当生产者获取到缓冲区资源时，此时empty为空，生产者进入睡眠，而消费者也无法获得缓冲区，永远等待下去。
  31. 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. }
  15. reader(){
  16.   while (true){
  17.     // 防止多个进程同时操作recount变量
  18.     down(rcount)
  19.     rcount++
  20.     if(rcount==0)  // 当第一个读者时，需要获取数据库资源
  21.       down(mutex)
  22.     up(rcount)
  23.     // read
  24.     down(rcount)
  25.     rcount--
  26.     if(rcount==0)
  27.       up(mutex)
  28.     up(rcount)
  29.   } 
  30. }
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. 物理内存页只有三个：701、7最长不会不会使用，因此应该把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)
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注