操作系统结构

操作系统

是一组控制和管理计算机软硬件资源，合理地对各类作业进行调度及方便用户使用的程序集合，是计算机的第一层软件。

系统结构

• 简单结构
• 模块化结构
• 层次结构
• 微内核结构

启动过程

1. 打开电源
2. CPU通过系统时钟初始化
3. 在BIOS中找到启动程序的CPU的第一条指令
4. 执行开机自检(POST)，检查所有硬件设备

I/O操作

IO设备可以和CPU同时执行 - I/O在设备和控制器缓存（controller's buffer）之间转移数据 - CPU在控制器和主存之间转移数据。

I/O设备访问 - Memory Mapped I/O（CPU就像访问内存一样访问I/O） - Programmed I/O（每个控制寄存器都分配一个I/O端口号，CPU使用特定的I/O指令去读写寄存器）。

操作系统的服务

• 程序执行 Program execution
• I/O操作 I/O operations
• 文件系统的操作 File-system manipulation
• Communications 在进程间传递消息

• 错误检测 Error detection

• 资源分配 Resource allocation

• 账号管理 Accounting
• 保护 Protection

系统组件

• Process Management
• Memory Management
• File Management
• I/O System Management
• Secondary Management
• Networking
• Protection System
• Command-Interpreter System

---

Process 进程

进程 Process

a program in execution一个执行过程中的程序，是资源分配的单位。

• Program（executable）：磁盘上的passive实体
• Process：active entity被激活的实体，包含程序计数器、栈、堆、文本、数据。

程序 Program

一个程序包含Code、Data、DLLs 动态链接库、mapped files。

Process vs Program

• 两个进程可能和同一个程序相关联

• 两条单独执行的顺序

• 文本部分相同，数据、堆、栈都不同

进程状态

• running：指令正在执行
• waiting：进程等待某个事件发生

• ready：进程等待分配给CPU

• new：进程被创建

• terminated：进程结束执行

进程控制块（PCB）

和每个进程相关联的信息，包含：

• Process state 进程状态
• Program counter 程序计数器
• CPU register 寄存器：为了能让CPU离开进程后回来还能执行
• CPU scheduling information CPU调度信息
• Memory-management information 内存管理信息

进程调度

• 长程调度Long-term scheduling(or job scheduling)：从job queue中选一个到ready queue中,内存可用时,从磁盘中移出一个到内存。
• 短程调度Short-term scheduling(or CPU scheduling)：从ready queue中选一个到running，内存到执行。
• 中程调度(Medium-term scheduling)：CPU和内存资源管理的混合
• 中断处理(Interrupt handling)：从waiting到ready

进程通信

• shared memory 共享内存
• message passing 消息传递

---

Threads 线程

进程是资源的拥有者，线程用来调度任务，是CPU的调度单位。

• 独立的 PC, Register, Stack pointer
• 共享的 Code, Data, File

两类线程

• 用户级线程，所有线程在user space中完成
• 核心级线程，OS直接执行

多线程编程

响应度高，资源共享，能够充分利用多处理器体系结构。包括了多对一，一对一，多对多线程模型。

---

CPU Scheduling

调度类型

• 非抢占式 ：1.从running到waiting，2.Terminates
• 抢占式：1.从waiting到ready，2.从running到ready

如何调度

1. 切换上下文
2. 转换为use mode
3. 跳转到用户程序中的适当位置来重启程序

Scheduling criteria 性能指标

• Max CPU utilization——让CPU越忙越好
• Max Throughput——单位时间内能完成的进程个数越多越好
• Min Turnround time——周转时间越短越好
• Min Waiting time——等待时间
• Min Response time——响应时间指从请求提交到第一个相应产生，并非输出产生

常用调度算法

• FCFS（First-Come, First-Served ）：FCFS最简单，是非抢占式的，进程按照请求CPU的顺序排序。
• SJF（Shortest Job First）：也是非抢占式的，如果运行时间事先已知，可以每次挑选最短的任务以避免小进程等待大进程释放的情况。SJF最优是可以证明的。但是难以得知下次CPU请求的长度，只能预测。一般通过数学期望 $t_{n+1}=at_{n}+(1-a)t_{n}$ 来确定。
• Priority（Priority Scheduling）：可以是抢占式的，也可以是非抢占式的，优先级最高的进程被选出来运行。最大的问题是可能会出现无限等待或starvation，优先级低的可能永远无法运行。可以使用老化(aging)进行解决，即每执行一个周期就把当前进程优先级降一下。
• RR （Round-Robin Scheduling）：先给定时间片（time quantum）的大小。Case 1: CPU burst <= one time quantum，执行完就退出执行其他任务；Case 2: CPU burst > one time quantum，执行不完将该任务放到队尾。

---

Process Synchronization

临界区问题

每个进程拥有的操作共享数据的代码称为critical section 临界区。要保证当一个进程执行时它的临界区代码时，其他进程不能执行临界区代码。

解决方案：在执行之前加点条件，判断能否执行，执行完毕后解锁.

do{
    entry section   //执行前判断
        crical section
    exit section    //执行完毕后解锁
        reminder section
}

解决临界区问题需要满足

• Mutual Exclusion 互斥

• Progress 前进原则,如果没有临界区代码在执行，有一个进程想进入临界区是，应当允许

• Bounded wait 有限等待,想进入临界区的在有限时间内总能进入。

信号量Semaphores

信号量 一个整形变量，只能通过两个标准原子操作：wait()，signal()。

// wait(s):
while(s<=0)
;   //no-operation
s--;

//signal(s):
s++

在wait()和signal()操作中，对信号量的修改必须是原子的，即当一个进程修改信号量值时，不能有其他进程同时修改同一信号的值。

//初始化：int matex=1; 
do {
    wait(mutex);
    //critical section
    signal(mutex);
    //remainder section
} while(1);

信号量实现

主要缺点是忙等待，即当一个进程位于其临界区内时，其他想进入临界区的进程必须连续循环等待，浪费了CPU时钟。也称为自旋锁。为了克服忙等待，可以使用阻塞并放入等待队列的操作。通过wakeup()来重新执行。

//定义一个新结构
typedef struct {
    int value;
    struct process *List;
} semaphore;

//新的信号量操作定义
wait(semaphore *S){
    S.value--;
    if(S.value<0) {
        block();    //add this process to S.List
    }
}

signal(semaphore *S) {
    S.value++;
    if(S.value<=0) {
        wakeup(P);  //remove a process P from S.List
    }
}

读写者问题

1. 写者、读者互斥访问文件资源。
2. 多个读者可以同时访问文件资源。
3. 只允许一个写者访问文件资源。

读者优先

• 没有读者会因为有一个写者在等待而去等待其他读者的完成
• 写者执行写操作前，应该让所有读者和写者退出
• 除非有一个写者在访问临界区，其他情况下，读者不应该等待

//初始化变量
BINARY_SEMAPHORE wrt=1;
BINARY_SEMAPHORE mutex=1;
int readcount=0;

//Reader:
do {
    wait(mutex);      //Allow 1 reader in entry
    readcount=readcount+1;
    if(readcount==1)
        wait(wrt);    //1st reader locks writer
    signal(mutex);
        //reading operation
    wait(mutex);
    readcount=readcount-1;
    if(readcount==0)
        signal(wrt);    //last reader frees writer
    signal(mutex);
}

//Writer:
do {
    wait(wrt);
        //writing operation
    signal(wrt);
}

写者优先

如果一个写者等待访问对象，那么不会有新读者开始读操作。

//初始化变量
BINARY_SEMAPHORE read=1;    //使有写者进行操作时读者等待
BINARY_SEMAPHORE file=1;    //使文件操作互斥
BINARY_SEMAPHORE mutex1=1;  //使改变readcount的方法互斥
BINARY_SEMAPHORE mutex2=1;  //使改变writecount的方法互斥
int readcount=0;
int writecount=0;

//Reader:
do {
    wait(read);         //等待直至读者队列没有阻塞，即全部写者都退出，同时自身进入后再次上锁，使后来的读者等待，因为接下来要进行一系列互斥的操作
    wait(mutex1);
    readcount++;
    if(readcount==1)    //第一个读者进入
        wait(file);     //后来的写者无法操作文件，但对后来的读者的文件操作不造成影响
    signal(mutex1);
    signal(read);       //释放
        //read operation
    wait(mutex1);
    readcount--;
    if(readcount==0)
        signal(file);
    signal(mutex1);
}

//Writer:
do {
    wait(mutex2);
    writecount++;
    if(writecount==1)   //第一个写者进入
        wait(read);     //阻塞读者队列
    signal(mutex2);
    wait(file);
        //write operation
    signal(file);
    wait(mutex2);
    writecount--;
    if(writecount==0)   //最后一个写者退出
        signal(read);   //释放读者队列
    signal(mutex2);
}

哲学家进餐问题

5个哲学家围着桌子吃饭，筷子只有5枝，分别在每个哲学家的左手边和右手边。哲学家必须得到两只筷子才能吃饭，要使每个哲学家都能吃到饭，该如何调度。

// 管程实现
void philosopher(int i) {   //主方法
    while(true) {
        thinking();
        dp.pickup(i);
        eating();
        dp.putdown(i);
    }
}

monitor dp {
    enum{thinking,hungry,eating} state[5];
    condition self[5];
    void pickup(int i) {
        state[i]=hungry;    //设置本人为饥饿状态
        test[i];            //测试左右两个人是否在吃
        if(state[i]!=eating)//如果需要等待
            self[i].wait(); //进入等待，在pickup方法处阻塞
    }
    void putdown(int i) {
        state[i]=thinking;
        test((i+4)%5);      
        test((i+1)%5);      //本人放下筷子后，状态发生了变化，测试左右两个是否等待吃，如有，则给他们开始吃的机会（但也不一定能马上开始吃）
    }
    void test(int i) {
        if((state[(i+4)%5]!=eating) && (state[i]==hungry) && (state[(i+1)%5]!=eating)) {     //如果左右两个人并没有在吃，而且自己处于饥饿状态
            state[i]=eating;    //设置状态为eating
            self[i].signal();   //释放pickup方法，在philosopher方法中下一步将执行eating操作
        }
    }
    initializationCode() {
        for(int i=0;i<5;i++)
            state[i]=thinking;
    }
}

生产者消费者问题

一个生产者，一个消费者，库存有限，如何能持续生产？解决方法：对于生产者，如果缓存是满的就去睡觉。消费者从缓存中取走数据后就叫醒生产者，让它再次将缓存填满。若消费者发现缓存是空的，就去睡觉了。下一轮中生产者将数据写入后就叫醒消费者。

伪代码

// 初始化变量：
semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲库存空间
semaphore full=0;  //库存初始化为空


//生产者进程：
producer ()
{
    while(1)
    {
        produce an item in nextp;  //生产数据
        P(empty);  //获取空闲库存单元
        P(mutex);  //进入临界区.
        add nextp to buffer;  //将数据放入缓冲区
        V(mutex);  //离开临界区,释放互斥信号量
        V(full);  //库存数加1
    }
}

//消费者进程：
consumer ()
{
    while(1)
    {
        P(full);  //获取库存数单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  //从库存中取出数据
        V (mutex);  //离开临界区，释放互斥信号量
        V (empty) ;  //空闲库存数加1
        consume the item;  //消费数据
    }
}

---

Deadlock

死锁的必要条件

• Mutual exclusion 互斥访问
• Hold and wait 占有和等待
• No preemption 非抢占
• Circular wait 循环等待

处理死锁的方法：忽略，预防，避免，检测恢复

死锁预防：使死锁条件不成立。

1. 打破互斥，不是所有的资源都行

2. 打破Hold and wait，在运行前把所有所需资源拿来（不容易），请求资源时把占有的资源都释放（很好）。

3. 打破非抢占，不可能

4. 打破循环等待，和hold and wait类似，有序的 资源访问。

死锁避免：判断请求在未来是否出现死锁（Banker's Algorithm 银行家算法）

• 每个新进程必须声明它所需每种资源的最大实例数

• 进程请求时，系统必须确认是否分配资源会让系统不安全

• 当一个进程得到所有所需资源后，它必须在有限时间内归还

死锁检测

• 等待图：每种资源类型只有单个实例的情况
• 与银行家算法类似的检测算法：每种资源类型可有多个实例的情况。

死锁恢复

• 终止所有死锁进程
• 一次只终止一个进程，知道取消死锁循环为止

---

Memory management

存储类型

• Main memory 主存
• Secondary storage 辅存

地址表示

• 逻辑地址（Logical address）： CPU生成 也叫Virtual address
• 物理地址（Physical address） ：实际在内存中的地址

内存分配

• 首次适应First-fit：分配按地址顺序的第一个可用的hole
• 最佳适应Best-fit：放到最小的足够大的hole
• 最差适应Worst-fit：放到最大的hole

First-fit通常比Best-fit好，First-fit和Best-fit通常比Worst-fit好

外部碎片

不同进程间还未分配出去的小内存空间，单个碎片无法分配给任何一个进程。外部碎片存在于可变分区、段式虚拟存储系统(分段存储 Segmentation)中，主要是可变分区。

内部碎片

已经被分配出去的大于请求所需的内存空间部分，在固定分区中表现为分区内进程未使用的内存空间。无法重新利用，只能被浪费。内部碎片存在于固定分区、页式虚拟存储系统（分页存储 Paging)中，主要是固定分区。

Paging 分页

• 把物理内存分为大小相等的块，称为Frame（帧）
• 把逻辑内存分为大小相等的块，称为Page（页） 页的大小和帧相同
• 追踪所有空闲帧，必要时可以找到n个空闲帧加载进程
• 建立 Page table（页表） 记录Page和Frame的映射 页表的数据列只有一列

CPU产生的地址被分为

分页的特点

• 清楚划分物理地址和逻辑地址
• 动态重定位
• 没有外部碎片，但会有一些内部碎片（最后一页）
• Page大小通常在4KB-8KB

TLB

一种支持并行搜索的高速硬件，先在TLB里面查，如果页号在里面，就取出相应的帧号，如果不在再去内存的页表找。

分段

分为大小不同的段，用来存一组相对完整的逻辑信息，逻辑地址包含 <段号，偏移>

段表

• Segment-table base register(STBR) 指向段表起始位置
• Segment-table length register(STLR) 指明段数量

---

Virtual memory

虚拟内存：将用户逻辑内存从物理内存分离

• 只有部分程序需要在内存中执行
• 因此逻辑内存空间可以比内存空间大很多
• 允许地址空间被多个进程共享

按需分页：当需要的时候才把页放入内存

页面置换

1. 在磁盘上找到需要的页的位置
2. 在内存上找到空闲帧
3. 如果没有，放一个牺牲帧到磁盘
4. 将页放入空闲帧，更新页表

页置换算法

• FIFO：先进先出
• OPT：置换最长时间不会使用的页
• LRU：置换最近最少从访问的页
• Clock：两次机会

系统颠簸

内存没有足够帧，进程忙于交换页，此时CPU利用率极低。

---

File system

文件系统

• 存大量数据

• 进程停止后数据能保存

• 多个进程可以并发访问

文件系统架构（自上而下）

层级	操作、实例
App, Programs	发出文件请求的代码
Logical File System	OS最高层。保护、安全、文件名解析
File-organization Module	逻辑块
Basic File System	具体文件块
I/O Control	驱动、中断
Devices	Disk,tapes

分配磁盘块方法

• Contiguous allocation 连续分配
• Linked allocation 链接分配
• Indexed allocation 索引分配

空闲空间管理

• 空闲表法

• Bit vector 位示图法

• Linked list 空闲链表法

---

I/O System

I/O Device

• Block devices 块设备：由于信息的存取总是以数据块为单位的，所以存储信息的设备称为块设备，如硬盘，每个都有自己的地址，可寻址。
• Character devices 字符设备：用于数据输入输出的设备为字符设备，因为其传输的基本单位是字符，如打印机，不可寻址。

I/O software layers

• 中断处理
• 设备驱动
• 设备无关的I/O软件

Kernel I/O Subsystem

• Scheduling
• Buffering 缓冲，在设备传输时存数据，解决设备速度不一致。
• Caching 缓存，快速存储数据备份。
• Spooling，保存设备输出。

---

Disk 磁盘

磁盘结构

磁盘物理地址：<磁头号，磁道号，扇区号>

访问时间

访问时间有两部分：1、Seek time 磁头寻道时间。2、Rotational latency 磁盘转到合适位置需要的时间。

磁盘调度算法

FCFS：遵循先来先服务原则。

SSTF：最短寻道时间优先 离磁头当前位置最近的优先。

SCAN ：先按一个方向移动至边界，再换另一个方向移动。

C-SCAN：先向一个方向移动至边界，直接到磁盘开始位置，再按同一方向移动。

LOOk：先按一个方向移动，到最远请求为止，再换另一个方向移动。

C-LOOK：先向一个方向移动，回来到最远的访问点，再按同一方向移动。