操作系统

操作系统

十二月 12, 2021

第一章

操作系统的基本特征

  • 并发：是指两个或多个活动在同一给定的时间间隔中进行。
  • 共享 ：是指计算机系统中的资源被多个进程所共用。
  • 异步：进程以不可预知的速度向前推进
  • 虚拟:把一个物理上的实体变成若干个逻辑上的对应物。

  • 最基本特征：并发、共享（两者互为存在条件）

进程调度

处理机调度

  • 概念

    是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

  • 分类

    • 高级调度(作业调度)(次数少)
    • 中级调度(内存对换)(次数中等)
    • 低级调度(进程调度)(次数最多)

  • 调度方法

    • 剥夺式(谁重要让谁去)

  • 非剥夺式(谁先来让谁先完成，后来的排队)

  • 调度准则

    • CPU利用率(越高越好)

  • 系统吞吐率(单位时间内CPU完成作业的数目)

  • 周转时间(完成时间-提交时间=等待时间+服务时间)

    • 平均周转时间 = 各作业周转时间之和/作业数目
    • 带权周转时间 = 作业周转时间/作业实际运行的时间         =    (作业完成时间点 - 作业提交时间点)/作业实际运行时间
    • 平均带权周转时间 = 各作业带权周转时间之和/作业数目

  • 等待时间(等待时间，是指进程/作业处于等待处理机状态的时间之和，显然，等待时间越长，用户满意度越低。公式如下)

    等待时间 = 周转时间 = 运行时间
    操作系统依靠平均等待时间来评价整体性能

    平均等待时间 = 等待时间 / 总数

  • 响应时间

    对于计算机用户来说，他们希望自己提交的请求尽早的开始被系统服务、回应，于是人们提出响应时间来衡量这个尺度。
    响应时间，指从用户提交请求到首次产生响应所用的时间。

  • 算法

    • 先来先服务

  • 短作业优先

  • 优先级调度算法

  • 高响应比优先调度算法

    （运行时间 + 等待时间）/等待时间
    也就是说响应比一定是大于一的

  • 时间片轮转
  • 多级反馈队列调度算法

处理机调度总结

wRpzka.png

进程同步

  • 引入原因

    协调进程之间的相互制约关系

  • 制约关系
    • 同步 (也称为直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。)
  • 互斥 （也称为简介制约关系。当时一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问次临界资源。）
  • 临界资源

    一次仅允许一个进程使用的资源（打印机，共享缓冲区，共享变量，公用队列）

  • 临界区

    在每个进程中访问临界资源的那段程序

  • 临界区互斥
    • 原则

      空闲让进：如果有若干个经常要求进入空闲时间的临界区，一次仅运允许一个进程进入。
      忙则等待：任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。
      有限等待:进入临界区的进程要在有限和司机爱你内退出，一遍其它进程能及时进入自己的临界区。
      让权等待:如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

  • 基本方法

    信号量：利用PV操作实现互斥

进程管理

易错点：导致进程进入阻塞态的事件：

1.当进程等待临界资源(不包括处理机)或等待I/O完成，都会进入阻塞态
2.系统将CPU分配给高优先权的进程，会使当前进程变为就绪状态不会导致进程的阻塞。

死锁

  • 产生的原因

    1.非剥夺资源的竞争 和 2.进程的不恰当推进顺序（与饥饿的区别）

  • 定义

    多个进程因为竞争资源而造成的一种僵局，如果没有外力，这些进程将无法推进

  • 解决办法
    • 预防死锁

      1.破坏互斥条件

    2.破坏不剥夺条件
    3.破坏请求和保持条件
    4.破坏循环等条件

  • 避免死锁

    1.安全状态
    2.银行家算法

  • 检测死锁:利用死锁原理
  • 解除死锁

    资源剥夺法
    撤销进程法
    进程回退发

程序执行过程的跟踪

  • 需要注意的是，在dos中运行程序时，是command将程序加载入内存；
  • 所以程序运行结束后返回到command中，而在这里是debug将程序加载入内存，所以程序运行结束后要返回到Debug中。

模拟

进程之间存在着哪几种制约关系

进程间存在着两种相互制约的关系：直接制约关系（即同步问题）和间接制约关系（即互斥问题）。同步问题是存在逻辑关系的进程之间相互等待产生的制约关系，互斥问题是相互无逻辑关系的进程间竞争使用相同的资源所发生的制约关系。

请用信号量机制解决以下的“过独木桥”问题：（8分）

   同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；

   当某一方向无人过桥时，另一方向的人可以过桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
对于A方向：
P（SA）
IF (countA=0)
THEN P(metux)
countA=countA+1
V(SA)
过桥
P(SA)
countA=countA-1
IF(countA=0)
THEN V(metux)
V(SA)



对于B方向：
P（SB）
IF (countB=0)
THEN P(metux)
countB=countB+1
V(SB)
过桥
P(SB)
countB=countB-1
IF(countB=0)
THEN V(metux)
V(SB)

除了信号量机制，还有哪些其他方法可以解决同步和互斥问题，各有什么优势

开锁加锁