1. kmalloc：

• 不清零获得的内存，分配的区在物理内存中连续；void *kmalloc(size_t size, int flags);size为分配块的大小，flags为分配标志；
• flags：GFP_KERNEL 分配代表运行在内核空间的进程进行，意味着调用函数代表一个进程执行一个系统调用，能够使当前进程在少内存情况下睡眠等待一页；内部通过调用__get_free_pages进行；
• 如果一个模块需要分配大块内存，最好使用面向页的技术；__get_free_page(unsigned int flags);返回一个指向新页的指针，不清零该页；
• flags：GFP_ATOMIC kmalloc从一个进程上下文外部调用时，当前进程不被睡眠，内核试图保持一些空闲页满足原子的分配；
• Linux内核内存区：支持DMA操作内存区、普通内存、高端内存；
• 支持DMA操作内存区位于一个优先的地址范围，外设可以在此进行DMA存取，大部分健全平台，所有内存都在该区，在x86，DMA区在RAM的
• 前16MB。
• kmalloc和__get_free_pages返回的内存地址是虚拟地址，实际物理地址寻址仍然由MMU管理；

1. 并发和竞争

• 实际产生竞争的情况

if (!dptr -> data[s_pos]) {
              dptr -> data[s_ops] = kmalloc(quantum, GFP_KERNEL);
              if (!dptr -> data[s_pos])
                   goto out;
         }

• 假设两个进程（A，B）独立地试图写入同一个设备的相同偏移，进程同时到达if测试，如果被测试指针为NULL，每个进程都会决定分配内存且复制给dptr -> data[s_ops]，显然只会有一个赋值可以成功；
• 如果A先赋值，则将被B覆盖，结果指针指向B分配的内存，而A分配的内存被丢掉，但是并没有返回给系统，产生了内存泄漏；
• 并发源：多个用户空间进程的运行；SMP系统能够同时在多个处理器上执行代码；内核代码抢占，驱动代码可能在任何时间失去处理器；设备中断，内核中延迟代码执行的机制等；
• 竞争来自对资源的共享存取，驱动设计时，应该避免共享的资源，比如全局变量的使用；

1. 驱动编写策略：

• 编写内核代码存取硬件，但是不能强加不同策略给用户；驱动应该做到使硬件可用，将所有关于如何使用硬件的事情交给应用程序；
• 单个设备可能由不同程序并发使用，驱动有完全自由决定如何处理并发性；

Maximal Rectangle

• 给一个二维数组，用0，1填充，找出包含1的矩形的最大面积。

思路

• 开始想到的思路是，比较好的时间复杂度应该是n方，动态规划（似乎看到二维数组，首先就想到DP，估计跟最近做的几个二维DP的题目有关，还是得好好总结，建立方法论）。即f[i][j]纪录以matrix[i][j]为右下顶点的矩形的最大面积。但是这样出现了一个问题，到f[i][j]的转移方程没法写，无法从f[i-1][j]/f[i][j-1]得到，思维还是存在漏洞。
• 正确思路：这个题目应该跟一维数组时，求最大能够容纳的水容量，或者是两根柱子组成的面积最大，连续整数的最大长度这些题一个类型，只是把数组从一维变成了二维。这样的话，按照原来两遍夹逼的思路。两个全局的数组L，R，对每一列都适用，即纪录当前行位置，第j列的最大允许的左边界以及右边界。两个局部的指针left，right，纪录当前行每个位置的左边界与右边界。并且通过left与right去更新L，R数组。

First Missing Positive

• 给一个未排序的整形数组，找出缺失的第一个正整数。算法需要满足O(n)的时间复杂度以及使用恒定的空间。
• 输入：A[] = {1, 2, 0}, n = 3 return 3.
• 输出：A[] = {3, 4, -1, 1}, n = 4 return 2.