Computer Theory

计算机程序、指令与控制器

程序(program) 是 指令(instruction)的集合 指令 = 操作码 + 数据。 由于程序和数据都放在存储器里,所以对控制器(Controller)来说, 上面的等式相当于  从某个地址读出的指令 = 操作码 + 数据的地址。 比如: 而控制器的基本任务就是: 1. 从存储器中取出第1条指令(fetch instruction) 2. 执行这条指令(execute instruction)。 这时可能还会从存储器中取出数据 (fetch operands) 3. 再取出第2条指令 4. …. 如此循环。 图示:

关于磁盘的一些知识

磁盘结构: 一个磁盘有多个盘片(platter),两面(2 surfaces)都可以存储数据,正反两面一般来说各有一个磁头(disk head) 1. 一个盘面由一系列磁道(track)组成,所有platter在同一直径上的磁盘组成一个柱面(cylinder) 2. 一个磁道包含多个扇区(sector) 存取时间的构成 存取时间由4部分组成:    1. 寻道时间(seek time): 磁头移动到正确的磁道上 (几个ms)    2. 旋转时间(rotational latency): 等待目标扇区旋转到磁头的下面 (几个ms)    3. 数据传输时间 (transfer time, 取决于数据传输率指标)(1k数据,零点几个ms)    4. 磁盘控制器带来的时延 (时延很低) 平均总时延一般是10ms左右    ============== 一个磁盘虽有多个磁头,但这些磁头整体上是同步移动的,并不能各移各的。所以多个进程对单个磁盘的访问,其实并不是并行的,而是串行的。

存储器的多级结构

内存 = cache + 主存储器, cpu可以直接访问 其他的都属于外存,cpu不能直接访问 关于cache:   1. 充当cpu和主存之间的速度缓冲   2. 程序员的代码访问不到cache  

常见寄存器

Data Registers:                暂存ALU的计算结果 Instruction Registers:         存储当前正在执行的指令 Program Counter:               下一条指令的地址 Address Registers:             存储当前指令所访问数据的地址 Control and Status Registers:  can store both data and addresses, i.e., they are combined Data/Address registers. Program Status Word:           程序状态。如进位标志、溢出标志、中断状态等

硬中断

中断是一种电信号,由硬件设备生成,然后传入到中断控制器的输入引脚。 中断控制器则发送一个电信号给CPU. CPU根据中断信号携带的数字标志(中断号),按一定算法找到对应的中断向量的地址(比如8086下是用中断号乘于4),读取这个地址上的值,拿到的就是中断服务程序的内存地址。 最后再执行中断服务程序。

从M个里取N个的组合 C(m,n)

用递归写的,使用时要注意栈空间问题 /** * 从m个里取n个的所有组合 c(m,n) * * @param m * @param n * @return */ public static List<List<Integer>> getCombinationList(int m, int n) { if (n == 1) { List<List<Integer>> resultList = new ArrayList<List<Integer>>(); for (int i = 1; i <= m; i++) { resultList.add(new ArrayList<Integer>(Arrays.asList(i))); } return resultList; } List<List<Integer>> nMinusOneCombList = getCombinationList(m, n – …

从M个里取N个的组合 C(m,n) Read More »

哈希表里的bucket是指什么东西?

转自维基百科: http://en.wikipedia.org/wiki/Hash_function In general, a hashing function may map several different keys to the same index. Therefore, each slot of a hash table is associated with (implicitly or explicitly) a set of records, rather than a single record. For this reason, each slot of a hash table is often called a bucket, and hash values …

哈希表里的bucket是指什么东西? Read More »