1. 处理机调度算法
先来先服务算法：（FCFS， First Come First Serverd），优点算法简单，如果时间短的进程排在了处理时间长的进程后面，就需要很长时间才能执行。
短进程优先算法：运行时间短的进程先执行，但是可能导致，运行时间长的进程一直执行不到。
最高响应比优先算法：采用等待时间与，进程运行时间比值的策略，解决了，执行时间长的进程，一直等不到资源的问题，但是不能抢占
时间片轮转算法：给每一个进程分配一定的时间片，时间片到期，执行时钟中断，交互性比较好，但是在上下文切换时会有额外的系统开销（时间片根据经验值来设（10ms, 用在上下文切换时间为1ms））
多级队列调度算法：在一般的操作系统中使用的算法，将就绪队列划分成多个独立的队列，时间长的放到一个队列中，执行先到先处理算法，时间短的放到另个队列中，执行时间片轮转算法
公平共享调度：控制用户对系统资源的调度，重要用户优先调度，不重要用户无法抢占资源。
2.进程同步互斥
1.0同步与互斥的区别
互斥体现的是排它性，同步体现的是协作性，互斥的抢占资源之间不知道对方的存在，也无法限制对临界区访问顺序，同步的资源之间知道对方的存在，可以控制对临界区访问顺序，如先生产再消费，同步中一般包含互斥，互斥是同步的一种实现方式，同一时间只能有一个线程或者进程访问临界区。
1.1
同步与互斥都是为了协调对共享资源的访问，同步可以通过信号量来实现，比如，多个线程同时更新一个变量，这是一种同步，在更新变量时需要加锁，每个线程都需要加锁，不能一个线程加了，一个线程没加，这又是一种同步；互斥是，同一时间只能有一个线程进入临界区，可以通过加锁来实现。
1.2同步、互斥、死锁、饥饿、临界区
同步：协调对共享资源访问的方式
互斥：一个进程占用资源，其他进程不能使用
死锁：多个进程各占一部分资源，相互等待
饥饿：几个进程轮流抢占资源，一个进程一直抢不到资源
临界区：进程中访问临界资源，需要互斥执行的一段代码
1.3临界区访问规则：
（记忆技巧：一入三等待）
（另一种问法，临界区是如何解决冲突的？）
（同步机制遵循的原则是什么？）
空闲进入：如果临界区空闲，则任何线程或者进程都可以进入
忙则等待：如果一个线程进入了临界区，另一个线程发现临界区不是处于空闲状态，但是也进入了，就可能导致最终的结果不对，如相加到100，最后大于100。
有限等待：等在进入临界区的线程或者进程不能无限期等待
让权等待（可选）：不能进入临界区的进程，应该释放CPU，如切换到阻塞状态
1.4.临界区的实现方法
1）更高阶的抽象方法（单处理器多处理器都可以）：
-
1.1锁
-
优点
支持单处理器多处理器，可以实现任意进程之间同步
简单
支持多个临界区
-
缺点：
忙则等待，浪费cpu资源，一个进程上锁之后其他进程只能处于等待状态
可能导致饥饿，一个进程退出临界区，有多个进程同时等待进入，有一个进程却一直进不去。
死锁：低优先级的进程占用临界区，高优先级的进程获得cup资源，想进入临界区却无法进入
-
-
1.2.信号量
是一个特殊的变量，本质是一个计数器，用来记录临界区资源的数量，它的作用是，协调进程对共享资源的访问，同一时间，临界区中只能有一个进程访问共享资源。
2）禁用中断：几乎不用，进入临界区，禁用所有中断，整个系统都会停下来，
适用单个处理器，如果多个处理器，也会修改进程中的变量
3）软件方法：复杂，两个线程之间需要共享全局变量
3.处理机与CPU
处理机=处理器(cpu)+主存储器+输入输出设备接口
处理机+外围设备=完整的计算机系统
4.数据块与扇区
1.1 数据块与扇区对应关系
操作系统每次从磁盘上读文件，都是以块为单位读数据。块的大小一般是1KB，2KB，4KB
1block = 8个连续扇区（sector） = 8 x 512 字节 = 4096B = 4KB
2.1为什么小文件更占内存？
因为每一个文件都会占用一个块，如果块大小是4KB，文件大小是4B，文件个数是10万，文件总的大小是400KB，但实际占了400MB大小；解决办法调整块的大小为1KB
3.1block与inode
操作系统进行磁盘分区时，会分成2个区域，一个是块区，一个是节点区。
超级块区（superblock）:用来存放block和inode总量
block：存放文件数据
inode: 存放文件属性，block ID
每一个文件名字都有一个inode
4.1硬连接软连接
硬连接：两个文件名字指向同一个inode, 使用同一个block，inode数量增加为2，一个文件删除，对另一个没有影响
软连接：软连接文件存放源文件名字，与源文件是两个不同的inode, 源文件删除，软连接文件No such file or directory
5.常见的接口设备
1.1
字符设备：键盘，鼠标
块设备：磁盘驱动器
网络设备：以太网，无线网，蓝牙
I/O命令：send/receive网络报文
6.磁盘
1.1磁盘缓存
指磁盘扇区中的数据，加载到在内存中的缓存区
1.2磁盘结构
磁盘包括：磁头，磁道，扇区，柱面等
[图片上传失败...(image-2aedfa-1629025612426)]
7.文件系统
1.1什么是文件描述符
打开文件的标识
1.2虚拟文件系统
介于文件系统和用户空间之间，为用户空间提供统一的API，使得操作系统可以支持不同的文件系统
1.3文件的存储方式
顺序存储
链式存储：文件数据块通过链表连接
树形结构，索引分配：(Unix File System)
1.4如何存储大文件？
通过UFS多级索引分配的方式实现，一个Inode 中，不但存放数据块的ID（数据块指针），还存放数据块索引，索引可以分为1，2，3级。
[图片上传失败...(image-40a853-1629025612426)]
8.死锁
1.0什么是死锁？
是指相互等待资源的现象
1.1出现死锁必要条件
互斥：任何时刻只能有一个进程使用临界区资源
持有并等待：一个进程中至少有一个资源，并且在等待其他进程，占用的资源。
非抢占：进程在使用资源后，不主动释放
循环等待：存在等待环路，例如，进程P0等P1，P1等P2，P2等P0
只有上面4个条件同时满足才会出现死锁
1.2死锁处理方法
死锁预防
-
死锁的必要条件不会同时满足
把互斥的共享资源封装成可同时访问
对资源排序，要求进程按顺序请求资源
进程请求资源时，要求它不持有任何其他资源
如进程请求不能立即分配的资源，则释放已占有资源
死锁避免
- 在分配资源时确定不会出现死锁，判断进程需要的最大资源数小于当前系统可用的数，动态检测避免出现环形等待
死锁恢复和检测
- 先让进程运行起来，当检测到死锁时再恢复，一次只终止一个进程直到死锁消除
9.进程通信
1.1进程间通信方式
-
管道（pipe）
是基于内存文件的通信机制，子进程继承父进程的文件描述符，缺省继承的父类文件描述符有0 stdin, 1 stdout, 2 stderr，传输数据有限。
[图片上传失败...(image-d9fb31-1629025612426)]
-
信号(Signal)
信号是软件中断的通知和处理机制，可以直接用于内核进程和用户进程的通信。缺点是每一次发送的信号量有限，一般用于控制传输。
正在运行的程序开启了一个进程，当按住ctrl+z时，进程收到一个停止信号，程序就停止运行了
（信号量主要用于同一进程间，不同线程之间的通信）
-
间接通信
内部消息队列：操作系统维护一个消息队列，进程A通过系统调用send向消息队列中发送数据，进程B通过receive从消息队列中取出消息，进程A，B实现相互通信；一个消息队列可以关联过个进程，每对进程可以共享多个消息队列，优点是不需要实现进程间同步，由系统调用来实现，缺点是需要用户空间和内核空间的相互拷贝，传输数据不易过大。
外部消息队列：
-
直接通信
- 通信进程之间创建共享链路，一对进程和链路之间是一对一的关系
-
共享内存
同一块物理内存映射到多个进程的内存地址空间，一个进程更新数据，另一个进程立即可见，不需要用户空间和内核空间相互拷贝的系统调度，速度最快。
但是进程之间数据的同步，需要自己实现（通过信号量来实现）
（每一个进程都有一个独立的内存地址空间，一个进程内的多个线程会共享内存地址空间）
-
socket
可以实现不同主机之间进程的通信
10.轮询与中断
1.1 轮询与中断比较
轮询是cpu依次检查IO，看是否有准备就绪的IO，遍历的时间复杂度比价高，中断则是当某个IO设备准备好了，主动通知cpu,比如通过callback函数，不需要依次遍历，但是执行中断之前需要对之前进程的数据进行保存，需要额外的内存，对硬件要求比较高，也需要中断服务的支持。
2.1什么是软件中断和硬件中断？
中断是指程序正在运行时，收到了某个中断请求，系统会将正在运行的进程状态保存，优先处理中断请求执行中断服务程序，处理完成后，再回到刚才未处理的进程，或转入其他进程。
接入外部设备
11.内存
[图片上传失败...(image-72d64a-1629025612426)]
1.1逻辑地址和物理地址定义
程序内部的地址，一个进程运行起来就会生成逻辑地址，内存或者外存上的地址是物理地址
逻辑地址通过映射可以对应到物理地址
1.1.1逻辑地址是如何转换成物理地址的？
一个进程运行起来就会生成逻辑地址，然后存储管理单元将逻辑地址转换成物理地址，通过总线对应到内存
1.2操作系统中采用的内存管理方式
分段
分页
虚拟存储
垃圾回收
重定位
1.3什么是动态内存？
程序被加载执行时，分配连续内存的过程称为动态内存分配
1.4内存碎片如何产生的？
程序一次被加载执行，有的进程执行完了，两个进程之间空出一段区域，称为碎片，也叫外部碎片，在进程内部没有充分利用的区域称为内部碎片。
1.5内存碎片如何整理？
将已经分配了内存的进程移动到一起，空出来的部分连在一起形成一个大块的连续内存。
分区对换：将等待队列中的进程，移动到外存，腾出内存空间
2.1非连续内存
一个程序可以使用，非连续的物理地址空间
2.2非连续内存中块的大小如何定义的？
通过段式和页式存储管理定义
2.3什么是分段？
将进程中具有相同功能的部分放到一个段中，如果数据放一个段，代码放一个段，每一个段之间可以是不连续的。在虚拟地址空间中，一个段号和段内偏移确定一个段。
2.4段表
段表实现虚拟地址和物理地址的映射，段表中存放段号和段长度。
2.5什么是分页？
页是一个一维结构只需要一个虚拟地址或者物理地址就能表示
页桢（桢）：将物理地址划分成大小相同基本分配单位
页面（页）：将逻辑地址划分成大小相同的基本分配单位
2.6页表
页表中有页表项，存放页号和桢号，表示页与桢的对应关系，实现逻辑地址和物理地址的映射
12.中断、异常、系统调用
1.1 三者比较
内核与外部通信的方式，中断，异常，系统调用，当有外部设备接入时会触发外部中断，当应用程序遇到缺页异常或者除0异常时，会触发异常服务例程，当用户使用系统提供的系统调用函数时会触发系统调用；中断是异步的，异常是同步的，系统调用是异步或者同步的；
[图片上传失败...(image-efd432-1629025612426)]
1.2系统调用与函数调用的比较
INT和IRET指令用于系统调用，为了保证内核安全有堆栈切换、特权指令转换
CALL和RET用于函数调用，没有堆栈切换
13.虚拟存储
1.1什么是虚拟存储？
当虚拟内存大于物理内存时，执行部分交换，将部分虚拟地址空间进行调入和调出，将不常用的数据从内存转到外存，。
1.2虚拟存储如何实现的？
通过虚拟页式存储和虚拟段式存储实现
1.3覆盖技术
将程序划分成功能独立的代码块，不会同时执行的代码块共享同一块内存
1.4交换技术
发生在进程之间，当一个进程处在等待队列中时，可以先将进程转到外存，
空出内存空间，以便优先级高的进程先使用
1.5局部性原理
在短时间内，程序执行的一些指令，以及这些指令操作的数据，局限在一定的区域范围内，局部性原理从理论上说明了虚拟存储技术时可以实现的。
14.进程与线程
1.1孤儿进程，僵尸进程，守护进程
孤儿进程：父进程退出，它的子进程还没有退出，子进程就变成了孤儿进程，孤儿进程由init进程统一管理。
僵尸进程：子进程退出，父进程没有调用wait,子进程的文件描述符还被占用着，子进程就成为了僵尸进程。
守护进程：在后台运行的进程
1.2孤儿进程，僵尸进程,带来的问题，处理办法？
孤儿进程，会由init进程统一管理，进行资源回收，所以不会带来什么问题；
僵尸进程，如果有大量僵尸进程存在，则会占用进程号，使得新创建的进程没办法完成，解决办法，找到创建将僵尸进程的父进程，kill掉，僵尸进程就会成为孤儿进程，被init进程回收收掉
1.3进程与线程的关系以及区别？
关系：一个进程里面至少有一个线程，一个进程也可以开多个线程，多个线程共享进程的代码，数据，文件描述符等资源
区别：进程是系统进行资源分配和调度的最小单元，线程是程序执行流的最小单元；进程有进程控制块，里面存放代码数据文件描述符等信息，线程有线程控制块，里面存放寄存器，堆栈，当前指令指针等信息。
1.4从资源分配和系统调度角度说明进程和线程
一段程序被加载到内存进形成了一个进程，进程的创建是通过系统调用函数fork,execv 完成的，当执行完execv系统调用时，当前进程有了独立的进程控制块，一个进程中至少有一个线程，线程也是通过相应的系统调用实现的，当进程执行完时，会执行exit（）系统调用，并释放内存，文件描述符等资源，保留进程ID，进入僵尸进程，然后给父进程发送一个信号，父进程调用信号处理函数，在信号处理函数中调用wait()系统调用，完成对子进程的资源回收。
1.5什么是缓冲区溢出？
程序运行起来时会占用一部分内存，这部分内存可以存放数据，当接受到的数据量大时，会超过给程序分配的内存，会覆盖内存中其他部分的数据。解决办法：校验接受数据的长度
1.6.线程之间是如何进行同步的？
event事件通知
锁：线程之间通过串行的方式访问
信号量：可以同时准许多个线程访问共享资源，但是信号量限制了同时访问的线程数
1.进程、线程都各有什么特点？
2.进程之间如何进行交互？
3.线程之间如何进行交互？
全局变量加锁
信号
