@TOC

前言

本篇文章继续我们的刷题之路。

资料合集地微信公众号：优质程序猿

一、进程控制块

这里只讲解进程的PCB控制块，线程的TCP控制块作用和进程PCB控制块作用类似。

1.PCB控制块的作用

进程控制块（Process Control Block，PCB）是操作系统中用于管理和跟踪进程信息的数据结构。每个进程在操作系统中都有一个对应的 PCB，它存储了与进程执行和管理相关的各种信息。PCB 在进程的创建、切换和终止等操作中起着重要的作用。

PCB 通常包含以下信息：

1.进程标识符（Process ID，PID）：用于唯一标识一个进程。

2.进程状态（Process Status）：表示进程当前的执行状态，例如运行、就绪、阻塞等。

3.寄存器内容（Register Context）：保存进程的寄存器状态，包括程序计数器（PC）、堆栈指针（SP）等。当进程切换时，这些寄存器的状态会被保存到 PCB 中，以便在切换回来时进行恢复。

4.进程优先级（Process Priority）：用于调度和确定进程的执行顺序。

5.程序计数器（Program Counter，PC）：记录下一条要执行的指令的地址。

6.内存管理信息：包括进程的地址空间、页表、分配的物理内存等。

7.文件描述符表（File Descriptor Table）：记录进程打开的文件和网络连接的信息。

8.资源使用信息（Resource Usage）：统计进程使用的 CPU 时间、内存、文件描述符等资源的使用情况。

9.父子关系和进程关系（Process Relationships）：记录进程的父进程、子进程、兄弟进程等关系。

10.同步和通信信息（Synchronization and Communication）：用于进程之间的同步和通信，如信号量、互斥锁、管道等。

PCB 是操作系统在进程创建时分配的数据结构，用于存储和管理进程的各种状态和信息。当操作系统进行进程切换时，它会保存当前进程的状态到其对应的 PCB 中，然后加载下一个进程的 PCB，从而实现进程之间的切换和调度。

PCB 在保证进程状态的正确性和执行的顺序上起着关键的作用，操作系统通过维护和管理 PCB 来实现进程的调度、资源分配和进程通信等功能，从而提供了一个稳定和可靠的多任务环境。

2.PCB的存储位置

PCB 被存储在内核的内存空间中，而不是进程的用户空间。这是为了确保 PCB 的安全性和可靠性，避免进程对其进行非法访问或篡改。

二、进程的三级映射

在操作系统中，进程的三级映射（Three-level Page Table Mapping）是一种虚拟内存管理技术，通过使用多级页表来实现大规模的内存映射。它是现代操作系统中常见的内存管理方案之一。

传统的两级页表结构由一个单一的页表来管理虚拟地址到物理地址的映射关系。然而，当系统的物理内存非常大时，这种单级页表会占据较大的内存空间，并且遍历页表以查找映射关系的时间也较长。为了解决这些问题，引入了三级页表。

三级页表的结构由三个层次的页表构成，每个层次都有一个页表。其中，每个页表通过索引来决定下一个页表的地址，从而实现逐级查找的快速内存映射。

具体来说，三级页表的结构如下：

1.顶级页表（PML4，Page Map Level 4）：顶级页表是三级页表的最高级别，在这一级别上进行虚拟地址到物理地址的映射。顶级页表结构包含了多个页表项，每个页表项指向下一级的页目录表。

2.页目录表（PDPT，Page Directory Pointer Table）：页目录表是三级页表的中间级别，包含了多个页目录项。每个页目录项指向下一级的页表。

3.页表（PD，Page Directory）：页表是三级页表的最低级别，包含了多个页表项。每个页表项最终映射到物理页面。

通过三级页表，系统可以将大型的虚拟地址空间分割成更小的块进行管理。只有在需要的情况下，才会加载或创建实际的页表项和物理页面，从而实现了懒加载和按需分配的内存管理机制。这样可以节省内存空间，并提高内存访问的效率。

总结起来，进程的三级映射是一种虚拟内存管理技术，通过三层级联的页表结构实现了大规模的内存映射。它提供了更灵活的内存管理和更高效的映射查找，适用于大型内存系统和需要管理大量虚拟地址空间的场景。

三、return , exit, pthread_exit

1.return : 返回调用者

2.exit : 退出进程

3.pthread_exit ： 退出线程

四、pthread_join作用

使用pthread_join()函数等待子线程的结束，并且释放包括堆栈空间和其他系统资源。

五、互斥锁和信号量的区别

旋锁（Spin Lock）和信号量（Semaphore）是同步机制中常用的两种方式，它们有以下区别：

1.工作方式：自旋锁是一种忙等待的方式。当一个线程尝试获取自旋锁时，如果锁已被其他线程占用，该线程会一直循环检查锁的状态，直到锁可用。这种方式适用于锁的占用时间很短暂的情况。信号量是一种阻塞机制。当一个线程尝试获取信号量时，如果信号量计数为0，则线程会被阻塞，在计数不为0时才能继续执行。

2.CPU占用：自旋锁在获取锁失败时会进行忙等待，持有锁的线程可能长时间不释放锁，导致等待线程一直在循环检查，占用CPU资源。而信号量使用阻塞机制，等待线程会被挂起，不占用CPU资源，直到信号量可用才会被唤醒。

3.同步范围：自旋锁主要用于对临界区的保护，即一小段代码或一段操作。线程在进入临界区前先获取自旋锁，退出临界区后释放自旋锁。信号量可以用于限制资源的访问数目，可以对多个临界区进行保护，线程在资源可用时获取信号量，使用资源后释放信号量。

4.适用场景：自旋锁适用于锁的占用时间短暂、锁冲突的概率低、并发程度高的情况。当临界区的执行时间相对较短，忙等待的开销可以接受时，自旋锁是一个有效的选择。信号量适用于锁的占用时间较长、锁冲突概率高、并发程度低的情况。当临界区的执行时间较长或者需要限制资源的并发访问时，阻塞等待的方式可以有效避免忙等待造成的资源浪费。

六、怎么判断链表是否有环

1.创建两个指针，一个指针称为快指针（fast），另一个指针称为慢指针（slow），初始时都指向链表的头节点。

2.快指针每次向前移动两个节点，慢指针每次向前移动一个节点。

3.如果链表中存在环，那么快指针和慢指针最终会相遇。

4.如果链表中不存在环，那么快指针最终会先到达链表尾部，此时可以判断链表无环。

#include <stdbool.h>

// 定义链表节点
struct ListNode {
    int val;
    struct ListNode* next;
};

bool hasCycle(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return false;  // 链表为空或只有一个节点，不可能有环
    }
    
    struct ListNode* slow = head;  // 慢指针
    struct ListNode* fast = head->next;  // 快指针
    
    while (fast != slow) {
        if (fast == NULL || fast->next == NULL) {
            return false;  // 快指针已经到达链表尾部，没有环
        }
        
        // 快指针每次移动两步，慢指针每次移动一步
        fast = fast->next->next;
        slow = slow->next;
    }
    
    return true;  // 快指针追上慢指针，存在环
}

总结

本篇文章就介绍到这里。