0%

图检索算法

图的表示

原文链接

对于图G=(V,E)借助数组存储的方法有邻接矩阵表示法和邻接表表示法,边集表示法。

邻接矩阵

图的邻接矩阵(adjacent matrix)表示法是使用数组来存储图结构的方法,也被称为数组表示法。 它采用两个数组来表示图:一个是用于存储所有顶点信息的一维数组,另一个是用于存储图中顶点之间关联关系的二维数组,这个关联关系数组也被称为邻接矩阵。

邻接矩阵有如下特性:

  • 图中各顶点序号确定后,图的邻接矩阵是唯一确定的。
  • 无向图和无向网的邻接矩阵是一个对称矩阵。
  • 无向图邻接矩阵中第i行或第i列的非0元素个数即为第i个顶点的度。
  • 有向图邻接矩阵第i行非0元素个数为第i个顶点的出度,第i列非0元素个数为第i个顶点的入度,第i个顶点的度为第i行与第i列非0元素个数之和。
  • 无向图的边数等于邻接矩阵中非0元素个数之和的一半,有向图的弧数等于邻接矩阵中非0元素个数之和。
  • 除完全图外,其他图的邻接矩阵有许多零元素,特别是当n值较大,而边数相对完全图的边n-1又少的多时,则此矩阵称为稀疏矩阵,非常浪费存储空间。

邻接表

邻接表(adjacency list)是图的一种链式存储方法,邻接表表示法类似于树的孩子链表表示法。

  在邻接表中对于图G中的每个顶点vi建立一个单链表,将所有邻接于vi的顶点vj链成一个单链表,并在表头附设一个表头结点,这个单链表就称为顶点vi的邻接表。

邻接表中共有两种结点结构,分别是边表结点和表头结点。

  

邻接表中的每一个结点均包含有两个域:邻接点域和指针域。

  • 邻接点域用于存放与定点vi相邻接的一个顶点的序号。
  • 指针域用于指向下一个边表结点。

边表结点由3个域组成:

  • 邻接点域(adjvex)指示与定点vi邻接的顶点在图中的位置。
  • 链域(nextdge)指向下一条边所在的结点。
  • 数据域(info)存储和边有关的信息。

头结点由2个域组成:

  • 链域(firstedge)指向链表中的第一个结点之外。
  • 数据域(data)存储顶点相关信息。

如下图为邻接表的存储示例:

  

在无向图的邻接表中,顶点的每一个边表结点对应于与顶点相关联的一条边。

在有向图的邻接表中,顶点的每一个边表结点对应于以顶点为始点的一条弧,因此也称有向图的邻接表的边表为出边表。

在有向图的邻接表中,将顶点的每个边表结点对应于以顶点为重点的一条弧,即用便捷点的邻接点域存储邻接到顶点的序号,由此构成的邻接表称为有向图的逆邻接表,逆邻接表有边表称为入边表。

邻接表的性质如下:

  • 图的邻接表表示不是惟一的,它与表结点的链入次序有关。
  • 无向图的邻接表中第i个边表的结点个数即为第i个顶点的度。
  • 有向图的邻接表中第i个出边表的结点个数即为第i个结点的出度,有向图的逆邻接表中第i个入边表的结点个数即为第i个结点的入度。
  • 无向图的边数等于邻接表中边表结点数的一半,有向图的弧数等于邻接表(逆邻接表)中出边表结点(入边表结点)的数目。

需要说明的是:

  • 在邻接表的每个线性链接表中各结点的顺序是任意的。
  • 邻接表中的各个线性链接表不说明他们顶点之间的邻接关系。
  • 对于无向图,某顶点的度数=该顶点对应的线性链表的结点数。
  • 对于有向图,某顶点的“出度”数=该顶点对应的线性链表的结点数;求某顶点的“入度”需要对整个邻接表的各链接扫描一遍,看有多少与该顶点相同的结点,相同结点数之和即为“入度”值。

邻接表与邻接矩阵的关系如下:

  • 对应于邻接矩阵的每一行有一个线形连接表;
  • 链接表的表头对应着邻接矩阵该行的顶点;
  • 链接表中的每个结点对应着邻接矩阵中该行的一个非零元素;
  • 对于无向图,一个非零元素表示与该行顶点相邻接的另一个顶点;
  • 对于有向图,非零元素则表示以该行顶点为起点的一条边的终点。

宽度(广度)优先检索BFS

广度优先搜索类似于树的层次遍历。从图中的某一顶点出发,遍历每一个顶点时,依次遍历其所有的邻接点,然后再从这些邻接点出发,同样依次访问它们的邻接点。按照此过程,直到图中所有被访问过的顶点的邻接点都被访问到。

算法实现

广度优先遍历背后基于队列,下面介绍一下具体实现的方法:

  1. 访问起始顶点,并将插入队列;

  2. 从队列中删除队头顶点,将与其相邻的未被访问的顶点插入队列中;

  3. 重复第二步,直至队列为空。

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
//邻接矩阵
public String breadFirstSearch(int v) {
if (v < 0 || v >= numOfVexs)
throw new ArrayIndexOutOfBoundsException();
visit = new boolean[numOfVexs];
StringBuilder sb = new StringBuilder();
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(v);
visit[v] = true;
while (!queue.isEmpty()) {
v = queue.poll();
sb.append(vexs[v] + ",");
for (int i = 0; i < numOfVexs; i++) {
if ((edges[v][i] != 0 && edges[v][i] != Integer.MAX_VALUE)&& !visited[i]) {
queue.offer(i);//因为使用的是队列,所以每次poll出去的都是同一层的。这个和深度优先算法使用栈,每次pop出的都是一层中的一个元素不同
visit[i] = true;
}
}
return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
}
//邻接表
public String breadFirstSearch(int v) {
if (v < 0 || v >= numOfVexs)
throw new ArrayIndexOutOfBoundsException();
visit = new boolean[numOfVexs];
StringBuilder sb = new StringBuilder();
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(v);
visit[v] = true;
ENode current;
while (!queue.isEmpty()) {
v = queue.poll();
sb.append(vexs[v].data + ",");
current = vexs[v].firstadj;
while (current != null) {
if (!visited[current.adjvex]) {
queue.offer(current.adjvex);
visit[current.adjvex] = true;
}
current = current.nextadj;
}
}
return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
}

深度优先检索DFS

从一个顶点V0开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,然后从另一条路开始走到底

从图中的某一个顶点x出发,访问x,然后遍历任何一个与x相邻的未被访问的顶点y,再遍历任何一个与y相邻的未被访问的顶点z……依次类推,直到到达一个所有邻接点都被访问的顶点为止;然后,依次回退到尚有邻接点未被访问过的顶点,重复上述过程,直到图中的全部顶点都被访问过为止。

算法实现

深度优先遍历背后基于堆栈,有两种方式:第一种是在程序中显示构造堆栈,利用压栈出栈操作实现;第二种是利用递归函数调用,基于递归程序栈实现。

堆栈法

  1. 访问起始顶点,并将其压入栈中;
  2. 从栈中弹出最上面的顶点,将与其相邻的未被访问的顶点压入栈中;
  3. 重复第二步,直至栈为空栈。
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
//采用邻接矩阵
public void depthFirstSearch(int v) {
if(v<0||v>=numOfVexs) throw new ArrayIndexOutOfBoundException();
boolean []visit = new boolean[numOfVexs];//用来标记节点是否被访问
Stack<Integer> stack = new Stack<Integer>();
StringBuilder sb = new StringBuilder();
stack.push(v);
visit[v]=true;
while(!stack.isEmpty())
{
v=stack.pop();//每层依次出一个没有标记的节点
sb.append(vexs[v] + ",");
for(int i=numOfVexs-1;i>=0;i--)
{
if((edges[v][i]!=0&&edges[v][i]!=Integer.MAX_VALUE)&&!visit[i])
{
stack.push(i);
visit[i]=true;
}
}
}
}
//基于邻接表
public void depthFirstSearch(int v) {
if(v<0||v>=numOfVexs) throw new ArrayIndexOutOfBoundException();
boolean []visit = new boolean[numOfVexs];//用来标记节点是否被访问
Stack<Integer> stack = new Stack<Integer>();
StringBuilder sb = new StringBuilder();
stack.push(v);
visit[v]=true;
Node current;
while(!stack.isEmpty())
{
v=stack.pop();//每次一层选一个出栈
sb.append(vexs[v].data + ",");
current = vexs[v].firstadj;
while(current!=null)
{
if(!visit[current.adjvex])
{
stack.push(current.adjvex);//这里也是把邻接点全部入栈
visit[current.abjvex]=true;
}
current=current.nextabj;
}
}
}

递归法

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
//邻接矩阵
public void depthFirstSearch(int v) {
if(v<0||v>=numOfVexs) throw new ArrayIndexOutOfBoundException();
boolean []visit = new boolean[numOfVexs];//用来标记节点是否被访问
visit[v]=true;
printf("%d ",v);
for(int i=0;i<numOfVexs;i++)
{
if(visit[i]!=0&&(edges[v][i]!=0&&edges[v][i]!=Integer.MAX_VALUE))
depthFirstSearch(i);
}
}
//邻接表
public void depthFirstSearch(int v) {
if(v<0||v>=numOfVexs) throw new ArrayIndexOutOfBoundException();
boolean []visit = new boolean[numOfVexs];//用来标记节点是否被访问
visit[v]=true;
printf("%d ",v);
Node current;
while(current!=null)
{
if(visit[current.abjvex]!=true)
depthFirstSearch(current.abjvex);
current=current.nextabj;
}
}

贪心算法

贪心算法是这样一种方法:分步骤实施,它在每一步仅作出当时看起来最佳的选择,即局部最优的选择,并希望通过这样的选择最终能找到全局最优解

贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性(即某个状态以后的过程不会影响以前的状态,只与当前状态有关。)

所以,对所采用的贪心策略一定要仔细分析其是否满足无后效性。

最优解问题大部分都可以拆分成一个个的子问题,把解空间的遍历视作对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪,两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法,我们自底向上构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。而贪心算法是动态规划方法的一个特例,可以证明每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况。换句话说,不需要知道一个节点所有子树的情况,就可以求出这个节点的值。由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了。

对比动态规划方法:

在动态规划方法中,每个步骤也都要进行一次选择,但这种选择通常依赖于子问题的解,这导致我们要先求解较小的子问题,然后才能计算较大的子问题。

在贪心方法中,我们总是做出当前看来最佳的选择,然后求解剩下的唯一一个子问题。尽管贪心算法进行选择时可能依赖之前做出的选择,但不依赖任何将来的选择或子问题的解。

动态规划要先求解子问题才能进行选择,贪心算法在进行第一次选择之前不需要求解任何子问题。

动态规划算法通常采用自底向上的方式完成计算,而贪心算法通常是自顶向下的,每一次选择,将给定的问题转换成一个更小的问题,然后继续求解小问题

贪心算法的步骤

贪心算法通常采用自顶向下的设计,做出一个选择,然后求解剩下的子问题。每次选择将问题转化成一个更小规模的问题。

  • 确定问题的最优子结构

  • 将最优化问题转化为这样的形式:每次对其作出选择后,只剩下一个子问题需要求解;

  • 证明作出贪心选择后,剩余的子问题满足:其最优子解与前面的贪心选择组合即可得到原问题的最优解(具有最优子结构)。

注:对应每个贪心算法,都有一个动态规划算法,但动态规划算法要繁琐的多。

贪心算法存在的问题

  • 不能保证求得的最后解是最佳的
  • 不能用来求最大值或最小值的问题
  • 只能求满足某些约束条件的可行解的范围

贪心算法适用的问题

贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
实际上,贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可以做出判断。

活动选择问题

有n个需要在同一天使用同一个教室的活动a1,a2,…,an,教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后,活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠,ai和aj两个活动就可以被安排在这一天。

活动选择问题:就是对给定的包含n个活动的集合S,在已知每个活动开始时间和结束时间的条件下,从中选出最多可兼容活动的子集合,称为最大兼容活动集合。不失一般性,设活动已经按照结束时间单调递增排序:

$$
f1<=f2<=f3<=f4<=…<=fn-1<=fn
$$

活动选择问题的最优子结构

令Sij表示在ai结束之后开始且在aj开始之前结束的那些活动的集合。

问题和子问题的形式定义如下:设Aij是Sij的一个最大兼容活动集,并设Aij包含活动ak,则有:Aik表示Aij中ak开始之前的活动子集,Akj表示Aij中ak结束之后的活动子集。并得到两个子问题:寻找Sik的最大兼容活动集合和寻找Skj的最大兼容活动集合。

活动选择问题具有最优子结构性,即:必有:Aik是Sik一个最大兼容活动子集,Akj是Skj一个最大兼容活动子集。而Aij= Aik∪{ak}∪Akj。——最优子结构性成立。

活动选择问题的动态规划方法

$$
c[i,j]表示集合s_{ij}的最优解大小,递归式如下:\
c[i,j]=c[i,k]+c[k,j]+1\
c[i,j]=\begin{cases}
0,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if\quad S_{ij}=\Phi\
\max\limits_{a_k\in S_{ij}}(c[i,k]+c[k,j]+1)\ \ if\quad S_{ij}\not=\Phi
\end{cases}
$$

活动选择问题的贪心算法

活动选择问题的贪心选择:每次总选择具有最早结束时间的兼容活动加入到集合A中。

直观上,按这种方法选择兼容活动可以为未安排的活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段最大化,以便安排尽可能多的兼容活动。

贪心算法的正确性

假设Aij是Sij的某个最大兼容活动集,假设Aij中,最早结束的活动是an,分两种情况:

1、如果an=ai ,得证

2、如果an!= ai ,则an的结束时间一定会晚于a1的结束时间,我们用ai去替换Aij中的an,于是得到A^1^,由于ai比an结束的早,而Aij中的其他活动都比an的结束时间开始 的要晚,所以A^1^中的其他活动 都与ai不想交,所以A^1^中的所有活动是兼容的,所以A^1^也是Sij的一个最大兼容活动集。

贪心算法的递归实现

自顶向下的设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//s、f数组分别表示n个活动的开始时间和结束时间,假设n个活动已经按照结束时间单调递增排列好了
//list用来保存已选的活动
//对于当前的k,返回Sk的一个最大兼容活动集
public static List<Integer> RECURSIVE_ACTIVITY+SELECTOR(List<Integer> list,int[] s ,int[] f,int k,int n)
{
int m = k+1;//表示是当前剩下没有添加到list的第一个活动
if(k==0)
list.add(m);
//往后找f[k]<=s[m]的活动
while(m<=s.length&&s[m]<f[k])
{
m++;
}
if(m<=n)
{
list.add[m+1];//m+1对应活动编号。k=0时的第一个加入的活动编号为1
RECURSIVE_ACTIVITY+SELECTOR(s,f,m,n);
}
return list
}

贪心算法的迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static List<Integer> GREEDY_ACTIVITY+SELECTOR(List<Integer> list,int[] s ,int[] f,int n)
{
int k=1;
list.add(k);//添加第一个活动。
for(int m=2;m<=n;m++)
{
if(s[m]>=f[k])//依次添加符合条件的活动,反正f都是排好序的
{
list.add(m);
k=m
}
}
return list;
}

分数背包问题

已知n种物品,各具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn),及一个可容纳M重量的背包。

问:怎样装包才能使在不超过背包容量的前提下,装入背包的物品的总效益最大?

​ 这里:

​ 1)所有的wi>0, pi>0,1≤i≤n;

​ 2)问题的解用向量(x1,x2,…,xn)表示,每个xi表示物品i被放入背包的比例,0≤xi≤1。当物品i的一部分xi放入背包,可得到pixi的效益,同时会占用xiwi的重量。

问题分析:

  • 装入背包的总重量小于等于M,即:
    $$
    \sum_{1<=i<=n}W_iX_i<=M
    $$

  • $$
    求\sum_{1<=i<=n}P_iX_i的最大值
    $$

  • 可行解:满足上述约束条件的任一(x1,x2,…,xn) 都是问题的一个可行解。可行解可能有多个(甚至是无穷多个)。

  • 最优解:能够使目标函数取最大值的可行解是问题的最优解。最优解也可能有多个。

贪心策略

这里我们需要思考:

1、策略一:以每装入一件物品,就使背包获得最大可能的效益增量作为策略

2、策略二:让背包容量尽可能慢地被消耗,从而可以尽可能多地装入一些物品。

3、如下的贪心策略

我们要设计一个贪心策略来使得装入背包物品的价值最大。我们的第一直觉肯定是要选择单位重量价格最高的。

然后再选择物品里面第二高的,一次类推直到装满背包为止!

证明

可以利用反证法求证策略一和策略二都不是最优解。

策略三:

需要注意的是Xi 的值是小于等于1的

我们首先假设我们有一个最优解A1,那么我们首先找到A1里面单位价值最高的物品am

  • 情况一:am=商品里面单位价值最高的物品a1。那么问题得证(因为只要不断拿掉单位价值最高的即可)
  • 情况二:am<a1。运用剪枝技巧,讲am 剪掉,补上a1 (a1将am进行全部替换或者部分替换)
    • 如果am 的重量比a1 的重量小,a1 全部替换am
    • 如果am 的重量比a1 的重量大,a1 部分替换am,其余部分保留

Huffman编码

其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

前缀码(Prefix code):任何码字都不是其它码字的前缀。

问题是:如何设计前缀码?

编码树

一种为表示字符二进制编码而构造的二叉树。

叶子结点:对应给定的字符,每个字符对应一个叶子结点。

编码构造:字符的二进制码字由根结点到该字符叶子结点的简单路径表示:0代表转向左孩子,1代表转向右孩子。

一个文件的最优字符编码方案总对应一棵满(full)二叉树,即每个非叶子结点都有两个孩子结点。

最优编码方案

文件的最优编码方案对应一棵满二叉树。

  • 设C为字母表

    • 对字母表C中的任意字符c,令属性c.freq表示字符c在文件中出现的频率(设所有字符的出现频率均为正数)。
    • 最优前缀码对应的树中恰好有|C|个叶子结点,每个叶子结点对应字母表中的一个字符,且恰有|C|-1个内部结点。
  • 令T表示一棵前缀编码树;

  • 令dT(c)表示c的叶子结点在树T中的深度(根到叶子结点的路径长度)。

    • dT(c)也是字符c对应的码字的长度。

令B(T)表示采用编码方案T时文件的编码长度,则:
$$
B(T)=\sum_{c\in C}c.freq*d_T(c)
$$
即文件要用B(T)个二进制位表示.

  • 称B(T)为T的代价。
  • 最优编码:对给定的字符集和文件,使文件的编码长度最小的编码称为最优编码。
    • Huffman编码是一种最优编码。

Huffman编码的贪心算法

自底向上法

1
2
3
4
5
6
7
8
9
10
11
12
13
HUFFMAN(C)//C表示字母表
{
int n=C.size();
queue Q =C;
for(int i=0;i<n-1;i++)
{
new node z;
z.left = x = EXTRACT_MIN(Q);//取队列中频率最小的
z.right=y=EXTRACT_MIN(Q);
z.freq=x.freq+y.freq;
INSERT(Q,Z);//频率低的拼好后,一步步往上累加
}
}

时间分析

Q是使用最小二叉堆实现的。

  • 首先,Q的初始化花费O(n)的时间。

  • 其次,循环的总代价是O(nlgn)。

    • for循环共执行了n-1次,每次从堆中找出当前频率最小的两个结点及把合并得到的新结点插入到堆中均花费O(lgn),所以循环的总代价是O(nlgn).

所以,HUFFMAN的总运行时间O(nlgn)

HUFFMAN算法的正确性

1、第一点:令C为一个字母表,其中每个字符c∈C都有一个频率c.freq。令x和y是C中频率最低的两个字符。那么存在C的一个最优前缀码,x和y的码字长度相同,且只有最后一个二进制位不同。

二叉树T表示字符集C的一个最优前缀码,证明可以对T作适当修改后得到一棵新的二叉树T”,在T”中x和y是最深叶子且为兄弟,同时T”表示的前缀码也是C的最优前缀码。设b和c是二叉树T的最深叶子,且为兄弟。设f(b)<=f(c),f(x)<=f(y)。由于x和y是C中具有最小频率的两个字符,有f(x)<=f(b),f(y)<=f(c)。首先,在树T中交换叶子b和x的位置得到T’,然后再树T’中交换叶子c和y的位置,得到树T’’。如图所示:

由此可知,树T和T’的前缀码的平均码长之差为:

因此,T’’表示的前缀码也是最优前缀码,且x,y具有相同的码长,同时,仅最优一位编码不同。

2、第二点:令C为一个给定的字母表,其中每个字符c∈C都有一个频率c.freq。

令x和y是C中频率最低的两个字符。
令C’为C去掉字符x和y,并加入一个新字符z后得到的字母表,即C’= C -{x, y}∪{z}。

类似C,也为C’定义freq,且z.freq= x.freq+ y.freq。
令T’为字母表C’的任意一个最优前缀码对应的编码树。则有:可以将T’中叶子结点z替换为一个以x和y为孩子的内部结点,得到树T,而T表示字母表C的一个最优前缀码。

最优子结构性质

贪心选择性:

  • 1、第一点说明首次选择频率最低的两个字符和选择其它可能的字符一样,都可以构造相应的最优编码树。
  • 2、第二点说明首次贪心选择,选择出频率最低的两个字符x和y,合并后将z加入元素集合,可以构造包含z的最优编码树,而还原x和y,一样还是最优编码树。
  • 所以贪心选择性成立。

资源分配与调度

资源管理概述

资源:应用程序执行时所需要的全部硬件、软件和数据

资源管理的目标:

  • 保证资源的高利用率。
  • 在“合理”时间内使所有顾客有获得所需资源的机会。
  • 对不可共享的资源实施互斥使用。
  • 防止由资源分配不当而引起的死锁。

资源管理的任务

(1) 资源数据结构的描述
包含资源的物理名、逻辑名、类型、地址、分配状态等信息。

(2) 确定资源的分配原则(调度原则)
决定资源应分给谁,何时分配,分配多少等问题。

(3) 实施资源分配
执行资源分配;资源收回工作。

(4) 存取控制和安全保护
对资源的存取进行控制并对资源实施安全保护措施。

资源的静态分配和动态分配

静态分配

系统对作业一级采用资源静态分配方法。系统在调度作业时,根据作业所需资源进行分配;并在作业运行完毕时,收回所分配的全部资源。这种分配通常称为资源的静态分配。

动态分配

系统对进程一级采用资源动态分配方法。系统在进程运行中,根据进程提出的资源需求,进行资源的动态分配和回收。这种分配通常称为资源的动态分配。

(1)作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后,系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体,是向系统申请分配资源的基本单位。任一进程,只要它被创建,总有相应的部分存在于内存中。

(2)一个作业可由多个进程组成,且必须至少由一个进程组成,反过来则不成立。

(3)作业的概念主要用在批处理系统中,像UNIX这样的分时系统中就没有作业的概念。而进程的概念则用在几乎所有的多道程序系统中。

虚拟资源

  • 物理资源(实资源)

  • 虚拟资源(逻辑资源):用户使用的逻辑资源,这是经过操作系统改造的、使用方便的虚资源,而不是物理的、实际的资源。

可以理解为操作系统将资源进行了封装,用户无需关心具体的资源在哪里,只要关心操作系统向用户提供的虚资源的描述。

资源分配结构和策略

资源管理的实质是资源管理的机制和资源管理的策略

  • 机制:进行资源分配所必须的基本设施和部件,包括描述资源状态的数据结构、保证不可共享资源互斥使用的同步机构以及对不能立即得到满足的资源请求进行排队的各种资源队列的结构。

  • 策略:资源分配的原则。

资源分配的机构

资源描述器

描述各类资源的最小分配单位的数据结构称为资源描述器rd(resource descriptor)。如:主存分区分配方法中,最小分配单位为主存分区。资源描述器描述了资源的特性和该资源的管理方式

用于资源分配的最重要的信息是这一资源分配单位是可用的还是已分配的。

  • 若它具有N个资源分配器,则有N个资源描述器。这些描述器的组织是个重要问题。
  • 描述器的组织方式取决于资源分配单位的数量和数量是否可变这一特征。
    • 如果数量不可变,使用表结构。
    • 如果数量可变,使用队列结构。
    • 如果数目变化范围可知且不大,使用数组。

资源描述器的内容:

资源名、资源类型、最小分配单位的大小、地址、分配标志、描述器链接信息、存取权限、密级、存取时间

资源信息块

描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。

资源分配程序包括了资源分配程序和资源回收程序。当有进程请求资源的时候,先去资源分配程序中看看有没有资源,没有的话,将进程加入到等待资源队列中;当进程执行释放资源命令时,使用资源回收程序,将释放的资源加入到可利用资源的队列中。

资源分配策略

对某类资源而言,在多个资源有多个请求者申请的情况下,资源分配的策略包括选择请求者的策略和选择资源的策略两种。

选择请求者的策略:即资源分配策略,即在众多请求者中选一个满足条件的请求者的原则。

选择资源的策略:是在同等资源间选择一个满足条件的资源的原则。

具体实现:体现在队列的排队原则上。

资源分配的时机

  • 当请求者发出一个明确的资源请求命令时;
  • 当处理机空闲时;
  • 当一个存储区被释放变为空闲时;
  • 当一个外存设备发生完成中断时。

先请求先服务策略

每一个新产生的请求均排在队尾;当资源可用时,取队首元素,并满足其需要。

排序原则:按请求的先后次序排序。(有饿死现象!

优先调度策略

对每一个进程指定一个优先级,优先级反映了进程要求处理的紧迫程度;

每一个新产生的请求,按其优先级的高低插到相应的位置;

当资源可用时,取队首元素,并满足其需要。

排序原则:按优先级的高低排序。

缺点:因为优先级不同,会存在插队的状况。所以会消耗时间,导致效率下降

针对设备特性的调度策略

目的是为了当有大量I/O请求时,降低完成这些I/O服务的总时间。

移臂调度

总是选取与当前移动臂前进方向上最近的那个I/O请求,使移臂距离最短。

移臂的方向是由外向里,即柱面号由小到大

旋转调度

总是选取与当前读写头最近的那个I/O请求,使旋转圈数最少。

几种移臂调度算法

最短寻道时间优先算法(SSTF)

从等待访问者中挑选寻找时间最短的(也就是离得最近的)那个请求先执行

缺点:可能会引起读写头在盘面上的大范围移动,可能会推迟请求的服务导致无限拖延

扫描算法(SCAN,即电梯调度算法)

磁头前进方向上的最短查找时间优先算法。

很大程度上消除了SSTF的不公平性

循环扫描算法(CSCAN)

就是在电梯算法的基础上,一个方向找完了,回到起点再找(电梯算法是一个方向找完了转身反方向找)

死锁

在两个或多个并发进程中,如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源,否则就不能向前推进。此时,称这一组进程产生了死锁。

死锁的起因和条件

死锁的原因

①系统资源不足

②进程推进顺序非法

产生死锁的必要条件

①互斥条件

涉及的资源是非共享的,即为临界资源。

②不剥夺条件

进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走。

(根据操作系统的特性,例如windows系统就是不可剥夺的)

③部分分配

进程每次申请它所需要的一部分资源。在等待一新资源的同时,进程继续占用已分配到的资源。

④环路条件

存在一种进程的循环链,链中的每一个进程已获得的资源同时被链中下一个进程所请求。

解决死锁问题的策略

破坏产生死锁的四个必要条件之一

  • 采用静态资源分配方法——预防死锁。
  • 采用有控资源分配方法——避免死锁
  • 死锁的检测与忽略

死锁的预防和避免

静态预防死锁的方法

在作业调度时为选中的作业分配它所需要的所有资源,当资源一旦分配给该作业后,在其整个运行期间这些资源为它独占。

动态避免死锁的方法

有序资源分配法(破坏了部分分配和循环等待)

系统中所有资源都给定一个唯一的编号,所有分配请求必须以上升的次序进行。当遵守上升次序的规则时,若资源可用,则予以分配;否则,请求者等待。(缺点:资源浪费!)

银行家算法

申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时,由系统审查现有该类资源的数目是否能满足当前进程的最大需求量,如能满足就予以分配,否则拒绝。

死锁的检测与忽略

检测:算法复杂,开销很大

忽略:后患无穷

问题

假设一个可移动磁头的磁盘具有 200个磁道,其编号为0~199,当它刚刚结束了 125道的存取后,现正在处理143道的服务请求,假设系统当前的请求序列以请求的先后次序排列如下: 86、147、91、177、150、102、175、130。试问对以下几种磁盘IO请求调度算法而言,满足以上请求序列,磁头将分别如何移动?

(1) 先来先服务算法(FCFS)

(2) 最短寻道时间优先调度(SSTF)

(3) 扫描算法(SCAN)

(4) 循环扫描算法(CSCAN)

答:

(1) FCFS:143→86→147→91→177→150→102→175→130;

(2) SSTF:143→147→150→130→102→94→91→86→175→177;

(3) SCAN:143→147→150→175→177→130→102→94→91→86;

(4) C-SCAN:143→147→150→175→177→86→91→94→102→130。

5-9 三个进程共享四个同类资源,这些资源的分配与释放只能一次一个,已知每一进程最多需要两个资源,试问该系统会发生死锁吗?为什么?

答:该系统不会发生死锁。

因为最坏情况是每个进程都占有一个资源,申请第二个资源,而此时系统中还剩一个资源,不管这个资源分给哪个进程,都能满足它的资源要求,因此它能在有限时间内运行结束而释放它所占有的两个资源,这两个资源又可以分配给另外两个进程,使它们能够运行结束,所以系统不会发生死锁。

5-10 p个进程共享m个同类资源,每一个资源在任一时刻只能供一个进程使用,每一进程对任一资源都只能使用一有限时间,使用完便立即释放,并且每个进程对该类资源的最大需求量小于该类资源的数目,设所有进程对资源的最大需求数目之和小于p+m,试证在该系统中不会发生死锁。

解:采用“反证法”,假定max(i)为第i个进程最大资源需求量,need(i)为第i个进程还需要的资源量,alloc(i)为第i个进程已分配的资源量,则

max(i)<=m

max(i)=need(i)+alloc(i)

max(1)+L+ max(p)=(need(1)+ L…+need(p))+(alloc(1)+ L…+alloc(p))<p+m

若发生死锁,则需要满足下面两个条件,

① 全部分配,alloc(1)+…+alloc(p)=m;② 所有进程无限等待

由①②可得, need(1)+…+need(p)<p

则死锁后,p个进程需要的资源小于p,则一定存在进程i,need (i) = 0,进程已获得全部资源,进程i 可以执行完,同假设发生矛盾,所以不会发生死锁。

5-11图5.9 表示一带闸门的运河,其上有两架吊桥,吊桥坐落在一条公路上,为使该公路避开一块沼泽地而其横跨运河两次。运河和公路的交通都是单方向的,运河的基本运输由驳船担负。在一艘驳船接近吊桥A 时就拉汽笛警告,若桥上无车辆,吊桥就吊起,直到驳船尾部通过该桥为止,对吊桥B按同样次序处理

(1) 一艘典型驳船的长度为200 米,当它在河道航行时是否会产生死锁?若会,其理由是什么?

(2) 如何能克服一个可能的死锁?请想出一个防止死锁的办法。

(3) 如何利用信号灯的P、V 操作实现车辆和驳船的同步?

(1) 答:驳船长200 米,当驳船通过了A 桥,其船头到达B 桥,请求B 桥吊起,而此时它的尾部占据A 桥,若这个时候B 桥及B桥到A 桥之间的公路都被汽车占据,而汽车又要求通过A 桥。这样驳船和汽车都无法前进,形成死锁的局面。

(2) 答:方案之一。可规定资源按序申请和分配,从而破坏了死锁的循环等待条件,防止死锁的发生。规定如B 桥的序号小于A 桥的序号,驳船和汽车都必须先申请序号小的资源B 桥,申请得到满足后,再申请序号大的资源A 桥。

(3) 答:将每台车的行驶看作是进程,则有Auto1,Auto2,LAutoi i个汽车进程。将每条驳船的航行看作是进程,则有Ship1,Ship2,LShipj个驳船进程。桥A和桥B对车和船为互斥资源。

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
main{
int SA=1//A桥的互斥信号量//
int SB=1//B桥的互斥信号量//
cobegin
Auto1;Auto2;···Autoi;
Ship1; Ship2; ···Shipj;
coend
}

Autoi(){
车在公路上行驶;
P(SB);
过B桥;
V(SB);
过弯道;
P(SA);
过A桥;
V(SA);
车在公路上行驶;
}

Shipj(){
运河航行;
P(SB);
P(SA);
吊起过A桥;
运河航行;
吊起过B桥;
V(SA);
V(SB);
运河航行;
}

5-14在采用银行家算法管理资源分配的系统中,有A、B、C三类资源可供5个进程P1、P2、P3、P4、P5共享。3类资源的总量为(17, 5, 20),即A类17个,B类5个,C类20个。假设T0时刻各进程对资源的需求和分配情况如下表所示。

img

(1) 现在系统是否处于安全状态?如是,给出一个安全序列。

(2) T0时刻,如果进程P4和P1依次提出A、B、C资源请求(2,0,1)和(0,2,0),系统能否满足它们的请求?请说明原因。

答:(1)系统处于安全状态,如P4→P2→P3→P5→P1。

(2)不能满足。由于P4与P1提出请求后,A、B、C剩余(0,1,2),此时A类无,只能等待拥有足够A类资源的进程结束释放A类资源,别的进程才能执行,而此时P4需(0,2,0),P3需(0,0,6),而剩余(0,1,2),不能满足要求,产生死锁。

1. 设有一个售票大厅,可容纳200人购票。如果厅内不足200人则允许进入,超过则在厅外等候;售票员某时只能给一个购票者服务,购票者买完票后就离开。试问:

(1) 购票者之间是同步关系还是互斥关系?

答:互斥关系。

用P、V操作描述购票者的工作过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore empty=200;
semaphore mutex=1;
semaphore waiting=0
void buy()
{ p(waiting);
p(mutex);
买票;
v(mutex);
v(empty);
}

void waiting()
{
p(empty);
等待;
waiting++;
}

主存管理概述

现代操作系统将主存区分为物理主存和逻辑主存2类。

物理主存是共享的物质基础。由多个物理地址构成。

主存共享方式—-分片共享

分片的方式

(1) 大小不等的区域—根据用户程序的实际需要决定分区的大小

①分区存储管理

②段式存储管理

(2) 大小相等的区域—以块为单位,根据用户程序的实际需要决定应分配的块数

页式存储管理

(3) 二者结合

段页式存储管理

由于不同程序的物理地址的首地址都是乱七八糟的,不方便用户使用。所以采用逻辑地址(虚地址)将首地址设置为0。逻辑地址和物理地址之间的映射就是地址映射。

程序的逻辑组织

一维地址结构

一个程序是一个连续、线性的地址结构;确定线性地址空间中的指令地址或操作数地址只需要一个信息。

二维地址结构

一个程序由若干个分段组成(数据段、代码段、栈段······),每个分段是一个连续的地址区;

确定线性地址空间中的指令地址或操作数地址需要两个信息,一是该信息所在的分段,另一个是该信息在段内的偏移量。

主存管理功能

实现的功能:主存分配、主存保护、虚拟主存

  • 地址映射—-将逻辑地址映射成物理地址
  • 主存分配—-在多用户之间分配物理主存
  • 存储保护—-对各用户区的信息提供保护措施
  • 主存扩充/虚拟主存—-扩充逻辑主存区

地址映射

将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程,称为地址映射。

地址重定位就是操作系统将逻辑地址转变为物理地址的过程。。。也就是对目标程序中的指令和数据进行修改的过程

将逻辑地址空间重定位到物理地址空间的时机有三种:

1、程序编译连接时。

​ 在程序编写或程序编译时确定虚、实地址之间的对应关系,结果是一个不能浮动的程序模块。

2、程序装入内存时。

​ 在程序装入过程中随即进行的地址变换方式称为静态地址映射

3、程序执行时。

​ 在程序执行期间,随着每条指令和数据的访问自动地连续地进行地址映射,这种地址变换方式称为动态地址映射

静态地址映射与动态地址映射的区别

静态地址映射 动态地址映射
在程序装入过程中在程序执行期间进行地址映射 在程序执行期间进行地址映射进行地址映射
需软件(重定位装入程序) 需硬件地址变换机构( 重定位寄存器)
需花费较多CPU时间 地址变换快
不灵活 灵活

一、静态重定位
  静态重定位是在程序执行之前进行重定位,它根据装配模块将要装入的内存起始位置,直接修改装配模块中的有关使用地址的指令。
  例如,一个以“0”作为参考地址的装配模块,要装入以100为起始地址的存储空间。显然,在装入之前要做某些修改,程序才能正确执行。例如,MOV  EAX,[500]这条指令的意义,是把相对地址为500的存储单元内容1234装入EAX号累器。现在内容为1234的存储单元的实际地址为1500, 即为相对地址(500)加上装入的地址(1000),因此,MOV EAX,[500]这条指令中的直接地址码也要相应地加上起始地址,而成为MOV  EAX,[1500]。
  程序中涉及直接地址的每条指令都要进行这样的修改。需要修改的位置称为重定位项,所做的加实际装入模块起始地址修改中的块起始地址称为重定位因子。
  为支持静态重定位,连接程序在生成统一地址空间和装配模块时, 应产生一个重定位项表,连接程序此时还不知道装配模块将要装入的实际位置,故重定位表 所给出的需修改位置是相对地址所表示的位置。
  操作系统的装入程序要把装配模块和重定位项表一起装入内存。由装配模块的实际装入起始地址得到重定位因子,然后实施如下两步:
  (1)取重定位项,加上重定位因子而得到欲修改位置的实际地址;
  (2)对实际地址中的内容再做加重定位因子的修改,从而完成指令代码的修改。
  对所有的重定位项实施上述两步操作后,静态重定位才完成,尔后可启动程序执行。使用过的重定位项表内存副本随即被废弃。

  静态重定位有着无需硬件支持的优点,但存在着如下的缺点:一是程序重定位之后就不能在内存中搬动了;二是要求程序的存储空间是连续的,不能把程序放在若干个不连续的区域内。

二、动态重定位
  动态重定位是指,不是在程序执行之前而是在程序执行过程中进行地址重定位。更确切地说,是在CPU每次访问内存单元前才进行地址变换。动态重定位可使装配模 块不加任何修改而装入内存,但是它需要硬件——定位寄存器的支持。
  程序的目标模块装入内存时,与地址有关的各项均保持原来的相对地址不进行任何修改。如MOV 1,[500]这条指令仍是相对地址500。当此模块被 操作系统调度到处理机上执行时,操作系统将把此模块装入的实际起始起始地址减去目标模块的相对基地址,然后将其差值装入定位寄存器中。当CPU取得一条访问内存的指令时,地址变换硬件逻辑自动将指令中的相对地址与定位寄存器中的值相加,再依此和值作为内存绝对地址去访问该单元中的数据。
  由此可见,进行动态重定位的时机是在指令执行过程中,每次访问内存前动态地进行。采取动态重定位可带来两个好处:
  (1)目标模块装入内存时无需任何修改,因而装入之后再搬迁也不会影响其正确执行,这对于存储器紧缩、解决碎片问题是极其有利的;
  (2)一个程序由若干个相对独立的目标模块组成时,每个目标模块各装入一个存储区域,这些存储区域可以不是顺序相邻的,只要各个模块有自己对应的定位寄存器就行。

  动态重定位技术所付出的代价是需要硬件支持。

主存分配

用于主存分配的数据结构:主存资源信息块、空闲区队列;

主存管理器的一些策略

分配策略——在众多个请求者中选择一个请求者的原则

放置策略——在可用资源中,选择一个空闲区的原则

调入策略——决定信息装入主存的时机预调策略:预先将信息调入主存请调策略:当需要信息时,将信息调入主存

淘汰策略——在主存中没有可用的空闲区(对某一程序而言)时,决定哪些信息从主存中移走,即确定淘汰已占用的内存区的原则。

调入策略对页式系统或非页式系统没有多大区别,但是淘汰策略和放置策略在页式和非页式系统中是不同的。(页式的页的大小是固定的)

主存扩充

实现的方法:

  • 程序的全部代码和数据存放在辅存中;
  • 将程序当前执行所涉及的那部分程序代码放入主存中;
  • 程序执行时,当所需信息不在主存,由操作系统和硬件相配合来完成主存从辅存中调入信息,程序继续执行。

虚拟存储器

由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器,这个存储器称为虚拟存储器。本质的大小其实是没有变的,但是给用户的感觉就是变大了,1元钱看成了100元,这100元就是虚拟存储器

虚拟存储器的核心是将程序的访问地址和主存的物理地址分离。为什么这么说?我们知道访问地址其实是逻辑地址(虚地址),它会去进行地址映射找到主存地址(这个功能由操作系统实现,所以用户不用管)。但是引入了虚存后(不要和虚地址搞混淆了),我们不需要了解主存的物理地址,我们只在虚存中运行(当然,真正运行的时候还是调入一部分进主存的)。这样就把访问地址和虚存互相对应(也就说成了和主存的物理地址分离)

  • 逻辑地址与物理地址分开
  • 存储空间与虚地址空间分开
  • 提供地址变换机构

实现虚拟存储器的物质基础

  • 有相当容量的辅存:足以存放应用程序的虚地址空间
  • 有一定容量的主存:存放进入主存的多进程的信息
  • 地址变换机构

存储保护

在多用户环境中,主存储器按区分配给各用户程序使用。为了互不影响,必须由硬件(软件配合)保证各用户程序只能在给定的存储区域内活动,这种措施叫做存储保护。

界地址保护

上、下界保护

比较的是物理地址

硬件为分给应用程序的每一个连续的主存空间设置一对上下界寄存器—–分别指向该存储空间的上界和下界。

基地址、限长保护

比较的是逻辑地址

基地址存放的是逻辑地址—段的首地址

存储键保护

分区存储管理

对应的是主存分配

动态分区分配

在处理程序的过程中,建立分区,依用户请求的大小分配分区。

很明显,空闲区被切碎会产生内存碎片。

动态分区的分配方法中,对用户程序进行动态分配并实现动态地址映射(这个不难理解,由于在动态分区中,系统是根据程序的大小再决定分给程序内存空间的大小,在地址映射中,事先根本就不可能有物理地址让你静态地址映射)

分区分配数据结构

主存资源信息块(M_RIB)

分区描述器(PD)

flag:为0 ——空闲区
为1 ——已分配区

size:分区大小

next:空闲区——自由主存队列中的勾链字
已分配区——此项为零

分区的分配和回收

注意:动态地址映射只是决定了用户程序什么时候将虚地址映射到物理地址中。但是主存分配给用户程序的地址还没有决定。

分区分配

动态分区的策略如下:“放置策略”

①寻找空闲块
依申请者所要求的主存区的大小,分区分配程序在自由主存队列中找一个满足用户需要的空闲块;

②若找到了所需的空闲区,有两种情况
i 空闲区与要求的大小相等,将该空闲区分配并从队列中摘除;
ii 空闲区大于所要求的的大小,将空闲区分为两部分:一部分成为已分配区,建立已分配区的描述器;剩下部分仍为空闲区。返回所分配区域的首址;

③否则,告之不能满足要求。

分区回收

①检查释放分区(即为回收分区)在主存中的邻接情况
若上、下邻接空闲区,则合并,成为一个连续的空闲区

②若回收分区不与任何空闲区相邻接
建立一个新的空闲区,并加入到空闲区队列中。

放置策略

选择空闲区的策略,称为放置策略。

本质上是空闲区队列的排序问题:
如上述提到的从高地址到低地址的分配方式:对应的就是按照地址增加、减少的次序分类排序
其他的排序还有:按照区的大小增加、减少的次序排序

常用的放置策略——

  • 首次匹配(首次适应算法)
  • 最佳匹配(最佳适应算法)
  • 最坏匹配(最坏适应算法)

首次适应

首次适应算法是将输入的程序放置到主存里第一个足够装入它的地址最低的空闲区中。

空闲区队列结构:

空闲区地址由低到高排序

首次适应算法的特点

尽可能地利用存储器中低地址的空闲区,而尽量保存高地址的空闲区。

最佳适应

最佳适应算法是将输入的程序放置到主存中与它所需大小最接近的空闲区中。

空闲区队列结构

空闲区大小由小到大排序

最佳适应算法的特点

尽可能地利用存储器中小的空闲区,而尽量保存大的空闲区。

最坏适应

最坏适应算法是将输入的程序放置到主存中与它所需大小差距最大的空闲区中。

空闲区队列结构

空闲区大小由大到小排序

最坏适应算法的特点

尽可能地利用存储器中大的空闲区。

碎片问题及拼接技术

在已分配区之间存在着的一些没有被充分利用的空闲区。

所谓拼接技术是指移动存储器中某些已分配区中的信息,使本来分散的空闲区连成一个大的空闲区。

页式存储管理

程序的存放将不再是连续的。

程序的地址空间被等分成大小相等的片,称为页面,又称为虚页。
一般页面的大小为1KB、2KB、4KB

主存被等分成大小相等的片,称为主存块,又称为实页。

主存的块和页面的大小是相等的并且为2的幂次

好处:可以方便的支持虚拟存储,扩充内存。因为它可以只将一部分页面装入主存中即可。也直接解决了碎片问题。

但是在按区分配中,

需要解决的问题:

  • 页式系统的地址映射—–动态地址映射
  • 请调策略—-当装入部分页面的时候,需要询问当前访问的信息是否在主存中。不在的话,系统会从辅存中调入请求的页面。
  • 放置策略—-确定程序的各个页面分配到主存的哪些块中,以及什么原则挑选主存块
  • 淘汰策略—-当主存块用完后,确定哪些页面被淘汰出主存。

页式地址变换

页表

为了实现从地址空间到物理主存的映象,系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表,简称页表。

页表的组成:

​ i 如果选择高速缓冲存储器:地址变换速度快,但成本较高

​ ii 如果选择主存区域:地址变换速度比硬件慢,成本较低主存管理——页式存储管理

虚地址结构

页号+页内位移。

当CPU给出一个虚地址(指令地址或者操作数地址),将其拆分成页号和页内位移表示该地址对应于物理地址中的具体位置(哪个页面和页面中的哪个位置)

页式地址变换

页式地址变换步骤

i CPU给出操作数地址(为2500) ;
ii 由分页机构自动地把逻辑地址分为两部分,得到页号p和页内相对位移w (p =2,w =452);
iii 根据页表始址寄存器指示的页表始地址,以页号为索引,找到第2页所对应的块号(为7) ;
iv 将块号b和页内位移量w拼接在一起,就形成了访问主存的物理地址(7x1024+452=7620)

通过页表将虚地址(也就是逻辑地址)中的页号对应到物理地址中的块号。由于页面的大小和内存块的大小是一样的,所以虚地址的页内位移就是物理地址中的块内位移。

分区管理的地址映射:

每个进程在分区说明表( 为了管理分区,设置一张不属于任何进程的分区说明表,也就是放置策略章节对应的分区表)找到自己对应的表项目,根据表中的物理起始地址+自己的逻辑地址,就得到了实际的物理地址!目前为止需要注意的是,分区分配中,每个进程的分配的物理空间仍然是连续的!

换一个说法:

作业装入内存时,是将该用户的程序和数据原封不动地装入到内存中。当调度该进程在cpu上执行时,操作系统就自动将该进程在内存的起始地址装入基址寄存器,将进程的大小装入限长寄存器
。当执行指令时,如果地址合法,则将相对地址与基址寄存器中的地址相加,所得结果就是真正要访问的内存地址;如果地址越界,则发出相应中断,进行处理。

虚实地址映射极为简单。

联想存储器LSB

高速、小容量半导体存储部件,又称缓冲存储器

快表

在缓冲存储器中存放正在运行的进程当前用到的页号和对应的块号,又称为快表。

具体可以参见《组成原理》中《存储系统》章节。

注意一点:页表查询只在联想映像不匹配时进行

请调页面的机制

①简单页式系统:装入一个程序的全部页面才能投入运行。

②请求页式系统:装入一个程序的部分页面即可投入运行。

Q:如何发现所要访问的页面不在主存?

A:扩充页表功能

Q:如何确认所要访问的页面不在主存时如何处理?

A:缺页处理

扩充页表功能

中断位i:标识该页是否在主存

​ 若i=1,表示此页不在主存;
​ 若i=0,表示该页在主存

辅存地址:该页面在辅存的位置

缺页处理

  • 当从虚地址中得到页号,判断页号不在主存的时候,会发送缺页中断。

  • 接下来要将缺页的部分拉回到主存中:

    • 判断时候有空闲块:
      • 有的话就从辅存读入所需的页,并且调整存储分配表和页表,然后重新启动被中断的指令
      • 没有的话根据淘汰算法选择一页淘汰(淘汰掉的页如果还有用就将其放回辅存,没有用就丢掉),调整存储分配表和页表。然后从辅存中读入所需的页

淘汰机制和策略

用来选择淘汰哪一页的规则叫做置换策略,或称淘汰算法。

Q:如何确定那一页被淘汰?

A:根据最近有没有使用、使用频率等

扩充页表功能

①引用位——标识该页最近是否被访问
为“0”——该页没有被访问;为“1”——该页已被访问

②改变位——表示该页是否被修改
为“0”——该页未被修改;为“1”——该页已被修改

颠簸(thrashing),又称为“抖动”

简单地说,导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为“抖动”。

缺页中断率

假定程序p共有n页,系统分配m块,有1≤m≤n;若程序p在运行中:成功的访问次数为s,不成功的访问次数为f;缺页中断率:
$$
f′=f/ (s+ f)\
f′= f (r,m,p);\
r:置换算法;m:系统分配的块数;p:程序特征
$$

常用的置换算法

最佳算法(OPT算法)

当要调入一新页而必须先淘汰一旧页时,所淘汰的那一页应是以后不再要用的,或者是在最长的时间以后才会用到的那页。

简单说,就是不肯可能实现的(你怎么知道那页是以后不用的)

站在现在,往未来看

先进先出淘汰算法(FIFO算法)

总是选择在主存中居留时间最长(即最早进入主存)的一页淘汰。

实现

  • 建立一个页面进入主存的先后次序表;
  • 建立一个替换指针,指向最早进入主存的页面;
  • 当需要置换一页时,选择替换指向的那一页,然后调整替换指针的内容(指向替换后最早进入主存的页面,因为之前最早进入的被替换出去了)。

在存储分块表中记录页面进入主存的先后次序:4→5→1→2 当要调入第6页时:如何处理? 5→1→2 →6

最久未使用淘汰算法(LRU算法)

总是选择最长时间未被使用的那一页淘汰。

实现

  • 用引用位考察页面的使用情况;

  • 当访问页面时,将引用位置1,并记时;

  • 当要淘汰一页时,选择时间最长的一页淘汰。

    要精确实现很困难

    • 硬件方法:采用计数器
    • 软件方法:采用页号栈

段式、段页式存储管理

段式地址空间

分段是程序中自然划分的一组逻辑意义完整的信息集合。
分段的例:代码分段、数据分段、栈段页。

程序地址空间

由若干个逻辑分段组成,每个分段有自己的名字,对于一个分段而言,它是一个连续的地址区。

段式地址结构

段式地址变换

步骤:

  • 取出程序地址(s,w);
  • 用s检索段表;
  • 如w<0或w≥L则主存越界;
  • (B+w)即为所需主存地址(B是基址

页式系统与段式系统的区别

用户地址空间的区别

①页式系统中用户地址空间:一维地址空间

②段式系统中用户地址空间:二维地址空间

分段和页面的区别

分段 页面
信息的逻辑划分 信息的物理划分
段长是可变的 页的大小是固定的
用户可见 用户不可见
w字段的溢出将产生越界中断 w字段的溢出自动加入到页号中

段页式系统

在段式存储管理中结合分页存储管理技术,在一个分段内划分页面,就形成了段页式存储管理。

程序地址空间

地址结构=段号+段内页号+页内位移

每一个程序一张段表,每个段对应一张页表,段表中的地址是页表的起始地址

段页式地址变换要得到物理地址需要经过3次主存访问(当段表、页表都在主存中):

  1. 访问段表,得到页表起始地址
  2. 访问页表,得到主存块号
  3. 将主存块号与页内位移组合得到物理地址

问题

第七章 习题及解答

7-11如图7.45所示,主存中有两个空白区。现有如下程序序列:程序1要求50KB;程序2要求60KB;程序3要求70KB。若用首次适应算法和最佳适应算法来处理这个程序序列,试问:哪一种算法可以分配得下 ? 简要说明分配过程 (假定分区描述器所占用的字节数已包含在程序所要求的主存容量中) 。

答:(1) 首次适应法:

程序1要求50KB,在起始地址为150KB,大小为120 KB的空白区进行分割。120KB-50KB=70KB,分割后剩70KB 的空白区。

程序2要求60KB,在剩余的70KB空白区进行分割。70KB-60KB=10KB,分割后剩 10KB的空白区。

程序3要求70KB,在起始地址为300KB,大小为78KB的空白区进行分割。78KB-70KB=8KB,分割后剩8KB 的空白区。

因此首次适应法可满足该程序序列的需求。

(2) 最佳适应法

程序1要求50KB,在起始地址为300KB,大小为78 KB的空白区进行分割。78KB-50KB=28KB,分割后剩28KB 的空白区。

程序2要求60KB,在起始地址为150KB,大小为120KB的空白区进行分割。120KB-60KB=60KB,分割后剩60KB的空白区。

程序3要求70KB,。此时系统中有大小为 28KB 和60KB 的两个空白区,它们均不能满足程序3 的需求。

因此最佳适应法不能满足该程序序列的需求。

设备管理概述

操作系统的设备管理,又称为I/O管理,它负责管理设备和控制I/O传输操作。

设备分类:

  • 存储设备

    存储设备又称块设备,是存储信息的设备,如:磁盘、 磁鼓 (以块为单位传输信息) 。

  • 输入输出设备

    输入输出设备又称字符设备,能将信息从计算机外部输入到机内,或反之,如:键盘、显示器、打印机 (以子符为单位传输信息) 。

  • 通信设备

    通信设备负责计算机之间的信息传输,如调制解调器、网卡等。

设备管理的目标

(1) 提高设备利用率

合理分配设备

提高设备与CPU、各外部设备之间的并行性

(2) 方便用户的使用

​ 提供使用方便且独立于设备的界面

统一:对各种不同的设备提供一致的界面

独立于设备:用户使用的设备与物理设备无关

(可以看成具有良好的封装性)

设备管理的三大功能

(1) 状态跟踪

动态地记录各种设备的状态。设备状态信息保留在设备控制块中。

(2) 设备分配与回收

静态分配 —— 应用程序级

程序进入系统时进行分配,退出系统时收回全部资源。

动态分配 —— 进程级

​ 进程提出设备申请时进行分配,使用完毕后立即收回。

(3) 设备控制

实施设备驱动和中断处理的工作。

设备独立性

所谓设备独立性是指,用户在程序中使用的设备与实际使用的设备无关,也就是在用户程序中仅使用逻辑设备名。

逻辑设备名

逻辑设备名,是用户自己指定的设备名 (或设备号),它是暂时的、可更改的。

物理设备名

物理设备名,是系统提供的设备的标准名称,它是永久的、不可更改的。

两种类型的设备独立性

一个程序独立于分配给它的某种类型的具体设备

系统可以根据设备的使用情况,动态地分配给程序某类设备中的任一台物理设备,程序都能正确地执行。

程序应尽可能与它所使用的I/O设备类型无关

在输入 (或输出)信息时,信息可以从不同类型的输入 (或输出)设备上输入 (或输出),若要改变输入 (或输出) 设备的类型,程序只需进行最少的修改。

优点:

​ 很明显,方便用户、改善设备利用率、提高系统的可扩展性和可适应性

逻辑设备描述器ldd:

描述了进程的逻辑设备和物理设备名的对应关系。

设备独立性的实现

在高级语言中用软通道实现

使用高级语言提供的指派语句,通过指派一个逻辑设备名(通道号)来定义一个设备或文件。

​ 如:fd = open(“/dev/lp”, mode)

在批处理系统中,用联接说明语句来定义

如:OUTPUT1 = LPT

在交互系统中,用指派命令来定义

​ 如:PDP系列机上的RT11系统

​ ASSIGN 设备物理名 设备逻辑名

设备控制块DCB

系统为每一台设备都配置了一个用来记录设备的硬件特性、连接和使用情况的一组数据,称为设备控制块。

设备名

设备的系统名,即设备的物理名

设备属性

描述设备现行状态的一组属性。

命令转换表

​ 转换表包含设备特定的I/O例程地址,不具备相应功能的设备在其例程地址上可以填“-1”。

缓存技术

缓冲是两种不同速度的设备之间传输信息时平滑传输过程的常用手段。

缓冲类别:

缓冲器

​ 缓冲器是用来暂时存放数据的一种存储装置,它容量较小,存取速度快。

软件缓冲

​ 在I/O操作期间用来临时存放I/O数据的一块存储区域。

引入缓冲的目的:

处理数据流的生产者与消费者间的速度差异

​ 如:从调制解调器收到一个文件,并保存到硬盘上。

协调传输数据大小不一致的设备

​ 如:在计算机网络中用来处理消息的分段和重组。

应用程序的拷贝语义

​ 如:操作系统需要保证系统调用write的正确语义 (应用程序要写入磁盘的数据就是write系统调用发生时的版本)。

​ 方法:在系统调用返回前将应用程序缓冲区复制到内核缓冲区。

利用缓冲技术进行I/O操作

进程活动时,读入数据

步骤:

ⅰ 当用户要求在某个设备上进行读操作时,首先从系统中获得一个空的缓冲区 (图中标注的操作①);

ⅱ 将一个物理记录送到缓冲区中 (图中标注的存在②) ;

ⅲ 当用户请求这些数据时,系统将依据逻辑记录特性从缓冲区中提取并发送到用户进程存储区中 (图中标注的操作③) ;

ⅳ 当缓冲区空而进程又要从中取用数据时该进程被迫等待。此时,操作系统需要重新送数据填满缓冲区,进程才能从中取数据继续运行。

要注意操作②与操作③的同步关系

进程活动时,输出数据

步骤:

ⅰ 当用户要求进行写操作时,首先从系统中获得一个空的缓冲区 (图中标注的操作①) ;

ⅱ 将一个逻辑记录从进程存储区传送到缓冲区中 (图中标注操作②) ;

ⅲ 当缓冲区写满时,系统将缓冲区的内容作为物理记录文件写到设备上,使缓冲区再次为空 (图中标注的操作③) ;

ⅳ 只有在系统还来不及腾空缓冲区之前,进程又企图输出信息时,它才需要等待。

要注意操作②与操作③的同步关系

上述在保证BUF写、输入是满的前提下再进行输出、输入操作是为了保证数据的可靠性

双缓冲

在双缓冲方案下,为输入或输出分配两个缓冲区buf1 、 buf2 。

①输入设备先填满BUF1

②进程从BUF1提取数据的同时,输入设备填充BUF2

③当BUF1空、BUF2满时,进程又可从BUF2提起数据,与此同时,输入设备又填充BUF1

还可以使用缓冲池。

UNIX系统的缓冲区管理

目的:

加快系统响应、增强系统吞吐量

减少对磁盘的I/O操作次数

UNIX系统缓冲管理的思路

  • 当进程要从磁盘读数据时,首先考虑从高速缓冲中读———–预先缓存

  • 当进程要写数据到磁盘时,先写入高速缓冲中———–延迟发送

缓冲区队列结构

设备缓冲区队列

与某类设备有关的所有缓冲区组成的队列称为设备缓冲区队列,简称b链。

空闲缓冲区队列

可供重新分配使用的缓冲区组成的队列称为空闲缓冲区队列,简称av链。

步骤:

​ ⅰ 一个buf被分配用于读/写某设备上的块时置B_ BUSY=1,位于b链上,不在av链上;

​ ⅱ 当读/写操作结束时释放该buf,置B_BUSY=0,仍留在b链上,并送入av链尾

  • 在空闲缓冲区队列中的缓存,只要还没有重新分配就保持原有内容不变

​ ⅲ 若进程需要的信息在buf中时在该设备的b链上找到,置B_BUSY=1;从av链上摘除,使用完后,又送入av链,链入队尾。

​ ⅳ 对空闲buf空队列的处理
​ 当需要一个空闲buf时,总是取空闲buf队列(av链) 的首元素;一个使用过的buf释放时,插入到空闲buf队列(av链)的队尾。

实现了精确的最久未使用淘汰算法 (LRU算法)

​ ⅴ 对延迟写的处理
​ 当一个具有延迟写标记的buf移到av链头,要用于分配时,立即进行写操作。从av链上摘除,使用完后又送入av头部。

设备分配

独占分配

在一个作业执行前,将它所要使用的设备分配给它;当它结束撤离时,将分配给它的这类设备收回。

让一个作业在整个运行期间独占使用的设备

特点

ⅰ 临界资源

ⅱ 费时的I/O操作或需人工干预

可能会引起进程死锁

共享分配

由多个作业、进程共同使用的设备称为共享设备。

特点

ⅰ 旋转设备,可直接或随机访问

ⅱ 便于共享,转接简单,耗费较少

不会引起进程死锁

虚拟分配

就是如果要使用独占设备的话,就先将数据输入、输出到辅存中。当进程需要输入数据、输出数据的时候,再把数据输入、输出(从辅存中)。理论上一个独占设备可以和辅存上的多个存储区连接,就形成了独占设备变成共享设备的假象。

本质上是提高了独占设备的利用率。

(1) 虚拟技术

​ 所谓虚拟技术,是在一类物理设备上模拟另一类物理设备的技术,是将独占设备转化为共享设备的技术。

(2) 虚拟设备

​ 通常把用来代替独占型设备的那部分外存空间 (包括有关的控制表格)称为虚拟设备。

(3) 虚拟分配

    当进程需要与独占型设备交换信息时,系统将分配磁盘空间,并建立相应的数据结构,这种分配方法称为设备的虚拟分配。

SPOOLING系统

​ SPOOLING系统提供外围设备同时联机操作的功能。利用通道和中断技术,在主机控制之下,由通道完成输入输出工作。系统提供一个软件系统 (包括预输入程序、缓输出程序、井管理程序、预输入表、缓输出表)。它提供输入收存和输出发送的功能,使外部设备可以并行操作。这一软件系统称为SPOOLING系统。

设计思想(也就是虚拟设备的设计思想)

① 预输入

​ 在应用程序需要数据前,OS已将所需数据预先输入到辅存 输入井存放。当应用程序 (或进程) 需要数据时,可直接从辅存中读入主存。

② 缓输出

​ 在应用程序执行时,将输出数据写入辅存输出井中。当应用程序 (或进程)执行完毕 (或需要数据时) ,由操作系统将数据输出。

优点:

① 提供虚拟设备

外围设备同时联机操作

加快作业处理速度

实现SPOOLING系统的基础

大容量的辅存空间

​ 在辅存上需开辟两个较大的输入井和输出井,用以存放大量应用程序的输入信息和输出信息。

硬件基础

​ 通道装置、中断系统

数据结构

​ 预输入表、缓输出表:描述辅存输入井和输出井的状态变化。

​ 如: 输入信息从哪台设备输入,存放在辅存输入井什么位置;输出信息存放在辅存输出井什么位置,从哪台输出设备输出。

所需的软件程序

输入程序 控制信息从独占设备输入到辅存

缓输出程序 控制信息从辅存输出到独占设备

井管理程序 控制用户程序和辅存之间的信息交换

输入\输出控制

端口:设备与计算机通信的硬件连接点。

总线:一组线+一组严格定义的可以描述在线上传输信息的协议。这一组线用来连接一个或者多个设备,这种连接成为总线。

控制器:用于操作端口、总线或设备的一组电器器件。

输入\输出控制方式

循环测试I/O方式

I/O中断方式

通道方式

DMA方式

具体可见组成原理相关章节

I/O子系统

对设备的控制和操作由内核的IO子系统来实现。可以对设备进行分类,并且提供接口。

解释用户的I/O系统调用

设备驱动

中断处理

在应用层为用户提供I/O应用接口

对设备的控制和操作则由内核I/O子系统来实施。

每个通用设备类型都通过一组标准函数(及接口)来访问

具体的差别被I/O子系统中的内核模块(称为设备驱动程序)所封装,这些设备驱动程序一方面可以定制以适合各种设备,另一方面也提供了一组标准的接口。设备驱动程序层的作用是为内核I/O子系统隐藏设备控制器之间的差异。将I/O子系统与硬讲分离,简化了操作系统开发人员的任务,也有利于设备的设计与制造。

设备处理程序

​ 设备处理程序是能直接控制设备运转的程序,它根据各类设备的特点和性能来编写。每一类设备有一个相应的设备处理程序,能控制同类中多台物理设备同时工作。

控制I/O核心模块的方式

以设备处理进程的方式

ⅰ 为每一类设备设置一个设备处理进程 (对应的程序就是设备处理程序);

ⅱ 当有I/O请求来到时该进程被唤醒,进行设备驱动工作;当没有I/O请求时,该进程睡眠。

​ 由I/O控制模块的接口程序负责解释用户的I/O系统调用,将其转换成I/O控制模块认识的命令形式后,将I/O请求发给对应的设备处理进程。

将设备与文件一样对待

将设备与文件一样对待,使用文件系统的系统调用命令进行设备的读、写。

例子:

(1) 用户进程请求I/O的系统功能调用

系统功能调用的形式为:

doio(ldev,mode,amount,addr);

ldev: 逻辑设备名

mode: 操作模式

amount:传输数据的数目

addr: 传送地址

​ (2) I/O接口程序(I/O过程)

将逻辑设备转换为物理设备

​ ⅰ 获得 I/O系统调用中给出的逻辑设备名 (ldev);

ⅱ 根据逻辑设备描述器,将逻辑设备名转换为物理设备名。

合法性检查

​ ⅰ 获得 I/O系统调用中给出的操作模式mode;

ⅱ 根据DCB中命令转换表中允许的操作,检查操作的合法性。

形成I/O请求块,发消息给对应的设备处理进程

ⅰ 根据请求的参数形成I/O请求块 (IORB);

ⅱ 将I/O请求块 (IORB)挂到对应的设备请求队列。

​ (3) I/O接口程序的描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{       while  (该进程的逻辑设备描述器队列不空)
{
if (与ldev相联结的物理设备找到)
break/ *找到* /
}
if (该进程的逻辑设备描述器队列为空)
return(错误码); / * 设备逻辑名错* /
检查参数与该设备特性是否一致;
if (不一致)
return (错误码); / * 传送参数错 * /
构造iorb;
把iorb插入到该设备的请求队列中;
唤醒因等待I/O请求块而睡眠的进程;
}

(4) 设备处理进程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
process  io
{ lwhile (设备请求队列不空)
{ 取一个iorb
提取请求的详细信息;
启动I/O操作;
sleep (事件:I/O完成) /* I/O操作* /
/*I/O完成后,进入中断处理程序,并在那里唤醒设备处理进程* /
if (出错) 将错误信息写在该设备的dcb中;
传送数据到目的地;
唤醒请求此I/O操作的进程;
删除iorb
}
sleep (事件:因无I/O请求)
goto l
}

问题

第七章 习题及解答

8-1 什么是设备独立性?引入这一概念有什么好处?

答:所谓设备独立性是指,用户在编制程序时所使用的设备同实际使用的设备无关,也就是在用户程序中仅使用逻辑设备。

引入设备独立性,可使应用程序独立于物理设备。此时,用户编程只需用逻辑设备去请求使用某类设备。当系统中有多台该类设备时,系统将其中的任一台备分配给请求进程,而不必局限于某一指定设备。这样,可以显著地提高资源的利用率和可适应性。

独立性还可以使用户程序独立于设备类型。例如,在进行输出时,既可以利用显示终端进行输出,也可以利用打印机进行输出。有了这种适应性,就可以很方便地实现输出重定向,类似地可以实现输入重定向。

8-4 什么是缓冲?引入缓冲的原因是什么?

答:缓冲是两种不同速度的设备之间传输信息时平滑传输过程的常用手段。

引入缓冲技术的原因有如下几点。

(1) 缓和CPU 和I/O设备之间速度不匹配的矛盾。

(2) 减少中断次数和CPU 的中断处理时间。如果没有缓冲,慢速 I/O设备每传一个字节就要产生一个中断,CPU 必须处理该中断;如果采用了缓冲,则慢速 I/O 设备将缓冲填满时,才向CPU发出中断,减少了中断次数和CPU 的中断处理时间。

(3) 解决 DMA 或通道方式下数据传输的瓶颈问题。DMA或通道方式都用于成批数据传输,在无缓冲的情况下,慢速 I/O设备只能一个字节一个字节的传输信息,成了DMA 或通道方式数据传输的瓶颈。缓冲的设置适应了DMA 或通道方式的成批数据传输方式,解决了数据传输的瓶颈问题。

8-5 常用的缓冲技术有哪些?

答:常用的缓冲技术有双缓冲、环形缓冲和缓冲池。

引入双缓冲以提高处理机与I/O设备之间的并行操作程度,例如,输入设备备先将第一个缓冲装满数据,在输入设备向第二个缓冲装数据时,处理机就可以从第一个缓冲中取出数据进行处理。第一个缓冲的数据处理完毕,若第二个缓冲已经装满数据,则处理机又可以从第二个缓冲中取出数据进行行处理,而输入设备又向第一个缓冲装填数据。

为了在CPU与 外设对信息的操作速度相差甚远时仍能得到良好并行效果,可以采用环形缓冲技术。环形缓冲技术是在主存中分配一组大小相等的存储区作为缓存区,并将这些缓存区链接起来,每个缓存区中有一个指向下一个缓存区的指针,最后一个缓存区的指针指向第一个缓存区,这样n 个缓存区就成了一个环形缓冲外,系统中有个缓冲链首指针指向第一个缓存区。环形缓冲用于输入输出时,需要两个指针in 和out,in 指向第一个空缓存区,out 指向第一个装满数据的缓存区。输入时,把数据输入到in 所指的空缓存区中,然后 in 模取后移一位,指向下一个空缓存区。输出时, 从out所指的满缓存区中取出数据,然 out 模取后移一位,指向下一个满缓存区。

缓冲池是由若干个大小相等的缓存区组成的。缓冲池中的每一个缓存区都由系统统一管理和动态分配。若某个进程需要使用缓冲时便提出申请,由系统将缓存区分配给它,进程不再使用缓存区时,就将缓存区交还给缓冲池。这样,就可以用少量的缓存区服务更多的进程。缓冲池通常将缓存区排成3 个队列:空闲缓存区队列、输入缓存区队列和输出缓存区队列。

8-8 什么是独占设备?对独占设备如何分配?

答:独占设备是指在一段时间内只允许一个用户进程访问的设备。系统一旦把这类设备分配给某进程后,便由该进程独占直到使用完后释放。多数低速 I/O设备都属于独占设备,如打印机等。

独占设备采用独占分配方式,即将一个独占设备分配给某进程后便一直由它独占,直到该进程完成或释放该设备时,系统才能将该设备分配给其他进程。

8-9 什么是共享设备?对共享设备如何分配?

答:共享设备是指在一段时间内允许多个进程同时访问的设备,如磁盘。对共享设备可将其同时分配给多个进程,使用共享分配方式显著提高了设备的利用率,但对设备的访问需进行合理的调度。

8-10 什么是虚拟设备技术?什么是虚拟设备?如何进行行虚拟分配?

答:所谓虚拟设备技术,是在一类物理设备上模拟另一个物理设备的技术,是将独占设备转换成共享设备的技术。目前广泛流行的虚拟设备技术是SPOOLing技术,网络环境中的虚拟打印机。

虚拟设备是指通过虚拟技术将一独占设备变换成若干台逻辑设备,供若干个用户进程使用,通常把这种经过虚拟技术处理的设备称为虚拟设备。引入虚拟设备的目的是为了克服独占设备速度较慢、资源利用率较低的缺点,以提高设备的利用率。

虚拟分配是针对虚拟设备而言的。当进程申请独占设备时,由系统分配给它共享设备,如磁盘的一部分存储空间。当进程要和设备交换信息,系统就将要交换的信息放到这部分存储空间中,在合适的时候,系统再将存储空间中的信息传到独占设备。

文件管理概述

广义上的I/O操作是指不经过CPU的操作,侠义的是指对磁盘的访问

文件是在逻辑上具有完整意义的信息集合,它有一个名字以供标识,文件名是以字母开头的字母数字串。

构成文件的基本单位:信息项(单个字符或者字节)、记录

(3) 文件的其他描述

①文件是具有符号名的信息(数据)项的集合

②文件是具有符号名的记录的集合

(4) 文件分类

①按文件的性质和用途分类
系统文件(只能通过系统调用) 、程序库文件(允许用户调用,不允许修改) 、用户文件

②按文件保护级别分类
不保护文件、 执行文件、 只读文件、 读写文件

③分类按文件流向分类
输入文件、 输出文件、 输入输出文件

(5) 文件名与属性

①文件名
每个文件有一个给定的名字,这个名字是由串描述且由文件内容来表示,包括文件符号名和内部标识符。

  • 用户使用文件符号名进行文件操作

  • 系统使用文件内部标识符管理文件

②文件扩展
文件扩展表示文件的使用特征,如:.c .obj .lib 等。

③文件属性
文件的属性字,表示文件类别、保护级等信息。

文件系统

文件系统是操作系统中负责管理和存取文件信息的软件机构。

文件系统的组成

①管理文件所需的数据结构
如目录表、文件控制块、存储分配表

②管理程序

③一组操作

文件系统的功能

①从用户角度看——文件系统实现了“按名存取”的功能。

②从系统角度看——辅存空间管理、构造文件结构、提供文件共享功能、提供存取文件的方法、文件保护、提供一组文件操作命令

文件系统的特点

①使用简单
使用文件名、一组文件操作命令。

②安全可靠
提供防护措施,在文件遭受破坏时,能及时复。全量备份、增量备份、动态备份、远程备份

③既能共享,又能保密
身份验证、存取权限验证。

存储数据的文件存储器具有固定的物理特性,数据在辅存设备上的排序、分布构成了文件的物理结构

文件系统负责实现逻辑特性到物理特性的转换

文件组织的两种结构

逻辑结构

从用户角度看到的文件面貌。即用户对信息进行逻辑组织形成的文件结构。

研究文件逻辑结构的目的:

i 为用户提供一种逻辑结构清晰、使用简便的逻辑文件形式。

ii 用户按文件的逻辑结构形式去存储、检索和加工文件中的信息

物理结构

文件的物理结构是信息在物理存储器上的存储方式,是数据的物理表示和组织。

研究文件物理结构的目的

i选择工作性能良好、设备利用率高的物理文件形式。

ii 系统按照文件的物理结构形式和外部设备打交道,控制信息的传输。

逻辑记录与物理记录

①逻辑记录

文件中按信息在逻辑上的独立含义来划分的信息单位,逻辑记录是对文件进行存取操作的基本单位。

②物理记录

在存储介质上,由连续信息所组成的一个区域称为块,也叫物理记录。

③逻辑记录与物理记录的区别与联系

i 一个是逻辑的概念,一个是物理的概念。

ii 逻辑记录最终要存放到物理记录上。

文件的逻辑结构与存取方法

流式文件

流式文件是相关的有序字符的集合,是无结构的。

流式文件是按信息的个数或以特殊字符为界进行存取的。

简单来说就是没有格式的文件

UNIX系统为了方便会将流式文件按照512B的大小划分为若干个逻辑记录,将流式文件转变为记录式文件。

记录式文件

记录式文件是一种有结构的文件。这种文件在逻辑上总是被看成一组连续顺序的记录的集合。

如果文件中所有记录的长度都相同,就称这种文件为定长记录文件。其长度由记录的数量来决定。

如果文件中记录的长度不相同,就称这种文件为变长记录文件。其长度由各个记录长度相加得到。

文件存取方法

(1) 顺序存取

后一次存取总是在前一次存取的基础上进行的。顺序存取时不必给出具体的存取位置。

(2) 随机存取

用户以任意次序请求某个记录。随机存取时要指出起始存取位置(例如记录号)。

文件的物理结构

连续文件

连续文件结构是由一组分配在磁盘连续区域的物理块组成的。

如果连续文件的逻辑记录和磁盘的物理块一样大,就如下图所示:

连续文件的第一个逻辑记录所在的磁盘块号记录在文件目录项中,同时文件目录还记录了磁盘块的数量。8

连续文件的特点

①连续存取时速度较快

②文件长度一经固定便不易改变

③文件的增生和扩充不易

但是当文件不断创建或者删除的时候,将会造成存储空间的浪费(因为文件长度是固定的,多次创建就是占着茅坑不拉屎)

串联文件

串联文件结构是按顺序由串联的块组成的,即文件的信息存于若干块物理块中,每个物理块的最末一个字作为链接字,它指出后继块的物理地址。文件的最后一块的链接字为结束标记“^”,它表示文件至本块结束。

串联文件的特点

①能较好地利用辅存空间

②易于对文件进行增生和扩充

③连续存取时速度较快

串联文件的特点也决定了它适合的是顺序存取方式,不适用于随机存取方式。(就像链表一样,找中间元素得遍历链表,不方便)

索引文件

索引文件将逻辑文件顺序地划分与物理存储块长度相同的逻辑块。(不一定)

系统为每个文件建立逻辑块号与物理块号的对照表。这张表称为该文件的索引表。文件由数据文件和索引表构成。这种文件称为索引文件。

注意:物理块号可以是不连续的。但是逻辑块号一般是连续的。

①索引文件在存储区中占两个区

i 索引区:存放索引表

ii 数据区:存放数据文件

②访问索引文件的操作

i 查文件索引,由逻辑块号查得物理块号

ii 由此磁盘物理块号而获得所要求的信息

索引文件的特点

①易于文件的增删

②直接读写任意记录

有点像页表。每次对文件进行修改,索引表都可能会发生改动。

直接索引

文件目录项中有一组表项用于索引。每一个表项登记的是逻辑记录所在的磁盘块号。

一级间接索引

需要注意:间接索引表磁盘块号和磁盘块号不是一回事

文件目录项中有一组表项,其内容登记的是第一级索引表块的块号。第一级索引表块中的索引表项登记的是文件逻辑记录所在的磁盘块号。

二级间接索引

文件目录项中有一组表项,其内容登记的是第二级索引表块的块号。第二级索引表块中的索引表项登记的第一级索引表块的块号,第一级索引表项中登记的是文件逻辑记录所在的磁盘块号。

套娃下去可以是可以,但是检索的时间就变长了。

文件存储空间的管理

就是为了管理怎么分配文件存储空间的。

文件目录及其结构

文件目录是记录文件的名字、存放地址及其他有关文件的说明信息和控制信息的数据结构

文件目录项的内容

①文件名

②文件逻辑结构
说明该文件的记录是否定长、记录长度及记录个数等。

③文件物理结构:记录文件的物理结构形式
连续文件——指出文件第一块的物理地址、文件所占块数
串联文件——指出该文件第一块的物理地址
索引文件——指出索引表地址

④存取控制信息
文件主具有的存取权限、核准的其他用户及其相应的存取权限

⑤管理信息
文件建立日期、时间,上一次存取时间、要求文件保留的时间等

⑥文件类型
文件的类型,例如可分为数据文件、目录文件、块存储设备文件、字符设备文件

一级文件目录

系统将已建立的所有文件的文件名、存放地址及有关的说明信息放在一张表中,这张表称为一级文件目录。

一级文件目录的特点

  • 实现了按名存取的功能,比较简单;
  • 要求文件名和文件之间有一一对应的关系,即:不允许两个文件有相同的名字。

重名问题

所谓“重名”,是指不同用户对不同文件起了相同的名字,即两个或多个文件只有一个相同的符号名。又称为命名冲突。

为了解决命名冲突、获得更灵活的命名能力,文件系统必须采用多级目录结构

树型文件目录

在多级目录系统中(除最末一级外),任何一级目录的目录项可以描述一个目录文件,也可以描述一个非目录文件(数据文件),而数据文件一定在树叶上。这样,就构成了一个树形层次结构。

文件路径名

多级目录中,文件的路径名是由根目录到该文件的通路上所有目录文件符号名和该文件的符号名组成的字符串,相互之间用分隔符分隔。

文件共享与安全

文件共享是指某一个或某一部分文件可以让事先规定的某些用户共同使用。

所谓文件安全,就是文件的保护问题。文件的保护是指文件本身不得被未经文件主授权的任何用户存取,而对于授权用户也只能在允许的存取权限内使用文件。

②如何进文件的保护

需要对用户的权限进行验证。所谓存取权限的验证,是指用户存取文件之前,需要检查用户的存取权限是否符合规定,符合者允许使用,否则拒绝。

③验证用户存取权限的方法

i 访问控制矩阵

ii 存取控制表

iii 用户权限表

iv 口令

v 密码

用文件路径名加快文件的查找

当前目录是当前用户正在使用的文件所在的目录。当指定当前目录后,用户对文件的所有访问都是相对于“当前目录”进行的。这时,文件路径名是由“当前目录”到信息文件的通路上所有各级目录的符号名加上该信息文件的符号名组成。用“*”表示当前目录的父节点

链接技术

所谓“链接”,就是在相应目录表目之间进行链接,即一个目录中的表目直接指向另一个目录表目所在的物理位置。

注意,这种链接不是直接指向文件,而是指向相应的目录表目。这种办法也称为连访,被共享的文件称为连访文件。

相当于添加共享文件中间的链接

在当前目录下新键一个子目录用于链接其共享文件

UNIX/Linux下的链接文件有两种,硬连接(Hard Link) 和软连接。

软连接又称符号链接(Symbolic link)。符号链接文件中并不包括实际的文件数据,而只是包括了它指向文件的路径。它可以链接到任意的文件和目录,包括处于不同文件系统的文件以及目录。当用户对链接文件操作时,系统会自动的转到对源文件的操作,但是删除链接文件时,并不会删除源文件。

硬连接是指通过索引节点对文件的链接。保存在系统中的每一个文件都会有一个索引节点。每当有文件链接文件A时,文件A的索引节点的引用计数+1(因为文件自身对自己索引节点会链接,所以索引节点的初始值为1.)当文件系统进行删除文件的时候,对应的文件索引节点的引用计数-1。只要引用计数不等于0,文件就不会真正删除。

文件操作和文件备份

常用的文件操作命令

1
2
3
4
5
6
7
create://创建一个新文件
delete//从系统目录中撤消一个文件
rename://在系统目录中改变文件的名字
open://打开文件 在用户和文件(或设备)之间建立一个逻辑通路
close://关闭文件 在用户和文件(或设备)之间撤消一个逻辑通路
write://写到一个文件(或设备)上
read://从一个文件(或设备)读入数据信息

①打开文件操作

所谓打开文件就是把该文件的有关目录表目复制到主存中约定的区域,建立文件控制块,建立用户和这个文件的联系。

②关闭文件操作

所谓关闭文件就是用户宣布这个文件当前不再使用,系统将其在主存中的文件控制块删去,因而也就切断了用户同这个文件的联系。

文件备份

为了能在软、硬件失效的意外情况下恢复文件,保证文件的完整性、数据的连续可利用性,文件系统提供适当的机构,以便复制备份。

文件备份的方法

①周期性转储

按固定的时间周期把存储器中所有文件的内容转存到某种介质上,通常是磁带或磁盘。在系统失效时,使用这些转存磁盘或磁带,将所有文件重新建立并恢复到最后一次转存时的状态。(全部)

②增量性转储

这种技术转储的只是从上次转储以后已经改变过的信息;增量转储的信息量较小,故转储可在更短的时间周期内进行(部分)

问题

1.何谓数据项、记录和文件?

答:①数据项分为基本数据项和组合数据项。基本数据项描述一个对象某种属性的字符集,具有数据名、数据类型及数据值三个特性。组合数据项由若干数据项构成。

②记录是一组相关数据项的集合,用于描述一个对象某方面的属性。

③文件是具有文件名的一组相关信息的集合。

4.何谓逻辑文件?何谓物理文件?

答:逻辑文件是物理文件中存储的数据的一种视图方式,不包含具体数据,仅包含物理文件中数据的索引。物理文件又称文件存储结构,是指文件在外存上的存储组织形式。

8.试说明顺序文件的结构及其优点。

答:第一种是串结构:各记录之间的顺序与关键字无关。第二种是顺序结构:指文件中的所有记录按关键字(词)排列。可以按关键词长短排序或英文字母顺序排序。

顺序文件的最佳应用场合是对诸记录进行批量存取时,存取效率最高;只有顺序文件才能存储在磁带上并有效工作。

15.什么是索引文件?为什么要引入多级索引?

答:索引文件是指当记录为可变长度时,通常为之建立一张索引表,并为每个记录设置一个表项构成的文件。通常将索引非顺序文件简称为索引文件。索引是为了是用户的访问速度更快,多级索引结构可以有效的管理索引文件,可根据用户的访问情况多级处理。

17.对目录管理的主要要求是什么?

答:实现按名存取、提高检索目录的速度、文件共享、允许文件重名。

18.采用单级目录能否满足对目录管理的主要要求?为什么?

答:不能。单级目录在整个文件系统中只建立一张目录表,每个文件占一个目录项,其中含文件名、文件扩展名、文件长度、文件类型、文件物理地址、状态位等其它文件属性。

单级只能实现目录管理的基本功能,不能满足查找速度、允许重名和文件共享的要求。

19.目前广泛应用的目录结构有哪些?它有什么优点?

答:现代操作系统都采用多级目录结构。基本特点是查询速度快、层次结构清晰、文件管理和保护易于实现。

9-6 设文件B按串联文件构造,并由四个逻辑记录组成 (其大小与磁盘块大小相等,均为512B)。这四个逻辑记录分别存放在第100、157、66、67号磁盘块上,回答如下问题。

(1) 画出此串联文件文件的结构,

(2) 若要读文件B第1560字节处的信息,问要访问哪一个磁盘块? 为什么?

(3) 读文件B第1560字节处的信息需要进行多少次I/O操作? 为什么?

(1) 答:此串联文件结构如下图所示。

(2) 答:1560/512=3余24,因此文件第1560逻辑字节在r3逻辑块上,该逻辑块被分配在67号磁盘块上。

(3) 答:要访问67号磁盘块,需要先找到文件目录,然后依次访问100、157和66号磁盘块,最后读取67号磁盘块。因此若文件已打开 (文件目录信息已在内存中) 需要4次I/O操作,文件未打开需要5次I/O操作。

9-16什么是“重名”问题 ? 二级文件目录结构如何解决这一问题?

答:重名是指不同用户对不同文件起了相同的名字。在二级文件目录结构中,每个用户建立用户文件目录,系统建立主目录,登记所有用户目录的信息,用目录名加文件名唯一标识每个文件解决重名问题。

9-18 假设两个用户共享一个文件系统,用户甲要用到文件a、b、c、e,用户乙要用到文件a、d、e、f。已知:用户甲的文件a与用户乙的文件a实际上不是同一文件;用户甲的文件c与用户乙的文件f实际上是同一文件;甲、乙两用户的文件e是同一文件。试拟定一个文件组织方案,使得甲、乙两用户能共享该文件系统而不致造成混乱。

答:如下图所示。用户甲的主目录名为jia,有四个文件,文件名为a、b、c、e。

用户乙的主目录名为yi,有四个文件,文件名为a、d、e、f。

处理机调度

作业调度(宏观):

­决定哪些程序调入计算机系统。

进/线程调度(微观):

­决定哪个(些)进程占用CPU。

不同类型操作系统的侧重点不同。

批处理系统

2层 作业—选择作业进入主存

​ 进程—选择获得CPU的进程

分析:作业 小时—分钟为单位 发生的频率低

​ 高效调度,充分优化

进程 发生的频率高 ms为单位 快速调度

​ 例:20ms—时间片,2ms—调度执行

分时操作系统—进程调度

个人计算机操作系统—进程调度或线程调度

作业调度

一般来说,计算机系统把用户要求处理的一项工作称为一个作业

作业有四种状态:

­1 . 提交状态 用户将程序和数据提交计算中心;

­2. 后备状态 将作业录入到后援存储设备;

­3. 执行状态 作业调入计算机系统内存;

­4. 完成状态 作业计算完成的善后处理。

作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。

功能:

­**1. ** 确定数据结构,记录已进入系统的各作业的情况JCB(Job Control Block)

­2. 按一定的调度算法,从后备作业中选择一个或几个作业进入内存;

­3. 分配资源,为被选中的作业创建进程,并为其申请系统资源;

­4. 作业结束后作善后处理。(进程和作业的资源回收是同时的)

作业控制块JCB

每个作业进入系统时由系统为其建立一个作业控制块JCB(Job Control Block),它是存放作业控制和管理信息的数据结构。

调度算法性能的衡量

需要考虑系统中各种资源的负载均匀

作业的周转时间:
$$
t_i = t_ci - t_{si}\
t_i:作业周转时间,t_ci:作业完成时间,t_{si}:作业提交到系统的时间
$$
平均周转时间:
$$
t=1/n\sum_{i=1}^n t_i
$$
平均带权周转时间
$$
w=1/n\sum_{i=1}^nw_i\
w_i=t_i/t_{ri}\
t_{ri}:作业i实际运行时间
$$

作业调度算法

先来先服务算法FCFS

­先来先服务算法是按作业来到的先后次序进行调度的,换句话说,调度程序每次选择的作业是等待时间最久的,而不管作业的运行时间的长短。这种调度算法突出的优点是实现简单,效率较低,在一些实际的系统和一般应用程序中采用这种算法的较多。

短作业优先算法SJF

­短作业优先调度算法考虑作业的运行时间,每次总是选择一个运行时间最小的作业调入内存(系统)

­在一般情况下这种调度算法比先来先服务调度算法的效率要高一些。实现相对先来先服务调度算法要困难些,如果作业的到来顺序及运行时间不合适,会出现饿死现象。

响应比高者优先算法

每调度一个作业投入运行时,就计算后备作业表中的每个作业的响应比,将响应比最高的作业投入运行。
$$
响应比=响应时间/执行时间\
响应时间=作业进入系统的等待时间+执行时间
$$

理论上讲是比较好的,但是需要估计作业的等待时间和运行时间,比较复杂,开销大。

优先数调度算法

­优先数调度算法是终合考虑各方面的因素(作业等待时间、运行时间、缓急程度,系统资源使用等),给每个作业设置一个优先数,调度程序总是选择一个优先数最大(或者最小)的作业调入(系统)内存。

确定优先数的一种简单的方法是:用户为自己的作业确定一个优先级

当然,优先数是可以浮动的。

进程调度

见《进程管理》

UNIX系统进程调度

  • 采用优先数调度算法

  • 进程有一个进程优先数p_pri

  • p_pri取值范围是-127~127,其值越小,进程的优先级越高

优先数的确定
系统设置
在sleep()中设置将要进入睡眠状态进程的优先数,当该进程被唤醒后,就以系统给它设置的优先数去参与处理机的竟争。

0#进程(-100优先数);
资源请求得不到满足的进程,磁盘(-80),打印机(-20),…;
所有处于用户态运行进程同步(一般情况下为大于**0)。

­优先数的计算

1
2
3
4
5
6
 p_pri = min{127, (p_cpu/16+p_nice+PUSER)}
其中:
p_cpu: 进程占用CPU的程度
p_nice: 用户通过系统调用nice(priority)设置的
进程优先数
PUSER: 常数,其值为100

Linux系统进程调度

进程调度程序是内核的组成部分,负责选择下一个要运行的进程。

进程调度可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。

进程调度程序是如Linux这样的多任务操作系统的基础。

Linux进程调度策略

基于动态优先级和可变时间片的调度

调度方式为可抢占式调度

调度目标

  • 实现算法复杂度为O(1)级的调度

    • 进程调度算法保证在恒定的时间内完成
    • 算法执行时间与系统中处于就绪(可运行)状态的进程个数无关
  • 提高交互性能

    • 提高交互性能,保证系统能快速响应
  • 保证公平

    • 在合理设定的时间范围内,没有进程会出现饥饿状态,也不会有进程获得大量的时间片
  • 实现对称多处理器(SMP)可扩展性

I/O消耗型和处理器消耗型的进程

  • I/O消耗型进程

    • 大部分时间是使用外部设备,交互式进程具有此特征
  • 处理器消耗型进程

    • 大部分时间是使用CPU,计算进程具有此特征

交互式的程序都是I/O消耗型的。Linux为了保证交互式应用,优化了进程的响应,更倾向于优先调度I/O消耗型进程,但并未忽略处理器消耗型程序。

进程调度的特点

  • Linux系统实现了基于进程过去行为的启发式算法;
  • Linux系统选择优先级高的进程先运行,相同优先级的进程按循环方式调度;
  • 动态优先级依进程占有CPU的情况、休眠时间的长短来增、减 ;
  • 系统根据进程优先级调整分配给它的时间片;
  • 实施可抢占调度方式

动态优先级

每个进程有一个动态优先级,它是进程调度程序选择可运行进程所使用的参数,其取值范围是100(最高优先级) ~ 139(最低优先级)

动态优先级的计算

动态优先级 = max(100,min(静态优先级- bonus + 5,139))

bonus是范围 0 10的值,

​ 值小于5表示降低动态优先级以示惩罚

​ 值大于5表示增加动态优先级以示奖励

进程调度使用的是动态优先级,通过effective_prio( )函 数来计算一个进程的动态优先级。

确定I/O消耗型和处理器消耗型进程的方法

依据 —— 进程睡眠时间的长短

若进程睡眠时间长 —— I/O消耗型

若进程睡眠时间短 ——处理器消耗型

可变时间片

对交互式进程,系统提供较长的时间片

调度程序根据进程的优先级动态调整分配给它的时间片

时间片处理的时机

  • 创建新进程时的处理

    • 新创建的子进程和父进程均分父进程剩余的时间片
  • 进程用完时间片时的处理

    • 当一个进程的时间片用完时,依任务的静态优先级重新计算时间片;
    • task_timeslice()函数为给定任务返回一个新的时间片

时间片的使用

  • 一个进程拥有的时间片可分多次使用,放弃CPU时进入活动队列

  • 当一个进程的时间片耗尽时,认为是过期进程,进入过期队

时间片的计算

基本时间片

静态优先级本质上决定了进程的基本时间片

​ (140 -静态优先级) ×20 若静态优先级 < 120

​ (140 -静态优先级) ×5 若静态优先级 ≥ 120

静态优先级越高(值越小),基本时间片越长。

活动队列和过期队列

​ 每个处理器维护两个优先级数组—— 活动数组和过期数组

活动数组上的可执行队列中的进程都有剩余时间片

过期数组上的可执行队列中的进程都已耗尽时间片

当一个进程的时间片耗尽时,被移至过期队列中;

当活动数组上的可执行队列中的所有进程都已耗尽时时间片,这时,在活动数组和过期数组之间切换指针。

问题

6-3 某系统的进程状态变迁图如图6.12所示 (设该系统的进程调度方式为非剥夺方式)。

(1) 说明一个进程发生变迁3的原因是什么? 发生变迁2、变迁4的原因又是什么?

(2) 下述因果变迁是否会发生,如果有可能的话,在什么情况下发生 ?

① 2→5; ② 2→1; ③ 4→5; ④ 4→2; ⑤ 3→5

(3) 根据此进程状态变迁图叙述该系统的调度策略、调度效果。

(1) 答:

发生变迁3的原因:当运行进程在执行过程中,需要等待某事件的发生才能继续向下执行时会发生变迁3。

发生变迁2的原因:运行进程在分得的时间片100ms 或500ms内未完成,当其时间片到时将发生变迁2。

发生变迁4的原因:当等待进程等待的事件发生了,将会发生变迁4。

(2) 答:

① 2→5的因果变迁可能发生。条件是:高优先就绪队列非空。

② 2→1的因果变迁可能发生,当运行进程的时间片到时发生的变迁2,若此时高优先就绪队列为空,必然引起低优先就绪队列中的一个就绪进程被调度执行而发生变迁1。

③ 4→5的因果变迁不可能发生,因为采用的是非剥调度夺式。

④ 4→2的因果变迁不可能发生。

⑤ 3→5的因果变迁可能发生,条件是:高优先就绪队列非空。

(3) 答:

调度策略:首先调度高就绪队列中的进程 (一般是I/O 型进程) 投入运行,给高优先就绪队列中的进程分配的时间片大小为100ms。只有当高就绪队列中的所有进程全部运行完或因等待某事件发生处于阻塞状态,高就绪队列中没有进程可运行时,才调度低优先就绪队列中的进程 (一般是计算型进程) ,给低优先就绪队列中的进程分配的时间片大小为500ms。若一个运行进程时间片100ms 或500ms到时未完成就进入低优先就绪队列。若某进程在运行期间因等待某事件发生而进入阻塞队列,则当所等待事件完成后,它将进入高优先就绪队列。

调度效果:这种算法优先照顾了I/O 量大的进程 (高优先级) ,但通过给计算型进程分配更长的时间片也适当照顾了计算型进程。

6-10 Linux2.6版本为了实现O(1)级算法复杂度,采用了什么措施?

答:Linux系统进程调度用的数据结构最重要的是运行队列结构,该结构给出了处理机上可运行进程的链表。该结构中包含一个称为优先级数组的结构数组。每个数组都表示一个可运行进程集合,包括两个重要信息:① 一个优先级位图;

② 140个双向链表头,每个链表对应一个可能的进程优先级队列。

Linux系统采用优先调度策略。在Linux2.6版本的进程调度程序中,基于上述进程调度用数据结构,查找系统中优先级最高的进程这一问题转化为查找优先级位图中第一个置为1的位。找到这一位就是找到了最高优先级链表,即可确定优先级最高的、可运行的进程。由于优先级个数是定值,所以查找时间恒定。许多体系结构提供find_first_bit指令(字操作指令),找到第一个设置为1的位所花费的时间微不足道。这是保证Linux系统进程调度具有O(1)级算法复杂度的关键所在。

1. 系统有5个进程,它们的到达时间和服务时间如表4-8所示。新进程(没有运行过)与老进程(运行过的进程)的条件相同时,假定系统选新进程运行。

表4-8 进程情况

进程名 到达时间 服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2

若按先来先服务(FCFS)、时间片轮法(时间片q=1)、短进程优先(SPN)、最短剩余时间优先(SRT,时间片q=1)、响应比高者优先(HRRN)及多级反馈队列(MFQ,第一个队列的时间片为1,第i(i>1)个队列的时间片q=2(i-1))算法进行CPU调度,请给出各个进程的完成时间、周转时间、带权周转时间,及所有的进程的平均周转时间和平均带权周转时间。

答:

img

img

1. 设系统中有5个进程P1、P2、P3、P4、P5,有3种类型的资源A、B、C,其中A资源的数量是17,B资源的数量是5,C资源的数量是20,T0时刻系统状态如表4-9所示。

表4-9 T0时刻系统状态

进程 已分配资源数量 最大资源需求量 仍然需求资源数
A B C A B C A B C
P1 2 1 2 5 5 9 3 4 7
P2 4 0 2 5 3 6 1 3 4
P3 4 0 5 4 0 11 0 0 6
P4 2 0 4 4 2 5 2 2 1
P5 3 1 4 4 2 4 1 1 0
  1. 计算每个进程还可能需要的资源,并填入表的“仍然需要资源数”的栏目。

(2) T0时刻系统是否处于安全状态?为什么?

答:处于安全状态,因为序列<p4,p2,p3,p5,p1>是一个安全状态。

(3) 如果T0时刻进程P2又有新的资源请求(0,3,4),是否实施资源分配?为什么?

答:不实施资源分配,因为将所有资源都分配给p2时,p2的C是5,不能够运行,进入死锁。

(4) 如果T0时刻,若进程P4又有新的资源请求(2,0,1),是否实施资源分配?为什么?

答:实施;因为p4请求资源后,存在安全状态。

(5) 在(4)的基础上,若进程P1又有新的资源请求(0,2,0),是否实施资源分配?为什么?

答:不实施;

进程和进程管理

程序的顺序执行

一个计算的若干操作必须按照严格的先后次序顺序地执行,这类计算过程就是程序的顺序执行过程。

顺序程序的特点

  • 顺序性——处理机的操作严格按照程序所规定的顺序执行。
  • 封闭性——程序一旦开始执行,其计算结果不受外界因素的影响。
  • 可再现性——程序执行的结果与它的执行速度无关(即与时间无关),而只与初始条件有关。

并发程序

若干个程序段同时在系统中运行,这些程序段的执行在时间上是重叠的,一个程序段的执行尚未结束,另一个程序段的执行已经开始,即使这种重叠是很小的一部分,也称这几个程序段是并发执行的。

并发程序的特点

1、失去程序的封闭性和可再现性

因为一个程序的执行可能会改变另一个程序的变量

2、程序并发执行的相互制约

  • 间接的相互制约关系——资源共享
  • 直接的相互制约关系——公共变量

进程

进程与程序的区别

简单来说是进程是有生命周期的,但是程序只要输入相同,输出一定相同。

①程序是静态的概念,进程是动态的概念;

②进程是一个独立运行的活动单位;

③进程是竞争系统资源的基本单位;

④一个程序可以对应多个进程,一个进程至少包含一个程序。

进程的状态

进程的基本状态:

①运行状态(running)
该进程已获得运行所必需的资源,它的程序正在处理机上执行。

②等待状态(wait)
进程正等待着某一事件的发生而暂时停止执行。这时,即使给它CPU控制权,它也无法执行。

③就绪状态(ready)
进程已获得除CPU之外的运行所必需的资源,一旦得到CPU控制权,立即可以运行。

进程状态的变迁

新建态: 对应于进程刚刚被创建时没有被提交的状态,并等待系统完成创建进程的所有必要信息。 进程正在创建过程中,还不能运行。操作系统在创建状态要进行的工作包括分配和建立进程控制块表项、建立资源表格(如打开文件表)并分配资源、加载程序并建立地址空间表等。创建进程时分为两个阶段,第一个阶段为一个新进程创建必要的管理信息,第二个阶段让该进程进入就绪状态。由于有了新建态,操作系统往往可以根据系统的性能和主存容量的限制推迟新建态进程的提交。

终止态:进程已结束运行,回收除进程控制块之外的其他资源,并让其他进程从进程控制块中收集有关信息(如记帐和将退出代码传递给父进程)。类似的,进程的终止也可分为两个阶段,第一个阶段等待操作系统进行善后处理,第二个阶段释放主存。

注意因果变迁:

系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁,这种变迁称为因果变迁

进程描述

进程控制块

描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构,称为进程控制块PCB (process control block)。

①进程标识符——进程符号名(唯一的标识符)或内部id号(方便系统管理)

②进程当前状态——本进程目前处于何种状态(只有处在就绪态,才有可能获得处理机)

③当前队列指针next——该项登记了处于同一状态的下一个进程的PCB地址。

​ 进程一般是采用队列的形式,把具有相同状态的进程链在一起,形成队列。

④进程优先级——反映了进程要求CPU的紧迫程度。

⑤CPU现场保护区——当进程由于某种原因释放处理机时,CPU现场信息被保存在PCB的该区域中。

⑥通信信息——进程间进行通信时所记录的有关信息。

⑦家族联系——指明本进程与家族的联系

​ (一般而言,子进程继承父进程的全部资源。如果父进程被杀死,子进程会向上托孤,过继给祖进程)

⑧占有资源清单——不同的OS的PCB结构不同,占有资源清单可以显示PCB的内容

进程的组成

进程=程序 + 数据 + PCB

进程和程序最本质的区别是进程的动态特征。

进程控制

常用的进程控制原语

创建原语、撤消原语、阻塞原语、唤醒原语

进程创建

使用进程创建原语:create (name,priority) // name为被创建进程的标识符,priority为进程优先级

以父进程为模板创建子进程,复制父进程的pcb大部分数据(共用代码段,数据独有,有自己的虚拟地址空间)。

Linux中使用fork函数

1
2
#include <unistd.h>
pid_t fork(void);

返回值:

  • 子进程返回0
  • 父进程返回子进程的pid

进程撤销

使用撤销原语

撤消当前运行的进程。将该进程的PCB结构归还到PCB资源池,所占用的资源归还给父进程,从总链队列中摘除它,然后转进程调度程序。

return调用exit( ),exit 调用终止处理程序和标准I/O清理程序,然后调用 _exit( )或 Exit( )

exit( ) 直接调用 _exit( )或 _Exit( )

_exit( ) 或 _EXIT( )直接调用内核

进程等待

使用进程等待原语

(注意保护进程的CPU现场到PCB结构中)

中止调用进程的执行,并加入到等待chan(等待的资源)的等待队列中;最后使控制转向进程调度。

进程唤醒

使用进程唤醒原语

当进程等待的事件发生时,唤醒等待该事件的进程。

进程之间的约束关系的概念

进程互斥、同步的概念是并发进程下存在的概念,有了并发进程,就产生了资源的竞争与协作,从而就要通过进程的互斥、同步、通信来解决资源的竞争与协作问题。

在多道程序设计系统中,同一时刻可能有许多进程,这些进程之间存在两种基本关系:竞争关系和协作关系

==进程的互斥、同步、通信都是基于这两种基本关系而存在的。==

==为了解决进程间竞争关系(间接制约关系)而引入进程互斥;==

==为了解决进程间松散的协作关系(直接制约关系)而引入进程同步;==

==为了解决进程间紧密的协作关系而引入进程通信。==

竞争关系

资源竞争出现了两个控制问题:

一个是死锁 (deadlock )问题,一组进程如果都获得了部分资源,还想要得到其他进程所占有的资源,最终所有的进程将陷入死锁。

另一个是饥饿(starvation )问题,这是指这样一种情况:一个进程由于其他进程总是优先于它而被无限期拖延。

操作系统需要保证诸进程能互斥地访问临界资源,既要解决饥饿问题,又要解决死锁问题。
进程的互斥(mutual exclusion )是解决进程间竞争关系( 间接制约关系) 的手段。 进程互斥指若干个进程要使用同一共享资源时,任何时刻最多允许一个进程去使用,其他要使用该资源的进程必须等待,直到占有资源的进程释放该资源。

协作关系

某些进程为完成同一任务需要分工协作,由于合作的每一个进程都是独立地以不可预知的速度推进,这就需要相互协作的进程在某些协调点上协调各自的工作。当合作进程中的一个到达协调点后,在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己,直到其他合作进程发来协调信号或消息后方被唤醒并继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。

进程间的协作可以是双方不知道对方名字的间接协作,例如,通过共享访问一个缓冲区进行松散式协作;也可以是双方知道对方名字,直接通过通信机制进行紧密协作。允许进程协同工作有利于共享信息、有利于加快计算速度、有利于实现模块化程序设计。

进程的同步(Synchronization)是解决进程间协作关系( 直接制约关系) 的手段。

进程互斥

临界资源

一次仅允许一个进程使用的资源称为临界资源。

临界区

临界区是进程中对公共变量(或存储区)进行审查与修改的程序段,称为相对于该公共变量的临界区。

注意:

  • 临界区是针对某一个临界资源而言的
  • 临界区的数量是共享该临界资源的进程数量
  • 每次只能至多有一个进程处于其临界区中
  • 进程处于临界区的时间是有限的。防止其他进程被饿死
  • 为了避免多个进程试图同时进入临界区而导致的阻塞,每个进程进入临界区的时间是有限的,不是任意时候都可以进入临界区

临界区是一种轻量级的同步机制,与互斥和事件这些内核同步对象相比,临界区是用户态下的对象,即只能在同一进程中实现线程互斥。因无需在用户态和核心态之间切换,所以工作效率比较互斥来说要高很多。虽然临界区同步速度很快,但却只能用来同步本 进程内的线程,而不可用来同步多个进程中的线程。

互斥

在操作系统中,当某一进程正在访问某一存储区域时,就不允许其他进程来读出或者修改存储区的内容,否则,就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。

进程同步

并发进程在一些关键点上可能需要互相等待与互通消息,这种相互制约的等待与互通消息称为进程同步。

不难看出,==进程互斥关系是一种特殊的进程同步关系==,即逐次使用互斥共享资源,也是对进程使用资源次序上的一种协调。

进程通信

并发进程之间的交互必须满足两个基本要求:同步和通信。

进程竞争资源时要实施互斥,互斥是一种特殊的同步,实质上需要解决好进程同步问题,进程同步是一种进程通信,通过修改信号量,进程之间可建立起联系,相互协调运行和协同工作。但是信号量与PV操作只能传递信号,没有传递数据的能力。有些情况下进程之间交换的信息量虽很少,例如,仅仅交换某个状态信息,但很多情况下进程之间需要交换大批数据,例如,传送一批信息或整个文件,这可以通过一种新的通信机制来完成,进程之间互相交换信息的工作称之为进程通信IPC (InterProcess Communication)(主要是指大量数据的交换)。

进程间通信的方式很多,包括:

1 mmap(文件映射)

2 信号

3 管道

4 共享内存

5 消息队列(重要)

6 信号量集(与signal无关)

7 网络(套接字)

进程同步机制

Linux 下常见的进程同步方法有:

1、信号量

2、管程

3、 互斥量(基于共享内存的快速用户态 )

4、文件锁(通过 fcntl 设定,针对文件)

针对线程(pthread)的还有 pthread_mutex 和 pthread_cond(条件变量)。

线程的同步方法:

1、信号量

2、互斥量

3、临界区

4、事件

锁、上锁、开锁操作

  • 检测w的值(是0还是1);
  • 如果w的值为1,继续检测;
  • 如果w的值为0,将锁位置1 (表示占用资源),进入临界区执行。(此为上锁操作)
  • 临界资源使用完毕,将锁位置0。(此为开锁操作)

信号灯和P、V操作

信号灯是一个确定的二元组(s,q),s是一个具有非负初值的整型变量,q是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理。信号灯是整型变量。

变量值≥ 0 时,表示绿灯,进程执行;
变量值<0 时,表示红灯,进程停止执行。

注意:创建信号灯时,应准确说明信号灯s 的意义和初值(这个初值绝不能为负值)。

P操作

是原语。

即取信号灯值做的是 - 1操作:

  • 如果结果>=0,继续执行
  • 如果结果<0,该进程阻塞,进入等待队列

V操作

是原语。

即取信号灯值做的是+ 1操作:

  • 如果结果>0,继续执行
  • 如果结果<=0,帮助唤醒在信号灯等待队列上的一个进程

P、V操作和上锁、解锁的联系

设置信号灯mutex:

  • 1:表示没有进程进入到临界区
  • 0:表示有一个进程进入到临界区
  • -1:表示有一个进程进入到了临界区,并且有一个进程在等待

当mutex=1时,P操作相当于上锁;V操作相当于解锁。

两类同步问题的解法

合作进程的执行次序

使用流图来表示进程的执行顺序。

共享缓冲区的合作进程的同步

生产者和消费者问题

也称为有限缓冲问题。生产者的主要作用是生成一定量的数据放到缓冲区中,然后重复此过程。与此同时,消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据,消费者也不会在缓冲区中空时消耗数据。

要解决该问题,就必须让生产者在缓冲区满时休眠(要么干脆就放弃数据),等到下次消费者消耗缓冲区中的数据的时候,生产者才能被唤醒,开始往缓冲区添加数据。同样,也可以让消费者在缓冲区空时进入休眠,等到生产者往缓冲区添加数据之后,再唤醒消费者。通常采用进程间通信的方法解决该问题。如果解决方法不够完善,则容易出现死锁的情况。出现死锁时,两个线程都会陷入休眠,等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。

生产者与消费者的同步关系

  • 生产者:

    • 当有界缓冲区中无空位置时,要等待;
    • 向有界缓冲区放入物品后,要发消息。
  • 消费者:

    • 当有界缓冲区中无物品时,要等待;
    • 从有界缓冲区取出物品后,要发消息。

信号灯设置:

i 两个同步信号灯——

  • sb:表示空缓冲区的数目,初值=n
  • nsa:表示满缓冲区(即信息)的数目,初值= 0

ii 一个互斥信号灯——

  • mutex:表示有界缓冲区是否被占用,初值= 1
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
main{
int sa=0;//表示的是满缓冲区的数量
int sb=n;//表示的是空缓冲区的数量
int mutex=1;//表示的是有界缓冲区的互斥信号灯
cobegin
p1();p2();······pn();
c1();c2();······cn();
coend
}
pi()
{
while(生产未完成)
{
P(sb);
P(mutex);
生产();
V(sa);
V(mutex);
}
}
ci()
{
while(继续消费)
{
P(sa);
P(mutex);
消费();
V(sb);
V(mutex);
}
}

理发师睡觉问题

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便在理发椅上睡觉。当一个顾客到来时,他必须先叫醒理发师,如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他们就坐下来等。如果没有空椅子,他就离开。

一个理发师,一把理发椅,n把等候理发的顾客椅子。

(1)如果没有顾客,则理发师在理发椅上睡觉;
(2)当有一个顾客到达时,首先看理发师在干什么,
如果理发师在睡觉,则唤醒理发师理发;
如果理发师正在理发,则查看是否有空的顾客椅子可坐;
如果有顾客椅子可坐,则坐下等待,
如果没有,则离开。

(3)理发师为一位顾客理完发后,查看是否有人在等待,如果有则唤醒下一位顾客理发,没有则理发师去睡觉。

理发师和顾客之间的同步关系:

​ 理发师睡觉的时候,顾客进来需要唤醒理发师
​ 当有顾客的时候,理发师理发;没有就睡觉

理发师与顾客、顾客与顾客之间的互斥关系

​ 由于每次理发师只能为1个人理发,且可供等侯的椅子只有n把,即理发师和椅子是临界资源,顾客之间是互斥的关系。

信号灯设置:

​ 1、控制变量waiting用来记录等候理发的顾客数,初值均为0; 进入理发店的顾客必须先看等候的顾客数,如果少于椅子数,他留下来等,否则他就离开。

​ 2、信号量customers用来记录等候理发的顾客数,并用作阻塞理发师进程,初值为0;

​ 3、信号量barbers用来记录正在等候顾客的理发师数,并用作阻塞顾客进程,初值为0;

​ 4、信号量mutex用于互斥,初值为1.

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
main{
int customers=0;
int barbers=1;
int waiting=0;
int mutex=1;
cobegin
barber();
customers();
coend
}
barber()
{
while(true)
{
P(customers);//如果顾客人数为0,睡觉
P(mutex);
waiting-=1;
V(barbers);//该理发师不再睡觉,已经激活
V(mutex);
理发;
}
}
customers()
{
P(mutex);//该顾客被锁定
if(waiting==n)
{
店满了,走人;
V(mutex);//顾客走了,取消锁定
}
else
{
waiting+=1;//增加一名顾客
V(customers);//告诉理发师,有顾客,睡觉的让他起来
V(mutex);
P(barbers);//该理发师为这位顾客理发,其他的顾客得等到理发师理完发即V(barbers)
剪发;
}
}

进程通信

进程通信(InterprocessCommunication, IPC)是指进程之间直接以较高的效率传递较多数据的信息交互方式。

IPC机制:指消息(message)从一个进程的地址空间拷贝到另一个进程的地址空间的过程,而不使用共享存储器。该机制由操作系统提供。发送或是接收消息需要操作系统的干预

进程通信方式:消息缓冲通信/信箱通信

消息缓冲通信

在消息通信中,接收方和发送方之间有明确的协议和消息格式。

​ (大多数使用消息头:发送/接收进程的ID、被传消息的字节数……)

消息缓冲通信方式包括消息缓冲、发送原语和接收原语。

​ 发送进程先形成一个消息缓冲区(含消息头和消息内容),然后用发送原语发出。

​ 接收进程在接收前,在本进程的主存空间设置一个接收区,然后用接收原语接收。

信箱通信

在信箱通信中,需要定义信箱结构,还包括消息发送和接收功能模块,提供发送原语和接收原语。

信箱通信中,所使用的信箱可以位于用户空间中,是接收进程地址空间的一部分;也可以放置在操作系统的空间中。

缺点:要求OS为所有的进程分配主存信箱,受系统限制,可能对通信进程数限制。

线程概念及特点

线程就是进程的一个执行路径,一个进程可以有多条执行路径。这样,一个进程内部就有多个可以独立活动的单位,可以加快进程处理的速度,进一步提升并行处理能力。

  • 进程中的一条执行路径;
  • 它有自己私用的堆栈和处理机执行环境;
  • 它与父进程共享分配给父进程的主存
  • 它是单个进程所创建的许多个同时存在的线程中的一个。

进程和线程的主要区别

根本区别:进程是操作系统资源分配的基本单位,而线程是任务调度和执行的基本单位

在开销方面:每个进程都有独立的代码和数据空间(程序上下文),程序之间的切换会有较大的开销;线程可以看做轻量级的进程,同一类线程共享代码和数据空间,每个线程都有自己独立的运行栈和程序计数器(PC),线程之间切换的开销小。

所处环境:在操作系统中能同时运行多个进程(程序);而在同一个进程(程序)中有多个线程同时执行(通过CPU调度,在每个时间片中只有一个线程执行)

内存分配方面:系统在运行的时候会为每个进程分配不同的内存空间;而对线程而言,除了CPU外,系统不会为线程分配内存(线程所使用的资源来自其所属进程的资源),线程组之间只能共享资源。

包含关系:进程是线程的容器,不存在没有线程的进程。

线程的状态变迁

用户线程和内核线程

  • 用户线程:

    • 在内核的支持下,在用户层通过线程库实现
    • 创建和调度在用户空间进行,无需内核干预
    • 优点:能快速创建和管理
    • 缺点:如果内核是单线程的,一旦一个用户线程执行了等待的系统调用,则整个进程阻塞
  • 内核线程

    • 由OS管理,创建和调度在OS主存空间内完成
    • 当一个线程执行时阻塞,内核能调度另一个线程运行

操作系统的并发机制实例

创建进程

在UNIX/LINUX系统中,使用fork()函数。

函数的具体用法可见另一篇:《linux的琐碎知识点》

UNIX/Linux系统的核心为系统调用fork完成下列操作:

①为新进程分配一个新的pcb结构;

②为子进程赋一个唯一的进程标识号(PID);

③做一个父进程上下文的逻辑副本。由于进程的正文区(代码段) 可被几个进程所共享,所以核心只要增加某个正文区的引用数即可,而不是真的将该区拷贝到一个新的内存物理区。这就意味着父子进程将执行相同的代码。数据段和堆栈段属于进程的私有数据,需要拷贝到新的内存区中。

④增加与该进程相关联的文件表和索引节点表的引用数。这就意味着父进程打开的文件子进程可以继续使用。

⑤对父进程返回子进程的进程号,对子进程返回零。

启动一个新的程序的执行

父进程为了启动一个新的程序的执行,在UNIX/LINUX系统中需要用到exec()类函数

Exec()类函数很多

  • 作用是根据参数指定的文件名找到可执行文件,并用它来取代调用进程的内容,即在调用进程内部执行一个可执行文件。

exec-执行文件,启动新程序运行

①更换进程执行代码,更换正文段,数据段

②调用格式:exec (文件名,参数表,环境变量表)

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
main(){
if(fork()==0){
printf(“a”);
execlp(“file1”,0);
printf(“b”);
}
printf(“c”);
}
file1:
main()
{
printf(“d”);
}
运行结果:
acd、cad、adc(无论如何字母b不会被打印)

创建线程

LINUX下的多线程程序,需要使用pthread.h,连接时需要使用库libpthread.a。

Clone( )是LINUX特有的系统调用,用来实现pthread。与fork( )类似。

1
2
3
4
5
6
7
8
9
10
功能:创建一个新的线程
原型
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*star
t_routine)(void*), void *arg);
参数
thread:返回线程ID
attr:设置线程的属性,attr为NULL表⽰示使⽤用默认属性
start_routine:是个函数地址,线程启动后要执⾏的函数
arg:传给线程启动函数的参数
返回值:成功返回0;失败返回错误码

终止线程

return返回
pthread_exit(void *val)

1
2
3
4
5
6
功能:线程终止 原型
void pthread_exit(void *value_ptr);
参数
value_ptr:value_ptr
返回值:无返回值,跟进程一样,线程结束的时候无法返回到它的调用者(自身)

pthread_canel()取消线程,返回-1

1
2
3
4
5
6
功能:杀死一个执行中的线程
原型
int pthread_cancel(pthread_t thread);
参数
thread:线程ID
返回值:成功返回0;失败返回错误码

等待进程、线程的终止

等待进程终止

为什么要线程等待呢?

1、就像子进程死亡,需要父进程等待并回收一样,新线程死亡,其空间没有被释放,需要主线程等待回收

2、如果再创建新的线程不会复用刚才退出线程的地址空间

(1) 等待进程终止

wait();waitpid();

进程一旦调用了wait,就立即阻塞自己,由wait自动分析是否当前进程的某个子进程已经退出,如果让它找到了这样一个已经变成僵尸的子进程,wait
就会收集这个子进程的信息, 并把它彻底销毁后返回;如果没有找到这样一个子进程,wait就会一直阻塞在这里,直到有一个出现为止。

如果该进程没有子进程,则立即出错返回,返回值为-1(注意,是wait()函数立即返回,而不是说该父进程也跟着结束了,父进程里该语句后的内容还是要照样接着执行的)

定义函数 pid_t wait (int * status);

  • wait()函数用于使父进程(也就是调用wait()的进程)阻塞,直到一个子进程结束或者该进程接收到了一个指定的信号为止。如果该父进程没有子进程或者它的子进程已经结束,则wait()函数就会立即返回。参数status所指向的变量存放子进程的退出码,即从子进程的main函数返回的值或子进程中exit()函数的参数。如果status不是一个空指针,状态信息将被写入它指向的变量。

定义函数 pid_t waitpid(pid_t pid,int * status,int options);

  • waitpid()的作用和wait()一样,但它并不一定要等待第一个终止的子进程(它可以指定需要等待终止的子进程),它还有若干选项,如可提供一个非阻塞版本的 wait()功能,也能支持作业控制。实际上,wait()函数只是 waitpid()函数的一个特例,在Linux 内部实现 wait()函数时直接调用的就是waitpid()函数。

进程调度

调度:在众多处于就绪状态的进程中,按一定的原则选择一个进程。

分派:当处理机空闲时,移出就绪队列中第一个进程,并赋予它使用处理机的权利。

调度程序负责将一个进程插入到就绪队列并按一定的原则保持队列结构

分配程序是将进程从就绪从就绪队列中移出并建立该进程执行的机器状态

进程调度的功能

1、记录进程的有关情况

2、决定调度策略:

①优先调度
就绪队列按进程优先级高低排序

②先来先服务
就绪队列按进程来到的先后次序排序

3、 实施处理机的分配和回收

进程调度的方式

  • 非剥夺方式

    当“重要而紧迫”的进程来到时,让正在执行的进程继续执行,直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时,才把处理机分配给“重要而紧迫”的进程。

  • 剥夺方式

当“重要而紧迫”的进程来到时,便暂停正在执行的进程,立即把处理机分配给优先级更高的进程。

进程调度算法

进程优先数调度算法

预先确定各进程的优先数,系统把处理机的使用权赋予就绪队列中具备最高优先权(优先数和一定的优先级相对应)的就绪进程。

优先数的分类及确定

i 静态优先数

  • 在进程被创建时确定,且一经确定后在整个进程运行期间不再改变。

ii 静态优先数的确定

  • 优先数根据进程所需使用的资源来计算
  • 优先数基于程序运行时间的估计

iii 动态优先数

  • 进程优先数在进程运行期间可以改变。

iv 动态优先数的确定

  • 进程使用CPU超过一定数值时,降低优先数
  • 进程I/O操作后,增加优先数
  • 进程等待时间超过一定数值时,提高优先数

循环轮转调度算法

当CPU空闲时,选取就绪队列首元素,赋予一个时间片,当时间片用完时,该进程转为就绪态并进入就绪队列末端。相当公平。

队列排序的原则是先来先服务。

循环轮转调度算法的特征:就绪队列中的所有进程以等速度向前进展
$$
q = t/n
$$
t 为用户所能接受的响应时间,n为进入系统的进程数目。

注意:

​ q值如果取值很大的话,会导致所有进程都可以在分给它的时间片内完成,轮转调度就退化成了FIFO算法。

​ q值如果取值很小的话,进程切换的时间就变得不可忽略,系统的开销又很大。

  • 可变时间片轮转调度

每轮开始时,系统根据就绪队列中的进程数量计算一次q值,然后进行轮转。

  • 多重时间片循环调度

调度用的进程状态变迁图

①进程状态

  • 运行状态

  • 低优先就绪状态

  • 高优先就绪状态

  • 因I/O而等待状态

②队列结构

  • 低优先就绪队列
  • 高优先就绪队列
  • 因I/O而等待队列

优先调度与时间片调度相结合的调度算法

i 当CPU空闲时,若高优先就绪队列非空,则从高优先就绪队列中选择一个进程运行,分配时间片为100ms。

ii 当CPU空闲时,若高优先就绪队列为空,则从低优先就绪队列中选择一个进程运行,分配时间片为500ms。

调度效果

优先照顾I∕O量大的进程;适当照顾计算量大的进程。

四种进程或线程同步互斥的控制方法

原文链接

1、临界区:通过对多线程的串行化来访问公共资源或一段代码,速度快,适合控制数据访问。
2、互斥量:为协调共同对一个共享资源的单独访问而设计的。
3、信号量:为控制一个具有有限数量用户资源而设计。
4、事 件:用来通知线程有一些事件已发生,从而启动后继任务的开始。

临界区(Critical Section)

保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区,那么 在有一个线程进入后其他所有试图访问此临界区的线程将被挂起,并一直持续到进入临界区的线程离开。临界区在被释放后,其他线程可以继续抢占,并以此达到用原子方式操 作共享资源的目的。
临界区包含两个操作原语:

1
2
3
EnterCriticalSection() 进入临界区 
LeaveCriticalSection() 离开临界区
EnterCriticalSection() 语句执行后代码将进入临界区以后无论发生什么,必须确保与之匹配的 LeaveCriticalSection()都能够被执行到。否则临界区保护的共享资源将永远不会被释放。虽然临界区同步速度很快,但却只能用来同步本 进程内的线程,而不可用来同步多个进程中的线程。

MFC提供了很多功能完备的类,我用MFC实现了临界区。MFC为临界区提供有一个 CCriticalSection类,使用该类进行线程同步处理是 非常简单的。只需在线程函数中用CCriticalSection类成员函数Lock()和UnLock()标定出被保护代码片段即可。Lock()后代 码用到的资源自动被视为临界区内的资源被保护。UnLock后别的线程才能访问这些资源。

MFC提供了很多功能完备的类,我用MFC实现了临界区。MFC为临界区提供有一个 CCriticalSection类,使用该类进行线程同步处理是 非常简单的。只需在线程函数中用CCriticalSection类成员函数Lock()和UnLock()标定出被保护代码片段即可。Lock()后代 码用到的资源自动被视为临界区内的资源被保护。UnLock后别的线程才能访问这些资源。

互斥量(Mutex)

互斥量跟临界区很相似,只有拥有互斥对象的线程才具有访问资源的权限,由于互斥对象只有一个,因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出,以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享,而且可以在不同应用程序的线程之间实现对资源的安全共享。

互斥量包含的几个操作原语:

1
2
3
4
CreateMutex() 创建一个互斥量 
OpenMutex() 打开一个互斥量
ReleaseMutex() 释放互斥量
WaitForMultipleObjects() 等待互斥量对象

信号量(Semaphores)

信号量对象对线程的同步方式与前面几种方法不同,信号允许多个线程同时使用共享资源 ,这与操作系统中的PV操作相同。它指出了同时访问共享 资源的线程 最大数目。它允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore()创建信号量 时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数,每增加一个线程对共享资源的访问,当前可用资源计数 就会减1,只要当前可用资源计数是大于0的,就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目, 不能在允许其他线程的进入,此时的信号量信号将无法发出。线程在处理完共享资源后,应在离开的同时通过ReleaseSemaphore()函数将当前可 用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。
PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数,S大于等于零时代表可供并发进程使用的资源实体数,但S小于零时则表示正在等待使用共享资源的进程数。
P操作 申请资源:
  (1)S减1;
  (2)若S减1后仍大于等于零,则进程继续执行;
  (3)若S减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转入进程调度。
V操作 释放资源:
  (1)S加1;
  (2)若相加结果大于零,则进程继续执行;
  (3)若相加结果小于等于零,则从该信号的等待队列中唤醒一个等待进程,然后再返回原进程继续执行或转入进程调度。

1
2
3
4
CreateSemaphore() 创建一个信号量 
  OpenSemaphore() 打开一个信号量
  ReleaseSemaphore() 释放信号量
  WaitForSingleObject() 等待信号量

  信号量包含的几个操作原语:

事件(Event)

事件对象也可以通过通知操作的方式来保持线程的同步。并且可以实现不同进程中的线程同步操作。
信号量包含的几个操作原语:

1
2
3
4
5
6
7
8
9
10
11
12
CreateEvent() 创建一个事件 
  OpenEvent() 打开一个事件
  SetEvent() 回置事件
  WaitForSingleObject() 等待一个事件
  WaitForMultipleObjects()         等待多个事件
    WaitForMultipleObjects 函数原型:
     WaitForMultipleObjects(
     IN DWORD nCount, // 等待句柄数
     IN CONST HANDLE *lpHandles, //指向句柄数组
     IN BOOL bWaitAll, //是否完全等待标志
     IN DWORD dwMilliseconds //等待时间
     )

参 数nCount指定了要等待的内核对象的数目,存放这些内核对象的数组由lpHandles来指向。fWaitAll对指定的这nCount个内核对象的两种等待方式进行了指定,为TRUE时当所有对象都被通知时函数才会返回,为FALSE则只要其中任何一个得到通知就可以返回。 dwMilliseconds在这里的作用与在WaitForSingleObject()中的作用是完全一致的。如果等待超时,函数将返回 WAIT_TIMEOUT。

总结

1. 互斥量与临界区的作用非常相似,但互斥量是可以命名的,也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多,所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量 。因为互斥量是跨进程的互斥量一旦被创建,就可以通过名字打开它。
2. 互斥量(Mutex),信号灯(Semaphore),事件(Event)都可以被跨越进程使用来进行同步数据操作,而其他的对象与数据同步操作无关,但对于进程和线程来讲,如果进程和线程在运行状态则为无信号状态,在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和 线程退出。
3. 通过互斥量可以指定资源被独占的方式使用,但如果有下面一种情况通过互斥量就无法处理,比如现在一位用户购买了一份三个并发访问许可的数据库系统,可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作,这时候如果利用互斥量就没有办法完成这个要求,信号灯对象可以说是一种资源计数器。

问题

1.操作系统中为什么要引入进程的概念?为了实现并发进程中的合作和协调,以及保证系统的安全,操作系统在进程管理方面要做哪些工作?

答: 为了从变化角度动态地分析研究可以并发执行的程序,真实的反应系统的独立性、并发性、动态性和相互制约,操作系统中不得不引入进程的概念。

为了防止操作系统及其关键的数据结构如:PCB等,受到用户程序破坏,将处理机分为核心态和用户态。对进程进行创建、撤销以及在某些进程状态之间的转换控制。

\2. 试描述当前正在运行的进程状态改变时,操作系统进行进程切换的步骤。

答:分为两种情况:

img(1):运行状态 就绪 状态:根据进程的自身的情况插入到就绪队列的适当位置,系统收回处理及转入进程调度程序重新进行调度。

(2):运行状态→阻塞状态:系统会调用进程调度程序重新选择一个进程投入运行。

3.现代操作系统一般都提供多任务的环境,是回答以下问题。

为支持多进程的并发执行,系统必须建立哪些关于进程的数据结构?

答:系统必须建立PCB。

为支持进程的状态变迁,系统至少应该供哪些进程控制原语?

答:阻塞、唤醒、挂起和激活原语。

当进程的状态变迁时,相应的数据结构发生变化吗?

答:会根据状态的变迁发生相应的变化。例如:将进程PCB中进程的状态从阻塞状态改为就绪状态,并将进程从阻塞队列摘下,投入到就绪队列中。

4.什么是进程控制块?从进程管理、中断处理、进程通信、文件管理、设备管理及存储管理的角度设计进程控制块应该包含的内容。

答:PCB:描述进程本身的特征、状态、调度信息以及对资源占有情况等的数据结构,是进程存在的唯一标识。

进程控制块所包含的内容:

①进程信息描述;②CPU信息状态;③进程调度信息;④进程控制和资源占用信息。

5.假设系统就绪队列中有10个进程,这10个进程轮换执行,每隔300ms轮换一次,CPU在进程切换时所花费的时间是10ms,试问系统化在进程切换上的开销占系统整个时间的比例是多少?

解:P=(10*10)/[(300+10)*10]=3.2%

6.试述线程的特点及其与进程之间的关系。

答:线程的特点:是被独立分派和调度的基本单位。线程与进程的关系:线程是进程的一部分,是进程内的一个实体;一个进程可以有多个线程,但至少必须有一个线程。

7.根据图2-18,回答以下问题。

进程发生状态变迁1、3、4、6、7的原因。

答:变迁1原因:创建进程后,将其按高优先级插入就绪队列;

变迁3原因:进程请求I/O或等待某事件而阻塞;

变迁4原因:时间片用完;

变迁6原因:进程I/O完成或时间完成;

变迁7原因:进程完成而退出。

系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁,这种变迁称为因果变迁。下述变迁是否为因果变迁:3→2,4→5,7→2,3→6,是说明原因。

答:

3→2是因果变迁,当一个进程从运行态变为阻塞态时,此时CPU空闲,系统首先到高优先级队列中选择一个进程。

4→5是因果变迁,当一个进程运行完毕时,此时CPU空闲,系统首先到高优先级队列中选择进程,但如果高优先级队列为空,则从低优先队列中选择一个进程。

7→2 是因果变迁,当一个进程运行完毕时,CPU空闲,系统首先到高优先级队列中选择一个进程。

3→6不是因果变迁。一个进程阻塞时由于自身的原因而发生的,和另一个进程等待的时间到达没有因果关系。

根据此进程状态转换图,说明该系统CPU调度的策略和效果。

当进程调度时,首先从高优先级就绪队列选择一个进程,赋予它的时间片为100ms。如果高优先级就绪队列为空,则从低优先级就绪队列选择进程,并且赋予该进程的时间片为500ms。

这种策略一方面照顾了短进程,一个进程如果在100ms运行完毕它将退出系统,更主要的是照顾了I/O量大的进程,进程因I/O进入阻塞队列,当I/O完成后它就进入了高优先级就绪队列,在高优先级就绪队列等待的进程总是优于低优先级就绪队列的进程。而对于计算量较大的进程,它的计算如果在100ms的时间内不能完成,它将进入低优先级就绪队列,在这个队列的进程被选中的机会要少,只有当高优先级就绪队列为空,才从低优先级就绪队列选择进程,但对于计算量大的进程,系统给予的适当照顾时间片增大为500ms。

8.回答以下问题。

若系统中没有运行进程,是否一定没有就绪进程?为什么?

答:是,因为一旦系统中没有运行程序,就会马上从就绪队列中调度就绪进程,只有就绪进程队列为空时,系统中才没有进程。

若系统中既没有运行进程,也没有就绪进程,系统中是否就没有阻塞进程?解释。

答:不是,不一定,当运行的程序都因为请求I/O或等待事件时而进入阻塞,系统中就没有就绪进程。

如果系统采用优先级调度策略,运行的进程是否一定是系统中优先级最高的进程?为什么?

答:不一定,若优先级高的进程进入阻塞状态时,而且优先级高的就绪队列里没有等待的进程,这时就会调度优先级低的就绪队列的进程。

第四章 习题及解答

4-3 什么是进程?进程与程序的主要区别是什么?

答:进程是一个具有一定独立功能的程序关于某个数据集合的一次活动。进程与程序的主要区别是:

(1) 程序是指令的有序集合,是一个静态概念。进程是程序在处理机的一次执行过程,是一个动态概念。进程是有生命期的,因创建而产生,因调度而执行,因得到资源而暂停,因撤消而消亡;

(2) 进程是一个独立的运行单元,是系统进行资源分配和调度的独立单元,而程序则不是。

(3) 进程与程序之间无一一对应关系。一个程序可以对应多个进程,一个进程至少包含一个程序。

4-9 某系统进程调度状态变迁图如图4.31所示,请说明:

(1) 什么原因会导致发生变迁2、变迁3、变迁4 ?

答:发生变迁2的原因:时间片到

发生变迁3的原因:请求I/O或其他系统调用

发生变迁4的原因:I/O完成或其他系统调用完成

(2) 在什么情况下,一个进程的变迁3 能立即引起另一个进程发生变迁1 ?

答:一个进程的变迁3 能立即引起另一个进程发生变迁的条件是,就绪队列非空。

(3) 下列因果变迁是否可能发生?若可能,需要什么条件?

a. 2→1; b. 3→2; c. 4→1

答:a. 2→1 不需要条件,一定会发生。

b. 3→2 不可能发生。

c. 4→1 可能发生,条件:就绪队列为空,或在可剥夺调度方式下,转变为就绪状态的进程优先级最高。

4-10某系统进程状态除了3个最基本状态外,又增加了创建状态、完成状态、因等消息而转变为等待状态3种新的状态,试画出增加新状态后的进程状态变迁图,并说明发生每一个变迁的原因。

答:进程状态变迁图:

进程状态变迁原因:

运行—>等待:请求I/O; 等待—>就绪:请求完成;运行—>就绪:时间片到; 就绪—>运行:CPU空闲,进程调度程序工作;

创建—>就绪:进程创建; 运行—>等消息:等待消息;等消息—>就绪:收到消息;运行—>完成:任务完成

4-12 n个并发进程共用一个公共变量Q,写出用信号灯实现n个进程互斥时的程序描述,给出信号灯值的取值范围, 并说明每个取值的物理意义。

1
2
3
4
5
6
7
8
9
10
11
12
13
main ( ){
int mutex=1; //公共变量Q的互斥信号灯
cobegin
P1; P2; … Pn;
coend
}
Pi(){

P(mutex);
使用Q;
V(mutex);

}

(2) 信号灯值的取值范围:[- (n–1),1]

(3) mutex每个取值的物理意义:

mutex = 1 说明没有进程进入临界段执行;

mutex = 0 说明有一个进程进入临界段执行;

mutex = -1 说明有一个进程进入临界段执行,另有一个进程正在等待进入;

mutex = - (n–1) 说明有一个进程进入临界段执行,另有(n–1)个进程正在等待进入。

4-13 图4.32(a)、(b) 分别给出了两个进程流图。试用信号灯的p、v操作分别实现图4.32(a)、(b)所示的两组进程之间的同步,并写出程序描述。

4-15 如图4.34所示,get、copy和put三个进程共用两个缓冲区s和t (其大小每次存放一个记录) ,get 进程负责不断地把输入记录输入缓冲区s 中,copy 进程负责从缓冲区s 中取出记录复制到缓冲区t 中,而put 进程负责从缓冲区t 中取出记录打印。试用PV 操作实现这三个进程之间的同步,并写出程序描述。

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
main(){
int s1=1,s2=0; // s1 表示缓冲区S 是否为空,s2 表示是否已满//
int s3=1, s4=0; // s3 表示缓冲区T 是否为空,s4 表示是否已满//
cobegin
get;
copy;
put;
coend
}

get(){
while(1){
P(s1);
input data to buffer S;
V(s2);
}
}

copy (){
while(1){
P(s2);
copy data from buffer S;
V(s1);
P(s3);
input copy-data to buffer T;
V(s4);
}
}

put(){
while(1){
P(s4);
output data to buffer S;
V(s3);
}
}

4-16 什么是进程的互斥与同步?同步和互斥这两个概念有什么联系和区别?

答:在操作系统中,当某一进程正在访问某一存储区域时,就不允许其他进程读出或者修改该存储区的内容,否则,就会发生后果无法估计的错误。进程之间的这种相互制约关系称为互斥。

所谓同步,就是并发进程在一些关键点上可能需要互相等待与互通消息,这种相互制约的等待与互通信息称为进程同步。

同步和互斥这两个概念都属于同步范畴,描述并发进程相互之间的制约关系。同步是指并发进程按照他们之间的约束关系,在执行的先后次序上必须满足这种约束关系。而互斥是同步的一种特例,是指并发进程按照他们之间的约束关系,在某一点上一个时刻只允许一个进程执行,一个进程做完了,另一个进程才能执行,而不管谁先做这个操作。

4-22 什么是线程?线程和进程有什么区别?

答:线程也称为轻量级进程,它是比进程更小的活动单位,它是进程中的一个执行路径,一个进程可能有多个执行路径,即线程。

线程和进程的主要区别如下。

(1) 线程是进程的一个组成部分,一个进程可以有多个线程,而且至少有一个可执行的线程。

(2) 进程是资源分配的基本单位,它拥有自己的地址空间和各种资源;线程是处理机调度的基本单位,它只能和其他线程共享进程的资源,而本身并没有任何资源。

(3) 进程的多个线程都在进程的地址空间内活动。这样,在以线程为单位进行处理机调度和切换时,切换时间较短;而以进程为单位进行处理机调度和切换时,由于涉及到资源转移及现场保护等问题,将导致切换时间变长和资源利用率下降。

(4) 线程和进程一样,都有自己的状态和相应的同步机制,但是,由于线程没有自己单独的程序和数据空间,因而不能像进程那样将程序和数据交换到外存去。

(5) 进程的调度和控制大多由操作系统的内核完成,而线程的控制既可以由操作系统内核完成,也可以由用户控制完成。

4-27 试画出Linux系统的进程状态变迁,并说明这些变迁可能的原因。

答:画出Linux系统的进程状态变迁如图所示:

(1) 进程创建

当系统或用户需要创建一个新进程时,调用fork()系统调用,被创建的新进程被置为就绪状态TASK_RUNNING。

(2) 进程调度

当调度时机来到时,进程调度程序从进程运行队列中选择优先级最高的进程,将其投入运行,设置状态为运行状态。

(3) 被抢占

正在CPU上运行的进程,当其优先级低于处于就绪状态的某一个进程的优先级时,它被抢占而被迫让出CPU的控制权,此时,该进程的状态转为就绪状态。

(4) 进程等待

若正在运行的进程因等待某一事件而暂时不能运行下去时,进入相应的等待队列,设置为等待状态。

(5) 进程唤醒

当某个进程等待的原因撤销时,该进程被唤醒,将其从等待队列中移出,进入就绪队列。

(6) 进程终止

当正在运行的进程完成其任务时,通过exit()系统调用终止自己而进入终止状态。

4-29某公园有一个长凳,其上最多可以坐5个人。公园里的游客遵循以下规则使用长凳:

(1) 如果长凳还有空间可以坐,就坐到长凳上休息,直到休息结束,离开长凳。

(2) 如果长凳上没有空间,就转身离开。

试用信号灯的P、V操作描述这一场景。

答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
main(){
int count=5; // 长凳上可坐的人数
int mutex=0; // 访问count的互斥信号灯
cobegin
guesti; // i =1,2,3,4……
coend
}
guesti {
P(mutex);
if (count == 0) {
V(mutex);
return;
}
count--;
V(mutex);
休息;
P(mutex);
Count++;
V(mutex);
}

4-31 6个进程合作完成一项计算任务的并发描述如图4-38所示,程序中,s1、s2、s3、s4、s5、s6分别是同步信号灯,x、y、z是共享数据变量。试给出变量z的最终结果,并画出6个进程合作的进程流图。

答:

img

Z=12

4-32现有3个并发进程P1、P2和P3,如图4.39所示。3个并发进程共享两个单缓冲区B1和B2。进程P1负责不断从输入设备读数据,若读入的数据为正数,则直接送入B2,否则应先将数据送入B1,经P2取出加工后再送入B2,P3从B2中取信息输出。请使用信号灯和P、V操作描述进程P1、P2、P3实现同步的算法。

4-34某商场有一个地下停车场,有N个停车位,车辆只能通过一个指定的通道进出停车场,通道处只能容一辆车通过,请设计信号灯和P、V操作给出进、出车辆两种进程的程序描述。

答:

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
main()
{
int count1=count2=0;/*计数器*/
int mutex1=mutex2=1;/*两个计数器的互斥访问信号灯*/
int mutex=1; /*通道互斥访问信号灯*/
cobegin
in();
out();
coend
}
in()
{
P(empty);
P(mutex1);
Count1++;
if count1==0 P(mutex);
V(mutex1);
开车进地下停车场;
P(mutex1);
count1--;
if count1==0 V(mutex);
V(mutex1);
}
out()
{
P(mutex2);
Count2++;
if count2==0 P(mutex);
V(mutex2);
开车出地下停车场;
P(mutex2);
Count2--;
if count2==0 V(mutex);
V(mutex2);
V(empty);
}

操作系统和其结构的关系

首先明确操作系统的作用:
1> 方便用户
2> 提高资源使用率

操作系统与计算机各层次的关系

操作系统管理系统中的各种资源,控制用户和应用程序的工作流程。

(1) OS对各层的管理和控制包括下以方面:

  • 控制CPU的工作

  • 访问存储器

  • 设备驱动、中断处理

  • 控制、管理

  • 提供方便的用户界面

  • 提供优质的服务

(2) 各层对OS的制约和影响

下层硬件环境的制约:

  • 提供OS运行环境
  • 限制了OS的功能实现

存储程序式计算机的结构和特点

主要说的就是冯式结构计算机。

集中顺序过程控制的特点

①过程性:模拟人们手工操作

②集中控制:由CPU集中管理

③顺序性:程序计数器

早期的计算机是单用户OS,是顺序计算模型。他的问题就是CPU的利用率不高。

操作系统形成和发展过程

操作系统发展的初期阶段

手工操作阶段

  • 独占性
  • 串行性

批处理阶段

出现监管程序

联机批处理

解决了人机矛盾。

①特点:监督程序、作业自动过渡

②问题:CPU高速与I/O慢速的矛盾

③解决办法:由卫星机负责I/O

监管程序是为了审查作业对系统资源的要求,满足就把作业调入主存中。

注意:联机的意思是CPU对I/O的控制方式,如果CPU是直接控制I/O的操作,就是联机操作方式

脱机批处理

为了克服CPU高速和/O低速之间的矛盾。

①特点:主机与卫星机并行操作

②问题:调度不灵活;保护问题

③解决办法:硬件技术的发展——通道技术、中断技术

主机负责计算、卫星机负责I/O工作。作业通过卫星机输入到磁带上,然后移到主机上。

执行系统

提供了系统保护,避免了磁盘的拆卸。

(1) 什么是执行系统

借助于通道与中断技术,由主机控制I/O工作。原有的监督程序不仅要负责调度作业自动地运行,而且还要提供I/O控制功能。它常驻主存,称为执行系统。

(2) 特点

主机、外设并行操作;增强了保护能力

(3) 基本功能

I/O控制功能、调度

(4) 问题主机与外设的并行是有限度的,还依赖于程序运行的特征。

操作系统的形成

多道程序设计技术

其自动处理过程是:首先,由监督程序将磁带上的第一个作业装入内存,并把运行控制权交给该作业。当该作业处理完成时,又把控制权交还给监督程序,再由监督程序把磁带(盘)上的第二个作业调入内存。计算机系统就这样自动地一个作业一个作业地进行处理(顺序性),直至磁带(盘)上的所有作业全部完成(自动性)。内存中仅有一道程序运行,即监督程序每次从磁带上只调入一道程序进入内存运行,当该程序完成或发生异常情况时,才换入其后继程序进入内存运行(单道性),这样便形成了早期的批处理系统;

从上述分析可知,在输入操作系统结束之前,处理机处于空闲状态,原因是I/O处理与本道程序相关。

① 什么是多道程序程序设计技术

多道程序设计技术是在计算机主存中同时存放几道相互独立的程序这些程序在管理程序控制之下,相互穿插地运行。当某道程序因某种原因不能继续运行下去时(如等待外部设备传输数据),管理程序便将另一道程序投入运行。

② 多道运行的特征

  • 多道
  • 宏观上并行
  • 微观上串行(由下面的运行过程可知,本质上还是串行运行的,只不过提高了CPU的利用率,导致宏观上看前来是并行的)

1、运行过程

​ 在该系统中,用户所提交的作业都先存放在外存上并排成一个队列,称为“后备队列”(首先将作业放置在磁盘中,然后再由磁盘调入道内存中);然后,由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存,使它们共享 CPU和系统中的各种资源。

2、优缺点

​ 提高资源利用率:共享资源的充分利用;

​ 提高系统吞吐量:系统在单位时间内完成的总工作量;

​ 平均周转时间长:作业从进入系统开始直至作业完成并推出系统所经历的时间;

​ 无交互能力:用户无法与自己的作业进行交互;

3、多道批处理系统应该解决的问题

​ 处理机的管理;

​ 内存的管理;

​ I/O设备的管理;

​ 文件的管理;

​ 作业的管理;

分时技术

① 什么是分时技术

22所谓分时技术,是把处理机时间划分成很短的时间片(如几百毫秒)轮流分配给各个应用程序使用,如果某个程序在分配的时间片用完之前计算还未完成,该程序就暂时中断,等待下一轮继续计算。

注意:CPU是一个独占资源

② 分时处理

一台计算机与许多终端设备连接,终端用户以联机方式使用计算机。

实时技术

①什么是实时

计算机对于外来信息能够在被控对象允许的截止期限(deadline)内作出反应。

②实时处理

实时处理以快速反应为特征,对实时信号能在截止期限之内处理并作出反应。
实时处理具有实时性和可预测性。

计算机体系结构与操作系统的关系

(1) 单CPU计算机配置的操作系统

批量操作系统 分时操作系统

实时操作系统 个人计算机操作系统

(2) 具有并行结构的计算机系统配置的操作系统

网络操作系统(计算机网络,松耦合)
多处理机操作系统(多处理机系统,紧耦合)
集群操作系统(分布存储的多计算机系统)
并行分布式系统(分布存储的多计算机系统)
分布式系统(具有单一用户界面,支持分布式数据处理)
分布式实时系统(支持分布式实时数据处理)

操作系统的定义

资源共享与资源竞争

  • 资源共享:多个计算任务对计算机系统资源的共同享用
  • 资源竞争:多个计算任务对计算机系统资源的争夺

操作系统的定义和特征

(1) 操作系统的定义

操作系统是一个大型的程序系统,它负责计算机系统软、硬件资源的分配;控制和协调并发活动;提供用户接口,使用户获得良好的工作环境。

(2) 操作系统的特征

并发
能处理多个同时性活动的能力

共享
多个计算任务对系统资源的共同享用

不确定性
操作系统能处理大量的、随机的事件序列,使各用户的计算任务正确地完成。

操作系统的资源管理功能

操作系统的主要功能:

  • 对系统资源实施管理和调度
  • 控制和协调并发活动
  • 对外提供用户界面

计算机系统中最重要的资源就是CPU内存也是计算机系统的重要资源。

处理机管理

(1) 提出进程调度策略

确定将CPU先分给哪个用户程序,它占用多长时间,下一个又该轮到哪个程序运行等问题。

(2) 给出进程调度算法

确定进程调度下一个进程的顺序

(3) 进行处理机的分派

在调度时机到来时,进行处理机分派。

存储器管理

(1) 存储分配和存储无关性

确定各应用程序在主存中的位置及所占区域的大小;应用程序无需关心存储细节,由存储管理模块提供地址重定位能力。

(2) 存储保护

系统提供基址、界限寄存器等存储保护方法,使各应用程序相互隔离。

(3) 存储扩充绪论——操作系统的资源管理功能

系统提供虚拟存储技术,扩大逻辑主存。

设备管理

(1) 设备无关性

设备无关性是指用户向系统申请和使用的设备与实际操作的设备无关,以达到方便用户、提高设备利用率的目的。

(2) 设备分配

操作系统为各应用程序和运行实体分配各种设备。设备分配通常采用三种基本技术:独享、共享及虚拟技术。

(3) 设备的传输控制

设备的传输控制包括:启动设备、中断处理、结束处理三个方面

信息管理(文件系统)

文件系统为用户提供一种简便的、统一的存取和管理信息的方法,并解决信息的共享、数据的存取控制和保密等问题。

  • 信息组织
  • 存取方法
  • 文件共享
  • 文件安全
  • 文件完整性
  • 磁盘空间分配

操作系统的基本类型

批量操作系统

采用多道程序设计技术。该系统把用户提交的程序组织成作业形式。作业成批送入计算机,然后由作业调度程序自动选择作业,在系统内多道运行。

比较远古。

特点

  • 系统吞吐率高

    合理的搭配多道程序即可

  • 作业周转时间长,用户使用不方便

    用户向系统提交作业到获得系统的处理信息的时间间隔就是作业周转时间

分时操作系统

分时操作系统是操作系统的另一种类型。它一般采用时间片轮转的办法,使一台计算机同时为多个终端用户服务。该系统对每个用户都能保证足够快的响应时间,并提供交互会话功能。

特点

①并行性

宏观上并行

②独占性

微观上串行,当时间片很短时,就会形成独占的错觉

③交互性

用户和计算机之间可以进行命令行的交互对话

实时操作系统

实时操作系统对外部输入的信息,能够在规定的时间内处理完毕并作出反应。

特点

i 可靠性和安全性
放在第一位,系统的效率放在第二位。

ii 及时响应

这是实时操作系统的核心特点

实时系统

配置了实时操作系统的系统。该系统可以对科学实验、医学成像、工业控制、武器装备控制和特定显示系统进行实时控制的系统。

硬实时系统

系统必须满足应用程序对截止期限(deadline)的要求,若错过了截止期限,将导致灾难性后果。

软实时系统

系统中截止期限被错过的情况下,只造成系统性能下降而不会带来严重后果。

个人操作系统

windows是单用户多任务操作系统

UNIX系统是多用户多任务分时操作系统

Linux系统是多用户多任务系统

多处理机系统

广义上说,使用多台计算机协同工作来完成所要求的任务的计算机系统都是多处理机系统。传统的狭义多处理机系统是指利用系统内的多个CPU并行执行用户多个程序,以提高系统的吞吐量或用来进行冗余操作以提高系统的可靠性。

① 包含两个或多个功能相当的处理器

② 所有处理器共享一个公共内存

③ 所有处理器共享I/O通道、控制器和外围设备

④ 由一个操作系统控制

网络操作系统

网络操作系统把计算机网络中的各台计算机有机地结合起来,提供一种统一、经济而有效的使用各台计算机的方法,实现各个计算机之间的互相传送数据。网络操作系统最主要的特点是网络中各种资源的共享以及各台计算机之间的通信。

有点类似于集中式

分布式系统

分布式计算机系统是由多台计算机组成并满足下列条件的系统:系统中任意两台计算机通过通信方式交换信息;系统中的每一台计算机都具有同等的地位,即没有主机也没有从机; 每台计算机上的资源为所有用户共享;系统中的任意若千台计算机都可以构成一个子系统,并且还能重构;任何工作都可以分布在几台计算机上,由它们并行工作、协同完成。用于管理分布式计算机系统的操作系统称为分布式计算机系统。该系统的主要特点是:分布性和并行性。分布式操作系统与网络操作系统本质上的不同之处在于分布式操作系统中,若干台计算机相互协同完成同一任务。

分布式系统和计算机网络系统的共同点是:多数分布式系统是建立在计算机网络之上的,所以分布式系统与计算机网络在物理结构上是基本相同的。
他们的区别在于:分布式操作系统的设计思想和网络操作系统是不同的,这决定了他们在结构、工作方式和功能上也不同。网络操作系统要求网络用户在使用网络资源时首先必须了解网络资源,网络用户必须知道网络中各个计算机的功能与配置、软件资源、网络文件结构等情况,在网络中如果用户要读一个共享文件时,用户必须知道这个文件放在哪一台计算机的哪一个目录下;分布式操作系统是以全局方式管理系统资源的,它可以为用户任意调度网络资源,并且调度过程是“透明”的。当用户提交一个作业时,分布式操作系统能够根据需要在系统中选择最合适的处理器,将用户的作业提交到该处理程序,在处理器完成作业后,将结果传给用户。在这个过程中,用户并不会意识到有多个处理器的存在,这个系统就像是一个处理器一样。

操作系统的结构和硬件支持

操作系统虚拟机

配置在裸机上的第一层软件是操作系统。在裸机上配置了操作系统后就构成了操作系统虚拟机。

操作系统虚拟机的指令系统

裸机的指令系统:机器指令

操作系统虚拟机的指令系统:
1、操作命令

  • 键盘命令
  • 作业控制语言
  • 图形化用户界面

2、系统功能调用

操作系统的结构

层次结构

操作系统由许多层构成,每一层都提供一项功能,并且该功能依赖于该层以内的各层。“洋葱结构”。

各层之间的模块只能是单向依赖或单向调用(如只允许上层或外层模块调用下层或内层模块)关系。将整体式结构的无序性变为有序性

优点:化整为零(功能分解);结构清晰、不构成循环;易于调试、易于修改、易于扩充、易于维护、易于保证正确性(增加或替换一层不影响其它层)

微内核OS结构(客户机/服务器)

在微内核设计背后的思想是为了实现高可靠性,将操作系统划分成小的、良好定义的模块,只有其中一个模块–微内核–运行在内核态上,其余的模块,由于功能相对弱些,则作为普通用户进程运行。特别地由于把每个设备驱动和文件系统分别作为普通用户,这些模块中的错误虽然会使这些模块崩溃,但是不会使得整系统死机。

特点如下:

1.运行在核心态的内核:内核提供所有操作系统基本都具有的那些操作,只提供了一个很小的功能集合。

2.运行在用户态的并以客户机/服务器方式运行的进程层:除内核部分外,操作系统所有的其他部分被分成若干个相对独立的进程,每一个进程实现一组服务,称为服务进程。

客户机/服务器运行模式:
客户机进程与服务器进程之间的通信是采用发送消息进行的,这是因为每个进程属于不同的虚拟地址空间,它们之间不能直接通信,必须通过内核进行,而内核则是被映射到每个进程的虚拟地址空间内的,它可以操纵所有进程。客户机进程发出消息,内核将消息传给服务进程。服务进程执行相应的操作,其结果又通过内核用发消息方式返回给客户机进程。

客户机/服务器运行模式的优点:
将操作系统分成若干个小的并且自包含的分支(服务进程),每个分支运行在独立的用户进程中,相互之间通过规范一致的方式接收发送或消息而联系起来。操作系统在内核中建立起了最小的机制,而把策略留给用户空间中的服务进程,这带来了很大的灵活性。
可靠:分支独立只包含,单一故障不影响其它。
灵活:方便增加新的服务功能。
适宜于分布式环境:不同服务进程可以运行在不同处理器或计算机上。

客户机/服务器运行模式的缺点:
所有的用户进程只能通过微内核相互通信,微内核本身就成为系统的瓶颈,在一个通信很频繁的系统中,微内核往往不能提供很好的效率。

实例操作系统的结构

UNIX操作系统的结构

  • UNIX核心层
    • 处理机管理
    • 存储管理
    • 设备管理
    • 文件系统
  • UNIX实用层
    • 实用程序 —— 编辑程序、调试程序、系统状态监控、 文件管理等实用程序
    • 存储管理软件工具 ——源代码控制程序SCCS、文档准备程序包等

Linux系统的核心结构

Linux系统一般有4个主要部分:

内核、shell、文件系统和应用程序。内核、shell和文件系统一起形成了基本的操作系统结构,它们使得用户可以运行程序、管理文件并使用系统。

shell是系统的用户界面,提供了用户与内核进行交互操作的一种接口。它接收用户输入的命令并把它送入内核去执行,是一个命令解释器。

用户态和核心态

Linux系统将自身划分为两部分,一部分为核心软件,即是kernel,也称作内核空间,另一部分为普通应用程序,这部分称为用户空间。

windows系统的结构

运行时的组织结构

调用一个给定的OS的内部例程有两种方式:

  • 系统功能调用方式

只能通过用户程序间接调用:

  • 客户端/服务器方式

将操作系统服务作为系统服务进程来提供,服务请求和服 务响应是通过消息传递来实现的。
提供服务的是服务器,调用服务的是客户端

处理机的特权级

区分处理机状态是为了保护操作系统

处理机的态,又称为处理机的特权级,是中央处理机的工作状态。当前处理机正在执行哪类程序,决定处理机的态。

处理机状态的分类

① 管态 (Supervisor mode)

操作系统的管理程序执行时机器所处的状态,又称处理机的特权级。在此状态下处理机可使用全部指令(包括一组 特权指令);使用全部系统资源(包括整个存储区域)。

② 用户态(User mode)

用户程序执行时机器所处的状态称为用户态。在此状态下禁止使用特权指令,不能直接取用资源与改变机器状态, 并且只允许用户程序访问自己的存储区域。

处理机状态的特权指令集

① 涉及外部设备的输入/输出指令

② 修改特殊寄存器的指令

③ 改变机器状态的指令

实例操作系统处理机的状态

① DOS系统
不分态

② Windows 系统
3环 用户态
0环 系统态
还有1、2环预留

③ UNIX系统 (Linux)系统
00 核态
01 管态
11 用户态

中断及其处理

在上述的处理机的状态可见,假设用户程序执行时,超过了它的权限要求,就要把系统从用户态转变为管态。在这个过程中,系统将发生中断。

中断

所谓中断是指某个事件 (例 如电源掉电、定点加法溢出 或I/O传输结束等) 发生时, 系统中止现行程序的运行、 引出处理事件程序对该事件 进行处理,处理完毕后返回 继续执行 断点继续执行的过程。

需要明确的是中断是硬件和软件结合实现的:硬件实现的中断进入;软件的中断处理过程。

中断类型

(1) 按中断功能分类

① 输入输出中断: I/O传输结束或出错中断

② 外中断: 时钟中断、操作员控制台中断、通信中断等

③ 机器故障中断 :电源故障、主存取指令错等

④ 程序性中断 :定点溢出、用户态下用核态指令、非法操作

⑤ 访管中断 :对操作系统提出某种需求时所发出的中断(例如:printf)

(2) 按中断方式分类

① 强迫性中断: 不是正在运行的程序所期待的中断。 如:输入输出中断、外中断、机器故障中断、程序性中断

② 自愿中断: 是运行程序所期待的事件。 如:访管中断

(3) 按中断来源分类

① 中断 :由处理机外部事件引起的中断

② 俘获 :由处理机内部事件引起的中断

③ 中断与俘获的例

中断进入(响应)

(1) 保护现场和恢复现场

① 现场

在中断的那一时刻能确保程序继续运行的有关信息。

ⅰ 后继指令所在主存的单元号
ⅱ 程序运行所处的状态
ⅲ 指令执行情况
ⅳ 程序执行的中间结果等

② 保护现场

当中断发生时,必须立即把现场信息保存在主存中,这一 工作称之为保护现场。

③ 恢复现场

程序重新运行之前,把保留的该程序现场信息从主存中送 至相应的指令计数器、通用寄存器或一些特殊的寄存器中。 完成这些工作称为恢复现场。

(2) 程序状态字 (psw)

① 定义

反映程序执行时机器所处的现行状态的代码。

② 内容

指令地址、指令执行情况、处理机状态、应屏蔽的中断等。

③ 程序状态字的例子

ⅰ IBM 370 机 程序状态字内容 → PSW:寄存器
ⅱ IBM PC 机 程序状态字内容 → CS IP 指令地址、 flag 标志寄存器
ⅲ PDP 11系列机 程序状态字内容 → PC 指令计数器 、PS 处理器状态寄存器

(3) 什么是中断响应

中断响应是当中央处理机发现已有中断请求时,中止现行 程序执行,并自动引出中断处理程序的过程。

(4) 中断响应所需的硬件支持

指令计数器、处理机状态寄存器、系统堆栈、中断向量表

(5) 中断响应过程

① 保留程序断点及处理机有关信息

② 自动转入相应的中断处理程序执行

(6) 中断响应的实质

交换指令地址及处理机的状态信息

软件中断处理

当硬件完成了中断进入过程后,由相应的中断处理程序得到控制权,进入了软件的中断处理过程。

Linux系统的特权级与中断处理

硬件部分和上述讨论的一致。区别在于其软件部分。

Linux将中断分为两个部分:

  • 上半部:中断处理有严格时间限制的工作,是关键而紧迫的部分。
  • 下半部:处理可以稍后完成的工作,是可以被打断的。

操作系统的用户接口

用户工作环境

用户工作环境的形成

由OS为用户提供:

(1) 系统提供各种硬件、软件资源

(2) 设计并提供使用方便的命令集合

(3) 将OS装入计算机并初始化,形成可供使用的工作环境

操作系统的初启

(1) 系统引导的任务

将操作系统的必要部分装入主存并对系统进行初始化工作,最终使系统处于命令接收状态。

  • 初始引导:把系统核心装入主存中的指定位置,并在指定地址启动
  • 核心初始化:执行系统核心的初启子程序,初始化系统核心数据(初始化系统数据结构和参数)
  • 系统初始化:为用户使用系统做准备

经过这三个阶段,OS就处在接收命令的状态。

(2) 系统引导的方式

①现场独立引导方式(滚雪球方式,bootup)

OS核心文件存储在系统本身的存储设备中,由系统自己将OS核心程序读入主存并运行,建立一个操作环境。

适用于微机和大多数系统

②辅助下装方式(download)

OS主要文件不放在系统本身的存储设备中,在系统启动后执行下装操作,从另外的计算机系统中将操作系统常驻部分传送到该计算机中,使它形成一个操作环境。

适用于多计算机系统、由主控机与前端机构成的系统以及分布式系统。

(3) 独立引导方式(滚雪球方式) 的过程

①初始引导

  • 系统加电;
  • 执行初始引导程序,对系统硬件和配置进行自检,保证系统没有硬件错误;
  • 硬盘中读入操作系统引导程序,并将控制权交给该程序模块。

②引导程序执行

  • 引导程序执行,将操作系统核心文件读入内存,并将控制交给核心的初始化程序

③核心初始化

初始化系统数据结构及参数

  • 系统加电建立进程有关的数据结构;
  • 获得自由存储空间的容量,建立存储管理的数据结构;
  • 建立系统设备和文件系统的数据结构;
  • 初始化时钟。

④系统初始化

  • 完善OS的操作环境,装载命令处理程序(或图形用户界面),并初始化;
  • 在多用户系统中,为每个终端建立命令解释进程,使系统处于命令接收状态。

(4) Linux系统初启

Linux系统是以滚雪球的方式启动

加电或复位→BIOS的启动→ Boot Loader → OS初始化

系统生成

所谓系统生成,就是指为了满足物理设备的约束和需要的系统功能,通过组装一批模块来产生一个清晰的、使用方便的操作系统的过程。

一般是厂商进行组装

应用程序的处理

处理应用程序的步骤

编辑——编译——-连接——–运行

编译:

高级语言(我们这里指C源文件) 代码 转化为 汇编代码

1.1.1 预处理
预处理过程通过预处理器来完成, 预处理器是程序中处理输入数据,产生能用来输入到其他程序的数据的程序。输出被称为输入数据预处理过的形式,常用在之后的程序比如编译器中.

本文只讨论C预处理器, C预处理器是C语言、C++语言的预处理器。用于在编译器处理程序之前预扫描源代码,完成 头文件的包含, 宏扩展, 条件编译, 行控制(line control) 等操作。

对于C/C++语言预处理一般分为以下几个过程:

1.1.1.1 包含文件
所谓包含文件即为头文件 #include 到的文件, 在预处理的过程中会将其加入到预处理器的输出文件中, 以供编译程序处理.

汇编

将汇编代码翻译成目标机器语言的过程. 生成的目标文件也就是与源程序在逻辑上等效的机器语言代码.

生成的机器语言代码被称为目标代码, 生成的二进制文件被称为目标文件(.o), 也成为二进制文件.

链接:

链接过程是由链接器进行操作的. 链接器(英语:Linker),又译为链接器、连结器,是一个程序,将一个或多个由编译器或汇编器生成的目标文件外加库链接为一个可执行文件

2.1.1 静态链接(编译时)
链接器将函数的代码从其所在地(目标文件或静态链接库中)拷贝到最终的可执行程序中。这样该程序在被执行时这些代码将被装入到该进程的虚拟地址空间中。静态链接库实际上是一个目标文件的集合,其中的每个文件含有库中的一个或者一组相关函数的代码。
优点: 只需保证在开发者的计算机有正确的库文件,在以二进制发布时不需考虑在用户的计算机上库文件是否存在及版本问题.
缺点: 生成的可执行文件体积较大。当初正是为了避免此问题,才开发了动态库技术。

2.1.1 动态链接 (加载, 运行时)
所谓动态链接,就是把一些经常会共用的代码(静态链接的OBJ程序库)制作成DLL档,当可执行文件调用到DLL档内的函数时,操作系统才会把DLL档加载存储器内,DLL档本身的结构就是可执行档,当程序有需求时函数才进行链接。透过动态链接方式,存储器浪费的情形将可大幅降低。静态链接库则是直接链接到可执行文件。
DLL档本身也是可执行文件, 在程序执行的时候直接进行动态调用即可.

静态链接 动态链接
编译时 加载, 运行时
lib在编译时就组装进exe文件 程序运行时exe文件可以动态的加载dll
不用考虑计算机库文件版本 节省内存, 维护性高
整个软件包只有exe文件 软件包中有exe和dll
lib文件是外部函数和变量, 在编译时复制进目标程序, 后缀为.a dll文件本身是可执行的, 在运行时动态链接, 可以包含源码, 数据, 资源的多种组合, 后缀为.so

连接类型

静态连接

一个源程序经编译后,生成一个可重定位的目标模块,并产生内部符号表和外部符号表,供连接程序(Link)使用。

①内部符号表

​ 本模块可以被其他程序调用的入口点。

②外部调用表

​ 本模块要调用的外部的程序模块名。操作系统的用户接口——应用程序的处理

③连接需要做的工作

  • 将各模块连接成为一个整体;
  • 构造全程符号表,在其中填写模块的逻辑地址;
  • 查找各程序段的外部调用表,填入对应调用函数的地址

④静态连接的缺点

​ 静态连接将所需的外部函数链接到目标文件中形成为一个可执行文件。若多个应用程序都调用了同一个库中的外部函数,那么,多个应用程序的目标文件中都会包含这个外部函数对应的代码

动态连接

动态连接不需要将外部函数链接到目标文件中。而是在应用程序中需要调用外部函数的地方作记录,并说明要使用的外部函数名和引用入口号。

用户接口(用户界面)

操作系统的用户接口分为:操作接口和程序接口。

(1) 操作界面(命令接口)

用户使用操作界面来组织工作流程和控制程序的运行。

(2)系统功能服务界面(程序接口)

用户程序在其运行过程中,使用系统功能调用来请求操作系统的服务。

操作接口

分为以下三种形式:其形式和操作系统的类型有关。

  • 键盘命令(具有交互操作方式的操作系统:分时操作系统、个人计算机操作系统,是联机处理方式)
  • 图形化界面(具有交互操作方式的操作系统:分时操作系统、个人计算机操作系统)
  • 作业控制语言(批处理操作系统,是脱机处理方式)

作业控制语言(JCL)

  • 一种命令语言,包括作业处理命令和资源请求命令
  • 脱机方式下系统提供作业控制语言
  • 批处理系统中作业的组成
    • 作业申请:作业名、需用CPU时间、最迟完成时间、资源请求(主存、外设)等
    • 操作说明书:编辑命令、编译命令、连接命令、运行命令等
    • 程序与数据

结合之前的脱机处理方式,这种方式要求我们提前预测可能出现的处理,因为无法控制作业的运行过程。

键盘命令

  • 操作系统为联机用户提供的一种操作命令,用户通过这一组命令直接控制和干预程序的运行
  • 系统为联机用户提供键盘命令
  • 键盘命令的功能
    • 分时操作系统——用于注册、通信、注销的各类命令
    • 个人计算机操作系统——用于通信的各类命令

图形用户界面

  • 菜单驱动方式面向屏幕的交互方式,将键盘命令以屏幕方式来体现;命令和系统能完成的操作,用菜单分类分窗口列出;用户像点菜一样选择命令或某种操作,以控制系统去完成指定的工作;菜单系统的类型有多种,如下拉式菜单、上推式菜单和随机弹出式菜单
  • 图符驱动方式图符(Icon)也称图标,是一个小小的图符符号,代表操作系统中的命令、系统服务、操作功能、各种资源。良好的用户交互界面,将菜单驱动、图符驱动、面向对象技术等集成在一起,形成一个图文并茂的视窗操作环境。

图形用户界面的特点

  • 所有程序以统一的窗口形式出现
  • 提供统一的菜单格式
  • 系统资源、系统命令、操作功能以图标表示
  • 统一的操作方法

(1) MS-DOS ─ ─ 键盘命令、系统功能调用

(2) Windows─ ─图形用户界面、系统功能调用

(3) Linux (UNIX) ─键盘命令(XWindow)、系统功能调用

系统功能调用(程序接口)

系统功能调用是用户在程序一级请求操作系统服务的一种手段,它是带有一定功能号的“访管指令”。其功能是由操作系统中的程序完成的,即由软件方法实现的。

用户程序如何调用系统功能:通过访管方式。

需要注意到系统的程序是处于管态的,用户程序是处于用户态的。我们无法像用户程序调用用户程序一样调用系统程序(会发生处理机状态的转换)。

访管方式

访管指令(自愿进管指令)

svc n svc 表示机器访管指令的操作码记忆符,n为地址码(功能号)

用户可以使用不同功能号的访管指令来请求不同的功能

访管中断

当处理机执行到访管指令时发生中断,该中断称为访管中断,它表示正在运行的程序对操作系统的某种需求。

借此中断,机器状态由用户态转为管态。访管中断处理程序会转到用户程序所需要的系统程序。

系统调用的特点

不同的操作系统,系统调用实现的具体方法有所不同,但其实质特点相同:

  • 每个系统调用对应一个系统调用号(要请求调用某个系统功能就要在访管时给出对应的功能号)
  • 每个系统调用有一个对应的执行程序段
  • 每个系统调用要求一定数量的输入参数和返回值
  • 整个系统有一个系统调用执行程序入口地址表

系统功能调用vs. 库函数

在程序设计语言(如C语言)中,往往提供与各系统调用对应的库函数,应用程序可通过对应的库函数来使用系统调用

库函数的目的是隐藏访管指令细节,使系统调用更象过程调用,但一般地说,库函数属于用户程序而非系统程序(但是有些库函数是不涉及系统调用的)

库函数在执行是不会导致CPU状态的变化,但是其系统调用的代码属于OS,故在系统调用的代码执行的时候就会让CPU的状态由用户态变为管态

操作系统为用户提供系统调用也出于安全和效率考虑,使得用户态程序不能自由地访问内核关键数据结构或直接访问硬件资源

Linux系统调用由两部分组成:

  • 核心函数:实现系统调用功能的(内核)代码
  • 接口函数:提供给应用程序的API,以库函数形式存在Linux的lib.a中

Linux系统调用控制程序

(1)取系统调用号,检验合法性;

(2)建立调用堆栈,保护现场信息;

(3)根据系统调用号定位核心函数地址;

(4)根据通用寄存器内容,从用户栈中取入口参数;

(5)核心函数执行,把结果返回应用程序;

(6)执行退栈操作,判别调度程序scheduler是否将执行。

习题补充

第一章 习题及解答

1-2批处理系统和分时系统各具有什么特点?为什么分时系统的响应较快?

答:在批处理系统中操作人员将作业成批装入计算机,在程序运行期间用户不能干预,用户使用计算机的方式是脱机操作方式。批处理系统中作业成批处理,系统内多道程序是并发执行的,所以其特点是:系统吞吐率高,但作业周转时间长,用户使用不方便。

在分时系统中不同用户通过各自的终端以交互方式共同使用一台计算机,计算机以“分时”的方法轮流为每个用户服务,用户使用计算机的方式是联机操作方式。分时系统的主要特点是多个用户同时使用计算机的同时性,人机问答方式的交互性,每个用户独立使用计算机的独占性以及系统快速响应的及时性。

分时系统一般采用时间片轮转的方法,使一台计算机同时为多个终端用户服务,因此分时系统的响应较快。

1-3实时信息处理系统和分时系统从外表看来很相似,它们有什么本质的区别呢?

答:实时信息处理系统和分时系统从外表来看,都是一台计算机连接一个或多个终端设备;用户以联机方式直接与计算机交互。二者的本质区别是:

实时信息处理系统采用的进程调度策略是优先调度策略,而分时系统采用的进程调度策略是时间片轮转调度策略。

实时信息处理系统的终端设备通常只是作为执行装置或咨询装置,不允许用户编写新的程序或修改已有的程序。而分时系统的用户可以通过终端设备修改程序,可以与系统交互以控制程序的运行。

1-5什么是多道程序设计技术?试述多道程序运行的特征?

答:多道程序设计技术是指同时多个作业或程序进入主存并允许它们交替执行和共享系统中的各类资源。当一道程序因某种原因如 I/O 请求而暂停执行时,CPU立即转去执行另一道程序。多道程序运行具有如下特征:

多道:计算机内存中同时存放几道相互独立的程序。

宏观上并行:同时进入系统的几道程序都处于运行过程中,它们先后开始了各自的运行,但都未运行完毕。

微观上串行:从微观上看,主存中的多道程序轮流或分时地占有处理机,交替执行。

1-9 设一计算机系统有输入机一台、打印机两台,现有A、B两道程序同时投入运行,且程序A先运行,程序B后运行。程序A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。程序B运行的轨迹为:计算50ms,输入数据80ms,再计算100ms,结束。回答如下问题。

(1)用图画出这两道程序并发执行时的工作情况。

(2)说明在两道程序运行时,CPU 有无空闲等待?若有,在哪段时间内等?为什么会空闲等待?

(3)程序 A、B 运行时有无等待现象?在什么时候会发生等待现象?

答:(1) 这两道程序并发执行时的工作情况如下图所示。

imgimgimgimg

CPU 50ms 50ms 50ms 100ms
输入机 80ms
打印机1 100ms 100ms
打印机2
A B

(2)CPU有空闲等待,当B 50ms计算完后,A 100ms打印仍在进行,中间CPU空闲 50ms。

(3)程序 A、B运行时有等待现象。当 B 80ms输入完成后,需等待20ms后才能进行计算。

第二章 习题及解答

2-1什么是操作系统虚拟机?

答:操作系统是最基本的系统软件,它是硬件功能的第一层扩充。配置了操作系统的计算机称为操作系统虚拟机。

操作系统虚拟机除了可使用原来裸机提供的各种基本硬件指令,还可以使用操作系统提供的操作命令和系统调度命令。

2-3什么是处理机的态?为什么要区分处理机所谓态?

答:所谓处理机的态就是处理机当前处于何种状态,正在执行哪类程序。为了保护操作系统,至少需要区分两种状态:管态和用户态。

操作系统是计算机系统中最重要的系统软件,为了能正确地进行管理和控制,其本身是不能被破坏的。为此,系统应能建立一个保护环境。当用户程序执行时,应有所限制,其所需资源必须向操作系统提出请求,自己不能随意取用系统资源,如不能直接启动外部设备的工作,更不能改变机器状态等。因此系统必须区分处理机的工作状态,即区分当时正在执行的程序的类别。

2-4 什么是管态?什么是用户态?二者有何区别?

答:管态又称为系统态,是操作系统的管理程序执行时机器所处的状态。在此状态下中央处理机可以使用全部机器指令,包括一组特权指令 (例如,涉及外部设备的输入/输出指令、改变机器状态或修改存储保护的指令) ,可以使用所有的资源,允许访问整个存储区。

用户态又称为目态,是用户程序执行时机器所处的状态。在此状态下禁止使用特权指令,不能直接取用资源与改变机器状态,并且只允许用户程序访问自己的存储区域。

二者的区别如下所述。

(1)处理机当前正在执行的程序类别不同。管态执行的是系统程序;用户态执行的是用户程序。

(2)执行的指令范围不同。管态下可以执行全部指令;用户态不能执行特权指令。

(3)使用资源范围不同。管态可以使用全部系统资源;用户态只能使用用户私有资源,如只能访问自己的存储区域。

2-6按中断的功能来分,中断有哪几种类型?

答:按中断的功能来分,中断有如下五种类型:

(1) I/O 中断

(2) 外中断

(3) 硬件故障中断

(4) 程序性中断

(5) 访管中断

2-11 什么是程序状态字?在微机中它一般由哪两个部分组成?

答:程序状态字是指反映程序执行时机器所处的运行状态的代码。在微机中它一般由指令计数器 PC 和处理机状态寄存器 PS 组成。

2-12 什么是向量中断?什么是中断向量?

答:向量中断是指当中断发生时,由中断源自己引导处理机进入中断服务程序的中断过程。中断向量就是存储该类型中断服务例行程序的入口地址和处理器状态字的存储单元。

2-18 Linux系统的中断处理为什么要分为上半部和下半部?

答:操作系统的中断机制实现了I/O设备与CPU以及多进程之间的同时执行,大大提高了系统效率。

操作系统的中断处理程序比较复杂,而且在系统一级处理时不允许打断。如何提高中断处理的效率?如何解决处理时间短的要求和处理事务复杂性的矛盾?Linux提出了一个很好的解决办法。Linux系统将中断处理程序分为两部分,将中断响应后必须立即处理的工作即刻执行(而且其执行时必须关中断),而将更多的处理工作向后推迟执行。即将中断处理程序分为上半部(tophalf)和下半部(bottom half)。Linux系统将中断处理程序分为上半部和下半部的目的是为了缩短关中断的时间,提高系统的处理能力。

第三章 习题及解答

3-3 处理应用程序分为哪几个步骤?这些步骤之间有什么关系?

答:处理应用程序分为四个步骤:编辑,编译,连接和运行。这些步骤是相互关联、顺序执行的。具体表现为:

每个步骤处理的结果产生下一个步骤所需要的文件;

每一个步骤能否正确地执行,依赖于前一个步骤是否成功地完成。

3-5 用户与操作系统的接口是什么?一个分时系统提供什么接口?一个批处理系统又提供什么接口?

答:用户与操作系统的接口是操作系统提供给用户与计算机打交道的外部机制。一个分时系统提供的接口有系统功能调用和键盘操作命令。一个批处理系统提供的接口有系统功能调用和作业控制语言。

3-8 什么是系统调用?对操作系统的服务请求与一般的子程序调用有什么区别?

答:系统调用是用户在程序一级请求操作系统服务的一种手段。编程人员利用系统调用,在源程序一级动态请求和释放系统资源,调用系统中已有的系统功能来完成那些与机器硬件部分相关的工作以及控制程序的执行等。因此,系统调用像一个黑箱子那样,对用户屏蔽了操作系统的具体动作而只提供有关的功能。

系统调用与一般过程调用的主要区别如下:(1)程序的性质不同。系统调用服务例程是操作系统程序的一部分,它在核态下执行。而用户子程序是用户程序的一部分,它在用户态下执行。(2)调用方式不同。系统调用是通过陷入到操作系统内核来实现的,调用它们需要中断处理机制来提供系统服务。而子程序调用是在用户程序中直接调用。

3-10 简述系统调用的执行过程。

答:系统调用命令的具体格式因系统而异,但由用户程序进入系统调用的步骤及执行过程大体相同。其执行过程如下:

1.保护用户程序的现场信息,同时把系统调用命令的编号等参数放入指定的存储单元;

2.根据系统调用命令的编号查找系统调用入口表,找到相应系统功能调用子程序的入口地址;

3.转到该子程序执行,当系统调用命令执行完毕,相应的结果通常返回给参数,这些参数放在指定的存储单元里;

4.系统调用命令执行完毕后恢复用户程序执行的现场信息,同时把系统调用命令的返回参数或参数区首址放入指定的寄存器中,供用户程序使用。

3-12 在Linux系统中,增加一个新的系统调用需要做哪些工作?

答:在Linux系统中,增加一个新的系统调用需要做的工作包括如下几个方面。

(1) 编写一个新增加的功能的服务例程。编写新增的服务例程,并加到内核中去,即在/usr/src/linux/kernel/sys.c文件中增加一个新的函数。

(2) 增加一个新的系统调用号。在linux中,每个系统调用被赋予一个唯一的系统调用号。找到linux中定义系统调用号定义的文件 (在include/asm-i386/unistd.h头文件中)。在此文件中按其规定的格式添加一项。

(3) 在系统调用表中登记新的系统调用号以及对应的服务例程。系统调用表记录了内核中所有已注册过的系统调用,它是系统调用的跳转表,实际上是一个函数指针数组,表中依次保存所有系统调用的函数指针。找到linux中的系统调用表 (Linux系统调用表保存在arch/i386/kernel/下的entry.S中)。在此文件中按其规定的格式增加一个新的系统调用号以及对应的服务例程。

(4) 新增加的服务例程要为Linux系统接受,必须重新编译内核,生成新的包含新增服务例程的内核。

选择算法

选择问题

从n个元素的集合中选择第i个顺序统计量的问题形式化地归结为“选择问题”。

中位数和顺序统计量

1)顺序统计量:在一个由n个元素组成的集合中,第i个顺序统计量(order statistic)是该集合中的第i小的元素。如:在一个元素集合中,最小值是第1个顺序统计量(i=1);最大值是第n个顺序统计量(i=n)

2)中位数:对一个有n个元素的集合,将数据排序后,位置在最中间的数称为该集合的中位数。

假设集合中的元素是互异的(可推广至包含重复元素的情形)。

输入:一个包含n个(互异)元素的集合A和一个整数i,1≤i≤n。
输出:元素x∈A,且A中恰好有i-1个其他元素小于它。

解决的办法:

1)排序元素集合排序后,位于第i位的元素即为该集合的第i个顺序统计量。时间复杂度:O(nlogn)

2)选择算法设法找出元素集合里面的第i小元素,该元素为集合的第i个顺序统计量。时间复杂度:O(n)

最大值和最小值问题

在一个有n个元素的集合中,需要做多少次比较才能确定其最小元素或者最大值呢?n-1次,时间:O(n)

这是求解上述问题的最好结果

不失一般性,就变成了求解上述第i小的问题。

快速选择算法(Quick Selection)

通常用来在未排序的数组中寻找第k小/第k大的元素。快速选择及其变种是实际应用中最常使用的高效选择算法。

快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(nlog n)至**O(n)**,不过最坏情况仍然是O(n^2^)。

Quick Selection原理

Quick Selection算法和Quick Sort算法是由同一个作者提出,这两者之间有很大的相似之处——分治,即将问题的规模一次次的减小,直到求出最终解。

目标:找到第n大的数

  1. 随机产生一个pivot
  2. 根据这个pivot,将小于其的数放左边,大于其的数放右边
  3. 更新第n大数的估计值的位置,选择其中一边,直到=n
  4. 重复2、3步骤

Quick Select复杂度分析

1、时间复杂度

完整的平均时间复杂度分析非常复杂,在这里不再赘述。有兴趣的可以看这里
一般来说,因为我们才用了随机选取pivot的过程,平均来看,我们可以假设每次pivot都能选在中间位置。设算法时间复杂度为T(n)。在第一层循环中,我们将pivot与n个元素进行了比较,这个时间为cn 。
所以第一步时间为:T(n) = cnc + T(n/2)。其中T(n/2)为接下来递归搜索其中一半的子数组所需要的时间。
在递归过程中,我们可以得到如下公式:
T(n/2) = c(n/2) + T(n/4)
T(n/4) = c(n/4) + T(n/8)

T(2) = 2c + T(1)
T(1) = 1
c
将以上公式循环相加消除T项可以得到:
T(n) = c(n + n/2 + n/4 + n/8 + … + 2 + 1) = 2n = O(n)
因此得到Quick Select算法的时间复杂度为O(n)。

1)造成最坏情况是O(n^2^)的原因分析:类似快速排序的最坏情况。

2、空间复杂度

算法没有使用额外空间,swap操作是inplace操作,所以算法的空间复杂度为O(1)。

Quick Select Java实现

Leetcode 215 Top k

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
class Solution {
public int findKthLargest(int[] nums, int k) {
int begin =0;
int end = nums.length-1;
k=nums.length+1-k;
while(begin<end)
{
int pos = quick_select(nums,begin,end);
if(pos==k-1)break;
else if(pos<k-1)begin=pos+1;
else end=pos-1;
}
return nums[k-1];
}
public int quick_select(int[] s,int right,int left)
{
int i=right,j=left;
int x=s[right];
while(i<j)
{
while(i<j&&s[j]>=x)//找到右边最近一个小于x的值
j--;
if(i<j)
{
int temp =s[j];
s[i]=temp;//填坑
s[j]=s[i];
i++;
}//此时 s[j]==x
//从左向右找数填s[j]
while(i<j&&s[i]<=x)
i++;
if(i<j)
{
int temp =s[i];
s[j]=temp;//填坑
s[i]=s[j];
j--;
}//此时 s[i]==x
}
//退出时 i==j,将x填入坑中
s[i]=x;
return i;
}
}

最坏情况为线性时间的选择算法(五分化中项的中项)

本质上还是快速选择算法,但是我们在选择枢纽元的时候,有既定的策略—–五分化中项的中项(也叫中位数的中位数)。这样就可以保证在最坏情况下依然是线行O(n)的复杂度

实现

  1. 将输入数组的n个元素划分成[n/5]组,每组5个元素,且最多只有一组由剩下的n mod 5个元素组成

  2. 寻找这[n/5]个元素的中位数,首先对这组元素进行插入排序,然后确定每组有序元素的中位数,即第三个元素

  3. 把每组找出的中位数重组为一个新的数组,找出其中位数x(递归调用SELECT以找出中位数x,如果由偶数个中位数,约定x是较小的中位数)

  4. 使用PARTITION,将x对输入数组进行划分,返回k,低区的k - 1个元素小于x,高区的n - k个元素大于x
    (partition的工作原理是将一个数组划分成两段,其中一段的元素都小于主元,另一段数组的元素都大于主元)

  5. 比较k和i的大小,如果i < k,在低区递归调用SELECT,如果i > k,在高区递归调用SELECT,如果i = k,直接返回x。

简单来说:我们选择的枢纽元是中位数的中位数X,其他的和快速选择算法一致,递归求解第K大的值。

时间复杂度分析

对于大于中位数的中位数x,大于x的元素个数至少有:
3(⌈1/2⌈n/5⌉⌉−2)⩾3n/10−6
那么,递归至多作用于(7n/10+6)个元素。
算法中的
第(3)步时间复杂度为T(⌈n/5⌉)
第(5)步的时间复杂度为T(7n/10+6)
我们可以得到算法的总时间复杂度为
T(n)≤T(⌈n/5⌉)+T(7n/10+6)+O(n)
假设一个任意常数C,使得T(n)≤cn
又假设O(n)的上界为an
那么带入c,a得到:
T(n)⩽9cn/10+7c+an=cn+(−9n/10+7c+an)
只需要证明: −9n/10+7c+an⩽0 即可
该不等式等价于:c⩾10a(n/(n−70))
所以当n>140时,c⩾20a这样就可以满足不等式。
因此最坏情况下选择算法的运行时间是线性的。

算法描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//下面给定的是二次取中算法的说明性描述
SELECT2(int a[],int i,int n)
{
//在集合a中找第i小元素,且n为集合a的元素数量
if(n<r)
{
//采用插入排序直接对a进行分类并返回第i小的元素
}
else
{
//把a分成大小为r的(n/r)个子集合,忽略多余的元素
}
int m[r];//表示这些子集合的中间值集合
v=SELECT2(m,(n/r)/2,(n/r));//得到中间值的中间值v
j=PARTITION(a,v);//得到v在a中是第j小元素
if(i==j)
return v;
else if(i<j)//说明要往下区寻找
return SELECT2(s,i,j-1);//s是a[1:j-1]
else
return SELECT2(R,i-j,n-j);//R是a[j+1:n]
}

算法分析

记T(n)是SELECT2所需的最坏情况时间

对特定的r分析SELECT2:选取r=5。

假定A中的元素各不相同,则有

  • 若n≤r,则采用插入法直接对A分类并返回第i小元素 → Ο(1)
  • 把A分成大小为r的(n/r)个子集合,忽略多余的元素 → Ο(n)
  • 得到m的集合(中间值) → Ο(n)
  • v=SELECT2(m,(n/r)/2,(n/r));//得到中间值的中间值v → T(n/5)
  • j=PARTITION(a,v);//得到v在a中是第j小元素 → Ο(n)
  • else if(i<j)//说明要往下区寻找 → T(3n/4),当n≥24
    return SELECT2(s,i,j-1);//s是a[1:j-1]
    else
    return SELECT2(R,i-j,n-j);//R是a[j+1:n]

用归纳法(代入法)可证:T(n)≤20cn

故,在r=5地情况下,求解n个不同元素选择问题的算法SELECT2的最坏情况时间是Ο(n)。

进一步分析

若A中有相同的元素时,上述结论T(n)=O(n)可能不成立

原因:

步骤⑤经PARTITION调用所产生的S和R两个子集合中可能存在一些元素等于划分元素v,可能导致|S|或|R|大于0.7n+1.2,从而影响到算法的效率。

例如:设r=5,且A中有相同元素。不妨假设其中有0.7n+1.2个元素比v小,而其余的元素都等于v。
则,经过PARTITION,这些等于v的元素中至多有一半可能在落在S中,故|S|≤0.7n+1.2+(0.3n-1.2)/2=0.85n+0.6。
同理,|R|≤0.85n+0.6。
可得,此时步骤④和⑥所处理的元素总数将是
T(n/5)+T(0.85n+0.6)≈1.05n+0.6>n
不再是线性关系。故有T(n)≠Ο(n)

改进

方法一:将A集合分成3个子集合U,S和R,其中U是由A中所有与v相同的元素组成,S是由A中所有比v小的元素组成,R则是A中所有比v大的元素组成。

同时步骤⑥更改:

1
2
3
4
5
case 
:|S|≥k:return(SELECT2(S,k,|S|)
:|S|+|U|≥k:return(v)
:else: return(SELECT2(R,k-|S|-|U|,|R|))
endcase

从而保证|S|和|R|≤0.7n+1.2成立,故关于T(n)的分析仍然成立。即T(n) = Ο(n)

中位数问题

示例:

石油管的最优位置Olay教授正在为一家石油公司咨询,公司正在计划建造一条由东向西的大型管道。该管道要穿过一个有n口井的油田。从每口井中都有一条喷油管沿最短路径与主管道直接相连(或南或北)

问题:给定各口井的x坐标和y坐标。问,Olay教授如何选择主管道的最优位置,使得喷管长度总和最小?

带权中位数:首先也是将这个数组的数据按一定的顺序排列, 带权中位数(Weighted Median)对于n个互不相同的元素集合x1、x2……xn,其权重依次为w1、w2……wn。令W =
$$
\sum_{i=1}^n{Wi}=1
$$
,则带权中位数XK满足:(这里的权重可以用这个数据出现的频率来表示,或者这个数据的重要性)

$$
\sum_{X_i<X_k} W_i<\frac{1}{2}
$$

$$
\sum_{X_i>X_k} W_i<=\frac{1}{2}
$$

带权中位数的应用

(1)一维空间上的问题

一条直线上有若干个带权的点p1,p2,…,pn,它们的权重分别是ω1,ω2,…,ωn,在该直线上寻找一个点p,使得
$$
\sum_{i=1}^nW_id(p,p_i)
$$
最小,其中d(a,b)表示点a与b之间的距离d(a,b)=|a-b|——称点p为该n个点的一维带权中位数。

称点p为该n个点的一维带权中位数。

(2)二维空间上的问题

设二维平面上分布着n个点p1, p2,… pn,点pi的坐标用(xi,yi)表示,每个点附有一个权重ωi,
$$
\sum_{i=1}^n{Wi}=1
$$

定义点p1(x1,y1)与点p2(x2,y2)之间的距离是
d(p1, p2)=|x1-x2|+|y1-y2|(称为Manhattan距离)
问题:在二维平面上找一个点p(x,y),使得
$$
\sum_{i=1}^nW_id(p,p_i)
$$
最小,则称p为该二维平面上n个点的带权中位数。

问题:为什么使
$$
\sum_{i=1}^nW_id(p,p_i)
$$
最小的点满足
$$
\sum_{p_i<p} W_i<=\frac{1}{2}和 \sum_{p_i>p} W_i<\frac{1}{2}?
$$

带权中位数问题常见算法:

1:朴素算法:

方法:枚举集合点,进行计算

时间复杂度:O(N^2)

2:递推算法:

1.朴素递推:

方法:分别计算对于一个点从左右过来的总代价,求其最小值

时间复杂度:O(N)

2.递推改进算法

方法:利用前面证明的结论和带权中位数的定义,只需要一次扫描即可

时间复杂度:O(N)

3:分治算法:

1. O(NlogN)的算法

方法:二分集合点,比较集合点为M与M+1时的谁更优,不断缩小范围

2. O(N)的二分改进算法

方法:二分集合点,但利用了已知信息,将时间复杂度降到O(N)