/assets/images/avatar.jpeg

Harry's Space

Linux 系统 I/O 模型及 select/poll/epoll 详解

基本概念说明

理解Linux的IO模型之前,首先要了解一些基本概念,才能理解这些IO模型设计的依据

用户空间和内核空间

操作系统使用虚拟内存来映射物理内存,对于32位的操作系统来说,虚拟地址空间为4G(2^32)。操作系统的核心是内核,为了保护用户进程不能直接操作内核,保证内核安全,操作系统将虚拟地址空间划分为内核空间和用户空间。内核可以访问全部的地址空间,拥有访问底层硬件设备的权限,普通的应用程序需要访问硬件设备必须通过系统调用来实现。

算法(7): 动态规划

  • 动态规划的关键思想在于将问题转换成较小的子问题,然后根据子问题的结果总结出一个状态转移方程,最后得到整个问题的解

7.1 打家劫舍

LeetCode No.198

问题描述:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。

算法(6): 贪心算法

分治的思想为将大问题分解为子问题,子问题再分解为更小的子问题,直到不能再拆分,然后再合并子问题的结果,通常需要用到递归。关键是要找对如何拆解问题。

算法(4): 搜索

3.1 深度优先DFS

问题1:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 https://upload-images.jianshu.io/upload_images/14151453-d06c5120f4a6ffc0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240 Input: “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]