嵌入式开发工程师笔试面试指南-操作系统-2
4 死锁 ⭐⭐⭐⭐⭐
1 死锁概述
死锁是指两个或多个进程在执行过程中，因竞争系统资源而互相等待对方的资源，导致进程无限期地阻塞的现象。简而言之，就是若干个进程因为相互等待对方释放资源而陷入了死循环，无法向前推进，也无法退出。
死锁通常发生在多个进程共享有限的系统资源时，如共享内存、文件、打印机等。当多个进程都在等待某个资源时，而这些资源又被其他进程占用时，就会出现死锁的情况。例如，进程A占用了资源1，并等待资源2，而进程B占用了资源2，并等待资源1，这样就形成了死锁。
死锁的出现导致系统资源的浪费，也会使得进程卡住，无法完成任务，从而影响系统的稳定性和可靠性。因此，防止和解决死锁问题在操作系统中是一个重要的研究方向。
2 死锁的起因
造成死锁的起因主要是由于系统资源的竞争和分配不合理，具体来说，有以下几个方面：
- 竞争互斥资源：多个进程竞争同一个互斥资源（比如一块儿共享内存），这种资源只能被一个进程占用，其他进程需要等待资源释放。
- 进程持有部分资源而请求资源：进程已经获得了部分资源，但是又请求其他进程正持有的资源，而这些资源又无法被抢占。
- 进程推进顺序不当引起死锁，除了系统中多个进程对资源的争夺会引起死锁外，进程在运行的过程中，对资源进行申请和释放的顺序是否合法，也是在系统中产生死锁的一个重要因素。
- 资源分配不当：系统在分配资源时出现问题，比如错误的资源分配顺序或者过多地分配资源，从而导致某些进程一直无法获得需要的资源。
- 循环等待：各个进程之间互相等待对方所持有的资源释放，形成了一个循环等待的状态，从而导致了死锁的出现。
因此，为了避免出现死锁，需要合理地设计程序和系统，合理分配资源，并采取一些解决措施，如资源预分配、进程抢占、超时机制和死锁检测和恢复等。
3 死锁的四个必要条件
死锁是指两个或多个进程在执行过程中，因争夺系统资源而产生的一种僵局，它们都无法继续执行下去。产生死锁的原因在于这些进程相互占用着所需资源却又无法释放，无法向前推进，形成了死结。死锁具有以下四个必要条件：
- 互斥条件：至少有一种资源必须被独占而不能共享，即进程只能拥有一个资源。
- 请求与保持条件：进程必须同时持有所需要的资源并且在等待它未拥有的资源时不释放自己所占有的资源。
- 不剥夺条件：进程已获得的资源，在未使用完之前，不能被其他进程所强制夺去。
- 环路等待条件：由若干个进程之间形成一种头尾相接的循环等待资源的关系，使得请求资源的进程永远不能得到满足。
当以上四个条件全部满足时，就会发生死锁。对于死锁的预防和避免，可以采取一些措施，例如破坏死锁中的其中一个或多个条件等。
4 预防死锁
预防死锁的方法有以下几种：
1. 避免使用死锁发生的资源：首先避免使用可导致死锁发生的资源，比如互斥锁，限定资源的访问只能单向进行。
- 尽量减少保持资源的时间：在程序中，尽可能减少对共享资源的使用时间，这样可以降低资源竞争的概率，也减小了死锁发生的可能性。
- 破坏循环等待条件：通过规定资源的分配顺序，避免进程之间互相等待。可以采取将所有资源类型编号，要求进程只能按编号升序访问资源的方式，从而避免循环等待的局面。
- 死锁检测和恢复：实时监测系统资源的状态，及时发现死锁，以及采取相应的措施，如释放资源、抢占进程等来解除死锁状态。
综上所述，预防死锁的方法主要是通过限定资源的访问顺序、尽可能减少保持资源的时间、破坏循环等待条件，以及采取死锁检测和恢复等方法，使系统没有死锁的情况出现。
5 避免死锁
为避免死锁，可以从以下几个方面着手：
- 破坏循环等待条件：通过定义资源使用规则，避免进程之间形成循环等待的情况。
- 预防死锁：避免使用可能导致死锁的资源，尽量减少保持资源的时间，合理分配资源，从而降低死锁的发生概率。
- 死锁检测和恢复：实时监测系统资源的状态，及时发现死锁，以及采取相应的措施，如释放资源、抢占进程等来解除死锁状态。
- 调整资源分配策略：在资源分配策略方面可以尝试采取其他方案，如资源复制、动态资源分配等，进一步减少死锁的概率。
总之，避免死锁需要综合考虑资源分配、进程调度、死锁检测等多方面的因素，并采取相应的措施来确保系统的可靠性和稳定性。具体而言，尽可能地破坏循环等待条件、避免死锁产生、实时检测死锁状态、调整资源分配策略等都是可行的方法。
6 死锁的检测和解除
死锁的检测和解除死锁的检测和解除是一种重要的死锁处理方法。它的基本思想是通过检测系统的状态并采取相应的措施来解除死锁状态。
在实际应用中，可以采用以下方法来检测和解除死锁：
- 静态检测：通过分析系统的资源分配情况来判断是否会发生死锁。这种方法适用于系统规模较小，资源数量较少的情况。
- 动态检测：在运行时动态地检测系统的资源分配情况，当系统进入死锁状态时，采取相应的措施解除死锁。常用的动态死锁检测算法有银行家算法、死锁检测图算法等。
- 死锁的解除：一旦发现死锁情况，就需要采取相应的措施来解除死锁。常用的死锁解除方法有剥夺资源法、撤销进程法、进程回退法等。
死锁的解除需要仔细考虑，否则可能导致系统的崩溃或丢失数据等严重问题。因此，必须根据具体的情况，综合考虑多种因素，以最小代价解除死锁。
总之，死锁的检测和解除是一种常用的死锁处理方法，主要是通过监测系统状态、判断是否存在死锁并采取相应的解锁措施来保证系统的稳定性和可靠性。
7 操作系统中的锁
临界区
在计算机科学中，临界区（Critical Section，也称作临界段）是指一段代码，这段代码在同一时刻只能被一个进程或线程访问。在临界区内，对于共享的资源（如全局变量、共享内存等）进行操作。因此，在多线程和多进程的环境下，为了避免互相干扰造成资源访问的冲突和数据不一致的情况，需要将临界区的访问进行同步。
当多个线程或进程需要同时访问共享资源时，为了确保数据的正确性，需要使用互斥锁等同步机制来控制线程或进程对临界区的访问。在临界区内，一次只有一个线程或进程能够对共享资源进行读写操作，以避免数据访问的竞争和冲突。
临界区同步机制可以确保任意时刻只有一个线程或进程能够访问共享资源，从而避免了资源争用的问题，并保证了多线程和多进程的环境下程序的正确性和稳定性。同时，合理的使用临界区机制也能够提高程序的运行效率和吞吐量。
需要注意的是，临界区的长度应该尽量的短，只包含必须的代码段，以避免过多的等待锁的时间，造成程序的性能损失。
互斥锁
互斥锁（Mutex）是一种常见的同步机制，用于控制多个线程对共享资源的互斥访问。当一个线程持有互斥锁时，其他线程必须等待该线程释放锁后才能进入临界区。
互斥锁的基本操作包括上锁（lock）和解锁（unlock）。当一个线程要访问共享资源时，它需要先请求（lock）互斥锁，如果互斥锁没有被其他线程占用，则该线程获得锁并进入临界区，否则线程将被阻塞，直到锁被释放为止。当线程完成对共享资源的访问后，它需要调用解锁（unlock）操作来释放互斥锁，以便其他线程可以获取锁并访问共享资源。
互斥锁的优点是敦促线程按照规定的顺序通过临界区，避免了竞态条件和数据竞争，同时提高了程序的可靠性和稳定性。但是，如果互斥锁的使用不当，则可能会导致死锁等问题，因此需要注意锁的使用和释放。
在不同的操作系统和编程语言中，互斥锁的实现方式有所不同。例如，在Linux系统中，可以使用pthread_mutex_t结构体和相关函数来实现互斥锁，而在Java中，可以使用synchronized关键字来实现线程同步和互斥。
读写锁
读写锁（Read-Write Lock）是一种特殊的锁机制。它允许多个线程同时读取一个共享资源，但只允许一个线程写入共享资源。读写锁分为读锁（Shared Lock）和写锁（Exclusive Lock）两种模式。在读模式下，多个线程可以同时持有读锁，而在写模式下，只有一个线程可以持有写锁。
与互斥锁相比，**读写锁的优势在于允许多个线程同时对共享资源进行读取操作，从而提高了并发性能和效率。**在读多写少的场景下，采用读写锁可以更好地利用CPU和资源，避免了读操作的阻塞，提高了程序的响应速度和吞吐量。
但需要注意的是，如果读写锁被频繁的转换成写锁以及持有锁的时间过长，可能会导致锁的竞争和等待时间过长，进而影响程序的运行效率，因此需要在使用读写锁的场景下进行合理的设计和使用。
在Linux系统中，可以使用pthread_rwlock_t结构体和相关函数来实现读写锁，在C++11标准中，标准库提供了std::shared_mutex（共享互斥量）类来实现读写锁。
自旋锁
自旋锁（Spin Lock）是一种特殊的锁机制。不同于互斥锁或读写锁，在自旋锁的实现中，线程不会被挂起或进入睡眠状态，而是在一个循环中不断的尝试去获取锁，直到成功为止。
因为自旋锁不会让线程睡眠或切换上下文，所以它的优点在于减少了线程切换的开销和上下文切换的时间，提高了程序的响应速度和吞吐量。但同时需要注意，如果自旋锁一直无法获取到锁，就会导致线程不停地在循环中忙等待，浪费了CPU的资源。
因此，自旋锁适用于多处理器系统，在这种系统中，对于其他处理器而言，持有锁的线程可能仍然处于就绪状态，因此持有锁的时间很短，使用自旋锁可以减少线程的切换开销以及上下文切换的时间，提高了程序的执行效率。
在Linux系统中，可以使用pthread_spin_lock()函数和pthread_spin_unlock()函数来实现自旋锁。在C++11标准中，标准库提供了std::spin_lock类来实现自旋锁。
条件变量
条件变量（Condition Variable）是一种线程间同步的机制，它允许一个或多个线程在满足特定条件的情况下等待或唤醒其他线程。简单来说，条件变量解决的是线程间的等待和通知问题。
条件变量通常与互斥锁一起使用，因为条件变量最常见的应用场景是在等待共享资源的时候。当一个线程在持有互斥锁的时候，发现所需的共享资源没有准备好，这时就可以使用条件变量将该线程加入等待队列，释放锁并挂起等待条件满足的状态。当其他线程释放资源并通知条件变量后，该线程就可以从等待队列中被唤醒，重新获取互斥锁，继续执行操作。
在Linux系统中，可以使用pthread_cond_t结构体和相关函数来实现条件变量，常用的函数包括pthread_cond_init()、pthread_cond_wait()、pthread_cond_signal()和pthread_cond_broadcast()等。在C++11标准中，标准库提供了std::condition_variable类来实现条件变量。
信号量
信号量（Semaphore）是一种用于进程之间或者线程之间同步的机制。它可以确保在同一时刻内只有一个线程或进程访问共享资源，避免了数据争用和相互干扰。
信号量分为两种类型：二元信号量和计数信号量。二元信号量的取值只有0和1两种，通常用于实现互斥锁的功能，也称为互斥量（Mutex）。而计数信号量的取值可以是任意正整数，它可以用于实现线程的同步和协调操作。
在Linux系统中，可以使用sem_t结构体和相关函数来实现信号量，常用的函数包括sem_init()、sem_wait()、sem_post()和sem_destroy()等。在C++11标准中，标准库也提供了std::counting_semaphore和std::binary_semaphore类来实现计数信号量和二元信号量。
8 互斥锁、读写锁、自旋锁、条件变量、信号量的区别和各自应用场景
互斥锁、读写锁、自旋锁、条件变量和信号量都是操作系统中常用的同步机制，它们各有不同的应用场景。
- 互斥锁
互斥锁可以确保同一时刻只有一个线程或进程访问共享资源，防止并发访问导致的数据竞争问题，常用于保护共享变量、全局数据和文件等关键资源的访问。适用于互斥资源访问的场景。
- 读写锁
读写锁适用于经常被读取而很少被修改的共享资源，它允许多个线程同时读取资源，但只有一个线程能写入资源。读写锁的引入可以大大提高并发访问的效率，有效降低读取操作的等待时间。适用于读多写少的数据结构和高并发读取的场景。
- 自旋锁
自旋锁也是一种互斥锁，但它采用占用式的轮询方式，而不是将线程阻塞休眠。当发现自旋锁已经被占用时，线程会不断地尝试获取锁，直到获取到为止，从而避免线程上下文的切换和进程间调度的开销。适用于锁的竞争不激烈或者锁的占用时间非常短的场景。
- 条件变量
条件变量通常与互斥锁一起使用，用于线程之间的等待和通知。当一个线程持有互斥锁时，发现所需的条件未满足时，就可以使用条件变量将该线程挂起等待条件满足的状态。当其他线程释放资源并通知条件变量后，该线程就可以从等待队列中被唤醒，重新获取互斥锁，继续执行操作。适用于需要等待条件满足才能进行后续操作的场景。
- 信号量
信号量分为二元信号量和计数信号量。二元信号量通常用于实现互斥锁，它只有两个取值，可以保证在同一时刻内只有一个线程或进程访问共享资源。计数信号量的取值可以是任意正整数，它常常用于实现多个线程之间的同步和协调操作。适用于需要实现进程或线程同步的场景。
综上所述，不同的同步机制适用于不同的应用场景，需要根据实际情况选择合适的同步机制来实现线程间的同步和协作操作。
9 自旋锁和信号量可以睡眠嘛？为什么？
自旋锁和信号量都是操作系统中的同步机制，不同之处在于它们的策略不同。自旋锁是一种忙等待的策略，即线程会不断地检查锁是否可以被获得。如果锁已经被占用了，线程就会一直占用CPU直到锁被释放。而信号量则是一种休眠的策略，即线程在不能获得资源时会进入睡眠状态，等待其他线程释放资源后，再唤醒自己。
因此，自旋锁是不会睡眠的，它会一直占用CPU，等待锁被释放。这种忙等待的方式会浪费CPU时间，而且由于自旋锁不能睡眠，它在多核处理器上的效率可能比较低。
信号量则是可以睡眠的，因为它采用休眠等待的方式，即当一个线程等待信号量时，它会进入睡眠状态，等待其他线程释放资源后，再被唤醒执行。这种方式可以使得线程占用的CPU时间更少，而且能够提高系统的整体效率。但是仍然需要谨慎使用，因为睡眠和唤醒都需要一定的时间开销，如果频繁的睡眠和唤醒可能会影响系统的性能表现。
总之，自旋锁是一种适用于短时间并发操作的同步机制，而信号量则适用于需要较长时间等待资源的同步场景。在实际应用中，需要根据具体的场景和需求选择合适的同步机制来确保程序的正确性和性能。
10 自旋锁和信号量可以用于中断嘛？为什么？
在中断处理程序中，一般不应该使用自旋锁和信号量。这是因为中断处理程序必须尽可能快速地完成任务，保证中断的处理能够及时地响应，如果在中断处理程序中使用了自旋锁或信号量，可能会导致以下问题：
- 自旋锁会占用CPU，并且在中断处理程序的上下文中，如果持有自旋锁、则无法响应其他中断，这样会影响系统的实时性，但可以用于中断。由于自旋锁会不断的占用CPU时间，还会增加中断延迟，从而影响系统整体的性能。
- 信号量在等待时会进行睡眠操作，在中断环境中是不能睡眠的，因为中断处理程序是处理异步事件的，中断程序不可被阻塞，否则会引起系统崩溃。
因此，在中断处理程序中，应该避免使用需要等待的同步机制（如信号量、读写锁等），而是应该采用可重入锁或者原子操作等非阻塞的同步机制。这能够使中断处理程序快速地响应和完成处理任务，确保系统实时性和稳定性。
5 存储管理 ⭐⭐⭐⭐⭐
1 存储器的层次结构
计算机的存储器层次结构，从下到上依次为：
- 寄存器：位于CPU内部的存储器，速度最快，容量最小，一般只存储少量临时数据和指令操作码。
- 高速缓存（Cache）：位于CPU和主存之间的存储器，作为缓存来提供更快的访问速度和更高的访问效率，一般分为L1、L2、L3级别。
- 主存储器（Main Memory）：由DRAM（Dynamic Random Access Memory）芯片组成的存储器，是计算机系统中存储数据的主要设备，速度比较快，但容量一般较小。
- 辅助存储器（Auxiliary Storage）：例如硬盘、光盘等，容量很大、速度较慢而且访问时间不固定，主要用来长期存储和备份数据，可作为虚拟内存，供程序使用。
以下是存储器层次结构的图示：
---------------------------
| CPU |
---------------------------
|
---------------------------
| Cache |
---------------------------
|
---------------------------
| Main Memory |
---------------------------
|
---------------------------
| Auxiliary Storage |
---------------------------
其中，CPU内部的寄存器与Cache的关系最近，Cache与主存之间的关系其次，主存与辅助存储器之间的关系最远。在程序进行读写操作时，从辅助存储器到CPU的路径上逐级访问，随着存储器层次的提高，存储器的存储速度逐渐提高，但是容量逐渐降低。
这些存储器的速度和容量随层次的不同，从上至下逐渐降低而容量逐渐增大，每级存储器的价格也会随着降低。优化程序在性能上应该利用好高速缓存和主存储器，在程序设计时尽量减少对辅助存储器的访问次数。
2 程序的装入和链接
程序的装入
定义：是将可执行程序从外存调入内存的过程。程序的装入通常包括以下几个步骤：
- 分配内存空间。操作系统需要查看可执行程序的大小，预留足够的内存空间。
- 加载可执行代码。将可执行程序的二进制代码从外存读入内存中。
- 加载数据段。将可执行程序中的数据段加载到内存中，通常是动态分配内存空间，将数据段内容复制到动态分配的内存空间中。
- 重定位。在加载代码时，需要进行地址的重定位，将程序中使用的地址映射到正确的内存地址上，保证程序能够正确运行。
通常，操作系统会在程序运行启动时，预先分配一段内存用于存储可执行程序，该段内存称为进程空间。进程空间通常包括代码段、数据段、堆和栈等不同区域。可执行代码存储在代码段中，在代码段加载时，需要根据程序代码的起始地址和长度信息计算出代码段中具体的内存地址，并将代码全部加载到指定的内存地址中。
数据段通常存储程序的全局变量和静态变量等数据，由于数据大小可能不确定，因此数据段通常采用动态分配内存的方式进行加载。
在程序加载时，通常需要进行地址的重定位。在编写程序时，通常使用的是逻辑地址，即程序所使用的内存地址是虚拟的，需要在加载时转换成物理地址。由于程序加载位置可能不确定，因此需要将所有的逻辑地址都加上偏移量，计算得到正确的物理地址。
以上就是程序装入的基本步骤。
程序的链接
程序的链接是指将程序的各个模块之间相互调用的关系建立起来的过程，通常包括以下几个步骤：
- 符号解析。将各个模块中的符号引用找到对应的符号定义。
- 地址重定位。将引用的符号的地址映射到正确的地址上。
- 符号决议。将静态链接的符号连接到代码中。
- 重定义。将符号定义合并。
链接可以分为静态链接和动态链接。
静态链接是指将外部模块代码的副本直接拷贝到可执行文件中，使得可执行文件直接包含外部模块中的代码。这种方法使得可执行文件无需依赖外部模块的存在，也不需要在程序运行的时候进行链接。但是，这样会增加可执行文件的体积，使得可执行文件变得更大。
动态链接是指在程序运行时才进行链接，使得程序在链接的时候可以动态地使用外部模块。这种方式使得多个程序可以共享同一个库文件，并且在运行过程中能够动态地升级和替换库文件。但是，动态链接可能会降低程序的执行效率。
3 分配存储管理方式
存储管理是操作系统中非常重要的一个功能。它的主要任务是对计算机的物理内存进行分配和管理，以便让不同的程序和进程能够共享计算机的内存资源。常见的存储管理方式包括以下几种：
- 单一连续分配：将整个内存分配给一个进程使用，操作系统只有在进程执行完毕后才能释放内存。这种方式适用于单用户系统，但不适用于多任务操作系统。
- 固定分区分配：将内存划分成多个固定大小的区域，每个区域只能分配给一个进程使用。这种方式比较简单，但是容易浪费内存空间。
- 动态分区分配：将内存分成不同大小的块，每个进程请求分配内存时，会从可用的块中选择一个大小适合的块进行分配。这种方式比较灵活，但是需要维护一个内存管理表，而且容易产生内存碎片问题。
- 伙伴系统：将内存分成大小相等的块，每次分配内存时，选择一个大小刚好的块进行分配，如果需要更大的内存时，则从相邻的两个较小块中合并成一个相对较大的块。这种方式相比于动态分区分配效率更高，但是实现相对较为复杂。
- 虚拟存储：在实际内存不足时，将部分不常用的数据和代码转移到硬盘等外部存储器中，以释放内存空间。由于硬盘速度较慢，虚拟存储的性能相比于实际内存较低，但是可以大大扩展计算机的内存容量。
4 动态分区分配算法
动态分区分配是一种可以动态地为进程分配内存的方式，根据进程的需要，将内存分成多个不同大小的块。当进程需要内存时，动态分区分配算法会按照一定规则从内存块中选取一个大小适合的块分配给进程。主要的动态分区分配算法包括以下几种：
- 首次适应算法（First Fit）：分配时从内存分区的起始地址开始查找，找到第一个能满足需求的分区进行分配。由于查找速度快，所以操作效率较高，但是可能会产生较多的内存碎片。
- 最佳适应算法（Best Fit）：分配时从内存分区中找到能满足需求且大小最小的分区进行分配。这种方式可以更充分地利用内存空间，但是搜索代价较大，容易产生大量的未分配空间。
- 最坏适应算法（Worst Fit）：分配时从内存分区中找到能满足需求且大小最大的分区进行分配。与最佳适应算法相比，最坏适应算法更容易产生较大的未分配空间。
- 循环首次适应算法（Next Fit）：与首次适应算法类似，但是从上次分配分区的下一个开始搜索，避免了每次都从头开始搜索的开销，减少了碎片产生的概率。
这些算法各有优缺点，根据实际需求选择合适的算法。
5 分页存储管理方式
分页存储管理方式是一种内存分配方式，将物理内存分成大小相等的若干个固定大小的块，称为页框（Page Frame）。同时，将进程的虚拟地址空间分成大小相等的若干个固定大小的块，称为页面（Page）。当进程需要使用某个页面时，操作系统将其映射到某个页框中，页框的大小通常为 4KB 或 8KB。
此外，分页存储管理方式需要使用页表（Page Table）进行虚拟地址到物理地址的转换。页表是一个记录了所有页面与页框之间映射关系的数据结构，每个进程都有自己独立的页表。当进程访问某个页面时，操作系统会根据页表将该页面映射到对应的物理地址上。
分页存储管理方式的优点是：
- 提高了内存利用率：按照固定大小划分内存空间，避免了内存碎片的产生，提高了内存利用率。
- 方便了进程的内存管理：通过使用页表实现虚实地址的映射，进程可以更方便地进行内存管理。
- 提高了系统的可靠性：通过使用分页机制，使得操作系统能够更方便地对内存空间进行保护和管理，提高了系统的可靠性。
但分页存储管理方式也存在一些缺点：
- 由于每个进程都需要有一份页表，并且页表较大，需要额外的内存空间，因此会增加操作系统的开销。
- 分页会导致一些额外的开销，如页表的查询和更新、页面的拷贝等，这些操作都会导致一定的开销。
6 分段存储管理方式
分段存储管理方式是一种将进程的虚拟内存空间划分为多个大小不同的段，每个段代表着不同的逻辑单元，如代码段、数据段、堆栈段等。与分页方式类似，每个段都被映射到物理内存中的某个区域。
分段存储管理方式的优点：
- 每个段都有特定的逻辑含义，使得程序的分析和设计更为方便。
- 每个段的大小可以根据其需要进行动态分配，可以更精确地控制内存的使用。
- 避免了由内部碎片带来的浪费。
- 同一段内的地址空间可以连续使用，便于内存的管理和维护。
分段存储管理方式的缺点：
- 由于每个进程的段数及大小都不同，因此需要使用表格来存储段信息，会增加表格的复杂程度。
- 分段模式中，段与段之间不是必须紧密相邻的，并且可能会发生随机存取，这样就会造成重复而频繁的内存空间的调用和切换，这样会拖累整个系统的速度。
- 由于段的大小不同，因此碎片问题仍然存在，如果不加以管理，会浪费部分内存空间。
总的来说，分段存储管理方式的优缺点与分页相比，二者都有其适用的场景。分页更适合于进程内存的紧凑管理，而分段更适合于程序中多个逻辑单元的分离存储。
7 段页式存储管理方式
段页式存储管理方式是将段式存储管理方式和页式存储管理方式结合起来的一种存储管理方式。它将进程的虚拟地址空间划分为多个段，然后将每个段再划分为多个页面。
段页式存储管理方式的优点：
- 可以兼具段式存储管理方式和页式存储管理方式的优点，既能够体现程序的逻辑结构，又能够提高内存利用率。
- 分页可以减小内存碎片，有效提高了内存的使用率。
- 不同的段可以分别采用不同的分页方式，用于不同的内存管理需求，灵活性更高。
- 可以避免页式存储管理方式由于过多的交换页面导致的性能下降问题。
段页式存储管理方式的缺点：
- 管理复杂度高，需要维护多级页表和多级段表，增加了内存访问的开销。
- 物理内存分配过小，可能会导致分配不足的问题，这需要系统支持动态内存分配。
- 段与段之间的地址空间可能不连续，需要额外的机制来处理段与段之间的访问。
总的来说，段页式存储管理方式是在分段和分页的基础上结合起来的一种存储管理方式，既具有段式存储方式的管理优点，又避免了页式存储管理方式的管理缺陷。但是由于其管理复杂度高，因此需要在实际应用中进行权衡和选择。
8 简述LRU算法及其实现方式。
LRU（Least Recently Used）算法是一种用于页面置换的算法，用于决定哪些页面应该被置换出内存。这个算法的基本思想是，当需要置换页面时，选择最近最少被使用的页面进行替换。
LRU 算法：
实现 LRU 算法的方式可以利用一个数据结构来记录页面的访问历史，可以使用链表或者队列来实现。下面是一种基于双向链表的 LRU 算法实现方式：
- 维护一个双向链表。链表的头部表示最近使用的页面，尾部表示最久未使用的页面。
- 当访问一个页面时，如果页面在链表中存在，将其从原位置删除，并插入到链表头部。
- 当访问一个页面时，如果页面不在链表中，且缓存未满，则直接将该页面插入到链表头部。
- 当访问一个页面时，如果页面不在链表中，且缓存已满，则删除链表尾部的页面，并将新页面插入到链表头部。
通过这种方式，最近访问的页面会被移到链表头部，而长时间未被访问的页面会逐渐移到链表尾部。当需要置换页面时，只需要淘汰链表尾部的页面即可。
LRU算法的优点是可以充分利用程序的局部性原理，将最近被访问的页面保留在内存中，从而提高缓存命中率和访问效率。但它也存在一些缺点，如实现复杂度较高和需要额外的数据结构来记录页面访问历史等。
#include <iostream>
#include <unordered_map>
using namespace std;
class LRUCache {
private:
struct ListNode {
int key;
int value;
ListNode* prev;
ListNode* next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
unordered_map<int, ListNode*> cache;
ListNode* head;
ListNode* tail;
int capacity;
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head->next = tail;
tail->prev = head;
}
void addToHead(ListNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
void deleteNode(ListNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
int get(int key) {
if (cache.count(key)) {
ListNode* node = cache[key];
deleteNode(node);
addToHead(node);
return node->value;
}
return -1;
}
void put(int key, int value) {
if (cache.count(key)) {
ListNode* node = cache[key];
deleteNode(node);
node->value = value;
addToHead(node);
} else {
if (cache.size() == capacity) {
ListNode* tailNode = tail->prev;
deleteNode(tailNode);
cache.erase(tailNode->key);
delete tailNode;
}
ListNode* newNode = new ListNode(key, value);
addToHead(newNode);
cache[key] = newNode;
}
}
};
int main() {
LRUCache lruCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
cout << lruCache.get(1) << endl; // 输出 1
lruCache.put(3, 3);
cout << lruCache.get(2) << endl; // 输出 -1，因为缓存中已经不存在 key 为 2 的元素
lruCache.put(4, 4);
cout << lruCache.get(1) << endl; // 输出 -1，因为缓存中已经不存在 key 为 1 的元素
cout << lruCache.get(3) << endl; // 输出 3
cout << lruCache.get(4) << endl; // 输出 4
return 0;
}使用了一个结构体 ListNode 表示双向链表的节点，通过指针 prev 和 next 连接节点。缓存的数据通过哈希表 cache 来进行快速查找，键为键值，值为节点指针。LRU 缓存的容量由变量 capacity 控制。每次访问或插入新数据时，通过操作链表的头部指针和节点的连接关系来更新缓存的访问顺序，同时使用哈希表来查询快速访问指定键值的节点。
6 虚拟存储器 ⭐⭐⭐⭐⭐
1 虚拟存储器概述
虚拟存储器（Virtual Memory）是一种计算机内存管理技术，它使得计算机可以同时运行多个大型应用程序，并将内存中正在使用的部分数据暂时存储到磁盘，从而释放出更多的内存。
虚拟存储器的基本原理是将内存空间分为一组固定大小的块（称为页面或页），当内存不足时，可将当前未被使用的页面从内存中存储到磁盘的虚拟存储器中。当程序需要这些页面时，系统可以将它们读回到内存中。
虚拟存储器技术可以提高计算机系统的性能和可用性，具有以下优点：
- 能够运行更多的程序，提高系统的并发性能和效率。
- 易于管理和分配内存，不需要手动控制内存分配和释放。
- 能够充分利用系统的物理内存和磁盘空间，避免了因内存不足而导致的程序运行错误或奔溃问题。
- 能够限制程序对物理内存的依赖，提高系统的稳定性和可靠性。
虚拟存储器技术的实现需要硬件和软件的支持，例如内存管理单元（MMU）、虚拟地址转换、页面置换算法等。虚拟存储器技术也存在一些缺点，如性能开销、磁盘空间占用和页面置换算法带来的开销等。
2 虚拟存储器定义和特征
虚拟存储器（Virtual Memory）是计算机内存管理技术的一种。它将磁盘作为扩展的内存空间，通过将物理内存。
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
#承诺提供免费技术答疑# 本专栏主要是介绍嵌入式开发岗位相关知识和学习攻略。“C/C++软件开发岗位”也可以参考。 该专栏覆盖了嵌入式求职过程中99%常见面试题，详细讲解了嵌入式软件开发岗位、学习攻略、项目经验分享、面试心得，从技术面，HR面，主管面，谈薪一站式服务。订阅即赠送简历模板、内推机会，需要的同学点击我头像私信即可！
元戎启行公司福利 3990人发布
查看7道真题和解析