操作系统基础概念
- 操作系统是指控制和管理整个计算机系统的硬件与软件资源，合理的组织，调度计算机的工作与资源的分配，进而为用户和其它软件提供方便接口与环境的程序集合；
- 特征：并发（在同一间隔内，可以同时运行多个程序）、共享（资源共享）包括两种方式，一种是互斥共享，另一种是同时访问方式，两者的区别在于一段时间内是否独占资源、虚拟（利用时分复用技术或者是空分复用技术达到让用户感觉自己拥有很多处理器与内存）、异步（指运行程序不是一直运行的，而是走走停停）；
- 功能一：（1）处理机管理—进程管理（2）存储器管理—内存分配与回收，地址映射（3）I/O设备管理（4）文件管理；
- 功能二：作为用户与计算机交互的接口（1）命令接口：脱机命令接口，联机命令接口（2）程序接口（广义指令，系统调用）：用户通过一系列程序请求操作系统为其提供服务；
- 操作系统关心的是如何存储，而不是存储的内容；高级程序编译器实质其实是一段存储在系统中的程序指令；操作系统提供给应用程序的接口是系统调用；多道程序设计的基本特性不包括顺序性；计算机开机后，操作系统被加载到RAM；
操作系统的发展与分类
- 1.手工操作阶段：用户独占全机，CPU等待手工操作，利用不充分；
- 2.批处理阶段：单批道处理系统，多道批处理系统，单的话虽说是批处理，但是内存中始终只有一道作业，如果其因某些事情中断后，则处理机效率依旧低下；多的话就可以解决这种问题，一个中断就去执行另一个；
- 3.分时操作系统：把处理器运行时间分成很短的时间片，轮流为各个作业服务，具有同时性，交互性；
- 4.实时操作系统：能够保证优先级，在某些事情优先的情况下能够及时响应；
操作系统的运行环境
- 通常CPU分为两种状态，一种为内核态，另一种为用户态，内核态可以执行除访管指令的其他所有指令，而用户态只能执行一般指令；
- 原语：处在操作系统最底层，是最接近硬件的部分，程序的运行具有原子性，运行时间较短，且比较频繁；
- 中断和异常，异常也叫做内中断，包括自愿中断（指令中断）和一些硬件故障和软件中断，外中断包括外设请求和人的干预；
- 系统调用 ：因为系统中的各种共享资源都由操作系统统一掌管，所以在用户程序中，凡是与资源有关的操作，都必须通过系统调用的方式向操作系统提出服务请求；
- 通道技术（I/O设备）用户态到核心态的转化是由硬件完成的，访管指令是在用户态下进行，发生的中断可以使得从用户态转化为内存态
进程管理
2.3 进程同步
进程同步 ： 在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步。
临界资源： 一次仅同意一个进程访问的资源，包含4个区域：进入区（置标置位），临界区（访问临界资源的那段代码），退出区（清除标志位），剩余区（代码中其他部分）。
同步 ： 同步亦称直接制约关系，为完成某种任务而建立的两个或者多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待，传递信息所产生的制约关系，可以理解为B需要A才能完成下一步工作。
互斥 ：互斥也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区时，才被同意去访问此临界资源，可以理解为A和B属于平级。
同步机制： （1）空闲让进 （2） 忙则等待 （3） 有限等待 （4） 让权等待。
实现临界区软件互斥的方法
- 单标记法 （孔融让梨）设置一个公用整形变量turn，用于让谁进入临界区的标识符，缺点是一个人如果一直不进入，且另一个想进入，会造成资源浪费。
P0进程 p1进程
while (turn != 0); while (turn != 1);
critical section; critical section;
turn = 1; turn = 0;
remainder section; rematinder section;
- 双标记先检查法 （互相竞争）先看一下临界资源是否正在被访问，若正在访问，则需要等待；若没有，则进入临界区，缺点是可能出现都进入的不可控局面。
p0进程 P1进程
while (flag[j]); while (flag[i]);
flag[i] = true; flag[j] = true;
critical section; critical section;
flag[i] = FALSE; flag[j] = FALSE;
remainer section; remainer section;
- 双标记后检查法 （互相谦让）先表明自己想要访问，若对方正在访问，则等待，若没有，则进入临界区，缺点是可能会造成双方互相谦让，造成饥饿。
p0进程 P1进程
flag[i] = true; flag[j] = true;
while (flag[j]); while (flag[i]);
critical section; critical section;
flag[i] = FALSE; flag[j] = FALSE;
remainer section; remainer section;
- 皮尔森算法 设置变量turn，算法1 + 算法3
p0进程 P1进程
flag[i] = true, turn = j; flag[j] = true, turn = i;
while (flag[j] && turn == j); while (flag[i] && turn == i);
critical section; critical section;
flag[i] = FALSE; flag[j] = FALSE;
remainer section; remainer section;
实现临界区互斥硬件实现方法
- （1）中断屏蔽方法 （2）硬件指令方法
信号量 ： 包括整形信号量（表示资源数目）与记录型信号量（+进程链表）
- 利用信号量实现同步
S = 0;
P1 ()
{
x;
V(S); // 执行完后，将P2从堵塞态转化为就绪态；
}
p2 ()
{
P(S); // 无S资源，被堵塞，等待P1；
y;
}
- 利用信号量实现互斥
S = 1；
P1 （）
{
P（S）；
V（S）；
}
P2 （）
{
P （S）；
V （S）；
}
- 利用信号量实现前驱关系 前V后P， PV相互。
- 分析进程同步和互斥问题的方法步骤
1.关系分析。找出问题中多个进程数，并分析他们之间的同步或者互斥关系；
2.整理思路。找出解决问题的关键点，并根据做过的题目找出求解思路；
3.设置信号量。设置需要的信号量，确定初值，完善整理；
管程：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序。包括4部分：名称，对共享数据结构的说明，对数据结构进行操作的一组过程，对莞城内部的共享数据设置初始值的语句。
- 其实和PV操作差不多，只是进行了封装，方便人们进行操作。
经典进程的同步问题
- 生产者消费问题
问题描述：一组生产者进程和一组消费者进程共享一个初始值为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，他只同意一个生产者放入消息，或一个消费者从中取出消息
问题分析：（1）关系分析：两者对缓冲区的访问属于互斥关系，同时只有生产者生产后消费者才能消费，两者之间又是同步关系（2）整理思路：需要解决的就是互斥和同步PV操作的位置（3）信号量设置：mutex表示互斥信号量，full记录当前缓冲区“满”缓冲区数，empty记录当前缓冲池中“空”缓冲区数
mutex = 1;
empty = n;
full = 0;
producer ()
{
while (1)
{
produce an item in nextp;
p (empty);
p (mutex);
add nextp to buffer;
v (mutex);
v(full);
}
}
consumer ()
{
while (1)
{
p (full);
p (mutex);
remove an item from buffer;
v (mutex);
v (empty);
consume the item;
}
}
- 读者写者问题
问题描述：有读者和写者两组并发过程，共享一个文件，当两个或以上的读进程同时访问共享数据是不会产生副作用，但若某个写进程和其他进程同时访问共享数据时，则可能导致数据不一致的错误。因此要求：1同意多个读者可以同时对文件执行读操作；2.只同意一个写者往文件中写信息；3.任一写者在完成写操作之前不同意其他读者或写着工作；4.写者执行操作前，应让已有的读者和写者全部退出
问题分析：（1）关系分析：读者和写者互斥，写者和写者互斥，读者和读者不互斥（2）整理思路：两个进程。读者和写者，写者容易，因为写者和任何东西都是互斥的，读者在实现与写者互斥的同时，实现与其他读者的同步，这里采用一个计数器，当有读者时，写者是无法写文件的，读者会一直占用文件，没有读者时，写者才会写文件，不同读者对计数器的访问也应该是互斥的
int count = 0;
mutex = 1; // 更新count变量时的互斥
rw = 1; // 读者和写者互斥访问文件
writer ()
{
while (1)
{
P(rw);
writing;
v(rw);
}
}
reader ()
{
while (1)
{
p (mutex);
if(count == 0)
p(rw);
count ++ ;
v (mutex);
reading;
p (mutex);
count --;
if (count == 0)
v (rw);
v (mutex);
}
}
-
哲学家进餐问题
问题描述：一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子之间是一碗米饭，哲学家倾注毕生精力用于思考和进餐，哲学家在思考时并不耽误其他人，只有当哲学家饥饿时，才试图拿起左右两根筷子（一根一根拿起）若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。
问题分析：（1）关系分析：5名哲学家与左右邻居对其中间筷子的访问是互斥关系。（2）整理思路：本题的关键在于哲学家同时拿到左右两根筷子而不造成死锁或者饥饿的现象，一是让他们同时拿起筷子，二是对每名哲学家的动作制定规则，避免饥饿或者死锁现象的发生（3）信号量设置：定义互斥信号量数组，用于对5个筷子的互斥访问，哲学家i左边筷子的编号为i，哲学家右边筷子的编号为（i+ 1）% 5
chopstick[5] = {1,1,1,1,1};
Pi()
{
do {
p (chopstick[i]);
p (chopstick[(i + 1) % 5]);
eat;
v (chopstick[i]);
v (chopstick[(i + 1) % 5]);
think;
} while (1);
}
该算法的话，可能造成5个哲学家都拿起筷子，出现死锁，因此可以采取第二种方法，对哲学家进程施加一些限制条件 ，当一名哲学家左右两边筷子都可以用，才同意他抓起筷子
chopstick [5] = {1,1,1,1,1};
mutex = 1;
pi ()
{
do {
p (mutex);
p (chopstick [i]);
p (chopstick [(i + 1) % 5]);
v (mutex);
eat;
v (chopstick[i]);
v (chopstick[(i + 1) % 5]);
think;
} while (1);
}
- 吸烟者问题
问题描述 ： 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽掉他，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草，纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限的提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的卷烟这卷一根烟并抽掉他，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌子上，如此重复
问题分析：（1）关系分析：供应者与三个抽烟者是同步关系，三者抽烟者对抽烟这个动作是互斥的（2）整理思路：有四个进程，供应者作为生产者向三个抽烟者提供材料（3）信号量设置：信号量offer1，offer2，offer3分别表示烟草和纸组合的资源，烟草和胶水组合的资源，纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作
int num = 0;
offer1 = 0;
offer2 = 0;
offer3 = 0;
finish = 0;
process p1()
{
while (1)
{
num ++;
num = num % 3;
if (num == 0)
v (offer 1);
else if (num == 1)
v (offer 2);
else
v (offer 3);
p (finish);
}
}
process p2 ()
{
while (1)
{
p (offer 3);
v (finish);
}
}
process p3 ()
{
while (1)
{
p (offer 2);
v (finish);
}
}
process p3 ()
{
while (1)
{
p (offer 1);
v (finish);
}
}
🐮🐮🐮