小魚の干物

1.信号量机制实现进程互斥

1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
2. 设置互斥信号量mutex，初始值为1
3. 在临界区之前执行P(mutex)
4. 在临界区之后执行V(mutex)

1.信号量机制

进程互斥的四种软件实现方式和进程互斥的三种硬件实现方式都存在一些问题。

1.在双标志检查法中，进入区的“检查”、‘上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题。

2.所有的解决方案都无法实现“让权等待”。

1965年，荷兰学者迪杰斯特拉Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法–信号量机制

这里什么都没写，先占个坑以后再写。

1.单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

1.什么是进程同步

回顾：进程具有异步性的特征。异步性是指：各自并发执行的进程以各自独立的、不可预知的速度向前推进。

例子：进程通信 —- 管道通信

写进程往管道里写数据，读进程再从管道里读数据。读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行，如何解决这种一部问题，就是进程同步所讨论的内容。

1.时间片轮转（RR，Round-Robin）

RR

• 算法思想：公平地、轮流地为每个进程服务，让每个进程在一定时间间隔内都可以得到响应

• 算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放回就绪队列尾重新排队。

• 用于作业/进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理及时间片）

• 是否可抢占？：若进程未在一个时间片内执行完，将被剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到。

• 优缺点：

  • 优点：公平；响应快，适用于分时操作系统
  • 缺点：由于高频率的进程切换，因此有一定的开销；不区分任务的紧急程度。

• 是否会导致饥饿：不会

• 补充：时间片太大或太小会有什么影响？

软件工程别人整理的考研笔记

整理的挺全面的

1.先来先服务（FCFS，First Come Firse Serve）

FCFS

• 算法思想：主要从“公平”的角度考虑（类似于生活中排队买东西）

• 算法规则：按照作业/进程到达的先后顺序进行服务

• 用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是那个进程先到达就绪队列

• 是否可抢占？ 非抢占式的算法

• 优缺点：

  • 优点：公平、算法实现简单
  • 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对作业来说用户体验不好。即：FCFS算法对长作业有利，对短作业不利（EG:排队买奶茶）

• 是否会导致饥饿（某进程，作业长期得不到服务）：不会（只要进程或作业一直等着总会得到服务）

1.综合数据类型概述

组合数据类型能够将多个同类型或者不同类型的数据组织起来，通过单一的表示是数据操作更有序，更容易。Python中组合数据类型分为序列类型，集合类型，映射类型。

1.CPU利用率

由于早期的CPU造价极其昂贵，因此人们希望让CPU尽可能多地工作

CPU利用率：指CPU“忙碌”的时间占总时间的比例

$利用率=\frac{忙碌的时间}{总时间}$