CSAPP Data Lab 思路和笔记

Data Lab[Updated 11/2/18]

11/2/18 新鲜出炉的 Data Lab,不同时期的 lab 内容会不一样。

肝了两天还是没有全部做出来,之前很以为很简单呢(

最近也终于买了 CS:APP3e 英文版,配合 CMU 的课程视频食用更佳。顺便可以练习英语听力和阅读,阅读已经可以流畅了,这种英文书基本看得懂,但是听力就不行(

解题的思路一般会写在注释里的。

bitXor

/*s
 * bitXor - x^y using only ~ and &
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  // 德摩根定律
  // a xor b = (~a | ~b) & (a | b)
  // = ~(a & b) & ~(~a & ~b)
  return ~(~x & ~y) & ~(x & y);
}

虽然这题比较简单,但我还是想了好久。主要是我把这个德摩根定律忘得差不多了,记得在离散数学里讲过。

利用的性质主要是:

  • a ^ b = (~a | ~b) & (a | b)
  • (~a | ~b) = ~(a & b)

阅读全文

Spring Boot项目部署之开启HTTPS

迫于课设,完成了对 LightBlog 的重构,使用 Spring Boot 和 SSM 框架,今晚突然想要支持一下 HTTPS(小绿锁)。 差不多折腾了一小时,现在使用的是下面这种方案(又不是

阅读全文

【Spring 揭秘(二)】Spring AOP

术语

术语不是为了限制你的设计,而是借此可以更方便的讨论和思考这个问题。这是我早上在《游戏设计要则探秘》上看的一句话,当然术语也不能华而不实,最好做到顾名思义或指出本质。

在使用 AOP 之前,我们需要了解AOP涉及的相关概念。

  • JoinPint:AOP的功能模块要植入到OOP的模块中,需要知道在哪些执行点上进行植入,这些执行点就是JoinPoint。JoinPoint可以是方法的调用,字段设置,异常处理执行等等。

  • PointCut:PointCut是对JoinPoint的表现形式,可以直接用方法名,正则表达式还有特定的PointCut表述语言。

  • Advice:Advice就是横切点功能的载体。包括,Before Advice,AAfter Advice,Around Advice。这三个切入的时间不同,可顾名思义。

  • Aspect:Aspect可以理解为切面,它可以包含多个PointCut和Advice。

阅读全文

【Spring 揭秘(一)】Spring Bean DI and Instantiating

cheatsheet

如果你赶时间,可以只看这一节的内容。

bean 的实例化方式

  • XML 配置时
    • 工厂方法
    • 静态工厂
    • 构造函数
  • 注解方式

关于注解方式:

  1. @Component:可以用于注册所有bean
  2. @Repository:主要用于注册dao层的bean
  3. @Controller:主要用于注册控制层的bean
  4. @Service:主要用于注册服务层的bean

Spring bean 的注入方式

  • XML配置
    • setter 方法注入
    • 构造函数注入
    • 工厂方法/静态工厂
  • 注解方式注入(@AutoWired

阅读全文

Map DateTime to Java Date in MyBatis

问题 最近在用 Spring Boot 重写 LightBlog,查询到的博客的 Date 属性的日期正常,但是时间始终为 00:00:00。 resultMap 映射如下: <resultMap id="blogMap" type="Blog"> <id property="blogId" column="blog_id"/> <result property="blogUid" column="blog_uid"/> <result property="blogTagId" column="blog_tag_id"/>

阅读全文

【瞎折腾】Hack Deepin Desktop Environment

我想要什么?

初来乍到 Deepin,界面不可谓不美观。试用不久就发现一个不爽的地方,键盘快捷方式太少了,特别是没有控制窗口停靠贴标的快捷方式,根本就没有这个选项。

在官方论坛里搜索一番,deepin-wm的 commit message 中有一条 :feat: support interactive tiling,这个新功能在官方论坛中也有介绍:

1、当一个窗口拖到边界分屏的时候; 2、剩下的应用窗口会全部平铺展示; 3、这时候点击剩下的应用窗口,会自动放置在另一半屏幕,方便左右对比;

阅读全文

Concurrent with Semaphore

Semaphore

Dijkstra 大佬提出了一种解决不同线程之前同步和互斥问题的方法。这种方法就是 PV 操作,它基于 Semaphore(信号量)。

可以把信号量简单看成一个非负整数,只能使用两种操作来改变它的值,这两种操作就是 P 和 V,用伪代码描述如下(与教材《操作系统教程》上不同,这里的信号量不能为负值)。PV 操作的伪代码实现如下:

  • P(s)

    P(s) {
        if (p != 0) {
         s--;
        } else {
         append this thread to list;
         sleep();
        }
    }
    
  • V(s)

    V(s) {
        s++;
        if (list is no empty) {
            list.pop().wakeup();
        }
    }
    

P 和 V 的执行过程都是不可打断的,并且 P 和 V 要成对的出现。这样就保证了程序不可能进入信号量为负值的状态,可以利用这个特性实现进程之间的互斥和同步。

阅读全文

6.828 Homework 2:Shell

这次的作业是实现一个简单的 shell。通过阅读 xv6 book 的第零章,基本上就可以实现题目中所说的三个功能,也是shell的基本功能:运行简单的命令,输入输出重定向,管道。

题目提供的sh.c已经实现了命令的解析(大概看了一下流程,大概就是个递归下降解释器吧,这次作业无需关心这个),只需要完成runcmd函数中缺少的代码即可。

流程

先从 main 函数看起:

int main(void) {
  static char buf[100];
  int fd, r;

  // Read and run input commands.
  while (getcmd(buf, sizeof(buf)) >= 0) {
    if (buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' ') {
      // Clumsy but will have to do for now.
      // Chdir has no effect on the parent if run in the child.
      buf[strlen(buf) - 1] = 0; // chop \n
      if (chdir(buf + 3) < 0)
        fprintf(stderr, "cannot cd %s\n", buf + 3);
      continue;
    }
    if (fork1() == 0)
      runcmd(parsecmd(buf));
    wait(&r);
  }
  exit(0);
}

main 函数循环调用 getcmd从 console 读取命令,对 cd 命令做了特别处理。之后fork创建子进程,调用parsecmd解析命令,再调用runcmd执行得到的命令。最后调用wait等待子进程结束。main 的基本流程就这样。

阅读全文