操作系统基础37-请求调页的性能

2020-12-29 01:08·重学IT的老猫

请求调页可以显著影响计算机系统的性能。为了说明起见，下面计算一下请求调页内存的有效访问时间。 对大多数计算机系统而言，内存访问时间(用ma表示)的范围为10〜200ns。只要没有出现缺页错误，有效访问时间就等于内存访问时间。然而，如果出现缺页错误，那么就应先从磁盘中读入相关页面，再访问所需要的字。 设 p 为缺页错误的概率(0≤p≤1)。希望p接近于0，即缺页错误很少。那么有效访问时间为：

操作系统基础36-请求页面调度概念

2020-12-28 10:54·重学IT的老猫

如何从磁盘加载可执行程序到内存? 一种选择是在程序执行时将整个程序加载到物理内存，这种方法的问题是最初可能不需要整个程序都处于内存。假设程序开始时带有一组用户可选的选项。加载整个程序会导致所有选项的执行代码都加载到内存中，而不管这些选项是否最终使用。 另一种策略是仅在需要时才加载页面。这种技术被称为请求调页，常常用于虚拟内存系统。对于请求调页的虚拟内存，页面只有在程序执行期间被请求时才被加载。因此，从未访问的那些页从不加载到物理内存中。 请求调页系统类似于具有交换的分页系统，如下图所示，这里进程驻留在外存上（通常为磁盘）。当进程需要执行时，它被交换到内存中。不过，不是将整个进程交换到内存中，而是采用惰性交换器。惰性交换器除非需要某个页面，否则从不将它交换到内存中。

操作系统基础35-什么是虚拟内存

2020-12-27 15:32·重学IT的老猫

分页，分段这些策略都有相同的目标，就是同时将多个进程保存在内存中，以便允许多道程序。然而，这些策略都倾向于要求每个进程在执行之前应完全处于内存中。

操作系统基础34-页表结构

2020-12-24 13:01·重学IT的老猫

下面将探讨组织页表的一些最常用技术，包括分层分页、哈希页表和倒置页表。

分层分页

大多数现代计算机系统支持大逻辑地址空间（2^32〜2^64）。在这种情况下，页表本身可以非常大。例如，假设具有 32 位逻辑地址空间的一个计算机系统。如果系统的页大小为4KB（2^12），那么页表可以多达 100万的条目（2^32/2^12）。假设每个条目有4字节，那么每个进程需要4MB 物理地址空间来存储页表本身。显然，我们并不想在内存中连续地分配这个页表。这个问题的一个简单解决方法是将页表划分为更小的块。完成这种划分有多个方法。

操作系统基础33-内存管理-分页

2020-12-21 12:10·重学IT的老猫

分段允许进程的物理地址空间是非连续的。分页是提供这种优势的另一种内存管理方案。然而，分页避免了外部碎片和紧缩，而分段不可以。分页还避免了将不同大小的内存块匹配到交换空间的问题，在分页引入之前采用的内存管理方案都有这个问题。由于比早期方法更加优越，各种形式的分页为大多数操作系统采用，包括大型机的和智能手机的操作系统。实现分页需要操作系统和计算机硬件的协作。

操作系统基础32-内存管理-分段

2020-12-20 03:27·重学IT的老猫

通过前面的学习我们知道，用户的内存视图与实际的物理内存不一样。这同样适用于程序员的内存视图。

事实上，对操作系统和程序员来说，按物理性质来处理内存是不方便的。如果硬件可以提供内存机制，以便将程序员的内存视图映射到实际的物理内存，系统将有更多的自由来管理内存，而程序员将有一个更自然的编程环境。分段提供了这种机制。

操作系统基础31-连续内存分配

2020-12-19 03:40·重学IT的老猫

内存应容纳操作系统和各种用户进程，因此应该尽可能有效地分配内存。下面介绍一种早期方法：连续内存分配。 内存通常分为两个区域：一个用于驻留操作系统，另一个用于用户进程。操作系统可以放在低内存，也可放在高内存，这取决于中断向量的位置。由于中断向量通常位于低内存，因此程序员通常将操作系统也放在低内存。因此，这里只讨论操作系统位于低内存的情况，其他情况的讨论也类似。 通常，我们需要将多个进程同时放在内存中。因此我们需要考虑，如何为输入队列中需要调入内存的进程分配内存空间。在采用连续内存分配时，每个进程位于一个连续的内存区域，与包含下一个进程的内存相连。

首发于技术猫开源俱乐部

HyperLogLog 算法详解

Abser Ari

基数计数基本概念

概率算法

实际上目前还没有发现更好的在大数据场景中准确计算基数的高效算法，因此在不追求绝对准确的情况下，使用概率算法算是一个不错的解决方案。概率算法不直接存储数据集合本身，通过一定的概率统计方法预估基数值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括: