1
2
3
4
5
6
7
8
9
title: 操作系统
description: 操作系统
date: 2023-10-28 11:45:00
update: 2023-10-28 11:45:00
tags:
  - 课程
categories:
  - 操作系统
swiper_index: 16

操作系统

进程的描述与控制

程序顺序执行

程序执行过程中通常存在顺序执行问题

  • 构成程序的若干个程序段之间
  • 组成程序段的多条语句之间

程序顺序执行时的特征

  1. 顺序性

    处理机的操作，严格按照规定顺序执行

  2. 封闭性

    • 封闭环境下运行，程序独占全机资源
    • 只有当前运行程序才能改变资源状态
    • 程序执行结果不受外界因素的影响

  3. 可再现性

    只要程序执行时的环境和初始条件相同，程序重复执行结果相同

程序的并发执行

在一段时间里，多道程序一起共享计算机系统的资源，一起操作向前推进

程序并发执行时的特征

  1. 间断性

    ”执行一暂停执行—执行”的活动规律

  2. 失去封闭性

    系统资源共享及资源状态改变的多样性，致使程序运行失去封闭性，程序运行必然会受到其它程序的影响

  3. 不可再现性

    并发执行的程序，计算结果与其执行速度及时间有关

进程的定义及特征

进程的引入

  • 并发、共享及多道程序环境
  • 基于程序的概念已不能完整、有效地描述并发程序在内存中的运行状态
  • 必须建立并发程序的新的描述和控制机制
  • 基于程序段、数据段和进程控制块而引入进程的概念以对应程序的运行过程
  • 进程控制块存放了进程标识符、进程运行的当前状态、程序和数据的地址以及关于该程序运行时的CPU环境信息

进程的定义

  1. 进程是可并发执行的程序在一个数据集合上的运行过程，亦即进程实体的运行过程
    进程实体由程序段、数据段及进程控制块三部分构成
  2. 进程是系统进行资源分配和调度的一个独立单位

进程的特征—-与程序的区别与联系

  1. 结构特征

    程序段、数据段及进程控制块

  2. 动态性

    生命周期及“执行”本质

  3. 并发性

    共存于内存、宏观同时运行

  4. 独立性

    调度、资源分配、运行

  5. 异步性

    推进相互独立、速度不可预知

进程并发制约关系及临界区

并发进程间制约关系

资源共享关系—-间接制约

  • 多个进程彼此无关，完全不知道或只能间接感知其它进程的存在
  • 系统须保证诸进程能互斥地访问临界资源
  • 系统资源应统一分配，而不允许用户进程直接用

相互合作关系—-直接制约
系统应保证相互合作的诸进程在执行次序上的协调和防止与时间有关的差错

临界资源

一段时间内只允许一个进程访问的资源。如 许多物理设备、变量及表格

临界区

每个进程中访问临界资源的那段代码称为临界区
保证诸进程互斥地进入自己的临界区是实现它们对临界资源的互斥访问的充要条件（同一个临界资源）

进程同步机制基本准则

  1. 空闲让进

    当无进程处于临界区时，可允许一个请求进入临界区的进程立即进入自己的临界区

  2. 忙则等待

    当已有进程进入自己的临界区时，所有企图进入临界区的进程必须等待

  3. 有限等待

    对要求访问临界资源的进程，应保证该进程能在有限时间内进入自己的临界区

  4. 让权等待

    当进程不能进入自己的临界区时，应释放处理机

进程互斥访问临界资源的软件解决方案

进程互斥算法1-设置访问编号

1
2
3
4
5
6
7
8
9
Var turn：integer：=i；[全局变量]

Pi：while turn!=i

		do no_op;

		临界区

		turn:=j;

强制设置进程访问，违背了空闲让进

进不了临界区也没有让出处理器资源，违背了让权等待

进程互斥算法2-设置访问标志

1
2
3
4
5
6
7
8
9
10
11
Var flagi,flagj:boolean:=false,false;[全局变量]

Pi：while flagj

		do no_op;

		flagi:=true;

		临界区

		flagi:=false;

违背了忙则等待和让权等待

进程互斥算法3-设置欲访问标志

1
2
3
4
5
6
7
8
9
10
11
Var flagi,flagj:boolean:=false,false;[全局变量] 

Pi：flagi:=true;

		while flagj

		do no_op;

		临界区

		flagi:=false;

违背了空闲让进、有限等待和让权等待

进程互斥算法4-编号+标志（Peterson算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
Var flagi,flagj:boolean:=false,false;[全局变量] 

	turn：integer；

Pi：flagi：=true；trun:=j;

		while(flagj and turn==j)

		do no_op;

		临界区

		flagi:=false;

违背了让权等待

整型信号量机制

整型信号量s（计算机资源可用的数量）除初始化外，仅能被两个标准的原子操作wait(s)和signal(s)亦即P/V操作来访问。

1
2
3
wait(s)：while s<=0 do no_op;
			    s:=s-1;
signal(s):s:=s+1;

违背了让权等待

记录型信号量机制

信号量类型声明

1
2
3
4
type semphore=record//信号量
	value:integer;//>=0表示对该信号量的可用资源数量，<=0其绝对值表示阻塞队列的长度，即有多少个进程正在等待资源
	L:list of process;//当前等待使用资源的进程列表或者队列
end

wait（s）操作描述

1
2
3
4
5
6
procedure wait(s)
Var s:semphore;
begin
	s.value:=s.value -1;
	if s.value<0 then block(s.L);//<0表示已经没有资源了，无资源则将该进程挂到阻塞队列
end

signal（s）操作描述

1
2
3
4
5
6
procedure signal(s)
Var s:semphore;
begin
	s.value:=s.value 1;
	if s.value<=0 then wakeup(s.L);//=0表示阻塞队列长度为|-1|，则需要唤醒被阻塞进程
end

AND型信号量集机制

引入

对于多个进程要共享两个以上的资源的情况，记录型信号量机制侧可能由于使用不当而导致死锁的发生

对于临界资源的互斥信号量的初始值为1

对策

若干个临界资源的分配采取原子操作方式

Swait（s1，s2，…，sn）操作

1
2
3
4
5
6
7
8
procedure Swait(s1,s2,...sn)
Var s1,s2,...,sn:semphore;
begin
	if s1.value≥1 and..and s.value≥1
	then for i:=1 to n do
		si.value:=s .value -1;
	else blockProcessAndResetPC(sfirstless);//挂到第一个不能满足的信号量阻塞队列上，资源重新做申请操作
end

Swait详细

1
2
3
4
5
6
7
8
9
10
11
12
13
begin
    Var zSbG:boolean:=false;
    for i:=1 to n do
    {if (si.value <1)
    	{zSbG:=true;break;}
    }
    if (zSbG)
    {ResetPC();
    block(si.L);}
    else
    {for i:=1 to n do
    si.value:=si.value -1;}
end

Ssignal（s1，s2，…，sn）操作

1
2
3
4
5
6
7
8
procedure Ssignal(s1,s2,...,sn)
Var s1,s2,...,sn semphore;
begin
	for i:=1 to n do
		si.value:=si.value＋1;
		wakeup(si.L);
	endfor;
end

一般信号量集机制

引入

  • 记录型信号量及AND信号量集机制中，wait(s)和signal(s)操作仅能对信号量施以增1和减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需d个某类临界资源时，便需要进行d次wait(s)操作，这显然是低效的。
  • 此外，在有些情况下，要求当资源数量低于某一下限值时，便不予分配。故在每次分配之前，都必须测试该资源的数量是否不小于测试值t。
  • 基于以上两点可以对AND信号量集机制进行扩充，形成一般化的“信号量集”机制。

Swait（s1，t1，d1，…，sn，tn，dn）操作

1
2
3
4
5
6
7
8
9
procedure Swait(s1,t1,d1,...,sn,tn,dn)
Var s1,s2,...,sn:semphore;//信号量
	t,t2,…,tnd,d2,…,dn:integer;//d为申请多少资源，t为下限值
begin
	ifs.value≥tand.…and sn.value≥tn
	then for i:=1 to n do
		si.value:=si.value -di;
	else blockProcessAndResetPC(sfirstless);
end

Swait详细

1
2
3
4
5
6
7
8
9
10
11
12
13
begin
Var zSbG:boolean:=false;
for i:=1 to n do
{if (si.value <t
	{zSbG:=true;break;}
}
if (zSbG)
{ResetPC();
block(si.L);}
else
{for i:=1 to n do
	si.value:=si.value di;}
end

Ssignal（s1，d1，…，sn，dn）操作

1
2
3
4
5
6
7
8
9
procedure Ssignal(s1,d1,...sn,dn)
Var s1,s2,...,s:semphore;
	d1,d2,…,dn:integer;,
begin
	for i:=1 to n do
		si.value:=si.value d;
		wakeup(si.L);
	endfor;
end

一般信号量集的几种特殊情况

Swait(s,d,d)

信号量集中只有一个信号量，但它允许每次申请d个资源；当现有资源少于d个时，便不予分配

Swait(s,1,1)

此时的信号量集已退化为一般的记录型信号量

Swait(s,1,0)
  • 一种特殊且很有用的信号量，相当于可控开关
  • 当s≥1时，允许多个进程进入某特定区；当s变为0后，将阻止任何进程进入该特定区

基于信号量机制解决进程并发问题的应用基础

利用信号量实现互斥—-主程序

1
2
3
4
5
6
7
Var mutex:semphore:=1;//互斥信号量，且初始值必须为1
begin
	parbegin//表示process1和process2可以并发执行
		processl;
		process2;
	parend
end

利用信号量实现互斥—-子程序

1
2
3
4
5
6
7
8
process1:
begin
	repeat
		wait(mutex);
		临界区
		signal(mutex);
	until false;
end

生产者-消费者问题

问题背景

  1. 生产者一消费者问题是相互合作进程关系的一种抽象

    • 输入时的输入进程与计算进程
    • 输出时的计算进程与输出进程

  2. 生产者一消费者问题具有很大的代表性和实用价值

    计算机系统一IPO系统

问题描述

  • 一群生产者进程在生产数据，并将此数据提供给一群消费者进程去消费处理
  • 为使二者可以并发执行，在它们之间设置了一个具有n个缓冲区的循环缓冲，生产者进程可以将它所生产的数据放入一个缓冲区中，消费者进程可以从一个缓冲区中取得一个数据消费
  • 异步运行方式及彼此必须保持同步

问题剖析

空缓冲区和满缓冲区
  • 空缓冲区是指未投放数据或虽曾投放数据但对应数据已被取走的缓冲区
  • 满缓冲区则指已投放数据且对应数据尚未被取走的缓冲区
进程同步
  • 当生产者进程要把所生产的数据送入循环缓冲时，首先应检查是否有空缓冲区存在，若有，则可向对应空缓冲区中投放数据，同时通知逍费者进程；否则只有等待。
  • 当消费者进程要从循环缓冲中提取数据时，首先应检查是否有满缓冲区存在，若有，则从对应满缓冲区中提取数据，并通知生产者进程，否则只有等待
进程互斥

缓冲区及其“指针”是临界资源：多个生产者/消费者进程

程序变量设计

循环缓冲表示机制

一维数组ouffer::array[0.n-l]of item;

输入指针in
  • 指示下一个可以投放数据的缓冲区
  • 初始值为0；变化方式：in:=(in+1) mod n
输出指针out
  • 指示下一个可以获取数据的缓冲区
  • 初始值为0；变化方式：out:=(out+1) mod n
暂存数据

nextp/nextc暂存每次要生产或消费的数据

程序信号量的设计

循环缓冲（缓冲区及其指针）的互斥使用

互斥信号量mutex,初始值为1

资源信号量
  • empty表示循环缓冲中的空缓冲区的数量其初始值为n
  • full表示循环缓冲中的满缓冲区的数量，其初始值为0

主程序设计

1
2
3
4
5
6
7
8
9
Var buffer:array [0..n-1]of item;//循环缓冲
	in,out:integer :0,0;//输入输出指针
	mutex,empty,full semphore :=1,n,0
begin
	parbegin
		producer1;..produceri;...producerY;
		consumer1;..consumerj;...;consumerX；
	parend
end

生产者子程序设计

1
2
3
4
5
6
7
8
9
10
11
12
produceri;:
Var nextp:item;
	begin
		repeat
			produce an item in nextp;
			wait(empty);
			wait(mutex);
			buffer[in]:=nextp;in :=(in+1)mod n;
			signal(mutex);
			signal(full);
		until false;
	end

消费者子程序设计

1
2
3
4
5
6
7
8
9
10
11
12
consumerj:
Var nextc:item;
	begin
		repeat
			wait(full);
        	wait(mutex);
			nextc:=buffer[out];out:=(out+1)mod n
			signal(mutex);
			signal(empty);
			consume.the item in nextc;
		until false;
	end

初步解决方案的反思

关于相邻wait（signal）操作颠倒的分析

在生产者一消费者问题中，如果将两个wait操作即wait(full)和wait(nutex)互换位置；或者是将signal((mutex)与signal(full)互换位置，结果会如何？

  1. wait(full)和wait(mutex)互换位置

    • 消费者wait(mutex)=>wait(full)

    • 生产者wait(empty)=>wait(mutex)

    • 时间节点：循环缓冲均为空缓冲区时

    • 陷入死锁

  2. signal(mutex)与signal(full)互换位置

    没有影响

关于signal操作缺失的分析

在生产者一消费者问题中，如果缺少了signal(full)或signal(empty),对执行结果会有何影响？

  1. 缺少了signal（full）
    • 生产者：开始—>生产者生产数据填满n个缓冲区时—->陷入死锁
    • 消费者：等待full信号量—->陷入死锁
  2. 缺少了signal（empty）
    • 生产者：等待empty信号量—->陷入死锁
    • 消费者：开始—->消费者取走了n个缓冲区数据时—->陷入死锁

基于AND信号量的生产/消费者子程序设计

生产者子程序
1
2
3
4
5
6
7
8
9
10
produceri;:
Var nextp:item;
	begin
		repeat
			produce an item in nextp;
			Swait(empty,mutex);
			buffer[in]:=nextp;in :=(in+1)mod n;
			Ssignal(mutex,full);
		until false;
	end
消费者子程序
1
2
3
4
5
6
7
8
9
10
consumerj:
Var nextc:item;
	begin
		repeat
			Swait(full,mutex);
			nextc:=buffer[out];out:=(out+1)mod n
			Ssignal(mutex,empty);
			consume.the item in nextc;
		until false;
	end

同步问题程序设计要领

  • 每个并发子程序关于互斥信号量的wait与signal操作必须在同一子程序中成对出现
  • 关于资源信号量的wait与signal操作同样需成对出现，但可以分别处于不同的并发子程序中
  • 每个并发子程序中的多个wait操作的顺序不能颠倒，即资源信号量wait操作执行在前而互斥信号量wait操作执行在后，否则可能引起死锁
  • 每个并发子程序中的多个signal操作的执行顺序无关紧要
  • 非临界资源访问操作无需放到临界区中，且最好放到临界区外

ZGS版

主程序设计
1
2
3
4
5
6
7
8
9
Var buffer:array [0..n-1]of item;
	in,out:integer :=0,0;
	mutexP,mutexC,empty,full semphore :=1,1,n,0；
begin
	parbegin
		producer;..produceri;...producery;
		consumer;...consumerj;...;consumerx;
	parend
end
生产者子程序设计ZGS版
1
2
3
4
5
6
7
8
9
10
11
12
produceri:
Var nextp:item;
	begin
		repeat
			produce an item in nextp;
			wait(empty);
			wait(mutexP);
			buffer[in]:=nextp;in :=(in+1)mod n;
			signal(mutexP);
			signal(full);
		until false;
	end
消费者子程序设计ZGS版
1
2
3
4
5
6
7
8
9
10
11
12
consumerj:
Var nextc:item;
	begin
		repeat
			wait(full);
			wait(mutexC);
			nextc:=buffer[out];out :=(out+1) mod n;
			signal(mutexC);
			signal(empty);
			consume the item in nextc;
		until false;
	end

哲学家进餐

问题描述

哲学家进餐问题是典型的同步问题

  • 五个哲学家共用一张圆桌，分别坐在环桌均匀摆放的五张椅子上，并全部实践着交替地进行思考和进餐的生活方式
  • 圆桌上放有五支筷子，均匀排放在哲学家之间的位置上
  • 哲学家饥饿时便试图去取用圆桌上最靠近他左右两端的两支筷子，且只有在同时拿到两支筷子时方可进餐，进餐完毕则把筷子放回原处，并继续进行思考

问题解析

  1. 筷子是临界资源
    信号量数组chopstick[0..4],初始值均为1

  2. 第i个哲学家活动

    1
    2
    3
    4
    5
    6
    Think;
    wait(chopstick[i]);
    wait(chopstick[(i+1)mod 5])
    Eat;
    signal(chopstick[i]);
    signal(chopstick[(i+1)mod 5]);

  3. 上述解决方案在五个哲学家同时饥饿且各自拿起左边筷子的情况下会引起死锁

  4. 避免死锁的三种方法

    • 仅当哲学家左右两支筷子均可使用时，才允许他拿筷进餐
    • 奇数号哲学家先拿左筷后拿右筷；而偶数号哲学家则相反
    • 至多允许四个哲学家同时进餐，以保证至少有一个哲学家可以同时拿到两支筷子而进餐

双筷齐举[AND型信号量]

主程序设计
1
2
3
4
5
6
7
8
9
Var
chopstick:array[0..4]of semphore:=(1,1,1,1,1)
begin
	parbegin
		philosophy0;
		…;philosophyi;…
		philosophya;
	parend
end
子程序设计
1
2
3
4
5
6
7
8
9
philosophyi:
begin
	repeat
		Think;
		Swait(chopstick[i],chopstick[(i+1)mod 5]);
		Eat;
		Ssignal(chopstick[i],chopstick[(i+1)mod 5]);
	until false;
end

双筷齐举[记录型信号量]

主程序设计
1
2
3
4
5
6
7
8
9
10
Var
chopstick:array[0..4]of semphore:=(1,1,1,1,1)
mutex:semphore:=1;
begin
	parbegin
		philosophy0;
		…;philosophyi;…
		philosophya;
	parend
end
子程序设计
1
2
3
4
5
6
7
8
9
10
11
12
13
philosophyi:
begin
	repeat
		Think;
		wait(mutex);
		wait(chopstick[i]);
		wait(chopstick[(i+1)mod 5]);
		signal(mutex);
		Eat;
		signal(chopstick[i]);
		signal(chopstick[(i+1)mod 5]);
	until false;
end

奇偶有别[记录型信号量]

主程序设计
1
2
3
4
5
6
7
8
9
Var
chopstick:array[0..4]of semphore:=(1,1,1,1,1)
begin
	parbegin
		philosophy0;
		…;philosophyi;…
		philosophya;
	parend
end
子程序设计[奇数]
1
2
3
4
5
6
7
8
9
10
11
philosophyi（i为奇数，即奇数号哲学家）：
begin
	repeat
		Think;
		wait(chopstick[i]);
		wait(chopstick[(i+1)mod 5]);
		Eat;
		signal(chopstick[i]);
		signal(chopstick[(i+1)mod 5]);
	until false;
end
子程序设计[偶数]
1
2
3
4
5
6
7
8
9
10
11
philosophyi（i为偶数，即偶数号哲学家）：
begin
	repeat
		Think;
		wait(chopstick[(i+1)mod 5]);
		wait(chopstick[i]);
		Eat;
		signal(chopstick[(i+1)mod 5]);
		signal(chopstick[i]);
	until false;
end

进餐限数[记录型信号量]

主程序设计
1
2
3
4
5
6
7
8
9
10
Var
chopstick:array[0..4]of semphore:=(1,1,1,1,1);
limit:semphore:=4;
begin
	parbegin
		philosophy0;
		…;philosophyi;…
		philosophya;
	parend
end
子程序设计
1
2
3
4
5
6
7
8
9
10
11
12
13
philosophyi:
begin
	repeat
		Think;
		wait(limit);
		wait(chopstick[i]);
		wait(chopstick[(i+1)mod 5]);
		signal(limit);
		Eat;
		signal(chopstick[i]);
		signal(chopstick[(i+1)mod 5]);
	until false;
end

读者-写者

问题描述

  1. 读者一写者问题是指保证任何写者进程必须与其它进程互斥地访问共享数据对象（数据文件或记录)的同步问题。
    • 存在多个进程共享一个数据对象
    • 只要求读的进程称为读者进程
    • 拥有写或修改要求的进程称为写者进程
    • 允许多个读者进程同时执行读操作
    • 任何写者进程的执行具有排它性
  2. 读者一写者问题常用于测试新同步原语

程序信号量及变量设计

  1. 写者进程与其它进程的互斥执行

    写互斥信号量wmutex,初始值为1

  2. 读者进程之间的并发执行

    读者进程计数变量readercount,表示正在执行的读者进程数量，其初始值为0

  3. 读者进程计数变量的互斥访问

    readercounti对于多个读者进程而言是临界资源，应为之设置读互斥信号量rmutex,其初始值为1

主程序设计

1
2
3
4
5
6
7
8
Var readercount:integer 0;
	rmutex,wmutex:semphore :=1,1;
begin
	parbegin
		reader;...;readeri ;...readerm;
		writer;..;writerj;..;writern;
	parend
end

写者子程序设计

1
2
3
4
5
6
7
8
writerj:
	begin
		repeat
			wait(wmutex);
			Perform write operation;
			signal(wmutex);
		until false;
	end

读者子程序设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
readeri:
	begin
		repeat
			wait(rmutex);
			if readercount=0 then wait(wmutex);
			readercount:=readercount +1;
			signal(rmutex);
			Perform read operation;
			wait(rmutex);
			readercount:=readercount -1;
			if readercount=0 then signal(wmutex)
			signal(rmutex);
		until false:
	end

反思

  1. 如果读者到来
    • 若为第一个读者：若无写者写，则开始读；否则插入wmutex队列等待
    • 若非第一个读者：若前有读者在读（无论是否有写者已在等待)，新读者均开始读：否则插入rmutex队列[前面读者在等]等待
  2. 如果写者到来
    • 无写者写且无读者读，则新写者开始写
    • 有写者写或有读者读，则插入wmutex队列等待

消除读者优先

  1. 一旦有写者到达，则后续的读者必须等待（无论当时是否有读者在读）
  2. 如果读者到来
    • 有写者写或有写者等，则新读者等待
    • 无写者写且无写者等，则新读者可读
  3. 如果写者到来
    • 无读者读且无写者写，则新写者可写
    • 有读者读或有写者写，则新写者等待

公平型读者-写者

主程序设计
1
2
3
4
5
6
7
8
Var readercount:integer 0;
	S,rmutex,wmutex:semphore :=1,1,1;
begin
	parbegin
		reader;...;readeri ;...readerm;
		writer;..;writerj;..;writern;
	parend
end
读者子程序设计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
readeri:
	begin
		repeat
			wait(S);
			wait(rmutex);
			if readercount=0 then wait(wmutex);
			readercount:=readercount +1;
			signal(rmutex);
			signal(S);
			Perform read operation;
			wait(rmutex);
			readercount:=readercount -1;
			if readercount=0 then signal(wmutex)
			signal(rmutex);
		until false:
	end
写者子程序设计
1
2
3
4
5
6
7
8
9
10
writerj:
	begin
		repeat
			wait(S)；
			wait(wmutex);
			Signal(S);
			Perform write operation;
			signal(wmutex);
		until false;
	end

存储器管理

程序的执行首先要加载装入到内存，然后程序的运行从内存提取加载到CPU执行，重点如何把程序里的地址转化成内存的物理单元的物理地址

用户程序处理过程

源程序（符号名空间）

编译程序

目标模块（目标/相对地址空间）

链接程序

装入模块（统一的目标地址空间）

装入程序

内存（物理地址空间）

程序处理与内存管理

程序地址空间及形成

  • 目标模块（由编译/汇编得到）：相对地址
  • 链接过程实现各目标模块相对地址的统一

内存管理逻辑部件

  • MMU负责将逻辑地址转换为物理地址
  • X86体系结构MMU支持分页和分段机制

内存管理模式

实模式和保护模式

操作系统概论

导论

INTERFACE（接口、界面、介面）

接口是连接两个物体的边界，通过这个界面，两边可以很好地对话

  • 硬件-硬件：USB、VGA、HDML、
  • 软件-硬件：指令集
  • 软件-软件：Application Programming Interface（API）

VIRTUAL MACHINE

操作系统向用户提供一个容易理解和使用的“计算机”（虚拟的)，用户对这个“计算机”的操作都将被操作系统转成对计算机硬件的操作

操作系统功能

用户角度
  • 提供良好的用户界面
  • 标准的函数库
  • 使得编程更加方便并且不
    容易出错
系统角度
  • 管理资源
    • 硬件资源（处理机，存储器，设备)
    • 信息资源（文件）
  • 解决申请资源时产生的冲突
  • 阻止错误的产生和对计算机不正当的使用

操作系统的定义

  1. 操作系统在用户和计算机硬件之间扮演了中间人的角色
  2. 操作系统的目标是为提供一个方便高效执行代码的环境
  3. 操作系统是管理计算机硬件的软件

计算机系统的组成

  • memory
  • CPU
  • disk controller->disks
  • mouse、keyboard、printer、monitor->USB controller
  • monitor->graphics adapter(显示适配器)->显卡
  • Bus
主引导扇区（BOOT SECTOR）
  1. 硬盘的0柱面、0磁头、1扇区称为主引导扇区，在这扇区里存放着一段代码：主引导记录MBR(Main Boot Record),它用于硬盘启动时将系统控制权转给用户指定的、在分区表中登记了某个操作系统分区
  2. MBR的内容是在硬盘分区时由分区软件写入该扇区的，MBR不属于任何一个操作系统，不随操作系统的不同而不同，即使不同，MBR也不会夹带操作系统的性质，具有公共引导的特性
BOOTSTRAP->OS自己把自己拉启动

Pull oneself up by one’s bootstraps.

BOOTSTRAP OF COMPUTER
  • 打开电源
  • CPU将控制权交给BIOS（基本输入输出系统，存放在CMOS中)
  • BIOS运行一个程序：通电自测试程序
  • BIOS确认所有外部设备：硬盘或扩充卡
  • BIOS找到磁盘的引导区，将其中的主引导程序bootloader装入内存。（主引导程序是一段代码，它可以将OS余下部分装入内存)
  • 引导操作系统结束，操作系统接管计算机
  • 操作系统等待事件发生…
中断
  • 当有事件（Event)发生时，CPU会收到一个中断(Interrupt)信号，可以是硬中断也可以是软件中断。
  • CPU会停下正在做的事，转而执行中断处理程序执行完毕会回到之前被中断的地方继续执行。
  • 操作系统是一个以中断驱动的系统
STORAGE SYSTEM(存储系统)
  1. CPU负责将指令(Instruction)从内存（Memory)读入，所以程序必须在内存中才能运行。
  2. 内存以字节为存储单位，每个字节都有一个地址与之对应。通过load/store:指令即可访问指定地址的内存数据
    • load:将内存数据装入寄存器(Register)
    • store:将寄存器数据写入内存
I/O结构
  • 存储器只是众多IO设备中的一种，IO设备是计算机体系结构中种类最丰富的设备类型，而且他有着很强的扩展性。
  • 管理IO设备是操作系统非常重要的组成部分，操作系统中有一个专门的O子系统负责完成这项工作。

计算机体系结构

单处理器系统
  • Single-processor System
  • 只有一颗主CPU,执行通用指令集。
  • 带有其他专用处理器，为特定设备服务，如：磁盘、键盘、图形控制器等。
    • 它们能够执行的指令有限，不处理用户进程
    • 操作系统会向它们发出任务，并监控它们的状态
多处理器系统
  • Multiprocessor/Multicore System
  • 有两个或多个紧密通信的CPU,它们共享计算机总线、时钟、内存和外设等。
    • 非对称处理(Asymmetric multiprocessing)
      对称处理(Symmetric MuliProcessing)
集群系统
  • Clustered System
  • 该系统由若干节点（node)通过网络连接在一起每个节点可为单处理器系统或多处理器系统，节点之间是松耦合(loosely coupled)关系。
    • 高可用性(high availability)
    • 高性能计算(high-performance computing)

操作系统结构

单用户单模式

输入500个字符（花78ms),经CPU处理52ms后，将结果2000个字符存到磁带上（花20ms),重复进行。CPU利用率=52/(78+52+20)≈35%

多道程序设计
  • 操作系统最重要的一点是具有多道程序(multiprogramming)能力。
  • 单道程序不能让CPU和IO设备始终忙碌，多道程序设计通过安排任务使用得CPU总有一个执行任务，从而提高CPU利用率。
  • 实现的硬件保证：处理器和IO设备具备并行工作的能力
分时系统
  • 分时系统（time sharing)也称多任务系统(multi-tasking)，是多道程序设计的自然延伸。
  • 允许多个用户共享一台计算机
    • 用户只有输入和输出设备
    • 分时系统为每个用户轮流分配等量的CPU时间
    • 用户从发出指令到得到即时结果的时间称为响应时间
  • 第一个分时系统CTSS由MIT于1962年开发出来
引发的其他模式
  • 处理器调度（CPU Scheduling)
  • 交换(Swapping）
  • 虚拟内存(Virtual Memory)
  • 磁盘管理（Disk Management）
  • 同步(Synchronization)
  • 死锁(Deadlock)

操作系统提供的服务

USER INTERFACE

Almost all operating system have a user interface(UI).It offers a way for users to interface（交互） with OS.

CLI（Command Line Interface）（命令行）

command interpreter(shell)命令解释器

GUI(Graphic User Interface)

A user friendly graphical user interface.

Batch(批处理)
  • It is a file which contains commands and directives.
  • Demonstration …

系统调用（SYSTEM CALLS）

  1. 系统调用提供了访问和使用操作系统所提供的服务的接口
    • 系统调用的实现代码是操作系统级的
    • 这个接口通常是面向程序员的
  2. API(Application Programming Interface)):指明了参数和返回值的一组函数。
    • 应用程序App的开发人员通过透过API间接访问了系统调用
    • Windows API POSIX API JAVA API
实现机制
  • 每个系统调用都有一个唯一的数字编号，被称为系统调用
  • 用户代码调用API时，API中会向系统调用接口指明其所要用的系统调用号，操作系统内核中维护了一张索引表，依据这个调用号可以检索到访系统调用代码在内核中的位置。

双重模式（DUAL MODE）

  1. 现代计算机系统有一个特殊的硬件，用于划分系统的运行状态，至少需要两种单独运行模式：
    • 用户模式(user mode)：执行用户代码
    • 内核模式(kernel mode):执行操作系统代码
  2. 目的：确保操作系统正确的运行
  3. 实现方式：用一个硬件模式位来表示当前模式：0表示内核模式，1
    表示用户模式。

进程概念

程序和进程

  • A program is a passive entity,such as a file containing a list of instructions stored on disk(often called an executable file).
  • A program becomes a process when an executable file is loaded into memory.
  • A process is an active entity,with a program counter specifying the next instruction to execute an a set of associated resources

PROGRAM COUNTER

  • 程序计数器(PC)是一个CPU中的寄存器，里面存放下一条要执行指令的内存地址
    在Intel x86和Itanium微处理器中，它叫做指令指针（Instruction Pointer,IP），有时又称为指令地址寄存器(instruction address register,IAR)、指令计数器
  • 通常，CPU在取完一条指令之后会将PC寄存器的值加“1”，以计算下条要执行指令的地址。

PROCESS IN MEMORY

  • text：代码
  • data：全局和静态变量
  • stack：栈用于存放局部变量、函数返回地址
  • heap：堆用于程序运行时的动态内存分配

并发的进程

  • Concurrency:the fact of two or more events or circumstances happening（存在） or existing at the same time.
  • 并行：running at the same time
  • 并发进程可能无法一次性执行完毕，会走走停停。
  • 一个进程在执行过程中可能会被另一个进程替换占有CPU,这个过程称作“进程切换”

进程的定义

  1. 进程是一个程序的一次执行过程
    • 能够具体完成的
    • 是在某个数据集合上完成的
    • 执行过程是可并发的
  2. 进程是资源分配、保护和调度的基本单位

进程状态（PROCESS STATE）

进程在执行期间自身的状态会发生变化，进程有三种基本状态，分别是：

  1. 运行态(Running)：此时进程的代码在CPU上运行
  2. 就绪态(Ready):进程具备运行条件，等待分配CPU
  3. 等待态(Waiting)：进程在等待某些事件的发生（比如IO操作结束或是一个信号)

进程何时离开CPU

  1. 内部事件
    • 进程主动放弃（yield）CPU，进入等待/终止状态
    • 例如使用I/O设备，（非）正常结束如除以0
  2. 外部事件
    • 进程被剥夺CPU使用权，进入就绪状态。这个动作叫抢占(preempt)。
    • 例如时间片到达，高优先权进程到达。

进程切换和进程调度

进程切换

并发进程中，一个进程在执行过程中可能会被另一个进程替换占有CPU,这个过程称作“进程切换”。

中断技术（Interrupt）

中断是指程序执行过程中

  • 当发生某个事件时，中止CPU上现行程序的运行
  • 引出该事件的处理程序执行
  • 执行完毕返回源程序中断点继续执行

中断源

外中断（interrupt）

来自处理器之外的硬件中断信号

  • 如时钟中断、键盘中断、外围设备中断
  • 外部中断均是异步中断
内中断（异常Exception）

来自于处理器内部，指令执行过程中发生的中断，属同步中断

  • 硬件异常：掉电、奇偶校验错误等
  • 程序异常：非法操作、地址越界、断点、除数为0
  • 系统调用

特权指令和非特权指令

特权指令

只能在内核态运行的指令

  • I/O指令和停止整个系统指令
  • 关闭所有中断
  • 设置定时器
  • 进程切换
非特权指令

只能运行在用户态

模式切换

  • 中断是用户态向核心态转换的唯一途径！系统调用实质上也是一种中断
  • OS提供LoadPSW指令装载用户进程返回用户状态

进程切换

切换时机
  • 进程需要进入等待状态
  • 进程被抢占CPU而进入就绪状态
切换过程
  • CPU从用户态切换到核心态
  • 保存被中断进程的上下文信息（Context）
  • 修改被中断进程的控制信息（如状态等）
  • 将被中断的进程加入相应的状态队列
  • 调度一个新的进程并恢复它的上下文信息

进程的上下文包含了进程在内存中的text、data、heap、stack和PCB

运行实体：text、data、heap、stack

进程控制块

PCB包含了一个指定进程的许多信息，包括如下

  • 进程状态
  • 进程编号PID
  • PC值
  • 寄存器的值
  • 内存信息
  • 打开的文件

进程调度（PROCESS SCHEDULING）

进程在整个生命周期中会在各个调度队列中迁移，由操作系统的一个调度器（scheduler）来执行。

fork（）函数

用于创建一个新进程，该进程为当前进程的子进程，创建的方法：fork（）；

父进程在执行了fork后，将当前进程在内存中的所有数据原模原样复制一份，从fork（）开始并发执行fork（）之后的所有代码

fork（）的返回值：

  • 如果成功创建子进程，对于父子进程fork会返回不同的值，
  • 对于父进程它的返回值是子进程的进程id值
  • 对于子进程它的返回值是0
  • 如果创建失败，返回值为-1

线程

定义

进程中的执行流

  • A thread is a basic unit of CPU utilization(利用）;it comprises a thread id,a program counter,a register set,and a stack
  • It shares with other threads belonging to the same process its code section,data section,and other operating-system resources,such as open files and signals（共享）
  • A traditional (or heavyweight（重量级）)process has a single thread of control,If a process has multiple threads（lightweight轻量级 ）of control,it can perform more than one task at a time.

采用多线程的优点

  • 响应性
  • 资源共享
  • 经济
  • 可伸缩性

多核编程

在多处理器系统中，多核编程机制让应用程序可以更有效地将自身的多个执行任务（并发的线程）分散到不同的处理器上运行，以实现并行计算

多线程模型

  • 用户线程ULT(User Level Thread)

    ULT在user mode下运行，它的管理无需内核支持。

  • 内核线程KLT(Kernel Level Thread)
    KLT在kernel mode下运行，由操作系统支持与管理。

处理器调度

基本概念

  • 多道程序设计的目的将CPU的利用率最大化。
  • 多个进程同时存在于内存(并发)，当一个进程暂不使用CPU时，系统调度另一个进程占用CPU。

CPU调度程序

Whenever the CPU becomes idle（空闲）,the operating system must select one of the processes in the ready queue to be executed.The selection process is carried out by the CPU scheduler.

抢占调度

非抢占调度（Nonpreemptive scheduling）

一旦某个进程得到CPU,就会一直占用到终止或等待状态。

抢占调度(Preemptive scheduling)

调度算法性能的衡量

  • CPU利用率：CPU的忙碌程度
  • 响应时间：从提交任务到第一次响应的时间（针对交互式系统）
  • 等待时间：进程累积在就绪队列中等待的时间
  • 周转时间：从提交到完成的时间
  • 吞吐率：每个时钟单位处理的任务数
  • 公平性：以合理的方式让各个进程共享CPU

调度性能指标

  • 作业（job）=进程(process）
  • 假设作业提交给系统的时刻是ts,完成的时刻是tf,所需运行时间为tk,那么：
  • 平均作业周转时间T(ti是单个作业的周转时间)
  • T=求和ti（i=1…n）×1/n（ti=tf-ts）

调度算法

先来先服务（FCFS/FIFO）

  • First-Come,First-Served(FCFS)

    • 早期系统里，FCFS意味着一个程序会一直运行到结束（尽管其中会出现等待I/O的情况)
    • 如今，当一个程序阻塞时会让出CPU

  • 例题

    process Time
    P1 28
    P2 9
    P3 3

    如果三个进程的到达顺序是：P1,P2,P3

  • 等待时间分别是：P1=0;P2=28;P3=37

  • 平均等待时间是：(0+28+37)/3=22

  • 平均作业周转时间是：(28+37+40)/3=35

先来先服务（续）

如果换一种执行顺序的话：P3,P2,P1

  • 等待时间分别是：P1=12；P2=3;P3=0
  • 平均等待时间是：(12+3+0)/3
  • 平均周转时间是：(3+12+40)/3=18

第二种排列方式比第一种要好，平均周转时间缩短为18

先来先服务优缺点
  • 简单易行(+)
  • 如果短作业处在长作业的后面将导致周围时间变长（-）。
时间片轮转（ROUND ROBIN）

针对分时系统

  • 每个进程都可以得到相同的CPU时间(CPU时间片，time slice),当时间片到达，进程将被剥夺CPU并加入就绪队列的尾部

  • 抢占式调度算法P

  • n个就绪队列中的进程和时间片q→

    • 每个进程获得1/n的CPU时间，大约是q个时间单位
    • 没有进程等待时间会超过(n-1)q

  • 例题（时间片=20）

    Process CPU Time
    P1 68
    P2 53
    P3 24
    P4 8

    • 等待时间分别是：

      P1=(68-20)+(112-88)+(145-32)=85
      P2=(20-0)+(88-40)+(132-108)=92
      P3=(40-0)+(108-60)=88
      P4=(60-0)=60

    • 平均等待时间=(85+92+88+60)/4=81.25

    • 平均周转时间=(153+145+112+68)/4=119.5

    • 如果采用FCFS算法，平均等待时间83.5，平均周转时间121.75

RR算法分析
  1. 时间片（time slice）取选
    • 取值太小：进程切换开销显著增大（不能小于进程切换的时间）
    • 取值较大：响应速度下降（取值无穷大将退化成FCFS)
    • 一般时间片的选取范围为10ms~100ms
    • 上下文切换的时间大概为0.1ms~1ms（1%的CPU时间开销)
  2. RR算法优缺点
    • 公平算法(+)
    • 对长作业带来额外的切换开销(-)
  3. RR不一定优于FCFS
最短作业优先（SJF）
  • SJF(Shortest Job First)):下一次调度总是选择所需要CPU时间最短的那个作业（进程)。
  • 抢占式SRTF
SJF/SRTF算法分析
  • 该算法总是将短进程移到长进程之前执行，因此平均等待时间最小，该算法被证明是最优的。
  • 饥饿现象：长进程可能长时间无法获得CPU
  • 预测技术
    • 该算法需要事先知道进程所需的CPU时间
    • 预测一个进程的CPU时间并非易事
  • 优缺点
    • 优化了响应时间(+)
    • 难以预测作业CPU时间(-)
    • 不公平算法(-)
优先级调度（PRIORITY）

优先级通常为固定区间的数字，如[0,10]：

  • 数字大小与优先级高低的关系在不同系统中实现不一样，以Linux为例，0为最高优先级。
  • 调度策略：下一次调度总是选择优先级最高的进程。
  • SJF是优先级调度的一个特例。
  • 优先级调度可以是抢占式，也可以是非抢占式。
优先级的定义

  1. 静态优先级

    优先级保持不变，但会出现不公平（饥饿）现象

  2. 动态优先级（退化Aging）

    • 根据进程占用CPU时间：当进程占有CPU时间愈长，则
      慢慢降低它的优先级；
    • 根据进程等待CPU时间：当进程在就绪队列中等待时间
      愈长，则慢慢提升它的优先级。

  3. 现代操作系统采用动静态结合的优先级

进程同步

并发进程/线程

在内存中同时存在的若干个进程/线程，由操作系统的调度程序采用适当的策略将他（们）调度至CPU(s)上运行，同时维护他们的状态队列。

  • 多个并发进程/线程从宏观上是同时在运行；
  • 从微观上看，他们的运行过程是走走停停：
  • 并发的进程/线程之间是交替执行(Interleaving)。

并发进程之间的关系

  1. 独立关系
    • 并发进程分别在自己的变量集合上运行
    • 例如：chrome进程和music进程
  2. 交互关系
    • 并发进程执行过程中需要共享或是交换数据
    • 例如：银行交易服务器上的receiver:进程和handler:进程
    • 交互的并发进程之间又存在着竞争和协作的关系

竞争（RACE）

协作（COOPERATION）

异步

  • Asynchronous means RANDOM!
  • 会引发竞争条件(Race Condition)：一种这样的情况：多个进程并发操作同一个数据导致执行结果依赖于特定的进程执行顺序。

同步

  • Process Synchronization means a mechanism（机制） to maintain（维护） the consistency（一致性） of data shared in cooperative processes.
  • Synchronization Tool Kits
    • Mutex lock(互斥锁)
    • Semaphore（信号量）

互斥锁

临界区问题（CRITICAL-SECTION PROBLEM）

  • Each concurrent(并发) process has a segment of code,called a critical section,in which the process may be changing common variables（公共数据）,updating a table,writing a file,and so on.
  • The important feature of the system is that,when one process is executing in its critical section,no other process is allowed to execute in its critical section.That is,NO two processes are executing in their critical sections at the same time.
  • The critical-section problem is to design a protocol（协议） that the processes can use to cooperate.

进程进出临界区协议

  • 进入临界区前在entry section要请求许可；
  • 离开临界区后在exit section要归还许可。

临界区管理准则

  • Mutual exclusion(Mutex):互斥
  • Progress:前进
  • Bounded waiting:有限等待

简而言之

  • 有空让进
  • 择一而入
  • 无空等待
  • 有限等待
  • 让权等待

软件解决临界区管理

  • 实现需要较高的编程技巧
  • 两个进程的实现代码是不对称的，当处理超过2个进程的时候，代码的复杂度会变得更大
  • 两个著名的软件方案
    • Peterson
    • Dekker

MUTEX LOCKS

Operating-systems designers build software tools to solve the critical-section problem.The simplest of these tools is the mutex lock.

  • A process must acquire the lock before entering a critical section;
  • It must release the lock when it exits the critical section.

锁的基本操作

  • 上锁
    • 等待锁至打开状态
    • 获取锁并锁上
  • 解锁
  • 原子操作

原子操作

  • Atomic operations mean the operation can NOT be interrupted while it’s running.
  • 原子操作（愿语）是操作系统重要的组成部分，下面2条硬件指令都是原子操作，它们可以被用来实现对临界区的管理（也就是“锁”)。
    • test_and _set()
    • compare_and_swap()

锁的实现

1
2
3
4
5
6
7
8
bool available = true;//unlocked
lock(){
	while(!ts(&available))
       do nothing;
}
unlock(){
	available = true;
}
1
2
3
4
5
6
原子操作
bool ts(bool *target){
	bool result =*target
	*target = false;
	return result;
}

忙式等待（BUSY WAITING）

  • 忙式等待是指占用CPU执行空循环实现等待
  • 这种类型的互斥锁也被称为“自旋锁”(spin lock)
    • 缺点：浪费CPU周期，可以将进程插入等待队列以让出CPU的使用权；
    • 优点：进程在等待时没有上下文切换，对于使用锁时间不长的进程，自旋锁还是可以接受的；在多处理器系统中，自旋锁的优势更加明显。

信号量

信号量的定义

  • 信号量(Semaphore)是一种比互斥锁更强大的同步工具，它可以提供更高级的方法来同步并发进程。
    • 1965年由荷兰学者Dijkstra提出
  • A semaphore S is an integer variable（整型变量） that,apart from initialization（初始化赋值）,is accessed only through two standard atomic operations:P(proberen in Dutch)（测试）and V(verhogen in Dutch)（增加）.
    • P：wait（）operation
    • V：signal（）operation

信号量的实现

1
2
3
4
5
6
7
8
P(s){
	while(s<=0)
		do nothing;
	S--;
}
V(s){
	S++;
}

信号量的使用

BINARY SEMAPHORE

顾名思义，二值信号量的值只能是0或1，通常将其初始化为1，用于实现互斥锁的功能。

1
2
3
4
5
6
semaphore mutex = 1;
process pi{
	P(mutex);
	critical section
	V(mutex);
}
COUNTING SEMAPHORE

一般信号量的取值可以是任意数值，用于控制并发进程对共享资源的访问。

1
2
3
4
5
6
7
semaphore road = 2;
process Cari{
	P(road);
	pass the fork
	in the road.
	V(road);
}

信号量初始值=0，用于进程同步

同步问题

  • 同步问题实质是将异步的并发进程按照某种顺序执行
  • 解决同步的本质就是要找到并发进程的交互点，利用P操作的等待特点来调节进程的执行速度；
  • 通常初始值为0的信号量可以让进程直接进行等待状态，直到另一个进程唤醒他。

经典同步问题

生产-消费者问题

生产者(P)与消费者(C)共用一个缓冲区，生产者不能往“满”的缓冲区中放产品，消费者不能从“空”的缓冲区中取产品。

单缓冲解决方案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Semaphore empty = 1;
//signal for producer
Semaphore full = 0;
//signal for consumer


Producer{
	while (true){
		make a product;
		P(empty);
		put the product into buffer;
		V(full);
	}
}

Consumer{
	while (true){
		P(full);
		pick product from buffer;
		V(empty);
		consume the product;
	}
}
有界缓冲区（THE BOUNDED-BUFFER PROBLEM）
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
item B[k];
semaphore empty = k;
semaphore full = 0;
int in = 0,out =0;
semaphore mutex = 1;

Process producer_i{
	make a product;
	P(empty);
	P(mutex);
	B[in] = product;
	in=（in+1)%k;
	V(mutex);
	V(full);
}

Process consumeri{
	P(full);
	P(mutex);
	product = B[out];
	out=（out+1)%k;
	V(mutex);
	V(empty);
	consume a product;
}

  1. 不要随意扩大临界区

  2. 同步信号量：empty和full的PV操作不在同一进程

    互斥信号量：mutex的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
semaphore sp = 1;/*盘子里允许放一个水果*/
semaphore sg1 = 0;/*盘子里没有桔子*/
semaphore sg2 = 0；/*盘子里没有苹果*/

Process father{
	削一个苹果；
	P(sp);
	把苹果放入plate;
	V(sg2);
}

Process daughter{
	P(sg2);
	从plate中取苹果；
	V(sp);
	吃苹果；
}

Process mother{
	剥一个桔子；
	P(sp)；
	把桔子放入plate；
	V(sg1);
}

Process son{
	P(sg1);
	从plate中取桔子；
	V(sp);
	吃桔子；
}

读者-写者问题（Reader，Writer）

Rules:
  1. R和W：竞争
  2. W和W：竞争
  3. R和R：共享/同时
解决方案
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
Semaphore rw=1;
int reader_count=0;//正在读文件的读者数量
Semaphore r_mutex=1;
Reader_i{
 while(1){
 	P(r_mutex);
 	reader_count++;
	if(reader_count==1){
		P(rw);
	}
	V(r_mutex);
	Read file;
	P(r_mutex);
	reader_count--;
	if(reader_count==0){
		V(rw);
	}
	V(r_mutex);
 }
}

Writer_i{
	P(rw);
	Write file;
	V(rw);
}

理发师问题

问题描述
  • 有一个睡觉的理发师等待顾客唤醒理发
  • 当顾客发现理发师在为其他顾客理发时就坐到椅子上等待
  • 当椅子上都坐满了（椅子的最大值为MAX_CHAIRS），前来理发的新顾客离开
解决方案
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
Semaphore customer=0;//理发师正在理发的顾客
Semaphore barber=1;//理发师目前是否可以理发
Semaphore mutex=1;//互斥信号量
int waiting=0;等待的顾客数量

Barber{
	P(customer);
	P(mutex);
	waiting--;
	V(mutex);
	cut hair;
	V(barber);
}

Customer_i{
	P(mutex);
	if(waiting<MAX_CHAIRS){
		waiting++;
		V(mutex);
		P(barber);
		V(customer);
		get haircut;
	}else{
		V(mutex);
		leaving;
	}
	
}

哲学家就餐问题

解决方案
1
2
3
4
5
6
7
8
9
10
11
12
Semaphore chopstick[5]={1};

Philosopher_i{
	while(1){
		Thinking;
		P(chopstick[i]);
		P(chopstick[(i+1)%5]);
		Eating;
		V(chopstick[i]);
		V(chopstick[(i+1)%5]);
	}
}

死锁

哲学家用餐死锁问题

  • 当所有人同时拿到一侧的筷子时，发生永远等待现象（即死锁）
  • 有若种办法可避免死锁：
    • 至多允许四个哲学家同时吃；
    • 奇数号先取左手边的筷子，偶数号先取右手边的筷子；
    • 每个哲学家取到手边的两根筷子才吃，否则一根也不取。
  • 进程访问资源流程：申请->使用->释放

DEADLOCK(定义)

  • In a multiprogramming environment,several processes may compete for a finite（有限的） number of resources.
  • A process requests resources;if the resources are not available at that time,the process enters a waiting state.
  • Sometimes,a waiting process is never again able to change state,because the resources it has requested are held（占有） by other waiting processes.
  • This situation is called a deadlock.

死锁与饥饿

  • 饥饿：进程长时间等待

    e.g.低优先级进程总是等待高优先级所占有的进程

  • 死锁：循环等待资源

    • A和B分别占有打印机和扫描仪
    • 同时分别申请扫描仪和打印机

  • 死锁=>饥饿（反之不亦然）

    • 饥饿可能终止
    • 如果无外部干涉，死锁无法终止

产生死锁的四个必要条件

死锁发生，以下四个条件同时成立

  • 互斥使用

    一个时刻，一个资源仅能被一个进程占有

  • 不可剥夺

    除了资源占有进程主动释放资源，其它进程都不可抢夺其资源

  • 占有和等待

    一个进程请求资源得不到满足等待时，不释放已占有资源

  • 循环等待（上面三个条件同时存在产生的结果）

    每一个进程分别等待它前一个进程所占有的资源

METHONDS FOR HANDLING DEADLOCKS

  • Deadlocks are NOT allowed to appear.We must prevent or avoid deadlock state.
  • Deadlocks are allowed to appear,but the system can detect（检测） them and recover.
  • We pretend that deadlocks never occur in the system.

死锁的解决方案

死锁的防止(Prevention)

破外四个必要条件之一

死锁的避免(Avoidance)

允许四个必要条件同时存在，在并发进程中做出妥善安排避免死锁的发生

死锁的检测和恢复（Detection&Recovery）

允许死锁的发生，系统及时地检测死锁并解除它

死锁的防止

破坏死锁任一必要条件（可操作性太复杂）

  • 互斥使用=>允许资源共享使用

    不可行

  • 不可剥夺=>资源可被抢夺

    不可行

  • 占有和等待

    可行

    缺点：资源浪费

  • 循环等待

    可行

    缺点：资源浪费

安全状态(SAFE STATE)

  • A state is safe if the system can allocate resources to each process (up to its maximum)in some order and still avoid a deadlock.More formally,a system is in a safe state only if there exists a safe sequence.
  • If no such sequence exists,then the system state is said to be unsafe.
  • A safe state is NOT a deadlocked state.
  • An unsafe state MAY lead to a deadlock.

死锁的避免

  • 系统对进程的每一次资源申请都进行详细的计算，根据结果决定是分配资源还是让其等待，确保系统始终处于安全状态，避免死锁的发生。
  • 银行家算法（Banker’s algorithm)
    • 已知系统中所有资源的种类和数量
    • 已知进程所需要的各类资源最大需求量
    • 该算法可以计算出当前的系统状态是否安全（寻找安全序列)

银行家算法-数据结构

  • Available:当前系统中可用资源数量
  • Max:每个进程的最大资源需求量
  • Allocation:已经分配给进程的资源数量
  • Need:每个进程还需要的资源数量

银行家算法的优缺点

  • 优点：允许死锁必要条件同时存在
  • 缺点：缺乏实用价值
    • 进程运行前就要求知道其所需资源的最大数量
    • 要求进程是无关的，若考虑同步情况，可能会打乱安全序列
    • 要求进入系统的进程个数和资源数固定

死锁的检测与恢复

  • 允许死锁发生，操作系统不断监视系统进展情况判断死锁是否发生
  • 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
  • 死锁检测的时机
    • 当进程等待时检测死锁（系统开销大）
    • 定时检测
    • 系统资源利用率下降时检测死锁

资源分配图表示法

  • 资源类（资源的不同类型）
  • 资源实例（存在于每个资源中）
  • 进程
  • 申请边
  • 分配边

死锁定理

  • 如果能在“资源分配图”中消去某进程的所有请求边和分配边，则称该进程为孤立结点。
    • 可完全简化
    • 不可完全简化
  • 系统为死锁状态的充分条件是：当且仅当该状态的进程一资源分配图”是不可完全简化的。该充分条件称为死锁定理

死锁的解除

  • 中止进程，强制回收资源

    • 交通问题：将某列火车吊起来
    • 哲学家问题：将某个哲学家射死

  • 剥夺资源，但不中止进程

  • 进程回退(roll back)

    • 就像DVD的回退，好像最近一段时间什么都没有发生过
    • 交通问题：让某列火车倒车
    • 哲学家问题：让某个哲学家放下一把叉子

  • 重新启动

    没有办法的办法，但却是一个肯定有效的办法

HOW OS DO TO DEADLOCKS?

  • In the absence of algorithms to detect and recover from deadlocks,we may arrive at a situation in which the system is in a deadlocked state yet has no way of recognizing what has happened.In this case,the undetected deadlock will cause the system’s performance（执行效率） to deteriorate（恶化）,because resources are being held by processes that cannot run and because more and more processes,as they make requests for resources,will enter a deadlocked state.Eventually,the system will stop functioning and will need to be restarted manually（手动重启）
  • Although this method may not seem to be a viable（可行） approach to the deadlock problem,it is nevertheless used in most
    operating systems.

进程内存空间

物理地址

内存单元看到的地址，是指令和数据真实的内存地址，而逻辑地址是面向程序而言的

**物理地址=基址+逻辑地址 **

进程的内存映像

以32位机器为例，地址总线是32位，可寻址的最大内存空间是22 Bytes,即4 GBytes。每一个运行的进程都可以获得一个4GB的逻辑地址空间，这个空间被分成两个部分：内核空间和用户空间，其中用户空间分配到从0x00000000到0xC0000000共3GB的地址，而内核空间分配了0xC0000000到0 xFFFFFFFF高位的1GB地址

内存管理

MAIN MEMORY（主存）

  • Main memory is central to the operation of a modern computer system.
  • Memory consists of a large array of bytes（字节数组或者字节序列）,each with its own address.
  • The CPU fetches instructions from memory according to the value of the program counter(PC).These instructions may cause additional loading from and storing to specific memory addresses.
  • A typical instruction-execution cycle（指令执行周期）,for example,first fetches（取指） an instruction from memory.The instruction is then decoded（译码） and may cause operands to be fetched from memory.After the instruction has been executed on the operands,results may be stored back in memory.

高速缓存CACHE

高速缓存是一种存取速度比内存快，但容量比内存小的多的存储器，它可以加快访问物理内存的相对速度。

保护操作系统和用户进程

用户进程不可以访问操作系统内存数据，以及用户进程空间之间不能互相影响

  • 通过硬件实现，因为操作系统一般不干预CPU对内存的访问
    • base register:基址寄存器
    • limit register:限长寄存器
  • 上述两个寄存器的值只能被操作系统的特权指令加载

内存管理目标

  • 存取速度
  • 操作正确（分配和回收）
  • 保护操作系统
  • 保护用户进程
  • 地址转换

地址空间和地址转换

  • 逻辑地址：面向程序的地址，总是从0开始编址，每一条指令的逻辑地址就是与第1条指令之间的相对偏移，因此逻辑地址也叫相对地址或虚拟地址。
  • 物理地址：内存单元看到的实际地址，也称为绝对地址。
  • 所有逻辑地址的集合称为逻辑地址空间，这些逻辑地址对应的所有物理地址集合称为物理地址空间。
  • 地址转换：由逻辑地址转换成物理地址。

地址转换时机

编译时

前提：提前知道这个程序要加载的物理内存的起始地址R

缺点：不允许被移动

加载时

加载时知道基址R

缺点：不允许被移动

运行时

逻辑地址->MMU->物理地址

内存管理单元MMU

Memory-Management Unit完成逻辑地址到物理地址运行时的转换工作。

  • 重定位寄存器(relocation register)或基址寄存器（base register）

CONTIGUOUS MEMORY ALLOCATION（连续内存分配）

In contiguous memory allocation,each process is contained in a single section of memory that is contiguous to the section containing the next process.

  • Memory allocation
  • Memory recycle
  • Memory protection

FIXED-SIZED PARTITION（固定大小分区）

Memory is divided to several fixed-sized partitions. Each partition may contain exactly one process.

  • 缺点：存在碎片造成空间浪费

VARIABLE-PARTITION（可变分区）

  • In the variable-partition scheme,the operating system keeps two tables indicating which parts of memory are available and which are occupied.
  • Initially,all memory is available for user processes and is considered one large block of available memory,a hole.（孔/洞）
  • Eventually,as you will see,memory contains a set of holes of various sizes.（不同大小孔洞的集合）

动态存储分配问题

  • 首次适应

    分配首个足够大的孔，效率最高

  • 最佳适应

    分配最小的足够大的孔，浪费最小

  • 最坏适应

    分配最大的孔，产生的剩余孔更可能被再利用

地址转换和保护

  • 两种连续分配方案的地址转换方式是相似的：

    **物理地址=基址+逻辑地址 **

  • 地址保护策略：与限长limit进行比较

碎片

Fragmentation:some little pieces of memory hardly to be used.

  • internal fragmentation（对于固定分区而言）
  • external fragmentation（对于可变分区而言）
    • 解决办法：compaction（紧凑/压缩）
    • 限制
      • static relocation（静态地址转化不可以使用，运行时地址转换才能使用）
      • cost（开销）

分段和分页

MOTIVATION

  • Solution to fragmentation（碎片）:permit the logical address space of processes to be noncontiguous.（不连续)
  • The view of memory is different between
    • logical (programmer’s ):a variable-sized segments(可变大小的段)
    • physical:a linear array of bytes（线性数组/字节序列）
  • The hardware could provide a memory mechanism that mapped the logical view to the actual physical memory.

程序员眼中的内存世界

  • 程序员看到的
    • 主函数和一组其他函数
    • 各种数据结构：变量、结构体、对象、数组等
    • 所有的模块都是名字来引用的
  • 因此他们认为在内存中，程序是由若干个大小不等的段构成的，每个段都有专门的用途，段的大小和用途相关。
  • 段和段之间不必连续存放（离散）

分段

逻辑地址：段号+段内位移

  • 段基址
  • 段限长
  • 段表

转换成物理地址

  • 段内位移小于段限长，物理地址=段基址+段内位移
  • 段内位移大于段限长，error

分页

逻辑地址：页号+页内位移

物理地址=页框号×页面大小+页内位移

若以二进制表示，物理地址：页框号+页内位移

LOGICAL ADDRESS（分页的逻辑地址）

  • The page size(like the frame size)is defined by the hardware.The size of a page is a power of 2,varying between 512 bytes and 1 GB per page,depending on the computer architecture.

  • The selection of a power of 2 as a page size makes the translation of a logical address into a page number and page offset particularly easy.

  • If the size of the logical address space is 2^m,and a page size is 2^n bytes, then the high-order m-n bits of a logical address designate the page number,and the n low-order bits designate the page offset.Thus,the logical address is as follows:

    高位：m-n比特 表示有多少个页面

    低位：n比特 表示页内位移

    总共m个比特

分段和分页的区别

分段 分页
信息的逻辑单位 信息的物理单位
段长是任意的 页长由系统确定
段的起始地址可以从主存任一地址开始 页框起始地址只能以页框大小的整数倍开始
(段号，段内位移)构成了二维地址空间 (页号，页内位移)构成了一维地址空间
会产生外部碎片 消除了外部碎片，但会出现内部碎片

页表

PAGE TABLE

  • The operating system maintains a copy of the page table for each process.
  • This copy is used to translate logical addresses to physical addresses.
  • It is also used by the CPU dispatcher（调度程序） to define the hardware page table when a process is to be allocated the CPU.
  • Paging therefore increases the context-switch time.（上下文切换开销）

HARDWARE PAGE TABLE

  • The page table is kept in main memory and a page **table base register(PTBR) **（CPU中的寄存器）points to the page table.
  • Changing page tables requires changing only this one register,substantially reducing context-switch time.
  • With this scheme,two memory accesses（访问内存两次） are needed to access a byte (one for the page-table entry,one for the byte).

TLB（是一个硬件）

**TLB(Translation Look-aside Buffer) **（转换旁路/后备缓冲区/相联存储器）is a kind of small, fast-lookup hardware cache.It is used with page tables in the following way.

  • The TLB contains **only a few of the page-table entries.**（仅包含部分的页表的页表项，就是快表）
  • When a logical address is generated by the CPU,its page number is presented to the TLB.
  • If the page number is found,its frame number is immediately available and is used to access memory.（一次内存访问）
  • If TLB miss（未命中）,a memory reference to the page table must be made.（两次内存访问）

TLB HIT RATIO（命中率）

  • The percentage of times（次数的比例） that the page number of interest is found in the TLB is called the hit ratio.
  • An 80-percent hit ratio,for example,means that we find the desired page number in the TLB 80 percent of the time.If it takes 100 nanoseconds to access memory,please find the effective memory-access time.
    • effective access time = 0.80 x 100 + 0.20 x 200 = 120 ns

保护

  • 为了防止地址转换时出现异常，可在页表每个条目设置一个“valid–invalid”比特位，用于表示该页的有效性。
  • 这个方法可以被轻松扩展以提供更好的保护级别，如“只读”、“读写”、“可执行”等。

页表页

逻辑地址：页表页号+页号+页内位移

多级页表

  • 上面是一个32位地址采用两级页表的例子，页面大小是4 KBytes,第一级页表页的数量是1K个，每个页表页中包含的页面数量也是1K个。
  • 下面是x86-64架构CPU采用的四级页表方案

虚拟内存

局部性原理

  • 时间局部性(Temporal locality)

    如果某个信息这次被访问，那它有可能在不久的未来被多次访问，

  • 空间局部性(Spatial locality)

    如果某个位置的信息被访问，那和它相邻的信息也很有可能被访问到，

  • 内存局部性(Memory locality)

    访问内存时，大概率会访问连续的块，而不是单一的内存地址，其实就是空间局部性在内存上的体现

  • 分支局部性(Branch locality)

    计算机中大部分指令是顺序执行，顺序执行和非顺序执行的比例大致是5：1

  • 等距局部性(Equidistant locality)

    等距局部性是指如果某个位置被访问，那和它相邻等距离的连续地址极有可
    能会被访问到。

修改缓存数据

  • Write through（直接写）

    修改缓存数据的同时修改内存数据

  • Write back（回写）

    只修改缓存数据，直到该数据要被清除出缓存再修改内存中的数据

缓存数据的淘汰

  • 缓存的容量很小，当缓存满的时候，就需要将缓存中的部分数据淘汰，装入新的数据。
  • 淘汰
    • 用得最少的
    • FIFO

部分装入和部分对换

  • 部分装入
    • 进程运行时仅加戟部分进入内存，而不必全部装入
    • 其余部分暂时放在swap space
  • 部分对换
    • 可以将进程部分对换出内存，用以腾出内存空间
    • 对换出的部分暂时放在swap space

VIRTUAL MEMORY（虚拟内存）

  • Virtual memory is a technique that allows the execution of processes that are not completely in memory.（部分装入）
  • One major advantage of this scheme is that programs can be larger than physical memory.
  • Further,virtual memory abstracts main memory into an extremely large,uniform array of storage,separating logical memory as viewed by the user from physical memory.
  • This technique frees programmers from the concerns of memory-storage limitations.

DEMAND PAGING（请求调页）

  1. 基于分页方案
  2. 页表：valid/invalid
  3. 内存驻留
  4. demand a page
  5. paging
  • With demand-paged virtual memory,pages are loaded only when they are demanded during program execution.
  • Pages that are never accessed are thus never loaded into physical
    memory.

请求调页步骤

  1. reference（引用）
  2. trap：page fault（缺页中断）
  3. 接下来操作系统调页
  4. page is on backing store（找页面）
  5. bring in missing page（将缺失页面加载到内存当中）
  6. reset page table（更新页表)
  7. restart instruction

请求调页的性能

  • 假设访问内存时间为ma,处理一次缺页中断的时间记作page fault time,令p为缺页中断的出现几率，则有效访问时间的计算公式为：
    • effective access time =(1-p) x ma + p x page fault time
  • 若ma=200ns,page fault time=8ms，P=0.001,则
    • effective access time =8200ms
  • 缺页中断率p对性能影响重大

页面置换

当进程在执行过程中发生了缺页，在请求调页的时候发现内存已经没有空闲页框可用，操作系统在此时会做出一个处理：页面置换。

页面置换策略

FIFO

总是淘汰最先进入内存的页面，因为它在内存中待的时间最久。

优点

简单

缺点

与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如：含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。

OPTIMAL（最优）

总是淘汰最长时间不会再使用的页面。

  • 无法实现，因为无法预测未来
LRU (LEAST RECENT UNUSED）

总是淘汰最近最少使用的页面。

优点

考虑程序访问的时间局部性，一般能有较好的性能，实际应用多。

缺点

实现会需要较多的硬件支持，会增加硬件成本。

THRASHING（抖动）

  • If the process does not have the number of frames it needs to support pages in active use,it will quickly page-fault.At this point,it must replace some page.However, since all its pages are in active use,it must replace a page that will be needed again right away.Consequently,it quickly faults again,and again,and again,replacing pages that it must bring back in immediately
  • This high paging activity is called thrashing.A process is thrashing if it is spending more time paging than executing.

抖动的原因

  • 并发进程数量过多
  • 进程页框分配不合理

PAGE FAULT FREQUENCY

PF称作页面故障（频）率，基于这个数据可以实施一个防止抖动的策略：动态调节分配给进程的页框数量。

CONCLUDING REMARKS

  • Practically speaking,thrashing and the resulting swapping have a disagreeably large impact on performance.
  • The current best practice in implementing a computer facility is to include enough physical memory,whenever possible,to avoid thrashing and swapping.
  • From smartphones through mainframes,providing enough memory to keep all working sets in memory concurrently,except under extreme conditions,gives the best user experience.

大容量存储

磁盘结构

  • 磁道（track）：能被磁头访问的一组同心圆

  • 扇区（sector）：磁道上的区域，数据存放的基本单位

  • 柱面：所有盘片同一磁头下的磁道集合

  • 恒角速度CAV

    • 每条磁道上的肩区数相等

    • 不同磁道密度不同，但转速恒定

    • 硬盘

  • 恒线速度CLV

    • 每条磁道上的数据密度相等

    • 磁道密度相同，但转速不断变化

    • 读一个扇区的情况下，数据在外转速慢，在内转速快

    • DVD/CD

磁盘格式化

  • 低级格式化（Low-level formatting）
    • Physical formatting
    • 为每个扇区使用特殊的数据结构进行填充，包括一个头部、数据区域和一个尾部。
    • 头部和尾部包含一些控制信息，如扇区号、ECC码等。
  • 高级格式化(High-level formatting)
    • Logical formatting
    • 构建文件系统，在磁盘上初始化文件系统数据结构，如空闲和已分配空间表、一个空目录等。

磁盘性能指标

  • 查找一个物理块的顺序：柱面号、磁头号和扇区号
    • 寻道时间Ts:将磁头定位到正确磁道（柱面）上所花的时间，与盘片直径和传动臂速度相关，平均20ms
    • 旋转延迟T:所查找的扇区转到磁头下所用的时间，与磁盘的旋转速度有关，一个10,000r/m的磁盘平均旋转延迟为3ms。
    • 传送时间T:传送扇区内的数据的时间，同样取决于磁盘的旋转速度，T=b/(rN)(b为要传送的字节数，N为一个磁道中的字节数，r为转速)
  • 总的平均存取时间Ta=Ts+Tr+T

DISK I/O REQUEST

Whenever a process needs I/O to or from the disk,it issues a system call to the operating system.The request specifies several pieces of information:

  • Whether this operation is input or output
  • What the disk address for the transfer is（柱面、磁头、扇区）
  • What the memory address for the transfer is
  • What the number of sectors（扇区） to be transferred is

DISK SCHEDULING（磁盘调度）

For a multiprogramming system with many processes the disk queue may often have several pending requests.Thus,when one request is completed,the operating system chooses which pending request to service next.How does the operating system make this choice?

FCFS SCHEDULING
SSTF SCHEDULING（Shortest-Seek-Time First 最短寻道时间优先)
  • ”磁臂粘连“现象->饥饿
SCAN SCHEDULING（扫描算法）
  • 负载均衡
C-SCAN SCHEDULING（循环扫描算法）
LOOK SCHEDULING（电梯算法）

SELECTION OF A ALGORITHM

  • FCFS is the simplest.
  • SSTF is common and has a natural appeal but it may cause a starvation problem.
  • SCAN and C-SCAN perform better for systems that place a heavy load on the disk.
  • How to know which algorithm is chosen by Linux?

LINUX IO SCHEDULER

  • noop:it performs FCFS policy which is good enough for SSD.
  • deadline:it works by creating two queues:a read queue and a write queue.Each I/O request has a time stamp(时间戳) associated that is used by the kernel for an expiration time.When an I/O request reaches its deadline,it is pushed to the highest priority
  • cfq:Complete Fairness Queueing works by creating a per- process I/O queue.（为每个进程维护一个队列）The goal of this I/O scheduler is to provide a fair I/O priority to each process.While the CFQ algorithm is complex,the gist of this scheduler is that after ordering the queues to reduce disk seeking,it services these per-process I/O queues in a round-robin fashion.

I/O系统

BUS

总线：一组线路和通过线路传输信息的一个协议

  • 并行：Multiple Lane

    同一时刻发送多个比特，缺点占线面积大，比特与比特之间的干扰

  • 串行：Single Lane

    PCIe、SATA、USB

PERIPHERALS COMPONENT INTERCONNECT（外围设备 组件 相互连接）

PORTS（端口）

  • PCIe
  • SATA（硬盘）
  • USB(Universal Serial（串行） Bus)
  • VGA
  • HDMI
  • DVI
  • Thunder Blot

设备类型

块设备（block device）
  • 存取单位是一个block
  • 如磁盘、磁带、DVD等
字符设备（character device)
  • 存取单位是一个字符
  • 如显示器、键盘、鼠标等

CONTROLLER

A controller is a collection of electronics（电子元件） that can operate a port,a bus,or a device.

  • A serial-port controller is a simple device controller.It is a single chip (or portion of a chip)in the computer that controls the signals on the wires（线缆） of a serial port.
  • A SCSI bus controller is NOT simple because the SCSI protocol is complex.It typically contains a processor（微处理器）,microcode,and some private memory to enable it to process the SCSI protocol messages.
  • Some devices have their own built-in controllers.You will see a circuit board attached to one side of a disk drive.This board is the disk controller.It implements the disk side of the protocol for some kind of connection-SCSI or Serial Advanced Technology Attachment (SATA), for instance.It has microcode and a processor to do many tasks,such as bad-sector mapping（坏道）,prefetching（预先获取）,buffering（缓冲）,and caching（缓存）

如何对控制器发布命令

控制器有一个或多个用于数据和控制信号的寄存器（存储二进制）。CPU通过读写这些寄存器来控制通信。

  • 控制寄存器：可以被主机发布命令或改变设备状态
  • 状态寄存器：包含一些主机可读的位信息
  • 数据寄存器：记录主机可读或写入的数据

I/O地址

I/O地址：控制寄存器地址

编址方式

  • I/O独立编址：使用独立的I/O指令，如IN、OUT;
  • 内存映射编址：划出一块内存地址，将I/O的端口地址映射进来，这样就可以使用访问内存指令对控制寄器进行读写。

I/O控制方式

轮询
  1. 步骤
    • 重复测试busy位，直到清零；
    • 设置控制寄存器为write操作，并将要写入的字节X存入数据寄存器；
    • 设置ready位
    • 若ready位为1，则设置busy位
    • 执行write命令，将字节X写入设备
    • 清除ready位和busy位
  2. 评价
    • 优点：逻辑简单
    • 缺点：忙式等待
中断
  1. 步骤
    • CPU向I/O控制器发布要启动I/O控制器的命令，然后CPU执行其他任务去
    • I/O设备就绪可以被执行，通过中断方式通知CPU
    • 如果CPU收到这个中断， 中断处理程序处理数据，然后从中断返回
    • CPU恢复中断前的工作
    • 循环以上步骤
  2. 评价
    • 优点：CPU没有循环等待I/O设备是否就绪
    • 缺点：CPU的利用率依旧不高
DMA直接内存访问

步骤

  • CPU向磁盘控制器发出命令传递C个字节的磁盘数据到地址为X的内存区
  • 磁盘控制器初始化DMA传输，向DMA控制器发送每个字节
  • DMA控制向X地址内存传输字节，增加内存地址并减少C的值
  • C=0时，DMA发出中断，通知CPU传输完毕

CYCLE STEALING（周期窃取）

  • When the DMA controller seizes the memory bus,the CPU is momentarily prevented from accessing main memory.We call the DMA steals the CPU’s cycle.
  • Although this cycle stealing can slow down the CPU computation,offloading(卸载) the data-transfer work to a DMA controller generally improves the total system performance.

内核I/O结构

内核I/O结构包括I/O硬件和I/O软件两个部分，I/O软件的设计目标主要体现在：

  • **高效率(efficiency)**：通过一些手段提高I/O设备的访问效率。
  • **通用性（generality)**：屏蔽硬件细节，让用户使用统一的接口方便地使用不同的硬件。

设备驱动层

Device-driver layer makes the I/O subsystem independent of the hardware through hiding the differences among device
controllers.（屏蔽底层硬件的差异性，向上提供统一接口）

内核I/O子系统

  • Several services-scheduling（调度）,buffering（缓冲）,caching（缓存）, spooling（假脱机=>真联机）,device reservation（设备预留）,and error handling-are provided by the kernel’s I/O subsystem and build on the hardware and device-driver infrastructure.
  • The I/O subsystem is also responsible for protecting itself from errant processes（偏离正轨的进程） and malicious users.
BUFFERING

缓冲主要用于处理数据流的生产者和消费者速度不匹配问题。内存充当缓冲

BUFFER & CACHE

The difference between a buffer and a cache is that a buffer may hold the only existing copy of a data item, whereas a cache,by definition,holds a copy on faster storage of an item that resides elsewhere.

SPOOLING

A spool (Simultaneous Peripheral Operations On-Line)(外围设备操作同时在线）is a buffer that holds output for a device,such as a printer,that cannot accept interleaved（交替） data streams.Although a printer can serve only one job at a time,several applications may wish to print their output concurrently,without having their output mixed together.

I/O请求的生命周期

看视频最后的图片

期末复习

OS目标

  • 方便性：方便用户使用计算机

  • 有效性：提高系统资源利用率和系统的吞吐量

  • 可扩充性：有随着硬件的提升可适应能力

  • 开放性

OS功能

管理计算机资源：处理器管理、存储管理、设备管理、文件管理

用户与硬件的接口

用户角度

  • 提供良好的用户界面
  • 提供标准的函数库
  • 使得编程更加方便不容易出错

系统角度

  • 管理资源
  • 解决申请资源产生的冲突
  • 阻止错误的产生和计算机不正当的使用

多道程序基本特点

  • 多道：即计算机内存中同时存放几道相互独立的程序
  • 宏观上并行：同时进入系统的几道程序都处于运行过程中，即它们先后开始了各自的运行，但都未运行完毕。
  • 微观上串行：从微观上看，内存中的多道程序轮流地或分时地占有CPU。

分布式系统使用的场合

  • 搜索引擎
  • 社交网络
  • 电子商务
  • 云计算

进程与线程的关系

  • 一个进程可以有多个线程，但至少有一个线程；而一个线程只能在一个进程的地址空间内活动。
  • 资源分配给进程，同一个进程的所有线程共享该进程所有资源。
  • CPU分配给线程，即真正在处理器运行的是线程。
  • 线程在执行过程中需要协作同步，不同进程的线程间要利用消息通信的办法实现同步。

页表项与什么有关

总的比特数-页内偏移的比特数

页内地址偏移与页表大小关系

2^页内偏移的比特数=页面大小

决定地址结构

页号+位移量

动态分区管理算法的过程与评价，系统性能与影响、评价指标

首次适应

将空闲分区链以地址递增的顺序连接；在进行内存分配时，从链首开始顺序查找，直到找到一块分区的大小可以满足需求 时，按照该作业的大小，从该分区中分配出内存，将剩下的空闲分区仍然链在空闲分区链中。

优点

高址部分的大的空闲分区得到保留，为大作业的内存分配创造了条件；

缺点
  • 每次都是优先利用低址部分的空闲分区，造成低址部分产生大量的外碎片。
  • 每次都是从低址部分查找，使得查找空闲分区的开销增大

最佳适应

将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。每次从链首进行查找合适的空闲分区 为作业分配内存，这样每次找到的空闲分区是和作业大小最接近的，所谓“最佳”.

优点

找到的空闲分区是大小最接近待分配内存作业大小的；

缺点

产生大量难以利用的外部碎片。

最坏适应

将空闲分区链的分区按照从大到小的顺序排序形成空闲分区链，每次查找时只要看第一个空闲分区是否满足即可。

优点

效率高，分区查找方便；

缺点

大作业就找不到合适的空闲分区。

页式内存中多级页表性质、带来的收益、损失

多级页表，页目录表+页表

收益

节省大量内存

损失

需要访问三次内存；cpu每一条指令执行的时间其实大部分都是浪费在访问内存上

段页式而没有页段式

驱动程序谁编写

设备制造商