White Death
 
        操作系统实验课,老师明确说了考试考fork()和exec族函数,我一直以为自己理解的比较透彻,结果昨天小quiz,考了一道非常简单的题,虽然我做对了,但是我竟然有所犹豫,所以需要巩固一下,刚刚进行了一些实验,发现理解的更进一步了。首先,上个简单的例子:

int main()
{
   int p1,p2;
  
   printf("Once or Twice %d\n",getpid());         // 1
   p1 = fork();
   if(p1 == 0)
   {
      printf("This is the child process \n");
      execl("/bin/ls","ls","-a",NULL);
      printf("Will it be displayed????? \n");            //2
   }
   else
   {
       wait(p1);
       printf("This is the parent \n");
   }
   printf("The end\n");           //3
   return 0;
}


        我发现,1,3都只会显示一次,而2永远不显示,但是讲蓝色高亮的那行execl去掉,2就会显示1次了,而3会显示2次了。说明fork()新创建的子进制只执行从fork开始后面的进程内容(注意,是“只执行”,而不是“只复制”,我们后面会看到),而exec族函数调用后会将所有的进程都覆盖,也就是说不保留父进程的任何信息,相当于脱胎换骨了,所以在那个if里面execl后面写任何代码都不会被执行的。同理,3处的代码,子进程也不好去执行了。
      然后这里就想到一个好玩的程序,如果是在for循环里面调用fork()呢,如下:
int main()
{
    int i,pid1;
    for (i=0; i < 3; i++ )
   {
      pid1 = fork();
      if (pid1 == 0) {
        printf("This is child process! \n");
        //return 0; 
      } else {
        wait(pid1);
        printf("This is parent process!\n");
      }
   }
   return 0;
}
     如果你执行一下这段程序,你就会发现,咦?不应该是显示3对么?怎么这么多?
于是,为了看得清楚:
int main()
{
  int i,pid1;
  for (i=0; i < 3; i++ )
   {
      pid1 = fork();
  
      if (pid1 == 0) {
        printf("This is child process! %d \n",i);
        //return 0; 
      } else {
        wait(pid1);
        printf("This is parent process! %d\n",i);
      }
   }
   return 0;
}

    于是,我们得到如下结果:
Picture
      为什么这么诡异呢?看到0,1,2,2,1...于是我知道了,再第一次循环的时候,子进程并非只复制父进程fork()后面的内容,而且复制了父进程的所有内容,只是它只是从fork()后面执行而已(相当于CS:IP为fork()后一条指令的地址!)
     于是这个例子就不难理解了,i = 0时,那个child开始循环,注意,这里child保存了父进程的所有内容,包括i,所以child执行i = 1,接着 i =2,结束后,开始parent 2(注意:虽然child改变了i,但是这里执行的是copy on write,即在子进程修改前,父进程先另外copy一份i保存起来),parent1(还原child1相对的那个i)....整个过程就像是递归调用似的...
     这样就把fork剖析地更清楚了:每当父进程fork一个子进程时,其实就是将子进程弄个指针过来,指向父进程的内存块,但是,保留了CS:IP,即当前进程的入口地址,然后安装父进程的内存内容进行执行...当需要改变某一内容时,父进程会另外保存这个内容,即copy on write...
 
本文转载自Matrix大牛博客,原地址:Hit here
     这里我们来看:用正则表达式判断数的整除性。例如,下面这个表达式可以匹配01串S当且仅当S是一个可以被3整除的二进制数。

     ^1((10*1)|(01*0))*10*$

     如果你不信的话,不妨把下面这段代码粘贴进浏览器的地址栏,然后回车运行一下:

      javascript:alert(/^1((10*1)|(01*0))*10*$/.test("1000000100"))

     被test的是516的二进制表达。516可以被3整除,因此程序返回true。你可以自己把1000000100换成其它的二进制数试试。
     但是呢,从这个正则表达式里我们竟看不出任何端倪。奇怪了,为什么这个正则表达式可以用于判断整除性?能被3整除的二进制数究竟有何规律?

      其实,能被3整除的二进制数并没有什么明显的规律。这个正则表达式的求法可以说是相当暴力的。这一切的谜底很简单——判断一个数的整除性能轻易地用有限状态自动机实现,而有限状态自动机又可以翻译成正则表达式。

Picture
      
       注意到,一个二进制数后面加一个“0”相当于该数乘以2,一个二进制数后面加一个“1”相当于该数乘2加1。设定三个状态,分别叫做0、1和2,它们表示当前的数除以3所得的余数。如果对于某个i和j,有i*2≡j (mod 3),就加一条路径i→j,路径上标一个字符“0”;如果i*2+1≡j (mod 3),则在路径i→j上标记“1”。状态0既是我们的初始状态,也是我们的最终状态。我们的自动机就做好了。现在,假如二进制数10010走进来了。从状态0出发,机器首先读到一个“1”,于是当前位置挪到状态1,表明目前该数模3余1;然后,系统读了一个“0”,我们紧跟着走到状态2,表明二进制数“10”被3除余2;下一步,我们回到状态1,表明“100”除以3余1;再往后,我们得知“1001”能被3整除。最后呢,我们读到一个0,“1001”的两倍当然还是能被3整除,我们依旧停留在原位。我们得到结论:二进制数10010能被3整除。
      有限状态自动机是可以转化为正则表达式的。上面的这个自动机转化起来非常容易。我们可以先试着用自然语言叙述一下。首先,每个二进制数第一位必然为“1”。到达状态1后,我们可以随意地、任意多次地在状态1周围绕圈圈,最终回到状态1。临近末尾,我们再读到一个“1”返回状态0,这之后随便读多少个“0”都可以了。现在问题分解为:我们又如何用正则表达式表述“从状态1出发随意地走最终回到状态1”呢?在本例中,这是很好描述的:它可以是字符串“1000..001”和“0111..110”的任意组合。把这些东西用正则表达式写出来,就是我们刚才那个神秘的式子:1((10*1)|(01*0))*10* 。
       从原理上说,我们可以这种方法求出任意进制下用于任意数的整除性判断的正则表达式。只不过,它们所对应的自动机都更加复杂,从而得出一长串令人眼花缭乱的表达式。本文开头我把1((10*1)|(01*0))*10*的来源作为一个有趣的问题提出来,因为这个式子恰好不长,让人很难想到这背后藏有一个普适的暴力算法。

 
         最近学了差分约束系统,其实很早很早,可以追溯到半年前了,就知道什么是差分约束系统,就知道怎么解题了,不过当时还不会bellman-ford的算法,所以就搁浅了。然后这个学期学会了bellman-ford的算法,于是在一个睡不着的晚上用手机查资料,又回顾了一下,觉得自己想通了。可是...正所谓站着说话不腰疼,或者说通过实践才能真正的学会知识,前天做了差分约束的第一题,结果花了一晚上,真正真正的理解了差分约束!
        这里插一句,本来打算今晚把1420也搞定后再写这个的,可是编译Linux那个内核弄的什么都很卡,风扇呼呼的,啥也做不下去,就写个记录吧~话说快2个小时了,不给力啊~!
        至于概念已经解题什么的,不多说了,满天飞。说一个最重要的问题,至少是我认为最重要的问题:
        我在弄清楚这一切前,总是不能想通大于小于的问题以及为什么求的是最长路?然而有的博客里又求的是最短路?...而且大多数博客和资料都没有详细谈这个问题(或许是我搜索资料的能力不强吧~~!)

        最后明白了,思路整理如下:
        差分约束的完整描述:满足一组不等式的一组变量,使得xn与x1的差值最小~
        两个要求:一组不等式! xn与x1的差值最小!

        要求x2 - x1 >= c,那么说明,从x1到x2的路径长度必须大于c,于是我们就给x1到x2搭一条路,最后求从x1到xn的最长路(说明一下,个人感觉这是差分约束的核心内容,但是我理解了很长时间。最后我一边默念这句话一边想,终于想通了:因为x1到x2原来的路径是正无穷,当然也是满足条件的,但是我们现在求的是满足条件的xn-x1最小,就是说如果这条路c长度可以满足,我们就绝不搭长为c+1的路,所以我们搭了一条这样的路。)接下来,x3 - x1 >= d ; x2 - x3 >= e。这个时候,我们已经搭成这样:   
                            3
                          /  \
                        d      e
                      /          \
                   1  -- c -->  2

       这时候如果d+e大于c的话,那么x1到x2的距离就必须更新为d+e了,为什么?因为原来的c不能满足条件了,虽然求最小,但是满足条件才是first!然后,其实,这时候表达式x1 - x2 >= c已经不管用了,x1 --- x3 --- x2 这条路径已经足够约束x1和x2啦!~
      当然,反过来,求最短路也可以的,但是,需要倒着来。
      结论,两个选择:
      1. 如果 xi - xj >= w,那么从xj到xi连一条又向边,然后求从前往后(假设j < i)的最长路;
      2. 如果 xi - xj >= w,那么转化为xj - xi <= -w,于是从xi到xj连一条有向边,然后求从后往前的最短路(亦假设j<i)。

      其他问题就不说了,bellman-ford或者SPFA,搭完路就开始(n - 1)次松弛和一次检验,n为顶点数。
      不过在实际应用中,一般不是真正的不等式组,不是给出一些二元不等式,而是这样:
      给出一个序列,1至n这n个数字,然后已知从 i 到 j 的数字和至多a、至少b,给出这么一组,然后求每个数字最小为多少,或者求总和最小为多少。
     于是构造,设s[i]为0到i的和,那么s[1]即为第一个数字,s[2]-s[1]即为第二个数字,于是给出的条件转换为:
     s[i] - s[j] >= b
     s[i] - s[j] <= a
     s[i] - s[i-1] >= 0
    s[i] - s[i-1] <= V (*如果是1到n这n个容器,每个容器有容量,或者特殊情况n个布尔值,那么需要加上这个限制条件)
   具体例子在这里 hit
 
        今天收到了zjubox的回复,原来以前都回复过我的,只是邮件莫名其妙的丢失了,悲催的,错怪人家了。然后发现一片空白,不像weebly这样很傻瓜化的。因为自己本来就是土人一个,所以就决定安装wordpress吧,否则不知道从何下手...于是安装mysql,安装php...(因为重装系统都不在了)...最后又装了wamp...数据库和PHP什么的都已经忘光光了,于是翻出陈年老底的PHP视频(1), wamp的各种配置...上网查了下wordpress安装,终于完成了,wordpress的那帮人也真搞,上图,不说话:
Picture
       设置方法(我是用wamp5配置安装的):
                1. 先将下载好的wordpress文件夹放在wamp的工作目录内(默认为wamp里面的www文件夹);
                2. 然后打开phpMyAdmin(任务栏wamp左键 -> phpMyAdmin),在里面新建一个database,命名为wordpress;
               3. 然后新建一个用户(主页-> Privileges -> Add a new User),自己命名,我命名为wordpress,加上密码(user name 和 Password选择 Use text field,Host选择local)。然后将所有权限赋予给这个新的user,最后在下面选择wordpress数据库的所有edit权限赋予这个新user;
              4. 打开wordpress文件夹里的wp-config-example.php文件,将里面
                  /** WordPress 数据库的名称 */
                  define('DB_NAME', 'wordpress');
                 /** MySQL 数据库用户名 */                  
                  define('DB_USER', 'wordpress');
                 /** MySQL 数据库密码 */
                  define('DB_PASSWORD', '123456');
              改为刚才设置的;
            5. 在浏览器里面打开 http://localhost/wordpress/wp-admin/install.php 即可以完成安装~

           安装后,http://localhost/wordpress进入博客,下面界面进行登录操作:         
Picture
         虽然在本地搭配好了,但是试着在学习的zjubox上面缺不成功,因为权限不够,没法创建用户和数据库,所以先等等吧。
          上面写的不一定好,但是正如我们OS老师说的,人获得了知识或者是努力成功一件事,总是希望分享的,不仅仅是结果,还有过程,bow~
 
        花了好长时间,初步“搭建”成功了这个网站。还花时间去了解了一个网站和网页的知识,php或asp在服务器工作,下载到pc后,就是html和css以及jsp工作了,blablabla...
        我对这些界面、图形、视频之类的不是很感兴趣,所以之前一直没有对这些进行深究(只有大二上学期学过点php和apache知识),但是我又不满足于QQ空间、百度博客这类,根本没有自由可言,所以一直在试图着完全自己搭建属于自己的博客。等有兴趣了自己学学设计吧,至少换个图片吧, ^_^ ..
    ---------------------------------------------------------------------------------------------------       
        接下来是忏悔时间..⊙o⊙
      
        上个学期不知怎么搞的,先是看动漫bleach,后又看美剧lost,每天在98和NHD里面闲逛,而且ms还得了抑郁症,于是包括今天接连玩了四天,一扫以前的不快...这个学期最大欣慰的是,课程几乎没有落下的(计算理论...继续忏悔...),而且前几天还小小复习了下的...而最该忏悔的是ACM刷题速度明显下降,比蜗牛都慢了,而真正学到的东西更少...
        发现自己的一个坏毛病很难改掉,就是什么事情都坚持不下去,学习什么都不能达到很精通的地步,这样是坚决不行的...于是决定:python就不继续学了,继续像上学期一样当计算器使用。下学期学好新课程C#,继续刷ZOJ和usaco里面的题目,codeforces的比赛也尽量参加,除了课程还有一块继续学的就是网络知识和socket编程,加油!!至于bleach,先不看了,等寒假的吧,lost呢,悠着点儿看,心情不好的时候看,2011年前看到第四季吧。
        明天实验后再继续“维护”下这个博客~