Components of introduction.
可能是由于自己本科时经常去图书馆养成的学习习惯，发现自己在安静的、大家都在学习的环境下效率会更高。如果处于一个封闭的独处空间或者开放的办公室空间，在无deadline的情况下，很难进行长时间的专注。
不插电学习法，表示一个0）不携带手机，1）不联接网，2）不插电的工作学习方法，对于写作，写代码这种不太需要信息获取的工作效率提升明显（实验样本目前只有自己）。
不联网即完全隔绝网络上的信息，保持一个无人打扰的状态。没有email，没有sns，没有娱乐网站。如果进行编程的话，可以使用离线文档, 如dash。因为编程大多数时候bug是不需要从网上寻找解决方法的，同时对于自己的写bug能力也有提升。
不插电是为了保持合理的工作休息时间。对于一个老mac用户，不插电电脑可使用4.5小时左右（屏幕亮度在90%以上）。电量每下降30%左右可以休息一首歌的时间（保护视力）。这个方法和番茄工作法的区别之处是保持了更久的工作时间。在电量15%左右时返回一个有手机有网的环境（保护电脑的电池）。这个时候已经应该高效地工作了3个多小时，完成了一个battery time。如果一天能完成两个battery time，那就已经非常高效了。
在办公室的时候可以去楼下的study room或者library，需要和colleague讨论的时候返回实验室去讨论一番。在家也可以去小区的公开study room，效果比在家/实验室效率会高很多。
Assume we initialize each node’s parent is itself. root[i] = i
Union operation is just to set one root to be a child of another root.
1 | void union_root(int x, int y) { |
The plain version is to find root of its parent until its parent is itself.
1 | int find_root(int x) { |
Path compression (No reason not to use.)
1 | int find_root(int x) { |
or1
2
3
4
5
6
7int find_root(int x) {
while (x!=root[x]) {
root[x] = root[root[x]];
x = root[x];
}
return root[x];
}
What is empirical study? or characteristic study? It is a way of gaining knowledge by observations (empirical evidence) qualitatively or quantitatively. With collected evidence (data), empirical questions should be answered.
I read four papers of characteristic study papers in a few days, which covers from concurrency bugs[1], incorrect bug fixes[2], configuration errors[3, 4, 6], and log practices[5]. These excellent study papers cover different research themes and share something for common. Here are some notes.
All these studies are done with a specific perspective.
It is not just the interesting/important topic, but also the findings with a special angle to look at. [1] for concurrency bugs with bug patterns, fix strategies, and manifestation method. [2] for quantitive analysis on significance, types, patterns, reasons of incorrect fixes. [3, 4, 6] are from different perspect of configurations. [3] looks at importance, types, reactions and cause of misconfig. [4] is more about number of configuration settings, and the percentage of parameters being userd well. Based on the findings to propose that we should simplify config and improve config navigation method. [6] focus on latent config errors. [5] is all about log practices, and one interesting finding that log is modified more than other code, which give insights on improving logging practices.
Structure
Intro - Methodology - Perspect 1-N - Related work - Conclution
First, be clear what is the problem/overall topic. It should have a strong focus.
Then think about (0) significance or prevalence of this problem (1) causes/reasons for this problem, (2) types/categories of this problem, (3) characteristic for different types, (4) possible solutions discussion, can be simple to demostrate why the findings beneficial.
Angles for permissions
Goal: provide insights for developers, users, policy makers! not a single app company.
What is the problem?
Incorrect permission understanding android users, they do not understand current permission design. fine-grained vs coarse grained
Small perspects
What data do we have?
- user - app - permission - grant/not
- app - category - permission
[1] Learning from Mistakes — A Comprehensive Study on Real World Concurrency Bug Characteristics, ASPLOS’08
[2] How Do Fixes Become Bugs? – A Comprehensive Characteristic Study on Incorrect Fixes in Commercial and Open Source Operating Systems, FSE’11, best paper
[3] An Empirical Study on Configuration Errors in Commercial and Open Source Systems, SOSP’11
[4] Hey, You Have Given Me Too Many Knobs! Understanding and Dealing with Over-Designed Configuration in System Software, FSE’15
[5] Characterizing Logging Practices in Open-Source Software, ICSE’12
[6] Early Detection of Configuration Errors to Reduce Failure Damage, OSDI’16 morning paper
What makes good characteristic study paper? Interesting findings with practical implications for users/developers/policy makers.
Real world statistics to show current study on concurrent concurrency bugs is not enough, or can not cover very important perspectives.
13 findings in Table 1, only select interesting ones here.
Even though many works on bug study has been done, but this one stress on concurrency bugs. To see why cc bugs are different, this one is a must read.
Section2 Methodology part specifies (1) bug sources and why these many bugs covers many software systems (2) categories and dimensions of study, specified in Table 2. (3) Threats to validity, frankly tell readers why it is limited. It makes reviewers stupid to point it out in reviews.
…
Useful links for understanding.
Understand how kmp works, Post by Ruanyi Feng
Understand how to calculate the next table, post from Zhihu
My implementation of calculate next table.
1 | vector<int> cal_next(string s) { |
Why I gave your paper a Strong Accept by Matt Welsh
Why I gave your paper a Strong Reject by Matt Welsh
Finances for recent CS Ph.Ds headed to academia by dave anderson
side channels with interesting examples
Just find and replace… It is better to read the code through though.
In alarm.java, make current thread wait for some interval. Just need an external structure to store the thread according to the priority. And in timerInterrupt() to wake them up if current time is larger than the designated time for each thread.
Note that the structure involves read and write at the same time, need to disable interrupt before handle it, or use some concurrent structure maybe.
Need to has an external variable to record in which thread the join has been called. And a counter to record how many times has been called. But this is too cumbersome, since it involves atomicity. Maybe just test whether the join thread has been set or not.
Condition.java implements conditional variable (CV) using semaphores. Just open Semaphore.java and copy paste all the code into Condition2.java… Just kidding. Basicly, you do the samething. Use a simpler interrupt on a wait queue for threads trying to get the conditional variables. Think about that, when you wait (sleep) on some variables in one thread, need to put this thread into the wait queue. When others finished (call wake), then make this thread ready. Done.
Wait… Is that simple? What is the relationship with lock? Each CV has a lock. When wait (sleep) for some CV, you need first release the lock, let next thread N on the wait queue for the lock be ready. Then let the current thread C to sleep, put C on the wait queue for the conditional variable. Then let N acquire the lock, and do things.
It is a little complicated… Let’s think it fundementally. CV is a high level of synchronize primitive, which combines Lock with signal process. When you release the lock, you also signal others you are free. Put others on the wait queue for the lock to be ready. So when you wait for the conditional variables, you do not need to constantly check if the lock is free. Instead, you use a signal procedure to avoid this spinning waiting. Here is a helpful stack overflow link. differences-between-conditional-variables-mutexes-and-locks
Geoff’s homework is GameMatch, which is really geoff style. It does basicly the samething for locks and conditions. First N-1 players are waiting, then the Nth player comes to wake them all, and increase the match counter. The description is not so clear, so I assume it is first come, first serve order. However it is hard for testing if there are multiple rounds of matches.
Since it involves mips gcc which can not run on my stupid macintosh, I switch to the ubuntu on my pc.
Implement calls creat, open, read, write, close, and unlink, as specified in test/syscall.h.
Let’s do it step by step. Startring from the simple ones.
Personally I feel open, close are the simplest ones, from the length of description lol. You need to create a file descriptor table, to hold the fd. size is specified as 16. To read the file name, your need to call APIs, like readVirtualMemoryString in UserProcess.
read(), write should consider many corner cases; like what if read failed, or read only 0 byte, which might be failure, or just no read. ?
unlink(): let fs handle the problem of multiple open files
questions:
[1] Nachos related document. Especially nachos javadoc for walk through the APIs.
What problem does the paper address?
low overhead in a few coordinated attempts.How is it different from previous work, if any?
gettime() can be recorded for re-execution. (3) Timing variation from hardware, can be overcomed by logic time, eg. number of instructions executed. But (3) causes problems in multicore.The most problematic source of non-determinism comes from timing variations caused by hardware, such as cache state, memory refresh-scrubbing, and timing variations on buses and devices.
What is the approach used to solve the problem?
Fig 3. PRES approach overview
How does the paper support or otherwise justify its arguments and conclusions?
What do you like / dislike this paper?
Was the paper, in your judgement, successful in addressing the problem?