操作系统基础·

L1 什么是操作系统·

操作系统是计算机硬件和应用之间的一层软件

管理哪些硬件？CPU 内存终端磁盘文件网络电源多核

学习OS的三个层次

学习计算机接口，从软件出发用OS
从应用软件出发进入OS
设计并实现OS

Lab0 准备工作·

配置·

准备好ubuntu20.04的机器

#安装环境
git clone https://github.com/Wangzhike/HIT-Linux-0.11.git ~/hit-oslab
cd hit-oslab
./setup.sh
#可能还需要安装这几个32位版本的软件
sudo apt-get install libsm6:i386 
sudo apt-get install libx11-6:i386
sudo apt-get install libxpm4:i386
#编译
cd ~/code
tar -zxvf hit-oslab-linux-20110823.tar.gz
cd ~/code/oslab/linux-0.11
make all 
# make自动跳过未被修改的文件，链接时直接使用上次编译生成的目标文件，从而节约编译时间
# make -j 2 多处理器加速并行编译
# make clean && make all
cd ..
./run

调试·

#汇编调试
./dbg-asm
#help查看基本命令，更详细查看Bochs使用手册
#C语言调试
./dbg-c
./rungdb

文件交换·

#挂载hdc
sudo ./mount-hdc
cd hdc
ls -al
vi hello.txt
#卸载hdc文件系统
sudo umount hdc

L2 开始揭开钢琴的盖子·

计算机本质：计算模型类似人-笔-纸给一张纸，人用笔不断地按顺序算每一道题

图灵机就是一个控制器+一个纸袋

通用图灵机是复杂的控制器控制复杂的纸带，纸带上地数据包含设置控制器动作和状态的指令以及数据对象

冯诺依曼存储程序思想：将数据和程序存放在计算机内部的存储器中，计算机在程序的控制下一步步处理

打开电源·

x86 PC：

(1)x86 PC刚开机时CPU处于实模式（寻址方式为CS左移四位+IP，CS是段地址，和保护模式不一样）

(2)开机时，CS=0xFFFF; IP=0x0000

(3)寻址0xFFFF0(ROM BIOS映射区)

(4)检查RAM，键盘，显示器，软硬磁盘

(5)将磁盘0磁道0扇区读入0x7c00处

(6)设置cs=0x07c0，ip=0x0000

0x7c00处存放的代码·

是从磁盘引导扇区读入的512个字节，也就是启动设备的第一个扇区

启动设备信息被设置在CMOS（互补金属氧化物半导体，用来存储实时钟和硬件配置信息）中

硬盘第一个扇区上存放着开机后执行的第一段可以控制的程序

bootsect.s载入setup（四个扇区）模块和system模块（OS代码）

之后跳到setup执行

L3 操作系统启动·

setup.s·

完成OS启动前的设置

取出光标位置以及其他硬件参数，比如扩展内存大小

将system模块移到0地址

进入保护模式，用GDT将cs:ip变成物理地址

保护模式下有专门的地址翻译表和中断处理函数入口

之后跳到system模块执行

head.s·

设置各种数据结构，比如数据段，系统栈，内存管理的必要数据结构，且此时是32位汇编代码，和之前16位8086不一样

设置idt，gdt

函数调用设置页表，之后进入main函数

main函数·

main的工作就是xx_init: 内存、中断、设备、时钟、CPU等内容的初始化…

关于汇编·

(1) as86汇编：能产生16位代码的Intel 8086(386)汇编·

1	mov ax, cs //cs-->ax, 目标操作数在前

(2) GNU as汇编：产生32位代码，使用AT&T系统V语法·

1 2	movl var, %eax//(var)-->%eax movb -4(%ebp), %al //取出一字节

AT&T美国电话电报公司，包含贝尔实验室等，1983年AT&T UNIX支持组发布了系统V

(3) 内嵌汇编，gcc编译x.c会产生中间结果as汇编文件x.s·

__asm__(“汇编语句”
: 输出
: 输入
: 破坏部分描述);

__asm__(“movb 
%%fs:%2, %%al”
:”=a”(_res)
:”0”(seg),”m”(*(addr))
);

0或空表示使用与相应输出一样的寄存器

a表示使用eax，并编号%0

%2表示addr，m 表示使用内存

Lab1 操作系统的引导·

实验介绍·

此次实验的基本内容是：

阅读《Linux 内核完全注释》的第 6 章，对计算机和 Linux 0.11 的引导过程进行初步的了解；
按照下面的要求改写 0.11 的引导程序 bootsect.s
有兴趣同学可以做做进入保护模式前的设置程序 setup.s。

改写 bootsect.s 主要完成如下功能：

bootsect.s 能在屏幕上打印一段提示信息“XXX is booting…”，其中 XXX 是你给自己的操作系统起的名字，例如 LZJos、Sunix 等（可以上论坛上秀秀谁的 OS 名字最帅，也可以显示一个特色 logo，以表示自己操作系统的与众不同。）

改写 setup.s 主要完成如下功能：

bootsect.s 能完成 setup.s 的载入，并跳转到 setup.s 开始地址执行。而 setup.s 向屏幕输出一行"Now we are in SETUP"。
setup.s 能获取至少一个基本的硬件参数（如内存参数、显卡参数、硬盘参数等），将其存放在内存的特定地址，并输出到屏幕上。
setup.s 不再加载 Linux 内核，保持上述信息显示在屏幕上即可。

编译与运行bootsect.s·

汇编+链接

as86 -0 -a -o bootsect.o bootsect.s
ld86 -0 -s -o bootsect bootsect.o
dd bs=1 if=bootsect of=Image skip=32 #跳过最开始的32字节的文件头信息
cp ./Image ../Image

其中 -0（注意：这是数字 0，不是字母 O）表示生成 8086 的 16 位目标程序，-a 表示生成与 GNU as 和 ld 部分兼容的代码，-s 告诉链接器 ld86 去除最后生成的可执行文件中的符号信息。

L4 操作系统接口·

接口：连接两个东西，信号转换，屏蔽细节

操作系统接口：连接上层用户和操作系统软件

用户使用计算机：命令行，图形按钮，应用程序

命令行其实就是一段程序 shell是/bin/sh

图形界面是包含画图的C程序消息框架程序+消息处理程序

OS接口：普通C代码加上一些重要的函数，OS提供这些函数也就是操作系统接口，表现为函数调用，由系统提供，称为系统调用

POSIX: Portable Operating System Interface of Unix(IEEE制定的一个标准族)

L5 系统调用的实现·

需要将内核程序和用户程序隔离区分内核态和用户态

用CS最低两位表示执行在什么态 0是内核态，3是用户态

必须CPL（CS）RPL（DS）<=DPL时才允许访问

硬件提供主动进入内核方式，对于x86：int指令将CS中CPL改成0，从而进入内核

系统调用核心：

用户程序中包含一段包含int指令的代码
操作系统写中断处理，获取想调程序的编号
操作系统根据编号执行相应代码

先设置好eax系统调用号，ebx,ecx,edx都可以存放参数，eax还存放返回值

进入set_system_gate函数，设置0x80的中断处理

进入system_call中断处理程序找到相应系统调用处理函数入口（全局数组_sys_call_table中寻找）

之后调用相应系统调用处理函数

L6 操作系统历史·

上古神机IBM7094(1955-1965)·

计算机昂贵造价在250万美元以上

专注于计算
批处理操作系统

一个作业完成，自动读入下一个作业

从IBSYS到OS/360(1965-1980)·

计算机开始进入多个行业：科学计算(IBM 7094)，银行(IBM 1401)

需要干多件事多道程序

作业的切换和调度成为核心既有IO任务，又有计算任务，需要让CPU忙碌

IBM OS/360 表示全方位服务，开发周期 5000人年

从OS/360到MULTICS(1965-1980)·

使用人数增加作业之间需要快速切换

分时系统产生代表：MIT MULTICS (MULTiplexed Information and Computer Service)

核心仍然是任务切换

从MULTICS到UNIX(1980-1990)·

小型计算机出现

1969年：贝尔实验室的Ken Thompson、 Dennis Ritchi等在一台没人使用的PDP-7上开发一个简化 MULTICS，就是后来的UNIX

UNIX是一个简化的MULTICS，核心概念差不多，但更灵活和成功

从UNIX到Linux(1990-2000)·

1981，IBM推出IBM PC；个人计算机开始普及

1987年Andrew Tanenbaum发布了MINIX(非常类似UNIX)用于教学

Linus Torvalds在386sx兼容微机上学习minix，作出小Linux于1991年发布

1994年，Linux 1.0发布并采用GPL协议，1998年以后互联网世界里展开了一场历史性的Linux产业化运动

IBSY ==> OS/360 ==> MULTICS ==> Unix ==> Linux·

核心思想、技术·

用户通过执行程序来使用计算机(吻合冯诺依曼的思想)
作为管理者，操作系统要让多个程序合理推进，就是进程管理
多进程(用户)推进时需要内存复用等等

软件实现·

对于操作系统，实现很重要OS/360==>UNIX
需要真正的群体智慧 UNIX==>Linux

多进程结构是操作系统基本图谱对于OS 实现概念比理解概念更重要

PC与DOS·

1975年Digital Research为Altair 8800开发了操作系统CP/M

CP/M：写命令让用户用，执行命令对应的程序，单任务执行

1980出现了8086 16位芯片，从CP/M基础上开发了QDOS(Quick and Dirty OS)

从QDOS到MS-DOS·

1975年，22岁的Paul Allen和20岁的 Bill Gates为Altair 8800开发了BASIC解释器，据此开创了微软

1977年Bill Gates开发FAT管理磁盘

QDOS的成功在于以CP/M为基础将BASIC和FAT包含了进来 文件管理和编程环境…都是用户关心的!

1980年IBM想和Digital Research协议授权使用CP/M，但没有达成，转向和微软合作；1981微软买下QDOS，改名为MS-DOS(Disk OS)，和IBM PC打包一起出售

从MS-DOS到Windows·

MS-DOS的磁盘、文件、命令让用方便，但似乎可以更方便

1989年，MS-DOS 4.0出现，支持了鼠标和键盘，此时微软已经决定要放弃MS-DOS

不久后Windows 3.0大获成功

后来就是一发不可收拾了，95，XP，Vista，Win 7，Win 8…

文件、开发环境、图形界面对于OS的重要性

Mac OS与iOS·

1984年，苹果推出PC(麦金塔机，Macintosh)，简称Mac机，其处理器使用IBM、Intel或AMD等，核心在于屏幕、能耗等

与Mac机一起发布System X系统，一上来就是GUI

在System 7以后改名为Mac OS 8

2007年发布iOS，核心仍然是Mac OS，专为移动设备，如手势等

Mac OS核心是UNIX，专注于界面、文件、媒体等和用户有关的内容

CP/M ==> QDOS ==> MS-DOS ==> Windows ==> Unix ==> System ==> Mac OS ==> iOS·

核心思想、技术·

仍然是程序执行、多进程、程序执行带动其他设备使用的基本结构
但用户的使用感觉倍加重视了：各种文件、编程环境、图形界面

软件实现·

如何通过文件存储代码、执行代码、操作屏幕…
如何让文件和操作变成图标、点击或触碰…

掌握、实现操作系统的多进程图谱

掌握、实现操作系统的文件操作视图

L7 学习任务·

Lab2 系统调用·

进程与线程·

L8 CPU 管理的直观想法·

让CPU工作：取指执行

让CPU充分利用：启动多个程序，交替执行

一个CPU上交替的执行多个程序：并发。让IO和计算利用率都提升

记录每个程序的信息的结构：PCB 这样才能正常切换程序

运行的程序：进程，和静态程序不一样

L9 多进程图像·

main中的fork创建了第一个进程，init执行了shell（windows桌面），shell再根据命令启动其他基本进程，返回shell再启动其他进程

Process Control Block：记录进程信息的数据结构

PCB的列表：一些进程在执行（运行），一些进程在等待执行（就绪队列），一些进程在等待某事件（硬件等待队列…）

graph LR
a[新建态]-->b[就绪态]
b-->c[运行态]
c-->d[终止态]
c-->e[阻塞态]
e-->b
c-->b

交替的三个部分：队列操作+调度（选择下一个进程）+切换（PCB信息存储和切换 schedule函数）

通过内存管理来隔绝多个进程的地址空间，地址映射，每个进程的地址被映射到特定的一块物理内存

多个进程合作：进程同步（合理的推进）给共享变量上锁

如何形成多进程图像？·

读写PCB，OS中最重要结构
操作寄存器完成切换（L10,L11,L12）
写调度程序（L13,L14）
进程同步与合作（L16,L17）
地址映射（L20）

Lab3 进程运行轨迹的跟踪与统计·

L10 用户级线程·

User Threads

是否可以资源不动切换指令序列

进程=资源+指令执行序列 1个资源+多个指令执行序列

线程：保留了并发特点，避免了进程切换代价

例子：访问网站，所有图片，文字都显示在同一屏幕，需要共享资源。多个线程分别处理不同的事。比如先下载图片，在等待图片数据的时候切换到获得文字的线程

两个线程一个栈会出现问题，需要每个线有一个栈

Yield函数先切换栈指针，再直接函数结束返回栈顶地址，不用主动jmp切换PC。需要TCB（Thread Control Block），有栈指针

两个线程：两个TCB，两个栈，切换的PC在栈中

用户级线程不会进入内核，当遇到硬件阻塞时就丧失作用。内核级线程是系统调用，会进入内核，内核知道TCB

L11 内核级线程·

多处理器：每个cpu有相应的Cache和MMU

多核：多个CPU使用相同的Cache核MMU

多进程适用于多处理器的情况，核心级线程适用于多核

核心级线程：一个栈到一套栈，包含用户栈，代码和数据，内核栈，线程控制块。TCB关联内核栈

用户栈在有中断时启动内核栈，通过TCB切换到另一个线程的TCB，再切换到B的内核栈，并通过中断返回iret到相应的B用户栈和用户代码。从一套栈切换到另一套栈

内核线程switch_to的五段论·

中断入口：进入切换

中断处理：引发切换

找到目的TCB，线程调度

完成内核栈切换

完成第二级切换，切换用户栈和用户执行地址

L12 核心级线程实现实例·

tss：task structure segment

长跳转至TSS段选择符造成CPU执行任务切换操作，相当于把当前所有寄存器内容放在当前TR寄存器所在的段中，之后将TR切换到新的描述符，从而同时切换所有的寄存器值

fork中的函数copy_process，创建栈：申请内存空间，创建TCB，创建内核栈和用户栈，填写两个stack，关联栈和TCB

fork是父进程创建子进程/子内核级线程可以共用用户栈

子进程中fork返回值为0，父进程不为0 修改%eax的值！！

L13 操作系统的那棵树·

研究复杂系统：从一个小点出发，做成一颗大树。从一个小想法开始，提出新问题，解决新问题并不断完善。

运转CPU：取指执行。

没有好好运转？交替执行，引入多进程。切换跳转需要使用栈来实现。

一个栈进行切换造成了混乱？采用2个栈+2个TCB，Yield找到下一个TCB，找到新的栈，切换新的栈

遇到中断阻塞就麻烦了，引入内核栈的切换。

实现idea，从一个简单清晰目标出发，交替打印A和B

发散思维适合创新，线性思维适合执行工作

L14 CPU调度策略·

获得next进程

FIFO 先进先出：简单有效银行食堂常用

需要优先级，任务很短/很长的应该怎么调度

要让进程满意：

尽快结束任务：周转时间短（任务进入到任务结束）
操作尽快响应：响应时间短（从操作发生到响应）
系统内耗时间少：吞吐量（完成的任务量）

原则：专注于任务执行，又能合理调配任务

吞吐量和响应时间有矛盾（响应时间小，切换时间多，系统内耗大，吞吐量小）

前台任务和后台任务关注点不同（前台关注响应时间，后台关注周转时间）

IO约束型任务和CPU约束型任务有各自特点

First Come First Served FCFS 先来先服务·

类似FIFO

SJF 短作业优先·

平均周转时间最短

考虑响应时间：RR 按照时间片来轮转调度·

时间片大响应时间太长，时间片小，吞吐量小

同时考虑响应时间和周转时间·

定义前台任务和后台任务两个队列，前台RR，后台SJF 前台任务没有时才调度后台任务

后台有可能一直分配不到

L15 一个实际的schedule函数·

counter既用来表示优先级，也表示时间片

经过IO以后，counter变大，IO时间越长，counter越大，照顾了IO进程。IO进程每次中断阻塞时，会被设置成counter初值+当前counter的一半，从而越来越大，从而提高优先级

后台进程一直按照counter轮转，近似了SJF调度。每次时间片用完才重置，因为没有IO，不需要阻塞！

Lab4 基于内核栈切换的进程切换·

L16 进程同步与信号量·

进程合作：多进程共同完成一个任务

生产者消费者实例

核心：等待

利用信息量决定睡眠和唤醒

例子：一种资源的数量是8，这个资源对应的信号量的当前值是2，说明有2个资源可以使用

如果是-2，说明有2个进程在等待这个资源

struct semaphore
{
    int value;//记录资源个数
    PCB* queue;//记录等待在该信号量上的进程
}

P(semaphore s)//消费资源
{
    s.value--;
    if(s.value<0){
        sleep(s.queue);
    }
}

V(semaphore s)//产生资源
{
    s.value++;
    if(s.value<=0){
        wakeup(s.queue);
    }
}

生产者消费者模式实例·

semaphore full = 0; 
semaphore empty = BUFFER_SIZE;
semaphore mutex = 1;

Producer(item) 
{
    P(empty);
    P(mutex); 
    读入in;将item写入到in的位置上;
    V(mutex);
    V(full); 
}

Consumer() 
{
    P(full); 
    P(mutex);
    读入out;从文件中的out位置读出到item;打印item;
    V(mutex);
    V(empty); 
}

L17 对信号量的临界区保护·

多个生产者共同修改信号量可能会出问题

解决竞争条件：给共享变量上锁

一段代码一次只允许一个进程进入原子操作

临界区：一次只允许一个进程进入的一段代码

进出上锁，退出开锁

基本原则：互斥进入

好的保护原则：

有空让进
有限等待

以下代码临界区表示进入条件

进入临界区一个尝试：轮换法·

一个跑完了修改标志让另一个可以进入

//A
//临界区
while (turn!=0); 
//剩余区
turn = 1;
//B
//临界区
while (turn!=1);
//剩余区
turn = 0;

改进：标记法·

//A
//临界区
flag[0]=true
while(flag[1]);
//剩余区
flag[0]=false;
//B
//临界区
flag[1]=true
while(flag[0]);
//剩余区
flag[1]=false;

再一次尝试：非对称标记

进入临界区Peterson算法·

结合标记和轮状两种思想

//临界区
flag[i]=true
turn=j
while(flag[j]&&turn==j);
//剩余区
flag[i]=false;

多个进程：面包店算法·

轮转：每个进程都获得一个序号，序号最小的进入

标记：进程离开时序号为0，不为0的序号即为标记

choosing[i] = true; num[i] = max(num[0], …, num[n-1])+1;
choosing[i] = false; 
for(j=0; j<n; j++) 
{ 
    while(choosing[j]);
	while ((num[j] != 0) && (num[j], j)<(num[i], i])); 
}

num[i] = 0;

临界区保护的另一类解法·

硬件实现：

//临界区
cli(); 
//剩余区
sti();

多CPU不能使用

控制能否产生中断，阻止被调度

硬件原子指令法·

boolean TestAndSet(boolean &x)
{
    boolean rv = x;
    x = true;
    return rv;
} //一次执行完毕 不管是什么都设置成true

while(TestAndSet(&lock)) ;
//临界区
lock = false;
//剩余区

L18 信号量的代码实现·

if lock导致只能逐个唤醒

sys_sem_wait(int sd){
    cli();
    if(semtable[sd].value -- < 0)
    {
        设置自己为阻塞;
        将自己加入semtable[sd].queue中;
        schedule();
    }
    sti(); 
}

while lock可以让许多进程一起竞争，同时唤醒因为中断返回可以继续竞争锁

lock_buffer(buffer_head*bh)
{
	cli();
    while(bh->b_lock)
    	sleep_on(&bh->b_wait);
    bh->b_lock = 1;
    sti(); 
}

L19 死锁处理·

互相等待对方持有的资源造成所有进程都无法执行的情况

死锁必要条件：互斥使用不可抢占（只能资源放弃）请求和保持（占有资源了，再去申请其他资源）循环等待

处理方法：死锁预防（破坏死锁出现的条件）死锁避免（检测每个资源请求，如果造成死锁就拒绝）死锁检测+恢复（检测到，让一些进程回滚，让出资源）死锁忽略

死锁预防·

一次性申请所有需要的资源，不会占有资源再申请其他资源
- 需要预知未来，编程困难
- 许多资源分配后很长时间才使用，资源利用率低
对资源类型进行排序，资源申请必须按序进行，不会出现环路等待
- 仍然造成资源浪费

死锁避免·

如果系统中所有进程存在一个可完成的执行序列P1，P2…,Pn，则称系统处于安全状态

安全序列：执行序列P1…Pn

找安全序列的银行家算法·

每次根据每种资源剩余数量和每个进程需要资源数量，寻找一个可以完成的进程，并把它的资源释放，再观察是否有可以完成的，直到找不到或者全部进程完成。

int Available[1..m]; //每种资源剩余数量
int Allocation[1..n,1..m]; //已分配资源数量
int Need[1..n,1..m];//进程还需的各种资源数量
int Work[1..m]; //工作向量
bool Finish [1..n]; //进程是否结束
Work = Available; Finish[1..n] = false; 
while(true){ 
    for(i=1; i<=n; i++){
        if(Finish[i]==false && Need[i]£Work){
            Work = Work + Allocation[i];
            Finish[i] = true; 
            break;
        }
        else {
            goto end;
        }
    } 
}
End: for(i=1;i<=n;i++) 
if(Finish[i]==false) return “deadlock”;

实际使用：每次有新进程进入，就将它和当前其他进程做计算。每次都是$O(mn^2)$复杂度

死锁检测+恢复：发现问题再处理·

发现问题再处理。定时检测或者发现资源利用率低时检测

实现回滚比较困难

许多通用操作系统上都采用死锁忽略方法，可以用重新启动的方式解决死锁问题

Lab5 信号量的实现和应用·

内存管理·

L20 内存使用与分段·

内存使用：程序放在内存中，执行程序

程序中的地址是逻辑地址（相对地址）需要转换为内存中真实的物理地址 也就是重定位

什么时候完成重定位？编译时（嵌入式，静态硬件设备）载入时（更加灵活）

编译时重定位：程序只能放在内存固定位置，效率高

载入时重定位：程序一旦载入内存就不能动了，但需要修改地址，稍微慢一些

但程序载入后还需要移动，因为内存有限，可能某个阻塞的进程需要和磁盘中的进程交换

重定位最佳时机：运行时重定位 每执行一条指令都要从逻辑地址算出物理地址：地址翻译

PCB中存储着base基址执行指令时第一步先从PCB中取出基址

每个进程寻找一段空闲内存，将基址放在PCB中每次取址执行，需要找到PCB中的基址切换进程时根据PCB切换，一起切换基地址

整个程序一起载入内存？不太可能程序由若干段组成，每个段有各自的特点用途

比如程序段（只读）数据段（可写）堆栈

分段：程序的各个段分别放入内存

PCB中要存储进程段表（LDT） OS对应的进程段表也就是GDT表

包含段号基址长度允许操作（读/写）

ldtr 段表寄存器

L21 内存分区与分页·

如何找到空闲的区域？

程序分段，找到空闲分区，PCB中存储映射段和内存地址的映射表

固定分区：OS初始化时，内存等分成k个分区但需求不一样

可变分区：大小不一样，动态变化

可变分区管理：请求分配包含空闲分区表（起始地址和长度）和已分配分区表（起始地址，长度，分配给的段标志）

OS中没有非黑即白的东西，要分析优缺点

有多个空闲分区时，选择空闲分区的方式：首先适配（复杂度低），最佳适配（容易产生小间隙），最差适配（分区均匀）

引入分页：解决内存分区导致的内存效率问题

分区其实和虚拟内存对应，物理内存使用分页管理

可变分区造成有很多内存碎片将空闲分区合并，需要移动一个段：内存紧缩（无法执行用户进程，相当于死机）实际使用不可行

从连续到离散：让内存没有碎片类似将面包切成片，将内存分成页

针对每个段内存请求，系统一页一页的分配给这个段（物理内存按照每4K作为一页）

根据页表来查页表寄存器 cr3

包含：页号（逻辑页号）页框号（物理页号）保护标记（读写）

利用mmu将逻辑地址转换为页号（物理实现）

逻辑地址向右移12位得到页号，查表得到页框号，利用页框号和逻辑地址低12位相拼接得到物理地址

每个段放在多个页

L22 多级页表和快表·

页比较小则页表就大了

页表放置成了问题 基本想法：连续存放所有逻辑页号对应的物理页号

大部分逻辑地址根本不会使用 第一种尝试：只存放用到的页 用到的逻辑页才有页表项

页表中的页号不连续可以折半，但是需要查多次内存

大页表占用内存，造成浪费既要连续也要让页表占用内存少==>使用多级页表 借鉴书籍的章节思想

即逻辑地址划分为页目录号(10bits) 页号(10bits) 地址偏移(12bits)

每个页目录项指向一个4M的空间（指向1K个页表项），每个页表项指向4KB的空间

提高空间效率，时间上每增加一级，访问内存次数增加一次

快表TLB：组相联快速存储，寄存器包含有效标记页号修改标记保护页框号

利用物理电路将页号直接映射到物理页号，速度快

有效访问时间=HitR*(TLB+MA)+(1-HitR)*(TLB+2MA) HitR命中率

程序地址访问存在局部性空间局部性，每次对某一段内存访问率高

L23 段页结合的实际内存管理·

程序段映射到地址空间地址空间再映射到物理页

也就是将程序段和虚拟内存映射，再将虚拟内存和物理内存映射（多级页表机制）

段面向用户，页面向硬件

代码中的cs:ip是虚拟内存

用户眼里包含操作系统段，用户数据段，用户代码段，用户堆栈段

地址翻译·

用户：cs:ip 段号+偏移

映射到段表，段表中包含段号基址长度保护标记 获得了基址之后加上偏移得到了虚拟地址

再将虚拟地址用多级页表映射到物理内存地址

实际内存管理·

分配段建段表找到空闲物理页分配页页表映射

进程带动内存使用

段表和页表设置好，执行指令时MMU自动完成地址翻译

fork：将一段新的虚拟内存分配给子进程（LDT），同时和父进程的物理内存完成映射，复制父进程页表

L24 内存换入-请求调页·

为了实现虚拟内存，需要实现换入换出

换入换出实现大内存比如虚拟内存是4G，物理内存为2G

将不同的虚拟内存地址映射到相同地址的物理内存请求的时候才映射（换入）

请求一个地址，地址缺页，对页做标记，需要中断来调入页面即页错误处理程序

从磁盘中找到相应程序，将程序载入换入对应的物理内存页中，设置好页表中的映射

实际的请求调页

L25 内存换出（页表置换）·

如果找不到空闲的物理页，则需要选择一页进行淘汰，换出到磁盘

实例：分配3个页框，页面引用序列为：A B C A B D A D B C B

FIFO 最简单·

A AB ABC ABC ABC DBC DAC DAC DAB CAB CAB

每次换出最早来的页面

存在7次缺页

MIN 最优·

A AB ABC ABC ABC ABD ABD ABD ABD CBD CBD

选最远将使用的页淘汰，是最优方案

存在5次缺页

LRU 折中最优·

用过去的历史预测未来 LRU：选取最近最长一段时间没有使用的页淘汰（最近最少使用）

A AB ABC ABC ABC ABD ABD ABD ABD CBD CBD

LRU是对局部性的认识和归纳

5次缺页

LRU 准确实现用时间戳·

每页维护一个时间戳

每个时间周期使用某一页时将这个页的时间戳更新为当前时间

之后需要替换时，将时间戳最小的淘汰

	A	B	C	A	B	D	A	D	B	C
A	1	1	1	4	4	4	7	7	7	7
B	0	2	2	2	5	5	5	5	9	9
C	0	0	3	3	3	3	3	3	3	10
D	0	0	0	0	0	6	6	8	8	8

每次地址访问都需要修改时间戳，需要维护一个全局时钟，需要找到最小值，实现代价很大

LRU 准确实现用页面栈·

维护一个页码队列

每次淘汰队头

每次地址访问需要修改栈（比如修改指针）

LRU近似实现-将时间计数变为是和否·

每页增加一个引用位（reference bit）

每次访问一页时，硬件自动设置该位

选择淘汰页：扫描该位，是1时清零，并继续扫描，是0时淘汰该页

组织成循环队列

再给一次机会（second chance replacement）算法

更改为最近没有使用

clock算法的分析和改造·

缺页很少，就会导致所有的R=1，从而退化成FIFO

不能记录太长的历史信息定时清除R位再来一个扫描指针

清除R位的移动速度快

选择淘汰页的指针移动速度慢

给进程分配多少页框（帧frame）·

分配太多，请求调页导致内存高效利用就没用了

分配太少，缺页太多，系统颠簸

计算工作集，设置进程的页框

进程数量，页框数量都要进行限制

补充：Clock算法·

是一种LRU的近似算法，是一种性能和开销较均衡的算法。由于LRU算法需要较多的硬件支持，采用CLOCK置换算法只需相对较少的硬件支持。又称为最近未用算法（NRU）

简单的CLOCK置换算法·

实现方法：

（1）为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列

（2）当某页被访问时，其访问位置为1

（3）当需要淘汰一个页面时，只需检查页的访问位：如果是0，选择此页换出；如果是1，将它置0，暂不换出，继续检查下一个页面

（4）若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0，再进行第二轮扫描，第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描

改进型的CLOCK置换算法·

引入：简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
思想：因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。
实现方法：修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。为方便讨论，用（访问位，修改位）的形式表示各页面状态。
算法规则：将所有可能被置换的页面排成一个循环队列

第一轮:从当前位置开始扫描到第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位

第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为0

第三轮:若第二轮扫描失败，则重新扫描，查找第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位

第四轮:若第三轮扫描失败，则重新扫描，查找第一个(0,1）的帧用于替换

注意：由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描

Lab6 地址映射与共享·

设备驱动与文件系统·

L26 I/O 与显示器·

让外设工作起来发出写命令到总线上，显卡或硬件驱动设备收到就进行相应操作也就是向设备控制器的寄存器写（out指令）

发出写命令（输出）
向CPU发出中断（输入）
读数据到内存

操作系统要形成简单的视图-文件视图

一段操作外设的程序

不管什么设备都是open read write close

根据设备文件名进行相应处理 open(“/dev/xxx”) 找到控制器的地址、内容格式等等

系统调用-相应文件的处理程序-具体设备的操作

open系统调用·

解析目录，找到inode 文件信息

PCB中的filp列表对应于一个文件指针列表，每个文件指针对应了一个文件的信息

向屏幕输出·

sys_write判断是否为字符设备转到rw_char函数

crw_table字符接口设备中找到相应读写函数地址tty_write 实现输出的核心函数

往缓冲区写字符最终读入缓冲区内容放入tty的队列中

最后通过con_write方法将字符放到显存的寄存器中统一编址用mov，独立编址使用out

L27 键盘·

从键盘中断开始

inb指令读入扫描码即对应了哪个按键

跳转到相应函数，根据相应函数得到key_map

从key_map中取出ASCII码将ASCII码放入缓冲队列头部 con.read_q

键盘中断处理程序再将ASCII码回写

Lab7 终端设备的控制·

L28 生磁盘的使用·

移动机械臂到相应柱面（磁道） 旋转磁盘将扇区和磁头对应，之后确定缓存位置 磁生电读，电生磁写

head：其实是磁盘圆柱的横截面中的每个扇形的标志（很多个圆）

cyl：是柱面，也就是一个圆柱体的侧面（展开是矩形）

sec：扇区

通过盘块号读写磁盘（一层抽象）·

磁盘驱动将block计算出cyl head sec

磁盘访问时间=写入控制器时间+寻道时间+旋转时间+传输时间 寻道时间最长，且无法显著提升

block相邻的盘块应该可以快速读出 ==> 相邻盘块尽量在同一个磁道上

磁盘读写扇区单位是扇区但是每次读入多个扇区，也就是一个盘块block

应用读入的单位是盘块 OS将盘块转为连续的若干个扇区CHS，从而读入连续的多个扇区，连续的扇区数是固定的，相当于一个盘块=n个扇区

block=C*(Heads*Sectors)+H*Sectors+S

S=block%Sectors

多个进程通过队列使用磁盘（二层抽象）·

多个请求将盘块号放在请求队列上

磁盘中断从队列中取出

磁盘调度·

调度目标是平均访问延迟小寻道时间是主要矛盾

对磁道进行考查看总的磁道移动数量

FCFS
SSTF 短寻道优先每次访问离得最近的磁道不适合读写频繁的程序，存在饥饿
SCAN=SSTF+中途不回折找到一个最近的磁道往那个方向处理完所有请求，再往回
C-SCAN=SCAN+直接移到另一端：两端请求都能很快处理

从简单算法出发，用主要矛盾和指标着手，发现如何改进

(1) 进程“得到盘块号”，算出扇区号(sector)

(2) 用扇区号make req，用电梯算法add_request

(3) 进程sleep_on

(4) 磁盘中断处理，唤醒进程

(5) do_hd_request算出cyl,head,sector

(6) hd_out调用outp(…)完成端口写

L29 从生磁盘到文件·

引入文件，对磁盘使用的第三层抽象·

文件抽象成一个字符流，按照行和列的形式组织成书-文件

建立字符流到盘块集合的映射关系

连续结构来实现文件·

文件的FCB：文件名起始块块数

将文件中的某个字符和某一块中的某个数据做映射

链式结构实现文件·

文件FCB：文件名起始块

文件长度增减容易，顺序访问慢

索引结构实现文件·

inode==>文件FCB：文件名索引块

索引块处有文件的每个块的索引

先读入索引块位置，再找在哪个具体的位置查

实际系统是多级索引·

重要且少的文件直接读，有的文件有一阶，二阶，三阶间接索引

很小的文件高效访问，也可以表示很大的文件

L30 文件使用磁盘的实现·

file_write(inode,file,buf,count)

inode==>FCB 找到盘块号

file==>有一个读写指针，是开始地址，再加上count（fseek就是修改这个指针）

用盘块号，buf等形成request放入队列

设备文件的inode和普通文件不一样包含文件类型属性

从文件/路径名找到inode 根据inode找到盘块号根据盘块号放入请求队列根据请求队列算出CHS 根据out发到磁盘驱动器上

第一条路读写磁盘第二条路输出到显示器

L31 目录与文件系统·

文件，抽象一个磁盘块集合建立字符流到盘块集合的映射

文件系统抽象整个磁盘第四层抽象·

所有文件一层太乱

引入目录树 k次划分后，每次集合中的文件数为$O(log_kN)$ 引入目录，表示一个文件集合

目录树中完成从路径名到FCB的映射

目录树中存储FCB的指针==>编号

磁盘分为引导块超级块 inode节点位图+盘块位图（表示是否空闲） inode节点+数据区

也可以分为引导快超级块位图 FCB数组数据盘块

目录项：文件名+对应FCB地址

根据某个目录的FCB找到数据盘块中的目录项，又对应相对应的FCB，继续找数据盘块中的目录项，直到找到文件

FCB数组第一个是根目录 “/” 找到数据块，匹配里面的每个文件名，再找到相应的FCB，循环往复一直找到对应的文件

inode位图：哪些inode空闲，哪些被占用盘块位图：哪些盘块空闲，硬盘大小不同这个位图大小不同空闲位图：位向量

超级块：记录两个位图有多大等信息

L32 目录解析代码实现·

其实目录解析就是如何open 找到inode读入内存

get_dir完成目录解析

初始化将根目录挂载进来

操作系统全图·

多进程视图 多进程交替执行程序 CPU忙碌起来取指执行

程序执行需要操作内存，从而对内存进行管理段页合作

程序执行还需要操作磁盘或者其他外设，需要将他们抽象成文件 文件视图

操作系统基础·

L1 什么是操作系统·

Lab0 准备工作·

相关链接·

配置·

调试·

文件交换·

L2 开始揭开钢琴的盖子·

打开电源·

0x7c00处存放的代码·

L3 操作系统启动·

setup.s·

head.s·

main函数·

关于汇编·

(1) as86汇编：能产生16位代码的Intel 8086(386)汇编·

(2) GNU as汇编：产生32位代码，使用AT&T系统V语法·

(3) 内嵌汇编，gcc编译x.c会产生中间结果as汇编文件x.s·

Lab1 操作系统的引导·

实验介绍·

编译与运行bootsect.s·

L4 操作系统接口·

L5 系统调用的实现·

L6 操作系统历史·

上古神机IBM7094(1955-1965)·

从IBSYS到OS/360(1965-1980)·

从OS/360到MULTICS(1965-1980)·

从MULTICS到UNIX(1980-1990)·

从UNIX到Linux(1990-2000)·

IBSY ==> OS/360 ==> MULTICS ==> Unix ==> Linux·

核心思想、技术·

软件实现·

PC与DOS·

从QDOS到MS-DOS·

从MS-DOS到Windows·

Mac OS与iOS·

CP/M ==> QDOS ==> MS-DOS ==> Windows ==> Unix ==> System ==> Mac OS ==> iOS·

核心思想、技术·

软件实现·

L7 学习任务·

Lab2 系统调用·

进程与线程·

L8 CPU 管理的直观想法·

L9 多进程图像·

如何形成多进程图像？·

Lab3 进程运行轨迹的跟踪与统计·

L10 用户级线程·

L11 内核级线程·

内核线程switch_to的五段论·

L12 核心级线程实现实例·

L13 操作系统的那棵树·

L14 CPU调度策略·

First Come First Served FCFS 先来先服务·

SJF 短作业优先·

考虑响应时间：RR 按照时间片来轮转调度·

同时考虑响应时间和周转时间·

L15 一个实际的schedule函数·

Lab4 基于内核栈切换的进程切换·

L16 进程同步与信号量·

生产者消费者模式实例·

L17 对信号量的临界区保护·

进入临界区一个尝试：轮换法·

改进：标记法·

进入临界区Peterson算法·

多个进程：面包店算法·

临界区保护的另一类解法·

硬件原子指令法·

L18 信号量的代码实现·

L19 死锁处理·

死锁预防·

死锁避免·

找安全序列的银行家算法·

死锁检测+恢复：发现问题再处理·

Lab5 信号量的实现和应用·

内存管理·

L20 内存使用与分段·

L21 内存分区与分页·

L22 多级页表和快表·

L23 段页结合的实际内存管理·

地址翻译·

LRU 准确实现用时间戳·

LRU 准确实现用页面栈·

文件系统抽象整个磁盘第四层抽象·