operating_system

Posted on | In | total read times
Words count in article: 7.8k | Reading time ≈ 30

Operating System course notes.

  • Note: how operating system works

    操作系统结构与功能
    操作系统结构与功能

1. Architecture

  • Def: operating system

  • Def: system call = 内核真正的函数, 一般用户态只能调用 system call API ()。每一个system call有一个对应的数字，API维护一个列表索引，指向对应的system call。

  • Usage：system call有什么作用，所有的操作系统底层都是由system call实现的。比如进程控制，文件管理，磁盘调度等等。

    • Note: 传递参数的方法：1）寄存器，2）放栈里

2. CPU process

  • Def: cpu = 运算器、控制器、通用寄存器、控制和状态寄存器（PC、IR、PSW）、高速缓存https://blog.csdn.net/qq_34801169/article/details/102782643?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

  • Def: 程序的一次执行，正在运行程序的抽象。进程是系统资源分配单位，每个具有独立地址空间，操作系统将CPU调度给进程。

    process = 堆+数据段+PCB。

    thread = 栈+上下文（寄存器）；

    • Note: process \(\neq\) program, program = text, and only when text is loaded it becomes process.

2.1. process control block

  • Def: PCB（放在数据块中）有什么东西：进程描述（PID、用户标识、进程组关系）、进程状态（状态、优先级、入口地址、队列指针）、资源和使用状况（存储空间、打开文件表）、CPU现场（计数器、寄存器、指向页表的指针、cpu时间）

2.1.1. process conditions

  • Def: conditions of process

    • Note: illustration

2.1.2. process create

  • Def : creation of process

    • Qua: from father to son

  • Qua: possible outcomes

    时间上：1）一起执行 2）父等子

    空间上：1）创建新空间 2）直接指针指向父亲共用（写时复制）

    • Example: unix ，

      fork(返回的是子pid) -> wait(不是自动等待，需要手动调用) -> exit

    • Def: 写时复制创建进程。

      Linux采用了写时复制的方法，以减少fork时对父进程空间进程整体复制带来的开销。

      写时复制是一种采取了惰性优化方法来避免复制时的系统开销。它的前提很简单：如果有多个进程要读取它们自己的那部门资源的副本，那么复制是不必要的。每个进程只要保存一个指向这个资源的指针就可以了。只要没有进程要去修改自己的“副本”，就存在着这样的幻觉：每个进程好像独占那个资源。从而就避免了复制带来的负担。如果一个进程要修改自己的那份资源“副本”，那么就会复制那份资源，并把复制的那份提供给进程。不过其中的复制对进程来说是透明的。这个进程就可以修改复制后的资源了，同时其他的进程仍然共享那份没有修改过的资源。所以这就是名称的由来：在写入时进行复制。

      在使用虚拟内存的情况下，写时复制（Copy-On-Write）是以页为基础进行的。所以，只要进程不修改它全部的地址空间，那么就不必复制整个地址空间。在fork( )调用结束后，父进程和子进程都相信它们有一个自己的地址空间，但实际上它们共享父进程的原始页，接下来这些页又可以被其他的父进程或子进程共享。

      • Def:

        1. fork( )的子进程可以COW也可以硬拷贝但是总归是不同的数据空间；vfork( )的是共享意思就是同一份。

        2. fork( )的父子进程的执行次序不确定；vfork( )保证子进程先运行，在调用exec或exit之前与父进程数据是共享的，在它调用exec或exit之后父进程才可能被调度运行。如果在调用这两个函数之前子进程依赖于父进程的进一步动作，则会导致死锁。

        3. exec()进程调用exec（）后，将在同一块进程内存里用一个新程序来代替调用    exec（）的那个进程，新程序代替当前进程映像，当前进程的“数据段”， “堆栈段”和“代码段”背新程序改写。

2.1.3. process terminate

  • Def: terminate

    • Qua 为什么终止

    • Example:

2.2. process communication

  • Def: communicate

2.2.1. message passing

  • Def: direct message pass：直接通信，每对进程只有一条边

  • Def: undirect message pass ：通过中间邮箱来传递。

  • Def: 同步 & 异步：阻塞 = 发出send/receive后等待被接受/等待有消息可用，一定会发到/收到。非阻塞 = 发完不care，有可能会发不到/收不到。

    • Note：如果都是阻塞发送/接受，那么消费者生产者模型就不重要了。

2.2.2. sharing memory

  • Def：有限缓冲= 有限空间生产者和消费者如果当内存边界时候都会等待。

  • Def： 有什么问题呢，因为即便是++这种操作也不是原子的，需要有寄存器存储中间变楼昂。所以一定不能同时访问数据（内存/寄存器）

  • Def：临界区解答必须满足三个条件。

2.2.2.1. person algorithm

  • Def: person algorithm

2.2.2.2. lock (hardware)

  • Def: using test&set

2.2.2.3. semaphore

  • Def: semaphore

2.2.2.4. problems

  • Def: consumer & producer

    mutex是必须的为了维护互斥区，empty和full控制两个边界。

  • Def：读写

2.2.3. deadlock

  • Def: 模型

2.2.3.1. safe condition

  • Def: deadlock 死锁条件。

  • Example:

2.2.3.2. deadlock prevention

  • Def: 预防是限制资源申请来预防死锁,不允许进入死锁状态。

2.2.3.3. deadlock avoidance

  • Def: 也是限制，只不过允许进入死锁状态，所以根据实时而定而不是直接一刀切做很大的限制。

2.2.3.3.1. graph algorithm

  • Def: safe condition

    • Note: figure

  • Def: draw a graph ：申请时候，进程指向资源块；申请成功后，资源指向进程；用完后，删除边。没有环就没有死锁。

    如果是一个资源只有一个，那么有环=死锁，无环=无死锁

    如果是一个资源有很多，那么有环={死锁+不死锁}，无环=无死锁

    更进一步，我们采用虚线表示未来可能发生的事，也就是提前一步预知。

    • Note ;

2.2.3.3.2. banker algorithm

  • Def: banker algorithm

    安全性算法说白了就是ava不断加上某一个进程的alloc，然后查看存在ava能否满足下一个进程的need，然后再加上这样循环。

    1）首先判断req是否大于need，这个是定义上的限制。

    2）再判断req是否大于ava，这个是语义上的限制，多了也给不了。

    3）然后对应操作减掉即可，need剪掉表示需求减少，alloc加上表示分配了，ava剪掉表示剩余减少。

    这个请求比较简单，就是看是否能满足，满足就给你了。安全性算法要求一个状态有可以安全分配完。所以每请求一个就要先用资源请求算法，然后用安全性算法来一下。

    • Example:

2.2.3.4. deadlock check

  • Def：graph algorithm

    用资源图即可，当然这也是只有一个实例的情况才行。

  • Def: banker algorithm，这里request是一个矩阵，也就是之前的算法是有顺序的，这里request是没有顺序的。这里和安全性算法只不过把need换成了request，意思就是假设request后它不会再需要更多的资源了，所以request约等于need。

    • Note: that this only check right/wrong & does not provide a solution

2.2.3.5. deadlock cancel

  • Def: deadlock preemptive

  • Def: deadlock termination

2.3. process scheduling

  • Def: how CPU deal with processes，在就绪队列和CPU中间的都是等待状态。

2.3.1. schedule queue

  • Def: schedule queue，每类进程状态有一个或多个队列，元素为PCB，进程状态改变就是换队.

  • Def: scheduling queue

2.3.2. scheduler

  • Def: long-term scheduler

    • Qua: difference frequency

  • Qua: short-term connects CPU & queue, long-term connects with memory & hard drive

2.3.3. CPU context switch

  • Def: 进程上下文：CPU的所有寄存器中的值、堆栈中的内容、内存页、进程的状态。

  • Def: 用户栈就是通常所说的虚拟内存；内核栈跟用户栈独立，属于进程，即每个进程都有自己的内核栈，单独分配，大小为8k，跟thread_info结构放在一起，在用户态和内核态切换时，需要进行切换。

    • Note: 怎么跳转：简单来说，通过task_struct的TSS结构进行栈寄存器切换。

      用户态堆栈指针：ss和esp；

      内核态堆栈指针：ss0和esp0；

      二者均位于任务的tss结构中。这里的任务是指除任务0和1之外的普通任务。

      CPU进行用户态堆栈到内核态堆栈的切换操作时，CPU会从当前任务的任务状态段TSS中取得新堆栈的段选择符和偏移值，即从TSS的ss0和esp0字段中获取，在定位了新堆栈（内核态堆栈）之后，CPU就会首先把原用户态堆栈指针ss和esp压入内核态堆栈，随后把标志寄存器eflags内容和返回位置cs、eip压入内核态堆栈。

  • Def : 中断和异常

    • 中断响应外部事件，异步处理，总是返回下一条指令，如I/O、时钟、硬件故障；

    • 异常源于内部正在执行的程序，同步处理，分为陷入、故障、终止，如系统调用、页故障、断点、权限保护。

    • 特权模式切换：系统调用/中断处理执行过程，系统调用过程中一直是同一个进程在运行，简单来说就是切换了内核/用户栈保存了寄存器，不牵扯到PCB：

      • CPU执行到特殊的陷入指令（比如软件中断调用了0x80 , 设置eax的值）

      • 通过0x80找到中断向量表(IDT)中的(第128项)门描述符，通过门描述符指向的系统调用程序(system_call)，硬件保护(把TSS中的ss、esp设置为内核ss、esp这是切换内核用户栈（所谓内核态），并把原来的ss、esp、eflags、cs、eip 压到内核栈），软件保护(SAVEALL)把(es、ds、eax、ebp、edi、esi、edx、ecx、ebx表示参数)压入内核栈，转入查到的系统调用总入口程序；

      • 执行查到的系统调用例程（所谓内核态）；

      • 恢复到用户态（从内核栈中恢复ss、esp），并得到调用结果（eax）；

    • 进程上下文切换：两个用户进程之间切换（如果是内核<->用户只需要切换寄存器和栈）

      • 系统调用函数执行中，已经处在内核态，处在内核堆栈中。

      • switch_mm()：更换通过task_struct->mm描述的内存管理上下文, 主要包括加载页表, 刷出地址转换后备缓冲器(部分或者全部)。

      • switch_to()：保存旧进程：内核寄存器eflags、ebp保存到内核栈；内核栈esp地址、ip地址保存到PCB的thread_info；恢复新进程：然后用新进程的thread_info->esp恢复新进程的内核堆栈，用thread->info的ip(pc)恢复新进程地址执行。

    • 线程上下文切换：这里指的相同进程中的两个线程。

      • 只需要切换线程的计数器、寄存器等不共享的数据。

  • Def: CPU context switch 1) save in PCB 2) retrieve from PCB：具体在保存寄存器状态，切换sp

    • Note: 上下文切换

  • Qua: the speed is related to hardware

2.3.4. scheduling algorithm

  • Def: CPU burst

    • Note:

  • Def: preemptive & non scheduling。

    抢占 = 存在直接中断再调度、存在把等待状态切换到就绪状态

    非抢占 = 进程要么终止要么被I/O切回等待。

  • Def: CPU principals

    CPU使用率 = 使用时间/总时间

    吞吐量 = 完成进程数/总时间

    周转时间 = 一个进程完成时间 - 一个进程提交时间

    等待时间 = 一个进程进入CPU时间 - 一个进程进入就绪队列时间

    响应时间针对交互系统。

    • Qua:

      • goals ：使用率最大化；

      • concerns: 优先级与优先数？是否抢占？I/O密集或CPU密集友好？时间片长度？

  • :Def 怎么选择？

    FCFS,SJF批处理处理看重吞吐量、周转时间、CPU利用率。

    RR，优先级更看重响应时间、平衡。

    Linux抢占式调度，Windows基于优先级的抢占式多任务调度

2.3.4.1. FCFS

  • Def: FCFS，先到先进。

    • Qua : non pre

2.3.4.2. SJF

  • Def: SJF，最短的先进

    • Qua: the best

    • Note: in practice, we need online version of SJF.

    • Note: SJF也可以抢占，当一个新进程进来的时候，会比较正在运行的进程的剩余时间，如果剩余时间大于新进程就抢占。

2.3.4.3. priority

  • Def:

    • Qua: problems，饿死用老化解决。

2.3.4.4. RR

  • Def： 分成小段，一人一段。

2.4. process & thread

  • Def: thread，线程最大的区别是有自己的stack/heap + 寄存器。最重要是线程可以共享代码+数据，节省空间。ID、状态、上下文、栈指针；

    • Note: difference with process

    • 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.都是CPU时间片的描述，只不过粒度一个大一个小。从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

    • 好处：

      • 线程的划分尺度小于进程，使得多线程程序的并发性高。

      • 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了  程序的运行效率。

      • 进程切换耗费很多资源

    • 坏处：

      • 不够健壮，不够安全，如果是多对1模型，一个线程死掉就全死，

2.4.1. thread models

  • Def: n to 1 https://blog.csdn.net/qq_40608137/article/details/104647648?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task 简而言之，lwp将用户线程映射到内核线程，用户线程是用来调度方便；内核线程才是真正的跑的东西。所谓模型就是一个用户线程是怎么映射的。如果是多对1/1对1模型的话，内核线程挂起，那么这一个进程的所有线程都跑不了了（因为它们只被映射到这一个内核线程上）

    • 用户级线程仅存在于用户空间中，此类线程的创建、撤销、线程之间的同步与通信功能，都无须利用系统调用来实现，不需要用户态/核心态切换。

    • 内核线程建立和销毁都是由操作系统负责、通过系统调用完成的。在内核的支持下运行，无论是用户进程的线程，或者是系统进程的线程，他们的创建、撤销、切换都是依靠内核实现的。

  • Def: 1 to 1

  • Def: n to n

  • Def: LWP

    • Note:

2.4.2. thread cancel

  • Def: thread cancel

2.4.3. thread pool

  • Def: 先开一些线程，然后来回使用。

  • Usage： 限制线程数、快速

3. memory

3.1. memory address

3.1.1. address alignment

  • Def: 结构体对齐

    https://blog.csdn.net/TAlice/article/details/82016508?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

  • Def: union 对齐

    所有东西都放在max（）里面。

3.1.2. address protection

  • Def: every process has its own memory range

    • Note: figure

  • Def: protect access from CPU

    • Note：

    • Note: kernel mode

3.1.3. address logical & physical

  • Def: address logical

  • Def: MMU

    • Note:

3.1.4. address binding

  • Def: address binding

    • Note: 编译时-装进内存前；加载时-装进内存后就不变；执行时-装进内存后也可能会变，装进去还没执行时候也会变。

3.1.5. dynamic loading

  • Def:

    • Qua:

3.1.6. dynamic linking

  • Def: similar idea

    • Qua:

    • Qua:

3.2. address allocation

3.2.1. continuous

  • Def: variable-partition ：一个进程是一大块连续的。

  • Def: fragmentation ，内部碎片指的是分配时候多分了一点，所以叫内部。

    • Note: how to deal with ，外部碎片可以用紧缩来调整。

3.2.2. incontinuous

3.2.2.1. page table

  • Def: paging with page table ；分页本身也是运行时重定位

    • Example:

      logic_address = page_address=logic_address/page_bytes 连接 logic_address%page_bytes. （都是二进制）

      true_address = pagetable[page_address] * page_bytes + logic_address%page_bytes;

      logic_length = log(page_num) + log(page_bytes)

      true_length = whatever you want >= logic_length

      true_memory <= 2^true_length B

      page_memory = page_num * 2^page_length B

    • Qua: no external fragment

    • Note： 页表是每个process一份，放pcb里。放内存里需要两次访问，很慢。

           

3.2.2.2. page table + TLB

  • Def: paging with page table + TLB

    页表只包含偏移，而TLB用页号（不用的话无法说明正确性）作为key。TLB可以理解为页表的缓存，用得多的页表就用TLB存起来。TLB也有一项ASID确定你这个页表里装的是正确的东西，上下文切换的时候TLB和页表必须刷新。TLB放在快速内存中。

    • Note: additional information

      • Example:

        TLB_length = log(page_num) + log(true_page_num)

3.2.2.3. multiple page table

  • Def: 层次页表的意义就是加一个外部页表，把之前的page_address变成pt1_address + pt1_offset。通过pt1来找pt的页号，然后提取pt的内容也就是真.页号，对比之前是用page_address直接就是pt的页号。为了减少页表大小，

3.2.2.4. hash page table

  • Def:

3.2.2.5. segmentation table

  • Def:

3.3. virtual memory

3.3.1. demand paging

  • Def: virtual memory

    为了防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏，采用了虚拟内存。虚拟内存空间映射到实际物理内存。

    建立时，初始化PCB中内存相关的链表，建立虚拟内存到磁盘的映射，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，分配好页表，运行时才会通过缺页异常，来拷贝数据。

    • Def: 好处

      1.扩大地址空间；

      2.内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。虚存还对特定的内存地址提供写保护，可以防止代码或数据被恶意篡改。

      4.当进程通信时，可采用虚存共享的方式实现。

      5.当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存

      7.在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片

  • Def: demand paging

  • Def: page fault （如果引用页表非法，调用磁盘操作然后分配进）

3.3.2. page swap algorithm

3.3.2.0.1. FIFO

  • Def: Belady现象FIFO算法，驻留集增大，缺页率可能反而增加

3.3.2.0.2. BEST

  • Def:

    • Qua:

3.3.2.0.3. LRU

  • Def: 开销大

3.3.2.0.4. LFU

  • Def:

3.3.2.0.5. MFU

  • Def:

3.4. thrashing

  • Def:

  • Note:

3.4.1. working set model

  • Def:

3.4.2. PFF

  • Def:

3.5. kernel address allocation

  • Note: 必须连续，内核代码不受分页系统控制。

3.5.1. buddy system

  • Def: 不断的分。/2

    • Example:

    • Qua:

3.5.2. slab

  • Def: slab

    • Note:

4. file system

  • Def:

  • Def: in disk 1）引导块（用于引导操作系统）2）super控制块 （用于记录各种信息）3）目录，存储FCB。注意一个节点有一个目录，指向儿子们，下一个目录保存在一个目录项的FCB的inode节点里。

    • 解决长文件名：使用不固定长度的目录项，添加长度和结束标志；名字统一在堆存放，目录项中包含指向堆内的指针；FAT32的每个长目录项可保存13字符，长目录项前必须有一个普通的短目录项

  • Def: in memory 目录缓存结构（指向磁盘中目录的位置）

    • Def: open file table：单个进程的打开文件表指向系统表；系统表包括FCB。这个在进程视角来看的，已经打开的文件的表，用于方便下一次打开，跟文件的实际存储没有关系。

    • Def: open file ，记录了上次访问的信息和文件的实际位置等。

    • Def: FCB = 目录项(文件名、文件号)+i节点(除文件名外所有字段，描述文件相关信息)

  • Note: file system，先搜索文件表看有没有，如果没有再去目录。这是因为要从目录搜索需要耗费磁盘。

  • :Def 打开文件过程：

    文件操作：读取目录（找目录项，更新共享计数，获取文件描述符）；创建（建FCB，分配存储空间）；指针定位（用户打开文件表加FCB指针）

    文件读取：从打开文件表中找。

    访问控制表（每个文件能被哪些用户操作），能力表（每个用户能操作哪些文件）

4.1. file

4.1.1. attributes

4.1.2. access

4.1.2.1. sequential

  • Def:

4.1.2.2. direct

  • Def:

  • Def: menu

    • Note:

    • Note: operations

4.2.1.1. single level

  • Def:

4.2.1.2. double level

  • Def:

    • Qua : disadvantage

4.2.1.3. tree

  • Def:

4.2.2.1. list

  • Def:

4.2.2.2. hash table

  • Def:

4.3. partition

  • Def: root partition

  • Def: mount ing

    • Note:

4.4. file allocation

4.4.1. continuous allocation

  • Def:

    • Note:

    • Qua:

    • Qua:

    • Qua:

  • Def:

    • Note:

  • Qua: adding

  • Qua: dis

  • Qua: FAT

    • Note:

4.4.3. index allocation(page table)

  • Def:

    • Note:

    • Qua:

4.4.4. free space management

4.4.4.1. bit map

  • Def:

4.4.4.2. linked list

  • Def:

    • Note:

4.4.4.3. group

  • Def:

5. disk

  • Def:

    • Note:

5.1. scheduling algorithm

5.1.1. FCFS

  • Def;

    • Note:

5.1.2. SSTF

  • Def:

    • Note:

    • Qua:

5.1.3. SCAN

  • Def;

    • Note:

5.1.4. C-SCAN

  • Def:

    • Note:

5.1.5. LOOK

  • Def:

    • Note:

5.1.6. comparison

  • Note:

5.2. bootcamp

  • ：Def ： 在系统盘里，有一个启动块（MBR），其中有一个ROM存储器，先把其中的启动程序启动、把整个MBR读入到内存、确定引导分区（操作系统）、读取引导分区。

5.3. RAID

  • Def:https://www.cnblogs.com/chuncn/p/6008173.html

  • Note:

  • Note:

6. I/O

6.1. 同步

  • 同步，就是我调用一个功能，该功能没有结束前，我死等结果。
  • 异步，就是我调用一个功能，不需要知道该功能结果，该功能有结果后通知我（回调通知）
  • 同步IO和异步IO的区别就在于：数据拷贝的时候进程是否阻塞

6.2. 阻塞

  • 阻塞，就是调用我（函数），我（函数）没有接收完数据或者没有得到结果之前，我不会返回。
  • 非阻塞，就是调用我（函数），我（函数）立即返回，通过select通知调用者
  • 阻塞IO和非阻塞IO的区别就在于：应用程序的调用是否立即返回

1)阻塞I/O（blocking I/O） 2)非阻塞I/O （nonblocking I/O） 3) I/O复用(select 和poll) （I/O multiplexing） 4)信号驱动I/O （signal driven I/O (SIGIO)） 5)异步I/O （asynchronous I/O (the POSIX )

简而言之异步的话非阻塞才有意义，异步阻塞就丧失了异步的意义；同步的话阻塞就是挂起，非阻塞就是不断尝试。

6.3. 阻塞I/O （同步）

  • Def: 应用程序调用一个IO函数，导致应用程序阻塞，等待数据准备好。 如果数据没有准备好，一直等待….数据准备好了，从内核拷贝到用户空间,IO函数返回成功指示。

  • Notee: 简单来说，就是调用recv()然后一直等待。调用recv()函数时，系统首先查是否有准备好的数据。如果数据没有准备好，那么系统就处于等待状态。当数据准备好后，将数据从系统缓冲区复制到用户空间，然后该函数返回。在套接应用程序中，当调用recv()函数时，未必用户空间就已经存在数据，那么此时recv()函数就会处于等待状态。

6.4. 非阻塞I/O （同步）

  • Def：非阻塞IO通过进程反复调用IO函数（多次系统调用，并马上返回）；在数据拷贝的过程中，进程是阻塞的

  • Note; 什么时候才用：我们把一个SOCKET接口设置为非阻塞就是告诉内核，当所请求的I/O操作无法完成时，不要将进程睡眠，而是返回一个错误。这样我们的I/O操作函数将不断的测试数据是否已经准备好，如果没有准备好，继续测试，直到数据准备好为止。在这个不断测试的过程中，会大量的占用CPU的时间。

  • Note：简单来说就是调用不断调用recvfrom然后如果返回错误告诉没有数据准备好就继续直到成功。

    img
    img

6.5. IO复用（同步）

  • Def: 主要是select和epoll；对一个IO端口，两次调用，两次返回，比阻塞IO并没有什么优越性；关键是能实现同时对多个IO端口进行监听； I/O复用模型会用到select、poll、epoll函数，这几个函数也会使进程阻塞，但是和阻塞I/O所不同的的，这两个函数可以同时阻塞多个I/O操作。而且可以同时对多个读操作，多个写操作的I/O函数进行检测，直到有数据可读或可写时，才真正调用I/O操作函数。

    • Note: 为什么使用：因为select可以对多个端口进行监听。

    • Note: 简单来说拆成了两次，一个select阻塞同步；一个revfrom阻塞同步。select对多个端口进行监听然后返回一个，recvfrom是一样的。

      img
      img

6.6. 信号驱动IO （先异步再同步）

  • Def: 首先我们允许套接口进行信号驱动I/O,并安装一个信号处理函数，进程继续运行并不阻塞。当数据准备好时，进程会收到一个SIGIO信号，可以在信号处理函数中调用I/O操作函数处理数据。

  • Note: 简单来说，先sigaction异步通知，然后阻塞同步传递。

    img
    img

6.7. 异步

  • Def：当一个异步过程调用发出后，调用者不能立刻得到结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者的输入输出操作

  • Note：简单来说，一个sio_read非阻塞异步，荣国sio_read的信号返回。

    img
    img

6.8. 对比

  • Def：对比

    img
    img
    • 不涉及到异步
      • 阻塞同步
      • 非阻塞同步
      • 复用就是监听多口的阻塞同步。
    • 涉及到异步
      • 信号驱动就是先异步再阻塞同步拷贝数据
      • 异步就是全异步。

6.9. epoll/select

  • Def: fdset: 实际上是一long类型的数组，每一个数组元素都能与一打开的文件句柄(socket、文件、管道、设备等)建立联系，建立联系的工作由程序员完成，当调用select()时，由内核根据IO状态修改fd_set的内容，由此来通知执行了select()的进程哪个句柄可读。

  • Def: select, 简单来说就是通过fd_set切换到内核态，然后对遍历这个set调用poll，返回一个mask掩码表示有哪些就绪的fd。

    1）使用copy_from_user从用户空间拷贝fd_set到内核空间

    （2）注册回调函数__pollwait

    （3）遍历所有fd，调用其对应的poll方法（对于socket，这个poll方法是sock_poll，sock_poll根据情况会调用到tcp_poll,udp_poll或者datagram_poll）

    （4）以tcp_poll为例，其核心实现就是__pollwait，也就是上面注册的回调函数。

    （5）__pollwait的主要工作就是把current（当前进程）挂到设备的等待队列中，不同的设备有不同的等待队列，对于tcp_poll来说，其等待队列是sk->sk_sleep（注意把进程挂到等待队列中并不代表进程已经睡眠了）。在设备收到一条消息（网络设备）或填写完文件数据（磁盘设备）后，会唤醒设备等待队列上睡眠的进程，这时current便被唤醒了。

    （6）poll方法返回时会返回一个描述读写操作是否就绪的mask掩码，根据这个mask掩码给fd_set赋值。

    （7）如果遍历完所有的fd，还没有返回一个可读写的mask掩码，则会调用schedule_timeout是调用select的进程（也就是current）进入睡眠。当设备驱动发生自身资源可读写后，会唤醒其等待队列上睡眠的进程。如果超过一定的超时时间（schedule_timeout指定），还是没人唤醒，则调用select的进程会重新被唤醒获得CPU，进而重新遍历fd，判断有没有就绪的fd。

    （8）把fd_set从内核空间拷贝到用户空间。

  • Def：poll使用的pollfd结构而不是select的fd_set结构，其他都类似

  • Def：epoll是改进三大缺点epoll_create,epoll_ctl和epoll_wait，epoll_create是创建一个epoll句柄；epoll_ctl是注册要监听的事件类型；epoll_wait则是等待事件的产生。

    （1）每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大 -> 对于第一个缺点，epoll的解决方案在epoll_ctl函数中。每次注册新的事件到epoll句柄中时（在epoll_ctl中指定EPOLL_CTL_ADD），会把所有的fd拷贝进内核，而不是在epoll_wait的时候重复拷贝。epoll保证了每个fd在整个过程中只会拷贝一次。这个是注册和等待分开，在注册的时候拷贝，在等待的时候就不拷贝。

    （2）同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大 -> 对于第二个缺点，epoll的解决方案不像select或poll一样每次都把current轮流加入fd对应的设备等待队列中，而只在epoll_ctl时把current挂一遍（这一遍必不可少）并为每个fd指定一个回调函数，当设备就绪，唤醒等待队列上的等待者时，就会调用这个回调函数，而这个回调函数会把就绪的fd加入一个就绪链表）。epoll_wait的工作实际上就是在这个就绪链表中查看有没有就绪的fd（利用schedule_timeout()实现睡一会，判断一会的效果，和select实现中的第7步是类似的）。（也就是说同样的，不会重复遍历fd，所有的fd只会遍历一遍）

    （3）select支持的文件描述符数量太小了，默认是1024 -> 对于第三个缺点，epoll没有这个限制，它所支持的FD上限是最大可以打开文件的数目，这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左右，具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。

Title:operating_system

Author:Benson

PTime:2019/11/19 - 12:11

LUpdate:2020/04/03 - 21:04

Link:https://steinsgate9.github.io/2019/11/19/operating_system/

Protocal: Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Please keep the original link and author.