操作系统期末预习笔记

whye

本课程教学采用的是32位操作系统

什么是操作系统

通用图灵机：操作+数据等于处理结果

冯诺依曼计算机：存储器储存指令（操作），控制器（通用图灵机）读取处理

开机

cs=0xFFFF,IP=0x0000

寻址0xFFFF0（cs:ip=cs<<4+ip）

检查硬件

boot.s->setup.s->system(head.s->main.c)

读入磁盘0x7c00（操作系统引导扇区）

cs=0x7c0,ip=0x0000

setup.s最后2条指令

mov ax,0x0001 mov cr0,ax

jmpi 0，8

IP=0，CS=8，由于普通的寻址模式最多只能寻址1MB内存空间，因此改用32位机最多寻址4G内存空间，32位寻址模式也称为保护模式。mov cr0,ax 将cr0寄存器最后一位置1，切换到保护模式

GDT：全局描述表，可以理解为一个储存了段地址的数组，CS中的值作为下标从这个数组中取出段地址。全局、唯一的，它的入口地址存放在GDTR寄存器中。该表由setup.s进行初始化

在8086/8088时期，都是16位的CPU，没有工作模式之分，有16位的寄存器，16位的数据总线，20位的地址总线，使用“Segment:Offset“寻址方式，具有1MB的寻址能力。
在80286以后出现实模式和保护模式的区别，实模式主要是为了兼容之前的CPU架构，可以运行之前的软件，寻址方式和寻址能力和8086CPU相同。依照CPU的设计规则，之后的X86CPU都是在实模式下启动。
而到了Intel 80386，CPU真正具有32位的寄存器，32位的地址总线，一个寄存器就具有具有4GB的寻址能力。但为了兼容80x86之前的机器，8086以后的机器启动后仍然进入实模式下，由16位段寄存器的内容乘以16（10H）当做段基地址，加上16位偏移地址形成20位的物理地址，最大寻址空间1MB，最大分段64KB。之后需要手动的切换到保护模式下。
保护模式与实模式相比，主要是两个差别：一是提供了段间的保护机制，防止程序间胡乱访问地址带来的问题，二是访问的内存空间变大，80386具有32位寄存器，寻址可达到4GB。

LDT：与GDT相对的，local的描述表，段选择子，也就是保护模式下的CS中有一个标志位标志了要从LDT还是GDT中选择段描述符，相应的，ldtr寄存器储存了LDT表的入口地址。

IDT：中断描述符，记录了中断号与调用函数之间的关系

/bin/sh

while(1){
    scanf("%S",cmd);
    if(!fork()){
       exec(cmd);
    }
    else{
        wait();
    }
}

系统调用接口手册：POSIX

系统调用实现

用户态和内核态

用户段和内核段

DPL目的权限级别

CPL当前权限级别

CS的最低2位表示权限级别，0表示内核态，3表示用户态

DPL>=CPL才能执行，因为权限级别数字越小，权限越高。

内核态程序的DPL在head.s中设置的GDT表中设为0。

计算机提供用户态进入内核态唯一的方法是int中断。

//部分中断将CS中的CPL置为0，进入内核态。

中断本身的DPL设为3供用户态调用，用户态调用中断后，中断将CPL设为0，让用户态进入内核态。

系统调用的核心：

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

将一个系统调用号置给eax寄存器后调用int 0x80中断进入内核，0x80中断调用system_call函数，system_call函数设置DS=ES=0x10，进入内核的数据段，然后调用sys_call_table函数传入eax寄存器，即系统调用号调用相应的系统调用 。

批处理->多进程->分时系统

CPU如何工作

存在IO操作导致CPU工作效率大大降低，CPU需要等待IO操作。

因此存在多道程序在内存中，交替执行，遇到等待的时候切换到别的程序执行。

多道程序，交替执行。

程序切换时需要保护现场，每个程序有一个存放信息的结构：PCB

运行状态的程序称为进程。

进程管理

进程的状态

新建态-》就绪态-》运行态-》阻塞态-》终止态(进程状态图)

内存映射表，为了防止多进程之间互相影响，设置了内存映射表位进程分配内存。可以实现逻辑地址相同，物理地址不同。通过映射表来实现多进程的地址空间分离。

通过锁来保障操作的原子性（只要涉及了多个进程同时（宏观上同时）使用同一个资源，都需要保证操作的原子性）。

进程切换函数

schedule()

schedule(){
    pNew = getNext(ReadyQueue);
    switch_to(pCur,pNew);   
}

进程交替的三个部分：队列操作，调度，切换

两个基本进程调度算法：FIFO（先进先出），Priority（存在优先级算法）

进程交替时将物理CPU里的信息写入PCB，保护现场

多进程的合作

生产者P和消费者C进程，PC模型。

生产者向共享内存中写入数据，消费者从共享内存中读取数据。

由于多进程的存在，产生了类似条件竞争的情况，因此要保证操作的原子性。如给counter上锁。进程切换前检查锁。

线程

在程序切换时，只切换指令代码不切换资源（即不更换内存映射表），可以提高执行效率，这样的每一组指令称为一个线程。线程保存了并发的优点同时减少了切换的开销。

和进程的区别，进程不光需要切换指令还要切换资源，线程只切换指令不切换资源。

例如浏览器对文本，图片，视频的下载解析使用不同的线程。

用户级线程

Create创建线程，Yield让出执行权限。

线程栈

如果在A线程中调用a函数，执行前需要将当前状态压栈，记S1，然后执行a函数中的yield()时跳到B线程，跳之前也需要压栈，记S2，线程B调用b函数，压栈记S3，b函数调用yield()函数跳回到A线程a函数处（因为是并发执行的，B线程的yield切回到A线程时继续上一次执行到的地方执行下去），跳转之前也要压栈，记S4，然后A线程的a函数执行完后需要返回到A线程调用a函数处继续执行，此时需要出栈S1，但是实际上确实出栈S4，这里出现了问题。

如何解决这个问题，即使用线程栈。每个线程使用单独的栈空间，就不会出现上述情况。既线程之间共享内存但不共享栈。

yield切换时，先切换栈指针再切换指令指针。

TCB：线程级全局，储存各个线程的栈指针（栈顶）。

注意在Yield函数中，不进行指令指针跳转，只进行TCB切换，这样在Yield函数结束时需要出栈，此时弹出的就是上一次目标线程跳出时压栈的内容。

由于Yield不进行指令跳转，指令跳转依赖栈指针，因此Create函数需要执行的工作为

• 初始化线程TCB
• 初始化线程栈
• 指令指针压栈
• 线程栈指针赋给线程TCB

用户级线程的缺点

用户级线程在内核看来还是串行程序，而需要访问硬件资源时必须要经过内核。假设进程A有a1,a2两个用户级线程，a1需要用到硬件资源如网卡，磁盘，需要经过内核，内核执行到此处时，认为进程A需要等待硬件，就会将进程A切换到阻塞态并切换到进程等待队列里的其他进程执行，此时进程A中的a2线程在用户级看来可以和线程a1并行执行，但是进程A被切换为阻塞态，a2无法和a1并行执行，只能等待a1请求的硬件资源响应后进程A回到就绪态，继续执行时才能执行。

内核级线程并发性优于用户级线程。

内核级线程

多处理器与多核的区别：

多处理器不光有多个CPU，还有相应的cache和MMU，而多核只有多个cpu，共享cache和MMU（内存管理单元）。而共享MMU和cache也就是线程。

并行：在共同的MMU和cache上同时执行（多核）。

并发：宏观并行，微观交替执行。

一组代码，既要在用户态运行，又要在内核级调用内核资源，因此一个线程需要用户栈和内核栈。代码执行在用户态，用户栈，一旦触发中断，立即切换到内核态，内核栈，由硬件完成。

内核级线程切换

五步：

• 中断进入切换（INT）
• 硬件操作/中断引发阻塞
• 找到下一个线程
• 内核栈切换（TCB）
• 跳出内核态到用户态（IRET）

ThreadCreate()函数完成内核级线程创建，与create类似，但是多了初始化内核栈，链接内核栈和用户栈的步骤。

用户栈提供给用户使用，而内核级线程切换时用户级保护现场由内核栈完成，即用户态寄存器数据压入内核栈。

在linux0.11中，内核级线程切换时，切换指令并不进行线程切换，而是修改PCB中的state，切换指令执行完由后续指令判断state和时间片（counter）决定是否跳转到reschedule进行切换。在linux0.11中，state=0为运行/就绪态，非0为阻塞态。

reschedule首先将出口指令（ret_from_sys_call）入栈，然后调用_schedule函数，该函数完成（TCB）切换后出栈出口指令跳出到用户态完成切换。

ret_from_sys_call实际上完成的是一串pop指令。pop完成后调用iret完成跳出，跳出到目标线程的用户态。

内核栈切换，TSS/knlsock

• TSS代码简单但是执行效率低，只在linux0.11等简单操作系统中使用。直接切换TSS即可，在GDT表中找到下一个线程的TSS段，赋给TR寄存器即可。TSS段内储存了对应进程/线程上依次切出时的现场。用户级现场保存在内核栈，内核级线程保存至TSS。TSS储存了全部寄存器的信息，包括ESP和EBP所指向的内核栈地址。TSS是TCB的一个子段，TCB是PCB的一部分。缺点：TSS描述符储存在GDT中， GDT大小存在限制；执行速度慢。

threadcreate创建由父进程创建子线程，首先调用copy_process完成PCB内存申请（get_free_page），然后完成PCB中TSS设置，tss.esp0/tss.ss0为内核栈，tss.esp/tss.ss为用户栈。copy_process复制线程时子线程和父进程共享用户栈。父子线程中的%eax不同，子线程%eax=0，ret相同都指向中断的下一条指令，而fork函数中int下一条指令为mov res, %eax，再由if(!fork())判断语句执行不同的父子线程代码。例如shell进程代码

int main(int argc, char * argv[]){
    while(1) {
        scanf("%s", cmd);
    }
    if(!fork()){
        exec(cmd);
    }
    wait(0);
}

上面代码中，在exec(cmd)一行执行前，父子线程执行的代码完全相同，代码exec(cmd)一行时，子线程进入exec，父线程跳过，子线程执行完exec后，应该跳转到与父进程不同的部分去执行，因此会修改内核栈中的iret。也就是在中断返回之前将需要执行的代码IP赋给iret，例如执行ls，那么将ls首行指令（a_entry）地址赋给iret。

上述过程中进程和线程等价，因为进程和线程的区别在于是否共享资源，而指令切换部分相同。并且linux0.11不支持内核级线程。

CPU管理（进程管理）+内存管理构成OSkernel

CPU调度

CPU调度关心的问题

• 周转时间短（从任务进入到任务结束）
• 响应时间短（从操作发生到响应）
• 内耗时间少

CPU调度算法的关键在于对各个方面的取舍和折中。

如果需要响应时间短，那么时间片就要小，即切换次数多，增加系统内耗，导致周转时间变长。

相对来说应该优先执行IO约束型任务，这样可以更好地让CPU和磁盘并行起来。一般来说IO约束型任务都是前台任务，这样有缩短了前台任务的响应时间，提高了用户体验。

FIFO

先进先出，最简单的调度算法。

FCFS

First Come，First Served

SJF

短作业优先，将短任务提前，缩短周转时间。

例如0-10-39-42-49-61到0-10-12-42-49-61，这里将第二个任务和第三个任务调换顺序，不会影响其他任务，但是会让任务三提前完成。

SJF算法周转时间最小。

RR

轮转调度

使用时间片，时间片10-100ms，切换时间0.1-1ms。提高响应时间。

分队列

前台后台程序使用不同的调度算法，前台使用RR，后台使用SJF，提高了前台程序的响应时间和后台程序的周转时间。前后台程序之间使用优先级。

动态优先级

以上算法均采用固定的优先级策略，可能会产生某个后台任务提交后一直得不到执行。

一个实际的schedule()函数

void Schedule(void){
    while(1){
        c = -1;
        next = 0;
        i = NR+TASKS;
        p = &task[NR_TASKS];
        while(--i){
            if(*p->state == TASK_RUNNING&&(*p)->counter>c){
                c = (*p)->counter;next = i;//找出最大的counter
            }
        }
        if(c) break;
        for(p=&LAST_TASK;p->&FIRST_TASK;--p){
            (*p)->counter = ((*p)->counter>>1)+(*p)->priority;//如果依次遍历没有找到就绪且时间片不会空的进程，则将所有进程时间片/2+初值。这样就绪态时间片置为初值，阻塞态时间片置为初值+现值/2，阻塞态程序时间片大于就绪态程序。后续执行时优先执行现在为阻塞态的程序，如IO读操作导致阻塞的程序，一般这样的程序为前台程序，提前执行可以提高用户体验。counter既是时间片又是优先级。
        }
        switch_to(next);
    }
}

可以证明如果一个进程第一次加载后一直阻塞，那么其时间片大于其他所有进程，并且收敛与2p（priority），这样保证了周转时间小于等于2np。由于时间片小于2p，长作业需要经过多个周期才能完成，而短作业很快就能完成，近似实现了SJF调度。每个进程只需要维护一个counter变量。

进程同步

进程间的合作，即某个进程需要依赖其他进程提供的资源。

如果没有信号量

//生产者
while(true){
    if(counter==BUFFER_SIZE)
        sleep();
    ...
    counter = counter+1;
    if(counter == 1)
        wakeup(消费者);
}

//消费者
while(true){
    if(counter==0)
        sleep();
    ...
    counter = counter-1;
    if(counter == BUFFER_SIZE)
        wakeup(生产者);
}

为了避免冲突，消费者每次wakeup只能唤醒一个生产者。如果有多个生产者在等待，那么唤醒其中一个生产者后，消费者继续执行，此时如果被唤醒的生产者还没有生产新的资源，那么此时counter = BUFFER_SIZE-1，下一次消费者执行到wakeup的判断时，counter= BUFFER_SIZE-2，不能唤醒后续的生产者，这里产生了非预期的问题。

信号量

从上面的例子可以知道，仅仅依靠一个信号并不能很好的解决进程间的同步问题，因此引入了信号量。

在消费者和生产者的共享缓冲区中加入一个sem/empty信号量记录当前等待的生产者/消费者数量，再由两个等待队列储存等待中的生产者/消费者，每次执行时通过判断sem/empty的值来决定是否执行唤醒。可以使用正的sem/empty表示空闲的缓冲区数量，负的sem/empty表示等待的消费者数量。除此之外信号量中还需要一个mutex锁，用来保证操作的互斥性。

最简单得信号量可以选择三个变量，empty表示剩余的缓冲区，full表示已使用的缓冲区，mutex表示可供操作（保证读写互斥）。

临界区

由于信号量被多个生产者/消费者共同控制，也就是被多个进程共同控制，因此产生了条件竞争的可能。

要避免条件竞争的出现，可以通过上锁的方式来保证操作的原子性。

对于进程A和进程B，他们都含有操作empty的代码，但是由于要保证操作的原子性，一次只能允许一个进程执行他们相应部分的代码，这部分代码被称为临界区。临界区总是在两个或多个进程中成对出现。读写信号量的代码一定是临界区。

为了保证信号量操作的原子性，需要在进入和退出临界区时加入进入区（如加锁、检查锁）和退出区（如开锁）代码来保护临界区。

临界区代码的保护原则：

• 基本原则：互斥进入；
• 有空让进：尽快让后续任务进入临界区；
• 有限等待：从请求发出进入请求到允许进入，不能无限等待。

临界区保护的一些方法

轮换法/值日法

通过某个全局变量来决定允许进入的进行。满足互斥进入，但不满足有空让进和有限等待。

//进程A
whlie(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算法

结合了标记和轮转两种思想。

//进程A
flag[0] = true;
trun = 1;
while(flag[1]&&trun ==1 );
//临界区
flag[0] = false;
//剩余区


//进程B
flag[1] = true;
turn = 0;
while(flag[0]&&turn == 0);
//临界区
flag[1] = false;
//剩余区

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

flag保证了不会有多个进程同时进入临界区，turn保证了有空让进和有限等待。

如果在flag置true后，turn置j前，进程B切换到A，会导致A无法进入临界区，但是切换到B后，B仍然能够进入临界区，B退出临界区后，A又能进入临界区。

面包店算法

多进程标记+轮转

每个进程期望进入临界区时获得一个序号，序号最小的进入临界区，退出临界区时释放序号。

choosing[i] = true;//声明正在选号
num[i] = max(num)+1;//选出num中最大的序号+1
choosing[i] = false;//选号结束
for(j=0;j<n;j++){
    while(choosing[j]);//有人正在选号，等待
    while((num[j]!=0)&&(num[j]<num[i]));//不是序号最小的.等待
}
//临界区
num[i] = 0;//释放序号

• 互斥性：只有序号最小的才能进入临界区；
• 有空让进，如果没有人在临界区中，最小序号的进程一定能够进入临界区；
• 有限等待：离开临界区时释放序号，下次进入重新取最大的号，释放后序号。

硬件方法

关中断

之所以会产生冲突，是由于进程交替执行，而进程切换需要中断，如果能够关闭中断，就能够保证操作的原子性。

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

关中断需要硬件的支持。

在单CPU系统中可以使用这种方式，但在多CPU系统中无效。

硬件原子指令

通过硬件的方式来保证造作的原子性。

boolean TestAndSet(boolean &x){
    boolean rv = x;
    x = true;
    return rv;
}

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

信号量的代码实现

理论代码

//生产者模型
Producer(item){
    P(empty);
    ...
    V(full);
}

//用户态程序
main(){
    sd = sem_open("empty");//获取相应得信号量
    for(i=1 to 5){
        sem_wait(sd);//向共享缓冲区写入需要修改信号量
        write(fd,&i,4);
    }
}

typedef struct{
    char name[20];
    int value;//empty/sem
    task_struct * queue;
} semtable[20];//内核中的全局变量

sys_sem_open(char *name){
    在semtable中寻找name信号量
    如果存在则返回对应得下标
    否则创建
}

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

linux0.11中的信号量实现

睡眠机制

bread(int dev , int block){
    struct buffer_head * bh;//申请内存缓冲区
    ll_rw_block(READ, bh);//启动读命令
    wait_on_buffer(bh);//在缓冲区内睡眠
}//读磁盘操作
//启动读磁盘以后睡眠，等待磁盘读完由磁盘中断将其唤醒。

lock_buffer(buffer_head * bh){
    cli();
    while(bh->b_lock)//检查锁
        sleep_on(&bh->b_wait);//在缓冲区的b_wait队列上睡眠
    bh->b_lock = 1;//给缓冲区上锁，解锁由磁盘中断完成
    sti();
}


void sleep_on(struct task_struct **p){
    struct task_struct * tmp;
    tmp = *p;//将队首指针赋给tmp
    *p = current;//将当前进程（的PCB）赋给*p
    current->state = TASK_UNINTERRUPTIBLE;//修改状态为阻塞
    schedule();//切换到别的进程
    if(tmp)
        tmp->state = 0;
}

队首赋给tmp，当前进程赋给p，切换到别的进程后，当前进程执行现场需要储存到栈中，由于信号量实在内核中实现的，因此需要储存到内核栈。将当前进程入队，分为两步，将当前进程设为队首，建立当前进程与原队首的连接。sleep_on函数的参数为b_wait，也就是缓冲区中等待队列的队首地址，在sleep_on函数*p = current一行完成了队首的切换。切换队首后，再次访问b_wait就是当前进程（PCB）的地址，在PCB中可以找到当前进程的内核栈，tmp也储存在当前进程的内核栈中，而tmp就指向原队首的地址，这样就建立了当前进程与原队首的连接。

唤醒机制

static void read_intr(void){
    ...
    end_request(1);
}
end_request(int uptodate){
    ...
    unlock_buffer(CURRENT->bh);
}
unlock_buffer(struct buffer_head * bh){
    bh->b_lock = 0;
    wake_up(&bh->b->wait);//唤醒等待队列的队首
}
wake_up(struct task_struct **p){
    if(p && *p){
        (**p).state = 0;将等待队列队首state置0，唤醒队首
        *p = NULL;
    }
}

在进程唤醒后将会继续执行，执行时从上次切出处继续执行，切出命令为schedule()，而schedule后的if会唤醒队列当前进程的下一个进程，下一个进程又会唤醒下下个，最终唤醒全部进程。

理论上的信号量实现是用if唤醒进程，但是if只能唤醒一个即最先进入的进程（先进先出），但是实际可能各个进程优先级不同，存在后进入的进程优先级更高的情况，因此唤醒所有进程，然后根据优先级选择执行的进程。

所有的进程都唤醒后，再通过上面while(bh->b_lock)判断，由于优先级高的会先执行，先通过这个校验然后执行bh->b_lock = 1;后续进程无法再通过while校验，继续睡眠。

这里还是存在一个问题，每个进程都是由它前面的一个进程唤醒的，那么唤醒它之前必须先执行它前面的进程，实际上还是队列前面的进程先执行。要解决这个问题需要在每一个if唤醒前面的进程后都进行一次schedule切换。

死锁处理

死锁产生

Producer(item){
    P(mutex);//mutex:1->0;//可以操作
    P(empty);//empty:0->-1;//不能操作，阻塞
//操作
    V(mutex);
    V(full);
}

Consumer(){
    P(mutex);//mutex:0->-1//进入阻塞
    P(full);
//操作
    V(mutex);
    V(empty);
}

Producer要想进入就绪态，需要Consumer执行V(empty)。Cousumer要想执行，需要Producer执行V(mutex)，产生了互相等待，即死锁的情况。要避免死锁要求重要的资源（mutex）后占有，先释放。

死锁出现的原因：每个进程都占有的部分资源，而每个进程所持有的资源不足以完成自身的任务，同时又不愿意释放自身所持有的资源。

死锁的四个必要条件

• 互斥使用
• 不可抢占
• 请求和保持
• 循环等待

死锁处理

死锁预防

破坏死锁出现的必要条件

一次申请

在进程执行前，一次性申请所有需要的资源，不会出现占有部分资源再等待另一部分资源的情况。

缺点：如果后续操作存在分支，可能执行其中一条，但是需要申请所有资源，降低使用效率，提高编程难度；部分资源可能申请后很久才会使用，降低资源利用率。

资源排序

对资源进行排序，必须先申请低级资源再申请高级资源。不会出现持有高级资源等待低级资源的情况。

缺点：资源利用率低，例如需要使用10号资源，需要先申请前9个资源；可能部分高级资源由进程本身提供。此条存疑，可能不会出现这种情况。

死锁避免

检测每个资源请求，如果会造成死锁就拒绝该请求

银行家算法

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

安全序列：满足上述条件的执行序列。

不存在一个安全序列的状态称为不安全状态，不安全状态不一定会导致死锁。在进程执行前，系统并不能准确地预测到进程执行所需要的资源（由于条件语句的存在），可能部分分支需要的资源并不会被用到，但操作系统计算时仍认为这是一个必须的资源。

由当前存在的资源选择下一个执行的进程，再判断下一个进程执行后释放相应资源后能否继续执行后续进程。如果能一直执行下去，则找到了一个安全序列。

//银行家算法（dijkstra）/下面代码可能存在问题
int Available[m];//每种资源可用数量
int Allocation[n][m];//每个进程已分配资源数量
int Need[n][m];//每个进行还需要的资源数量
int Work[m];//工作向量
bool Finish[n];//进程是否结束

Work = Available;
Finish[n] = false;
while(true){
    for(int i=1;i<=n;i++){
        if(Finish[i]==false && Need[i]<=Work){
            Work = Work + Alloction[i];
            Finish[i] = true;
            break;
        }
        else{
            goto end;
        }
    }
}
End: 
for(int i=1;i<=n;i++){
    if(Finish[i]==false)
        return "deadlock";
}


//来源：https://baike.baidu.com/item/%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95
intchkerr()//在假定分配资源的情况下检查系统的安全性
{
intWORK[N],FINISH[M],temp[M];//temp[]用来记录进程安全执行的顺序
inti,j,m,k=0,count;
for(i=0;i<M;i++)
FINISH[i]=FALSE;
for(j=0;j<N;j++)
WORK[j]=AVAILABLE[j];//把可利用资源数赋给WORK[]
for(i=0;i<M;i++)
{
count=0;
for(j=0;j<N;j++)
if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j])
count++;
if(count==N)//当进程各类资源都满足NEED<=WORK时
{
for(m=0;m<N;m++)
WORK[m]=WORK[m]+ALLOCATION[i][m];
FINISH[i]=TRUE;
temp[k]=i;//记录下满足条件的进程
k++;
i=-1;
}
}
for(i=0;i<M;i++)
if(FINISH[i]==FALSE)
{
printf("系统不安全!!!本次资源申请不成功!!!\n");
return1;
}

以上算法可以判断一个序列是否为安全序列，但时间复杂度为O(nm^2)，由于每次请求资源都需要执行一次该算法，开销太大。

死锁检测+恢复

检测到死锁出现，让一些进程回滚，让出资源

间隔一段时间应用一次banker算法判断是否存在死锁，如果存在，在死锁进程组中选择一个进程回滚。

如何选择进程，回滚到什么程度，都需要新的算法，产生新的开销。因此大部分PC机都选择忽略死锁。

死锁忽略

对于经常重启的设备，可以采取这种措施

在一般的PC机中，都采取了忽略死锁的方式。

内存管理

指令的内存映射

重定位：程序编译为汇编时，部分指令存在寻址操作，但是不同程序的地址可能相同引发冲突，因此程序中的地址实际上是逻辑地址（相对地址），程序运行时需要修改其地址为物理地址，这个过程称为重定位。

对于一些固定的设备，可以采用编译时重定位的方式，如嵌入式系统。编译时重定位的程序只能在内存的固定位置存放。

载入时重定位可以在载入时寻找空闲的内存，然后修改物理地址。缺点是每次载入都需要修改地址，并且一旦放入内存就不能移动。

• 交换：swap

由于内存资源少，因此对于部分长时间阻塞的进程，操作系统可能会将其放入磁盘，下一次执行时再装入内存，那么放入磁盘前和重新装入内存后的内存地址可能会发生变化。

运行时重定位：运行每条指令时才完成重定位。在指令运行时完成地址翻译，指令中只给出偏移量（offset），由基址加偏移量计算出物理地址。基地址也放在PCB中。这个过程实际上就是完成了指令的内存映射。

内存分段

一个程序不光包含代码段，还包含数据、栈、动态数组、函数库等部分。由于不同的部分有不通过的特征，如代码段只读，因此需要将不同段分开处理。一个程序不是一次性全部装入同一块内存，而是将各段分别放入内存的不同部分。

一个程序可能有很多个段，每个段都有相应的基址。如使用DS寄存器储存相应段的段号，在进程段表内查询到相应段的基址、长度、权限等信息。这个表就是LDT表，也就是内存映射表。操作系统的LDT表被称为GDT表。

内存分区与分页

分区

内存是如何分割的，分割内存后，就可以将段放入空闲分区。

固定分区

操作系统初始化时将内存等分成k个分区。

可变分区

根据申请段的大小分配不同大小的分区。

通过数据结构来储存内存分配信息（如空闲内存表和已分配内存表），通过数据结构内的信息来分配内存资源。

由于多进程的存在，系统中的内存占用并不是连续的，而是分散的，碎片化的。因此空闲分区表中可能有多个空闲分区，各有不同的长度。当收到一个内存请求时，如何选择内存分区。

• 首先适配：最先找到的内存分区

速度快，时间复杂度O(1)

• 最佳适配：内存大小最接近申请内存的（必须大于）

最佳适配每次寻找最接近申请的内存分区，会导致内存越来越碎片化，最终会产生大量的、碎片化的、细小的、无法使用的内存碎片。但是最佳适配会保留部分较大的内存分区。

• 最差适配：内存大小最不接近申请内存的

最差适配每次寻找最大的一个内存分区，最后产生部分大小均匀的内存分区。

分页

解决内存分区导致的内存效率问题

无论采取怎样的分区方法，都会产生内存碎片，如果遇到一个较大的内存申请，可能内存中的剩余内存大于申请内存，但是由于剩余内存不连续，不能给申请使用。要想解决这个问题，需要将已使用的内存分区移动到一起，使空闲分区连续（内存紧缩）。但是这种方法开销太大，并且内存紧缩过程中不能执行任何用户级程序。

操作系统初始化时，将内存分页（4k/页），页（也叫帧）是内存的最小分配单位。

CPU级的内存都是分页的，而用户级的程序支持分段。

分页避免了内存碎片的产生，因为页作为内存分配的最小单元，分配时（在物理地址层）可以不连续。例如每页大小为100，现在需要540大小的空闲内存，那么分配6个页。只要内存中存在6个页，就可与分配给该进程，即使这6个页不连续。

不连续的页如何寻址，如在该代码段中存在一个jmp 320指令，如何计算320的物理地址。

这里引入了一个页表，类似段表。虽然页之间在物理层不连续，但是可以让它在逻辑层连续。建立一个页表，页表中的页依页号排列，页号从0开始递增。在页表中，每一个页号唯一对应一个页框号，而页框号可以经过计算，固定的对应唯一的，物理内存中的内存页。这样就实现了不连续的内存页在逻辑上的连续。同样的，页表中也储存了页的权限信息。逻辑页和物理页大小要相同。页表地址存放在cr3寄存器中，也在PCB中。

要计算jmp 320的物理地址，首先要确定其页号，由于每页大小100，那么320存放在页3（0基）。首先找到页3对应的页框号对应的物理地址，再在此物理地址的基础上加上20的偏移量即得到了320的物理地址。

之所以页表中需要存放权限信息，是因为一个进程（线程）只有一个页表，其中存放了所有段的页对应信息。段是用户级的结构，而页是CPU级的结构。页表中代码段在前。

上面两段是第一次看到这边时的理解，可能存在一些问题。

实际上页表中的页号并不是程序运行时随意赋予的，因此不能随意的让其从0开始递增。页号代表的是程序中的逻辑地址，页表储存了逻辑地址与物理地址的对应关系。由于程序在编译时，其内存地址都是随机的，因此程序运行时逻辑地址也没有规律，对于一个32位的计算机，逻辑地址取值范围有4G，程序中的逻辑地址可能是4G内的任何值。所以每个进程的页表都要储存4G范围的页号（逻辑地址）。由于页是内存分配的最小单位，因此每个页空间过大会造成内存空间浪费，应该让页尽量小。但是过小的页又会造成页表过大，因为每个进程都有页表，每个页表都需要存储4G范围的逻辑地址页号，那么页表项就有4G/(单页空间)，单页空间越小，页表项越多，造成空间浪费。那么能不能只存储自己使用的内存页号，不储存未使用的呢。如果不储存未使用的页号，那么会造成页号不连续，在页表中寻找相应的页表项时需要遍历页表（类似链表），如果一个页表使用了4M空间即1千个页表，那么平均需要遍历五百次才能找到需要的页表项，由于页表也储存在内存中，当用户在内存中读一个数据时，需要首先在内存中读取五百次来获取物理地址，大大降低了执行效率。如果连续储存页号，那么寻找相应的页号只需要逻辑地址/(单页空间)取模即可找到页号（类似数组）。因此不储存不使用的地址不可取，要解决这个问题，需要用到下面的多级页表。**

在我第一次看这里的时候，误认为页号是随意进程随意赋予的。如果是这样，那么还需要另一个数据结构来储存逻辑地址和页号的对应关系，在这个数据结构中，查找逻辑地址和页号的关系时，仍然需要遍历，实际上和上面只存储使用到的逻辑地址的方式等价。

由于逻辑地址可能取到4G内存的任何部分，因此需要储存4G内存的页表，那么能否在程序载入时进行一次重定向，将逻辑地址从0开始依次排列？这样可以减少内存损耗，但是仍然存在上面说到的问题，就是程序过于僵化，在进程换入换出，或者需要另外申请内存时，需要对逻辑地址进行额外的修改，增加损耗。

数组储存浪费空间，链表储存浪费时间，那么能否找到一个数据结构既省空间又省时间？如果是用户级的程序，这里可以使用字典，既减少内存占用又能快速查找。字典的特征是建立时间长，后续查找快，并且不需要储存索引关系，但是由于字典需要用到哈希算法，由哈希算法决定存储地址，而哈希算法的不可逆性和操作系统需要管理空间内存分配相矛盾。如果将哈希算法换成一个可逆的算法呢，字典的核心就是由一个特定的算法决定存储地址，这本身就和操作系统对内存空间的管理相矛盾，在用户层，程序可以随意地使用逻辑地址，因此字典是一种优秀的存储介质，但是在内核层，并不能发挥字典地优点。

当然也可以使用索引结构，也就是下面的多级页表。

多级页表和快表

多级页表

由于内存按页分配，不足一页的申请也分配一页内存，这样造成了内存浪费，为了减少内存浪费，应该减少内存页的大小，但是内存页越小，页表就越大。页表太大就造成了页表存放问题。

在上面讨论了为什么不能不储存未使用的内存页来减少空间占用，是因为未使用的页也需要起到占位符的作用来帮助页表查找。既然是占位符，那么是否可以将多个未使用的占位符合并为一个，减少空间占用。这就是多级页表。

在页表中我们只储存页目录和页目录指针，例如我们可以将一百个页合并为一个页目录，那么在寻找页号时，首先模10确定在哪个页目录中，然后在相应的页目录中再查找页号。对与那些有使用的内存页，储存其所在地页目录地所以页号即可，对于绝大多数页目录，其所含的所有页号都没被使用，那么就不需要储存它所包含的页号，节省了内存空间。

多级页表减少了空间浪费，实际上也增加了时间开销，因为首先需要在高级页目录中查找，然后再进入相应的低级页目录。每增加一级页目录，就会多一次查找。

快表（TLB）

为了保持多级页表空间优势的同时减少时间开销，在CPU中增加了一个TLB寄存器，其中储存了最近使用的几个页号。TLB中的页号可以不连续，由于TLB是一个硬件设备，可以通过电路设计来直接命中需要的页号，进而取出它的物理地址。如果需要的页号在快表中未命中，那么再到多级页表中去查找。快表是缓存思想。（局部性原理）

TLB的工作效率取决于TLB的命中率，而TLB的命中率取决于TLB的大小，那么TLB的大小应该设计成多少合适。

一般的TLB在[64,2048]。一个4G内存，4k单页的系统，会有2e20个页号，那么为什么只需要64个快表条目。因为程序对内存的使用存在空间局部性，大部分逻辑内存地址都集中在几部分（因此程序存在大量循环结构）。

如果使用字典就不存在空间局限性了，岂不是会降低命中率。

段页结合

用户希望用段，物理内存希望用页。

虚拟内存：完成段和页的连接

用户层的段通过段表映射到虚拟内存，虚拟内存通过页表映射到物理内存。

段页结合的重定位（地址翻译）：

逻辑地址通过段表翻译到虚拟地址，虚拟地址通过页表翻译到物理地址。这个过程由硬件MMU完成。

虚拟内存结构：虚拟地址格式为10为页目录号，10位页号，12位offeset。共12位。

由逻辑地址计算虚拟地址：在段表中查到基址，基址加上逻辑地址得到虚拟地址。

由虚拟地址计算物理地址：（注意这里虚拟地址是4字节的，实际上页号也是4字节的）前10位找到页目录号，在页目录里用中间10位找到页号，也好对应的物理基址加上offset得到物理地址。

逻辑地址到虚拟地址，需要从虚拟地址中分配一个空闲分区，可以采用前面的分区算法，但是分区产生的碎片呢。

实际上每个进程都有自己的页表，因此虚拟内存只在进程内有效。所以每一个进程可用虚拟内存大小都是4G，因此即使产生碎片也不会影响进程执行。

上面一段存疑，关键在于虚拟内存是否在进程间共享。如果虚拟内存在进程间共享，那么就不需要多个页表了，只需要一个全局的页表储存虚拟内存到物理地址的映射即可，然而实际上每个进程都有自己的页表，因此我认为虚拟内存在进程间不共享。但是在下面的代码中，虚拟内存是按进程分配的。

答：在一般的操作系统中，确实虚拟内存在进程中不共享，因此每个进程都需要自己的页表。但是linux0.11是一个基础系统，因此采用了共享虚拟内存和页表的方式，所有进程公用一个页表和内存地址。因此上面引用符标记的部分是正确的（我认为是这样）。

程序载入内存步骤：

• 虚拟内存中找到一个空闲分区
• 建立段表
• 物理内存选择空闲页
• 建立页表
• 将指令放入物理内存

//linux/kernel/fork.c
int copy_process(int nr, long ebp,...){
    ...
    copy_mem(nr,p);
    ...
}

int copy_mem(int nr, task_struct *p){
    unsigned long new_data_base;
    new_data_base = nr*0x4000000;//进程号*64M，也就是按进程号固定分区
    set_base(p->ldt[1],new_data_base);//设置代码段
    set_base(p->ldt[2],new_data_base);//设置数据段
    
    unsigned long old_data_base;
    old_data_base = get_base(current->ldt[2]);获取父进程数据段地址(虚拟地址)
    copy_page_tables(old_data_base, new_data_base, data_limits);//复制页表
}

int copy_page_tables(unsigned long from, unsigned long to, long size){
    from_dir = (unsigned long *)((from>>20) &0xffc);//from是父进程32位虚拟地址，虚拟地址格式为10为页目录号，10位页号，12位offeset。
    //这里的操作是将from右移20位再将后两位清0，该操作等价于右移22位再乘4。
    //实际上是取出页目录表中父进程虚拟地址所在的页目录。
    //为什么是右移22位再乘4，右移22位取出的是32位虚拟地址的页目录号，但是为什么要右移4位呢。
    //因为父进程虚拟地址是32位的，也就是4字节，因此0目录地址为0，1目录地址为4，即地址=页目录号*4。
    //为什么虚拟内存地址是这个结构，因为这里的页空间是4k，最后12offset刚好可以寻址4k空间，linux0.11将页分为两级，也就是前10位页目录号和中间10位页号。
    //下同
    to_dir = (unsigned long *)((to>>20) &0xffc);
    size = (unsigned long)(size+0x3fffff)>>22;
    for(; size-->0; from_dir++, to_dir++){
        from_page_table = (0xfffff000&*from_dir);//后12位offset偏移量置0
        to_page_table = get_free_page();//分配一个物理内存页给子进程建立页表
        *to_dir = ((unsigned long) to_page_table) | 7;//将刚申请的页表赋给子进程页目录表中相应的页目录项
        for(; nr-->0; from_page_table++, to_page_table++){
            this_page = *from_page_table;
            this_page&=~2;//只读
            *to_page_table = this_table;
            *from_page_table = this_table;
            this_page -= LOW_MEN;
            this_page >>= 12;
            mem_map[this_page]++;
        }
    }
}

在下一次执行子进程时，由于共享了父进程的物理内存，但是该内存已经被设为只读，因此子进程会重新申请一段物理内存并修改页表，完成与父进程的分离。

内存的换入和换出

swap分区：linux中用来完成和内存换入换出操作的磁盘空间

虚拟内存的大小是由操作系统决定的，但是实际的计算机却有不同大小的内存，如何实现虚拟内存到物理内存的映射（如4G虚拟内存映射到1G物理内存）。需要用到换入和换出。

虚拟内存大小是由操作系统位数决定的，如32位操作系统就有2^32=4G大小的虚拟内存，因此在编译的时候可能用到0-4G空间中的任意地址。

内存换入

用户的程序储存在磁盘上，只有在执行时才需要读入内存中。在程序执行时，我们可以将一部分用到装入内存，其他部分不装入内存，在程序用到后在将刚才用过的部分写入磁盘，然后载入新的部分程序，完成了完整虚拟内存到不完整物理内存的映射。

请求调页

程序在执行时只载入一部分，那么如果访问未载入内存的部分会发生什么？

程序发出逻辑地址，由MMU计算得到虚拟地址再计算物理地址，在页表中查询页基址时，发现相应的页没有对应的物理基址，出现了缺页。那么立即（由中断）请求硬件完成新的程序载入内存。该中断由MMU发出，CPU执行中断处理程序，完成磁盘到内存的载入以及页表到物理内存的映射。（这里只考虑换入，不考虑换出。）这个中断是一个特殊的中断（中断号14）用来处理缺页，他不会在中断结束后将PC+1，而是保持PC不变（因为是执行到一条指令发现需要的资源不在内存中，然后请求调页，因此这条指令实际上还没有执行，因此中断结束后需要重新执行这条指令，而不是执行中断的下一条指令）。

除了使用请求调页，是不是也能使用请求调段。使用请求调段也能完成完整的虚拟内存到不完整的物理内存之间的映射，但是页的颗粒更小，使用调页可以提高内存使用效率。

第一次执行程序时，从磁盘中加载入内存也可以由请求调页来完成。

//linux/mm/menory.c
//do_no_page函数在14号中断处理程序中被调用
void do_no_page(unsigned long error_code, unsigned long address){
    address &= 0xfffff000;//页面地址
    tmp = address->current->start_code;//页面对应的偏移
    if(!current->executable||tmp>=current->end_data){
        get_empty_page(address);
        return;
    }
    page = get_free_page();//获取空闲内存，物理地址赋给page
    bread_page(page, current->executable->i_dev, nr);
    put_page(page, address);//建立页表中的映射
}

void get_empty_page(unsigned long address){
    unsigned long tmp = get_free_page();
    put_page(tmp,address);
}

unsigned long put_page(unsigned long page, unsigned long address){
    unsigned long tmp, *page_table;
    page_table = (unsigned long *)((address>>20)&ffc);
    if((*page_table)&1)//如果已经存在该页目录对应的页表，取得页表首地址
        page_table = (unsigned long *)(0xfffff000&*page_table);
    else{//不存在则创建
        tmp = get_free_page();
        *page_table = tmp | 7;
        page_table = (unsigned long *)tmp;
    }
    page_table[(address>>12)&0x3ff] = page | 7;//将物理地址page放到页表中对应的页号上。
    return page;
}

内存换出

在内存换入的时候是获取一个空闲页然后载入程序，但是并不能总是获取新的页，因为内存是有限的。因此换入时要选择一个页换出到磁盘。如何选择淘汰的页。

对于淘汰页选择算法的评价标准是产生的残页少。

FIFO

先进先出，算法简单，但是没有考虑各种进程的特点。

MIN算法

选择最远（晚）使用的页淘汰，是最优方案。但是选择最远使用的页需要预知未来的页使用顺序，但这是不可能的。

LRU算法

选择最近最长时间没有使用的页面淘汰。（局部性原理）

要实现基于时间来选择，就要记录页面使用的时间，在每个页中加上一个时间戳。每次选择最小时间戳的页面淘汰。每个逻辑页都需要一个时间戳，并且没执行一条指令，都需要取指执行，取值就要计算地址，计算地址就要访问页表，就要修改时间戳，增大系统开销。并且由于时间戳不断递增，对于长时间运行的系统很可能产生溢出。实现代价太大。

能否使用一个栈或队列，按运行时间顺序储存页。这样如果访问一个已经在内存中的页，需要将储存在队列中间的列再提到队首，仍然有很大的开销。

LRU近似实现（clock算法）

将LRU算法中的时间戳换为引用位，只需要1比特，并且可以放在页表中，并且所有页的引用位构成一个循环队列。每次MMU访问该页时自动将该位置1。需要淘汰页时，在循环队列中遍历，如果该位为1则置0，是0则淘汰，然后将队首指针指向队列中的下一项。（二次机会算法）

clock算法的改造

一般来说缺页很少发生（局部性原理）。缺页的时候才需要换入换出，换出才对引用队列进行查询，并将引用位1置为0。如果很长时间没有换出，那么引用队列中的页都趋近于1，那么下一次换出遍历队列时，从队首开始遍历，由于引用位全为1，那么需要遍历一遍将引用位全置0，遍历一遍后队列指针重新指向队首，此时队首已经被第一轮遍历置0，因此直接淘汰队首，并将队首指针指向队列中的下一项。经过很长时间的运行后，再次遇到缺页，此时可能队列中的引用位又全为1了，又重复上面的过程，淘汰当前队首，也就是上一次淘汰的队首的下一项。实际上已经近似为先进先出算法了。

clock算法所选择的是最近没有使用的页，这里的最近指的是两次指针遍历（也就是两次缺页）的间隔。但是间隔时间太长会导致clock算法近似为FIFO算法。也就是引用位储存了太久的信息（从上次缺页到这次缺页之间的页访问情况）。

要改造clock算法，也就是缩短R位（引用位）清除时间。因此引入了两个指针，一个用来清楚R位，一个用来选择淘汰页。清楚指针移动速度快，不断循环清除R位信息，淘汰选择指针移动慢（在缺页时调用），选择淘汰的页面，仿佛时钟的分针和时针，因此称为clock算法。

页框分配

颠簸：在计算机刚开始工作时，CPU利用率随着进程数的增加逐渐上升（由于进程间的交替执行）。当进程数增加到一定量时，CPU利用率突然急剧下降，这个现象称为颠簸。由于进程数量越来越多，而物理内存大小是固定的，那么分配给每个进程的物理页（页框）就越少，缺页率越来越高，CPU总是需要等待调页导致执行效率降低。也就是CPU总是在等待指令在磁盘和内存间不断换入换出。

利用一些算法算出程序的工作集，燃火分配相应的页框覆盖住程序的工作集即可。

外设

CPU向外设控制器中的寄存器发送指令，外设中的控制器执行完指令后向CPU发出一个中断。由于操作系统外设操作要向用户提供统一的接口，但是外设的种类非常复杂，各种外设的语法，结构都可能不同，因此外设操作的代码非常复杂。操作系统对外设的处理分为三个部分：

• 外设操作指令的实现，如out指令
• 对不同的外设通过统一的外设接口
• 编写外设的中断处理程序

在linux中，所有的设备都以文件的形式存放在dev文件夹下，对外设的操作就是对这些文件的操作，linux为外设操作提供的接口就是文件系统。

I/O与显示器

操作系统对printf的处理

printf("Host Name: %s",name);
//printf函数最终在函数库中展开为了一些写操作，其中的关键时write(1,buf,...);

//linux/fs/read_write.c
ini sys_write(unsigned int fd, char *buf, int count){
    struct file * file;
    file = current->file[fd];
    inode = file->f_inode;//inode存放了设备的相关信息
    if(S_ISCHR(inode->i_mode))//判断是否为字符设备
        return rw_char(WRITE, inode->i_zonde[0]/*设备号*/, buf, cnt);
    ...
}
//current->file数组储存在PCB中，而进程创建是由父进程创建子进程并复制PCB，所有的进程最终都是由操作系统复制的，这个file也由操作系统初始化。

//linux/fs/open.c
int sys_open(const char * filename, int flag){
    i = open_namei(filename, flag, &inode);
    current->file[fd] = f;//第一个空闲的fd
    f->f_mode = inode->i_mode;
    f->f_inode = inode;
    f->f_count = 1;
    return fd;
}

//linux/fs/char_dev.c
int rw_char(int rw, int dev, char * buf, int cnt){
    crw_ptr call_addr = crw_table[MAJOR(dev)];//找到设备号对应的处理函数的函数指针
    call_addr(rw, dev, buf, cnt);
    ...
}


static crw_ptr crw_table[] = {...,rw_ttyx};//假设这个rw_ttyx是上面数组中查到的元素
typedef (*crw_ptr)(int rw, unsigned minor, char *buf, int count);

static int rw_ttyx(int rw, unsigned minor, char *buf, int count){
    return ((rw==READ)? tty_read(minor, buf): tty_write(minor, buf));
}


//linux/kernel/tty_io.c
int tty_write(unsigned channel, char * buf, int nr){
    struct tty_struct * tty;
    tty = channel+tty_table;
    sleep_if_full(&tty->write_q);//如果队列已满就睡眠
    ...
    char c, *b = buff;
    while(nr > 0&&!FULL(tty->write_q)){
        c = get_fs_byte(b);//从用户缓冲区读
        if(c=='\r'){
            PUTCH(13, tty->write_q);
            continue;
        }
        if(O_LCUC(tty))
            c = toupper(c);
        b++;
        nr--;
        PUTCH(c, tty->write_q);
    }//输出结束或队列写满
    tty->write(tty);//真正的打印函数
}

//include/linux/tty.h
struct tty_struct{
    void (*write)(struct tty_struct *tty);
    struct tty_queue read_q, write_q;
}
struct tty_struct tty_table[] = {
    con_write,//console
    {0,0,0,0,""},
    {0,0,0,0,""},
    ...
}

//linux/kernel/chr_drv/console.c
void con_write(struct tty_struct *tty){
    GETCH(tty->write_q, c);
    if(c>31&&c<127){
        __asm__("movb _attr, %%ah\n\t"
            "movw %%ax, %1\n\t"::"a"(c),
            "m"(*(short*)pos):"ax");
        pos+=2;//pos是显存地址，每写一个字（ax），地址+2.
        //al存放字节，ah存放属性，从高到低：
        //D7：BL闪烁
        //D6-D4：RGB背景色
        //D3：高亮度
        //D2-D0：RGB前景色
    }
}

整个过程

• 库函数：printf
• 系统调用：write
• 字符设备接口：crw_table[]
• tty设备写：tty_write
• 显示器写：con_write
• 最终执行：mov pos, c

键盘

对外设的输出通过mov/out指令，对外设的输入通过中断。键盘中断号21号。

void con_init(void){
    set_trap_page(0x21, &keyboard_interrupt);
}

//kernel/chr_drv/keyboard.S
.globl _keyboard_interrupt
_keyboard_interrupt:
    inb $0x60, %al//从端口0x60读扫描码（每个按键对应一个扫描码）
        call key_table(, %eax, 4)//调用key_table+eax*4
        ...
        push $0 call_do_tty_interrupt

//kernel/chr_drv/keyboard.S
key_table:
    .long none, do_self, do_self, do_self//扫描码00-03
    .long doself,...., func, scroll, cursor
//可显示字符一般由do_self处理

        
mode: .byte 0
do_self:
    lea alt_map, %eax//找到alt组合键映射表
    testb $0x20, mode//判断alt是否同时按下
    jne 1f
    lea shift_map, %eax
    testb $0x03, mode
    jne 1f
    lea key_map, %eax//key_map和shift_map储存了按键对应字符的ascii码
1:
    movb (%eax, %eax), %al//扫描索引码，ascii->al
    orb %al, %al
    jne none//没有对应的ascii码
    testb $0x4c, mode//查看caps是否亮
    je 2f
    cmpb $'a, %al
    jb 2f
    cmpb $'}, %al
    ja 2f
    subb $32, %al//小写变大写
2:
    testb $??, mode//处理其他模式，如同时按下ctrl
3:
    andl $0xff, %eax
    call put_queue
none:
    ret
        
put_queue:
    movl _table_list, %edx
    movl head(%edx), %ecx

        
struct tty_queue *table_list[] = {
    &tty_table[0].read_q,
    &tty_table[0].write_q;
}
//上面键盘输入已经完成，下面是回显，也就是上面的显示器
void do_tty_interrupt(int tty){
    copy_to_cooked(tty_table+tty);
}

void copy_to_cooked(struct tty_struct *tty){
    GETCH(tty->head_q, c);
    if(L_ECHO(tty)){//判断是否需要回显
        PUTCH(c, tty->write_q);
        tty->write(tty);//立即回显
    }
    PUTCH(c, tty->secondary);
    ...
    wake_up(&tty->secondary.porc_list);
}

磁盘

机械硬盘

生磁盘

根据盘块号请求磁盘的方式称为生磁盘

向磁盘控制器发送柱面（磁道cyl）、磁头（head）、扇区（sec）、缓存位置。这些工作由磁盘驱动完成，操作系统只负责向磁盘驱动发送一个盘块号（block），磁盘驱动根据盘块号计算出cyl、head、sec（CHS）。

block是一维数据而CHS是三维数据，这里存在一个一维数据向三维数据的映射（编址）。由于一般程序使用的block都是连续的，映射也需要满足让相邻的block的访问更快这一原则。

寻道时间：磁臂移动时间，12到8ms

旋转时间：7200转/分钟 半周4ms

传输时间：50M/S 越0.3ms

主要延迟在于寻道时间。因此相邻block的盘块应该尽量映射到同一磁道，并且扇区应该连续（旋转连续读写）。

block = 磁道->磁头->扇区

Headers为每个磁道的磁头数，Sectors为每个磁头的扇区数。

由于磁盘访问时间主要是寻道时间和旋转时间，如果增加每次访问读取的数据数量，那么能大大提高读取数量，但是读取单位（簇）越大，磁盘空间浪费就越大。这里有一个时间和空间的折中。相对来说，磁盘提升空间大小是很容易的，但是提高寻道和旋转时间却很难，因此适当增大数据读取单位是划算的。那么一个block可能对应多个连续扇区，这个扇区数量（nsect）也会一起发送到磁盘驱动，然后由磁盘驱动和CHS一起发送到磁盘上。

既然磁盘驱动会将连续的block尽量映射到相邻的物理磁盘空间，读写就已经是连续的了，不需要额外移动磁臂，为什么还要提高读取单位来提高速度？

我的理解是由于进程调度的原因，假设现在进程A需要读取连续的3个扇区，如果没有读取单位，即读取单位为存储单位扇区，那么首先读取第一个扇区，然后阻塞等待磁盘读取，切换到其他进程B执行，磁盘读取 第一次移动磁头。这是被调度执行的程序可能也需要读取磁盘，向磁盘发送请求，由于已经是B进程，请求block大概率与A不连续，阻塞等待，磁盘读取，切换到A进程，A进程继续读第二个扇区，此时由于前面执行B进程的请求，磁臂发生了移动，需要读取A进程的扇区时需要在次移动磁臂，这是A进程中第二次移动磁臂，同理访问扇区3时可能还需要移动一次磁臂，那么为了完成A进程读取3个磁盘，移动了3次磁臂。如果修改读取单位为2个扇区，那么第一次移动磁臂一次读取1和2扇区，再调度到别的进程，第二次移动磁臂读取3和4扇区。这里虽然浪费了扇区4，但是却减少了磁臂移动，提高了访问速度。

为什么不一次性向磁盘请求队列放入多个连续扇区的请求，由磁盘驱动封装为一个读取请求，如果是因为考虑到某个进程读取大文件会导致队列溢出或者长时间连续占用磁盘，那么也可以考虑限制一次性最大写入扇区数量，这样不仅提高速度，也不会造成扇区浪费。可以理解为动态调整读取单位。

可能是这样会增加系统计算开销吧。个人认为这个算法也有道理，可能是和簇共同工作来提高磁盘性能的。

百度百科对簇的解释是操作系统无法对众多的扇区进行寻址，个人认为这个说法显然不成立，磁盘中每个扇区512字节（新的标准已经修改为4KB），那么一个512G的磁盘，也只有1G寻址空间，而32位系统就能够对4G内存进行寻址，也就能对2T磁盘进行寻址。更何况现在大多数操作系统都已经是64位，不存在扇区过多无法寻址的情况。不过也可能是其他原因导致的无法寻址。

由于多进程的存在，可能多个进程都希望访问磁盘，因此在操作系统和磁盘驱动之间还存在一个磁盘访问请求队列。每次磁盘读取完成，向CPU发送一个中断请求并取出下一个队列中的请求。当然加入队列也要保证操作原子性。

磁盘请求的调度

原则：尽量让磁头少移动，同时保证不能让某个请求无限等待。

FIFO（FCFS）

先进先出

SSTF

短寻道优先：优先处理扇区位置最近的请求

显然SSTF会造成一些较远的请求无限等待

SCAN

SSTF+周期性移动

先从0扇区单向移动（读取）到最大扇区，再从最大扇区单项移动（读取）到0扇区。

会导致两端扇区等待时间过长。

C-SCAN（电梯算法）

真实使用的算法

先从0扇区单向移动（读取）到最大扇区，然后从最大扇区回到0扇区，过程中不读取数据。

staticc void make_request(){
    ...
    req->sector = bh->b_blocknr<<1;//左移1位即*2，每个blocknr对应两个扇区
    add_request(major+blk_dev, req);
}

static void add_resquest(struct blk_dev_struct * dev, struct request *req){
    struct request * tmp = dev->current_request;
    req->next = NULL;
    //下面是插入请求队列的算法，队首为当前磁臂位置对应的请求。
    cli();
    for(;tmp->next;tmp=tmp->next){
        if(IN_ORDER(tmp, req)||(!IN_ORDER(tmp, tmp->next))&&IN_ORDER(req, tmp->next))
            break;
    }
    req->next = tmp->next;
    tmp->next = req;
    sti();
}

#define IN_ORDER(s1,s2) \
    ((s1) ->dev<(s2)->dev)||((s1)->dev == (s2)->dev\
    &&(s1)->sector<(s2)->sector)

• 进程得到盘块号，算出扇区号（不是sec扇区，而是包含CHS的扇区号）
• 用扇区号make_req，用电梯算法add_request
• 进程sleep_on
• 磁盘中断受理

static void read_intr(void){
    end_request(1);
    do_hd_request();
}

• do_hd_request算出CHS
• hd_out调用outp()完成端口写

文件

为了让普通用户更方便得使用磁盘，操作系统将盘块号封装成文件。

用户级的文件是一段字符流，而磁盘中的文件是盘块，文件也就是通过某一个结构建立字符流到盘块的映射。

连续结构（类数组）

每个文件用一个FCB储存信息，包括文件名、起始盘块、块数。磁盘操作时，文件提供一个字符起始位置（相对于本文件的），起始位置模盘块大小再加起始盘块就得到了盘块号。

这种方式的缺点在于如果不断增加文件内容，文件就要不断占用后续的盘块，如果后续盘块已经被占用，那么这种方式就不能正常工作了。

这种方式适合静态读写，不适合动态变化。

链式结构（类链表）

适合动态变化，不适合随机读写

索引结构

FCB中储存索引表的盘块号，在索引表中查找逻辑位置对应的盘块号。磁盘操作时先读索引块。文件较大时还可以建立多级索引。

磁盘操作代码实现

//linux/fs/read_write.c
int sys_write(int fd, const * buf, int count){
    struct file * file = current->file[fd];
    struct m_inode * inode = file->inode;//获取FCB
    if(S_ISREG(inode->i_mode)){
        return file_write(inode, file, buf, count);//file中有一个fseek偏移指针，储存的是文件操作点相对文件起始位置的偏移
    }
}

int file_write(struct m_inode * inode, struct file * filp, cahr * buf, int count){
    off_t pos;
    if(filp->f_flags&O_APPEND){
        pos = inode->i_size;
    }
    else{
        pos = filp->f_pos;
    }
    while(i<count){
        block = create_block(inode, pos/BLOCK_SIZE);//完成盘块号的计算，包括对索引表的查询
        bh = bread(inode->i_dev, block);
        int c = pos%BLOCK_SIZE;
        char * p = c+bh->b_data;
        bh->b_dirt = 1;
        c = BLOCK_SIZE-c;
        pos+=c;
        ...
        while(c-->0)
            *(p++) = get_fs_byte(buf++);
        brelse(bh);
    }
    filp->f_pos = pos;
}

//create_block模块
int _bmap(m_inode * inode, int block, int create){
    if(block<7){//小于7表示无索引直接查数据块
        if(create&&!inode->i_zone[block]){
            inode->i_zone[block] = new_block(inode->i_dev);
            inode->i_ctime = CURRENT_TIME;
            inode->i_dirt = 1;
            return inode->i_zone[block];
        }
        block-=7;
        if(block<512){
            bh = bread(inode->i_dev, inode->i_zone[7]);
            return (bh->b_data)[block];
        }
    }
}

struct d_inode{
    unsigned short i_mode;//文件类型，数据文件和设备文件，inode为外设提供了统一的文件视图
    unsigned short i_zone[9];
    ...
}

目录与文件系统

多文件的处理

• 单级储存
• 分用户
• 目录树
• 目录：表示一个文件集合

用户级：用路径操作文件

根据目录获取文件FCB

目录文件储存子文件的索引，实现树结构，如果储存文件名到FCB的映射，读取速度较慢，因为为了匹配的需要的文件，需要从磁盘中读取该目录下的全部文件的文件名和FCB。

在linux0.11中，目录储存的是文件名到FCB的编号，而这个编号就是相应文件FCB在FCB数组中的下标。

FCB[0]也就是根目录/的FCB

为了使整个文件系统能自举，还需要储存一些信息：

• 引导块
• 超级块：记录inode位图和盘块位图有多大
• inode位图：记录inode块的占用情况
• 盘块位图：记录盘块的占用情况
• inode区，即FCB数组
• 数据区