旅游网网站建设方案,廊坊教育云网站建设,优化一个网站可以做多少关键词,一般做网站的在哪里找文章目录1. 进程、线程管理2. 内存管理3. 进程调度算法4. 磁盘调度算法5. 页面置换算法6. 网络系统7. 锁8. 操作系统知识点文章字数大约1.9万字#xff0c;阅读大概需要65分钟#xff0c;建议收藏后慢慢阅读#xff01;#xff01;#xff01;1. 进程、线程管理 进程和线程…
文章目录1. 进程、线程管理2. 内存管理3. 进程调度算法4. 磁盘调度算法5. 页面置换算法6. 网络系统7. 锁8. 操作系统知识点文章字数大约1.9万字阅读大概需要65分钟建议收藏后慢慢阅读1. 进程、线程管理 进程和线程基础知识 进程进程是系统进行资源分配和调度的一个独立单位是系统中的并发执行的单位。 线程线程是进程的一个实体也是 CPU 调度和分派的基本单位它是比进程更小的能独立运行的基本单位有时又被称为轻权进程或轻量级进程。 进程 运行中的程序就被称为「进程」Process。 在一个进程的活动期间至少具备三种基本状态即运行状态、就绪状态、阻塞状态。 运行状态Running该时刻进程占用 CPU就绪状态Ready可运行由于其他进程处于运行状态而暂时停止运行阻塞状态Blocked该进程正在等待某一事件发生如等待输入/输出操作的完成而暂时停止运行这时即使给它CPU控制权它也无法运行 当然进程还有另外两个基本状态 创建状态new进程正在被创建时的状态结束状态Exit进程正在从系统中消失时的状态 挂起状态可以分为两种 阻塞挂起状态进程在外存硬盘并等待某个事件的出现就绪挂起状态进程在外存硬盘但只要进入内存即刻立刻运行 PCB 进程控制块 是进程存在的唯一标识 PCB 具体包含什么信息呢 进程描述信息 进程标识符标识各个进程每个进程都有一个并且唯一的标识符用户标识符进程归属的用户用户标识符主要为共享和保护服务 进程控制和管理信息 进程当前状态如 new、ready、running、waiting 或 blocked 等进程优先级进程抢占 CPU 时的优先级 资源分配清单 有关内存地址空间或虚拟地址空间的信息所打开文件的列表和所使用的 I/O 设备信息。 CPU 相关信息 CPU 中各个寄存器的值当进程被切换时CPU 的状态信息都会被保存在相应的 PCB 中以便进程重新执行时能从断点处继续执行。 线程 线程是进程当中的一条执行流程。 同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源但每个线程各自都有一套独立的寄存器和栈这样可以确保线程的控制流是相对独立的。 线程的实现 主要有三种线程的实现方式 用户线程*User Thread*在用户空间实现的线程不是由内核管理的线程是由用户态的线程库来完成线程的管理内核线程*Kernel Thread*在内核中实现的线程是由内核管理的线程轻量级进程*LightWeight Process*在内核中来支持用户线程 第一种关系是多对一的关系也就是多个用户线程对应同一个内核线程 第二种是一对一的关系也就是一个用户线程对应一个内核线程 第三种是多对多的关系也就是多个用户线程对应到多个内核线程 用户线程的整个线程管理和调度操作系统是不直接参与的而是由用户级线程库函数来完成线程的管理包括线程的创建、终止、同步和调度等。 线程的优点 一个进程中可以同时存在多个线程各个线程之间可以并发执行各个线程之间可以共享地址空间和文件等资源 线程的缺点 当进程中的一个线程崩溃时会导致其所属进程的所有线程崩溃这里是针对 C/C 语言Java语言中的线程奔溃不会造成进程崩溃 内核线程是由操作系统管理的线程对应的 TCB 自然是放在操作系统里的这样线程的创建、终止和管理都是由操作系统负责。 进程/线程上下文切换 进程 一个进程切换到另一个进程运行称为进程的上下文切换。 进程的上下文切换到底是切换什么呢 进程是由内核管理和调度的所以进程的切换只能发生在内核态。 所以进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源还包括了内核堆栈、寄存器等内核空间的资源。 通常会把交换的信息保存在进程的 PCB当要运行另外一个进程的时候我们需要从这个进程的 PCB 取出上下文然后恢复到 CPU 中这使得这个进程可以继续执行 发生进程上下文切换有哪些场景 为了保证所有进程可以得到公平调度CPU 时间被划分为一段段的时间片这些时间片再被轮流分配给各个进程。这样当某个进程的时间片耗尽了进程就从运行状态变为就绪状态系统从就绪队列选择另外一个进程运行进程在系统资源不足比如内存不足时要等到资源满足后才可以运行这个时候进程也会被挂起并由系统调度其他进程运行当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时自然也会重新调度当有优先级更高的进程运行时为了保证高优先级进程的运行当前进程会被挂起由高优先级进程来运行发生硬件中断时CPU 上的进程会被中断挂起转而执行内核中的中断服务程序 线程 线程上下文切换的是什么 这还得看线程是不是属于同一个进程 当两个线程不是属于同一个进程则切换的过程就跟进程上下文切换一样当两个线程是属于同一个进程因为虚拟内存是共享的所以在切换时虚拟内存这些资源就保持不动只需要切换线程的私有数据、寄存器等不共享的数据 所以线程的上下文切换相比进程开销要小很多。 进程/线程间通信方式 进程间通信IPCInterProcess Communication是指在不同进程之间传播或交换信息。IPC 的方式通常有管道包括无名管道和命名管道、消息队列、信号量、共享存储、Socket、Streams 等。其中 Socket 和 Streams 支持不同主机上的两个进程 IPC。 管道 它是半双工的具有固定的读端和写端它只能用于父子进程或者兄弟进程之间的进程的通信它可以看成是一种特殊的文件对于它的读写也可以使用普通的 read、write 等函数。但是它不是普通的文件并不属于其他任何文件系统并且只存在于内存中。 命名管道 FIFO 可以在无关的进程之间交换数据与无名管道不同FIFO 有路径名与之相关联它以一种特殊设备文件形式存在于文件系统中。 消息队列 消息队列是消息的链接表存放在内核中。一个消息队列由一个标识符 ID 来标识消息队列是面向记录的其中的消息具有特定的格式以及特定的优先级消息队列独立于发送与接收进程。进程终止时消息队列及其内容并不会被删除消息队列可以实现消息的随机查询消息不一定要以先进先出的次序读取也可以按消息的类型读取。 信号量 信号量semaphore是一个计数器。用于实现进程间的互斥与同步而不是用于存储进程间通信数据信号量用于进程间同步若要在进程间传递数据需要结合共享内存信号量基于操作系统的 PV 操作程序对信号量的操作都是原子操作每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1而且可以加减任意正整数支持信号量组。 共享内存 共享内存Shared Memory指两个或多个进程共享一个给定的存储区共享内存是最快的一种 IPC因为进程是直接对内存进行存取。 Socket通信 前面说到的通信机制都是工作于同一台主机如果要与不同主机的进程间通信那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信还可以用于本地主机进程间通信可根据创建 Socket 的类型不同分为三种常见的通信方式一个是基于 TCP 协议的通信方式一个是基于 UDP 协议的通信方式一个是本地进程间通信方式。 以上就是进程间通信的主要机制了。你可能会问了那线程通信间的方式呢 同个进程下的线程之间都是共享进程的资源只要是共享变量都可以做到线程间通信比如全局变量所以对于线程间关注的不是通信方式而是关注多线程竞争共享资源的问题信号量也同样可以在线程间实现互斥与同步 互斥的方式可保证任意时刻只有一个线程访问共享资源同步的方式可保证线程 A 应在线程 B 之前执行 线程、进程崩溃发生什么 一般来说如果线程是因为非法访问内存引起的崩溃那么进程肯定会崩溃为什么系统要让进程崩溃呢这主要是因为在进程中各个线程的地址空间是共享的既然是共享那么某个线程对地址的非法访问就会导致内存的不确定性进而可能会影响到其他线程这种操作是危险的操作系统会认为这很可能导致一系列严重的后果于是干脆让整个进程崩溃 崩溃机制 CPU 执行正常的进程指令调用 kill 系统调用向进程发送信号进程收到操作系统发的信号CPU 暂停当前程序运行并将控制权转交给操作系统调用 kill 系统调用向进程发送信号假设为 11即 SIGSEGV一般非法访问内存报的都是这个错误操作系统根据情况执行相应的信号处理程序函数一般执行完信号处理程序逻辑后会让进程退出 注意上面的第五步如果进程没有注册自己的信号处理函数那么操作系统会执行默认的信号处理程序一般最后会让进程退出但如果注册了则会执行自己的信号处理函数这样的话就给了进程一个垂死挣扎的机会它收到 kill 信号后可以调用 exit() 来退出但也可以使用 sigsetjmpsiglongjmp 这两个函数来恢复进程的执行 守护进程、僵尸进程和孤儿进程 守护进程 指在后台运行的没有控制终端与之相连的进程。它独立于控制终端周期性地执行某种任务。Linux的大多数服务器就是用守护进程的方式实现的如web服务器进程http等 创建守护进程要点 1让程序在后台执行。方法是调用fork产生一个子进程然后使父进程退出。 2调用setsid创建一个新对话期。控制终端、登录会话和进程组通常是从父进程继承下来的守护进程要摆脱它们不受它们的影响方法是调用setsid使进程成为一个会话组长。setsid调用成功后进程成为新的会话组长和进程组长并与原来的登录会话、进程组和控制终端脱离。 3禁止进程重新打开控制终端。经过以上步骤进程已经成为一个无终端的会话组长但是它可以重新申请打开一个终端。为了避免这种情况发生可以通过使进程不再是会话组长来实现。再一次通过fork创建新的子进程使调用fork的进程退出。 4关闭不再需要的文件描述符。子进程从父进程继承打开的文件描述符。如不关闭将会浪费系统资源造成进程所在的文件系统无法卸下以及引起无法预料的错误。首先获得最高文件描述符值然后用一个循环程序关闭0到最高文件描述符值的所有文件描述符。 5将当前目录更改为根目录。 6子进程从父进程继承的文件创建屏蔽字可能会拒绝某些许可权。为防止这一点使用unmask0将屏蔽字清零。 7处理SIGCHLD信号。对于服务器进程在请求到来时往往生成子进程处理请求。如果子进程等待父进程捕获状态则子进程将成为僵尸进程zombie从而占用系统资源。如果父进程等待子进程结束将增加父进程的负担影响服务器进程的并发性能。在Linux下可以简单地将SIGCHLD信号的操作设为SIG_IGN。这样子进程结束时不会产生僵尸进程。 孤儿进程 如果父进程先退出子进程还没退出那么子进程的父进程将变为init进程。注任何一个进程都必须有父进程。 一个父进程退出而它的一个或多个子进程还在运行那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养并由init进程对它们完成状态收集工作。 僵尸进程 如果子进程先退出父进程还没退出那么子进程必须等到父进程捕获到了子进程的退出状态才真正结束否则这个时候子进程就成为僵尸进程。 设置僵尸进程的目的是维护子进程的信息以便父进程在以后某个时候获取。这些信息至少包括进程ID进程的终止状态以及该进程使用的CPU时间所以当终止子进程的父进程调用wait或waitpid时就可以得到这些信息。如果一个进程终止而该进程有子进程处于僵尸状态那么它的所有僵尸子进程的父进程ID将被重置为1init进程。继承这些子进程的init进程将清理它们也就是说init进程将wait它们从而去除它们的僵尸状态。 如何避免僵尸进程 通过signal(SIGCHLD, SIG_IGN)通知内核对子进程的结束不关心由内核回收。如果不想让父进程挂起可以在父进程中加入一条语句signal(SIGCHLD,SIG_IGN);表示父进程忽略SIGCHLD信号该信号是子进程退出的时候向父进程发送的。父进程调用wait/waitpid等函数等待子进程结束如果尚无子进程退出wait会导致父进程阻塞。waitpid可以通过传递WNOHANG使父进程不阻塞立即返回。如果父进程很忙可以用signal注册信号处理函数在信号处理函数调用wait/waitpid等待子进程退出。通过两次调用fork。父进程首先调用fork创建一个子进程然后waitpid等待子进程退出子进程再fork一个孙进程后退出。这样子进程退出后会被父进程等待回收而对于孙子进程其父进程已经退出所以孙进程成为一个孤儿进程孤儿进程由init进程接管孙进程结束后init会等待回收。 第一种方法忽略SIGCHLD信号这常用于并发服务器的性能的一个技巧因为并发服务器常常fork很多子进程子进程终结之后需要服务器进程去wait清理资源。如果将此信号的处理方式设为忽略可让内核把僵尸子进程转交给init进程去处理省去了大量僵尸进程占用系统资源。 进程和线程的比较 线程是调度的基本单位而进程则是资源拥有的基本单位。 线程与进程的比较如下 进程是资源包括内存、打开的文件等分配的单位线程是 CPU 调度的单位进程拥有一个完整的资源平台而线程只独享必不可少的资源如寄存器和栈线程同样具有就绪、阻塞、执行三种基本状态同样具有状态之间的转换关系线程能减少并发执行的时间和空间开销 对于线程相比进程能减少开销体现在 线程的创建时间比进程快因为进程在创建的过程中还需要资源管理信息比如内存管理信息、文件管理信息而线程在创建的过程中不会涉及这些资源管理信息而是共享它们线程的终止时间比进程快因为线程释放的资源相比进程少很多同一个进程内的线程切换比进程切换快因为线程具有相同的地址空间虚拟内存共享这意味着同一个进程的线程都具有同一个页表那么在切换的时候不需要切换页表。而对于进程之间的切换切换的时候要把页表给切换掉而页表的切换过程开销是比较大的由于同一进程的各线程间共享内存和文件资源那么在线程之间数据传递的时候就不需要经过内核了这就使得线程之间的数据交互效率更高了 所以不管是时间效率还是空间效率线程比进程都要高。 1、线程启动速度快轻量级 2、线程的系统开销小 3、线程使用有一定难度需要处理数据一致性问题 4、同一线程共享的有堆、全局变量、静态变量、指针引用、文件等而独自占有栈 进程是资源分配的最小单位而线程是 CPU 调度的最小单位创建进程或撤销进程系统都要为之分配或回收资源操作系统开销远大于创建或撤销线程时的开销不同进程地址空间相互独立同一进程内的线程共享同一地址空间。一个进程的线程在另一个进程内是不可见的进程间不会相互影响而一个线程挂掉将可能导致整个进程挂掉
2. 内存管理 物理地址、逻辑地址、虚拟内存的概念 物理地址它是地址转换的最终地址进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取是内存单元真正的地址。逻辑地址是指计算机用户看到的地址。例如当创建一个长度为 100 的整型数组时操作系统返回一个逻辑上的连续空间指针指向数组第一个元素的内存地址。由于整型元素的大小为 4 个字节故第二个元素的地址时起始地址加 4以此类推。事实上逻辑地址并不一定是元素存储的真实地址即数组元素的物理地址在内存条中所处的位置并非是连续的只是操作系统通过地址映射将逻辑地址映射成连续的这样更符合人们的直观思维。虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存一个连续完整的地址空间而实际上它通常是被分隔成多个物理内存碎片还有部分暂时存储在外部磁盘存储器上在需要时进行数据交换。 虚拟内存有什么好处 第一虚拟内存可以使得进程对运行内存超过物理内存大小因为程序运行符合局部性原理CPU 访问内存会有很明显的重复访问的倾向性对于那些没有被经常使用到的内存我们可以把它换出到物理内存之外比如硬盘上的 swap 区域。第二由于每个进程都有自己的页表所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表所以这些页表是私有的这就解决了多进程之间地址冲突的问题。第三页表里的页表项中除了物理地址之外还有一些标记属性的比特比如控制一个页的读写权限标记该页是否存在等。在内存访问方面操作系统提供了更好的安全性。 内存管理 内存管理的概念就是操作系统对内存的划分和动态分配。 内存管理功能 内存空间的分配与回收由操作系统完成主存储器空间的分配和管理是程序员摆脱存储分配的麻烦提高编程效率。 地址转换将逻辑地址转换成相应的物理地址。 内存空间的扩充利用虚拟存储技术或自动覆盖技术从逻辑上扩充主存。 存储保护保证各道作业在各自的存储空间内运行互不干扰。 创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序通常需要以下几个步骤 编译由编译程序将用户源代码编译成若干目标模块把高级语言翻译成机器语言 链接由链接程序将编译后形成的一组目标模块及所需的库函数连接在一起形成一个完整的装入模块由目标模块生成装入模块链接后形成完整的逻辑地址 装入由装入程序将装入模块装入内存运行装入后形成物理地址 程序的链接有以下三种方式 静态链接在程序运行之前先将各目标模块及它们所需的库函数连接成一个完整的可执行文件装入模块之后不再拆开。 装入时动态链接将各目标模块装入内存时边装入边链接的链接方式。 运行时动态链接在程序执行中需要该目标模块时才对它进行链接。其优点是便于修改和更新便于实现对目标模块的共享。 内存的装入模块在装入内存时有以下三种方式 重定位根据内存的当前情况将装入模块装入内存的适当位置装入时对目标程序中的指令和数据的修改过程称为重定位。 静态重定位地址的变换通常是在装入时一次完成的。一个作业装入内存时必须给它分配要求的全部内存空间若没有足够的内存则不能装入该作业。此外作业一旦装入内存整个运行期间就不能在内存中移动也不能再申请内存空间。 动态重定位需要重定位寄存器的支持。可以将程序分配到不连续的存储区中在程序运行之前可以只装入它的部分代码即可投入运行然后在程序运行期间根据需要动态申请分配内存。 内存分配前需要保护操作系统不受用户进程的影响同时保护用户进程不受其他用户进程的影响。内存保护可采取如下两种方法 在CPU中设置一对上、下限寄存器存放用户作业在主存中的上限和下限地址每当CPU要访问一个地址时分别和两个寄存器的值相比判断有无越界。 采用重定位寄存器或基址寄存器和界地址寄存器又称限长存储器来实现这种保护。重定位寄存器包含最小的物理地址值界地址寄存器含逻辑地址的最大值。每个逻辑地址值必须小于界地址寄存器内存管理机构动态得将逻辑地址与界地址寄存器进行比较若未发生地址越界则加上重定位寄存器的值后映射成物理地址再送交内存单元。 常见的内存分配方式 1 从静态存储区域分配。内存在程序编译的时候就已经分配好这块内存在程序的整个运行期间都存在。例如全局变量static变量。 2 在栈上创建。在执行函数时函数内局部变量的存储单元都可以在栈上创建函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中效率很高但是分配的内存容量有限。 3 从堆上分配亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定使用非常灵活但问题也最多。 常见内存分配内存错误 1内存分配未成功却使用了它。 2内存分配虽然成功但是尚未初始化就引用它。 3内存分配成功并且已经初始化但操作越过了内存的边界。 4忘记了释放内存造成内存泄露。 5释放了内存却继续使用它。常见于以下有三种情况 程序中的对象调用关系过于复杂实在难以搞清楚某个对象究竟是否已经释放了内存此时应该重新设计数据结构从根本上解决对象管理的混乱局面。函数的return语句写错了注意不要返回指向“栈内存”的“指针”或者“引用”因为该内存在函数体结束时被自动销毁。使用free或delete释放了内存后没有将指针设置为NULL。导致产生“野指针”。 malloc如何分配内存 从操作系统层面上看malloc是通过两个系统调用来实现的 brk和mmap brk是将进程数据段(.data)的最高地址指针向高处移动这一步可以扩大进程在运行时的堆大小mmap是在进程的虚拟地址空间中寻找一块空闲的虚拟内存这一步可以获得一块可以操作的堆内存。 通常分配的内存小于128k时使用brk调用来获得虚拟内存大于128k时就使用mmap来获得虚拟内存。 进程先通过这两个系统调用获取或者扩大进程的虚拟内存获得相应的虚拟地址在访问这些虚拟地址的时候通过缺页中断让内核分配相应的物理内存这样内存分配才算完成。 如何避免预读失效和缓存污染 预读失效 这些被提前加载进来的页并没有被访问相当于这个预读工作是白做了这个就是预读失效。 传统的 LRU 算法法无法避免下面这两个问题 预读失效导致缓存命中率下降缓存污染导致缓存命中率下降 为了避免「预读失效」造成的影响Linux 和 MySQL 对传统的 LRU 链表做了改进 Linux 操作系统实现两个了 LRU 链表活跃 LRU 链表active list和非活跃 LRU 链表inactive list。MySQL Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域young 区域 和 old 区域。 缓存污染 如果这些大量的数据在很长一段时间都不会被访问的话那么整个活跃 LRU 链表或者 young 区域就被污染了。 为了避免「缓存污染」造成的影响Linux 操作系统和 MySQL Innodb 存储引擎分别提高了升级为热点数据的门槛 Linux 操作系统在内存页被访问第二次的时候才将页从 inactive list 升级到 active list 里。 MySQL Innodb在内存页被访问 第二次 的时候并不会马上将该页从 old 区域升级到 young 区域因为还要进行 停留在 old 区域的时间判断 如果第二次的访问时间与第一次访问的时间在 1 秒内默认值那么该页就不会被从 old 区域升级到 young 区域如果第二次的访问时间与第一次访问的时间超过 1 秒那么该页就会从 old 区域升级到 young 区域 通过提高了进入 active list 或者 young 区域的门槛后就很好了避免缓存污染带来的影响。 物理内存管理 操作系统物理内存管理主要包括程序装入、交换技术、连续分配管理方式和非连续分配管理方式分页、分段、段分页。 连续分配管理方式 连续内存分配 内存碎片 当给程序分配空间时可能会出现一些无法被利用的空闲碎片空间。 1.外部碎片分配单元之间无法被利用的内存碎片 2.内部碎片分配给任务内存大小大于任务所需内存大小时多出来的内存碎片。 分区的动态分配 连续内存分配情况将应用程序从硬盘加载到内存中给内存分配一块内存。应用程序运行访问数据数据的连续内存空间。 内存分配算法 具体问题具体分析适配算法。 首次适配 定义使用第一块内存大小大于需求大小的可用空闲块 实现方法需要有一个按地址排序的空闲块列表。寻找第一个满足内存需求的空闲块。对于回收要考虑空闲块与相邻空闲块合并问题。 优点简单易于产生更大的空闲块想着地址空间结尾分配 缺点产生外部碎片具有不确定性 最优适配 定义寻找整个空闲块中最满足分配请求的空闲块内存差值最小。 实现方法需要有一个按尺寸排序的空闲块列表寻找最满足分配的内存块。对于回收要考虑空闲块与相邻空闲块合并问题。 优点避免分割大空闲块最小化外部碎片的产生简单 缺点外部碎片很细有很多微小碎片不利于后续分配管理。 最差适配 定义找到差距最大的内存空闲块。 实现需要有一个按尺寸排序的空闲块列表寻找差距最大的内存块。对于回收要考虑空闲块与相邻空闲块合并问题。 优点避免产生微小外部碎片分配效率高适用于分配中大快 缺点对于大块请求带来一定影响 减少内存碎片方法 紧致压缩式碎片整理 调整运行程序的位置。 1.重定位的时机。不能在程序运行时进行可以在程序等待时拷贝。 2.内存拷贝开销很大。 swaping交换式碎片整理 把硬盘作为一个备份。把等待的程序包括数据主存挪到硬盘上。当硬盘上程序需要执行时再拷贝到主存上。 1.交换那个程序减小开销 2.交换的时机 非连续内存分配 连续内存分配和非连续内存分配 连续内存分配缺点1.分配给一个程序的物理内存是连续的内存利用率较低由外碎片内碎片的问题。 非连续内存分配优点1.程序物理地址是非连续的 2.更好的内存利用和管理 3.允许共享代码与数据 4.支持动态加载和动态链接 非连续内存分配缺点建立虚拟地址到物理地址的映射软件开销太大可以用硬件支持 -》硬件两种管理方案分段和分页 分段 分段地址空间 对于一段程序内存可以分为程序主程序子程序共享库变量栈、堆、共享数据段 分段更好的分离与共享将逻辑地址空间分散到多个物理地址空间 逻辑地址是连续的将具有不同功能的映射到物理空间中这些段大小不一位置不一 硬件实现分段寻址机制 一维逻辑地址有不同段组成首先将逻辑地址分为两段段寻址段号段偏移寻址addr 通过段号在段表找到逻辑内存的段起始地址看段起始地址是否满足段大小限制不满足返回内存异常满足将逻辑地址加偏移量是物理地址。 段表 1.存储逻辑地址段段号到物理地址段号之间的映射关系 2.存储段大小起始地址 段表的建立操作系统在寻址前建立。 分页 分页地址空间 需要页号和页地址偏移。相比分段分页页帧大小固定不变。 可以划分物理内存至固定大小的帧将逻辑地址的页也划分至相同内存大小。大小是2的幂。 建立方案 页帧Frame物理内存被分割为大小相等的帧 一个内存物理地址是一个二元组f,o 物理地址 2^S*fo f是帧号F位2F个帧o是帧内偏移S位每帧2S字节, 页Page逻辑地址空间分割为大小相等的页 页内偏移大小 帧内偏移大小页帧大小和页大小一致 页号大小和帧号大小可能不一致 一个逻辑地址是一个二元组p,o 逻辑地址 2^S*po p:页号P位2P个页o页内偏移S位每页2S个字节 页寻址机制 CPU寻址逻辑地址逻辑地址包含两部分po首先把p页号作为索引再加上页表基址查页表pagetable中对应帧号物理地址中f知道帧号加上页内偏移就是物理地址fo。 页表以页号为索引的对应的帧号物理地址为此需要知道页表的基址位置页号从哪个地址开始查。 页表的建立操作系统初始化时enable分页机制前就需要建立好 分页与分段 分页相比分段分页页内存固定导致页内偏移大小范围是固定的。不需要想分段一样考虑分页大小不一致的问题。 逻辑地址和物理地址空间 1.总逻辑页大小和总物理帧大小不一致一般逻辑地址空间大于物理地址空间。 2.逻辑地址空间连续物理地址空间不连续。减少内外碎片。 页表 页表结构 页表是个数组索引是页号对应的数组项内容里有帧号。 分页机制性能问题 1.时间开销访问一个内存单元需要两次内存访问 页表不能放在CPU里只能放在内存里CPU先做内存寻址找页表基址再进行页表访问进行两次内存访问访问速度很慢 2空间代价页表占用空间 1.64位计算机每页1KB页表大小2^54个数的页表很大 2.多个程序有多个页表 解决方法 时间上缓存 ——快表TLBTranslation Look-aside Buffer TLB 位于CPU中的一块缓存区域存放常用的页号-帧号对采用关联内存的方式实现具有快速访问功能。 -CPU寻址时会先通过页号在TLB查找看是否存在页号的Key对应得到帧号进而得到物理地址减少对物理地址的访问。TLB未命中把该项更新到TLB中x86CPU这个过程是硬件完成对于mps是操作系统完成。 编写程序时把访问的地址写在一个页号里。 空间上间接访问多级页表机制以时间换空间 二级页表 对于逻辑地址p1,p2,o CPU寻址时先通过p1查找一级页表一级页表中存放的是二级页表的p2的起始地址再在二级页表对应起始地址查找偏移p2对应存放的就是帧号。提高时间开销但一级页表中不存在页表项就不需要占用二级页表项的内存节省空间。 多级页表 页号分为K个部分建立页表“树” 快表 快表又称联想寄存器(TLB) 是一种访问速度比内存快很多的高速缓冲存储器用来存放当前访问的若干页表项以加速地址变换的过程。与此对应内存中的页表常称为慢表。 地址变换过程访问一个逻辑地址的访存次数基本地址变换机构①算页号、页内偏移量 ②检查页号合法性 ③查页表找到页面存放的内存块号 ④根据内存块号与页内偏移量得到物理地址 ⑤访问目标内存单元两次访存具有快表的地址变换机构①算页号、页内偏移量 ②检查页号合法性 ③查快表。若命中即可知道页面存放的内存块号可直接进行⑤;若未命中则进行④ ④查页表找到页面存放的内存块号并且将页表项复制到快表中 ⑤根据内存块号与页内偏移量得到物理地址 ⑥访问目标内存单元快表命中只需一次访存 快表未命中需要两次访存 内存交换技术 交换(对换)技术的设计思想内存空间紧张时系统将内存中某些进程暂时换出外存把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度) 换入把准备好竞争CPU运行的程序从辅存移到内存。 换出把处于等待状态或CPU调度原则下被剥夺运行权力的程序从内存移到辅存把内存空间腾出来。 **交换时机**内存交换通常在许多进程运行且内存吃紧时进行而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页就说明内存紧张此时可以换出一些进程;如果缺页率明显下降就可以暂停换出。 关键点 交换需要备份存储通常是快速磁盘它必须足够大并且提供对这些内存映像的直接访问。为了有效使用CPU需要每个进程的执行时间比交换时间长而影响交换时间的主要是转移时间转移时间与所交换的空间内存成正比。如果换出进程比如确保该进程的内存空间成正比。交换空间通常作为磁盘的一整块且独立于文件系统因此使用就可能很快。交换通常在有许多进程运行且内存空间吃紧时开始启动而系统负荷降低就暂停。普通交换使用不多但交换的策略的某些变种在许多系统中如UNIX系统仍然发挥作用。 分页与分段的区别 段是信息的逻辑单位它是根据用户的需要划分的因此段对用户是可见的 页是信息的物理单位是为了管理主存的方便而划分的对用户是透明的段的大小不固定有它所完成的功能决定页大大小固定由系统决定段向用户提供二维地址空间页向用户提供的是一维地址空间段是信息的逻辑单位便于存储保护和信息的共享页的保护和共享受到限制。
3. 进程调度算法 进程调度算法详细介绍 选择一个进程运行这一功能是在操作系统中完成的通常称为调度程序scheduler。 调度时机 在进程的生命周期中当进程从一个运行状态到另外一状态变化的时候其实会触发一次调度。 比如以下状态的变化都会触发操作系统的调度 从就绪态 - 运行态当进程被创建时会进入到就绪队列操作系统会从就绪队列选择一个进程运行从运行态 - 阻塞态当进程发生 I/O 事件而阻塞时操作系统必须选择另外一个进程运行从运行态 - 结束态当进程退出结束后操作系统得从就绪队列选择另外一个进程运行 因为这些状态变化的时候操作系统需要考虑是否要让新的进程给 CPU 运行或者是否让当前进程从 CPU 上退出来而换另一个进程运行。 另外如果硬件时钟提供某个频率的周期性中断那么可以根据如何处理时钟中断 把调度算法分为两类 非抢占式调度算法挑选一个进程然后让该进程运行直到被阻塞或者直到该进程退出才会调用另外一个进程也就是说不会理时钟中断这个事情。抢占式调度算法挑选一个进程然后让该进程只运行某段时间如果在该时段结束时该进程仍然在运行时则会把它挂起接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理需要在时间间隔的末端发生时钟中断以便把 CPU 控制返回给调度程序进行调度也就是常说的时间片机制。 调度原则 CPU 利用率调度程序应确保 CPU 是始终匆忙的状态这可提高 CPU 的利用率系统吞吐量吞吐量表示的是单位时间内 CPU 完成进程的数量长作业的进程会占用较长的 CPU 资源因此会降低吞吐量相反短作业的进程会提升系统吞吐量周转时间周转时间是进程运行阻塞时间等待时间的总和一个进程的周转时间越小越好等待时间这个等待时间不是阻塞状态的时间而是进程处于就绪队列的时间等待的时间越长用户越不满意响应时间用户提交请求到系统第一次产生响应所花费的时间在交互式系统中响应时间是衡量调度算法好坏的主要标准。 调度算法 调度算法是指根据系统的资源分配策略所规定的资源分配算法。常用的调度算法有先来先服务调度算法、时间片轮转调度法、短作业优先调度算法、最短剩余时间优先、高响应比优先调度算法、优先级调度算法等等。 先来先服务调度算法 先来先服务调度算法是一种最简单的调度算法也称为先进先出或严格排队方案。当每个进程就绪后它加入就绪队列。当前正运行的进程停止执行选择在就绪队列中存在时间最长的进程运行。该算法既可以用于作业调度也可以用于进程调度。先来先服务比较适合于常作业进程而不利于段作业进程。 时间片轮转调度算法 时间片轮转调度算法主要适用于分时系统。在这种算法中系统将所有就绪进程按到达时间的先后次序排成一个队列进程调度程序总是选择就绪队列中第一个进程执行即先来先服务的原则但仅能运行一个时间片。 短作业优先调度算法 短作业优先调度算法是指对短作业优先调度的算法从后备队列中选择一个或若干个估计运行时间最短的作业将它们调入内存运行。 短作业优先调度算法是一个非抢占策略他的原则是下一次选择预计处理时间最短的进程因此短进程将会越过长作业跳至队列头。 最短剩余时间优先调度算法 最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下进程调度总是选择预期剩余时间最短的进程。当一个进程加入到就绪队列时他可能比当前运行的进程具有更短的剩余时间因此只要新进程就绪调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样调度程序正在执行选择函数是必须有关于处理时间的估计并且存在长进程饥饿的危险。 高响应比优先调度算法 高响应比优先调度算法主要用于作业调度该算法是对 先来先服务调度算法和短作业优先调度算法的一种综合平衡同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时先计算后备作业队列中每个作业的响应比从中选出响应比最高的作业投入运行。 优先级调度算法 优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业将它们调入内存分配必要的资源创建进程并放入就绪队列。在进程调度中优先级调度算法每次从就绪队列中选择优先级最高的进程将处理机分配给它使之投入运行。
4. 磁盘调度算法 磁盘调度算法详细介绍 常见的磁盘调度算法有 先来先服务算法最短寻道时间优先算法扫描算法循环扫描算法LOOK 与 C-LOOK 算法 先来先服务 先来先服务First-ComeFirst-ServedFCFS顾名思义先到来的请求先被服务。 最短寻道时间优先 最短寻道时间优先Shortest Seek FirstSSF算法的工作方式是优先选择从当前磁头位置所需寻道时间最短的请求 扫描算法 最短寻道时间优先算法会产生饥饿的原因在于磁头有可能再一个小区域内来回得移动。 为了防止这个问题可以规定磁头在一个方向上移动访问所有未完成的请求直到磁头到达该方向上的最后的磁道才调换方向这就是扫描*Scan*算法。 这种算法也叫做电梯算法比如电梯保持按一个方向移动直到在那个方向上没有请求为止然后改变方向。 循环扫描算法 扫描算法使得每个磁道响应的频率存在差异那么要优化这个问题的话可以总是按相同的方向进行扫描使得每个磁道的响应频率基本一致。 循环扫描Circular Scan, CSCAN 规定只有磁头朝某个特定方向移动时才处理磁道访问请求而返回时直接快速移动至最靠边缘的磁道也就是复位磁头这个过程是很快的并且返回中途不处理任何请求该算法的特点就是磁道只响应一个方向上的请求。 LOOK 与 C-LOOK算法 扫描算法和循环扫描算法都是磁头移动到磁盘「最始端或最末端」才开始调换方向。 那这其实是可以优化的优化的思路就是磁头在移动到「最远的请求」位置然后立即反向移动。 针对 SCAN 算法的优化叫 LOOK 算法它的工作方式磁头在每个方向上仅仅移动到最远的请求位置然后立即反向移动而不需要移动到磁盘的最始端或最末端反向移动的途中会响应请求。 针对C-SCAN 算法的优化叫 C-LOOK它的工作方式磁头在每个方向上仅仅移动到最远的请求位置然后立即反向移动而不需要移动到磁盘的最始端或最末端反向移动的途中不会响应请求。
5. 页面置换算法 页面置换算法详细介绍 请求调页也称按需调页即对不在内存中的“页”当进程执行时要用时才调入否则有可能到程序结束时也不会调入。而内存中给页面留的位置是有限的在内存中以帧为单位放置页面。为了防止请求调页的过程出现过多的内存页面错误即需要的页面当前不在内存中需要从硬盘中读数据也即需要做页面的替换而使得程序执行效率下降我们需要设计一些页面置换算法页面按照这些算法进行相互替换时可以尽量达到较低的错误率。常用的页面置换算法如下 先进先出置换算法FIFO 先进先出即淘汰最早调入的页面。 最佳置换算法OPT 选未来最远将使用的页淘汰是一种最优的方案可以证明缺页数最小。 最近最久未使用LRU算法 即选择最近最久未使用的页面予以淘汰 时钟Clock置换算法 时钟置换算法也叫最近未用算法 NRUNot RecentlyUsed。该算法为每个页面设置一位访问位将内存中的所有页面都通过链接指针链成一个循环队列。
6. 网络系统 什么是零拷贝 为了提高文件传输的性能于是就出现了零拷贝技术它通过一次系统调用sendfile 方法合并了磁盘读取与网络发送两个操作降低了上下文切换次数。另外拷贝数据都是发生在内核中的天然就降低了数据拷贝的次数。 Kafka 和 Nginx 都有实现零拷贝技术这将大大提高文件传输的性能。 零拷贝技术是基于 PageCache 的PageCache 会缓存最近访问的数据提升了访问缓存数据的性能同时为了解决机械硬盘寻址慢的问题它还协助 I/O 调度算法实现了 IO 合并与预读这也是顺序读比随机读性能好的原因。这些优势进一步提升了零拷贝的性能。 I/O多路复用 既然为每个请求分配一个进程/线程的方式不合适那有没有可能只使用一个进程来维护多个 Socket 呢答案是有的那就是 I/O 多路复用技术。 一个进程虽然任一时刻只能处理一个请求但是处理每个请求的事件时耗时控制在 1 毫秒以内这样 1 秒内就可以处理上千个请求把时间拉长来看多个请求复用了一个进程这就是多路复用这种思想很类似一个 CPU 并发多个进程所以也叫做时分多路复用。 我们熟悉的 select/poll/epoll 内核提供给用户态的多路复用系统调用进程可以通过一个系统调用函数从内核中获取多个事件。 select/poll/epoll 是如何获取网络事件的呢在获取事件时先把所有连接文件描述符传给内核再由内核返回产生了事件的连接然后在用户态中再处理这些连接对应的请求即可。 select/poll/epoll select 和 poll 并没有本质区别它们内部都是使用「线性结构」来存储进程关注的 Socket 集合。 在使用的时候首先需要把关注的 Socket 集合通过 select/poll 系统调用从用户态拷贝到内核态然后由内核检测事件当有网络事件产生时内核需要遍历进程关注 Socket 集合找到对应的 Socket并设置其状态为可读/可写然后把整个 Socket 集合从内核态拷贝到用户态用户态还要继续遍历整个 Socket 集合找到可读/可写的 Socket然后对其处理。 很明显发现select 和 poll 的缺陷在于当客户端越多也就是 Socket 集合越大Socket 集合的遍历和拷贝会带来很大的开销因此也很难应对 C10K。 epoll 是解决 C10K 问题的利器通过两个方面解决了 select/poll 的问题。 epoll 在内核里使用「红黑树」来关注进程所有待检测的 Socket红黑树是个高效的数据结构增删改一般时间复杂度是 O(logn)通过对这棵黑红树的管理不需要像 select/poll 在每次操作时都传入整个 Socket 集合减少了内核和用户空间大量的数据拷贝和内存分配。epoll 使用事件驱动的机制内核里维护了一个「链表」来记录就绪事件只将有事件发生的 Socket 集合传递给应用程序不需要像 select/poll 那样轮询扫描整个集合包含有和无事件的 Socket 大大提高了检测的效率。 而且epoll 支持边缘触发和水平触发的方式而 select/poll 只支持水平触发一般而言边缘触发的方式会比水平触发的效率高。 高性能网络模式Reactor和Proactor 常见的 Reactor 实现方案有三种。 第一种方案单 Reactor 单进程 / 线程不用考虑进程间通信以及数据同步的问题因此实现起来比较简单这种方案的缺陷在于无法充分利用多核 CPU而且处理业务逻辑的时间不能太长否则会延迟响应所以不适用于计算机密集型的场景适用于业务处理快速的场景比如 Redis6.0之前 采用的是单 Reactor 单进程的方案。 第二种方案单 Reactor 多线程通过多线程的方式解决了方案一的缺陷但它离高并发还差一点距离差在只有一个 Reactor 对象来承担所有事件的监听和响应而且只在主线程中运行在面对瞬间高并发的场景时容易成为性能的瓶颈的地方。 第三种方案多 Reactor 多进程 / 线程通过多个 Reactor 来解决了方案二的缺陷主 Reactor 只负责监听事件响应事件的工作交给了从 ReactorNetty 和 Memcache 都采用了「多 Reactor 多线程」的方案Nginx 则采用了类似于 「多 Reactor 多进程」的方案。 Reactor 可以理解为「来了事件操作系统通知应用进程让应用进程来处理」而 Proactor 可以理解为「来了事件操作系统来处理处理完再通知应用进程」。 因此真正的大杀器还是 Proactor它是采用异步 I/O 实现的异步网络模型感知的是已完成的读写事件而不需要像 Reactor 感知到事件后还需要调用 read 来从内核中获取数据。 不过无论是 Reactor还是 Proactor都是一种基于「事件分发」的网络编程模式区别在于 Reactor 模式是基于「待完成」的 I/O 事件而 Proactor 模式则是基于「已完成」的 I/O 事件。 一致性哈希介绍 一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上如果增加或者移除一个节点仅影响该节点在哈希环上顺时针相邻的后继节点其它数据也不会受到影响。 但是一致性哈希算法不能够均匀的分布节点会出现大量请求都集中在一个节点的情况在这种情况下进行容灾与扩容时容易出现雪崩的连锁反应。 为了解决一致性哈希算法不能够均匀的分布节点的问题就需要引入虚拟节点对一个真实节点做多个副本。不再将真实节点映射到哈希环上而是将虚拟节点映射到哈希环上并将虚拟节点映射到实际节点所以这里有「两层」映射关系。 引入虚拟节点后可以会提高节点的均衡度还会提高系统的稳定性。所以带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景而且适合节点规模会发生变化的场景。
7. 锁 什么是死锁和产生死锁原因 死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局当进程处于这种僵持状态时若无外力作用它们都将无法再向前推进。 如下图所示如果此时有一个线程 A已经持有了锁 A但是试图获取锁 B线程 B 持有锁 B而试图获取锁 A这种情况下就会产生死锁。 产生死锁原因 由于系统中存在一些不可剥夺资源而当两个或两个以上进程占有自身资源并请求对方资源时会导致每个进程都无法向前推进这就是死锁。 竞争资源 例如系统中只有一台打印机可供进程 A 使用假定 A 已占用了打印机若 B 继续要求打印机打印将被阻塞。 系统中的资源可以分为两类 可剥夺资源是指某进程在获得这类资源后该资源可以再被其他进程或系统剥夺CPU 和主存均属于可剥夺性资源不可剥夺资源当系统把这类资源分配给某进程后再不能强行收回只能在进程用完后自行释放如磁带机、打印机等。 进程推进顺序不当 例如进程 A 和 进程 B 互相等待对方的数据。 死锁产生的必要条件 互斥条件进程要求对所分配的资源进行排它性控制即在一段时间内某资源仅为一进程所占用。请求和保持条件当进程因请求资源而阻塞时对已获得的资源保持不放。不剥夺条件进程已获得的资源在未使用完之前不能剥夺只能在使用完时由自己释放。环路等待条件在发生死锁时必然存在一个进程–资源的环形链。 如何避免死锁 预防死锁、避免死锁、检测死锁、解除死锁 预防死锁 破坏请求条件一次性分配所有资源这样就不会再有请求了破坏请保持条件只要有一个资源得不到分配也不给这个进程分配其他的资源破坏不可剥夺条件当某进程获得了部分资源但得不到其它资源则释放已占有的资源破坏环路等待条件系统给每类资源赋予一个编号每一个进程按编号递增的顺序请求资源释放则相反。 解除死锁 资源剥夺挂起某些死锁进程并抢占它的资源将这些资源分配给其他死锁进程但应该防止被挂起的进程长时间得不到资源撤销进程强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源撤销的原则可以按进程优先级和撤销进程代价的高低进行进程回退让一个或多个进程回退到足以避免死锁的地步。进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息设置还原点。 什么是悲观锁、乐观锁 悲观锁做事比较悲观它认为多线程同时修改共享资源的概率比较高于是很容易出现冲突所以访问共享资源前先要上锁。 乐观锁做事比较乐观它假定冲突的概率很低它的工作方式是先修改完共享资源再验证这段时间内有没有发生冲突如果没有其他线程在修改资源那么操作完成如果发现有其他线程已经修改过这个资源就放弃本次操作。 可见乐观锁的心态是不管三七二十一先改了资源再说。另外你会发现乐观锁全程并没有加锁所以它也叫无锁编程。 互斥锁、自旋锁、读写锁都是属于悲观锁。 哲学家进餐问题 生产者-消费者问题描述 生产者在生成数据后放在一个缓冲区中消费者从缓冲区取出数据处理任何时刻只能有一个生产者或消费者可以访问缓冲区 我们对问题分析可以得出 任何时刻只能有一个线程操作缓冲区说明操作缓冲区是临界代码需要互斥缓冲区空时消费者必须等待生产者生成数据缓冲区满时生产者必须等待消费者取出数据。说明生产者和消费者需要同步。 那么我们需要三个信号量分别是 互斥信号量 mutex用于互斥访问缓冲区初始化值为 1资源信号量 fullBuffers用于消费者询问缓冲区是否有数据有数据则读取数据初始化值为 0表明缓冲区一开始为空资源信号量 emptyBuffers用于生产者询问缓冲区是否有空位有空位则生成数据初始化值为 n 缓冲区大小 如果消费者线程一开始执行 P(fullBuffers)由于信号量 fullBuffers 初始值为 0则此时 fullBuffers 的值从 0 变为 -1说明缓冲区里没有数据消费者只能等待。 接着轮到生产者执行 P(emptyBuffers)表示减少 1 个空槽如果当前没有其他生产者线程在临界区执行代码那么该生产者线程就可以把数据放到缓冲区放完后执行 V(fullBuffers) 信号量 fullBuffers 从 -1 变成 0表明有「消费者」线程正在阻塞等待数据于是阻塞等待的消费者线程会被唤醒。 消费者线程被唤醒后如果此时没有其他消费者线程在读数据那么就可以直接进入临界区从缓冲区读取数据。最后离开临界区后把空槽的个数 1。 生产者、消费者问题 哲学家就餐的问题描述 5 个老大哥哲学家闲着没事做围绕着一张圆桌吃面巧就巧在这个桌子只有 5 支叉子每两个哲学家之间放一支叉子哲学家围在一起先思考思考中途饿了就会想进餐这些哲学家要两支叉子才愿意吃面也就是需要拿到左右两边的叉子才进餐吃完后会把两支叉子放回原处继续思考 一、让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。 在 P 操作时根据哲学家的编号不同拿起左右两边叉子的顺序不同。另外V 操作是不需要分支的因为 V 操作是不会阻塞的。 二、用一个数组 state 来记录每一位哲学家的三个状态分别是在进餐状态、思考状态、饥饿状态正在试图拿叉子。 那么一个哲学家只有在两个邻居都没有进餐时才可以进入进餐状态。 上面的程序使用了一个信号量数组每个信号量对应一位哲学家这样在所需的叉子被占用时想进餐的哲学家就被阻塞。 读者写者问题 读者只会读取数据不会修改数据而写者即可以读也可以修改数据。 读者-写者的问题描述 「读-读」允许同一时刻允许多个读者同时读「读-写」互斥没有写者时读者才能读没有读者时写者才能写「写-写」互斥没有其他写者时写者才能写 使用信号量的方式来尝试解决 信号量 wMutex控制写操作的互斥信号量初始值为 1 读者计数 rCount正在进行读操作的读者个数初始化为 0信号量 rCountMutex控制对 rCount 读者计数器的互斥修改初始值为 1 这种实现是读者优先的策略因为只要有读者正在读的状态后来的读者都可以直接进入如果读者持续不断进入则写者会处于饥饿状态。 那既然有读者优先策略自然也有写者优先策略 只要有写者准备要写入写者应尽快执行写操作后来的读者就必须阻塞如果有写者持续不断写入则读者就处于饥饿 在方案一的基础上新增如下变量 信号量 rMutex控制读者进入的互斥信号量初始值为 1信号量 wDataMutex控制写者写操作的互斥信号量初始值为 1写者计数 wCount记录写者数量初始值为 0信号量 wCountMutex控制 wCount 互斥修改初始值为 1 注意这里 rMutex 的作用开始有多个读者读数据它们全部进入读者队列此时来了一个写者执行了 P(rMutex) 之后后续的读者由于阻塞在 rMutex 上都不能再进入读者队列而写者到来则可以全部进入写者队列因此保证了写者优先。 同时第一个写者执行了 P(rMutex) 之后也不能马上开始写必须等到所有进入读者队列的读者都执行完读操作通过 V(wDataMutex) 唤醒写者的写操作。 既然读者优先策略和写者优先策略都会造成饥饿的现象那么我们就来实现一下公平策略。 公平策略 优先级相同写者、读者互斥访问只能一个写者访问临界区可以有多个读者同时访问临界资源
8. 操作系统知识点 对并发和并行的理解 并行是指两个或者多个事件在同一时刻发生而并发是指两个或多个事件在同一时间间隔发生并行是在不同实体上的多个事件并发是在同一实体上的多个事件 什么是用户态和内核态 用户态和内核态是操作系统的两种运行状态。 内核态处于内核态的 CPU 可以访问任意的数据包括外围设备比如网卡、硬盘等处于内核态的 CPU 可以从一个程序切换到另外一个程序并且占用 CPU 不会发生抢占情况一般处于特权级 0 的状态我们称之为内核态。用户态处于用户态的 CPU 只能受限的访问内存并且不允许访问外围设备用户态下的 CPU 不允许独占也就是说 CPU 能够被其他程序获取。 两大局部性原理是什么 主要分为时间局部性和空间局部性。 **时间局部性:**如果执行了程序中的某条指令那么不久后这条指令很有可能再次执行;如果某个数据被访问过不久之后该数据很可能再次被访问。(因为程序中存在大量的循环) **空间局部性:**一旦程序访问了某个存储单元在不久之后其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的并且程序的指令也是顺序地在内存中存放的) 异常和中断是什么有什么区别 中断 当我们在敲击键盘的同时就会产生中断当硬盘读写完数据之后也会产生中断所以我们需要知道中断是由硬件设备产生的而它们从物理上说就是电信号之后它们通过中断控制器发送给CPU接着CPU判断收到的中断来自于哪个硬件设备这定义在内核中最后由CPU发送给内核有内核处理中断。 异常 CPU处理程序的时候一旦程序不在内存中会产生缺页异常当运行除法程序时当除数为0时又会产生除0异常。所以大家也需要记住的是异常是由CPU产生的同时它会发送给内核要求内核处理这些异常。 相同点 最后都是由CPU发送给内核由内核去处理处理程序的流程设计上是相似的 不同点 产生源不相同异常是由CPU产生的而中断是由硬件设备产生的内核需要根据是异常还是中断调用不同的处理程序中断不是时钟同步的这意味着中断可能随时到来异常由于是CPU产生的所以它是时钟同步的当处理中断时处于中断上下文中处理异常时处于进程上下文中 原子操作 **处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。**首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存中读取或者写入一个字节是原子的意思是当一个处理器读取一个字节时其他处理器不能访问这个字节的内存地址。Pentium 6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的但是复杂的内存操作处理器是不能自动保证其原子性的比如跨总线宽度、跨多个缓存行和跨页表的访问。但是处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。 1使用总线锁保证原子性 第一个机制是通过总线锁保证原子性。 所谓总线锁就是使用处理器提供的一个LOCK信号当一个处理器在总线上输出此信号时其他处理器的请求将被阻塞住那么该处理器可以独占共享内存。 2使用缓存锁保证原子性 第二个机制是通过缓存锁定来保证原子性。 服务器高并发解决方案 应用数据与静态资源分离 将静态资源图片视频jscss等单独保存到专门的静态资源服务器中在客户端访问的时候从静态资源服务器中返回静态资源从主服务器中返回应用数据。客户端缓存 因为效率最高消耗资源最小的就是纯静态的html页面所以可以把网站上的页面尽可能用静态的来实现在页面过期或者有数据更新之后再将页面重新缓存。或者先生成静态页面然后用ajax异步请求获取动态数据。集群和分布式 集群是所有的服务器都有相同的功能请求哪台都可以主要起分流作用 分布式是将不同的业务放到不同的服务器中处理一个请求可能需要使用到多台服务器起到加快请求处理的速度。 可以使用服务器集群和分布式架构使得原本属于一个服务器的计算压力分散到多个服务器上。同时加快请求处理的速度。反向代理 在访问服务器的时候服务器通过别的服务器获取资源或结果返回给客户端。 抖动你知道是什么吗它也叫颠簸现象 刚刚换出的页面马上又要换入内存刚刚换入的页面马上又要换出外存这种频繁的页面调度行为称为抖动或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够) 为进程分配的物理块太少会使进程发生抖动现象。为进程分配的物理块太多又会降低系统整体的并发度降低某些资源的利用率 为了研究为应该为每个进程分配多少个物理块Denning 提出了进程工作集” 的概念
