第一章 操作系统概述

1，操作系统定义：操作系统(Operating System)使计算机系统中的一个<mark>系统软件</mark>，是一些程序模块的集合，它能以尽量有效，合理的方式<mark>组织和管理计算机的软硬件资源</mark>，合理组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使得计算机系统高效地运行。（没有广泛接受的标准定义）
2，操作系统中一些名词解释

操作系统中存在中断，共享，并发，竞争等情况
1,中断处理过程

第二章：进程

进程（process）定义：进程是一个具有一定独立功能的<mark>程序或程序段</mark>在一组数据集合上的一次<mark>动态执行</mark>
进程=程序+执行
进程包括程序，数据和进程控制块
2.1进程状态

一次只能有一个进程在处理器上运行（running）；
但是多个进程可以处于等待或就绪状态。

2.1.3进程控制块(process Control Block)
PCB包括进程控状态，进程计数器，CPU计数器等等
2.1.4线程
一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据
2.2进程调度
当有多个进程时，进程调度器（process scheduler)选择一个可用进程到CPU上执行，剩下的需要等待CPU空闲并重新调度。
2.2.1调度队列
进程在进入系统时，会被加入到作业队列（job queue),这个队列包括系统内的所有进程。
2.2.2上下文切换
中断（intirrput）导致CPU从执行当前任务改变到执行内核程序。
切换CPU到另一个进程需要保存当前进程状态和恢复另一个进程的状态为上下文切换（context switch)
2.3进程创建
2.3.1进程运行
大多数操作系统对进程的识别采用的是唯一的进程标识符（process identifier,pid)

3进程同步

3.1关于临界区问题名词解释

3.2临界区问题解决方案要满足的要求
①互斥（mutual exclusion）:如果进程Pi在临界区内执行，那么其他进程都不能在临界区内执行。
②同步（progress）：如果没有进程在临界区内执行，并且有进程需要进入临界区，那么只有那些不在剩余区执行的进程可以参加选择，以便确定谁能下一次进入临界区，而且这种选择不能无限推迟
③有限等待（bounded wating）：进程等待进入临界区的时间有范围，不会是无限大。
3.3解决临界区问题方法
①抢占式内核（preemptive kerbel）：允许处于内核模式的进程被抢占，处于内核模式的进程会一直运行，直到退出内核模式，阻塞或自愿放弃CPU控制。
②非抢占式内核（nopreemptive kerbel）:不允许处于内核模式下的进程被抢占
3.4.1Peterson解决方案（软件方法）

解释：设置两个进程共享数据项
int turn ;
boolean flag[2];
j=1-i;
两个进程P0和P1
过程

缺点：1，只适用于两个线程 2，现代计算机体系结构不支持
3.4.2硬件同步（硬件方法）
方法一 —>中断屏蔽方法
进入临界区前执行"<mark>关中断</mark>"指令
离开临界区后执行"<mark>开中断</mark>"指令
优点：简单有效
缺点：不适用于多处理器（耗时）
方法二–>测试并设置指令
前提：test_and_set()时原子的（执行不可中断）

为每个临界资源设置一个lock，初始为false
解释：当一个临界资源未被使用时，lock等于false，程序可以执行while下面的语句，当lock等于true时，test_and_set(&lock)函数返回值为true，程序在while中空转
3.4.3互斥锁（mutex lock）（软件方法）
互斥锁：一个进程进入临界区时得到锁，在它退出临界区时释放锁，函数acquire()获得锁，函数release()释放锁，每个互斥锁都有一个布尔变量available,它表示锁是否可用
互斥锁实现要求qcquire（）和release（）的调用必须是原子地执行

进程互斥访问示例

缺点：忙等待（busy wating），一个进程在临界区中其他任何进程都必须等待
3.6信号量（semaphore）
信号量S是一个整型变量，它的初始化通过两个标准原子操作wait()和signal(),wait()也叫P操作，signal()也叫V操作
wait（）函数体定义

wati(S)
{
   
while(S<=0);   //忙等待
S--；
}

signal()函数体定义

signal()
{
   
S++;
}

缺点：不满足让权等待（当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。）
3.4.5信号量的使用和实现
信号量使用改进(重新定义)

typedef struct
{
   
int value;
struct process *list;
}semaphore
//每一个信号量都有一个整数value和一个进程链表list，当一个进程必须等待信号量时，就被添加带进程链表，操作signal()从等待进程链表上取走进程，并加以唤醒

wait(semaphore *S)
{
   
S->value--;
if(S->value<0)
{
   
add this process to S->list;
block();
}
}

signal(semaphore *S)
{
   
S->value++;
if(S->value<=0)
{
   
remove a process P from S->list;
wakeup(P);
}
}

3.4.6死锁与饥饿
死锁：两个或多个进程无限等待一个事件，而该事件这些等待进程之一来完成，这些进程称为死锁
3.5经典同步问题
3.5.1生产者-消费者问题
3.5.2读者-作者问题
3.5.3哲学家就餐问题
3.6管程
管程定义：指关于贡献资源的数据及其在其上操作的一组过程或共享数据结构及其规定的所有操作（没听懂）
管程能够保证在任何时候最多只有一个线程（进程）操作管程中的代码

4进程调度

4.1 CPU-I/O执行周期
进程执行：包括周期进行CPU执行和I/O等待，进程在这两个状态下不断交替，进程执行从CPU执行开始，之后I/O执行，；接着另一个CPU执行，接着另一个I/O执行；
4.1.2 CPU调度程序
当CPU空闲时，操作系统就从队列中选择一个进程来执行并尾气分配CPU。
4.1.3抢占调度
需要CPU调度的四种情况
1，一个进程从运行态到等待状态
2，一个进程从运行状态到就绪状态
3，一个进程从等待状态到就绪状态
4，一个进程终止时
如果调度只发生在第1或4种情况，则调度是非抢占的，否则是抢占的，在非抢占调度下，一个进程在分配到CPU时，会一直运行直到终止或切换状态
4.1.4调度程序
调度程序功能：
1，切换上下文
2，切换到用户模式
3，跳转到用户程序的合适位置，以便重新启动程序

调度程序应尽可能快，调度程序停止一个进程而启动另一个进程所需要的时间称为调度延迟（dispatch latency）
4.2调度准则

4.3调度算法
4.3.1先到先服务调度
先到先服务调度（first-Come First_Served,FCFS）
先请求CPU的进程首先分配到CPU，当一个进程进入就绪队列时，他的PCB会被链接到队列尾部，当CPU空闲时，他会分配给队列头部的进程，并且这个运行进程从队列中移除
FSFS策略优点：简单，容易理解
FSFS策略缺点：平均等待时间长