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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
| # ch1&&ch2
操作系统:运行在计算机上的程序(称为内核(kernel))
## 实时操作系统 (RTOS) 与 分时操作系统 (TSOS)
* **分时系统 (Time-Sharing):** 追求**资源利用率**与**公平性**。通过将 CPU 时间划分为极小的“时间片”，轮流分配给多个用户或任务，营造“独占计算机”的错觉。其关键指标是**平均响应时间**。
* **实时系统 (Real-Time):** 追求**确定性 (Determinism)** 与**可预测性**。任务必须在严格定义的截止时间内完成。其关键指标是**最坏情况下的响应延迟**。
# ch3:进程
进程:操作相关资源执行某一命令的活动实体
### 进程控制块(Process Control Block,PCB)
进程可以用PCB来表示,它包含许多与某个特定进程相关的信息:
- 进程状态: new,running,waiting,terminated
- 程序计数器(program counter,PC): 进程要执行的下个指令的地址
- 寄存器(CPU register)
- CPU调度信息
### 进程调度
#### 调度序列
进程在进入系统时,会被加入到一个作业队列(job queue)中.
最初,新进程会进入就绪队列(ready queue),直到被选中执行,之后可能发生以下事件:
- 进程创建了一个新的子进程,并等待子进程终止
- 进程由于中断被强制返回就绪队列
- 发出使用某个设备的请求,进入设备队列
#### 调度类型
* **高级调度 (High-Level Scheduling)**
* 也称为**作业调度**或**宏观调度**。
* **核心逻辑**：负责从后备队列中挑选作业进入内存，为其创建进程并分配必要的资源。
* **时间尺度**：通常是**分钟、小时或天**。
* **中级调度 (Intermediate-Level Scheduling)**
* 涉及进程在**内、外存间的交换**（Swapping）。
* **资源管理维度**：从存储器资源管理的角度来看，把进程部分或全部**换出到外存**上，可为当前运行进程的执行提供所需内存空间；反之，将当前进程所需部分**换入到内存**。
* **物理约束**：指令和数据必须在内存里才能被处理机直接访问。
* **低级调度 (Low-Level Scheduling)**
* 也称**微观调度**或**进程调度**。
* **资源分配维度**：从处理机资源分配角度来看，处理机需要经常选择**就绪进程或线程**进入运行状态。
* **时间尺度**：通常是**毫秒级**的。
* **实现要求**：由于低级调度算法使用频繁，要求在实现时做到**高效**。
### 进程运行
#### 进程创建
当进程创建新进程时,有两种情况:
1. 父进程和子进程并发执行
2. 父进程等待子进程执行完毕
新进程的地址空间有两种可能:
1. 子进程与父进程有同样的程序和数据
2. 子进程加载的是另一个新程序
#### 进程终止
>Process executes last statement and asks the operating system to delete it (exit).
Parent may terminate execution of children processes (abort).
- Child has exceeded allocated resources.
- Task assigned to child is no longer required.
- Parent is exiting.
- Operating system does not allow child to continue if its parent terminates,which is called as **Cascading termination**.
- [chrome多线程架构](https://developer.chrome.com/blog/inside-browser-part1?hl=zh-cn)
### 进程间通信(InterProcess Communication,IPC)
与其他进程共享数据的进程为协作进程,协作进程需要有一种进程间通信的机制,允许进程之间交换数据,有两种基本模型:
1. 共享内存模型: 建立起一块供协作进程共享的内存区域.
2. 消息传递模型: 通过消息队列来处理.
#### 共享内存模型
一种方法是通过一个缓冲区供producer存放信息和consumer提取信息,这里的producer和consumer是相对的,协作进程可以同时扮演这两个角色
#### 消息传递系统(待补充)
# ch4:线程
### 概述
线程:cpu使用的基本单元,包括线程ID,程序计数器,寄存器组和堆栈,与同一进程的其他线程共享代码段,数据段和其他操作系统资源.
- 如果一个进程有多个线程,那么就能同时执行多个任务
### 多核编程
对于单核系统,并发仅意味着线程随着时间推移交错执行,因为内核在某一时刻只能执行单个线程;但对于多核系统,并发可以让线程并行运行
#### 并行类型
**数据并行**: 将数据分布于多个核上,在每个核上执行相同操作
**任务并行**: 不同核上的每个线程都执行一个单独的操作,可以操作相同的,也可以操作不同的数据
### 多线程模型
用户层的用户线程需要内核层的内核线程来支持和管理,有三种常见的关系模型
#### 多对一模型
映射多个用户级线程到一个内核线程,显然这无法利用多核操作系统
#### 一对一模型
一个用户线程对应一个内核线程,唯一缺点是创建一个用户线程就要创 建一个相应的内核线程,会影响应用程序的性能,故需要限制某一时刻下可供使用的线程数量,Linux和Windows是采用这一模型的代表
#### 多对多模型
该模型可以将多个用户线程映射到多个内核线程中
### 线程库
线程库为程序员提供创建和管理线程的API,有两种方法实现线程库:
1. 在用户层实现一个无内核支持的库,手写寄存器调用之类的操作
2. 在内核层实现一个库,创建线程时会发生系统调用
# ch5:CPU如何调度进程
### 调度算法
#### 先到先服务(First Come First Served ,FCFS)
当一个进程进入准备队列时,会被链接到队列尾部.
**缺点**: 平均等待事件很长,一旦CPU分配给了一个进程,进程就会一直运行直到CPU释放,不适用于分时系统
#### 最短作业优先调度(Shortest Job First ,SJF)
当CPU空闲时,会分配给执行时间最短的进程.
**缺点**: 很难判断新进程的具体执行时间,只能通过估计来处理
可分为抢占的和非抢占的,对于抢占SJF算法来说,如果当前执行的进程所需剩余执行时间比新进程长,就会被抢占.
#### 优先级调度(priority scheduling)
通过对进程标识优先级,保证优先级最高的进程先执行,同样可以分为抢占的和非抢占的.
**缺点**: 无穷阻塞,即低优先级进程可能永远无法执行,解决方法是老化(aging),即根据等待时间提高等待进程的优先级
#### 轮转调度(Round Robin,RR)
这个算法是专门为分时系统设计的,结合了FCFS调度和抢占的概念:
将一个较小时间单元(如10-100ms)定义为时间片,CPU调度程序为每个进程分配不超过一个时间片的占用时间,当一个进程占用时间超过一个时间片时,将会被抢占,并被加到队列尾部.
关键在于要根据进程切换的时间花费来设计时间片大小,从而保证进程切换不会过度拖延平均的进程运行时间.
#### 多级队列调度(multilevel queue)
根据进程的类型,大小,将准备队列分成具有优先级别划分的多个单独队列,每个队列使用独特的调度算法.
#### 多级反馈队列调度(multilevel feedback queue)
在多级队列调度中,进程进入系统时会被永久分配到某个队列.
但现在讨论的反馈队列调度算法允许进程在队列之间迁移,将等待过长的进程放入高优先级队列,将用时过长的进程放入低优先级队列.
- 是最通用,但也是最复杂的算法
### 线程调度(待补充)
### 多处理器调度
当操作系统有多个核即有多个CPU时,进程的调度会变得更加复杂,有两种方法,一种是让一个处理器负责处理所有的调度决定,I/O处理核其他系统活动,而其他的处理器只执行用户代码.这被称为**非对称多处理**.因为只有一个处理器能够访问系统数据,减少了数据共享的负担.
另一种方法是使用对称多处理(Symmetric MultiProcessing,SMP),每个处理器自我调度,可以使用一个共享的准备队列,也可以每个处理器单独使用一个准备队列.
几乎所有的现代操作系统都采用这一方案.
#### 处理器亲和性(processor affinity)
由于将一个进程从一个处理器转移到另一个处理器需要在处理器之间迁移缓存,代价过高,因此需要让一个进程一直运行在同一个处理器上,这被称为**处理器亲和性**.
#### 负载平衡(load balance)
对于共享队列的多处理器操作系统,由于处理器需要一直从队列中取得最新的进程,故没有处理器会保持空闲.
但对于具有单独准备队列的多处理器操作系统,需要决定每个处理器的负载分配,避免有处理器的负载太高或者太低.
有两种方法:
1. 推迁移(push migration): 超载处理器将进程push到空闲处理器
2. 拉迁移(pull migration): 空闲处理器从超载处理器pull进程.
这两种方法经常被同时使用,但因为发生了进程在处理器之间的迁移,会抵消**处理器亲和性**带来的好处.
#### 多核处理器
在多核处理器中应用多线程有两种方法:
1. 粗粒度(coarse-grained): 线程一直在处理器上执行,直到突然遇到长时间的中断(这里的中断仅仅是指处理器停止运行,而非通常意义的主动性中断),这时处理器会切换执行另一个线程.
2. 细粒度(fine-grained): 通过精细化线程的运行逻辑,减小线程的切换成本
### 实时操作系统的CPU调度(过)
# ch6:同步
### 临界区问题
假设某个系统有n个进程,每个进程有一段代码,称为**临界区**(critical section).当一个进程在临界区执行时,其他进程不允许在各自的临界区内执行,因为这个正在执行的进程有可能正在修改公共资源,不能被打扰.
临界区问题的具体情景如下:
在进入临界区前,每个进程需要进行访问申请,实现访问申请的代码段称为**进入区**;在临界区执行完后有**退出区**,其他代码为**剩余区**.
因此,我们需要实现以下三个要求:
1. 互斥: 保证某一时刻只有一个进程能够在临界区执行
2. 提升: 如果没有进程在临界区执行,那么只有不处于剩余区的进程可以选择是否进入临界区.
3. 有限等待: 如果有一个进程位于进入区,那么其他进程允许进入临界区的次数有一个上限值,从而保证该进程可以进入临界区
### 基于软件的临界区问题解决方案: Peterson
不妨假设有两个交替运行的进程P0和P1,这两个进程共享以下数据项:
```java
int turn;
boolean flag[2];
//turn表示允许让哪个进程进入临界区,flag表示哪个进程位于进入区.
|
