Lessons

Definitions:

  • Resource allocator: manages and allocates resources
  • Control program: controls the execution of user programs and operations of I/O devices
  • Kernel: the one program running at all times (all else being application programs)

Architecture:-

  • Single-processor Systems
  • MultiSingleSingle-processor Systems
  • Clustered Systems

分时 (time-sharing) 系统: 为了交互, 立即响应

Additional OS Functions:

  • Resource allocation
  • Accounting: 比如根据用户使用时间计费等
  • Protection

Benefits of Multithreaded:

  • Responsiveness (响应及时)
  • Resource Sharing (资源共享)
  • Economy (经济, 提高资源利用率)
  • Utilization of MP Architectures (多核优势)

进程管理

Process Status:

  • new
  • running
  • waiting
  • ready
  • terminated
flowchart LR A[new 新建] --> B[ready 就绪] B --> C[running 运行] C --> B C --> D[waiting 等待/阻塞] D --> B C --> E[terminated 终止]

因为请求某一资源会进入阻塞态, 已运行的程序被剥夺资源 (如剥夺的优先级调度) 会进入就绪态

Scheduling:

  • First-Come, First-Served (FCFS) Scheduling (先来先服务调度)

  • Shortest-Job-First (SJR) Scheduling (短作业优先调度)

    • Non-Preemptive 非剥夺时
    • Preemptive 剥夺时

  • Priority Scheduling (优先调度算法)

    • Non-Preemptive 非剥夺时
    • Preemptive 剥夺时

  • Round Robin (RR) (轮转调度算法)

$$WaitingTime (等待时间) = TurnaroundTime (进程结束时间) - BurstTime (进程占用时间) $$

$$AverageWatingTime = \frac{\sum_{i = 0}^{n}WatingTime_{Pi} } {n}$$

critical section:

  • Mutual Exclusion
  • Progress
  • Bounded waiting

Deadlock:

  • Mutual Exclusion
  • Hold and Wait
  • No Preemption
  • Circular Wait

银行家算法的个人理解:

  • allocation: 指已经分配的资源

  • max: 指最大能分配的资源, 但并不一定是需要分配这么多

  • need: 还需要分配的资源数量, $need = max - allocation$

  • request: 指实际请求的资源, $request \le need$ , 有 request 就按 request 算, 没有就按 max 算.

    是否是安全序列是按照 max 算的, 但实际的 request 可能并不会申请那么多, 所以 不安全状态 不代表 死锁, 如果不安全状态下有 request 申请则可能会进入死锁

  • work: 空闲的能够分配的资源, 分配的条件是 $$ \begin{cases} work \ge need \ (无 request 下) \ work \ge request \ (有 request 下) \end{cases} $$ 每次分配后都是 $work = work + allocation$

内存管理

First-fit: Allocate the first hole that is big enough.

Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. Produces the smallest leftover hole. (分配大小最接近的空闲区)

Worst-fit: Allocate the largest hole; must also search entire list. Produces the largest leftover hole. (分配最大的空闲区)

External Fragmentation: total memory space exists to satisfy a request, but it is not contiguous. (内存释放后由于空间不连续导致的碎片)

Internal Fragmentation: allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used. (分配太多导致浪费的碎片)

段分配只有外部碎片, 页分配只有内部碎片, 段页分配两种碎片都有

系列题目在B 站

opt 页面置换算法: 一分钟学会页面置换算法【OPT、FIFO、LRU、NUR】_opt 算法-CSDN 博客

Belady 现象: 采用 FIFO 等算法时可能出现分配的物理页数增加但缺页次数增加的现象。

  • 比如对于 1,2,3,4,1,2,5,1,2,3,4,5 这个序列
    • 如果 FIFO 队列长为 3，缺页次数为 9;
    • 如果 FIFO 队列长为 4，缺页次数为 10
  • 原因是
    • FIFO 算法的置换特征与局部性原理不相符;
    • 与进程访问的动态特征相矛盾;
    • 被它置换出去的页面并不一定是进程近期不会访问的。

工作集和抖动: 【操作系统】抖动与工作集_操作系统内存抖动的主要原因-CSDN 博客

TLB 就是用页面替换算法的表，访问速度最快，驻留集就是 TLB 的大小。页表在内存中，访问速度和访问内存一样。 缺页中断后对应的页框号为淘汰页面对应的页框号，发生缺页中断时页框号不变，但是页框号对应的内容从外存中调入，所以实际对应内容改变。

地址格式:

物理地址: frame + offset

逻辑地址: segement + page + offset (offset 即页大小)

文件管理

I/O 管理

Q&A

  1. Which is the method used to pass params between a running program and the os?

    • registers: 在寄存器中传递参数；
    • memory block: 将参数存储在内存中的块或表中，并将块的地址作为参数传递到寄存器中；
    • stack: 参数压入堆栈;由操作系统弹出。块和堆栈方法不限制传递的参数的数量或长度。

    (1) Pass the parameters in registers (this may prove insufficient when there are more parameters than registers). (2) Store the parameters in a block, or table, in memory, and pass the address of block as a parameter in a register. This approach is used by Linux and Solaris. (3) Push the parameters onto a stack; to be popped off by the OS. Block and stack methods do not limitt the number or length of parameters passed.

  2. If a process is waiting to be assigned to a processor, it must be in the state of ready

  3. What is the diff between process and thread?

    • 数据结构不同：进程是操作系统资源分配的基本单位，核心数据结构是 PCB；线程是操作系统中调度执行的基本单位，核心数据结构是 TCB；

      TCB（线程控制块）包含以下信息：

      1. 线程状态（Thread State）：表示线程的当前状态，例如运行、就绪、阻塞等。
      2. 程序计数器（Program Counter）：指向线程当前执行的指令地址，用于记录线程下一条将要执行的指令。
      3. 寄存器集合（Register Set）：保存线程的寄存器状态，包括通用寄存器、栈指针、帧指针等。
      4. 栈指针（Stack Pointer）：指向线程栈顶的地址，用于保存线程的局部变量和函数调用信息。
      5. 线程优先级（Thread Priority）：表示线程的优先级，用于调度器确定线程执行的顺序。
      6. 线程标识（Thread Identifier）：唯一标识线程的值，可以用于在系统中唯一地识别和引用线程。
      7. 线程所属的进程（Process）：记录线程所属的父进程，以便进行进程和线程之间的关联。

      PCB（进程控制块）包含以下信息：

      1. 进程状态（Process State）：表示进程的当前状态，例如运行、就绪、阻塞等。
      2. 程序计数器（Program Counter）：指向进程当前执行的指令地址，用于记录进程下一条将要执行的指令。
      3. 寄存器集合（Register Set）：保存进程的寄存器状态，包括通用寄存器、栈指针、帧指针等。
      4. 进程标识（Process Identifier）：唯一标识进程的值，可以用于在系统中唯一地识别和引用进程。
      5. 地址空间信息（Address Space Information）：描述进程的地址空间布局和内存分配情况，包括代码段、数据段、堆和栈等。
      6. 进程控制信息（Process Control Information）：包括进程优先级、调度信息、资源占用情况、打开文件列表等。
      7. 父子进程关系（Parent-Child Relationship）：记录进程的父进程和子进程，以维护进程之间的层次结构。

    • 资源分配和共享不同：进程之间资源独立，同一进程的不同线程之间资源共享（不同进程之间的线程也是资源独立）；

      note: 线程之间的 全局变量、静态变量、动态分配的内存 、 文件描述符 等可以共享，栈、寄存器、线程局部变量、栈帧等不能共享

    • 执行顺序不同：进程之间上下文切换慢，进程的创建、销毁和调度开销较大；线程作为执行流，上下文切换速度快，开销较小。

    Powered By 文心一言

    (1) 核心数据结构不同：进程是操作系统资源分配的基本单位，进程在操作系统中的核心数据结构是进程控制块（PCB），用来记录进程的相关信息。而线程是操作系统中调度执行的基本单位，线程在进程内的核心数据结构是线程控制块（TCB），用来记录线程的相关信息。 (2) 资源分配和共享不同：进程之间的资源是独立的，每个进程都有独立的虚拟地址空间和文件描述符表，一个进程崩溃一般不会影响其他进程。而线程之间的资源则是共享的，同一进程的多个线程之间共用虚拟地址空间和文件描述符表，一个线程崩溃很可能使得整个进程崩溃。 (3) 执行顺序不同：进程作为程序的一次运行，其上下文切换速度较慢，进程的创建、销毁和调度开销较大。而线程作为执行流，其上下文切换速度较快，线程的创建、销毁和调度开销相对较少

  4. 作业调度和进程调度

    作业调度: 将到达的作业调入内存中等待进程调度, 有几道就能调入几个作业

    进程调度: 将内存的作业按照调度算法 (比如: FCFS, RR 等) 进行调度

    参照 PPT 例题

  5. 课上讲到过进程之间可以用共享内存通信，可是每个进程的内存空间都是独立的，怎么会有共享内存呢？

    我们都知道，系统加载一个进程的时候，分配给进程的内存并不是实际物理内存，而是虚拟内存空间。那么我们可以让两个进程各自拿出一块虚拟地址空间来，然后映射到相同的物理内存中，这样，两个进程虽然有着独立的虚拟内存空间，但有一部分却是映射到相同的物理内存，这就完成了内存共享机制了。

  6. 信号量的申请和释放 (PV 操作)

    PV: 操作系统——PV 操作_在操作系统中,pv 操作用于管理资源的访问和同步。 理发师问题: 【操作系统-进程】PV 操作——理发师问题 - 漫舞八月（Mount256）

    个人总结:

    • P 代表申请一个资源, 资源数要 -1, 操作之后如果资源数 >=0, 代表之前有资源被申请到, 所以就可以往下进行, 否则就要将进程放入等待队列进行阻塞
    • V 代表释放一个资源, 资源数要 +1, 操作之后如果资源数 >0, 代表之前一直都有空闲资源则不会造成影响; 否则表示之前是缺少资源的状态, 就要从等待队列里面唤醒一个资源执行

  7. 对于三种分配策略 (顺序, 链接, 索引), 逻辑和物理地址是怎么映射的 ?

    powered by gpt

    • 顺序分配（Contiguous Allocation）：在顺序分配中，文件的逻辑块按照连续的方式映射到物理块。每个文件都有一个起始物理块地址和长度，通过逻辑块号与起始物理块地址的偏移计算出物理块地址。
    • 链接分配（Linked Allocation）：在链接分配中，每个文件的逻辑块都包含一个指向下一个物理块的指针。逻辑块号直接对应链表的节点，通过遍历链表找到对应的物理块地址。
    • 索引分配（Indexed Allocation）：在索引分配中，为每个文件分配一个索引块，该索引块中包含了指向文件实际数据块的索引项。逻辑块号直接对应索引块中的索引项，通过索引项中的物理块地址找到对应的物理块。

  8. trap 是什么, 和 interrupt (中断) 的区别

    trap 是由用户程序触发的操作系统用户态与内核态的切换; 而中断是由硬件触发, 外部事件导致的. 操作系统小结（三）- Trap 机制 - 知乎 (zhihu.com)

  9. A file is made up of 128-byte fix-sized logical records and stored on the disk in the unit of the block that is of 1024 bytes. The size of the file is 10240 bytes. Physical I/O operations transfer data on the disk into an OS buffer in main memory, in terms of 1024-byte block. If a process issues read requests to read the file’s records in the sequential access manner, what is the percentage of the read requests that will result in I/O operations?

    powered by gpt 根据给定的信息，每个块的大小是 1024 字节，而每个记录的大小是 128 字节。因此，每个块可以容纳 1024/128=8 个记录。 文件的大小为 10240 字节，因此总共有 10240/128=80 个记录。 当按顺序访问文件的记录时，每个块将被读取一次。由于每个块可以容纳 8 个记录，因此需要 80/8=10 个块来读取整个文件。 因此，总的 I/O 操作次数为 10 次，而总的读请求次数为 80 次。所以导致 I/O 操作的读请求的百分比为 10/80=12.5%。

    每次从缓冲中读入一个固定的逻辑记录，共需要读入80次；每次从磁盘中读入一个块，共需要读入10次，所以结果为 $\frac{10}{80} = 12.5%$