MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} }); 动态规划方法通常是用来求解最优化问题(optimization problem)。比起分治方法，动态规划对于子问题只求解一次，算是用空间换时间。 书中提到了设计动态规划算法的4个步骤： 刻画一个最优解的结构特此 递归地定义最优解的值 计算最优解的值，通常采用自底向上的方法 利用计算出的信息构造一个最优解     Continue Reading

Malloc Lab，据说是最难的一个lab。在看完第九章之后，因为要旅游，没有直接做lab，而是继续看书，结果回来了，书还剩1章，又顺势看完了剩余的部分。在整本书都读完了以后，才回过头来做Malloc Lab。 介绍需要完成mm.c里的内容，材料中需要完成的是 int mm_init(void) void *mm_malloc(size_t size) void mm_free(void *ptr) 其他的mm_realloc源码中已经填写好了。 这里，我是用书中的隐式空闲链表方法，先完成实验。     Continue Reading

这个实验是要实现一个简易的shell程序，主要考虑的是异常和信号的处理。 前期工作解压缩shlab-handout.tar，执行make clean | make,就可以得到编译好的文件。 文件夹中的tshref是正确的结果，可以用来验证。与其用 ./sdriver.pl -t trace01.txt -s ./tsh -a "-p" 来测试，我觉得实验手册里提到的另一种方法更好用， make test01 这是对自己写的tsh进行测试，要想对tshref进行测试，只需要在后面的test前面添加一个r即可，也就是make rtest01。     Continue Reading

MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} }); Lab4 的Cache Lab 的说明资料太少了，csim.c 里面空空的，惊了。身为弱渣的我只好先拿别人的代码来参考参考。这里选取的代码csim.c。 Part A: Writing a Cache Simulator需要些一个Cache模拟器，将 valgrind 内存访问记录作为参数，模拟是否命中缓存。输出命中，不命中，移除。 lab里提供了一个写好的程序 csim-ref ，使用LRU(least-recently used)替换原则，模拟缓存命中情况。 实验指导上给出了命令行参数 Usage: ./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile> -h: Optional help flag that prints usage info -v: Optional verbose flag that displays trace info -s <s>: Number of set index bits ($ S = 2^{s} $ is the number of sets) -E <E>: Associativity (number of lines per set) -b <b>: Number of block bits ($ B = 2^{b} $ is the block size) -t <tracefile>: Name of the valgrind trace to replay 所以在 csim.c 里也可以写个打印帮助的函数 void printUsage(){ printf("Usage: ./csim [-h] [-v] -s <s> -E <E> -b <b> -t <tracefile>\n"); printf("-s: number of set index(2^s sets)\n"); printf("-E: number of lines per set\n"); printf("-b: number of block offset bits\n"); printf("-t: trace file name\n"); }     Continue Reading

MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} }); Coursera 上的Machine Learning 算得上是经典的机器学习入门课程，是由Andrew Ng大牛上的课。出于对机器学习的好奇，打算用Python来完成这门课的学习。 Supervised learning 监督学习这里存在两种问题 regression 和 classification。前者是预测相关的问题，后者是分类相关的问题。 首先介绍的是监督学习，notes1中用房屋价格预测来介绍Linear Regression线性回归。这里因为没有数据集，所以我选择用ex1中的ex1data1.txt来做演示。 import matplotlib.pyplot as plt import numpy as np data = np.loadtxt('ex1data1.txt', delimiter=',') m = data.shape[0] X = data[:,0] y = data[:, 1] plt.scatter(X, y, c='r', marker='x', linewidths=1) plt.xlim([3, max(X)+3]) plt.ylabel('Profit in $10,000s') plt.xlabel('Population of City in 10,000s') plt.show() 可以画出数据分布散点图。     Continue Reading

Python2.7中有两个常用的多线程库Multiprocessing，Threading。在Python中，线程和进程的区别在于线程模块使用线程，进程模块使用进程233，不开玩笑，这是StackOverFlow上的解释。说重点，线程使用相同的内存空间，而进程使用不同的。这也就让进程之间传对象稍有点困难。当然，由于线程共享内存空间，那么必须要考虑线程安全。 threadthread算是轻量级的线程模块，它提供较为底层的多线程实现方案。使用start_new_thread(function, args[, kwargs])实现线程。使用allocate_lock()可以得到一个锁对象，用acquire()和release()来加锁和释放锁，用locked()来判断释放有锁。一把锁只能被一个线程得到，所以利用锁可以避免多个线程对同一资源的同时操作。     Continue Reading

从小到大，之前都没去过北京。一是对故宫长城并没有什么兴趣(毕竟只对吃感兴趣括弧笑)，二是总觉得北京那算是大都市，自己还是太Low了。机缘巧合，得到了张WOT 2016的票，再三犹豫之后还是毅然决定踏上旅程。唉，还是准备不重复，当初还以为北京的火车票应该不是那么难买，结果就先买了去的车票，几天以后才买回程的票，结果因为买迟了，足足少在北京玩2个小时。     Continue Reading

首先，使用tar xvf命令解压文件后，会有3个可执行的二进制文件bufbomb，hex2raw，makecookie。参考write-up。 Level 0Bufbomb程序运行会读一个字符串，使用一下函数getbuf: /* Buffer size for getbuf */ #define NORMAL_BUFFER_SIZE 32 int getbuf() { char buf[NORMAL_BUFFER_SIZE]; Gets(buf); return 1; } Gets函数和标准库的gets功能比较相似，是读取字符串。因为Gets没有办法判断是否buf足够大，所以要用一个函数去判断长度是否小于32。将字符串传入getbuf函数中，若字符串小于32，则返回1. 080491f4 <getbuf>: 80491f4: 55 push %ebp 80491f5: 89 e5 mov %esp,%ebp 80491f7: 83 ec 38 sub $0x38,%esp 80491fa: 8d 45 d8 lea -0x28(%ebp),%eax 80491fd: 89 04 24 mov %eax,(%esp) 8049200: e8 f5 fa ff ff call 8048cfa <Gets> 8049205: b8 01 00 00 00 mov $0x1,%eax 804920a: c9 leave 804920b: c3 ret getbuf是由函数test调用: void test() { int val; /* Put canary on stack to detect possiblecorruption */ volatile int local = uniqueval(); val = getbuf(); /* Check for corruption stack */ if (local != uniqueval()) { printf("Sabotaged!: the stack has beencorrupted\n"); } else if (val == cookie) { printf("Boom!: getbuf returned0x%x\n", val); validate(3); } else { printf("Dud: getbuf returned0x%x\n", val); } } 其中，Smoke源码： void smoke(){ puts("Smoke!: You calledsmoke()"); validate(0); exit(0); } level 0 的任务是让getbuf在执行后返回时，执行smoke函数，而不是返回test函数中。     Continue Reading

因为学习操作系统，因为还有一些其他事情要做，所以没有直接上MIT 6.828,选择了清华的操作系统课和配套的ucore。     Continue Reading

最近被老师带着搞科研，研究CSI(channel state information)。 环境安装需要用到CSI tool，这是一个运行在Ubuntu上的利用Intel Wi-Fi Wireless Link 5300 802.11n来做分析的程序。这里可以使用作者网站中方法来安装，也可以下载清华的版本。清华的版本附带了安装说明书，参考说明书上的方法，安装即可。 需要注意的是，发射源路由器需要选择单天线支持802.11n的路由器，我使用的是TP-LINK TL-WR742N。 获取数据cd进入csitools文件夹，进入linux-80211n-csitool-supplementary/netlink，运行 sudo ./log_to_file tmp.dat 打开另一个终端，运行 ping 192.168.1.1 -i 0.2 netlink文件夹中的tmp.dat就是采集的原始数据。 读取数据使用Matlab读取数据，进入linux-80211n-csitool-supplementary/matlab文件夹，使用read_bf_file函数可以读取数据。 一个例子数据包里包含 timestamp_low: 4 (In the sample trace, timestamp_low is invalid and always 4.) bfee_count: 72 Nrx: 3 Ntx: 1 rssi_a: 33 rssi_b: 37 rssi_c: 41 noise: -127 agc: 38 perm: [3 2 1] rate: 256 csi: [1x3x30 double] 其中: timestamp_low 是时间戳 bfee_count 数据包数量 Nrx,Ntx 分别表示接收端和发送端的天线数量 rssi_a, rssi_b, rssi_c 每个天线的RSSI数据，单位dB， agc Automatic Gain Control perm NIC重排列后的顺序结果，代表RF链路的顺序 rate 发送包的rate csi CSI原始数据，是个Ntx×Nrx×30复数矩阵 主要提取出CSI数据和timestamp_low。     Continue Reading