Skip to main content

Computer Science Intro

早期计算机early computing

  • 最早 算盘

  • 最早服务于战争(计算弹道), 然后 人口普查, 只是用于特定用途, 并不是"general goal Computer"

  • 第一位程序员: Ada Lovelace

电子计算机electronic computing

  • 机械继电器(relay), 翻转速度慢, 磨损 bug由来---->> 代替: 三极真空管, 易碎 ----->> 替代: 晶体管(固体, 小), 材料: 硅, 硅谷

布尔逻辑和逻辑门Boolean logic & logic gates

二进制(晶体管可表示两种状态, 事实上可以有更多状态, 但是容易受环境干扰, 二进制最容易区分信号)

一个晶体管类似这样: (最简逻辑门单元)

  • NOT gate 接地

  • AND gate 串联

  • OR gate 并联

  • XOR gate inputA和inputB必须不同, output才为true

二进制

表示数字, 表示文字(英语, 其他国家字符, emoji)

8bit, 32bit, 64bit

8bit = 1Byte

算术逻辑单元ALU

alu: 负责运算(加减乘除...)

2个单元: 算术单元, 逻辑单元

先看算术单元(负责数字操作, 比如加减操作, +1操作): 半加器, 全加器

  • 半加器(最简单的加法电路): 适合1+1的计算(即2个bit相加, bit为 0 or 1)

    进一步抽象:

  • 全加器: 超过1+1的计算需要 full adder

    全加器的表格:

    简图:

    现在, 可以计算8bit的加法了: 8bit full adder, A, B表示两个数字, A0, B0表示8bit中的第一个bit

    如果最后一个全加器还有carry bit(即还有carry7存在, 为1), 会溢出(overflow), 表示相加的结果超过8bit了, 比如8bit的吃豆人游戏, 当玩到了256关(8bit最高可表示数字255), 画面会出现乱码bug, (而这个乱码界面也表示了你是个吃豆人高水平玩家😀)

    要避免overflow, 可以拓展full adder, 使得可以操作16bit or 32bit的数字, 代价是增加更多的logic gate, 而且每次进位(产生 carry bit)都会花费实践

简单的alu 没有乘除法的计算操作, 都是通过加减法来变相实现乘除法, 可以实现, 但是耗时, 适用于遥控器, 冰箱, 空调等等; 但是电脑, 手机就不行了, 需要专门的乘除法alu

再看看逻辑单元: 执行逻辑操作( and, not, or, xor))

现在, 可以对 alu 做一个抽象: (就像抽象出了一个逻辑门)):

寄存器&内存 Registers&RAM

存储 + alu --> cpu

存储 1 和 0 的电路:

可以存贮 1 bit 的电路: -----锁存器(latch)

并排排列多个锁存器, 就可以存储多位, 比如并排 8 个 latch 可以存储8bit数据(eg: 一个 8bit 的数字), 一组(8个, 16个, 32个, 64个)这样的latch -----> 寄存器(register), 可以存一个数字, 数字有几位就是有多少个latch(叫做"位宽")

但是这种解决方案耗费线材--------可以矩阵排列以节省线材

register继续增大, 存储256位: 16*16 (256 bit) 的锁存器组成的矩阵--------------RAM

要启用某个锁存器, 打开相应的 行线 和 列线; 所以存储 1 bit, 需要知道行列号(最多16行/列, 所以行列号需要 4 bit 就够了), ------> 多路复用器(multiplexer), 两个, 一个处理行, 一个处理列, 专门用于解码8位地址定位到单个latch

现在线材只需要 16(行)+16(列)+1(数据线)+1(允许写入)+1(允许读取) = 35根

256bit内存抽象图:

8个256内存并排: --------> 可寻址的256byte内存

存储时候, 赋值给每个256bit内存块"一样的地址", 可以赋值256次(256个不同的地址, 每个地址可以存储一个8bit的值), 也就是说可以存储256byte(字节)

内存地址: 8bit(4bit给行号, 4bit给列号)最多只能指定256个地址(1111 1111是255, 0~255共256个内存地址)

the CPU

ram + register + alu ------> cpu(取指令-解释-执行)

程序就是一个个指令(instruction), eg: 数学指令(加减, cpu调用alu), 内存指令(cpu和内存通信, 读写值)

时钟: 控制"取指令-解释-执行"的进行, 这3个阶段为一个周期, 一个周期的的速度就是"时钟速度(clock speed)", 单位Hz(1Hz---> 1s 一个周期; "超频" 修改clock speed)

cpu 微结构示意图:

instruction 和 program 步步分析

处理器生产商: amd, arm, intel; 一般我们的 x64 就是指的 amd 生产的 64位处理器

编程语言发展史

reference: https://zhuanlan.zhihu.com/p/20887949

  • C# - Windows平台 的应用, 企业应用, 软件开发; 著名的 SOS 就是 C# 写就

    • 基于 C , 因此 c# 的结构可以可以转移至 C++, Java, Object-C , PHP

    • 全面集成 .Net 库, 强大的同时, 丢失了跨平台性 (不过现在也在逐渐拥抱开源)

  • C - 操作系统, 硬件/驱动; 如Linux, Kindle

    • 体型小, 可移植性好, 可被嵌入几乎一切处理器中, 可以运行在冰箱, 闹钟...中

    • 现代编程语言的始祖, 或多或少都有借鉴

    • 不具备 "运行时检查" 机制

    • 不支持 OOP , 因此 c++ 才会诞生

  • C++ - 操作系统, 搜索引擎, 视频游戏; 如Google搜索, outlook

    • 灵活自由, 操作内存/指针. 对于新手会是灾难

    • 对于于 C, 升级出了 OOP.

  • Java - 视频游戏, Android; 如 mineCraft

    • Android app 开发的基石

    • 占用大量内存, 开发时无需手都管理内存(GC)

    • spring framework, mybatis, springboot, springcloud

  • Go - 网络编程语言

    • 完整的开发工具链(命令)

    • 部署简单

    • native http 库, 内建的模板引擎

    • 优秀的并发模型(无需关心 锁)

  • JavaScript - 网站, 分析, web交互

    • 脚本语言

    • V8 引擎

    • nodejs 前后通吃

    • React, Vue 各种框架

    • 需要适配不同客户端/浏览器

  • PHP - wordpress 插件, 快速的 web开发, 包含数据库功能的页面; wordpress, 早期的Facebook

    • 脚本语言

    • 社区庞大

    • 速度快

    • 糟糕的错误处理机制

  • python - web开发, 视频游戏, 物联网, 机器学习, 爬虫; 如 YouTube, Instagram

    • 丰富的工具库

    • 脚本语言

  • ruby - web开发; 如 airbnb

    • 脚本语言

    • ruby on rails框架

    • 广泛的库, 社区强大

语句&函数(statement&function)

变量, 赋值语句, 条件控制语句, 循环

对多个statement打包 ---> function

参见yinwang：http://www.yinwang.org/blog-cn/2017/07/06/master-pl 重视语言特性而不是语言

语言特性：

变量定义
算术运算
for 循环语句，while 循环语句
函数定义，函数调用
递归
静态类型系统
类型推导
lambda 函数
面向对象
垃圾回收
指针算术
goto 语句

算法和数据结构

check here: {% post_link data-structure-and-algorithm 📚 数据结构和算法 %}

操作系统(Operation System)

批处理(batch processing)

计算机变得便宜变多, 有不同的配置, 写程序处理不同的硬件细节很痛苦, 操作系统出现 ==> 用来抽象硬件细节(操作系统提供api来操作硬件, 叫"硬件驱动程序")

冯·诺依曼体系结构​

计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成

数据的二进制表示​

  • 机器数 -- 真实数据在机器中的二进制表示, 用最高位0表示正、1表示负, 这是对于 "有符号机器数". "无符号机器数" 没有符号位

  • 真值 -- 用正负号表示的数称为“真值”

  • 编码 -- 真值表示成二进制字串的机器数的过程就称为编码

  • 原码 -- 符号位+真值的绝对值, 是否就是真值?存疑

    8bit 二进制数据表示范围: 正负2^7-1=127 (第一位位符号位)

  • 反码 - 正数反码是自身, 不变; 负数反码是 : 符号位不变, 其余各个位取反

  • 补码 - 正数的补码就是自身, 不变; 负数的补码, 符号位不变, 其余各个位取反, 最后 +1

  • 定点数与浮点数

    • 定点数是小数点固定的数 - 在计算机中没有专门表示小数点的位，小数点的位置是约定默认的。一般固定在机器数的最低位之后，或是固定在符号位之后;

      定点数表示法简单直观，但是数值表示的范围太小，运算时容易产生溢出。

    • 浮点数是小数点的位置可以变动的数 - 为增大数值表示范围，防止溢出，采用浮点数表示法。浮点表示法类似于十进制中的科学计数法。

  [+1] = [00000001]原 = [00000001]反 = [00000001]补

  [-1] = [10000001]原 = [11111110]反 = [11111111]补

  • 位："位(bit)"是电子计算机中最小的数据单位。每一位的状态只能是0或1。计算机进行数据处理和运算的单位为 32bit or 64bit

  • 字节：8个二进制位构成1个"字节(Byte)"，它是存储空间的基本计量单位。1个字节可以储存1个英文字母或者半个汉字，换句话说，1个汉字占据2个字节的存储空间。

  • 字节对齐

系统调用​

进程的执行在系统上的两个级别：用户级和核心级，也称为用户态和系统态(user mode and kernel mode)。

程序的执行一般是在用户态下执行的，但当程序需要使用操作系统提供的服务时，比如说打开某一设备、创建文件、读写文件等，就需要向操作系统发出调用服务的请求，这就是系统调用, 当进程发出系统调用之后，它所处的运行状态就会由用户态变成核心态, 但这个时候，进程本身其实并没有做什么事情，这个时候是由内核在做相应的操作

用户态, 系统态区别:

  • 用户态的进程能存取它们自己的指令和数据，但不能存取内核指令和数据（或其他进程的指令和数据）。然而，核心态下的进程能够存取内核和用户地址
  • 某些机器指令是特权指令，在用户态下执行特权指令会引起错误

并发​

check here: {% post_link java-concurrent 📚 java-concurrent %}

多任务​

问题: 如果让 CPU 只能运行一个程序，那么当 CPU 空闲下来（例如等待 I/O 时），CPU 就空闲下来了

改进: 使得每个程序运行一段时间之后，都主动让出 CPU 资源，这样每个程序在一段时间内都有机会运行一小段时间 ----- 这种程序协作方式 -> 分时系统（Time-Sharing System）

但是又有问题: 一个程序出错会影响整个系统

改进: 操作系统从最底层接管了所有硬件资源。所有的应用程序在操作系统之上以 进程（Process） 的方式运行，每个进程都有自己独立的地址空间，相互隔离; CPU 由操作系统统一进行分配。每个进程都有机会得到 CPU. 如果一个进程运行超过了一定时间，就会被暂停掉，失去 CPU 资源。这样就避免了一个程序的错误导致整个系统死机 ---------这种方式 -> 多任务（Multi-tasking）系统

进程​

就是一个执行中的程序, 有自己的内存区域, 资源.

进程的基本状态:

  • 等待态：等待某个事件的完成；
  • 就绪态：等待系统分配处理器以便运行；
  • 运行态：占有处理器正在运行

信号量​

信号量是一个确定的二元组（s，q）

  • s是一个具有非负初值的整形变量, 表示系统中某类资源的数目

    当其值 ≥ 0 时，表示系统中当前可用资源的数目

    当其值 < 0 时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目

  • q是一个初始状态为空的队列

过程: 类似 生产者 − 消费者 模式

  • 有一个进程执行 A(semaphore) 操作, semaphore 表示信号量 (s, q),这个操作会使得 资源数量 -1. 如果s >= 0, A 顺利执行; 如果 s < 0, 进程阻塞, 同时被加入 等待队列q;
  • 有一个进程执行 B(semaphore) 操作, .........................., 这个操作会使得资源数量 +1, 如果 s >= 0, 则进程继续执行, 如果 s < 0, 则处理往下执行外还会有额外操作: 从 等待队列q 中取出第一个被阻塞的进程, 使其变为 "就绪状态".

相当于一个升级版的 锁, 普通锁同一时刻只允许一个 thread 进入 某个资源, 信号量同一时刻允许多个 thread 进入 某个资源

内存管理&存储(memory&storage)​

程序可执行文件在内存中的结构​

一个程序的可执行文件在内存中的结果，可以分为两个部分：只读部分和可读写部分。只读部分包括程序代码（.text）和程序中的常量（.rodata）。可读写部分（也就是变量）大致可以分成下面几个部分

  • .data： 初始化了的全局变量和静态变量
  • .bss： 即 Block Started by Symbol， 未初始化的全局变量和静态变量
  • heap： 堆，使用 malloc, realloc, 和 free 函数控制的变量，堆在所有的线程，共享库，和动态加载的模块中被共享使用
  • stack： 栈，函数调用时使用栈来保存函数现场，自动变量（即生命周期限制在某个 scope 的变量）也存放在栈中。

data 和 bss 区​

他们都是用来存储全局变量和静态变量的，区别在于 data 区存放的是初始化过的， bss 区存放的是没有初始化过的

int val = 3;
char string[] = "Hello World";

- 这两个变量的值会一开始被存储在 .text 中（因为值是写在代码里面的），在
程序启动时会拷贝到 .data 中

static int i;
这个变量就会被放在 bss 区中。

attention: 静态变量和全局变量

在一个代码文件中，一个变量要么定义在函数中，要么定义在在函数外面。当定义在函数外面时，这个变量就有了全局作用域，成为了全局变量。全局变量不光意味着这个变量可以在整个文件中使用，也意味着这个变量可以在其他文件中使用. 此为前提.

如果在不同的代码文件定义了同名的全局变量, 在 Link 过程中会产生重复定义错误, 为了避免这种情况，就需要引入 static

静态变量： 指使用 static 关键字修饰的变量，static 关键字对变量的作用域进行了限制，具体的限制如下: (针对 c, go等来说, Java 相当于跟class类文件绑定了, 不属于对象实例)

  • 在函数外定义：全局变量，但是只在当前文件中可见
  • 在函数内定义：全局变量，但是只在此函数内可见
  • 在类中定义：全局变量，但是只在此类中可见

stack-栈​

栈是一块连续的内存区域，栈顶的地址和栈的最大容量是系统预先规定好的。

栈是用于存放本地变量，内部临时变量以及有关上下文的内存区域; 程序在调用函数时，操作系统会自动通过压栈和弹栈完成保存函数现场等操作，不需要程序员手动干预

能从栈获得的空间较小。如果申请的空间超过栈的剩余空间时，例如递归深度过深，将提示stackoverflow。

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持, 压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。

heap-堆​

堆是用于存放除了栈里的东西之外所有其他东西的内存区域

对于堆来说，释放工作由程序员控制，容易产生memory leak(泄漏)

计算机底层并没有对堆的支持，堆则是C/C++函数库提供的，同时由于频繁的new/delete势必会造成堆内存空间的不连续，从而造成大量的碎片，都会导致堆的效率比栈要低。

磁盘调度算法​

文件系统(file system)​

参考 linux-note

计算机网络

参考 tcp-ip-note

编译原理

词法分析器 语法分析器 语义分析及中间代码生成 代码优化 代码生成

各种编码

utf-8 是否需要带 bom

UTF-8 不需要 BOM，尽管 Unicode 标准允许在 UTF-8 中使用 BOM。 所以不含 BOM 的 UTF-8 才是标准形式，在 UTF-8 文件中放置 BOM 主要是微软的习惯（顺便提一下：把带有 BOM 的小端序 UTF-16 称作「Unicode」而又不详细说明，这也是微软的习惯）。 BOM（byte order mark）是为 UTF-16 和 UTF-32 准备的，用于标记字节序（byte order）。微软在 UTF-8 中使用 BOM 是因为这样可以把 UTF-8 和 ASCII 等编码明确区分开，但这样的文件在 Windows 之外的操作系统里会带来问题。

「UTF-8」和「带 BOM 的 UTF-8」的区别就是有没有 BOM。即文件开头有没有 U+FEFF。