Conzxy's blog

Fix Bug for lab2 在切换到lab3分支后，出现了lab2没有的bug1234$ make qemu....kernel panic at kern/pmap.c:163: PADDR called with invalid kva 00000000....根据错误信息，不难找到出问题的代码在哪：1kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;通过在该行前加入一些代码输出地址信息： 1234567kern_pgdir = (pde_t *) boot_alloc(PGSIZE); cprintf("kern_padir: %08x\n", kern_pgdir);memset(kern_pgdir, 0, PGSIZE);cprintf("kern_padir: %08x\n", kern_pgdir); 然后再运行下会得到：12kern_padir: f018f000kern_padir: 00000000 // ????十分迷惑，好像memset()写错了位 ...

rbtree的总体设计 STL的rbtree为了可以快速索取到有序序列的最小值和最大值，用到了header，它的left指向最小元素，right指向最大元素，而根节点也是通过它来获取：建立parent链接，更进一步地了识别这种特殊节点，建立特殊的关系：互为parent，整个树只有这两个节点有这样的特性，为了区别root和header，设置header颜色为红。除此之外，header还维护总结点数，即size，为了可以O(1)获取。header在逻辑上是value无法访问的节点，因此适合做end()，在逻辑上它是“最大值”，最大元素通过operator++应该得到header。1234struct RBTreeHeader { RBTreeBaseNode header; // see next section std::size_t node_count;};起初，没有节点的时候，header需要设置初始状态，我们令left和right都指向自身（这个对于insert处理有用），而parent设置为NULL rbtree节点的设计为了使得所有模板实例都可以共享相同 ...

half-close what只断开output，并可以继续读取peer发来的数据 whyhalf-close是一种很方便告诉对方“我已经发完数据”的手段通常用于client，这样server在处理完数据后可以立马关闭该连接（节约资源） In kanon

析构和多线程 鉴于C++没有（原生）垃圾回收机制，因此析构的race condition需要程序员来考虑 析构函数不需要锁来保证线程安全析构函数不能用锁来保护，原因有： 1）基类与派生类的析构函数是割裂的，因此必然无法保证线程安全 2）安全的析构原则上只有其他线程都不用它时才是安全的，即成为“垃圾”时 这个结论较为显而易见 析构函数的race condition析构函数有几个竞态条件： 1）析构的时候，是否有其他线程正在调用其成员函数 2）调用成员函数期间，其他线程是否正在析构其对象 3）在调用成员函数前，如何知道其是否存活 4）其他race condition 正如前面所说，如果有类似GC的机制就会好办很多 因此我们可以采取std::shared_ptr来解决1），2），而与std::weak_ptr组合成的弱回调（weak callback）可以解决3） 1）如果存在其他线程正在调用其成员函数，那么它的引用计数至少为1，不可能在析构 2）与1）同理，在调用成员函数期间，其他线程不可能正在析构其对象 3）通过std::weak_ptr的lock()原子提升为std::shared_p ...

并发排序在《APUE》中pthread_barrier处有一个例子是开8个线程对80万个元素进行排序，这是我第一次接触并发算法，感觉很有趣于是记录一下。思路是这样的：每个线程对“待排序元素个数/线程数”个元素进行进行排序（局部排序），然后最后通过一个合并算法来统合所有元素。算法如下：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869template< std::size_t numthread = 1, typename RI1, typename RI2, typename BinaryPred, typename V = typename std::iterator_traits<RI1>::value_type >void merge_impl(RI1 first1, RI1 last1, RI2 first2, BinaryPred pred)& ...

代理类这里提到的代理类是指《C++ 沉思录》中提到的surrogate类，而不是设计模式proxy 代理类在书中是用来解决两个问题的： 动态内存管理(double free) 如何将多态类型塞进容器(new base-type(…) “slice down”) 而通过代理类保存指向基类的指针并由派生类实现虚拷贝函数可以完美解决上述两个问题123Vehicle* parking_lot[1000]; //由于Vehicle会出现slice现象，所以用指针Automobile x=/*...*/parking_lot[num_vehicles++]=new Automobile(x); 这个代码就有前面所说的两个问题： 如果要让parking_lot[p]指向一个新建的Vehicle，且这个Vehicle的类型和值与parking_lot[q]相同，会如何？ 1234567891011if(p != q){ delete parking_lot[p]; parking_lot[p]=parking_lot[q]; //会导致double free}if ...

逆波兰表达式有一个自定义类型Query类，它可以实现搜索指定字符串的对应行并输出，同时支持&，|和~运算，于是我想通过用户输入字符串从而实现组合运算（包含括号），这时想起了逆波兰表达式 首先明确用户输入的是中缀表示式，但是中缀表达式是适用于人思考运算的，因为需要顾前顾后，但是计算机难以解读（因为一般是从左向右解析字符串的），并且需要考虑括号，而逆波兰表达式可以没有括号并且考虑了运算符优先级 一个简单的栗子：$1+(2+3) \times 5$=>$1 2 3 + 5 \times +$ 逆波兰表达式如何运算：从左到右依次压栈，遇到运算符，取出栈顶两个操作数进行运算再放回去 ，最后输出栈顶 中缀转后缀转化规则如下： （：push ）：）不push，pop栈顶直到遇到（或栈空 运算符：pop优先级>=当前运算符的元素直到遇到（或栈空 运算元：不push直接输出 空格：直接跳过 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 ...

归并排序归并排序采用分治策略 分：从q分开成$A[1…q]$和$A[q+1…n]$两个子序列 治：子序列递归执行归并排序 合：将子序列执行的结果组合在一起 归并排序与快排不同的在于关键步骤不同 快排是“分”下了功夫，而归并是“合”做了处理 在“治”之后，两个子序列都是有序的，我们设想有一个output pile而两个子序列是一个从小到大的pile， 我们从上面开始一一比较，将较小者假如output pile，然后有一组先取完，另一组的是除output pile中外最大的元素且有序，因此直接放入即可 这就给了归并排序“合”的灵感 递归伪码123456MERGESORT(A,p,r)if p < q q ← floor[(r-p)/2] MERGESORT(A,p,q) MERGESORT(A,q+1,r) MERGE(A,p,q,r) 根据上面所说栗子得到的启示：$A[p…q]$的元素注入$L[1…n_1+1]$，其中$n_1=Length(A[p…q])$，$A[q+1…r]$的元素注入$R[1…n_2+1]$，其中$n_2=Length(A[q+1…r])$,这两个序列都 ...

冒泡排序冒泡排序的思想就是相邻交换从而将最小元素浮上来，达到“冒泡”的效果 这里我们也可以划分已排序区域和未排序区域，已经“冒泡”的就是已经排序的，我们要做的是将未排序区域中的最小元素浮上来 12345BUBBLE-SORT(A)for i ← 1 to n do for j ← n-1 down to i do if A[j+1] < A[j] then swapped with A[j+1] and A[j] 算法正确性循环不变式为 $A[0…i-1]$已排序 初始：该区间没有元素 维持：假设$A[0…i-1]$已排序，注意第二层循环，$j$是从$n-1$一直往$i$移动，若$j+1$比$j$小，则交换元素，因此$A[i]$一定是$A[i…n]$的最小值，因此$A[0…i]$为已排序序列，再$i$自增，循环不变式维持 终止：此时，$i=n$，$A[0…n-1]$排序完成，而$A[n]$是$A[1…n]$的最大元素，$A[1…n]$排序完成 时间复杂度由嵌套for循环，显然为$O(n^2)$

选择排序选择排序和插入排序类似，也是分为已排序区域和未排序区域 插入排序是把key插入到已排序区域中合适的位置，使得已排序区域增长 而选择排序是将未排序区域中最小的元素放在第一个位置，来使得已排序区域增长 伪码如下： 123456789SELECTION-SORT(A)for i ← 1 to n do minIndex ← i for j ← i+1 to n do if A[j] < A[minIndex] then minIndex ← j end forend for swapped with A[i] and A[minIndex] C++代码： 12345678910void SelectionSort(vector<int> &arr){ for(int i=0;i < arr.size();++i){ int minIndex=i; for(int j=i+1;j < arr.size();++j){ if(arr[minIndex] &g ...