多线程编程及C#下的实现

发表于 2018-08-27

在Windows应用程序中多线程很常见，但是之前写的小程序都只用到了简单的线程操作，对于线程间通信较多的程序，该怎么处理呢？
C#给出了一些特定的实现，如果没有想清楚可能会造成很大的麻烦。
对于C#下的语法，查文档一般是MSDN，但是如果不行的话，也可以实验得到，不过对于多线程操作，在不同的CPU上表现不一定一样，通过实验下结论需要特别小心。

windows线程与线程通信

面试被问到过无数次线程与线程通信的概念，首先抄一段：

ref1: https://segmentfault.com/a/1190000008732448
ref2: http://www.cnblogs.com/lmule/archive/2010/08/18/1802774.html

进程和线程的区别

逻辑层级上的区别：一个程序至少有一个进程,一个进程至少有一个线程.
时间尺度上的区别：线程的划分尺度小于进程，使得多线程程序的并发性高。
内存管理上的区别：另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。
操作系统调用上的区别：线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。但是在windows下线程对操作系统可见！
总体概念上：进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位.
线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源.
一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行.

一些细节 on windows

在运行于32位处理器上的32位Windows操作系统中，可将一个进程视为一段大小为4GB（ $2^{32}$ 字节）的线性内存空间，它起始于0x00000000结束于0xFFFFFFFF。这段内存空间不能被其他进程所访问，所以称为该进程的私有空间。这段空间被平分为两块，TODO👉 2GB被系统所有，剩下2GB被用户所有。 👈TODO！但是这些空间并不是全部被分配到物理内存上，Windows是按需为每个进程分配内存的，4GB是32位系统中一个进程所占空间的上限。将进程所需的内存划分为4KB大小的内存页，并根据使用情况将这些内存页存储在硬盘上或加载到RAM中，通过系统的这种虚拟内存机制，我们可以有效地减少对实际内存的需求量。当然这些对用户和开发者来说都是透明的。

线程通信/同步

线程同步其实就需要线程通信来实现吧……
同步/互斥。。。

共享全局变量、资源，加锁
消息

同步方式

临界区
互斥量
信号量
事件

C#中相关操作

refs:

https://docs.microsoft.com/zh-cn/dotnet/standard/parallel-programming/index

https://docs.microsoft.com/zh-cn/dotnet/standard/async-in-depth

https://docs.microsoft.com/zh-cn/dotnet/standard/asynchronous-programming-patterns/task-based-asynchronous-pattern-tap

https://docs.microsoft.com/zh-cn/dotnet/csharp/async

托管(managed)与CLR

异步编程模式

EAP与TAP

C#与AppDomain

Git submodule —— 一点经验

发表于 2018-08-09

今天一天都在各种调整git的噩梦中度过，终于感觉自己对git的branch, submodule, commit 这些操作有所了解了，都是些Google很难搜到的东西，先整理一下orz。

官方教程： https://git-scm.com/book/en/v2/Git-Tools-Submodules

git中submodule的维护

工作的项目维护了一个很复杂的submodule树，不小心的话很容易就搞崩。记录几个重点。

git如何配置submodule

git提供了一个名为.gitmodules的配置文件来帮助你配置submodule，这个文件的一般格式如下：显然，path是子模块的相对位置，url是仓库地址。

1
2
3

[submodule "rack"]
      path = rack
      url = git://github.com/chneukirchen/rack.git

submodule的仓库的建立

初始化这些submodule有若干种方式：

直接clone –recursive

git clone /path/to/your/repo --recursive

如果你才刚开始或者想要放弃所有本地的修改，再来一次永远是最简单的方式。

利用git submodule 建立子模块

git submodule 这条命令可以帮你完成很多事，如果你不加任何后缀，它至少会帮你列出所有子模块：

1 2	$ git submodule -3cb76a4301dcc76d453c69c86c2c8a889bafac34 subproject/tutor-wpf-common

当你编辑了.gitmodules文件或者只建立了父级仓库，或是进行了一些别的骚操作导致你需要自己建立一次子模块：

git submodule update --init

或是更骚的：
git submodule update --init --recursive

这条命令帮助你建立了子模块的仓库， 并且还会帮你checkout到父级仓库所在的分支上

$ git submodule update --init
Submodule 'subproject/tutor-wpf-common' (ssh://gerrit.zhenguanyu.com:29418/tutor-wpf-common) registered for path 'subproject/tutor-wpf-common'
Cloning into 'D:/tutor-wpf-student/subproject/tutor-wpf-common'...
Total 32915 (delta 0), reused 32909 (delta 0)
Submodule path 'subproject/tutor-wpf-common': checked out '3cb76a4301dcc76d453c69c86c2c8a889bafac34'

值得注意的是，子模块的.git目录不在 path/to/child/.git，而是在 .git/modules/path/to/child

submodule的管理

3cb76a4301dcc76d453c69c86c2c8a889bafac34 <= 这串神秘数字显然是某个commit-id，你也许想到了，如果一个项目要依赖于某个子模块，那让这个子模块天天在master上更新不是个好主意，也许哪天更新了接口或是修复了feature呢？

所以，对于父级仓库来说，submodule是以整个repo为单位来进行管理的！而记录这个repo，对父仓库来说，只需要记录下它们的commit-id！对于大工程来说，这个commit-id是维护每个repo之间的依赖的关键！

这时候，你的子模块很可能会是这样的：

1
2
3

$ git branch
* (HEAD detached at 3cb76a43)
  master

因为一般项目开发人手都不够，很难保证依赖是最新的。

如果你觉得子模块实在是太旧了，直接切换到你想要到的分支上。

$ git checkout master
Previous HEAD position was 3cb76a43 MOD: move virtual call from constructor, and resigter jsobject async
Switched to branch 'master'
Your branch is up to date with 'origin/master'.

然后你的主仓库会变成这样：

$ git status
On branch master
Your branch is up to date with 'origin/master'.

Changes not staged for commit:
  (use "git add <file>..." to update what will be committed)
  (use "git checkout -- <file>..." to discard changes in working directory)

        modified:   subproject/tutor-wpf-common (new commits)

no changes added to commit (use "git add" and/or "git commit -a")

这时候就可以非常开心的git add .接git commit -a啦!

等等，这次push被老板reject了！！！

嗯，做完这一堆操作之后，你很可能发现你的代码没有通过code review，虽然你在本地磕磕绊绊干掉了build报的所有error，多出来几个warning，但是老板还是非常贴心地给你查出了100000个coding style error！嗯，为了吃饭没法坚持信仰了呢…QAQ。
更麻烦的是，老板告诉你，不要随便更新依赖库！
虽然你发现组里其他人的代码一样不忍直视，但是老板毕竟要舔好，幸亏你入职以前看了几篇《10分钟学会git》，又根据错误提示自己琢磨了下，打出了git reset HEAD^，然后胡乱用了几下code formatter准备交差。。。嗯。。。老板还说不能更新依赖。。。
难道是……

~~git checkout -- subproject/tutor-wpf-common~~

但是不知道为什么，似乎这不起作用啊！！！
赶紧切到submodule的repo。。。然而……刚才的branch已经不见啦！！！
这时候你只能通过父级仓库的命令去checkout到当前记录的那个commit！

git submodule update

关于gerrit

在gerrit上，你需要一个Change-Id，虽然可以通过 git commit --amend 在不更改Change-Id的情况下修改上一个commit，但是由于几乎没有一个git-gui能够非常完美地支持rebase，先Reset复制一下Change-Id，也许是比使用rebase更好的一种方式。

Change 243062 - Not Code-Review

ADD: add Services and interfaces for design view.

Change-Id: I952418a42a507d276f203f01976f710c04b5783a

统计学习方法习题1

发表于 2018-04-08

1.1 说明伯努利模型的极大似然估计以及贝叶斯估计中的统计学习方法三要素。伯努利模型是定义在取值为$0$与$1$的随机变量上的概率分布。假设观测到伯努利模型$n$次独立的数据生成结果，其中$k$次的结果为$1$，这时可以用极大似然估计或贝叶斯估计来估计结果为$1$的概率。

伯努利模型的极大似然估计：
$$
\hat{p} = \bar{x}
$$
贝叶斯估计，先验为$\theta \sim U(0, 1)$，则：
$$
\hat{\theta} = \frac{x + 1}{n + 2}
$$

1.2 通过经验风险最小化推导极大似然估计，证明模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化等价于极大似然估计。

经验风险最小化中

R_{emp} = \frac{1}{N} \sum_{i=1}^{N}{L(y_i, f(x_i))}

L(y_i, f(x_i)) = -logP(y_i|x_i)

\hat\theta = \arg\min_{\theta}{\frac{1}{N}\sum_{i=1}^{N}{L(y_i, f(x_i))}}

即
$$
\hat\theta = \arg\min_{\theta}{\frac{1}{N}\sum_{i=1}^{N}{-\log{P(y_i|x_i)}}}
$$

极大似然估计中

L(y, x) = \prod_{i=1}^{N}{P(y_i|x_i;\theta)}

\hat \theta = \arg\max_\theta \sum_{i = 1} ^ {N} -\log {P(y_i|x_i;\theta)}

春季学期课件下载集合

发表于 2018-03-26

系统结构实验

cmake创建动态库和引用动态库

发表于 2018-03-20

CLion默认使用Cmake作为工程构建工具，使用CLion还得先学这个吗……

学习教程

Cmake实践

Quick Cmake Tutorial

Cmake实践的介绍比较详细，但是我即使照着一步步做还是炸了。

坑点

在t4编译成功之后无法运行./src/main，报错:
error while loading shred libraries: libhello.so.1: cannot open shared objedct file: No such file or directory

阅读全文 »

OnlineJudge判题核心基本思路

发表于 2018-03-20

如果不考虑沙盒、权限、虚拟化等问题，其实一共就三步：编译、运行、比对。

其中，比对只需要写一个循环即可，编译也较为简单，
编译选项暂定为g+++ -fno-asm -Wall -lm –static -std=c++11 -DONLINE_JUDGE -o Main Main.cpp

关键是运行。

hust 的judge中采取了如下手段：

nice(19);

(限制进程优先级)

重定向

ptrace

主要是为了监视EXIT信号
long ptrace(enum __ptrace_request request, pid_t pid,
void *addr, void *data);
PTRACE_TRACEME
Indicate that this process is to be traced by its parent. A
process probably shouldn’t make this request if its parent
isn’t expecting to trace it. (pid, addr, and data are
ignored.)

          The PTRACE_TRACEME request is used only by the tracee; the
          remaining requests are used only by the tracer.  In the
          following requests, pid specifies the thread ID of the tracee
          to be acted on.  For requests other than PTRACE_ATTACH,
          PTRACE_SEIZE, PTRACE_INTERRUPT, and PTRACE_KILL, the tracee
          must be stopped.

wait4

用wait4来监视资源占用情况
但是wait4已经弃用了
所以我打算尝试用waitpid和getrusage来获取资源占用情况

waitpid

pid_t waitpid(pid_t pid, int *status, int options);
等待子进程的“状态改变”，包括：

进程结束
子进程发出信号停止或继续运行。

如何获取时间

waitpid后getruage，然后取ru_utime和ru_stime两项，其中ru_utime表示user CPU time， ru_stime表示system CPU time

如何获取内存

最简单的方式是等待子进程结束之后使用rusge结构中的max_rss这一项。
但是据说这种方式有缺陷，暂时没发现有什么问题。
而hustoj采用了不同的方式，它在进程退出之前检测/proc/pid/status这一“文件”，
并找出VmPeak这一项读出结果。
从目前的实验来看，这两者有一定的出入，差距在10-20M之间，效果还有待研究

秋季学期课件下载集合

发表于 2017-12-26

实在太麻烦了经常找不到各门课的下载地址QAQ

软件工程

公邮

操作系统

公邮

模式识别

学习空间

数据库

百度网盘
密码：Tsty

尝试介绍项目

shuacmOJ

这是一个用django结合celery编写的在线判题系统，主要功能是实现在线判题和比赛。
这个系统由题目管理，比赛管理，提交信息管理，判题系统，人员管理几个模块构成。
这个系统管理了一套ACM形式的题目，管理员可以进行题目的增删改查，用户可以查看题面。
解题代码可以以文本的方式提交。
用户可以通过练习和比赛两种方式提交自己的代码，代码提交到服务器之后，
会进行判题和比对。
用户每次提交代码会生成一次提交记录，提交记录包含了一次提交的代码，运行时间，结果等信息。
判题机和Web服务器之间利用HTTP通信，判题机提供http服务给Web服务器，因此通过建立一系列判题服务器，可以实现分布式的判题，用于应对短时间大量的提交。
比赛中的题目提交和平时的提交基本相似，不同的是比赛中的提交在获得提交结果后，需要更新用户在比赛中的成绩，实现展现一个榜单的功能。

这是一个用django结合celery编写的在线判题系统，主要功能是实现在线判题和比赛。
用户能通过在日常或比赛时提交代码后，系统自动运行代码，并将运行结果与标准答案进行对比。
用户的提交将会被记录下来，而且比赛和日常分为两个系统，在比赛系统中将会提供实时的榜单，使比赛选手可以看见其他选手的比赛情况。
这个系统由题目管理，比赛管理，提交信息管理，判题系统，人员管理几个模块构成。
为了应对网络比赛中出现的短时间大量的提交请求，将判题机和web服务器分开，判题机提供http服务给Web服务器，因此通过建立一系列判题服务器，实现分布式的判题。
该系统曾成功举办过金马五校网络赛，比担负着学校日常训练的任务。
我在该系统中主要做了XXX部分，改进了XXXX功能

自我介绍

My name is Laizenan, I’m currently junior student of Shanghai University. When I first come in School of Computer, I was addicted to programming contest
and plunged bunches of time writing c plus plus to solve standard problems. I get lots of experiences and prove myself in ACM International Collegiate
Programming Contest contests. I and my teammate get three bronze medals in 2016 and we win a silver medal and two bronze medals in 2017.
The best one I regard as is the silver prize in Xi’an Regional, at the last moment,
we solved a problem combining linear basis and segment tree, which sent us to
the 29th position in three hundred teams and more than one hundred universities.
Within one and a half years, I learned how to cooperate with my teammates and earned lots of coding experiences.
I’m currently writing a new Online Judge for ACM club, where I practices my cpp and python skills.
Do you need any further infomation about me ?

2017 Multi-University Training Contest - Team 1

发表于 2017-07-21

frustrating process

1001 and 1011 is solved instantly, however, I failed to notice a critical feature in 1002, and stuck on it for hours, no need to say that other problem is too difficult for me.

1006. Function

考虑置换 $a$ 的一个循环节，长度为 $l$ ，那么有 $f(i) = b_{f(a_i)} = b_{b_{f(a_{a_i})}} = \underbrace{b_{\cdots b_{f(i)}}}_{l\text{ times }b}$ 。

那么 $f(i)$ 的值在置换 $b$ 中所在的循环节的长度必须为 $l$ 的因数。

而如果 $f(i)$ 的值确定下来了，这个循环节的另外 $l - 1$ 个数的函数值也都确定下来了。

答案就是 $\sum_{i = 1}^{k} \sum_{j | l_i} {j \cdot cal_j}$ 改为 $\prod_{i = 1}^{k} \sum_{j | l_i} {j \cdot cal_j}$ ，其中 $k$ 是置换 $a$ 中循环节的个数， $l_i$ 表示置换 $a$ 中第 $i$ 个循环节的长度， $cal_j$ 表示置换 $b$ 中长度为 $j$ 的循环节的个数。

时间复杂度是 $\mathcal{O}(n + m)$ 。

14届浙江省赛部分题解 The 14th Zhejiang Provincial Collegiate Programming Contest

发表于 2017-04-28

不知道结果是什么样，但是不挣扎的话，就连RP爆炸摸到牌的机会都没有吧。

阅读全文 »

Codeforces Round 384 (Div. 2)

发表于 2017-01-04

打了场CF，来写个题解吧，第一次写题解好鸡冻。

C. Vladik and fractions

阅读全文 »