操作系统概论

kfkfka zkye...大约 39 分钟

操作系统概论

作业ip：https://10.11.119.115 / http://10.11.119.115:8234 [内网访问]
初始用户及密码均为学号
评分标准：
出勤率+作业+课堂表现 20%
平时测验（每次5%，共8次） 40%

IO结构

CPU、内存与I/O设备间的操作速率相差甚远，因此存在2中I/O结构

两种I/O结构

同步I/O：I/O启动后，只有当I/O完成后控制权才返回给用户进程。
- wait指令，使CPU空闲直到下一个中断开始
- 循环等待
- 在任何时候最多只能处理一个I/O请求
异步I/O：I/O启动后，控制权无须等待I/O操作完成就可返回给用户进程。
- 系统调用－请求OS允许用户等待I/O操作的完成
- 设备状态表包含了每个I/O设备的一个条目，用来指示该设备的类型、地址和状态（不工作、空闲或繁忙）
- OS通过查询I/O设备表来判断设备的状态，并修改该条目，以反映出现中断
image-20220301100257102

外部接口的IO操作模式

内存：CPU可以直接访问，不需要通过接口
I/O设备：需要通过被CPU访问

程序查询模式
中断模式
DMA模式

中断

中断发生时，OS必须通过保存寄存器和程序计数器来保留CPU的状态，
分轮询、向量中断系统，
将内核例程与用户例程分离，以决定每种类型的中断应该采取的动作。

中断通过中断向量表将控制传输给中断服务例程，中断向量表包括了所有设备服务例程的入口地址
中断体系结构必须保存中断指令的地址
当一个中断正被处理的时候，其他中断是被禁止的
陷阱是因错误或用户程序的特定请求所引起的软件生成中断
操作系统是中断驱动的

DMA模式

用于高速I/O设备，使之以接近内存的速度进行信息传输
设备传输器以块为单位直接将数据从存储器传输到主存，而无须CPU的干预
每个数据块传输的时候只产生一个中断，而不是一个字节的传输就会产生一个中断

硬件保护

双重模式操作

操作系统分用户模式和内核模式；

特权指令只能在内核[核心]模式下执行，非特权指令随意；

特权指令，如关机，在用户模式下无法执行；所有I/O指令均为特权指令；

特权指令的主要特征在于是否影响其它用户。

用户态切换内核态通过 trap 实现：

访管指令或陷阱指令（trap）：

CPU指令集中的一个特殊指令，只能在用户模式下执行，负责从用户模式切换到内核模式
当应用程序需要请求操作系统服务时，编译器会在发生系统调用时自动插入一条访管指令，CPU执行访管指令将产生一个访管中断(trap，自陷），然后启动相应的操作系统服务

硬中断、陷阱与软中断

中断即外中断，是指来自处理机和内存外部的中断，包括I/O设备发出的I/O中断、外部信号中断、各种定时器引起的时钟中断及调试程序中设置的断点等引起的调试中断等。陷阱即内中断，主要是指在处理机和内存内部产生的中断。它包括程序运算引起的各种错误。软中断是通信进程之间用来模拟硬中断的一种信号通信方式。

==!==陷入与硬件中断的不同：

① 陷阱通常由处理机正在执行的现行指令引起，而中断则是由与现行指令无关的中断源引起的。

② 陷阱处理程序提供的服务为当前进程所用，而中断处理程序提供的服务则不是为了当前进程的。

③ CPU在执行完一条指令之后，下一条指令开始之前响应中断，而在一条指令执行中也可以响应陷阱。

④ 在有的系统中，陷入处理程序被规定在各自的进程上下文中执行，而中断处理程序则在系统上下文中执行。

==!==软中断与硬中断的比较的相同点：

中断源发中断请求或软中断信号后，CPU或接收进程在适当的时机自动进行中断处理或完成软中断信号所对应的功能。

==!==软中断与硬中断的不同点：

接收软中断信号的进程不一定正好在接收时占有处理机，而相应的处理必须等到该接收进程得到处理机之后才能进行。

I/O保护

必须确保用户程序永远无法以monitor模式获得计算机的控制权

内存保护

CPU保护

分时系统

同时性
交互性
共享性
独占性

实时系统

对时钟管理高要求
可靠性
过载保护
【嵌入式系统是常见的应用；一定程度上也现在了其高并发的能力】

操作系统服务

API

exce 函数族

exec函数族提供了一个在进程中启动另一个程序执行的方法。它可以根据指定的文件名或目录名找到可执行文件，并用它来取代原调用进程的数据段、代码段和堆栈段，在执行完之后，原调用进程的内容除了进程号外，其他全部被新的进程替换了。另外，这里的可执行文件既可以是二进制文件，也可以是Linux下任何可执行的脚本文件。

使用exec函数族主要有两种情况：

当进程认为自己不能再为系统和用户做出任何贡献时，就可以调用exec函数族中的任意一个函数让自己重生。
如果一个进程想执行另一个程序，那么它就可以调用fork函数新建一个进程，然后调用exec函数族中的任意一个函数，这样看起来就像通过执行应用程序而产生了一个新进程(这种情况非常普遍)。

exec函数族共有6种不同形式的函数。这6个函数可以划分为两组：

execl、execle、execlp
execv、execve、execvp

用例

execlp("ls", "ls", "/", "-l", NULL);		//使用程序名在PATH中搜索
execl("/bin/ls", "ls", "/", "-l", NULL);   	//使用参数一给的绝对路径搜索
execl("./while", "ls","/home/wlr", "-l", NULL); //执行自定义程序

exec函数族一般规律

exec函数一旦调用成功即执行新的程序，不返回。只有失败才返回，错误值为 -1。所以我们通常直接在 exec 函数调用后直接调用 perror() 和 exit()，无须 if 判断【exec函数族后缀】

- l(list)：命令行参数
- p(path)：搜索file时使用path变量
- v(vector)：使用命令行参数数组
- e(environment)：使用环境变量数组，不使用进程原有的环境变量，设置新加载程序运行的环境变量

wait()函数

pid_t wait(int *stat_loc);

获取子进程退出状态并返回死掉的子进程ID。传整型变量地址 stat_loc 给函数，内核将子进程的退出状态保存在这个变量中，并返回子进程 pid。
调用会阻止调用进程，直到它的一个子进程退出或收到信号为止。子进程终止后，父进程在wait系统调用指令后继续执行。

父进程调用wait函数可以回收子进程终止信息。该函数有三个功能：

阻塞等待子进程退出
回收子进程残留资源
获取子进程结束状态（退出原因）

getpid()函数

获取当前进程 PID

getppid()函数

获取当前进程 PPID

进程

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。
线程（Thread）是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

CPU调度的基本单位是是线程。

一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

PCB 进程控制块

每个进程在内核中都有一个进程控制块(PCB)来维护进程相关的信息。其作用是使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位或其他进程并发执行的进程。PCB是系统感知进程存在的唯一标识。

进程调度

高级调度 (外存 --> 内存)：作业调度
中级调度 (外存 --> 内存)：内存调度
低级调度 (内存 --> CPU)：进程调度

作业调度：作业调度一般是将一个作业从外存调入内存，为其分配内存、外设等资源，使其能够竞争处理机资源。对每个作业来说，每个作业一般只调入一次、调出一次。
内存调度：内存调度是为了提高内存利用率和系统吞吐量，一般会将暂时无法运行的进程挂起，当具备运行条件且内存有空闲时，会将这些进程调回，挂在就绪队列上等待调度。
进程调度：最频繁的调度方式，一般从就绪队列中调出一个进程，为它分配处理机资源。

简单例子：

高级调度：研究怎么让还没进入过厕所的人进入厕所。(厕所外 --> 厕所内，之前一直在厕所外)
中级调度：有的人进入了厕所，但是尿不出来，于是他们被赶了出去。中级调度就是研究怎么让这些被赶出去的人再次回到厕所。 (厕所外 --> 厕所内，之前进入过厕所)
低级调度：研究怎么给厕所内的人分配马桶。(厕所内 --> 马桶上)

进程调度方式

非剥夺调度方式：当一个进程处于运行状态时，即使有更紧急或优先级更高的进程进入就绪队列，也不会抢占正在运行进程的处理机资源，只有当前运行进程结束运行或进入阻塞状态时才会从就绪队列将更紧迫的进程调出并分配处理机资源。
剥夺调度方式：当有一个更紧急或优先级更高的进程需要使用处理机，当前进程会被暂停，执行更紧迫进程的调度方式。

进程的挂起态与七状态模型

暂时调到外存等待的进程状态为挂起态。挂起态其实又可以进一步细分为就绪挂起、阻塞挂起两种状态，于是，五状态模型现在变成了七状态模型。

调度基本准则

CPU利用率：当CPU一直处于忙碌状态时，CPU利用率最高。
系统吞吐量：表示单位时间内完成的作业数量，当作业都是短作业时，系统吞吐量会比较大。
周转时间：是作业从提交到完成的时间，包括作业等待、在就绪队列排队、运行、IO操作的时间总和。
平均周转时间：是多个作业的周转时间的平均值。
带权周转时间：
平均带权周转时间：是多个带权周转时间的平均值。
等待时间：进程等待处理机的时间之和。
响应时间：从用户提交到首次响应所花费的时间。

调度算法

先来先服务（FCFS）调度算法

从名字就可以知道这是一种“先来后到”的调度算法，这种调度算法支持作业调度和进程调度。FCFS调度算法每次挑选队列中最先到达的进程或作业，依次进行调度。这是一种非剥夺调度算法，直观来看，非常公平，但是还是有缺点的。

特点：算法简单，但效率低，对长作业有利，短作业可能要等待很长时间。有利于CPU密集型作业，不利于IO密集型作业。

短作业/进程优先（SJF/SPF）调度算法

短作业/进程优先算法是一种优先调度短作业（进程）的调度算法，同样也是一种非剥夺调度算法。

特点：对短作业有利，对长作业不利，如果一直有短作业进来，可能长作业会一直得不到执行。不考虑作业紧迫程度，有些紧迫的作业可能不能及时处理。有利于IO密集型作业，不利于CPU密集型作业【可能是短作业会造成频繁的上下文切换】。

优先级调度算法

优先级调度算法既可以用于作业调度也可以用于进程调度。当用于作业调度时，会从后备作业队列中选出一个或多个优先级最高的作业，将它们调入内存中，并分配相应资源；当用于进程调度时，会从就绪队列中选出优先级最高的进程，将处理机分配给这个进程，使它能够运行。

根据高优先级进程能否抢占处理机还可以将这种算法分为非剥夺式优先级调度算法和剥夺式优先级调度算法。

在进程创建后进程优先级能否改变又可以将进程优先级分为静态优先级和动态优先级。

静态优先级。静态优先级是进程在创建时就已经确定好的，在进程运行期间不能改变。
动态优先级。动态优先级是指进程运行期间优先级根据进程实际运行情况动态变化的。

高响应比优先调度算法

高响应比优先调度算法适用于作业调度，是短作业优先调度算法和先来先服务算法的折中。我们先来看一下什么是响应比吧。

高响应比优先调度算法具有以下特点：

短作业的要求服务时间很短，因此在相同等待时间的情况下，短作业的响应比也更高，会被优先执行。
当要求服务时间相同时，等待时间长的作业会被优先服务。
长作业的要求服务时间比较长，但是随着等待时间的增加，长作业的响应比也会增加，然后可以分配处理机。

时间片轮转调度算法

时间片轮转调度算法一般在分时系统上使用，每个进程被分配固定大小的时间片，当时间片用完以后，无论进程是否执行结束，处理机都将被剥夺给下一个进程。

特点：时间片轮转调度算法的时间片大小选择很讲究，如果时间片过大，该调度算法会退化成为先来先服务调度算法，而时间片设置过小，处理机会频繁切换，进程真正使用处理机的时间减少，系统吞吐量下降。

多级反馈队列调度算法

多级反馈队列调度算法是这些调度算法中最复杂的，也是整合了前面一些调度算法而形成的算法，我们来看一下它的工作过程。

多级反馈队列调度算法工作过程有以下这些特点：

每一级队列从上至下的优先级逐渐递减，优先级越高的队列时间片越小。也就是说，最顶层的队列的时间片最小。
最新的进程进入内存会被放入最上层的队列末尾，当执行到这个进程时，如果能在分配的时间片内完成则会出队列，如果不能在时间片内完成就进入下一级队列末尾，等待处理机资源。
如果高优先级队列有进程存在，则处理机会优先处理上级队列中的进程。如果处理机正在执行某一队列中的进程，此时更高优先级队列中有进程进入，那么当前正在执行的进程会回到当前队列的队尾，处理机执行新进入队列的进程。

最后要提一点，多级反馈队列调度算法兼顾短作业优先的同时，不会让长作业长期处于等待状态最终出现饥饿。

进程通讯

信号

相关函数 signal()，sigprocmask()open in new window，sigpending()open in new window，sigsuspend()open in new window, sigemptysetopen in new window

// 高级信号（低级信号为signal，不可携带附加信息）
#include <sys/types>
#include <signal.h>
// 向指定pid发送信号；成功返回0，失败返回-1。
int sigqueue(pid_t pid, int sig, const union sigval value);
// pid是目标进程的进程号
// sig是信号代号，可通过 kill -l 查看，最大为64
// value参数是一个联合体,表示信号附带的数据，附带数据只能是 整数|指针 其一 ！！
// 有如下形式:
union sigval {
	int sival_int;
	void *sival_ptr;//指向要传递的信号参数
}; //value

// 在当前进程查询/接收信号
int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
// signum是信号编号，即上面的sig
// oldact是备份，方便恢复
struct sigaction {
	void (*sa_handler)(int);
	void (*sa_sigaction)(int signo, siginfo_t *resdata, void *unkonowp); // signo信号编号，resdata传入的附带信息，如resdata->si_value
	sigset_t sa_mask;  // 初始化/清空 sa_mask：sigemptyset(&act.sa_mask);
	int sa_flags;  // 获取附带信息：须使用sa_sigaction属性，必须设置sa_flags属性的值为SA_SIGINFO
	void (*sa_restorer)(void);
};
// sa_handler此参数和 signal() 的参数 handler 相同，代表新的信号处理函数，其他意义请参考signal()。
// sa_mask 用来设置在处理该信号时暂时将 sa_mask 指定的信号集搁置。
// sa_restorer 此参数没有使用。
// sa_flags 用来设置信号处理的其他相关操作，下列的数值可用。
// sa_flags还可以设置其他标志：
// SA_RESETHAND：当调用信号处理函数时，将信号的处理函数重置为缺省值SIG_DFL
// SA_RESTART：如果信号中断了进程的某个系统调用，则系统自动启动该系统调用
// SA_NODEFER ：一般情况下， 当信号处理函数运行时，内核将阻塞该给定信号。但是如果设置了 SA_NODEFER标记， 那么在该信号处理函数运行时，内核将不会阻塞该信号

循环中的fork()

#include<stdio.h>
#include<unistd.h>
int main(int argc,char **argv)
{
	for(int i=0;i<2;++i)
	{
		fork();
		printf("-");
	}
	return 0;
}
// 将会输出多少 “-” ？
// 8个

解答：有8个’-’是因为printf(“-”);语句有buffer；在fork的时候，缓存被复制到了子进程空间，所以，就多了两个。下图阴影双边框的两个子进程复制了父进程缓冲区的‘-‘

当i=0时，fork()创建了一个子进程，printf函数还没有执行，因此缓冲区中没有数据，父子进程打印了-
当i=1时，父进程又fork了一个子进程，但是此时父进程中的缓冲区中有数据，因此会复制缓冲区给子进程；同时子进程又执行了一次printf函数，因此子进程打印了两个-；同理由i=0创建的子进程也是如此主要原因：进程在fork时，缓冲区会被复制给子进程，且缓冲区非空。

若改为以下代码，则输出6个’-’。

#include<stdio.h>
#include<unistd.h>
int main(int argc,char **argv)
{
	for(int i=0;i<2;++i)
	{
		fork();
		printf("-\n");
	}
	return 0;
}

因为程序遇到“\n”，或是EOF，或是缓冲区满，或是文件描述符关闭，或是主动flush，或是程序退出，就会把数据刷出缓冲区。需要注意的是，标准输出是行缓冲，所以遇到“\n”的时候会刷出缓冲区，但对于磁盘这个块设备来说，“\n”并不会引起缓冲区刷出的动作，那是全缓冲，你可以使用setvbuf来设置缓冲区大小，或是用fflush刷缓存。

拓展：Unix下的设备有“块设备open in new window”和“字符设备open in new window”的概念，所谓块设备，就是以一块一块的数据存取的设备，字符设备是一次存取一个字符的设备。磁盘、内存都是块设备，字符设备如键盘和串口。块设备一般都有缓存，而字符设备一般都没有缓存。

线程

创建线程

// gcc -lpthread
#include <pthread.h>
int pthread_create(
                 pthread_t *restrict tidp,   //新创建的线程ID指向的内存单元。
                 const pthread_attr_t *restrict attr,  //线程属性，默认为NULL
                 void *(*start_rtn)(void *), //新创建的线程从start_rtn函数的地址开始运行
                 void *restrict arg //默认为NULL。若上述函数需要参数，将参数放入结构中并将地址作为arg传入。
                  );
// 返回值： 0 成功，-1 失败
// 1.避免直接在传递的参数中传递发生改变的量，否则会导致结果不可测。
// 2.对应pthread_join，确保线程正确退出

int pthread_join(
               pthread_t tid, //需要等待的线程,指定的线程必须位于当前的进程中，而且不得是分离线程
               void **status  //线程tid所执行的函数返回值（返回值地址需要保证有效），其中status可以为NULL
                 );
/* 返回值：0 成功，其他情况如下

ESRCH
描述: 没有找到与给定的线程ID 相对应的线程。（如果多个线程等待同一个线程终止，则所有等待线程将一直等到目标线程终止。然后一个等待线程成功返回。其余的等待线程将失败返回ESRCH错误）

EDEADLK
描述: 将出现死锁，如一个线程等待其本身，或者线程A和线程B 互相等待。

EINVAL
描述: 与给定的线程ID相对应的线程是分离线程。
*/

CPU调度

响应时间（Response time） : （第一次响应 - 到达时间）
周转时间（turnarouad time）: (结束时刻 - 到达时间)
等待时间（Waiting time）:（周转时间 - 运行时间）

CPU调度程序

CPU调度决策可以如下四种情况下发生：

当一个进程从运行状态切换到等待状态
当一个进程从运行状态切换到就绪状态
当一个进程从等待状态切换到就绪状
当一个进程终止时。

当调度只能发生在第一和第四两种情况时，称调度方法是非抢占的（ non-preemptive）
否则调度方案就是可抢占（preemptive）的。

调度准则

CPU使用率：使CPU尽可能忙
吞吐量（Throughput）：单位时间完成进程的数量
周转时间（Turnaround time）：从进程提交到进程完成的时间间隔称为周转时间
等待时间（Waiting time）：是在就绪队列中等待所花时间之和。
响应时间（Response time）：从提交请求到产生第一响应的时间
区间时间：程序完成所需耗时
剩余时间：程序结束还需耗时

优化准则

最大化CPU使用率
最大化吞吐量
最小化周转时间
最小化等待时间
最小化响应时间

调度算法

先到先服务调度（First Come, First Served, FCFS）
最短作业优先调度（Shortest-Job-First, SJR）
优先权调度（Priority Scheduling）
轮转法调度（Round Robin, RR）
多级队列调度（multilevel queue-scheduling）
多级反馈队列调度（multilevel feedback queue scheduling）

先到先服务（FCFS）

最短作业优先调度（SJF）

将每个进程与其下一个CPU区间段相关联。当CPU为可用时，它会赋给具有最短后续CPU区间的进程。如果两个进程具有同样长度的 CPU区间，那么可以使用FCFS调度来处理。

两种方式：

非抢占式：一旦进程获得CPU就一直占据CPU，直到其CPU区间完成为止
抢占式：如果一个新来的进程其CPU区间小于当前进程的CPU 区间，则抢占之。这种调度方式称为最短剩余时间作业优先（ Shortest Remaining Time First, SRTF）

SJF是最佳的：对于给定的一组进程，SJF算法的平均等待时间最小。

⬆️注意Arrival Time，只有进程在当前时间 arrival 后，才会加入比较

时间片轮转（RR）

轮转法是专门为分时系统而设计的。每个进程获得一小片CPU时间量（time quantum），通常为10-100毫秒。时间片结束后，进程被抢占并放入到就绪队列的最后重新参加调度。

如果就绪队列中有n个进程，具时间片为q，则每个进程会得到1/n的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过(n-1)q个时间单元，直到它的下一个时间片为止。

性能低速于时间片的大小

如果时间片非常大（无限），那么RR策略与FCFS策略一样。
如果时间片很小，那么RR方法称处理器共享。n个进程对于用户来说都有它自己的处理器，速度各为真正处理器速度的1/n

q必须大于上下文切换所需时间

多级反馈优先队列（）

进程可以在不同队列间移动。
每个队列有自己的调度算法——前台：RR 后台：FCFS

通常，多级反馈队列调度程序可由下列参数来定义：

队列数量
每个队列的调度算法
用以确定进程何时升级到较高优先权队列的方法
用以确定进程何时降级到较低优先权队列的方法
用以确定进程在需要服务时应进入哪个队列的方法

队列之间必须有调度

通常采用固定优先权可抢占调度来实现。
另一种可能是在队列之间划分时间片。每个队列都有一定的CPU时间，这可用于调度队列内的不同进程
- 20％给后台，80％给前台

进程同步

临界区设计准则

临界区：并发进程中可能改变共同变量、更新同一个表、写同一个文件的代码段。
进入区（上锁）、临界区、退出区（开锁）、剩余区

解决临界区问题必须满足如下三项要求：

互斥（Mutual Exclusion）：进程Pi在临界区内执行，其他进程不得进入临界区
前进/进步（Progress）：如果没有进程在临界区执行，那么允许不在剩余区的进程计入临界区
有限等待（Bounded Waiting）：从一个进程作出进入临界区的请求，直到该请求被允许为止，其他进程允许进入其临界区的次数有上限

忙则让权，空则进步，有限等待

算法实现

算法一

该算法无法实现互斥，在while (flag); flag = true处，进程仍可能冲突

算法二
算法三

TestAndSet 实现wait()和signal()

Swap() 实现互斥操作

进程饥饿

进程饥饿，即为Starvation，指当等待时间给进程推进和响应带来明显影响称为进程饥饿。当饥饿到一定程度的进程在等待到即使完成也无实际意义的时候称为饥饿死亡。也即：
由于别的并发的激活的进程持久占有所需资源,使某个异步进程在可预测的时间内不能被激活。

死锁

类型

竞争资源引起的死锁
进程通信引起的死锁
其他原因引起的死锁

死锁的条件

资源独占：一个资源在同一时间只能分给一个进程

不可剥夺：资源只能由其占有者在使用完后资源释放

保持申请：进程在占有部分资源后还可以申请新的资源，而且在申请新资源的时候并不释放它已经占有的资源

循环等待：存在一个循环等待链

处理

（静态）死锁预防：通过破坏死锁产生的必要条件实现，对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。预防分配策略、有序分配策略

（动态）死锁避免：在进程运行之前，为其分配所需的全部资源（预先分配策略）

饿死与活锁

饿死：当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时，称该进程被饿死

活锁：在忙式等待条件下发生的饥饿

内存管理

单一连续静态分区管理

动态分区方案

根据一组空闲孔来分配大小为n的请求。

首次适应（First-fit）
最佳适应（Best-fit）
最差适应（Worst-fit）

First-fit和best-fit在分配速度及存储效率上优于Worst-fit

而该方案虽然提高了空间利用，却导致了外部碎片

碎片

外部碎片：指内存中因为总剩余空间足够，而孔分散过小而无法利用的情况
内部碎片：指后续进行的分区管理中，由于需求内存小于统一分区管理的区大小，为了避免额外开销而分配整个分区的情况
紧缩（compaction）：用来降低外部碎片
- 移动内存内容，以便所有空闲空间合并成一整块。
- 如果重定位是动态的，是在运行时进行的，那么就能采用紧缩
另外一种可能解决外部碎片问题的方法是允许物理地址空间为非连续，这样只要有物理内存就可为进程分配。【即实现多重分区管理】
- 分页
- 分段

分区管理

解决外部碎片

地址转换

页式分区

内存空间划分：内存空间静态地划分为若干个等长区域，每个区域称为一个物理页架，每个页架通常由2i个单元，从0开始一次编址，称为页内地址。

进程空间划分：内存空间静态地划分为若干个等长区域，每个区域称为一个逻辑页面，每个页架通常由2i个单元，从0开始一次编址，称为页内地址。

所需表目：

页表：用于记录进程的逻辑页面和内存页架之间的对应关系
总页表：用于记录页架的使用情况

CPU生成的地址分成以下两部分【在CPU内部存在首址寄存器和界限寄存器】

页号(p)：页号作为页表中的索引。页表中包含每页所在物理内存的基地址。
页偏移(d)：与页的基地址组合就形成了物理地址，就可送交物理单元。

在这种方式下，每次数据/指令的访问需要访问两次内存。一次访问页表，另一次访问数据/指令
两次内存访问问题可以用特别的快速查找硬件缓冲（称为关联内存或翻译后备缓冲器）来解决

地址映射：物理地址=页架首址+页内地址=页架号*2i + 页内地址

    地址映射步骤：

          逻辑地址(p,d) -> 物理地址(f,d)

          (1) 由程序确定逻辑地址(p,d)；

          (2) 由p查快表得页架号f；

                如查不到：

                        (3) 由p与l比较，判别是否越界：

                              不满足：0 <= p <= l-1，越界；

                         (4) 由p和b查页表得f;

                         (5) parbegin

                               f与d合并得物理地址

                              (p,f)添加到快表，如满淘汰一个;

                               parend

          (3) f与d合并得物理地址

页表实现

几个进程几个页表，一般连续放置

段式分区

内存空间划分：内存空间静态地划分为若干个长度各异区域，每个区域称为一个物理段，每个物理段在内存中有一个起始地址，称为段首址。将物理段中的所有单元由0开始依次编址，称为段内地址。

进程空间划分：内存空间静态地划分为若干个长度各异区域，每个区域称为一个逻辑段。将一个逻辑段中的所有单元由0开始依次编址，称为段内地址。将一个进程的所有逻辑地址由0开始依次编号，称为段号所需表目：

段表：该表用于记录段号与段首址之间的关系
空闲表：用于记录并管理内存中的空闲区域
地址映射：逻辑地址(s,d) -> 物理地址(b’+d)

    地址映射步骤：

           (1)由程序确定逻辑地址(s,d);

           (2) 由s查快表得b’和l’

           如查不到：

                   (3) 由s与l比较判断是否越界

                        不满足：0<=s<=l-1，越界；

                   (4) 由s和b查段表，得b’和l’

                   (5) 由d与l’比较，判断是否越界

                        不满足：0<=d<=l’-1，越界;

                    (6)parbegin

                         由b’+d得物理地址

                         (s,b’,l’)加入快表, 如快表满淘汰一个；

                         parend

          (3) 由d与l’比较，判断是否越界

               不满足：0<=d<=l’-1，越界；

          (4) 由b’+d得物理地址。

问：分段与分页对比？

1)页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要（也是对用户透明的）。段是信息的逻辑单位，它含有一组其意义相对完整的信息（比如数据段、代码段和堆栈段等）。分段的目的是为了能更好的满足用户的需要（用户也是可以使用的）。

2)页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。

3)分页的作业地址空间是维一的，即单一的线性空间，程序员只须利用一个记忆符（线性地址的16进制表示），即可表示一地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名（比如数据段、代码段和堆栈open in new window段等），又需给出段内地址。

4)页和段都有存储保护机制。但存取权限不同：段有读、写和执行三种权限；而页只有读和写两种权限

总结：

分页是为了提高内存利用率，将内存分为一个个页架，将进程按照页架大小分为一个个页，分页对用户不可见。
分段则是按照程序的自身逻辑分配到内存中，对用户可见，用户编程时需要显示给出段名。
并且分段比分页更容易实现信息的共享，因为页的大小是由页架决定，一个页中可能包含多个逻辑模块，令多个逻辑模块共享同一块内存显然是不合理的。

问：简述分页的优点，存在的问题以及解决方法？

优点：内存空间利用率高，不会产生外部碎片，只会产生少量的页内碎片。

缺点：不方便按照逻辑模块实现信息的共享和保护；同时，页表也可能占据一部分物理空间；一旦页缺失，将大大提高查询时间。

解决：可以使用分段【使页内数据可通过逻辑模块实现信息联系】、多级页表【节省内存、可离散存储页表等】等方式；或者MMU添加TLB提高查询效率，使用巨型页，减低缺页异常。

虚拟地址

内存管理open in new window

TLB[ Translation Lookaside Buffers]: 转译后备缓冲器，也被翻译为页表缓存、转址旁路缓存，为CPUopen in new window的一种缓存，由存储器管理单元用于改进虚拟地址open in new window到物理地址的转译速度。
MMU[Memory Management Unit]: 内存管理open in new window单元，有时称作分页内存管理单元（paged memory management unit，PMMU）。一种负责处理中央处理器open in new window（CPU）的内存open in new window访问请求的计算机硬件open in new window。它的功能包括虚拟地址open in new window到物理地址open in new window的转换（即虚拟内存open in new window管理）、内存保护、中央处理器高速缓存open in new window的控制，在较为简单的计算机体系结构中，负责总线open in new window的仲裁open in new window以及存储体切换（bank switching，尤其是在8位的系统上）。

虚拟地址：页号+页内偏移

物理地址：块号+页内偏移

一级页表转换过程

虚拟地址 -> 物理地址：MMU截取 页号，根据 页号 在页表地址查询到 块号，

若命中，返回块号
若未命中，将数据从外部磁盘读入内存，并返回块号

拼接 块号 和 页内偏移，得到物理地址

加入TLB

MMU截取页号，根据页号在TLB中查询：

若TLB命中页，返回物理地址块号
若TLB未命中，查询页表
- 若页表命中，返回物理地址块号
- 若页表未命中，查询外部磁盘，将数据写入内存，并返回物理地址块号

拼接块号和页内偏移，得到物理地址

硬件

遍历页表，将虚拟地址转换为物理地址，页面权限管理等

MMU：查询TLB或者遍历页表
TLB：缓存最近转换的页表条目
页表基地址寄存器：存放页表基地址（物理地址）【对于多级页表：^作为MMU遍历多级页表的起点】

软件

不管虚拟内存如何转换为物理内存，对应用来说透明

应用程序：访问虚拟内存即可如执行指令、读写内存, 没有权限管理页表
Linux内核：填写页表，将页表基地址告诉MMU；内核初始化建立内核页表，实现缺页异常等机制为用户任务按需分配并映射页表

页表

页表属于内核空间，存放在内存上，其中存放的均为物理地址，为物理地址的 块号

Linux内核，使用的是多级页表，即存在多次转换，这增加了空间分配的灵活性，但也增加查询的复杂度，典型的时间换空间【换的是内存空间，不是存储空间】

问：为什么逻辑内存地址空间往往比物理内存地址空间大？

有MMU这个东西，可以分配虚拟地址(题中逻辑地址，下同)，再加上内核的支持，可以提升物理内存的利用率。

讲一下Linux Kernel的处理，当运行一个程序时，内核并不会把整个程序完全加载到物理内存中，而是分配好虚拟地址，加载可执行文件的部分到物理内存，只分配了虚拟地址而程序未加载到物理内存的部分，会在页表上做标记。

当程序运行到只有虚拟地址而没有对应物理内存的地方时，处理器会发生异常，然后内核就分配对应的物理内存页，把磁盘上的数据加载到物理内存，再从异常中返回，程序就能继续运行。这个过程，用户态的程序是无法感知到的。

这样，就算分配的虚拟地址大于实际的分配的物理内存也是没有问题的。通过这种机制，假设我有一个远大于物理内存的程序，也是能运行的。在系统物理内存用光的情况下，当程序运行到新的地方，而这部分只分配了虚拟地址，没有对应物理内存时，内核在缺页异常中搜索最不常执行的地方，断开物理内存与原来虚拟地址的连接，把这块物理内存分配给当前程序将要运行的新的虚拟地址，然后把磁盘上的程序加载到物理内存，这样程序又能快乐的运行了。

综上，虚拟地址会比物理地址多，而且也是有必要。计算机里有一个重要的情况，基本上很多东西都是局部的，一个程序虽大(比如我们的假设，磁盘上的程序远大于物理内存)，但经常执行的地方却不多。cache也是根据这个情况设计出来的，虽然可能只有几十兆，但是性能提升非常高。

上面说了单进程的情况，下面说说多进程的情况。多进程时，活跃的进程可能就那么几个，其他基本上在睡大觉。32位机上，每个进程都分了4g虚拟地址空间，但是真正需要全部把程序加载到物理内存的不多，或者，我一个程序原来用了很多内存，但后面不怎么运行，内核在内存紧张时，会把这部分物理内存释放掉，分配给其他用途。

前面说的是程序部分，现在说说数据部分，或者说是堆内存这块(malloc分配的)。如果这部分内存不常使用，内核会把他们丢入交换空间(swap，位于磁盘上)这个冷宫。等到真正需要时，才把数据从交换空间拿到物理内存。

综上，这几种情形，使用了虚拟地址，可以让物理内存可以使用得更高效。逻辑地址比物理地址多不言而喻了吧。

I/O 系统

外部设备硬件

独占设备：

对某些独占设备可以通过共享设备改造为共享设备【假脱机技术：在多道批处理系统中，专门利用一道程序（SPOOLing程序）来完成对设备的I/O操作。】

共享设备：

考试

基本概念
操作系统是指控制和管理计算机系统硬件与软件资源，合理地调度组织、调度计算机工作与资源分配，为用户和其他软件提供方便接口与调度环境的程序集合。
系统调用
系统资源需要从用户态切换到核心态
所有I/O都是特权指令

选择题 20 ！！！
简答题 30 = 5 * 6
- 概念简述
算法分析 50
- 算法 30
- 综合 20

前13章，前2章（基本概念，系统调用，接口，包含操作系统安全【每个进程xx空间分离，要调用使用陷进】，方便用户使用、管理系统资源、提高扩展，进程线程定义属性特点生命周期，）

操作系统接口类型
1.命令接口
提供一组命令供用户直接或间接操作。
根据作业的方式不同，命令接口又分为联机命令接口和脱机命令接口。
2.程序接口
程序接口open in new window由一组系统调用命令组成，提供一组系统调用命令供用户程序open in new window使用。
3.图形界面接口
通过图标窗口菜单open in new window 对话框及其他元素,和文字组合,在桌面open in new window上形成一个直观易懂使用方便的计算机操作环境.
CPU工作模式
？
进程结构、状态、状态转换
程序段、数据段、进程控制段；
PCB是进程的唯一标志；
进程是程序运行的过程，是系统进行资源分配和调度的独立单位
资源分配方式【抢占与否、画甘特图】
临时区原则
空则让进
忙则等待
有限等待
让权等待
死锁条件（4个条件、2个原因）
互斥条件、不可剥夺条件、请求并保持、循环等待
系统资源竞争、进程推进顺序非法
存贮体系、存贮保护（页面存贮管理、碎片、缺页置换算法优缺点、静/动态文件重定位）
文件系统，文件组织（文件结构发展）

综合题

进程同步算法 FCFS\RR\SJF\优先级\多级反馈队列\xxx（6个）
任务调度
系统安全状态检测（死锁）
页面置换算法、存贮管理方案（）
文件存贮
磁盘调度策略

理发问题、吃水果、哲学家【临界】

昵称

邮箱(可选)

网址(可选)

按正序
按倒序
按热度

操作系统概论

# 操作系统概论

# IO结构

# 两种I/O结构

# 外部接口的IO操作模式

# 中断

# DMA模式

# 硬件保护

# 双重模式操作

# 硬中断、陷阱与软中断

# I/O保护

# 内存保护

# CPU保护

# 操作系统服务

# exce 函数族

# wait()函数

# getpid()函数

# getppid()函数

# 进程

# PCB 进程控制块

# 进程调度

# 进程调度方式

# 进程的挂起态与七状态模型

# 调度基本准则

# 调度算法

# 先来先服务（FCFS）调度算法

# 短作业/进程优先（SJF/SPF）调度算法

# 优先级调度算法

# 高响应比优先调度算法

# 时间片轮转调度算法

# 多级反馈队列调度算法

# 进程通讯

# 信号

# 循环中的fork()

# 线程

# 创建线程

# CPU调度

# CPU调度程序

# 调度准则

# 优化准则

# 调度算法

# 先到先服务（FCFS）

# 最短作业优先调度（SJF）

# 时间片轮转（RR）

# 多级反馈优先队列（）

# 进程同步

# 临界区设计准则

# 算法实现

# TestAndSet 实现wait()和signal()

# Swap() 实现互斥操作

# 进程饥饿

# 死锁

# 类型

# 死锁的条件

# 处理

# 饿死与活锁

# 内存管理

# 单一连续静态分区管理

# 动态分区方案

# 碎片

# 分区管理

# 地址转换

# 页式分区

# 段式分区

# 虚拟地址

# 硬件

# 软件

# 页表

# I/O 系统

# 外部设备硬件

# 考试

预览:

操作系统概论

IO结构

两种I/O结构

外部接口的IO操作模式

中断

DMA模式

硬件保护

双重模式操作

硬中断、陷阱与软中断

I/O保护

内存保护

CPU保护

操作系统服务

exce 函数族

wait()函数

getpid()函数

getppid()函数

进程

PCB 进程控制块

进程调度

进程调度方式

进程的挂起态与七状态模型

调度基本准则

调度算法

先来先服务（FCFS）调度算法

短作业/进程优先（SJF/SPF）调度算法

优先级调度算法

高响应比优先调度算法

时间片轮转调度算法

多级反馈队列调度算法

进程通讯

信号

循环中的fork()

线程

创建线程

CPU调度

CPU调度程序

调度准则

优化准则

调度算法

先到先服务（FCFS）

最短作业优先调度（SJF）

时间片轮转（RR）

多级反馈优先队列（）

进程同步

临界区设计准则

算法实现

TestAndSet 实现wait()和signal()

Swap() 实现互斥操作

进程饥饿

死锁

类型

死锁的条件

处理

饿死与活锁

内存管理

单一连续静态分区管理

动态分区方案

碎片

分区管理

地址转换

页式分区

段式分区

虚拟地址

硬件

软件

页表

I/O 系统

外部设备硬件

考试