本文最后更新于8 天前

并发共享虚拟异步

并发：微观上进程交替进行，宏观上进程看起来同时进行

共享：系统中的资源可供内存中的多个并发执行的进程共同使用

虚拟：物理上的实体变为若干逻辑上对应的实体

异步：多道程序环境下，允许多个程序并发执行，但推进的速度是未知的，已不可预知的速度向前推进。

内核程序和应用程序

内核是操作系统最核心的部分，也是最接近硬件的部分

内核态和用户态是cpu的两种状态，内核态说明正在运行内核程序，此时可以执行特权指令

用户态说明正在运行应用程序，只能执行非特权指令

计算机如何区分这两种状态？cpu中有个程序状态字寄存器

用户态->内核态只能由中断引发。

内核态->用户态由一条修改PSW的特权指令引发

中断和异常

异常：中断信号来源于cpu内部，与当前执行的指令有关

异常：中断信号来源于cpu外部，与当前执行的指令无关

cpu每执行完一条语句都会检查是否有中断信号需要处理，如果有则转而执行中断处理程序

系统调用

操作系统提供给应用程序的接口包括：命令接口和程序接口

程序接口由系统调用组成（系统调用可以理解为可供应用程序调用的特殊函数），应用程序可以通过系统调用请求内核服务。

为什么要系统调用？为了统一管理共享资源，用户进程想要访问共享资源，只能通过系统调用向内核发出请求，内核会对各个请求进行协调管理。

Linux提供的系统调用：fork()创建新进程、exec()启动一个新程序、exit()终止进程、wait()等待子进程终止等，这些系统调用通常是通过c库函数来使用。

操作系统内核功能

时钟管理、中断处理、原语、系统资源管理（进程管理、存储器管理、设备管理）

操作系统引导

cpu从特定的主存地址开始取指令，进行硬件自检，再执行ROM中的引导程序（开机）
将磁盘第一块的主引导记录读入内存，执行磁盘引导程序，扫描分区表。
从磁盘中安装了操作系统的分区读入分区引导记录，执行其中的程序
从根目录下找到完整的操作系统初始化程序并执行，完成开机。

进程控制

进程控制就是实现进程状态转换

进程状态有：就绪、运行、阻塞、创建等

C程序的执行过程

预处理产生.i文件

链接产生.o文件

编译后产生ELF文件

链接后生成可执行文件exe

exe文件运行前需要把程序存入内存

cpu从内存中取指令，cpu中会有很多寄存器，用来存储中间数据

cpu寄存器:pc程序计数器，存放下一条指令的地址，IR指令寄存器，存放当前正在执行的指令

1-10

1.虚拟机的概念

装了软件的裸机

2.多道批处理系统的优缺点

充分利用处理机资源；用户不能知道程序的运行情况，无法交互

3.网络操作系统和分布式操作系统的区别

4.分布式系统的特点
5.中断的分类
6.异常的分类
7.系统调用的定义
8.访管指令
9.进程的概念
10.管道

11-20

11.引入进程和引入线程的目的
12.线程的定义
13.用户级线程和内核级线程各自的优缺点
14.高级调度，中级调度，初级调度
15.CPU利用率、系统吞吐量、周转时间
16.不能进行进程调度的三种情况
17.响应比的计算
18.先来先服务、短作业优先、高相应比优先、时间片轮转、多级反馈队列各自的优缺点以及默认是否抢占
19.上下文切换的上下文是什么，从哪里获得上下文
20.实现临界区互斥必须遵循的准则

21

21.实现互斥的方法以及各自的缺点

22-30

22.互斥锁的实现

23.自旋锁是什么，优缺点是什么

24.信号量如何修改

25.信号量分为哪两种类型，有什么区别，各自的PV如何实现

26.互斥和同步信号量初值应该如何设置

27.

如图同步信号量需要设置多少个

28.生产者问题如何实现（两个）

29.读者写者问题

30.哲学家进餐问题

31-35

31.吸烟者问题

32.管程的定义

33.管程由四部分组成

34.条件变量是什么，与信号量有什么区别

35.死锁产生的条件

36-40

36.循环等待和死锁的区别

37.如何实现死锁处理

38.安全序列是什么

39.死锁检测和死锁避免的对比

40.内存管理的主要功能（5点）

41-45

41.32位操作系统的32位代表什么

42.堆区和栈区分别存放什么类型的变量

43.连续分配管理方式包含哪三种，分别会产生内部碎片还是外部碎片

44.动态分区分配内存回收方法

45.动态分区分配内存分配算法

46-50

46.非连续分配方式包括哪两种

47.分页存储管理包括哪些方式

48.页框的两个别称、页的别称

49.页表

50.如何找到页表在哪里

51-55

51.页表项的大小是怎么确定的，和页面的大小有什么关系

52.段页式存储管理中，段表可以有几个，页表可以有几个

53.基本页式存储、基本段式存储、基本段页式存储、请求页式存储、请求段式存储、请求段页式存储的逻辑地址、页/段表结构是什么

54.对换区和文件区是什么

55.clock算法

56-60

56.改进CLOCK算法改进在哪里

57.改进CLOCK算法的过程

58.内存映射文件是什么，有什么好处

59.索引结点是什么

60.FCB包括哪些信息

61-65

61.文件打开过程

62.文件描述符

63.每个进程打开文件后都具有哪些关联信息

64.文件系统在磁盘中的结构

65.MAC帧前同步码位数、地址长度、数据长度、首部和尾部长度、MAC帧最短长度

66-70

66.TCP建立时，服务器和客户的状态变化

67.TCP释放时，服务器和客户的状态变化

68.FTP、TELNET、SMTP、DNS、TFTP、HTTP、SNMP的端口号（熟知端口号）

69.磁盘空闲空间管理方法

70.挂载是什么意思

71-75

71带权周转时间

72..硬盘需要依次进行物理格式化、对磁盘分区（创建硬盘分区表）、逻辑格式化（文件系统的根目录、文件系统的索引结点表）、操作系统存入磁盘、每次开机时操作系统初始化（内存中准备中断向量表、中断服务程序）

73.工作集

74.中断处理过程

75.进程唤醒

76-80

76.信道利用率

77.磁盘索引结点和内存索引结点

78.文件的基本操作

79.文件的打开过程

80.口令和密码

81-85

81.spooling技术

82.中断时需要保存的数据

83.请求分页系统的页面分配和置换策略

1-10

1、覆盖了软件的裸机
2、优点：资源利用率高，多道程序共享资源；CPU和其他资源保持忙碌状态，系统吞吐量大
缺点：用户响应时间长，用户不能了解自己程序的运行情况，也不能控制计算机
3.分布式操作系统实现多台计算机协同完成同一任务，而网络操作系统仅仅进行数据共享和计算机通信
4.分布式系统中的计算机地位平等；每台计算机上的数据所有计算机共享；系统中任意台计算机都可以构成子系统；任何工作都可以工作在多台计算机上，他们协同完成同一工作
5.

异常=内中断
异常也不能被屏蔽
6.故障：由指令执行引起的异常，包括非法操作码、除零异常、缺页故障、运算溢出等
自陷：事先被安排好的异常，用于在用户态下调用内核程序
终止：使CPU无法工作的硬件故障，如控制器出错、存储器校验错
7.用户在程序中调用操作系统提供的一些子功能。从用户态到内核态是由硬件实现的
8.用户进程请求从用户态到核心态的指令，运行在用户态
9.进程是进程实体的运行过程，是系统和资源进行调度的独立单位
10.管道是进程间通信的一种机制。管道大小固定，满时write被阻塞，空时read被阻塞。只能由创建进程所访问，子进程会继承父进程的管道，并用它来和父进程通信。管道只存储在内存中。

管道只能采用半双工通信，单向传输；管道空时，读操作阻塞；管道非空时，写操作阻塞。

管道的数据一旦读出即消失，因此只能有一个读进程，写进程可以有多个

11-20

11.引入进程是为了程序更好地并发执行，提高资源的利用率和系统吞吐量。线程的目的是减少程序在并发执行时的时空开销。
12.线程是最基本的CPU执行单元，是独立调度的基本单位
13.用户级线程线程切换的开销小，且不同进程可以自己决定使用什么样的线程调度方式，但是缺点是线程执行一个系统调用时，不仅该线程被阻塞，进程内的所有线程都会被阻塞。
内核级线程能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行。内核支持线程具有很小的数据结构和堆栈，线程切换比较快，开销小。线程本身也可采用多线程技术，提高系统的执行效率和速度。但是内核级线程的编程复杂度更高

只有内核级线程具有TCB，内核级线程才是处理机分配的基本单位。用户级线程的调度使用线程库，不需要切换到内核态

14.高级调度（作业调度）是内存与辅存之间的调度，从外存的后备队列中选择任务为其分配内存空间、输入输出设备等资源
中级调度（内存调度）是为了提高内存利用率和系统吞吐量，将暂时不能运行的进程调至外存等待，中级调度决定将外存上的那些具备了运行条件的进程重新调入内存
低级调度（进程调度）从就绪队列中选一个分配处理器资源

CPU利用率 = CPU工作时间/（CPU工作时间+CPU空闲时间）
系统吞吐量 = 单位时间内CPU完成的作业数
周转时间 = 作业从提交到结束所经历的时间
①处理中断过程中②进程在操作系统的内核临界区内③其他需要完全屏蔽中断的原子操作
（等待时间+要求服务时间）/要求服务时间
上下文指某时刻CPU寄存器和程序计数器中的内容，上下文保存在PCB中
空闲让进、忙则等待、有限等待、让权等待

21

21.

软件实现方法：
1.单标志法（缺点：违反空闲让进、让权等待（让权等待非必须））
```
P0
while(turn == 1);
critical section;
turn = 1;
reminder section;

P1
while(turn == 0);
critical section;
turn = 0;
reminder section;
```
2.双标志先检查法（违反忙则等待、让权等待）

P0
while(flag[1]);//flag代表进程进入临界区的意愿
flag[0]=true;
critical section;
flag[0]=false;
reminder section;

P1
while(flag[0]);
flag[1] = true;
critical section;
flag[1] = false;
reminder section;

3.双标志后检查法(违反空闲让进、有限等待、让权等待)

P0
flag[0]=true;
while(flag[1]);//flag代表进程进入临界区的意愿
critical section;
flag[0]=false;
reminder section;

P1
flag[1] = true;
while(flag[0]);
critical section;
flag[1] = false;
reminder section;

4.Peterson算法(违反让权等待)

P0
flag[0]=true;
turn = 1;
while(flag[1]&& turn == 1);//flag代表进程进入临界区的意愿
critical section;
flag[0]=false;
reminder section;

P1
flag[1] = true;
turn = 0;
while(flag[0]&&turn == 0);
critical section;
flag[1] = false;
reminder section;

硬件实现方法

关中断法（不适合多处理器，用户进程有关中断的权力很危险，限制了CPU交替执行程序的能力）

关中断
临界区
开中断

TestAndSet指令(适用于多处理器，简单，支持系统中有多个临界区，不能让权等待，可能饥饿)

boolean TestAndSet(boolean *lock){//设置新值，返回旧值
    boolean *old = lock;
    *lock = true;
    return old;
}
P
while(TestAndSet(&lock));//其他进程执行完会设置lock为false
critical section
*lock = false;
reminder section;

swap指令(适用于多处理器，简单，支持系统中有多个临界区，不能让权等待，可能饥饿)

boolean key = true;
while(key == true){//注意是key不是lock
    swap(key,lock);
}
critical section;
lock = false;
reminder section;

22-30

22.在进入临界区时调用acquire()，退出时调用release()

acquire(){
    while(!available);
    available = false;
}
release(){
    available = true;
}
注意这些代码都只是描述算法，并不是实际实现，也不一定是软件实现。这里acquire和release都是原子操作，通常采用硬件实现

23.自旋锁就是互斥锁，缺点是忙等待，在等待进入临界区时，必须连续调用acquire方法，这种循环浪费了CPU周期。优点是进程在等待锁期间没有上下文切换，若上锁时间较短，则等待代价不高。所以互斥锁适用于多处理器系统

24.信号量只能被两个标准原语wait()、signal()修改，这两个原语可以简写为P()、V()

25.分为整数型信号量和记录型信号量

整型信号量表示资源的数量，相比于普通变量，对整型信号量的操作只有初始化、P、V，缺点是忙等待

wait(S){
    while(S<=0);
    S=S-1;
}
signal(S){
    S=S+1;
}

记录型信号量的结构如下,克服了忙等的缺点，除了代表资源数量的value外，还用进程链表L记录了所有正在等待该临界资源的进程

typedef struct{
    int value;
    struct process*L;
}semaphore;

wait(semaphore S){
    S.value--;//注意整型信号量是先判断后减，这里是先减后判断
    if(S.value<0){//注意不带等号
        add this process to S.L;
        block(S.L);
    }
}
signal(semaphore S){
    S.value++;
    if(S.value<=0){说明还有进程在等待
        remove a process P from S.L
        wakeup(P);
    }
}

26.互斥信号量初值设置为资源的数量，同步信号量初值设置为0，含义是一开始没有这种“资源”，需要等待某进程完成后才能产生这种“资源”

27.7个，要注意的是s1->s6并不需要同步信号量

28.

semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;
Producer{
    while(1){
        P(empty);
        P(mutex);
        produce;
        V(mutex);
        V(full);
    }

}
Consumer{
    while(1){
        P(full);
        P(mutex);
        consume;
        V(mutex);
        V(empty);
    }

}

semaphore apple=0;//爸爸放苹果，女儿吃苹果
semaphore orange=0;//妈妈放橘子，儿子吃橘子
semaphore plate = 1;
Father{
    while(1){
        P(plate);
        produce an apple;
        v(apple);
    }

}
Mother{
    while(1){
        P(plate);
        produce an orange;
        v(orange);
    }

}
Daughter{
    while(1){
        P(apple);
        eat an anpple;
        V(plate);
    }


}
Son{
    while(1){
        P(orange);
        eat an orange;
        V(plate);
    }

}

29.

//读进程优先
semaphore mutex = 1;
semaphore rw = 1;
int count = 0;
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);

    }
}

//写进程优先（读写公平）
semaphore mutex = 1;
semaphore rw = 1;
semaphore w = 1;
int count = 0;
writer{
    while(1){
        P(w);
        P(rw);
        writing;
        V(rw);
        V(W);
    }

}
reader{
    while(1){
        P(w);
        P(mutex);
        if(count == 0){
            P(rw);
        }
        count++;
        V(mutex);
        V(w);//注意V的位置
        reading;
        P(mutex);
        count--;
        if(count == 0){
            V(rw);
        }
        V(mutex);

    }
}

30.哲学家进餐问题
semaphore chopstick[5] = {1,1,1,1,1};
semaphore 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)
}

31-35

31.

semaphore offer0 = 0;
semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore finished = 0;
int num = 0;
provider{
    while(1){
        num++;
        num = num%3;
        if(num==0){
            V(offer0);
        }
        if(num==1){
            V(offer1);
        }
        if(num==2){
            V(offer2);
        }
        P(finished);
    }
}
smoker0{
    while(1){
        P(offer0);
        smoke;
        V(finished);
    }
}
smoker1{
    while(1){
        P(offer1);
        smoke;
        V(finished);
    }
}
smoker2{
    while(1){
        P(offer2);
        smoke;
        V(finished);
    }
}

32.管程是一种代表共享资源的数据结构，抽象地表示系统中的共享资源，而将对该数据结构实施的操作定义为一组过程。进程对共享资源的操作都通过这组过程完成，这组过程还可以根据资源的情况接受或阻塞过程的访问，实现互斥使用共享资源。

33.①管程的名称②管程内部共享数据结构的说明③对该数据结构的一组过程④对共享数据设置初始值的语句

34.条件变量是管程中的概念，进程进入管程后被阻塞的原因定义为条件变量condition，条件变量的wait、signal类似于信号量的PV操作，都能实现进程的阻塞、唤醒，但是条件变量本身是没有值的，只能实现进程的排队等待功能。

35.互斥、不可剥夺（强调的是他人不剥夺）、请求并保持（强调的是自己不释放）、循环等待（存在一种循环等待链，链中每个进程持有的资源同时被下一个进程请求）

36-40

36.循环等待是死锁的必要条件

37.

死锁预防、避免死锁、死锁检测并解除

预防死锁的方法是破坏其中一个死锁的必要条件：

死锁避免：在每次分配资源时，都要检测此次分配是否会产生死锁危险。银行家算法是死锁避免算法

死锁检测和解除：①检测：简化资源分配图，如果能消除所有边则不死锁②解除：资源剥夺、撤销进程、进程回退

38.安全序列是进程不会发生死锁的进程执行顺序

39.

40.

内存空间的分配和回收、地址转换、内存空间的扩充、内存共享、存储保护

41-45

41.代表能够寻址的逻辑地址空间是从0到2^32^-1

42.堆区堆是程序运行中动态分配内存的区域，存放动态分配的变量，由程序员显式地控制，如malloc和new分配的变量存放在堆区

栈区内存分配和释放是自动的，一般存放与函数有关的变量，如函数参数、临时变量

43.单一连续分配（有内部碎片无外部碎片）、固定分区分配（有内部碎片无外部碎片）、动态分区分配（有外部碎片无内部碎片）

44.

45.基于顺序搜索的空间分配算法（从空闲分区表/链中选择一个分区的算法）：首次适应算法、邻近适应算法（性能最好）、最佳适应算法、最坏适应算法

基于索引搜索的空间分配算法（对于很大的空间，空闲分区链可能很长，采用顺序分配算法可能很慢，所以按照大小对空闲分区进行分类，每类空闲分区单独设置一个空闲分区链，并设置一张索引表管理这些空闲分区链）：快速适应算法（选择最小能容纳进程的大小）、伙伴系统（它用于管理操作系统中物理内存的分配与回收。该算法的核心思想是将内存划分为大小为2的幂次的块，并在分配和释放时尽可能合并相邻的空闲块以减少内存碎片。）、哈希算法（构建一张以空闲分区大小为关键字的哈希表，分配时根据分区大小计算得到哈希表中的位置）

46-50

46.分页存储管理和分段存储管理

47.根据运行作业时是否要将作业的所有界面都装入内存，分为基本分页存储管理和请求分页存储管理

48.页框也称为页帧或物理块，指的是固定大小的物理分区，页也称为页面，指的是与物理块同样大小的逻辑分区

49.系统为每个进程建立一张页面映射表，简称页表。作用是指明了每个页面在内存中存放的位置（页号->物理块号），使用页表可以让进程映像不必在内存中连续存储（使用二级页表可以使一级页表不用连续存储）

50.进程未执行的时候，页表始址和页表长度被存放在PCB中；进程执行时，CPU的页表寄存器（PTR）存放页表始址和页表长度。

51-55

51.

52.段表只能有一个，页表可以有多个

53.

基本页式存储：页号|块号逻辑地址：页号+页内偏移

基本段式存储：段号|段长|段始址逻辑地址：段号+段内偏移

基本段页式存储：逻辑地址：段号+页号+页内偏移

段表：段号|页表长|页表始址

页表：页号|块号

请求分页管理方式：页号|块号|状态位|访问字段|修改位|外存地址

逻辑地址：页号+页内偏移

请求分段式存储

54.请求分页系统的外存分为文件区和对换区，文件区采用离散分配方式，对换区采用连续分配方式，因此对换区的IO速度比文件区更快

55.

56-60

56.CLOCK算法只需考虑页面使用情况，换出最不可能用到的页。但是，换出修改过的页比换出未修改的页代价更大，这一点改进CLOCK算法考虑到了

57.

58.

好处是使程序员的编程更简单，对于已经建立映射的文件，只需按照访问内存的方式进行访问，并且能够方便多个进程访问同一磁盘文件

59.要找到文件的具体位置，就要顺序查找文件目录中的FCB。但是检索目录时，文件的其他描述信息不会用到，也不需要调入内存，所以unix等系统采用文件名和文件信息分离的方法，文件目录中每个目录仅仅由文件名和相应的索引结点号（指针）构成

60.FCB包括基本信息（文件名、文件物理位置、逻辑结构、物理结构）、存取控制信息（文件存取权限）、使用信息（文件建立时间、上次修改时间）

61-65

61.

62.文件打开后，系统就不再使用文件名，因为此时已经完成FCB在磁盘上的定位，对于打开文件表的索引号，UNIX称之为文件描述符，Windows称为文件句柄。只要文件未关闭，所有的文件操作都是通过文件描述符而不是文件名完成的

63.

64.文件系统包括：启动操作系统的方式、总块数、空闲块的数量和位置、目录结构和各个具体文件等

磁盘：主引导记录MBR（0号扇区）|分区表|分区C|分区D…

一个分区：引导块|超级块|空闲空间管理|i结点|根目录|文件和目录

MBR：计算机启动时，BIOS读入并执行MBR，MBR首先要读取分区表确定活动分区，读入活动分区的第一块，也就是引导块

引导块：负责启动该分区中的操作系统，Windows称之为引导扇区

超级块：包含文件系统中的所有关键信息，典型信息包括分区块的数量、块的大小、空闲空间的位向量表或空闲盘块号栈。在对卷中的文件进行操作前，超级块要预先读入内存

65.MAC前同步码8B、MAC地址长度6B、数据长度46-1500B，首部+尾部18B，最短帧长46+18=64B

66-70

66.

67.

68.FTP、TELNET、SMTP、DNS、TFTP、HTTP、SNMP的端口号（熟知端口号）

69.

空闲表法（序号|第一个空闲盘块号|空闲盘块数）

空闲链表法，包括空闲盘块链和空闲盘区链。空闲盘区包含若干相邻的空闲盘块

位视图法

成组链接法

70.文件系统在进程使用之前必须先安装，这就是挂载。将设备中的文件系统挂载到某个目录后，就可以通过这个目录来访问设备上的文件。这里的设备是逻辑上的设备，如一个磁盘上的不同分区都可以视为不同的设备

71-75

71.带权周转时间=周转时间/执行时间，没有单位

72.硬盘需要依次进行物理格式化、对磁盘分区（创建硬盘分区表）、逻辑格式化（文件系统的根目录、文件系统的索引结点表）、操作系统存入磁盘、每次开机时操作系统初始化（内存中准备中断向量表、中断服务程序）

73.最近一段时间内进程频繁访问的页面集合（t时刻时，最近访问过的n个页面的集合）

74.中断处理过程包括硬件完成的部分和操作系统中断程序完成的部分

硬件完成的部分：切换到内核态->关中断->保存断点和程序状态->中断服务程序寻址

操作系统完成的部分：保存现场和屏蔽字->开中断->执行中断服务程序（不需要关中断，但处于内核态）->关中断->恢复现场和屏蔽字->开中断->中断返回

75.进程唤醒指的是从阻塞态->就绪态

76-80

76.信道利用率=发送窗口发完的时间/传输周期

77.磁盘索引结点和文件一一对应，包括：文件其他信息、文件物理地址、所有指向该文件的文件名的指针计数

内存索引结点：文件被打开时，需要将当前文件的磁盘索引结点复制到内存索引结点中。每当有新进程要访问此索引结点（即打开文件）时，计数+1；访问结束-1

78.创建文件：为新文件分配新的外存空间，新建目录项

删除文件：根据文件名查找目录，删除对应的FCB和目录项，然后回收内存和磁盘空间

读文件：根据文件名查找目录，找到对应目录项后得到文件的外存地址，读指针包含在FCB中

写文件：根据文件名查找目录，找到对应目录项时得到文件的外存地址，写指针包含在FCB中

79.文件的打开过程

首先根据文件名在外存中查找目录项，将目录项复制到内存中操作系统维护的打开文件表内，然后将该文件在打开文件表中的索引返回给用户，用户就不需要每次读写都从外存中查找目录项了，而是根据打开文件表中该文件的索引（也称文件描述符）查找inode，进而得到文件信息。

多进程的操作系统采用两级打开文件表，包括系统的打开文件表和进程的打开文件表，进程的打开文件表保存了文件的当前读写指针和指向系统打开文件表中的相应条目的指针。只有第一个进程打开文件时会在系统打开文件表中创建新表项，其他进程再打开文件只是在自己的打开文件表中增加一个条目并指向系统打开文件表的对应表项。系统文件表记录指向自己表项的指针数，一旦减为0就删除该项

80.

81-85

81.Spooling技术，即“假脱机”（Simultaneous Peripheral Operations On-line）技术，是一种在计算机系统中使用的技术，旨在优化慢速I/O设备（如打印机、磁带驱动器等）与快速CPU之间的数据传输效率。

在早期的计算机系统中，I/O设备通常比CPU的处理速度慢得多，导致CPU在等待I/O操作完成时常常处于空闲状态。Spooling技术就是为了解决这个问题而设计的，其核心思想是使用磁盘空间作为输入和输出数据的缓冲区，具体工作原理如下：

输入Spooling：当多个进程产生输出数据需要打印时，这些数据首先被写入到磁盘上的一个文件（称为假脱机文件或spool文件），而不是直接发送到打印机。这样，各个进程在生成输出时不需要等待打印机逐个处理它们的数据。
输出Spooling：打印机服务进程会从spool文件中读取数据，并控制打印机打印，而此时CPU可以处理其他任务。由于打印机直接从磁盘读取数据，其速度远高于直接从CPU接收数据，因此打印过程对CPU的效率影响大大减少。

82.中断时需要保存的数据

①由硬件负责（一定会改变的数据）：程序计数器PC、程序状态字PSW

②操作系统负责（可能会改变的数据）：通用寄存器

cache和TLB都不用保存

83.请求分页系统的页面分配与置换策略

84.磁盘调度算法

先来先服务（FCFS, First-Come, First-Served）：这是最简单的磁盘调度算法。按照请求的顺序进行服务，适用于请求队列较短且请求分布均匀的情况。但可能会导致“饥饿”现象，即新的请求可能需要等待很长时间。
最短寻找时间优先（SSTF, Shortest Seek Time First）：选择距离当前磁头位置最近的请求进行服务。这种方法可以减少磁头的移动距离，提高效率，但可能会导致某些请求长时间得不到服务。
扫描算法（SCAN）：磁头从磁盘的一端开始，向另一端移动，在移动过程中服务所有请求。到达另一端后，磁头反向移动，继续服务请求。这种算法也称为电梯算法，因为它类似于电梯在建筑物中的运动。
循环扫描算法（C-SCAN）：类似于SCAN算法，但是磁头在到达磁盘的一端后，直接跳转到另一端，而不是反向移动。这样可以保证每个请求都能在一定时间内得到服务。

5.LOOK调度算法：类似于SCAN算法，但是磁头在到达磁盘的一端后不会继续移动到尽头，而是立即返回服务其他请求。这样可以减少不必要的寻道时间。

6.C-LOOK调度算法：类似于C-SCAN算法，但是磁头在到达磁盘的一端后不会继续移动到尽头，而是直接跳转到另一端的第一个请求。

进程

1.生产者-消费者——进程与进程之间是生产资源和消耗资源的关系

semaphore mutex=1;
semaphore empty = 1;
semaphore full = 0;
producter(){
    while(1){
        P(empty)
        生产
        P(mutex)
        放到盘子里
        V(mutex)
        V(full)
    }   
}

consumer(){
    while(1){
        P(full)
        从盘子里取出
        P(mutex)
        消费
        V(mutex)
        V(empty)
    }
}



apple_provider(){
    while(1){
        P(plate)
        生产苹果
        P(mutex)
        苹果放入盘子
        V(mutex)
    }
}
orange_provider(){
    while(1){
        P(plate)
        生产橘子
        P(mutex)
        橘子放入盘子
        V(mutex)
    }
}
apple_consumer(){
    while(1){
        P(mutex)//不需要mutex1，plate容量为1时也不需要mutex
        从盘子中取苹果
        V(mutex)
        V(plate)
        吃苹果

    }
}
orange_consumer(){
    while(1){
        P(mutex)
        从盘子中拿橘子
        V(mutex)
        V(plate)
        吃橘子
    }
}

2.理发师问题——服务与被服务

int waiting = 0;
semaphore service = 0;
customer(){
    P(mutex)
    取号
    waiting++;
    V(mutex)
    等待叫号
    P(service)
    被服务
}
server(){
    while(1){
        P(mutex)
        if(waiting){
        叫号
        waiting--;
        V(mutex)
        提供服务
        V(service);//服务完以后才增加一个service
        }else{
            V(mutex);//有if就要有else
        }
    }

}

int waiting = 0;
semaphore service = 0;
semaphore customer = 0;
customer(){
    P(mutex)
    if(waiting>MAX){
        V(mutex);//这里要V
        return;
    }
    取号
    waiting++;
    V(mutex)
    V(customer)
    等待叫号
    P(service)
    被服务
}
server(){
    while(1){
        P(mutex)
        if(waiting){
        叫号
        waiting--;
        V(mutex)
        提供服务
        V(service);
        }else{
            V(mutex);
            P(customer)//睡觉的含义是暂停循环
        }
    }

}

3.读者写者问题——同类不互斥、异类互斥

4.哲学家进餐问题——只有一类进程，每个进程拥有多种资源才能运行

让进程一口气获得所有资源，再开始运行

P(){
    while(1){
        P(mutex)
        P(bowl)
        取碗//
        P(c[i]%n)
        取左筷子
        P(c[i+1]%n)
        取右筷子
        V(mutex)
        吃饭

        还左筷子
        V(c[i]%n)
        还右筷子
        V(c[i+1]%n)
        还碗
        V(bowl)
    }
}

5.单纯的同步问题——前驱后继图

步骤（先写草稿，再誊写，DS也是如此）

1.有哪些进程？每类进程对应一个函数

2.在函数内部，用中文描述每个动作，如果动作只做一次，则不加while，动作不断重复则加while(1)。动作有的可以被PV操作平替，当然也可以保留这些动作

3.每个动作前是否需要P什么（注意隐含的互斥,是否有缓冲区）？只要有P必有V，每写一个P都要检查所有进程在合适的地方添加一个V

4.所有PV写完后，再去定义信号量

5.检查多个P操作连续出现(连续出现是指释放前继续P）是否会产生死锁。（若某信号量PV操作总连续出现，中间没有夹其他P，因此该信号量一定不会产生死锁）

6.检查是否满足题目需求，并添加注释

存储系统

进程的虚拟空间（若32位系统，则进程的虚拟内存为4GB）：在虚拟空间中，页是连续存储的；物理空间中，页框是离散的

操作系统内核（1GB，所有进程共享，所有页表映射到同一个物理地址）|

栈区 |

公共库函数 |

堆区（临时变量、malloc）

静态变量、全局变量|

存放指令区域|

每个进程并不会把4GB的虚拟空间全部用完

多级页表：顶级页表占用连续的物理页框，二级、三级页表最多只占用一个页框

文件

逻辑结构：看起来是连续的（顺序、索引（解决变长记录无法顺序访问问题）、索引顺序）

顺序文件。这是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。
索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。
索引顺序文件。这是上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。

物理结构：顺序、链接、索引

访问（变长记录索引分配）文件的过程：

1.文件系统挂载时，操作系统会读取根目录（在磁盘的固定位置）的信息到内存。根据文件相对于根目录的路径，解析出文件所在目录

2.根据文件名查询目录，找到对应的目录项（文件名|inode索引结点块号），将磁盘inode（index node, 索引结点）复制到活动inode中

3.当打开合法时，为文件分配用户打开文件表表项和系统打开文件表表项，并为后者设置初值，通过指针建立表项和活动inode之间的联系，再将文件描述符返回给调用者

4.inode包含文件的各种信息（就是FCB中的信息，但不包含文件名）。inode的结构（文件属性|索引表）如下图所示，其中，直接地址|一级间接地址|二级间接地址…被称为索引表。间接地址指向的是下一级索引表。

一级间接指针指向一个索引块，该索引块只包含直接数据块指针。（注意索引块不再是索引结点的结构）
二级间接指针指向一个索引块，该索引块只包含一级间接指针，这些一级间接指针再指向只包含直接数据块指针的索引块。

如果文件在磁盘中是连续分配或链接分配，则目录项（文件名|文件起始块号+文件大小|其他文件属性）。如果是显示链接分配，在磁盘的固定区域找到FAT表调入内存（FAT管理电脑的所有磁盘块，不只是一个文件的），根据FAT表和文件的起始块号，找到文件各项在磁盘中的位置

同一个簇不能一部分存一个文件，另一部分存另一个文件

一个inode对应一个文件，注意索引结点的间接地址的指针指向的是索引块，索引块不能被称为索引结点

硬链接和软链接：硬链接同一个文件使用相同的索引结点，软连接是单独的文件，有自己的索引结点，软连接的索引结点指向文件真正的索引结点

十八届三中全会
内容：①提出全面深化改革总目标


二十届三中全会
背景：站在新的历史起点上
主题：中国式现代化
内容：①科学谋划了围绕中国式现代化进一步全面深化改革的总体部署②继续完善和发展中国特色社会主义制度，推进国家治理体系和治理能力现代化（总目标）③新征程的根本动力仍然是改革开放，坚持将改革开放进行到底

磁盘

1.物理格式化：划分扇区，检测坏扇区，用备用扇区替代坏扇区

2.逻辑格式化：磁盘分区（分卷），完成各分区文件系统的初始化（在磁盘开头创建MBR主引导记录、在各分区开头创建引导块、超级块、位示图、inode区、根目录）

3.操作系统初始化，将操作系统程序添加到根目录中，在内存中准备中断向量表和中断服务程序

4.开机：CPU在ROM中找到操作系统引导程序，引导主机读入磁盘的主引导记录MBR，启动MBR中的磁盘引导程序并读入分区表。找到操作系统所在分区的引导块，执行引导块中的操作系统初始化程序，该程序检索根目录找到操作系统，完成开机。

在系统内存中设置磁盘缓冲区可以减少磁盘IO的次数，如果没有缓冲区，则每次IO只能将一块内容读入内存。（一次可能指的是操作系统交付一次IO任务）

并发共享虚拟异步

内核程序和应用程序

中断和异常

系统调用

操作系统内核功能

操作系统引导

进程控制

C程序的执行过程

1-10

11-20

21

22-30

31-35

36-40

41-45

46-50

51-55

56-60

61-65

66-70

71-75

76-80

81-85

1-10

11-20

21

22-30

31-35

36-40

41-45

46-50

51-55

56-60

61-65

66-70

71-75

76-80

81-85

进程

存储系统

文件

磁盘

发送评论 编辑评论

发送评论编辑评论