西电软工操作系统复习纲要-Toy模板网

这篇具有很好参考价值的文章主要介绍了西电软工操作系统复习纲要。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面

时间过得真快，转眼大二已经结束了。这学期软工的课程虽然不多，但是感觉都挺抽象的，个人也是在复习上下了比较大的功夫（主要是平时也没学），但最后的结果怎么说的，不咋地…

以下内容是个人根据复习提纲以及往年题进行的知识点总结，其中也会包含今年试题的回忆版，复习时只做了部分总结就没有发出来。考完试再着手一方面是帮助自己回忆os的相关知识，另一方面方便后来的学弟学妹可以借鉴一下。今年的成绩，贴张图自己体会吧…90+的只有12个人，当然没有我（哭）
西电软工操作系统复习纲要

第一章引论（Overview）

引论是对整本书要学的知识点的总结，要点挺少的。

一. 什么是操作系统？

os是什么？

答：是运行在内核态的软件（Software that runs in kernel mode），是源管理器（Source manager），扩展机器（extended machine），是用户与系统硬件的接口。

2022原题：

From the user’s point of view，the operating system is（A）

A. Extended machine, i.e. providing an abstract interface between user and computer hardware.
B. Software for limiting the speed of processes.
C. Software for organizing computer workflow reasonably.
D. A set of resources.

os的结构特征？

答：层次结构（Layered）、虚拟机器（virtual machine）、庞大而单一的（monolithic）。

什么是系统调用（system call）？

答：为了从操作系统获取服务，用户程序必须进行系统调用，该调用进入内核并调用操作系统。TRAP指令从用户模式切换到内核模式，启动操作系统。当工作完成后，根据系统调用之后的指令将控制返回给用户程序。

呃呃这个好像今年也考了一个概念题，背就行了。

第二章进程与线程（Process & Thread）

这章就是重量级咯，属于是十分重点的内容。

书上是这么说的：

操作系统中最核心的概念是进程：这是对正在运行程序的一个抽象。操作系统的其他所有内容都是围绕着进程的概念展开的，所以，让操作系统的设计者（及学生）尽快并透彻地理解进程是非常重要的。

一. 什么是进程

什么是进程？

答：正在运行的程序的实例。

进程与程序的本质区别？

答：进程是动态的而程序是静态的（进程是程序的一次执行）；进程是暂时的，程序是永久的；进程和程序的组成不同。

fork( )和exec( )的区别？

答：这个就十分重要了，可能你都没听说过，其实这是os课设中的内容。往年常考，算是老演员了。具体区别用下面两个例子来说明，问题是下面两段程序分别打印几个os exam

#include <unistd.h>
#include <stdio.h>
int main(){
	pid_t pid;
	pid = fork();
	if(pid == 0)
		printf("os exam\n");
	if(pid > 0)
		printf("os exam\n");	
	return 0;
}

#include <unistd.h>
#include <stdio.h>
int main(){
	pid_t pid;
	pid = fork();
	if(pid == 0)
		printf("os exam\n");
	return 0;
}

其实知道fork( )和exec( )两个函数的作用这题就十分简单了。fork( )是由父进程创建一个一模一样的子进程，子进程从fork( )函数结束处开始执行，而父子进程之间执行的先后顺序是随机的，且此函数执行返回的结果为0。所以这题答案就是两次和一次了，首先第一段程序是父进程执行fork( )后生成子进程，pid=0，之后父子进程执行后面的判断语句，父进程pid > 0，子进程pid=0，故打印两次；下面这题一样。

将第二段代码改一下呢？

#include <unistd.h>
#include <stdio.h>
int main(){
	pid_t pid;
	pid = fork();
	if(pid == 0)
		printf("os exam\n");
	if(pid > 0){
        execl("/bin/ls","ls","-1",0);
        printf("os exam\n");
    }	
	return 0;
}

此段代码出现了execl( )，这又是啥呢？它其实是exec函数族中的一个函数。
西电软工操作系统复习纲要
exec函数族可以根据指定的文件名或目录名找到可执行文件，并用它来取代原调用进程的数据段、代码段和堆栈段。在执行完后，原调用进程的内容除了进程号外，其它全部被新程序的内容替换了。啥意思呢，可以简单地理解为执行exec函数族之后，其后面的代码都不执行了。回到题目，上述的 ”os exam“ 的打印次数肯定就是一次了。父进程打印一次，子进程会执行execl( )函数，之后的打印语句不再执行。

再来一题，20年原题：

For the program listed below, how many “hello” will be printed? Please explain your answer.

int main()
{
	fork();
	printf("hello\n"); 
	execl("/bin/ls","ls","-l",0); 
	printf("hello\n");
}

答案自行解决吧嘻嘻。这题22年也考了，作为最后一个大题，两个小问，第一个比较平常就问你打印次数，第二题就比较怪了，问你如何证明exec函数执行为啥之后的程序不会执行？（好像是这个吧，记不太清了，反正是问原理的，当然我不会zzz）

什么是shell？

答：命令解释器。

进程创建的四种状态（four events for process creation）

系统初始化
正在运行的进程执行了一个创建进程的系统调用
用户请求创建一个新进程
一个批处理作业的初始化

进程终止的四种状态（four events for process creation）

正常退出（自愿的）
出错退出（自愿的）
严重错误（非自愿的）
被其他进程杀死（非自愿的）

什么是PCB？

答：PCB（process control block）进程控制块。包含寄存器，程序寄存器，程序状态字psw，堆栈指针，堆栈状态，进程ID。每一个进程都对应一个PCB，是进程存在的唯一标志。

进程的五种状态：创建（new）、就绪（ready）、运行（run）、阻塞（block）、终止（terminated）

二. 什么是线程

什么是线程？线程与进程的区别？

答：线程是轻量级进程。二者区别：线程有自己的程序计数器，寄存器，堆栈，状态。可以共享进程的地址空间，全局变量，打开文件等。进程是资源的管理者，线程是进程中运行的实体，是cpu的调用者。

这题今年作为简答题出现。

什么是用户级线程，什么是内核级线程，其各自的优缺点是什么？

答：① 用户级线程 User Level Thread：线程表在用户空间，进程表在内核空间。内核不知道线程的存在。

优点：线程的切换不需要陷入内核，进行上下文切换；允许进程有自己的调度算法

缺点：线程阻塞时会导致进程的阻塞。

② 内核级线程 Kernel Level Thread：线程表和进程表都在内核空间。

优点：线程阻塞时可以检查是否有其他可运行的线程（不止当前进程，也有可能其他进程）

缺点：线程切换开销很大

三. 进程间通信

这边的概念以及程序都十分重要，集中在70-83页，理解并会写代码，很可能考代码补全，虽然22年没考…其中peterson算法，TSL避免死锁，信号量解决生产者消费者（有一年考了利用线程解决生产者消费者问题，书上93页有代码，其实和其他方法大差不差，但是其中有的函数名称不看的话可能不知道）都是很重要的。

竞争条件 Race condition：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序。
互斥 mutual exclusion：以某种手段确保，当一个进程在使用共享变量或文件时，其他进程不能进行同样操作。
四种解决互斥的方案 four conditions to hold to have a good solution for race condition/mutual exclusion：
- 任何两个进程不能同时处于临界区
- 不应对CPU的速度和数量作出假设
- 临界区外运行的进程不能阻塞其他进程
- 不能使进程无期限等待进入临界区
临界区 critical region：对共享内存进行访问的程序片段称为临界区。
自旋锁 spin lock：用于忙等待，也叫忙等锁（busy-waiting lock）
自旋锁和信号量的区别？信号量和互斥量的区别？

答：自旋锁是自选等待，用于忙等待，对系统负载大，浪费cpu时间，效率较高，是关抢占的；信号量是睡眠等待，对系统消耗小，因为进行了进程间的切换效率较低，没有关抢占。信号量的值是0或者正数，而互斥量的值只能是0或者1；信号量一般是实现在内核态的，而互斥量是实现在用户态的。

管程：是一个由过程，变量，数据结构组成的一个集合。进程只能通过访问管程中的过程来访问过程中的数据结构。

四. 调度

进程调度算法，主要掌握FCFS、SJF、Round-Robin、Multiple Queue四种方法即可，考的比较少，近几年都没有考到。

但是这种调度方法还是要掌握的，对进程就绪、运行等状态有更好的认识，且跟后面的页面调度算法类似，要注意会画调度的甘特图。

五. 经典IPC问题

老演员了，哲学家进餐和读者写者问题。书上的代码，理解会写。

第三章内存管理（Memory Management）

也是一个重点章节，22级考的特别多…

一. 虚拟内存

static relocation & dynamic relocation

静态重定位：用户程序加载到内存时，一次性实现逻辑地址到物理地址的转化。把作业装入内存时的地址变化。当一个程序装载到地址x时，常数x被加到每一个程序地址上。

动态重定位：在逐条指令执行时，完成地址转换。在装载时无需重定位。
Paging：物理内存按照固定大小划分成若干单元，单元就是页框。
MMU：memory management unit内存管理单元，虚拟地址被送到MMU，MMU将虚拟地址映射为物理地址
Page Table：页表的目的就是将虚拟页面映射成页框。页表由页表项构成。实际内存的每个页框对应了一个表项，而不是每个虚拟页面对应一个表项。
TLB：Translation Looked aside buffer转换检测缓冲区，又叫快表。

计算机的一个小型硬件设备，将虚拟地址直接映射到物理地址，不需要再访问页表，通常在MMU中，包含少量的表项。当虚拟地址放入MMU中时，首先通过硬件在TLB中将虚拟页号与TLB中所有表项进行同时匹配，如果有效匹配，则取出页框号，不用访问页表。如果虚拟页号不在TLB中，MMU就会进行正常的页表查找，并且替换TLB 的表项。

二. 页面置换算法

没啥好说的，OPT、FIFO、LRU都要掌握，这三种今年都考了，问你缺页次数。看个例题吧：
西电软工操作系统复习纲要

三. 内存动态分区分配

也没啥好说的，首次适应、最好适应、最坏适应、领近适应，今年考了。这是原题：
西电软工操作系统复习纲要

四. 系统设计问题

可把我坑惨了，我没细看，结果考了两题。

Memory mapped files：进程通过一个系统调用(mmap)，将一个文件映射到其虚拟地址空间的一部分。对文件的读写，就像内存中的字符数组，而不用通过读写来访问文件。（这个考了）
DLL：shared library，dynamic linked libraries 共享库又称动态链接库，当一个程序和一个共享库链接时，连接器并没有加载所有的函数，有的函数只是加载了一段能在运行时绑定被调用函数的存根历程。当一个共享库被装载和使用时，整个库并不是一次性并装入内存。而是根据需要，以页面为单位装载的，没有被调用的函数是不会被装入内存的。（这个考了）
Shared Pages:进程实用相同的 i 空间页表。

第四章文件系统（File System）

一. 文件系统的实现

hard link & soft link

硬链接：两个文件目录指向一个inode；磁盘块不列入目录，列入目录的是i节点
软连接：符号链接，创建一个链接文件link，文件内容为要共享的文件的路径，把该文件放在B的目录下，只有真正的文件拥有者才拥有者真正的Inode。

FAT作用

FAT表：取出每个磁盘块的指针字，放到内存的一个表中。
作用：整个块都可以存放数据（不用第一个字放指针），随机访问也变容易了）。只要目录项中记录一个整数，按照它可以找到文件的所有块。

inode：最后一个记录了各个文件分别包含哪些磁盘块的方式是给每个文件赋予一个称为 i 节点的数据结构，其中列出了文件属性和文件块的磁盘地址。给定 i 节点，就能找到文件的所有块。
inode相较于FAT的优势：只有在文件打开时，i 节点才在内存中，为了打开文件而保留 i 节点的数组所占据的空间比FAT表要小得多。（今年考了）

二. 杂项

LFS：把磁盘当成一个大的循环使用的Log，每次都是从当前位置连续向后写，写到末尾，再返回从头开始向后写，这样就可大大降低寻道时间。所有的写操作最初都被缓冲在内存中，然后周期性的把已缓冲的写作为一个单独的段，在日志的末尾写入磁盘。要打开一个文件，则首先需要在i节点图中找到文件i节点。一旦文件定位后就可以找到相应的块的地址。
Journaling File System:保存一个用于记录系统下一步要做什么的日志。
VFS：将多种的文件系统统一成一个有序的结构。抽象出所有文件系统的共有部分，并将这部分代码放在单独的一层，该层调用底层的实际文件系统来管理数据。

呃呃反正22级没考。

第五章输入/输出（Input/Output）

Memory-Mapped I/O definition：内存映射IO,将所有控制器映射到内存空间中，每个控制器被分配唯一的一个内存地址，并且不会有内存被分配这个地址。这样的系统称为内存映射I/O。
Programmed I/O &Interrupted-Driven I/O &DMA I/O difference

这一章讲的不深，最重要的也就这个知识点了，年年考

Programmed I/O：CPU一直检查外设

Interrupted-Driven I/O：允许CPU在等待外设的时候，做些其他的事情，使用中断机制，中断发生在每个字符上。

IO using DMA：每个缓冲区中断一次，CPU可以自由在IO期间做其他事情。数据传输由DMA在内存和I/O中完成。
磁臂调度算法：FCFS、SSF、ELEVATOR。看个例题就理解了，22年没考

第六章死锁（Deadlock）

Deadlock：如果一个进程集合中的每一个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就是死锁的。
四个死锁必要条件及解决方案

互斥条件：将临界资源改造为可共享使用的资源，如spooling技术
占有并等待：运行前分配好所有需要的资源，之后一直保持
不可抢占条件：申请的资源得不到满足时，立即释放拥有的所有资源；申请的资源被其他进程占用时，由操作系统协作剥夺
环路等待：给资源编号，必须按照编号从小到大的顺序申请资源

safe state：没有死锁发生，即使每一个进程突然请求对资源的最大需求，也可能存在某种调度次序能够使每一个进程运行完毕。
Unsafe state：从安全状态出发，系统能保证所有的进程都能完成，从不安全状态出发，就没有这样的保证。

安全状态不一定一定不会发生死锁。不安全状态也不代表当前状态就是死锁状态，当前状态也可能是非死锁，但继续向下运行，一定发生死锁。

银行家算法：你懂的，必考，也不难
两阶段锁two-phase lock：第一阶段进程对所有所需的记录进行加锁，一次锁住一个记录。第二阶段完成更新然后释放锁。如果第一阶段某个进程需要的记录已经被加锁，该进程释放它所有加锁的记录，然后重新开始第一阶段。
活锁live lock：两个进程都在运行，但都没有实质性的进展。当进程意识到它不能获得下一个锁，就会释放已经得到的锁，然后等待一段时间，再尝试一次。当几个进程同时这么做。这个过程没有进程阻塞，甚至可以说进程正在活动，然而进程并不会继续往下执行，称为活锁。
饿死：进程永远得不到执行。