跟随,学习,进步

Yisaer

Yisa's Blog

https://yisaer.github.io

上海大学14级计算机学院,酷家乐黄埔研究院 研发工程师

转到作者网站

浅析unix文件系统

前言先这篇文章的原因在于前几天操作系统考试之前复习到文件系统那一块,发现书上关于目录,目录文件,索引结点这些说的十分模糊。光是看书完全没明白他在说什么,还好这块内容我在学习unix编程时接触过,这里特此做一个总结。概述文件包含数据,目录是文件的列表。不同的目录相互连接构成树状结构,目录还可以包含其他目录。那么如何理解文件在”一个目录中”? 硬盘实际上是一个金属圆盘,每个盘面上都有磁性物质,这些圆盘又是如何显示为一个包含文件,目录的树状结构呢。从用户的角度看文件系统从用户的角度来看,系统中硬盘里的文件组成了一颗目录树,每个目录包含了文件或者其他的目录。 我们可以通过常用的命令如: cd ,ls ,pwd 来查看目录或者文件的信息。很显然,文件的查看或者是更新都是任何一个操作系统都会提供的功能。 但是命令ln却并不常见,但却是unix里的一个基本操作。假设我们输入以下命令touch xln ./x ./xlinkls ./xlinkcat ./x我们创建了一个文件叫做x,然后创建了一个链接指向了x文件,然后将ls的输出重定向给xlink的内容,那么当我们执行cat ./x的时候会发现输出了当前所在位置的文件信息。从这些就可以大致了解了Unix的文件系统,硬盘上呈现了一个深度和广度都广泛延伸的目录树,Unix也提供了许多命令来和这种结构的对象一起工作。但他们是如何工作的?目录是什么?如何知道文件所处的目录?从一个目录转换到另一个目录意味着什么? pwd又是如何得知你当前的位置? 这些问题我们将继续探讨下去。Unix文件系统内部结构硬盘的实质其实是由磁性盘片组成的计算机系统的一个设备。所谓的文件系统,其实就是对这个设备的多层抽象第一层抽象 从磁盘到分区一个磁盘能存储大量的数据,一个磁盘可被分成区,每个分区都可以看做是一个独立的磁盘第二层抽象 从磁盘到块序列一个磁盘由磁性盘片组成,每个盘片的表面被分为很多同心圆,这些同心圆称为磁道,每个磁道又进一步被分成扇区,每个扇区可以存储一定字节数的数据。例如常见的每个扇区是512字节。扇区是磁盘的基本存储单元。第三层抽象 从块序列到三个区域的划分文件系统可以用来存储文件内容,文件属性,和目录,这些不同类型的数据是如何存储在被编号的磁盘块上呢?Unix使用了一个简单的方法,将磁盘分成了三部分。超级块文件系统中的第一个块被称为超级快,这个块存放文件系统本身的结构信息i节点表每个文件都有一些属性,如大小,文件所有者和最近修改时间等。这些性质都被记录在一个称为i节点的结构中,所有的i节点有相同的大小,文件系统中的每个文件都有一个i节点。数据区文件的内容保存在这个区域,磁盘上所有的块的大小是相同的。如果文件包含了超过一个块的内容,则文件内容会存放在多个磁盘块中。 那么系统是如何跟踪这些独立的磁盘块?文件系统的实现,创建文件文件的内容和属性分区存放看起来很简单,但实际上是如何工作的额呢? 创建一个文件时又会发生什么?如果我输入命令 who user当这个命令完成时,文件系统增加了一个存放命令who输出内容的新文件。 创建一个新文件的主要操作如下。存储属性,内核找到一个空的i结点,比如第47块,内核将文件的信息记录其中存储数据,文件内容存储在数据区的块中,如627 200 992记录分配情况,内核在i结点的磁盘分布区记录了上述块序列。添加文件名到目录,新文件的文件名是user,unix内核将入口(47,user)添加到目录文件。cat命令的工作原理现在我们再回头看之前所打的cat命令。cat ./x内核首先在目录中寻找文件名,得到x记录所包含的i节点号定位所得到的I节点并读取数据块编号访问存储文件内容的数据块,通过上面两步,内核已经知道文件内容在哪些数据块以及他们的顺序。理解目录用户看到的文件系统是目录与子目录的集合,每个目录能够包含文件和子目录,每个子目录有一个父目录,在文件系统内部,目录是一个包含文件名与i节点对的列表的文件。从用户的角度看到的是一个文件名的列表,而从Unix的角度看到的是一个被命名的指针的列表。文件在目录中的真正含义一般都说某个文件在某个目录中,但是现在已经知道目录中存放的只是文件在i节点表的入口,而文件的内容则存储在数据区内,文件在某个目录中,从用户的角度看文件y在目录demodir中,而从系统角度来看,看到的则是目录中有一个包含文件名y和i节点为491的入口。简单的说,目录包含的是文件的引用,每个引用被称为连接,文件的内容存储在数据块,文件的属性则被记录在i节点的结构中,i节点的编号和文件名存储在目录中。目录包含子目录也同样如此。目录包含子目录的真正含义从用户的角度看a目录是demodir目录的一个子目录。实际上demodir包含一个指向那个子目录i节点的连接。从系统角度看,最上面一个表包含名为a指向277节点的连接。如何知道277是左边那个目录的i结点号呢? 内核在每个目录中都设置了目录本身的一个i节点号的入口,称为”.” 。 子目录的父目录同理。文件名在Unix的文件系统中,文件没有文件名,但是链接具有名字。文件仅仅拥有i节点号。


编写命令解释器 上篇

前言这周操作系统的最后一个实验室写一个Shell,然而实验手册的pdf上只指明了你必须要完成什么函数,对于怎么写则是一点提示都没有。所以本篇文章则立意于如何写出一个简单可用的shell,个人认为这个主题应该会分为上中下三篇文章来阐明从零开始的Shell编写过程Shell做了什么简单的说,shell是一个管理进程和运行程序的程序,所有常用的shell有三个基本功能运行程序管理输入输出可编程Shell是如何运行程序的shell打印提示符,输入命令,然后就运行这个命令,随手再次打印提示符,如此反复。那么在这个过程中,背后到底有什么?一个shell的主循环执行下面四步:用户输入shell建立进程shell将程序从磁盘载入程序在他的进程中运行直到结束所以一个Shell的主循环可以写成while(!end_of_input) get command execute command wait for command to finish所以要写一个shell ,就需要学会运行程序建立进程等待exit一个程序如何运行另一个程序使用函数 int execvp(const char* file,char* const argv[]) ,这个函数会从PATH变量所指的目录中查找符合参数file的文件名,找到后便执行该文件,然后将第二个参数argv传递给执行的文件。使用demomain(){ char * arglist[3]; arglist[0] = "ls"; arglist[1] = "-l"; arglist[2] = 0; execvp("ls",arglist);}第一个Shell Demo12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include#include#include #include #include /** **prompting shell version 1 ** **Prompts for the command and its arguments. **Builds the argument vector for the call to execvp. **Uses execvp(), and never returns. **/#defineMAXARGS20#defineARGLEN100#defineCMDPROMPT"Command please: "#defineARGPROMPT"next argument please: "#defineprompt(n)printf("%s", (n)==0 ? CMDPROMPT : ARGPROMPT );main(){char*arglist[MAXARGS+1];intnumargs;charargbuf[ARGLEN];char*makestring();numargs = 0;while ( numargs #include#include #include #include /** **prompting shell version 2 ** **Solves the `one-shot' problem of version 1 **Uses execvp(), but fork()s first so that the **shell waits around to perform another command **New problem: shell catches signals. Run vi, press ^c. **/#defineMAXARGS20#defineARGLEN100#defineCMDPROMPT"Command please: "#defineARGPROMPT"next argument please: "#defineprompt(n)printf("%s", (n)==0 ? CMDPROMPT : ARGPROMPT );main(){char*arglist[MAXARGS+1];intnumargs;charargbuf[ARGLEN];char*makestring();numargs = 0;while ( numargs 8, exitstatus&0377);}}char *makestring( char *buf ){char*cp;if ( cp = malloc( strlen(buf) + 1 ) ){strcpy(cp, buf);return cp;}fprintf(stderr,"out of memory\n");exit(1);}总结到了这里,我们的shell demo已经可以基本的运行命令并且正常运行了,但是我们会发现一个新的问题,那么就是现在退出demo的唯一方法就是按ctrl-c键,那么如果在等待子进程结束时输入ctrl-c键会如何呢?我们会发现子进程结束,但是shell也技术了,ctrl-c生成的SIGINT信号不但杀死了运行的子进程,而且也杀死了运行shell的进程,这是为什么?键盘信号发给所有连接的进程程序shell和tr都连接到终端,当按下中断键以后,ttr驱动会告诉内核向所有由这个终端控制的进程发送SIGINT信号,子进程死了,shell也死了,即使他还在等待子进程的结束。那么如何才能让shell不被用户按下的中断或退出键杀死呢? 我将留到这一主题的中篇


并发下的搜索与排序

概论在传统的串行运行下,在数组内查找特定元素和将数组排序都有一套成熟的方法。对于数组内查找,如果是有序数组在可以在查找的话可以运用二分查找法,而对于无序数组则应该将数组遍历一遍。而对于数组排序,则是有类似快排,归并排序等等复杂度控制在O(nlogn)的算法。 从算法的角度来说,似乎并没有往下继续优化的空间了。但是如果运行在并行环境下,虽然理论上的算法复杂度并没有变小,但是我们可以用并行的方式来将时间缩短。为何可以使用并行考虑这么一件事情,如果我们将一堆苹果放在一个篮子里,那么我们唯一能做的做法就是将苹果一个个的依次放入篮子,这没什么好说的。那么如果我们要加快速度的话,我们会多派一个人手,比如将苹果堆一分为二,然后两个人分别将两堆苹果同时放到一个篮子里。但是如果我们考虑到我们希望放入苹果时,希望是一个红苹果一个青苹果间隔,那么在两个人毫无配合的情况下,这种方式反而不如一个人依次放入来的效果好。也就是说,运用并行的场景下,要求我们所处理的数据互相不干扰,那么你就可以使用并行来充分的利用起时间。数组并行搜索对于一个数组,我们想在里面找到元素a的下标,在串行模式中我们只能运用遍历的方式来搜索指定元素。但是如果我们将数组一分为二,然后将分配两个线程并行的单独搜索,那么CPU也就被更多的利用了。以Java为例子,首先我们准备好线程池,并发数,原子性的Int与数组static ExecutorService pool = Executors.newCachedThreadPool();static final int Thread_Num = 2;static AtomicInteger res = new AtomicInteger(-1);static int[] arr;然后我们在再编写每个线程所应该执行的搜索函数,规定了搜索值与搜索区间12345678910111213141516public static int search(int searchValue,int beginPos,int endPos){ for(int i = beginPos;i=0){ return res.get(); } if(arr[i] == searchValue){ System.out.println("Found"); if( !res.compareAndSet(-1,i)){ return res.get(); } return i; } } return -1;}然后我们创建每个线程完成的任务,以Future模式声明,实现了Callable接口12345678910111213141516public static class SearchTask implements Callable{ int begin,end,searchValue; public SearchTask(int begin, int end, int searchValue) { this.begin = begin; this.end = end; this.searchValue = searchValue; } @Override public Integer call() throws Exception { int re = search(searchValue,begin,end); return re; }}最好我们将搜索封装成一个函数即可,当中由于一个数组被切割成N份来并行搜索,我们可以用Arraylist来包装每个线程,从而遍历每个线程是否得到结果。123456789101112131415161718192021public static int pSearch(int searchValue) throws ExecutionException, InterruptedException { int subArrSize = arr.length/Thread_Num+1; List re = new ArrayList(); for(int i = 0;i=arr.length){ end = arr.length; } re.add(pool.submit(new SearchTask(i,end,searchValue))); } try { for (Future fu : re) { if (fu.get() = 0) { return fu.get(); } } return -1; }finally { pool.shutdown(); }}最后许多串行情境下的算法,只要当中数据不相互影响,大部分都可以用并发的情境来充分利用CPU,下次我会分析下如何使用并发来数组排序


寒假的总结与新学期的计划

前言寒假结束了,感觉这个寒假又像之前的假期一样,没有完全利用起来呀。 诶这也是没办法。总结一下这个寒假所做的事情并想一下接下来的安排吧。异步编程这个寒假首先做的事情应该就是接触异步编程,学习使用了Netty框架,并用Netty框架写了一个服务端用在了爬虫作业中。 看了一遍O’Reilly的JavaNio,现在想想感觉自己对选择器和信道还是感觉懵懵懂懂的。虽然写过一遍Demo,不过这个东西就像当初刚接触JDBC一样,希望自己以后能对异步编程的理解越来越深吧。爬虫大二的时候一直希望能学会写爬虫。这个寒假学了python的requests库与bs4库以后,写了两个爬虫来练手。一个是自己用于爬取OJ题目代码的爬虫,一个是爬取豆瓣上书的信息的爬虫。豆瓣爬虫也结合了线程池的技术来加快速度。 虽然感觉在爬虫上这不算什么,但是这种从不会到会的感觉还是很棒的。Unix编程这个寒假大部分的时候应该都放在了Unix编程上面。用C语言来调用系统函数来完成一个个功能非常有意思,而且也对于理解Unix类的操作系统有着非常大的帮助。虽然这本书在寒假大致已经看完了,但是感觉只看了一遍以后并没有完全吸收,而且我觉得这本书真的值得再去学习一遍,将代码再去完成一遍。之前有很多命令函数完成的比较囫囵吞枣,感觉这个学期还要抽时间一天来学习一章的速度重温一遍。以后想去刷apue与unp,希望自己有一天能发展成系统、网络的工程师。话说还一直赖着HTTPD的实现没有写,准备抽空用C语言将HTTP服务器实现。Java高并发程序设计一本国人写的非常棒的书,个人觉得比Java并发实战那本书写的更加直白易懂。这本书大概是在寒假的最后一礼拜开始看的,今天连看带写Demo的完成了前四章吧。总的来说是熟悉了大部分概念与JDK里面的Concurrent并发包。 虽然这是以JAVA对语言的多线程教材,但是感觉提出并解决了许多在并发状况下会出现的错误与如何解决。Loic为了给计算思维交差写的一个Syn泛洪攻击,类似于一个加农炮,服务端从操作大量客户端来向某一台主机发起Syn泛洪攻击。 感觉安全这方面还是很有趣的,我也只是试着写了一个工具测试。 不过如果以后接触安全的话我想我会去了解Web安全吧,毕竟在Web方面有点了解。计划安排接下来会去先将设计模式了解一下以后再将Java高并发刷完,当中会去熟悉学习springboot与mybatis框架,准备为下一次实习做起准备。如果能抽得出时间会二刷Unix系统编程。这应该就是短期内打算在冬季学期内完成的目标了吧。 长期的打算以后再看吧, 感觉自己有很多事情要去做就等以后再说吧。然后每天的锻炼也要坚持不能停,尽快将生物钟恢复到在学校的早睡早起吧。当然Github的活跃更新也不能断. 嗯就这样吧先..