数据链路层

多路访问控制(MAC)协议

两类链路:

  • 点对点链路:拨号接入的PPP,以太网交换机与主机间的点对点链路
  • 广播链路(共享介质):早期的总线以太网,HFC的上行链路,802.11无限局域网

单一共享广播信道

两个或两个以上节点同时传输:干扰,产生冲突,导致接受失败

多路访问控制协议(multiple access control protocol)

  • 采用分布式算法决定节点如何共享信道,即决策节点何时可以传输数据
  • 必须基于信道本身,通信信道共享协调信息

MAC协议分类

  1. 信道划分 (channel partitioning) MAC协议
    • 多路复用技术
    • TDMA,FDMA,CDMA,WDMA等
  2. 随机访问 (random access) MAC协议
    • 信道不划分,允许冲突
    • 采用冲突“恢复”机制
  3. 轮转 (taking turns) MAC协议
    • 节点轮流使用信道(保证节点在使用信道时不冲突,同时在使用的时候用的是信道的全部带宽)

信道划分MAC协议

TDMA: time division multiple access

  1. “周期性”接入信道
  2. 每个站点在每个周期占用固定长度的时隙(这里的长度是指分组传输时间)
  3. 未用的时隙空闲(idle)
  4. 例如,6-slot的LAN,1、3、4传输分组,2、5、6空闲

FDMA: frequency division multiple access

  1. 信道频谱划分为若干频带(frequency bands)
  2. 每个站点分配一个固定的频带
  3. 没有传输数据的频带空闲
  4. 例如,6站点LAN,1、3、4频带传输数据,2、5、6频带空闲

随机访问MAC协议

当节点要发送分组时,利用信道全部数据速率R发送分组,没有事先的节点间协调。

会发生冲突。

随机访问MAC协议需要定义:如何检测冲突、如何从冲突中恢复(通过延迟重传)

典型的随机访问MAC协议:

  • 时隙(sloted)ALOHA
  • ALOHA
  • CSMA, CSMA/CD, CSMA/CA

时隙ALOHA协议

假定:

  • 所有帧大小相同
  • 时间被划分为等长的时隙(每个时隙可以传输1个帧)
  • 节点只能在时隙开始时刻发送帧
  • 节点间时钟同步
  • 如果2个及以上的节点在同一时隙发送帧,则检测到冲突

运行:

  • 当节点有新的帧时,在下一个时隙(slot)发送
  • 如果无冲突:该节点可以在下一个时隙继续发送新的帧
  • 如果冲突,该节点在下一个时隙以概率p重传该帧,直至成功

优点:

  • 单个节点活动时,可以连续以信道全部速率传输数据
  • 高度分散化:只需同步时隙
  • 简单

缺点:

  • 冲突,浪费时隙
  • 时钟同步
  • 空闲时隙
  • 节点也许能以远小于分组传输的时间检测到冲突

非时隙ALOHA

更加简单,无需同步

当有新的帧生成时,立即发送

因此比时隙ALOHA协议更差。

CSMA协议

载波监听多路访问协议CSMA(carrier sense multiple access)

发送帧之前,监听信道(载波):

  • 信道空闲:发送完整帧
  • 信道忙:推迟发送

    • 1-坚持CSMA
    • 非坚持CSMA
    • P-坚持CSMA
  • 冲突可能仍然发生:存在信号传播延迟

CSMA/CD协议

CSMA/CD: CSMA with Collision Detection

  • 短时间内可以检测到冲突
  • 冲突后传输中止,减少信道浪费

冲突检测:

  • 有线局域网易于实现:测量信号强度,比较发射信号与接收信号
  • 无线局域网很难实现:接收信号强度淹没在本地发射信号强度下

网络带宽:R bps

数据帧最小长度:$L_min$ (bits)

信号传播速度:V(m/s)

“边发边听,不发不听”

主机A、B之间的距离是$d_{max}$,A向B发送数据帧,快到达B时,B又向A发送了一个数据帧,两者在靠近B的地方相遇,于是发生了冲突。A发送的数据帧到达B时,B检测到了冲突,但此时B发送的数据帧还未到达A,因此A还没有检测出冲突。最后,两者都检测到冲突时,用了$2d_{max}/V$的时间。

满足:$L/R >= 2d_{max}/V$

那么:

$L_{min}/R >= 2d_{max}/V$

$L_{min}/R = RTT_{max}$

$t_{prop}$趋近于0或$t_{trans}$趋近于∞时,效率趋近于1.

远优于ALOHA,并且简单、分散。

ARP协议

MAC地址

32位IP地址:

  • 接口的网络层地址
  • 用于标识网络层(第3层)分组,支持分组转发

MAC地址(或称LAN地址,物理地址,以太网地址)

  • 作用:用于局域网内标识一个帧从哪个接口发出,到达哪个物理相连的其他接口
  • 48位MAC地址(用于大部分LANs),固化在网卡的ROM中,有时也可以软件设置
  • 将48bits分为6个字节,16进制表示,e.g.: 1A-2F-BB-76-09-AD

局域网中的每块网卡都有一个唯一的MAC地址。

MAC地址由IEEE统一管理与分配。

网卡生产商购买MAC地址空间(前24比特),后24比特生产商依次分配。

类比:

  • MAC地址:身份证号
  • IP地址:邮政地址
  • MAC地址是“平面”地址,可”携带“,可以从一个LAN移到另一个LAN
  • IP地址是层次地址,不可“携带”,IP地址依赖于节点连接到哪个子网

ARP:地址解析协议

在同一个LAN内,如何在已知目的接口的IP地址前提下确定其MAC地址?

ARP表:LAN中每个IP节点(主机、路由器)维护一个表

  • 存储某些LAN节点的IP/MAC地址映射关系。如:
  • 存活时间TTL(time to live):经过这个时间后,该映射关系会被遗弃(典型时间是20min)

ARP协议:同一局域网内

  • A想要向同一局域网中的B发送数据报,但B的MAC地址不在A的ARP表中
  • A广播ARP查询分组,其中包含B的IP地址。LAN中所有节点都会接收到ARP查询。
  • B也接收到了,IP地址匹配成功,B向A应答B的MAC地址。利用单播帧向A发送应答。
  • A在自己的ARP表中缓存B的IP-MAC地址对,直至超时。超时后,再次刷新。
  • ARP是“即插即用”协议,节点自主创建ARP表,无需干预。

约束与触发器

完整性约束

删除/更新具有引用关系的表时,有以下操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
-- 被引用的行禁止删除
on delete restrict

-- 级联,被引用行删除时,引用行也一起删除;即子表里的行跟着父表里相应的行一起删除
on delete cascade

-- 被引用行删除时,引用行不做什么处理
no action

-- 被引用行禁止更新
on update restrict

-- 被引用行更新时,引用行自动更新
on update cascade


create table so_items(
item_id int not null,
so_id int references so_headers(id) on delete restrict,
product_id int,
net_price numeric,
primary key(item_id,so_id)
);

create table so_items(
item_id int not null,
so_id int references so_headers(id) on delete cascade,
product_id int,
net_price numeric,
primary key(item_id,so_id)
);

外键约束的几种方法:

方法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
create table so_headers(
id serial primary key,
customer_id int,
ship_to varchar(255)
);

-- 在创建表时,作为外键的列后面直接依赖父表列
create table so_items(
item_id int not null,
so_id int references so_headers(id),
product_id int,
net_price numeric,
primary key(item_id,so_id)
);

方法2:

1
2
3
4
5
6
7
8
9
10
-- 创建表时,在末尾指定外键约束
create table so_items(
item_id int not null,
so_id int,
product_id int,
net_price numeric,
primary key(item_id,so_id),
foreign key(so_id) references so_headers(id)
);
-- 【注】:如果没有指定外键别名,则默认的外键别名为:"表名_列名_fkey"

方法3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- 创建表时,在末尾指定外键约束,并且指定外键别名;so_id_fkey
create table so_items(
item_id int not null,
so_id int,
product_id int,
net_price numeric,
primary key(item_id,so_id),
constraint so_id_fkey foreign key(so_id) references so_headers(id)
);


-- 多个主键建立外键约束
create table child_table(
c1 int primady key,
c2 int,
c3 int,
primary key(c2,c3) references 父表(p1,p2)
);

方法4:

1
2
3
4
5
6
-- 修改表添加外键约束
alter table 表名 add constraint 外键别名 foreign key(列名) references 父表(列名);


-- 删除外键约束
alter table 表名 drop constraint 外键别名;

DEFERRABLE

推迟约束

触发器

触发器(trigger)是用户定义在关系表上的由事件驱动调用函数的机制。

触发器比CHECK更灵活,可以实施各种复杂的检查和操作,具有更精细和更强大的数据保护能力。

在创建触发器之前,必须首先创建触发器函数,触发器函数的语法格式是:

1
2
3
4
5
6
CREATE FUNCTION function_name() RETURNS TRIGGER AS $$
DECLARE 变量声明;
BEGIN
函数执行代码
END;
$$ LANGUAGE plpgsql;

触发器中有两对前是函数头部。触发器函数定义的头部RETURNS后面只能是TRIGGER,并且触发器函数不能带任何参数。

两对$$之间是函数体。包括DECLARE部分的变量声明以及BEGIN和END之间的函数执行代码。DECLARE部分是可选的。

由于PG允许使用各种语言比如PL/pgSQL,C,Python来编写函数,所以第二对$$之后是对函数编写语言的说明。这里是PL/pgSQL。

触发器函数创建后,使用CREATE TRIGGER命令创建触发器。

1
2
3
4
5
CREATE TRIGGER name {BEFORE|AFTER} {event [OR...]}
ON TABLE YYY
[FOR [EACH] {ROW|STATEMENT}]
[WHEN {condition}]
EXECUTE PROCEDURE function_name();

{event [OR…]}中,{}里面是一个或多个用OR分隔的事件列表。这里的事件包括数据库的数据修改操作,比如INSERT、DELETE或UPDATE等命令。

BEFORE|AFTER的意思是触发器可以分为BEFORE和AFTER触发器,分别在操作完成前和操作完成后执行触发器函数。

ON TABLE后面给出触发器所在表的表名。

触发器可以按行或按语句触发,也就是行级触发器和语句级触发器。

行级:[FOR [EACH] {ROW|STATEMENT}]

语句级:[FOR [EACH] {STATEMENT}]

行级触发器的触发器函数为触发语句影响的每一行执行一次。

语句级触发器的触发器函数为每条触发语句执行一次。

假设表examiner有10000行,定义了如下的UPDATE触发器:

1
UPDATE examiner SET erage = erage + 1;

如果是语句级触发器,则执行完该语句后,触发动作只发生1次;如果是行级触发器,则执行10000次。

触发器必须返回一个NULL或者一个元组类型的变量。

语句级触发器应返回NULL。

行级after触发器的值总是被忽略,可以返回null。

行级before触发器的返回值不同,对触发器操作的影响也不同。

如果返回NULL则忽略该触发器的行级操作,其后的触发器也不会执行。

如果返回非NULL,则返回的行将成为被插入或更新的行。

如果是行级触发器,可以在触发器函数中使用NEW和OLD引用UPDATE/INSERT事件之后的新值和UPDATE/DELETE事件之前的旧值。

插入examinee表的考号长度必须为10位:

创建触发器函数:

1
2
3
4
5
6
7
8
9
10
CREATE FUNCTION examineeid() RETURNS TRIGGER AS $examineeid$
BEGIN
IF(CHAR_LENGTH(new.eeid)<>10) THEN
RAISE EXCEPTION '格式错误';
RETURN NULL;
ELSE
RETURN NEW;
END IF;
END
$examinee$ LANGUAGE plpgsql;

NEW代表INSERT或UPDATE操作产生的新的数据行

创建触发器:

1
2
CREATE TRIGGER examineeid_insert BEFORE INSERT ON examinee
FOR EACH ROW EXECUTE PROCEDURE examineeid();

三种:

1.DEFERRABLE INITIALLY DEFERRED

2.DEFERRABLE INITIALLY IMMEDIATE

3.NOT DEFERRABLE

1
Copy"subject_iddddd" INTEGER REFERENCES "Subjects" ("id") DEFERRABLE INITIALLY IMMEDIATE

注1:IMMEDIATE 会在每一个语句执行后进行约束检查,DEFERRED 则只会在事务结束时才检查约束。(DEFERRED 只是推迟检查而不是不检查)

注2:此设置仅影响 UNIQUE,PRIMARY KEY,REFERENCES (外键)和 EXCLUDE 约束

1
SET CONSTRAINTS { ALL | name [, ...] } { DEFERRED | IMMEDIATE }

注1:NOT DEFERRABLE 来说,SET CONSTRAINTS 不生效。

注2:SET CONSTRAINTS ALL 更改所有 DEFERRABLE 约束。

网络层

网络层服务

从发送主机向接收主机传送数据段

发送主机:将数据段封装到数据报中。

接收主机:向传输层交付数据段。

每个主机和路由器都运行网络层协议。

路由器检验所有穿越它的IP数据报的头部域。

网络层核心功能

转发与路由

转发(forwarding):将分组从路由器的输入端口转移到合适的输出端口。

每个路由器维护一张转发表,转发表确定本路由器如何转发分组。

转发表的内容:地址-输出链路,如0100-3, 0101-2, 0111-2, 1001-1.

取出收到的数据报的地址信息,然后查转发表得到输出链路。

路由(routing):确定分组从源到目的经过的路径。

如何得到路由信息?

网络层设备都会运行一些路由协议,或路由算法(routing algorithms),根据路由算法确定通过网络的端到端路径。

连接的建立

数据分组传输之前两端主机需要首先建立虚拟/逻辑连接,网络设备(如路由器)参与连接的建立。

网络层连接与传输层连接的对比:

  • 网络层连接:两个主机之间的连接,并且在路径上的每个网络层设备都要参与建立连接。
  • 传输层连接:两个应用进程之间的连接(端到端的连接,对中间网络设备透明)。

网络层为发送端(主机)到接收端(主机)的数据报传送”通道(channel)”提供怎样的服务模型(service model)?

不同的网络架构(Network Architecture)提供的服务模型是不一样的。例如Internet提供的是best effort服务模型,不保障Bandwidth, Loss, Order或Timing,通过数据是否丢失来判断拥塞(congestion)。ATM的服务模型有CBR,VBR,ABR,UBR。

网络层服务模型

  • 无连接服务(connection-less service):
    • 不事先为系列分组的传输确定传输路径
    • 每个分组独立确定传输路径
    • 不同分组可能传输路径不同
    • 数据报网络(datagram network)
  • 连接服务(connection service):
    • 首先为系列分组的传输确定从源到目的经过的路径(建立连接)
    • 然后沿该路径(连接)传输系列分组
    • 系列分组传输路径相同
    • 分组传输顺序可以保证
    • 传输结束后拆除连接
    • 虚电路网络(virtual-circuit network)

虚电路网络和数据报网络

虚电路网络

数据报网络和虚电路网络是典型的两类分组交换网络

数据报网络提供网络层无连接服务。

虚电路网络提供网络层连接服务。

类似于传输层的无连接服务(UDP)和面向连接服务(TCP),但是网络层服务:

  1. 是主机到主机的服务
  2. 网络核心实现(传输层是端到端实现)

虚电路:一条从源主机到目的主机,类似于电路的路径(逻辑连接)。

  • 分组交换
  • 每个分组的传输利用链路的全部带宽
  • 源到目的路径经过的网络层设备共同完成虚电路功能

  • 通信过程:呼叫建立(call setup)——数据传输——拆除呼叫

  • 每个分组携带虚电路标识(VCID),而不是目的主机地址
  • 虚电路经过的每个网络设备(如路由器),都要维护每条经过它的虚电路的连接状态
  • 链路、网络设备资源(如带宽、缓存等)可以面向VC进行预分配
    • 预分配资源 = 可预期服务性能
    • 如ATM的电路仿真(CBR)

每条虚电路包括:

  1. 从源主机到目的主机到一条路径

  2. 虚电路号(VCID),沿路每段链路一个编号

    链路带宽越大,允许建立的虚电路的数量就越大。

    同一条虚电路在每一段链路上的VCID可能是不一样的。

  3. 沿路每个网络层设备(如路由器),利用转发表记录经过的每条虚电路。

沿某条虚电路传输的分组,携带对应虚电路的VCID,而不是目的地址。

同一条VC,在每段链路上的VCID通常不同:

  • 路由器转发分组时依据转发表改写/替换虚电路号

虚电路信令协议(signaling protocols)

用于VC的建立、维护与拆除:路径选择

应用于虚电路网络:如ATM、帧中继(frame-relay)网络等

目前的Internet不采用。

初识呼叫——呼叫到达——接受呼叫——呼叫建立——数据流开始——接收数据

通信结束后,也通过虚电路信令协议进行呼叫的拆除。

数据报网络

网络层无连接

每个分组携带目的地址

路由器根据分组的目的地址转发分组:

  • 基于路由协议/算法构建转发表
  • 检索转发表
  • 每个分组独立选路
  • 每个分组走的路径可能不一样,因为如果在传输过程中路由器更新了转发表,那么后面的分组就会走新的路径

数据报中含有目的主机的IP地址。但是IP地址是32位的二进制数,一共有2^32种不同情况,严重降低了传输效率。解决方法是:转发表中的目的地址不是一个明确的地址,而是一个地址范围。这样就将许多具有共同列表地址的转发表进行了聚合。

目的地址范围的匹配采用最长前缀匹配优先(在检索转发表时,优先选择与分组目的地址匹配前缀最长的入口[entry])。

Internet(数据报网络)

  • 计算机之间的数据交换:”弹性”服务,没有严格时间需求。
  • 链路类型众多:特点、性能各异,统一服务困难。
  • “智能”端系统:可以自适应、性能控制、差错恢复
  • 简化网络,复杂”边缘”

ATM(VC网络)

  • 电话网络演化而来
  • 核心业务是实时对话:严格的时间、可靠性需求,需要有保障的服务。
  • “哑”端系统(非智能):电话机、传真机
  • 简化”边缘”,复杂网络

IPv4协议

Internet网络层

主要功能就是路由和转发。

主机、路由器网络层主要功能:

  • 路由协议:路径选择,如RIP,OSPF,BGP
  • 转发表(路由表)
  • IP协议:寻址规约(conventions),数据报(分组)格式,分组处理规约
  • ICMP协议(互联网控制报文协议):差错报告,路由器”信令协议”
  • 实现IP协议,通常也要实现ICMP协议。后者可以看做是前者的一个伴随协议。

IP数据报(分组)格式

IP数据报格式:首部 + 数据(e.g. TCP, UDP段)

数据报长度是32位,即从0到31位。

首部(固定部分5行、可变部分1行)

数据(1行)

首部分为固定部分和可变部分。

固定部分:

版本号(4位,0~3),首部长度,服务类型(TOS),总长度

标识,标识位,片偏移

生存时间(TTL),协议,首部检验和

源IP地址

目的IP地址

可变部分:

选项字段(长度可变),填充

  1. 版本号:4位,如果是IPv4就是4,如果是IPv6就是6。

  2. 首部长度:4位。是IP分组的首部长度。

    • 以4字节为单位(1行32比特,刚好4字节)
    • IP固定部分首部长度为5*4=20字节
    • 最典型的,例如是IPv4协议,那么版本号是0100(4d),首部长度0101(5d)。
  3. 服务类型(TOS):8位,指示期望获得哪种类型的服务。
    • 1998年这个字段改名为区分服务
    • 只有在网络提供区分服务(DiffServ)时使用
    • 一般情况下不使用,通常IP分组的该字段(第2字节)的值为00H
  4. 总长度:16位,是IP分组的总字节数(首部+数据)
    • 最大IP分组的总长度:65535B
    • 最小的IP分组首部:20B(可变部分为0)
    • IP分组可以封装的最大数据:65535-20=65515B
    • 当然在实际中不会达到最大数据,因为一定会将它切分的。
  5. 生存时间(TTL):8位,是IP分组在网络中可以通过的路由器数(或跳步数)
    • 路由器转发一次分组,TTL减一
    • 如果TTL=0,则路由器丢弃该IP分组
  6. 协议:8位,指示IP分组封装的是哪个协议的数据包
    • 实现复用/分解
    • 6为TCP,表示封装的是TCP段;17为UDP,表示封装的是UDP数据报
  7. 首部校验和:16位,实现对IP分组首部的差错检测
    • 计算校验和时,该字段置为全0
    • 采用反码算数运算求和,和的反码作为首部校验和字段
    • 逐跳计算、逐跳检验
  8. 源IP地址、目的IP地址字段各占32位

IP分片

网络链路存在MTU(最大传输单元)——链路层数据可封装数据的上限。不同链路的MTU不同。

大IP分组向较小MTU链路转发时,可以被”分片”(fragmented)。

IP分片到达目的主机后进行”重组”(reassembled)。

路由器对IP分组只分片不重组。

如果此路由器不让分片,那么就把这个IP分组丢掉,一般地会再发一个ICMP的分组(具体是怎样再查查,这里只是粗略记录)。

IP首部中的总长度、标识、标识位和片偏移用来标识分片以及确定分片的相对顺序。

标识字段:16位,用于标识一个IP分组

  • IP协议利用一个计数器,每产生一个IP分组,计数器就加一,利用此时计数器的值和其他一些信息唯一标识该IP分组

标识位:3位

IP编址

接口:主机/路由器与物理链路的连接

  • 实现网络层功能
  • 路由器通常有多个接口
  • 主机通常只有一个或两个接口(有线的以太网接口,无限的802.11接口)

IP地址:32比特(IPv4)编号用于标识主机、路由器的接口

一般用点分十进制的方式表示。

11011111 00000001 00000001 00000001 = 233.1.1.1

一个IP地址唯一标识一个接口。

IP地址与每个接口关联。

IP子网(subnets)

IP地址:

  • 网络号(NetID) - 高位比特
  • 主机号(HostID) - 低位比特

NetID HostID

233.1.1 .1

相同的网络号构成IP子网。

IP子网:

  • IP地址具有相同网络号的设备接口
  • 不跨越路由器(第三及以上层网络设备)可以彼此物理联通的接口

“有类”编址:

A类地址,50%:NetID(8位) + HostID(24位)

0.0.0.0 ~ 127.255.255.255

B类地址,25%:NetID(16位) + HostID(16位)

128.0.0.1 ~ 191.255.255.255

C类地址,12.5%:NetID(24位) + HostID(8位)

192.0.0.0 ~ 223.255.255.255

D类地址,6.25%:32位,1110

224.0.0.0~239.255.255.255

E类地址,6.25%:32位,1111

240.0.0.0~255.255.255.255

IP子网划分与子网掩码

子网划分:

IP地址——网络号(NetID) + 子网号(SubID) + 主机号(HostID)

就是将刚才的主机号划分为了:子网号(SubID) + 主机号(HostID)。即 子网号是原主机号的部分比特。

子网划分定义:Internet组织机构定义了五种IP地址,有A、B、C三类地址。A类网络有126个,每个A类网络可能有16777214台主机,它们处于同一广播域。而在同一广播域中有这么多节点是不可能的,网络会因为广播通信而饱和,结果造成16777214个地址大部分没有分配出去。可以把基于每类的IP网络进一步分成更小的网络,每个子网由路由器界定并分配一个新的子网网络地址,子网地址是借用基于每类的网络地址的主机部分创建的。划分子网后,通过使用掩码,把子网隐藏起来,使得从外部看网络没有变化,这就是子网掩码。

比如,当一组IP地址指定给一个公司时,公司可能将该网络“分割成”小的网络,每个部门一个。这样,技术部门和管理部门都可以有属于它们的小网络。通过划分子网,我们可以按照我们的需要将网络分割成小网络。这样也有助于降低流量和隐藏网络的复杂性。

子网掩码:

形如IP地址:32位,点分十进制形式

取值:NetID, SubID位全取1,HostID全取0

例如:

A网的默认子网掩码为:255.0.0.0

B网的默认子网掩码为:255.255.0.0

C网的默认子网掩码为:255.255.255.0

借用3比特划分子网的B网的子网掩码为:255.255.224.0 (224就是11100000)

子网地址+子网掩码 —— 准确确定子网大小

将IP分组的目的IP地址与子网掩码按位与运算,提取子网地址。

CIDR与路由聚集

无类域间路由(CIDR: Classless InterDomain Routing)

  • 消除传统的A、B、C类地址界限:将NetID和SubID合在一起变成Network Prefix(Prefix),即统称为网络前缀,并且可以任意长度

  • 融合子网地址与子网掩码,方便子网划分

    无类地址格式:a.b.c.d/x,其中x为前缀长度

11001000 00010111 00010000 00000000

前面是前缀(长为8+8+7=23),后面是主机号HostID。

写成CIDR地址形式就是200.23.16.0/23。

优势

  • 提高IPv4地址空间分配效率
  • 提高路由效率
    • 将多个子网聚合为一个较大的子网
    • 构成超网
    • 路由聚合(route aggregation)

DHCP协议

如何获得IP地址?

  • “硬编码”:静态配置

  • 动态主机配置协议 - DHCP:Dynamic Host Configuration Protocol

    从服务器动态获取:IP地址、子网掩码、默认网关地址、DNS服务器名称与IP地址

    “即插即用”

    允许地址重用

    支持在用地址续租

    支持移动用户加入网络

动态主机配置协议DHCP

  1. 主机广播”DHCP discover”(发现报文)等待是否有DHCP服务器响应
  2. DHCP服务器利用”DHCP offer”(提供报文)进行响应,告诉客户端自己可以提供的一个IP地址
  3. 主机请求IP地址:客户端向服务器发送”DHCP request”(请求报文)表示愿意接受这个IP地址同时请求服务器将它真正分配给自己
  4. DHCP服务器分配IP地址:服务器向客户端发送”DHCP ack”(确认报文)表示确认分配

DHCP协议在应用层实现:

  • 请求报文封装到UDP数据报中
  • IP广播
  • 链路层广播(例如,以太网广播)

DCHP服务器内建于服务器中。

DHCP服务器构造ACK报文,包括分配给客户的IP地址、子网掩码、默认网关、DNS服务器地址。

NAT网络地址转换

本地网络内通信的IP数据报的源与目的IP地址均在子网10.0.0/24(显然这是一个私有地址,比如说是家庭网络)内。

所有离开本地网络去往Internet的数据报的源IP地址需要替换为相同的NAT IP地址(例如138.76.29.7)以及不同的端口号。

动机:

  • 只需从ISP申请一个IP地址,因此面临IPv4地址耗尽
  • 本地网络设备IP地址的变更,无需通告外界网络
  • 变更ISP时,无需修改内部网络设备IP地址
  • 内部网络设备对外界网络不可见,即不可直接寻址

实现:

  • 替换:利用(NAT IP地址,新端口号)替换每个外出IP数据报的(源IP地址,源端口号)
  • 记录:将每对(NAT IP地址,新端口号)与(源IP地址,源端口号)的替换信息存储到NAT转换表中
  • 根据NAT转换表,用(源IP地址,源端口号)替换每个进入内网IP数据报的(目的IP地址,目的端口号)

NAT转换表包含:WAN端地址、LAN端地址。

NAT穿透问题:外部设备期望连接内网地址的服务器

方法1: 静态配置NAT(转换表),将特定端口的连接请求转发给服务器。

方法2: 利用UPnP(Universal Plug and Play)互联网网关设备协议(IGD-Internet Gateway Device)自动配置:学习到NAT公共IP地址,在NAT转换表中增删端口映射。

方法3: 中继(如Skype)

互联网控制报文协议ICMP

Internet Control Message Protocol支持主机或路由器

差错或异常报告

网络探询

两类ICMP报文:

差错报文

IPv6

最初动机:32位IPv4地址空间已分配殆尽

其他动机:改进首部格式:快速处理/转发数据报,支持QoS

IPv6数据报格式:

  • 固定长度的40字节基本首部
  • 不允许分片

虽然首部没有可选项、是固定长度,但是有可选的扩展首部。

IPv6数据报格式:

基本首部,扩展首部1,扩展首部2,…,扩展首部N,数据部分(例如TCP段)

路由算法

路由算法(协议)确定最佳路径,转发表确定在本路由器如何转发分组。

路由算法分类

静态路由&动态路由

静态路由:

  • 手工配置
  • 路由更新慢
  • 优先级高

动态路由:

  • 路由更新快
    • 定期更新
    • 及时响应链路费用或网络拓扑结构变化
  • 由路由算法计算出来的

全局信息&分散信息

全局信息:

  • 所有路由器掌握完整的网络拓扑和链路费用信息。
  • 链路状态(LS)路由算法

分散信息:

  • 路由器只掌握物理相连的邻居以及链路费用。
  • 距离向量(DV)路由算法

链路状态路由算法

Dijkstra算法

  • c(x, y): 结点x到结点y的链路费用;如果x和y不直接相连,则为∞。

  • D(v): 从源到目的v的当前路径费用值。

  • p(v): 沿从源到v的当前路径,v的前序结点集合。
  • N’: 已经找到最小费用路径的结点集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
初始化:
N'= {u}
for 所有结点v
if v nextTo u
D(v) = c(u, v)
else
D(v) = ∞

循环:
找出不在N'中的结点w,使得D(w)最小
将w加入N'
更新w的所有不在N'中的邻居v的D(v): D(v) = min{c(v, w)+D(w), D(v)}
until 所有结点都在N'中

但是存在振荡现象。

距离向量路由算法

Bellman-Ford方程(动态规划)

  • Dx(y) := 从x到y最短路径的费用(距离)
  • Dx(y) = min{c(x, v) + Dv(y)}

异步迭代:

  • 引发每次局部迭代的因素:
    • 局部链路费用改变
    • 来自邻居的DV更新

分布式:

  • 每个结点只当DV变化时才通告给邻居

无穷计数问题

层次路由

将任意规模网络抽象为一个图计算路由——过于理想化。

标识所有路由器

“扁平”网络

网络规模巨大时,交换量会占用所有网络带宽。

聚合路由器为一个区域:自治系统AS

Internet路由

AS内部路由:

  • Internet采用层次路由
  • AS内部路由协议也称为内部网络协议IGP(interior gateway protocol)
  • 最常见的AS内部路由协议:
    • 路由信息协议:RIP(Routing Information Protocol)
    • 开放最短路径优先:OSPF(Open Shortest Path First)
    • 内部网关路由协议:IGRP(Interior Gateway Routing Protocol)
      • Cisco私有协议

RIP

早于1982年随BSD- UNIX操作系统发布

跳数指从源端口到达目的端口所经过的路由个数,每经过一个路由器,跳数加1 。数据包经过一台路由器就是一跳,经过的路由器数量,就是它的跳数。

距离向量路由算法:

  • 距离度量:跳步数(max = 15hops),每条链路1个跳步
  • 每隔30秒,邻居之间交换一次DV,成为通告(advertisement)
  • 每次通告:最多25个目的子网(IP地址形式)

LINK

OSPF(Open Shortest Path First)协议:

  • 开放:公众可用
  • 采用链路状态路由算法

Don’t let anyone rush yourself with their timelines.

传输层

传输层服务的基本理论和基本机制:

  • 多路复用/分用
  • 可靠数据传输机制
  • 流量控制机制
  • 拥塞控制机制

Internet的传输层协议

  • UDP: 无连接传输服务
  • TCP: 面向连接的传输服务
  • TCP拥塞控制

主机上运行着五层Internet协议栈,有应用层、传输层、网络层、数据链路层和物理层;路由器上只有三层协议栈,即网络层及以上的是没有的。

传输层协议为运行在不同host上的进程提供了一种逻辑通信机制

逻辑通信机制,就是指进程之间仿佛是直接连接的,不需要关心有多远的物理距离、经过了多少个路由器、使用的是什么物理媒介。

端系统运行传输层协议:

  • 发送方:将应用递交的消息分成一个或多个的segment,并向下传给网络层。
  • 接收方:将接收到的segment组装成消息,并向上交给应用层。

传输层可以为应用提供多种协议:

  • Internet上的TCP
  • Internet上的UDP

比较

  • 网络层:提供主机之间的逻辑通信机制

  • 传输层:提供应用进程之间的逻辑通信机制

    — 位于网络层之上(IP),依赖于网络层服务,对网络层进行(可能的)增强

Internet传输层协议

可靠、按序的交付服务(TCP)

  • 拥塞控制
  • 流量控制
  • 连接建立

不可靠的交付服务(UDP)

  • 基于”尽力而为 (best-effort) “的网络层,没有做(可靠性方面的)扩展

两种服务均不提供:延迟、带宽

多路复用和多路分用

为什么要多路复用/分用?

  • 如果某层的一个协议对应直接上层的多个协议/实体,则需要复用/分用。

socket是应用层和传输层之间的”门”。

接收端进行多路分用:传输层依据头部信息将收到的segment交给正确的socket,即不同的进程。

发送端进行多路复用:从多个socket接收数据,为每块数据封装上头部信息,生成segment,交给网络层。

分用——如何工作?

主机接收到 IP 数据报(datagram)

  • 每个数据报携带源 IP 地址、目的 IP 地址
  • 每个数据报携带一个传输层的段(segment)
  • 每个段携带源端口号和目的端口号

TCP/UDP 段格式:

|——————- 32 bits ——————-|

| 源端口号 | 目的端口号 |

| 其他头部信息 |

| 应用数据 (message) |

主机收到segment后,传输层协议提取IP地址和端口号信息,将segment导向相应的socket。(网络层是不关心端口号信息的)TCP会做更多的处理。

无连接分用

UDP的socket用二元组标识(目的IP地址,目的端口号)

主机收到UDP段后:

  • 检查段中的目的端口号
  • 将UDP段导向绑定在该端口号的socket

来自不同源IP地址和/或源端口号的IP数据包被导向同一个socket。

面向连接分用

TCP的socket用四元组标识:

  • 源IP地址
  • 源端口号
  • 目的IP地址
  • 目的端口号

接收端利用所有的4个值将segment导向合适的socket。

服务器可能同时支持多个TCP socket。每个socket用自己的四元组标识。

web服务器为每个客户端开不同的socket。

也就是说,例如host B中的进程1向host A发起TCP连接,SP(source port)是9157,DP是80;进程2也发起TCP连接,SP是5775,DP是80;两个进程的S-IP和D-IP相同,都是B和A。但是socket不同,服务器为每个客户端开不同的socket。进程1对应socket1,进程2对应socket2。服务器上的这两个socket的SP相同,都是80,S-IP和D-IP也分别相同,但是DP不同,分别是5775和9157.

UDP

User Datagram Protocol [ RFC 768 ]

基于Internet IP协议:

  • 复用/分用
  • 简单的错误校验(因为路由器在存储转发的过程中也可能会出错)

UDP提供的是”Best effort”服务,所以会丢失、非按序到达。

每个UDP段的处理独立于其他段。

UDP为什么存在?

  • 无需建立连接(减少延迟,因此DNS使用的是UDP)
  • 实现简单:无需维护连接状态
  • 头部开销少(UDP头部8个字节,而TCP是20个字节)
  • 没有拥塞控制:应用可以更好地控制发送时间和速率(TCP有拥塞控制,会根据实际情况自动调整发送时间和速率)

常用于流媒体应用:容忍丢失、速率敏感

UDP还用于:DNS,SNMP

在UDP上是可以实现可靠数据传输的——在应用层增加可靠性机制、应用特定的错误恢复机制(即在应用层实现,因此对应用层开发人员来说难度较大)

UDP segment format:

[32bits]

| sp | dp |

| length | checksum |

| Application data (message)|

length是UDP段的长度(包含头部),checksum是校验和(实现错误校验功能)。

UDP checksum

目的:检测UDP段在传输过程中是否发生错误(如位翻转)。

发生错误是因为传输是端到端的,可能经历了多种物理媒介、多个路由器等等,中途很有可能发生错误。

发送方

  • 将段的内容视为16-bit整数
  • 校验和计算:计算所有整数的和,进位单独取出来与剩下的16位相加,将得到的值按位求反,得到校验和
  • 发送方将校验和放入校验和字段

接收方

  • 计算所收到的校验和
  • 将其与校验和字段进行对比,若不相等则检测出错误,若相等则没有检测出错误,但仍然可能有错误

可靠数据传输原理

可靠——不错、不丢、不乱

可靠数据传输协议:

  • 可靠数据传输对应用层、传输层、链路层都很重要
  • 网络top-10问题
  • 信道的不可靠特性决定了可靠数据传输协议 (rdt) 的复杂性

可靠数据传输协议基本结构:接口

rdt_send(): 被上层应用调用,将数据交给rdt (reliable data transfer protocol) 以发送给对方。即发送方向上地响应这样一个rdt_send的调用。

udt_send(): 被rdt调用,在不可靠信道(unreliable channel)上向接收方传输数据。(所谓的不可靠信道,实际上就是我们所说的网络层的IP协议)

rdt_rcv(): 当数据包到达接收方信道时被调用。这一调用就会触发接收方的rdt协议对数据包进行处理。

deliver_data(): 被rdt调用,向上层应用交付数据。

可以看出,rdt_send()和deliver_send()是单向的。这是因为应用层只需要发数据和收数据,不关心数据是怎么处理和传输的。剩下的所有工作都由下面的层完成。

可靠数据传输协议

渐进的设计可靠数据传输协议的发送方和接收方,只考虑单向数据传输,但控制信息双向流动。利用有限状态机(Finite State Machine, FSM)刻画传输协议。

协议:(逐步贴近真实情况)

Rdt 1.0: 可靠信道上的可靠数据传输

假设底层信道完全可靠:不会发生位错误,不会丢弃分组

发送方和接收方的FSM独立(因为这是一个可靠信道!发送方和接收方之间就不需要什么交互,全部交给协议处理就行了)

Rdt 2.0: 产生位错误的信道

假设分组不会丢失,只是产生了位错误。

首先,接收方需要知道分组是否出错。如果错了,就要想办法恢复/重传。

检测出错已解决——底层信道可能翻转分组中的位(bit):利用校验和检测位错误

如何从错误中恢复?这就需要引入新的控制消息来标识——

  • 确认机制(Acknowledgements, ACK):接收方显示地告知发送方分组已正确接收。
  • NAK:接收方显示地告知发送方分组有错误。
  • 发送方收到NAK后,重传分组。

基于这种重传机制的rdt协议称为ARQ(Automatic Repeat Request)协议。

Rdt 2.0中引入的新机制:

  • 差错检测
  • 接收方反馈控制消息:ACK/NAK
  • 重传

但是有一个致命缺陷:如果ACK/NAK的传输出错怎么办?这里使用的是停-等协议,即stop and wait — sender sends one packet, then waits for receiver response.

what happens if ACK/NAK corrupted?

  • sender doesn’t know what happened at receiver!

  • can’t just retransmit: possible duplicate

Handling duplicates:

  • sender retransmits current pkt if ACK/NAK corrupted

  • sender adds sequence number to each pkt

  • receiver discards (doesn’t deliver up) duplicate pkt

Rdt 2.1 发送方应对ACK/NAK破坏

增加了两个序列号0和1。

对于发送方,有等待上层调用的状态和等待ACK/NAK的状态这两种,因此总状态是翻倍了的,即两个0两个1。(等待上层调用序列号0分组的状态,等待序列号0的ACK/NAK的状态,等待上层调用序列号1分组的状态,等待序列号1的ACK/NAK的状态)翻倍是因为必须记住当前分组的序列号。

Rdt 2.2: 无NAK消息协议

接收方通过ACK告知最后一个被正确接收的分组,在ACK中显示地加入被确认分组的序列号。

发送方接收到重复ACK后,重发当前分组。

停等操作使得Rdt 3.0的性能很差。

流水线协议

允许发送方在收到ACK之前连续发送多个分组。这就需要更大的序列号范围,发送方和接收方需要更大的存储空间以缓存分组

滑动窗口协议 Sliding-window protocol

窗口:允许使用的序列号范围

窗口尺寸为N,表示最多有N个等待确认的消息。

滑动窗口:随着协议的运行,窗口在序列号空间内向前滑动

滑动窗口协议:GBN,SR

GBN协议 (Go-Back-N)

分组头部包含k-bit序列号

采用累积确认的机制

ACK(n): 确认到序列号n(包含n)的分组均已被正确接收。

超时timeout(n)事件:重传序列号大于等于n,还未收到ACK的所有分组。

ACK机制:发送拥有最高序列号的、已被正确接收的分组的ACK

  • 可能产生重复的ACK
  • 只需要记住唯一的expectedseqnum

乱序到达的分组:

  • 直接丢弃——接收方不缓存
  • 重新确认序列号最大的、按序到达的分组

SR (Selective Repeat)

接收方对每个分组单独进行确认

  • 设置缓存机制,缓存乱序到达的分组

发送方只重传那些没收到ACK的分组

  • 为每个分组设置定时器

发送方窗口

  • N个连续的序列号
  • 限制已发送且未确认的分组

序列号空间大小与窗口尺寸满足的关系:$N_S+N_R\leq2^k$.

TCP

  • 点对点:一个发送方,一个接收方

  • 可靠的、按序的字节流

  • 流水线机制:TCP拥塞控制和流量控制机制设置窗口尺寸

  • 发送方/接收方缓存

  • 全双工 (full-duplex):统一连接中能够传输双向数据流

  • 面向连接:

    通信双方在发送数据之前必须建立连接

    连接状态只在连接的两端中维护,在沿途节点中并不维护状态

    TCP连接包括:两台主机上的缓存、连接状态变量、socket等

  • 流量控制机制

序列号

  • 序列号指的是segment中第一个字节的编号,而不是segment的编号,通常从500开始
  • 建立TCP连接时,双方随即选择序列号

ACKs

  • 希望接收到的下一个字节的序列号
  • 累积确认:该序列号之前的所有字节均已被正确接收到

接收方如何处理乱序到达的segment?

  • TCP规范中没有规定,由TCP的实现者做出决策

TCP可靠数据传输

  • TCP在IP层提供的不可靠服务基础上实现可靠数据传输服务

  • 流水线机制

  • 累积确认

  • TCP使用单一重传定时器

  • 触发重传的事件:超时,收到重复ACK
  • 渐进式:暂不考虑重复ACK,暂不考虑流量控制,暂不考虑拥塞控制

RTT和超时

如何设置定时器的超时时间?

  • 大于RTT——但是RTT是变化的
  • 过短:不必要的重传
  • 过长:对段丢失时间反应慢

如何估计RTT?

  • SampleRTT:测量从段发出去到收到ACK的时间

  • 忽略重传

  • SampleRTT变化,就测量多个取平均值

  • 指数加权移动平均:

    EstimatedRTT=(1-alpha)*EstimatedRTT+alpha*SampleRTT

    典型值:0.125

TCP发送方要处理的事件

从应用层收到数据:

  • 创建segment
  • 序列号是segment第一个字节的编号
  • 开启计时器
  • 设置超时时间TimeoutInterval

超时:

  • 重传引起超时的segment
  • 重启定时器

收到ACK:

如果确认此前未确认的segment

  • 更新SendBase
  • 如果窗口中还有未被确认的分组,重新启动定时器

快速重传机制

TCP实现中,如果发生超时,超时时间间隔将重新设置,即将超时时间间隔加倍,导致其很大,因此重发丢失的分组之前要等待很长时间。

通过重复ACK检测分组丢失

如果sender收到对同一数据的3个ACK,则假定该数据之后的段已经丢失,sender重传该分组。

快速重传:在定时器超时之前即进行重传

TCP流量控制

接收方为TCP连接分配buffer。

流量控制 (flow control):发送方不会传输的太多、太快以至于淹没接收方(buffer溢出)。

TCP连接管理

TCP sender和receiver在传输数据前需要建立连接

client是连接发起者,server等待客户连接请求。

Three way handshake

  1. client host sends TCP SYN segment to server

    specifies initial seq

    no data

  2. server host receives SYN, replies with SYNACK segment

    server allocates buffers

    specifies server initial seq

  3. client receives SYNACK, replies with ACK segment, which may contain data

TCP关闭——4次挥手

client向server发送FIN

server收到FIN,回复ACK,关闭连接,发送FIN

client收到FIN,回复ACK

  • 进入等待状态,timeout了会重复发送ACK

server收到ACK,连接关闭

拥塞控制原理

拥塞(congestion)

表现:

  • 分组丢失(路由器缓存溢出)
  • 分组延迟过大(在路由器缓存中排队)

拥塞控制的方法

端到端的拥塞控制:

  • 网络层不需要显式地提供支持
  • 端系统通过观察loss, delay等网络行为判断是否发生拥塞
  • TCP采取这种方法

网络辅助的拥塞控制:

  • 路由器向发送方显示地反馈网络拥塞信息
  • 简单的拥塞只是说

TCP快速重传为什么3次ACK

TCP为什么3次握手

TCP MSS

Java复习

文件IO操作

感觉自己没救了😭

路径分隔符:

static String pathSeparator

static char pathSeparatorChar

文件名称分隔符:

static String separator

static char separatorChar

操作路径:"Code"+File.separator+"Java"+File.separator+"Homework"

String类型和char类型作用完全相同,因为在源码里是这样的:

public static final String pathSeparator=""+pathSeparatorChar;

路径是不区分大小写的。Unix中文件名称分隔符是/,Windows是\,但是这是转义字符,所以写的时候要写成\\.

File类

构造方法

File(String pathname) 通过将给定路径名字符串转换为抽象路径名来创建一个新File实例。路径结尾可以是文件也可以是文件夹。可以是相对路径或绝对路径。路径可以存在也可以不存在。这是因为创建File对象,只是把字符串路径封装成File对象,不考虑路径的真假情况。

File(String parent, String child)

获取功能的方法

  • public String getAbsolutePath() 返回此File的绝对路径
  • public String getPath() 将此File转换为路径名字符串(就是把结果放到这个File对象中返回)
  • public String getName() 返回此File表示的文件或目录的名称
  • public long length() 返回由此File表示的文件的长度,以字节为单位。不能是文件夹。若文件不存在,则返回0.

判断功能的方法

  • public boolean exists() 此File表示的文件或目录是否实际存在
  • public boolean isDirectory() 此File表示的是否为目录
  • public boolean isFile() 此File表示的是否是文件

数据库复习

关系模型

关系数据库使用一个或多个表来存储数据。
数学上把一系列域上的笛卡尔积的子集称为关系。

软件系统无法保证数据的真实正确性,但可以保证数据符合可明确定义的约束。这种约束通常称为完整性约束。它是数据安全性的一部分。
常见的简单约束有两种形式,一种是对属性取值范围的确定,比如性别只有男、女两种属性的取值(个人认为应该是三种,男、女、无 :) )。另一种是对属性值之间相互关系的限定,最典型的就是关系模型中键的定义,如主键、超键、外键、候选键。
超键:在给定关系模式中,能唯一标识出各个元组的属性集合。超键中可能包含无关紧要的属性,也就是说超键的真子集也可能是超键。例如在学生成绩表中有学号、姓名和成绩3个属性,其中学号是超键,而且也是主键,因为姓名和成绩可能重复,但学号是唯一的。{学号,姓名},{学号,成绩},{学号,姓名,成绩}也是超键。
候选键:在给定关系模式中,能够唯一标识出各个元组的属性集合,并且不含多余属性。候选键是超键,但超键不一定是候选键。只有不存在任何真子集是超键的超键才是候选键。
主键:一个关系中可能有多个候选键,通常指定其中一个,并且只能是一个,用来标识元组。由于主键具有唯一性,所以主键是候选键,但候选键不一定是主键。
外键:如果关系表S1的一个属性子集A,必须匹配另一个关系表S2中出现的数值,则称A是关系表S1的外键。其中,S1称为引用关系,S2称为被引用关系。外键的值,或与被引用关系中出现的数值对应,或为空值。例如关系表1中有院系这个属性,并且是外键,对应关系表2中的单位这个属性,而院系属性中有工程学院,单位属性中此项为教育学院或为空值,那么就出问题了。如果院系属性也为教育学院,或者院系属性为空而单位属性为教育学院,那么是可以的。

可以用代数、逻辑等方法描述关系操作,最基本最常用的是代数方法,即关系代数。
关系代数也是一门代数,关系代数包括一个运算集合,这些运算以一个或两个关系作为运算数,产生一个新的关系作为结果。
关系代数运算包含基本关系代数运算、附加关系代数运算和扩展关系代数运算。其中基本关系代数运算包含选择、投影、集合并、集合差、笛卡尔积和更名运算。

选择:选择运算是选出满足给定谓词(条件)的元组,结果关系和原关系有着相同的模式。
选择运算用 $\sigma$ 表示。将谓词写作 $\sigma$ 的右下标,并在 $\sigma$ 后面的括号中给出作为参数的关系名。例如:

就是在students关系表中选出gender属性为none的元组。(hhh)
投影:投影运算用来从给定关系产生一个只有其部分列的新关系。投影运算用 $\pi$ 表示。所有希望在结果关系中出现的属性作为右下标,作为参数的关系名紧跟在 $\pi$ 后面的括号中。结果关系的模式是 $\pi$ 的下标中列出的所有属性,并按 $\pi$ 下标中列出的顺序出现。例如:

于是结果关系中只包含id和age两个属性,并且会去掉结果关系中重复的元组。
⚠️ 关系代数把表看作是作为元组集合的关系,既然是集合,就不包括重复元组,也就是说,关系代数每个运算都是去重的。
并运算:关系是相容的。两个关系必须是同元的,即它们所包含的属性个数必须相同;两个关系对应属性的域必须相同或相容。
例如,找出所有已有考生报考又安排了考官组卷的eid:

差运算:用来查询在一个关系中而不在另一个关系中的那些元组,和并运算一样,差运算只能在相容的关系间进行。
例如,找出所有已有考生报考但没有安排考官组卷的eid:

笛卡尔积运算:结果关系的模式是参与运算的两个关系的模式的串接。运算符左侧关系中的每一个元组与右侧关系的每一个元组拼接,形成结果关系中的一个元组。
⚠️ 元组的拼接
更名:对给定的关系代数表达式E,表达式 $\rho_X(E)$ 返回表达式E的结果,并把名字X赋给了它。
如果关系代数表达式E是n元的,则表达式 $\rho_{X(A_1,A_2,…,A_n)}(E)$ 返回表达式E的结果,并赋给它名字X,同时将E的各属性更名为 $A_1,A_2,…,A_n$。
关系运算的运算参数是关系,运算结果也是关系。
查询历史学院的考生的姓名:

关系代数基本运算是完备的,足以表达任何普通的关系代数查询。但是许多查询的表达式复杂、冗长,因此定义附加运算,简化一些查询的表达。
常见的附加运算有:集合交、自然联接、属性联接、条件联接和赋值运算。

集合交:集合交运算的结果是由那些同时在参与运算关系中存在的元组组成,只能在相容的关系间进行,用 $\bigcap$ 表示。

自然联接:可以将特定选择运算和笛卡尔积合并为一个运算。首先计算笛卡尔积,然后在笛卡尔积的结果上,基于两个关系模式中都出现的属性,即两个关系模式的所有同名属性进行属性值相等的选择运算,最后去掉重复列。也就是结果关系模式中相同的属性只保留一列,因为在任何元组中同名属性的值都是相等的。

例如:

examinee表:

eeid eename dname
123 A 历史
234 B 心理
345 C 教育

department表:

dname dloca dtele
历史 46-A 444
教育 45-B 555
心理 44-C 666

先算笛卡尔积:

examinee.eeid examinee.eename examinee.dname department.dname department.dloca department.dtele
123 A 历史 历史 46-A 444
123 A 历史 教育 45-B 555
123 A 历史 心理 44-C 666
234 B 心理 历史 46-A 444
234 B 心理 教育 45-B 555
234 B 心理 心理 44-C 666
345 C 教育 历史 46-A 444
345 C 教育 教育 45-B 555
345 C 教育 心理 44-C 666

选择examinee.dname和department.dname相同的元组,最终选出了3组,将examinee.dname和department.dname属性合并后,成为了结果关系。

属性联接:首先计算笛卡尔积,然后在笛卡尔积的结果上,基于两个关系模式中都出现的属性,即两个关系模式的指定同名属性进行属性值相等的选择运算,最后去掉重复列。指定同名属性只保留一个。

自然联接用 $S1 \infty S2$ 表示,属性联接用 $S1 \infty_{attribute} S2$ 表示。
例如指定了属性name,那么联接时就只看S1.name和S2.name相等的元组。
因此区别就是,当参与联接运算的两个表有多个同名列时,自然联接的匹配条件是所有同名列全部取值相等,而属性联接的匹配条件是指定其中的某些同名列取值相等。
赋值:赋值运算是将 $\leftarrow$ 右侧的表达式结果赋给其左侧的关系变量,该关系变量可以在后续的表达式中使用。
例如:从A中去除属性X

关系代数运算的进一步扩充:
广义投影:允许将算术运算作为投影的一部分
聚集:例如计算给定集合元素的总和、平均值等
外联接:使得关系代数表达式可以处理缺失信息

广义投影:允许在投影列表中使用算术表达式。
例如 $\pi_{F_1,F_2,…,F_n}(E)$ 中,E是任意关系代数表达式,$F_1,F_2,…,F_n$ 中的每一个都是涉及E的属性的算术表达式,也可以仅仅是单个属性或常量。
广义投影的结果是对关系表达式t的每一行分别计算 $F_1,F_2,…,F_n$,
聚集函数:sum, avg, count, max, min等。
例如:

查询结果只包含一个元组,只有单个属性。
还可以这样:

意思是说对元组按dname进行分组。

有些元组不能跟另外关系的任何一个元组匹配,一些实际应用系统可能希望在结果中保留悬浮元组,这就有了外联接运算。
不考虑悬浮元组的自然联接、属性联接和条件联接都属于内联接。
外联接:首先计算内联接,然后加入左侧关系、右侧关系、两侧关系中的悬浮元组,对应称为左外联接(L)、右外联接(R)、全外联接(F)。表示方法:$\infty^R$.

E-R图

实体用方框表示。

联系用菱形表示。

实体和实体集统称实体。

实体通常使用属性来描述。同类实体通常使用相同的属性组来描述。

属性可能取值的范围成为属性域

现实生活中经常需要区分同类实体集中一个个不同的实体。例如在考生实体集中,由于可能出现同名同姓的考生,所以用考号来区分。

能够并且用以区分一个实体集中不同实体的最小属性集称为标识符或主键,组成主键的属性称为标识属性。

属性用椭圆表示。

联系也有属性!

用线段将属性与其相对应的联系或实体连接起来。

并在那些用于标识实体或联系的属性下面加上下划线

2021/5/16 add

候选码(candidate key) / 候选键

关系中的一个属性组,其值能唯一标识一个元组,若从该属性组中去掉任何一个属性,它就不具有这一性质了,这样的属性组称为候选码。

关系中可以有多组候选码,例如:

1
Student(S#, Sname, Sage, Sclass, Saddress)

S#是候选码,(Sname, Saddress)也是候选码。

1
Employee(EmpID, EmpName, MobileNumber)

EmpID是候选码,MobileNumber也是候选码。

主码(primary key) / 主键

当有多个候选码时,可以选定一个作为主码。

DBMS以主码为主要线索管理关系中的各个元组。

例如可以选定属性 S# 作为 Student 表的主码,也可以选定属性组 (Sname, Saddress) 作为 Student 表的主码。

主属性和非主属性

包含在任何一个候选码中的属性被称作主属性,而其他属性被称作非主属性。

最简单的,候选码只包含一个属性。

最极端的,所有属性构成这个关系的候选码,称为全码(all-key)。

外码(foreign key) / 外键

关系R中的一个属性组,它不是R的候选码,但它与另一个关系S的候选码相对应,则称这个属性组为R的外码或外键。

例如”合同”关系中的”客户号”不是候选码,但却是外码,因为它与”客户”关系中的候选码”客户号”相对应。

两个关系是通过外键连接起来的。

关系模型的完整性

实体完整性

关系的主码中的属性值不能为空值。

空值:不知道或无意义的值。

意义:关系中的元组对应到现实世界相互之间可区分的一个个个体,这些个体是通过主码来唯一标识的;若主码为空,则出现不可标识的个体,这是不允许的。

参照完整性

如果关系R1的外码Fk与关系R2的主码Pk相对应,则R1中的每一个元组的Fk值或者等于R2中某个元组的Pk值,或者为空值。

意义:如果关系R1的某个元组t1参照了关系R2的某个元组t2,则t2必须存在。

用户自定义完整性

用户针对具体的应用环境定义的完整性约束条件。

例如,S# 要求是10位整数,性别只能是男或女,年龄只能在12到35岁之间。

DBMS对关系完整性的支持

实体完整性和参照完整性由DBMS系统自动支持。

DBMS系统通常提供了如下机制:

  • 它使用户可以自行定义有关的完整性约束条件
  • 当有更新操作发生时,DBMS将自动按照完整性约束条件检验更新操作的正确性,即是否符合用户自定义的完整性。

关系代数

并相容性

某些关系代数操作,如并、差、交等,需要满足”并相容性”。

参与运算的两个关系及其相关属性之间有一定的对应性、可比性或意义关联性。

定义:关系R与关系S存在相容性,当且仅当:

  1. 关系R和关系S的属性数目必须相同;
  2. 对于任意 i,关系R的第 i 个属性的域必须和关系S的第 i 个属性的域相同。

例如:

1
2
Student(SID char(10), Sname char(8), Age char(3))
Professor(PID char(10), Pname char(8), Age char(3))

并操作(Union)

定义:假设关系R和关系S是并相容的,则关系R与关系S的并运算结果也是一个关系,记作:$R \cup S$,它由或者出现在关系R中,或者出现在S中的元组构成。

并运算是将两个关系的元组合并成一个关系,在合并时去掉重复的元组。

theta-join

投影与选择操作只是对单个关系(表)进行操作,而实际应用中往往涉及多个表之间的操作,这就需要theta-连接操作。

数据库完整性

数据库完整性(DB Integrity)是指DBMS应保证的DB的一种特性——在任何情况下的正确性、有效性和一致性。

游标

游标是指向某检索记录集的指针。

通过这个指针的移动,每次读一行处理一行,直至处理完毕。

第一范式 1NF

若关系模式R(U)中关系的每个分量都是不可分的数据项,则称R(U)属于第一范式.

1
Star(name, address(street, city))

Star不属于1NF,因为属性address仍包含了street, city两个属性,其分量不是原子。

不符合1NF的处理

将非1NF转换为1NF:

1
2
3
Star(name, address(street, city))
转换为:
Star(name, street, city)Star(name, address)

第二范式 2NF

若R(U)是1NF且U中的每一非主属性完全函数依赖于候选键,则称R(U)属于第二范式。

1
2
3
4
5
6
7
R(S#, SN, SD, CN, G)
其中,S#是学号,SN是姓名,SD是班级,CN是课程,G是成绩,
函数依赖:S#->SN, S#->SD, (S#, CD)->G
候选键包含(S#, CN)
非主属性包含SN和SD
因为(S#, CN) -P-> (SN, SD),所以R不属于2NF。
将其分解为R1(S#, SN, SD), R2(S#, CN, G),则R1R2都属于2NF。

第二范式消除了非主属性对候选键的部分依赖。

第三范式 3NF

第三范式是确保每列都和主键列直接相关,而不是间接相关,即限制列的冗余性。 如果一个关系满足第二范式,并且除了主键以外的其他列都依赖于主键列,列和列之间不存在相互依赖关系,则满足第三范式。

第三范式(Third Normal Form,3rd NF)就是指表中的所有数据元素不但要能唯一地被主关键字所标识,而且它们之间还必须相互独立,不存在其他的函数关系。也就是说,对于一个满足2nd NF 的数据结构来说,表中有可能存在某些数据元素依赖于其他非关键字数据元素的现象,必须消除。

关系模式R 中若不存在这样的码X、属性组Y及非主属性Z(Z (强制依赖)Y),使得X→Y,Y→Z,成立,Y→X不成立,则称R ∈ 3NF。

若R∈3NF,则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。

如果R∈3NF,则R也是2NF。

采用投影分解法将一个2NF的关系分解为多个3NF的关系,可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。

将一个2NF关系分解为多个3NF的关系后,并不能完全消除关系模式中的各种异常情况和数据冗余。

SQL

SELECT INTO

SELECT INTO语句从一个表中选取数据,然后把数据插入另一个表中。

常用于创建表的备份复件或者用于对记录进行存档。

1
SELECT * INTO new_table_name [IN externaldatabase] FROM old_database

或者只把需要的列插入新表:

1
2
3
SELECT column_name(s)
INTO new_table_name [IN externaldatabase]
FROM old_table_name

AUTO INCREMENT

AUTO INCREMENT(自动增长)语句会在新纪录插入表时生成一个唯一的数字。PostgreSQL使用序列来标识字段的自增长,数据类型有smallserial, serial和bigserial。

使用AUTO INCREMENT的原因:我们通常希望在每次插入新纪录时,自动地创建主键字段的值。因此我们可以在表中创建一个AUTO INCREMENT字段。

伪类型 存储大小 范围
SMALLSERIAL 2字节 1 到 32,767
SERIAL 4字节 1 到 2,147,483,647
BIGSERIAL 8字节 1 到 922,337,2036,854,775,807

SERIAL数据类型的基础语法:

1
2
3
CREATE TABLE tablename(
colName SERIAL
);

假定我们要创建一张 COMPANY 表,并创建下面几个字段:

1
2
3
4
5
6
7
runoobdb=# CREATE TABLE COMPANY(
ID SERIAL PRIMARY KEY,
NAME TEXT NOT NULL,
AGE INT NOT NULL,
ADDRESS CHAR(50),
SALARY REAL
);

现在往表中插入几条记录:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
INSERT INTO COMPANY (NAME,AGE,ADDRESS,SALARY)
VALUES ( 'Paul', 32, 'California', 20000.00 );

INSERT INTO COMPANY (NAME,AGE,ADDRESS,SALARY)
VALUES ('Allen', 25, 'Texas', 15000.00 );

INSERT INTO COMPANY (NAME,AGE,ADDRESS,SALARY)
VALUES ('Teddy', 23, 'Norway', 20000.00 );

INSERT INTO COMPANY (NAME,AGE,ADDRESS,SALARY)
VALUES ( 'Mark', 25, 'Rich-Mond ', 65000.00 );

INSERT INTO COMPANY (NAME,AGE,ADDRESS,SALARY)
VALUES ( 'David', 27, 'Texas', 85000.00 );

INSERT INTO COMPANY (NAME,AGE,ADDRESS,SALARY)
VALUES ( 'Kim', 22, 'South-Hall', 45000.00 );

INSERT INTO COMPANY (NAME,AGE,ADDRESS,SALARY)
VALUES ( 'James', 24, 'Houston', 10000.00 );

查看 COMPANY 表的记录如下:

1
2
3
4
5
6
7
8
9
 id | name  | age | address    | salary
----+-------+-----+------------+--------
1 | Paul | 32 | California | 20000
2 | Allen | 25 | Texas | 15000
3 | Teddy | 23 | Norway | 20000
4 | Mark | 25 | Rich-Mond | 65000
5 | David | 27 | Texas | 85000
6 | Kim | 22 | South-Hall | 45000
7 | James | 24 | Houston | 10000

触发器

触发器是一种由事件自动触发执行的特殊存储过程,这些事件可以是对一个表进行 INSERT、UPDATE、DELETE 等操作。

触发器经常用于加强数据的完整性约束和业务规则上的约束等。

在SQL内部把触发器看作是存储过程但是不能传递参数。一般的存储过程通过存储过程名称被直接调用,而触发器主要是通过事件进行触发而被执行。

在SQL Server里就是对一个表的一定操作触发某种条件,从而执行的一段程序。触发器是一个特殊的存储过程。

  • SQL Server为每个触发器都创建了两个专用表﹕Inserted表和Deleted表。这两个表由系统来维护,它们存在于内存中而不是在数据库中。这两个表的结构总是与被该触发器作用的表的结构相同。触发器执行完成后,与该触发器相关的这两个表也被删除。 Deleted表存放由于执行Delete或Update语句而要从表中删除的所有行。 Inserted表存放由于执行Insert或Update语句而要向表中插入的所有行。

  • SQL Server提供了两种触发器:Instead of和After触发器。

    这两种触发器的差别在于它们

    • Instead of触发器用于替代引起触发器执行的T-SQL语句。除表之外,Instead of触发器也可以用于视图,用来扩展视图可以支持的更新操作。
    • After触发器在一个INSERT, UPDATE或DELETE语句之后执行,约束检查等动作都在After触发器被激活之前发生。After触发器只能用于表。一个表或视图的每一个修改动作(insert,update和delete)都可以有一个instead of 触发器,一个表的每个修改动作都可以有多个After触发器。
  • 触发器的执行过程:如果一个INSERT, UPDATE或DELETE语句违反了约束,那么After触发器不会执行,因为对约束的检查是在After触发器被激活之前发生的。所以After触发器不能超越约束。

  • Instead of 触发器可以取代激发它的操作来执行。它在Inserted表和Deleted表刚刚建立、其它任何操作还没有发生时被执行。因为Instead of 触发器在约束之前执行,所以它可以对约束进行一些预处理。

触发器创建语法

1
2
3
4
5
6
7
CREATE [ CONSTRAINT ] TRIGGER name
{ BEFORE | AFTER | INSTEAD OF } { event [ OR ... ]}
ON table_name
[ FROM referenced_table_name ]{ NOT DEFERRABLE | [ DEFEREABLE ] { IINITIALLY IMMEDIATE | INITIALLY DEFERED} }
FOR [ EACH ] { ROW | STATEMENT }
[ WHEN { condition }]
EXECUTE PROCEDURE function_name ( arguments )

Concurrency Control

The general process of assuring that transactions preserve consistency when executing simultaneously is called concurrency control.

The scheduler takes read/write requests from transactions and either executes them in buffers or delays them.

lec01

数据库是:长期存储在计算机内、有组织的、可共享的数据的集合。

数据库管理系统:DBMS是位于用户操作系统之间的一层数据管理软件。

  • DBMS是系统软件
  • DBMS是大型复杂的软件系统

数据库系统DBS (database system)是针对某种应用开发的信息管理系统 (IMS, information management system)。

DBS的构成:数据库、DBMS、数据库管理员(DBA)、应用程序

DBMS的诞生——三大标志性事件:

  • IMS系统——1966,层次数据模型
  • DBTG报告——1969,网状数据模型
  • Codd发表论文——1970,关系数据模型

A data model is a notation for describing data or information. It consists of 3 parts: structure, operations, constraints on the data.

Important data models: Relational model (object-relational extensions), Graph data model (RDF).

Other data models: Hierarchical data model, Network data model, XML data model, object-oriented model

Relational Model in Brief

  • structure
  • operations: relational algebra, table-oriented
  • constraints

Graph Model in Brief

RDF三元组

Relations: 2-dimensional table

Attributes: the column names of a relation, describing the meaning of entries in the column

Schemas: relation name and its attributes. The schema for relation Movies is: Movie(title, year, length, genre).

Relational database schema: the set of schemas for the relations of a database

Tuples: a row of relation. A tuple has one component for each attribute. e.g., (Gone With the Wind, 1939, 231 drama).

Domains: a particular elementary type. Associated with each attribute of a relation. e.g., Movies(title:string, year:integer, length:integer, genre: string)

Key: a set of attributes of a relation.

SQL: the principal language used to describe and manipulate relational databases.

Two aspects of SQL:

  • DDL(Data-Definition Language), declaring database schemas
  • DML(Data-Manipulation Language), querying and modifying database

Data Types

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
CHAR(n)
VARCHAR(n)

BIT(n)
BIT VARYING(n)

BOOLEAN -- TRUE, FALSE, UNKNOWN

INT or INTEGER
SMALLINT -- in book is SHORTINT, I use SMALLINT

FLOAT or REAL
DOUBLE PRECISION
DECIMAL(n, d) -- real number with a fixed decimal point, n decimal digits
-- 1234.45 of type DECIMAL(6, 2)
NUMERIC -- synonym for DECIMAL

DATE -- DATE '1948-05-14'
TIME -- TIME '15:00:02.5'

-- deleting a relation
DROP TABLE R;

-- Modifying a relation
ALTER TABLE MovieStar ADD phone CHAR(16);
ALTER TABLE MovieStar DROP birthdate;

-- default values
CREATE TABLE blahblah(
gender CHAR(1) DEFAULT '?',
birthdate DATE DEFAULT DATE '0000-00-00'
);
ALTER TABLE MovieStar ADD phone CHAR(16) DEFAULT 'unlisted';

Relational Algebra

Data-manipulation aspect of the relational model

  • querying the data
  • modifying the data

An algebra on relations: input and output are all relations

Set Operations

1
2
3
4
5
6
7
8
-- Union
(SELECT * FROM R) UNION (SELECT * FROM S);

-- Intersection
(SELECT * FROM R) INTERSECT (SELECT * FROM S);

-- Difference
(SELECT * FROM R) EXCEPT (SELECT * FROM S);

Projection

to avoid duplicate tuples, use DISTINCT.

1
SELECT DISTINCT genre FROM Movies;

Selection

1
SELECT name FROM Movies WHERE length >= 100;

Cartesian Product

1
SELECT * FROM R CROSS JOIN S;

Natural Joins

1
SELECT * FROM R NATURAL JOIN S;

Dangling tuple: a tuple fails to pair with any tuple of the other relation in a join

使用自然连接NATURAL JOIN时,两表中同名的字段不能超过一个;如果超过了1个,就用INNER JOIN.

Theta Join

1
SELECT * FROM U INNER JOIN V WHERE A < D;
1
2
SELECT * FROM U INNER JOIN V WHERE A < D AND U.B <> V.B;
SELECT * FROM U INNER JOIN V ON A < D WHERE U.B <> V.B;

Renaming

Use ESCAPE to define a escape character:

1
SELECT titles FROM Movies WHERE titles LIKE 'x%%x%' ESCAPE 'x';

NULL

1
2
SELECT titles FROM Movies WHERE name IS NOT NULL;
SELECT titles FROM Movies WHERE name IS NULL;

ORDER BY <list of attributes>

The order is by default ascending

Use key words DESC and ASC

1
2
3
4
SELECT *
FROM Movies
WHERE studioName = 'Disney' AND year = 1990
ORDER BY length, title;

All the atrributes of Movies are available at the time of sorting, even if they are not part of the SELECT clause.

1
SELECT s1.n, s2.n FROM Star s1, Star s2 WHERE s1.a = s2.a AND s1.n < s2.n;

Subquery

EXISTS R is a condition that is true if and only if R is not empty.

S IN R is true if and only if S is equal to one of the values in R.

S < ALL R is true if and only if S is greater than every value in unary relation R.

S <> ALL R is the same as S NOT IN R

S > ANY R is true if and only if S is greater than at least one value in unary relation R.

S = ANY R is the same as S IN R

Five Aggregation Operators

1
2
3
4
5
AVG
SUM
MIN
MAX
COUNT
1
2
3
4
5
6
SELECT
FROM
WHERE
GROUP BY
HAVING
ORDER BY

Two rules about HAVING clauses

  1. An aggregation in a HAVING clause applies only to the tuples of the group being tested

  2. Any attribute of relations in the FROM clause may be aggregated in the HAVING clause, but only those attributes that are in the GROUP BY list may appear unaggregated in the HAVING clause

    The same rule as for the SELECT clause

INSERT INTO table_name WHERE conditions;

DELETE FROM table_name WHERE conditions;

Delete all tuples in a relation: DELETE FROM table_name;

UPDATE R SET a=19 WHERE a<b;

inner join是内连接,显示符合连接条件的记录
语法如下:
select select_list from table1 inner join tabl2 on table1.column1=table2.column1
natural join是对两张表中字段名和数据类型都相同的字段进行等值连接,并返回符合条件的结果 。
natural join是自然连接,自动对两个表按照同名的列进行内连接语法如下:
select select_list from table1 natural join tabl2
使用自然连接要注意,两个表同名的列不能超过1个。

natural join:指明了两表进行自然连接,并且连接是基于两表中所有同名字段的。
join…using:用于两表有同名字段但数据类型不同,或者使用多个同名字段中的某一个做等值连接
join…on :最为灵活,可以指明连接的条件。

设K为R(U)中的属性或属性集合,若K完全函数决定U,则K是R(U)上的后候选键。

可选任意候选键作为R的主键。

包含在任一候选键中的属性称为主属性,其他属性称为非主属性。

完全函数依赖

{学号,课号}—>成绩

学号+课号 可以决定 成绩 但只有学号or只有课号无法决定成绩

部分函数依赖

{学号,课号}—>姓名

只有学号就能决定姓名 (课号是冗余的)

候选键:最小性、唯一性

外键:不是此关系的候选键,但是是另一个关系的候选键。

属性集闭包

SystemVerilog

基于SystemVerilog的测试程序

电路验证是确认所设计的电路功能正确性的过程,而仿真(simulation)是进行电路验证的主要手段,它可以及早发现所存在的设计问题,降低设计风险,节约设计成本。通常,仿真是通过编写测试程序(testbench)完成的。

测试程序也称为测试台,它是用于测试待测模块(Device Under Test, DUT)功能是否正确的一段SystemVerilog HDL代码,是不可综合的,由激励信号、DUT和输出响应三部分组成。

待测模块DUT:

1
2
3
4
module sillyfunction(input logic a, b, c,
output logic y);
assign y= ~b & ~c | a & ~b;
endmodule

测试程序示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
`timescale 1ns/1ns          //预编译指令,定义时间单位和时间精度
module sillyfunction_tb(); //测试程序没有输入/输出端口
logic a, b, c, y;
sillyfunction dut(.a(a), .b(b), .c(c), .y(y)); //实例化待测模块
initial begin //给出激励信号
a = 0; b = 0; c = 0; #10; //000
c = 1; #10; //001
b = 1; c = 0; #10; //010
c = 1; #10; //011
a = 1; b = 0; c = 0; #10; //100
c = 1; #10; //101
b = 1; c = 0; #10; //110
c = 1; #50; //111
$finish
end
initial begin //输出结果,否则只产生波形
$monitor($time, "a = %b, b = %b, c = %b, y = %b", a, b, c, y);
end
endmodule

10 表示延迟10个时间单位,$monitor, $time表示系统任务,

测试程序的模板如下:

1
2
3
4
5
6
module testbench_name();  //testbench为顶层模块,不会被其他模块实例化,因此不需要任何端口
//信号定义
//模块实例化
//添加激励信号
//显示输出结果(可以不添加任何显示打印语句,只生成波形图即可)
endmodule

在SystemVerilog中,施加激励就是向DUT添加输入信号(即测试向量),主要有三种方法:

  1. 通过initial过程块施加(线性)激励;
  2. 通过always过程块施加(循环)激励,主要用于产生时钟信号;
  3. 通过文件施加激励。

通过initial过程块施加激励

在initial块中施加激励,每个仿真时刻只用列出值需要改变的信号。initial块只执行一次。

在一个测试程序中可以包含多个initial块,并且它们都是同时并行执行,因此需要特别注意,不要在多个initial块中,在同一个仿真时刻对同一个信号赋值,否则将产生冲突。

1
2
3
4
5
6
7
8
9
initial begin
//时刻0发生赋值
data_bus = 8'h00; addr = 8'h3f;
#10 data_bus = 8'h45; //时刻10发生赋值
end

initial begin
#15 data_bus = 8'hff; //时刻15发生赋值
end
1
2
3
4
5
6
7
8
9
initial begin
//时刻0发生赋值
data_bus = 8'h00; addr = 8'h3f;
#10 data_bus = 8'h45; //时刻10发生赋值
end

initial begin
#10 data_bus = 8'hff; //错误,发送冲突
end

通过文件施加激励

将激励(测试向量)存放在一个文本文件中,测试程序从文件中读取激励,对DUT进行测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
module sillyfunction_tb();
logic a,b,c,y;
logic [2:0] stim [7:0]; //声明一个logic类型的数组stim
int i;
sillyfunction dut(.a(a),.b(b),.c(c),.y(y));
initial begin
$readmemb("testvector.txt",stim); //将所有激励读入数组
for(i=0;i<8;i=i+1) begin
{a,b,c}=stim[i]; #10; //依次测试各个激励
end
end
initial begin
$monitor($time, "a = %b, b = %b, c = %b, y = %b", a, b, c, y);
end
endmodule
1
2
3
4
5
6
7
8
9
testvector.txt
000
001
010
011
100
101
110
111

输出响应

在SystemVerilog中,输出响应是指在向DUT的输入端施加激励后,通过观察DUT输出的结果,并与预期结果进行比较,以验证电路功能是否正确。这一过程可通过观测波形图或借助SystemVerilog HDL提供的一系列系统任务显示输出结果来实现。

SystemVerilog HDL中常用的系统任务包括:

获取仿真时间:$time

显示信号值:$display, $monitor

结束/中断仿真:$finish, $stop

文件输入:$readmemb, $readmmemh

文件输出:$fopen, $fclose, $fdisplay, $fmonitor

获取仿真时间

获取仿真时间的系统任务的返回值使用由`timescale定义的时间单位。如:

`timescale 1ns/1ps

`timescale 1ns/1ns

$time返回一个64位的整数时间值

$stime返回一个32位的整数时间值

$realtime返回一个实数时间值

如:$monitor($time,"a=%b b=%b c=%b y=%b",a,b,c,y)

显示信号值

显示信号值的系统任务包括:$display和$monitor

$display($time,"a=%b",a);

$monitor($time,"a=%b",a);

$display和$monitor的区别在于前者只有执行到该语句时才会进行显示操作,而后者是一个监视器,只要输出变量列表中的某个变量发生变化,就执行一次显示操作。后者使用更方便。

%h %o %d %b %c %s %t %m
hexadecimal octonary decimal binary ASCII 字符串 时间 模块名

结束/中断仿真

结束/中断仿真的系统任务包括:$finish和$stop,用于对仿真过程进行控制。

$finish;

$finish(n);

$stop;

$stop(n);

参数n可以取0, 1等值,”0”表示不输出任何信息,”1”表示给出仿真时间。

文件输入

在SystemVerilog HDL中文件输入不需要打开文件操作,直接读取文件即可,相关的系统任务包括:$readmemb和$readmemh,前者读取2进制数据,后者读取16进制数据。

$readmemb(“数据文件名”, 数组(存储器)名, <起始地址>, <结束地址>);
$readmemh(“数据文件名”, 数组(存储器)名, <起始地址>, <结束地址>);

起始地址和结束地址均可缺省。

文件格式:

  • 可用”_”提高数据可读性

  • 可包含单行或多行注释

  • 可用空格换行来区分单个数据

  • 可以设定一个特定地址,规定其后的数据从该地址开始存储,格式如下:

    @hex_addr

    地址必须是16进制,且大小写不敏感,并且@和地址之间不允许有空格。

例如:

testmem.txt:

0000_0000
0110_0001 0011_0010
//地址3-255没有定义
@100 //hex, 256
1111_1100
//地址257-1022没有定义
@3FF
1100_0010

数组stim:
0 00000000
1 01100001
2 00110010
3
4

255
256 11111100
257

1022
1023 11000010

code:

1
2
3
4
5
logic [7:0] stim [1023:0];
initial begin
//$readmemb("testmem.txt",stim);
$readmemb("testmem.txt",stim,0,1023);
end

文件输出

在SystemVerilog HDL中文件输出需要先打开文件,相应的系统任务为$fopen,然后可以通过系统任务$fdisplay或$fmonitor将需要保存的信息输入到指定文件中。

1
2
3
4
5
int MCD;
MCD = $fopen("文件名", "操作模式");
$fdisplay(MCD, "显示格式控制符", <输出变量(信号)列表>);
$fmonitor(MCD, "显示格式控制符", <输出变量(信号)列表>);
$fclose(MCD);

$fopen打开指定文件并返回一个32位整数,若打开失败,则返回0。操作模式为w, w+, a, a+.

$fclose关闭打开的文件。

$fdisplay和$fmonitor的用法与$display和$monitor的用法一致。

自动化测试

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
module sillyfunction_tb();
logic a,b,c,y,yexpected;
logic [3:0] stim [7:0];
int i;
sillyfunction dut(.a(a),.b(b),.c(c),.y(y));

initial begin
$readmemb("at_vec.txt",stim);
for(i=0; i<8; i=i+1) begin
{a,b,c,yexpected}=stim[i]; #10;
if(y==yexpected)
$display($time,"test pass!");
else
$display($time,"Error: inputs=%b,%b,%b",{a,b,c});
end
end
endmodule
1
2
3
4
5
6
7
at_vec.txt

000_1
001_0
010_0
...
111_0

pthread多线程编程

线程函数需要声明为void*类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <pthread.h>

/*
* The function to be executed by the thread should take a
* void* parameter and return a void* exit status code.
*/
void *thread_function(void *arg){
// Cast the parameter into what is needed.
int *incoming=(int*)arg;

// Do whatever is necessary using *incoming as the argument.

// The thread terminates when this function returns.
return NULL;
}

int main(void){
pthread_t thread_ID;
void *exit_status;
int value;

// Put something meaningful into value.
value=42;

// Create the thread, passing &value for the argument.
pthread_create(&thread_ID,NULL,thread_function,&value);

// The main program continues while the thread executes.

// Wait for the thread to terminate.
pthread_join(thread_ID,&exit_status);

// Only the main thread is running now.
return 0;
}

重要函数:

  1. Create a new thread

pthread_create()

1
2
3
4
5
6
int pthread_create(
pthread_t *tid, //thread ID
const pthread_attr_t *attr, //thread attributes
void *(*start_routine)(void*), //pointer to function to execute
void *arg //argument to function
);

Return value: 0 if successful. Error code from otherwise.

Notes: Use a structure to pass multiple arguments to the start routine.

  1. Wait for a thread to terminate

pthread_join

1
2
3
4
int pthread_join(
pthread_t tid, //wait for a thread to terminate
void **status; //thread ID to wait for
);

Return value: 0 for success. Error code from otherwise.

Notes: Once a thread is joined, the thread no longer exists, its thread ID is no longer valid, and it cannot be joined with any other thread.

  1. Get my own thread ID

pthread_self

1
pthread_t pthread_self();

Return value: The ID of the thread that called this function.

Java面向对象

静态变量

静态变量被类中的所有对象共享。静态方法不能访问类中的实例成员。

如果想让一个类中的所有实例共享数据,就要使用静态变量(static variable),也称类变量(class variable)。静态变量将变量值存储在一个公共的内存地址。因为是公共的,所以如果某一个对象修改了静态变量的值,那么同一个类的所有对象都会受影响。

无需创建类的实例就可以调用静态方法(static method)。

要声明一个静态变量或定义一个静态方法,就需要中声明中加上修饰符static。

1
2
3
4
5
static int numberOfObjects;

static int getNumberOfObjects(){
return numberOfObjects;
}

Math类中所有的方法都是静态的。main方法也是静态方法。

类中的常量是被该类的所有对象所共享的。因此,常量应该声明为final static

1
final static double PI = 3.1415;

实例方法可以调用实例方法和静态方法,访问实例数据域或静态数据域。静态方法只能调用静态方法和访问静态数据域。因为静态方法和静态数据域不属于某个特定的对象。

一个常见的设计错误就是将一个本应该声明为静态的方法声明为实例方法。例如factorial(int n)应该定义为是静态的,因为它不依赖于任何具体的实例。

可见性修饰符

可见性修饰符可以用于确定一个类以及它的成员的可见性。

可以在类、方法和数据域前使用public修饰符,表示它们可以被任何其他的类访问。如果没有可见性修饰符,则默认类、方法和数据域是可以被同一个包中的任何一个类访问的。这称作包私有(package-private)或包内访问(package- access)。

包可以用来组织类。用下面的语句:

1
package packageName;

如果定义时没有包,就表示把它放在默认包中。

Java建议最好把类放入包中,而不要使用默认包。

private修饰符限定方法和数据域只能在它自己的类中被访问。

x

如果一个类没有被定义为公共类,则它只能在同一个包内被访问。

不可变对象和类

可以定义不可变类来产生不可变对象。不可变对象的内容不能被改变。

通常创建一个对象后,它的内容是允许之后改变的。有时候也需要创建一个一旦创建其内容就不能再改变的对象。我们称这种对象为一个不可变对象(immutable object),而它的类就是不可变类(immutable class)。例如,String类就是不可变的。如果把set方法去掉,也可能变为不可变类。

如果一个类是不可变的,那么它的所有数据域必须都是私有的,而且没有对任何一个数据域提供公共的set方法。但是这只是充分条件。反例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Student{
private int id;
private String name;
private java.util.Date dateCreated;

public Student(int ssn, String newName){
id=ssn;
name=newName;
dateCreated=new java.util.Date();
}
public String getName(){
return name;
}
public java.util.Date getDateCreated(){
return dateCreated;
}
}

getDateCreated方法返回的是一个引用。通过这个引用可以改变getDateCreated的值:

1
2
3
4
5
6
7
public class Test{
public static void main(String[] args){
Student student=new Student(111222333,"Mika");
java.util.Date dateCreated=student.getDateCreated();
dateCreated.setTime(200000); //Now dateCreated field is changed!
}
}

变量的作用域

实例变量和静态变量的作用域是整个类,无论变量是在哪里声明的。

一个类的实例变量和静态变量称为类变量(class’s variables)或数据域(data field)。在方法内部定义的变量是局部变量。

类变量只能声明一次,但是在一个方法内不同的非嵌套块中,可以多次声明相同的变量名。

如果一个局部变量和一个类变量具有相同的名字,那么局部变量优先,而同名的类变量被隐藏。

this引用

关键字this引用对象自身。它也可以在构造方法内部用于调用同一个类的其他构造方法。

关键字this是指向调用对象本身的引用名。可以用this关键字引用对象的实例成员。

在引用隐藏数据域(例如set方法将数据域名作为参数名)以及调用一个重载的构造方法的时候,this引用是必须的。

1
2
3
4
5
6
7
8
9
public class Circle{
private double radius;
public Circle(double radius){
this.radius=radius; //关键字this可以用于引用隐藏数据域
}
public Circle(){
this(1.0); //关键字this可以用于调用同一个类的另一个构造方法
}
}

继承和多态

面向对象编程允许从已经存在的类中定义新的类,这称为继承。

继承能够避免冗余并使系统更易于理解和易于维护。

父类和子类

如果类C1扩展自另一个类C2,那么称C1为次类(subclass),C2为超类(superclass)。超类也称父类(parent class)或基类(base class),次类又称子类(child class)、扩展类(extended class)或派生类(derived class)。子类从它的父类中继承可访问的数据域或方法,还可添加新数据域和新方法。

父类中的私有数据域是不能被子类访问的,但是可以用get和set方法。

extends

一个Java类只可能直接继承自一个父类,这种限制称为单一继承(single inheritence)。如果使用extends关键字来定义一个子类,它只允许有一个父类。然而,多重继承是可以直接通过接口来实现的。

super

关键字super指代父类,可以用于调用父类中的普通方法和构造方法。

调用父类的构造方法

构造方法用于构建一个类的实例。不同于属性和普通方法,父类的构造方法不会被子类继承。它们只能使用关键字super从子类的构造方法中调用。

调用父类构造方法的语法是:super 或 super(parameters)

语句super()调用父类的无参构造方法,而语句super(arguments)调用与参数匹配的父类的构造方法。它们必须出现在子类构造方法的第一行,这是显示调用父类构造方法的唯一方式。在子类中调用父类构造方法的名字会引起一个语法错误。例如:

1
2
3
4
public CircleFromSimpleGeometricObject(double radius,String color,boolean filled){
super(color,filled);
this.radius=radius;
}

原来是:

1
2
3
4
5
public CircleFromSimple(double radius,String color, boolean filled){
this.radius=radius;
setColor(color);
setFilled(filled);
}

构造方法链(IMPORTANT 354 355)

调用父类的方法

语法是:super.methodName(parameters)

例如:

1
2
3
public void print(){
System.out.println(super.getDateCreated());
}

方法重写

要重写一个方法,需要在子类中使用和父类一样的签名以及一样的返回值类型来对该方法进行定义。

子类从父类中继承方法,有时子类需要修改父类中定义的方法的实现,这称作方法重写(method overriding)。

例如GeometricObject类中的toString方法返回表示几何对象的字符串。这个方法可以被重写,返回表示圆的字符串。

1
2
3
4
5
public class Son extends Father{
public String toString(){ //toString is originally defined in Father
return super.toString()+"\nradius is "+radius;
}
}

Son使用super.toString()访问Father中的toString方法,但是GrandSon不能使用super.super.toString()访问Father中的toString方法。这是一个语法错误。

值得注意的是:

仅当实例方法是可访问时,它才可被覆盖。因为私有方法在它的类本身以外是不能访问的,所以它不能被覆盖。如果子类中定义的方法是父类中私有的,那么这两个方法完全没有关系。

与实例方法一样,静态方法也能被继承。但是静态方法不能被覆盖。如果父类中定义的静态方法在子类中被重新定义,那么在父类中定义的静态方法将被隐藏。可以使用语法:父类名.静态方法名(SuperClassName.staticMethodName)调用隐藏的静态方法。

重载意味着使用同样的名字但是不同的签名来定义多个方法。

重写意味着在子类中提供一个对方法的新的实现。

  • 方法重写发生在通过继承而相关的不同类中;方法重载可以发生在同一个类中,也可以发生在由于继承而相关的不同类中。
  • 方法重写具有相同的签名和返回值类型;方法重载具有相同的名字,但是不同的参数列表。

为了避免错误,可以使用一个特殊的Java语法,成为重写标注(override annotation),在子类的方法前面放一个@Override。例如:

1
2
3
4
5
6
7
public class Son extends Father{
//...
@Override
public String toString(){ //toString is originally defined in Father
return super.toString()+"\nradius is "+radius;
}
}

该标注表示被标注的方法必须重写父类的一个方法。如果具有该标注的方法没有重写父类的方法,编译器将会报错。

Object类及其toString()方法

Java中的所有类都继承自java.lang.Object类。

如果在定义一个类时没有指定继承性,那么这个类的父类就被默认为是Object。例如下面两个类的定义是一样的:

1
2
3
4
5
6
7
public class ClassName{
...
}

public class ClassName extends Object{
...
}

toString()方法的签名是:public String toString()

默认情况下,它返回一个由该对象所属的类名、@符号以及该对象十六进制形式的内存地址组成的字符串。但是通常这个结果没什么用。所以考虑重写这个方法:

1
2
3
public String toString(){
return "created on "+dateCreated+"\ncolor: "+color+" and filled: "+filled;
}
1
2
3
4
5
6
public class TestToString{
public static void main(String[] args) {
Object hahaha=new Object();
System.out.println(hahaha); //或System.out.println(hahaha.toString());
}
}

输出是:java.lang.Object@dcf3e99

多态

多态意味着父类的变量可以指向子类对象。

首先定义两个属于:子类型和父类型。一个类实际上定义了一种类型,子类定义的类型称为子类型(subtype),父类定义的称为父类型(supertype)。

继承关系使一个子类继承父类的特征,并且附加一些新特征。

Java笔记

初学Java,有些东西需要记录一下。

Part 1

Java的方法只能传值,不能传引用,但是可以用对象来解决这个问题。

例如swap函数:

方案1:构造一个新类MyInteger

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class SwapTwoNumbers {
static class MyInteger {
private int a;
public MyInteger(int a) {
this.a = a;
}
public int getValue() {
return a;
}
public void changeValue(int a) {
this.a = a;
}
}
public static void swap(MyInteger a, MyInteger b) {
int t = a.getValue();
a.changeValue(b.getValue());
b.changeValue(t);
}
public static void main(String[] args) {
MyInteger a = new MyInteger(4);
MyInteger b = new MyInteger(10);
System.out.println("a is "+a.getValue()+" and b is "+b.getValue());
swap(a, b);
System.out.println("a is "+a.getValue()+" and b is "+b.getValue());
}
}

方案2:利用main所在的类本身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class t1 {
int a, b;
public t1(int a, int b) {
this.a = a;
this.b = b;
}
public void swap() {
int t = a;
a = b;
b = t;
}
public static void main(String[] args) {
t1 x = new t1(3,4);
System.out.println("a is "+x.a+" and b is "+x.b);
x.swap();
System.out.println("a is "+x.a+" and b is "+x.b);
}
}

方案3:利用数组

1
2
3
4
5
public static void swap(int[] data, int a, int b) {
int t = data[a];
data[a] = data[b];
data[b] = t;
}

Part2

求gcd。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Random;

public class t1 {
public static int gcd(int a, int b) {
//if(a <= 0 || b <= 0) return 0;
if(a%b==0) return b;
return gcd(b, a%b);
}
public static void main(String[] args) {
Random r = new Random();
int a = r.nextInt(), b = r.nextInt();
a=Math.abs(a); b=Math.abs(b);
System.out.println(a+" "+b);
if(a<b) System.out.println(gcd(b,a));
else System.out.println(gcd(a,b));
}
}

求素数。