操作系统学习笔记

进程和线程

进程和线程的区别

线程具有许多传统进程所具有的特征，故又称为轻型进程(Light—Weight Process)或进程元；而把传统的进程称为重型进程(Heavy—Weight Process)，它相当于只有一个线程的任务。在引入了线程的操作系统中，通常一个进程都有若干个线程，至少包含一个线程。

• 根本区别：进程是操作系统资源分配的基本单位，而线程是处理器任务调度和执行的基本单位
• 资源开销：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。
• 包含关系：如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程。
• 内存分配：同一进程的线程共享本进程的地址空间和资源，而进程之间的地址空间和资源是相互独立的
• 影响关系：一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。所以多进程要比多线程健壮。
• 执行过程：每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，两者均可并发执行

进程的状态转换

三种基本状态：

• 运行态：占用CPU，并在CPU上运行
• 就绪态：已经具备了运行条件，但由于没有空闲的CPU，而暂时不能运行
• 阻塞态：因等待某一事件而暂时不能运行

另外两种状态：

• 创建态：进程正在被创建，操作系统为进程分配资源，初始化PCB
• 进程正在从系统中撤销，操作系统会回收进程拥有的资源，撤销PCB

进程间的通信

• 对于同步和互斥的理解：

区别：

互斥：是指三部在不同进程之间的若干程序片断，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。

同步：是指散步在不同进程之间的若干程序片断，它们的运行必须严格按照规定的 某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。

联系：

同步是一种更为复杂的互斥，而互斥是一种特殊的同步。也就是说互斥是两个线程之间不可以同时运行，他们会相互排斥，必须等待一个线程运行完毕，另一个才能运行，而同步也是不能同时运行，但他是必须要安照某种次序来运行相应的线程（也是一种互斥）。

• 进程间为什么需要通信

在操作系统中，协作的进程可能共享一些彼此都能共同读写的一些有限资源。而这些资源是有限的，或者如一些共享内存，进程随意读写可能会造成数据的顺序，内容等发生错乱，进程不能对其随意的使用，读写等。从而会发生竞争。我们把对共享内存进行访问的程序片称为临界资源或临界区，对同一共享内存，任何时候两个进程不能同时处于临界区.

• 进程间通信的目的：

• 数据传输：一个进程需要将它的数据发送给另一个进程。

• 通知事件：一个进程需要向另一个或一组进程发送消息，通知它（它们）发生了某种事件（如进程终止时要通知父进程）。

• 资源共享：多个进程之间共享同样的资源。为了做到这一点，需要内核提供互斥和同步机制。

• 进程控制：有些进程希望完全控制另一个进程的执行（如 Debug 进程），此时控制进程希望能够拦截另一个进程的所有陷入和异常，并能够及时知道它的状态改变

• 进程间通信的方式

1.管道通信：

• 管道只能采取半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道
• 各个进程要互斥的访问管道
• 数据以字节流的形式写入管道，当管道写满时，写进程的write()系统调用将会被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将会被阻塞

注意：匿名管道只能用于有亲缘关系间的进程，而有名管道允许无亲缘关系的进程间通信

2.消息队列MessageQueue：

消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

3.信号

信号是进程之间唯一的异步通信机制，信号的主要来源主要有硬件来源（入键盘操作ctrl + C） 和软件来源（如kill命令），信号传递的信息比较少，主要用于通知进程某个时间已经发生。比如利用kill pid，可以让系统优雅停机。

4.信号量

信号量是一个计数器，可以用来控制多个进程对资源的访问，通常作为一种锁机制，防止某个进程正在访问共享资源，其他进程也访问资源

5.共享内存

共享内存就是映射一段能被进程之间共享的内存，这段内存由一个进程创建，但是多个进程都可以共享访问，是最快的一种进程间通信的方式（不需要从用户态到内核态的切换），它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

6.Socket

socket套接字，不仅仅可以用于本地进程通信，还可以用于不通主机进程之间的通信。

进程的调度和处理机调度

进程调度(低级调度)，就是按照某种算法，从就绪队列中选择一个进程为其分配处理机

• 进程调度的时机

• 进程主动放弃处理机：进程正常终止，发生异常终止，进程主动请求阻塞(如等待I/O)等

• 进程被动放弃处理机：分配的时间片用完，IO中断，有更高的优先级进程进入就绪队列等

• 调度算法

• 设置多级就绪队列，各级的队列优先级从高到低，时间片从小到大

• 新进程到达时先进入第一级队列，按照先来先服务排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列的队尾，如果此时已经在最下级队列，则从新放回最后一级队列的队尾

• 只有当第K级的队列为空时，才会为K+1级的队列队头的进程分配时间片

• 先来先服务

• 最短作业优先

• 最高响应比优先 响应比：(等待时间+服务时间)/要求服务的时间

• 时间片轮转调度

• 优先级调度

• 多级反馈队列

内存管理

内存管理的功能

• 内存空间的分配与回收：由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率。
• 地址转换：在多道程序环境下， 程序中的逻辑地址与内存中的物理地址不可能一致， 因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址。
• 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存 。
• 存储保护：保证各道作业在各自的存储空间内运行，互不干扰。

内存分配方式

连续分配管理方式

连续分配方式，是指为一个用户程序分配一个连续的内存空间，比如说某用户需要1GB的内存空间，它就在内存空间中分配一块连续的 1GB的空间给用户。

• 单一连续分配：内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。
• 固定分区分配：固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备作业队列中， 选择适当大小的作业装入该分区，如此循环。
• 动态分区分配：动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分区方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区 ，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。

分配策略算法

• 首次适应 (First Fit) 算法：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。
• 最佳适应 ( Best Fit )算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。
• 最坏适应 ( Worst Fit )算法：又称最大适应 （ Largest Fit )算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。
• 邻近适应 ( Next Fit )算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。

非连续分配管理方式

非连续分配允许一个程序分散地装入到不相邻的内存分区中

分页存储管理方式

• 将内存空间分为一个个大小相等的分区(比如：每个分区4KB)，每个分区就是一个页框(页帧，内存块，物理块)，每个页框都有一个编号，即页框号(页帧号，内存块号，物理块号)，页框号从0开始
• 将用户进程的地址空间也分为与页框大小相等的一个个区域，称为 "页"或 “页面”，每个页面也有一个编号，即页号，页号也是从0开始(注意：进程最后一个页面可能没有页框那么大，因此页框不能太大，否则会产生过大的内部碎片)
• 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中，则进程的页面和内存的页框产生了一一对应的关系

image.gif

分段存储管理方式

• 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名(在低级语言中，程序员使用段名来编程)，每段从0开始编址
• 内存分配规则：以段位单位进行分配，每个段在内存中占据连续空间，但是各个段之间可以不相邻
• 优点：由于是按逻辑功能划分，用户编程更加方便，程序的可读性更高

image.gif

分页和分段存储管理的区别

• 页是信息的物理单位，分页是为实现离散分配方式，提高内存利用率。分页仅仅是由于系统管理的需要而并不是用户的需要。而段则是信息的逻辑单位，是为了更好地满足用户的需要。
• 分段比分页更容易实现信息的保护与共享，分段可以在某个段编写逻辑，实现对另外一个段的保护，而分页不行
• 页的大小固定且由系统决定，而段的长度取决于用户所编写的程序。

页面置换算法(追求最少的缺页率)

最佳置换算法OPT(无法实现，作为一个标准):每次选择淘汰的页面将是以后永不使用，或者在最长的时间内不被使用，由于无法预知将会访问哪些页面，所以这种算法无法实现，只能作为一个标准

例如：需要访问7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1，则访问顺序：

image.gif

先进先出置换算法FIFO:每次选择淘汰的页面是最早进入内存的页面

例如：需要访问 3 2 1 0 3 2 4 3 2 1 0 4 ，则访问顺序

image.gif

最近最久未使用置换算法(LRU)：每次淘汰的页面是最近最久未使用的页面

例如：需要访问 1 8 1 7 8 2 7 2 1 8 3 8 2 1 3 1 7 1 3 7 则访问顺序

最近未用置换算法NRU(Clock算法):为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1.当需要淘汰某个页面时，只需要检查页的访问位。如果是0，就将该页面换出，如果是1，则将他置为0，暂不换出。继续检查下一个页面，如果第一轮扫描之后全是1，则扫描完成，这些都置为0.再进行第二轮扫描，因此简单的Clock算法选择一个页面淘汰最多两轮

文件管理

文件的分配方式(物理结构)

文件块和磁盘块：类似于内存的分页

磁盘块:磁盘中的存储单元会被分为一个个"块/磁盘块/物理块"，在很多的操作系统中，磁盘块的大小与内存块，页面的大小相同

文件块：在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间被分为一个一个的文件块，文件的逻辑地址可以表示为(逻辑块号，块内地址)的形式。用户通过逻辑地址来操作自己的文件，操作

文件的分配方式

连续分配：要求每个文件在磁盘上占有一组连续的块

• 优点：支持顺序访问和直接访问(类似数组)，连续分配的文件在顺序访问时速度最快
• 缺点：不方便文件的扩展，存储空间利用率低,会产生磁盘碎片

链接分配：采取离散分配的方式，为文件分配离散的磁盘块。(类似链表数据结构)

• 隐式链接：目录中记录的文件的起始块号和结束块号。除了文件最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的,每次访问某个磁盘块都需从头访问

• 优点：方便文件的扩展，不会产生碎片问题，外存的利用率高

• 缺点：只支持顺序访问，不支持随机访问，查找时效率低

image.gif

显示链接：把用于链接文件各物理块的指针显示的存放在一张表中，即文件分配表。
文件目录只需要记录起始块号。一个磁盘只需要设置一张分配表，开机时，将分配表读入内存，并常驻内存

优点：支持顺序访问，也支持随机访问，方便文件的扩展，不会产生碎片问题，地址转换不需要访问磁盘，因此文件的访问效率更高

缺点：文件分配表需要占据一定的存储空间

image.gif

索引分配：索引分配允许文件离散的分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理的页表–建立逻辑页面到物理页面之间的映射关系)。索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块

文件存储空间管理

存储空间的划分和初始化

存储空间的划分：将物理磁盘划分为一个个文件卷(逻辑卷，逻辑盘，如Windows系统下的C，D，E盘等)

有的系统支持超大型文件，可由多个物理磁盘组成一个文件卷

存储空间的初始化：将各个文件卷划分为目录区，文件区

• 目录区：目录区主要存放文件的目录信息(FCB)，用于磁盘存储空间的管理的信息
• 文件区：文件区用于存放文件数据

存储空间的管理方法

空闲表法：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可以采用首次适应，最佳适应，最坏适应等算法来决定要为文件分配哪个区间

空闲链表法：分为—>

• 空闲盘块链：以盘块为单位组成一条空闲链
• 空闲盘区链：以盘区为单位组成一条空闲链

位示图法：每个二进制位代表一个盘块。例如可以用"0"来代表盘块空闲 ，"1"代表盘块已经分配

成组链接法：UNIX采用的策略，适合大型的文件系统。

IO管理

磁盘调度算法

一次磁盘读/写操作需要的时间：寻找时间+延迟时间+传输时间

• 寻找时间：在读/写前，将磁头移动到指定磁道所画的时间(启动磁头臂和移动磁头臂)
• 延迟时间：通过旋转磁盘，使磁头定位到目标扇区所需要的时间
• 传输时间：从磁盘中读出或写入数据所经历的时间

磁盘调度算法：

• 先来先服务算法(FIFO)：根据进程请求访问磁盘的先后顺序进行调度
• 最短寻找时间优先算法(SSTF)：优先处理的磁道是与当前磁道最近的磁道，可以保证每次的寻道时间最短，但是不能保证总的寻道时间最短(贪心算法)
• 扫描算法(SCAN，电梯调度算法)：SSTF算法可能会产生饥饿，磁头有可能在一个小区域内来回移动，因此扫描算法规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道才能往外移动，在这个基础上使用SSTF算法
• 循环扫描算法(C-SCAN)：SCAN算法对于各个位置磁道的响应频率不平均，C-SCAN算法在SCAN算法的基础上规定：只有磁头朝着某个特定的方向移动时才能处理磁道的访问请求，而返回时直接快速移动到起始端而不处理任何请求

死锁

对死锁的理解

如果一组进程中的每个进程都在等待一个事件，而这个事件是有这组中的某一个进程触发，这种情况则会导致死锁

资源死锁的条件：发生死锁时，以下四个条件必须全部具备

• 互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
• 保持和等待条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
• 不可抢占条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
• 循环等待条件：在发生死锁时，必然存在一个进程–资源的环形链。

死锁的避免->银行家算法

当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

安全序列的判断：

死锁的解除

• 资源剥夺法：挂起(暂时放到外存上)某些死锁的进程，并抢占他的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿
• 撤销进程法：强制撤销部分，甚至全部的死锁进程，并剥夺这些进程的资源。虽然实现简单，但是代价可能较大
• 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步

简单来说，死锁的破坏就是对死锁产生的四个条件进行破坏，让其中任意一个不满足即可。