操作系统复习资料

### 操作系统复习资料知识点详解 #### 一、进程间的制约关系与同步机制 **知识点1：进程间的制约关系** 1. **互斥**: 当多个进程需要访问同一资源时，如本例中的打印机，这些进程之间存在互斥的制约关系。这是因为打印机作为一个独占性资源（临界资源），在任何时刻只能被一个进程使用。 2. **临界资源**: 指的是系统中不允许同时被多个进程访问的资源。例如打印机、磁盘等。 **知识点2：使用信号量和P、V操作实现进程同步** 1. **信号量机制**: 信号量是一种用来控制多个进程对共享资源访问的机制。信号量是一个整型变量，可以被任何希望访问该资源的进程访问。 2. **P操作**: P操作（也称为Wait操作）会尝试减少信号量的值。如果信号量的值大于0，则将其减1，并允许进程继续执行；如果信号量的值小于等于0，则将当前进程挂起，等待其他进程执行V操作唤醒。 3. **V操作**: V操作（也称为Signal操作）会增加信号量的值。当一个进程完成对共享资源的访问后，它应该执行V操作来唤醒正在等待该资源的其他进程。 **示例代码解释**: 对于进程A和B，我们可以使用一个信号量`iMutex`来确保它们互斥地使用打印机。信号量的初始值设置为1，表示打印机是可用的。 ```plaintext // 进程A P(iMutex); 申请打印机; 使用打印机; V(iMutex); // 进程B P(iMutex); 申请打印机; 使用打印机; V(iMutex); ``` #### 二、程序执行流程分析 **知识点3：前驱图** 1. **定义**: 前驱图（Precedence Graph）是用来表示一系列任务之间依赖关系的一种图形表示方法。每个节点代表一个任务，箭头表示任务之间的依赖关系。 2. **构建方法**: 在给定的示例中，我们需要根据每条语句的执行顺序构建前驱图。具体步骤如下： - `S1`: a = 5 - x; （无前置条件） - `S2`: b = a * x; （前置条件：S1） - `S3`: c = 4 * x; （前置条件：S1） - `S4`: d = b + c; （前置条件：S2, S3） - `S5`: e = d + 3; （前置条件：S4） 前驱图如下所示： ``` S1 -> S2 -> S4 -> S5 S1 -> S3 -> S4 ``` **知识点4：CPU利用率计算** 1. **顺序环境下的CPU利用率计算**: 对于给定的问题，我们需要计算在顺序环境下先执行A程序再执行B程序时CPU的利用率。我们确定每个程序的执行时间以及它们使用CPU的时间。 - A程序总执行时间为40秒，使用CPU时间为25秒。 - B程序总执行时间为40秒，使用CPU时间为15秒。 总执行时间为80秒，CPU总共使用了40秒。因此，CPU利用率为\( \frac{40}{80} = 50\% \)。 2. **增加内存后的CPU利用率变化**: - **原内存配置下**: - 可用内存为32KB - 2KB(OS占用) = 30KB。 - 用户进程数为\(\frac{30KB}{10KB} = 3\)个。 - CPU利用率 = \(1 - (80\%)^3 = 48.8\%\). - **增加30KB内存后**: - 可用内存为62KB - 2KB(OS占用) = 60KB。 - 用户进程数为\(\frac{60KB}{10KB} = 6\)个。 - CPU利用率 = \(1 - (80\%)^6 = 73.79\%\). #### 三、调度算法的应用 **知识点5：不同调度算法的比较** 1. **先来先服务（FCFS）**: - **原理**: 按照作业到达的顺序依次执行。 2. **短作业优先（SJF）**: - **原理**: 优先执行运行时间较短的作业。 3. **响应比高者优先**: - **原理**: 根据作业的响应比（运行时间加上等待时间与运行时间的比值）来选择下一个执行的作业。 **示例计算**: 1. **FCFS调度算法**: - J1: 开始时间为8.00，完成时间为10.00，周转时间为2.00，带权周转时间为1.00。 - J2: 开始时间为10.00，完成时间为10.50，周转时间为2.00，带权周转时间为4.00。 - J3: 开始时间为10.50，完成时间为10.60，周转时间为1.60，带权周转时间为16.00。 - J4: 开始时间为10.60，完成时间为10.80，周转时间为1.30，带权周转时间为6.50。 平均周转时间为1.725，平均带权周转时间为6.875。 2. **SJF调度算法**: - J1: 开始时间为8.00，完成时间为10.00，周转时间为2.00，带权周转时间为1.00。 - J2: 开始时间为10.30，完成时间为10.80，周转时间为2.30，带权周转时间为4.60。 - J3: 开始时间为10.00，完成时间为10.10，周转时间为1.10，带权周转时间为11.00。 - J4: 开始时间为10.10，完成时间为10.30，周转时间为0.80，带权周转时间为4.00。 平均周转时间为1.55，平均带权周转时间为5.15。 3. **响应比高者优先调度算法**: - J1: 开始时间为8.00，完成时间为10.00，周转时间为2.00，带权周转时间为1.00。 - J2: 开始时间为10.10，完成时间为10.60，周转时间为2.10，带权周转时间为4.20。 - J3: 开始时间为10.00，完成时间为10.10，周转时间为1.10，带权周转时间为11.00。 - J4: 开始时间为10.10，完成时间为10.30，周转时间为0.80，带权周转时间为4.00。 平均周转时间为1.525，平均带权周转时间为5.05。 通过对比这三种调度算法，可以看出SJF和响应比高者优先调度算法在处理短作业时具有更好的性能，而FCFS则更倾向于按照到达顺序执行作业。不同的应用场景可以选择不同的调度策略来优化系统的整体性能。