Linux的内存回收机制？用了什么数据结构？

Linux的内存回收机制主要包括页面置换（Page Replacement）和内存压缩（Memory Compression）两种机制。

页面置换是指将占用内存的页面（Page）从内存中置换出去，以便为需要更多内存的进程腾出空间。Linux内核通过缺页异常（Page Fault）机制来实现页面置换。当一个进程请求访问一个不在内存中的页面时，CPU会产生一次缺页异常，内核就会根据其页面置换算法来决定哪些页面需要置换出去。常见的页面置换算法包括FIFO、LRU、CLOCK等。

内存压缩是指将进程占用的内存中的一些空间压缩，以腾出更多的内存空间。Linux内核采用的是Zswap和Zram两种内存压缩方式。Zswap是将压缩后的页面存储在一个特殊的压缩池中，Zram则是将页面压缩后存储在一个虚拟的块设备上。当需要使用压缩后的页面时，内核会将其解压缩后再写回到内存中。

Linux内核在页面置换和内存压缩过程中使用了多种数据结构，包括双向链表、红黑树、哈希表等。例如，在页面置换算法中，LRU算法使用了双向链表和哈希表，用于维护页面的使用顺序和快速查找某个页面是否在内存中；CLOCK算法则使用了循环链表和红黑树，用于维护页面的访问情况和快速查找某个页面是否需要置换。在Zswap和Zram中，内核使用了LZO、LZ4等压缩算法来对页面进行压缩。