0%

简单登录程序

跳转:

1
Response.Redirect("URL")

返回弹窗

1
Response.Write("<script>alter('用户名或密码错误');</script>")

文本框的使用

text默认为单行模式

1
2
3
4
5
6
7
8
9
10
11
<p>单行模式</p>
<br />
<asp:TextBox ID="TextBox1" runat="server"></asp:TextBox>
<br />
<p>密码模式</p>
<br />
<asp:TextBox ID="TextBox2" runat="server" TextMode="Password"></asp:TextBox>
<br />
<p>多行模式</p>
<br />
<asp:TextBox ID="TextBox3" runat="server" TextMode="MultiLine"></asp:TextBox>

image-20211209221532497

属性栏修改。

判断单选框

单选框将GroupName设置为一样即可

1
2
3
4
5
6
<label>性别</label>
<asp:RadioButton ID="RadioButton1" runat="server" Text="男" GroupName="sex"/>
&nbsp;&nbsp
<asp:RadioButton ID="RadioButton2" runat="server" Text="女" GroupName="sex"/>
<br />
<asp:Button ID="Button1" runat="server" Text="提交" OnClick="Button1_Click2" />
1
2
3
4
5
6
7
8
9
10
11
protected void Button1_Click2(object sender, EventArgs e)
{
if (RadioButton1.Checked == true)
{
Response.Write("<script>alert('性别为男');</script>");
}
if (RadioButton2.Checked == true)
{
Response.Write("<script>alert('性别为女');</script>");
}
}

判断多选框

1
“+string+”

下拉框

1
2
3
4
5
6
7
<asp:DropDownList ID="DropDownList1" runat="server">
<asp:ListItem>原平</asp:ListItem>
<asp:ListItem>忻州</asp:ListItem>
<asp:ListItem>五台</asp:ListItem>
<asp:ListItem>定襄</asp:ListItem>
<asp:ListItem>五寨</asp:ListItem>
</asp:DropDownList>
1
2
3
DropDownList1.SelectedItem.Value
DropDownList1.SelectedValue

呈现信息

构造一个用于盛放HTML代码的变量,用Response.Write(HTML),可先用Response.Clear()清理当前页面

转换

Convert.ToDouble()

捕获异常

1
2
3
4
5
6
7
try{

}
catch(Exception es)
{

}

显示数据

image-20211210120304445

1
inf.InnerHtml=HTML;

读取全部数据

1
foreach

连接数据库

image-20211210135917242

image-20211210135930367

初始

1
2
3
4
5
6
7
8
9
</system.web>
<system.webServer>
<defaultDocument>
<files>
<clear/>
<add value="index.aspk"/>
</files>
</defaultDocument>
</system.webServer>

显示表

image-20211210175458347

拆包

image-20211210184423626

image-20211210184758134

image-20211210185030345

image-20211210185043844

image-20211210190952668

image-20211210191832719

image-20211210191935390

image-20211211204121826

image-20211211204221557

image-20211211204301439

数据库部分

创建数据库

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
--创建数据库School Classroom Management Information System-SCMIS
create database SCMIS
on primary
(
name='f1',
filename='F:\sqlserver\sqlwj\scmis\f1.mdf',
size=3mb,
maxsize=unlimited,
filegrowth=3%
),
(
name='f2',
filename='F:\sqlserver\sqlwj\scmis\f2.ndf',
size=10mb,
maxsize=500mb,
filegrowth=6mb
)
log on
(
name='f3',
filename='F:\sqlserver\sqlwj\scmis\f3.ldf',
size=1mb,
maxsize=unlimited,
filegrowth=2%
)

创建教师信息表

1
2
3
4
5
6
7
8
9
10
--创建教师信息表
create table 教师信息
(
教师编号 varchar(15) not null,
教师姓名 varchar(15) not null,
性别 varchar(5) not null,
所属院系 varchar(10) not null,
职称 varchar(15) not null,
身份证号 varchar(18) not null
)

创建学生信息表

1
2
3
4
5
6
7
--创建学生信息表
create table 学生信息
(
学号 varchar(9) not null,
院系号 varchar(5) not null,
身份证号 varchar(18) not null
)

创建教室信息

1
2
3
4
5
6
7
--创建教室信息表
create table 教室信息
(
教室编号 varchar(5) not null,
教学楼编号 varchar(2) not null,
楼层号 varchar(2)
)

创建教学楼信息表

1
2
3
4
5
6
--创建教学楼信息表
create table 教学楼信息
(
教学楼名称 varchar(10) not null,
教学楼编号 varchar(5) not null
)

有个信息不匹配,进行修改

1
2
alter table 教室信息
alter column 教学楼编号 varchar(5) not null

创建教室使用信息表

1
2
3
4
5
6
7
8
--创建教室使用信息表
create table 教室使用信息
(
教学楼编号 varchar(5) not null,
教室编号 varchar(5) not null,
时间 varchar(10) not null,
状态 varchar(10) not null
)

创建课程信息表

1
2
3
4
5
6
7
--创建课程信息表
create table 课程信息
(
课程名称 varchar(15) not null,
课程编号 varchar(10) not null,
教师编号 varchar(15) not null,
)

创建课程时间表

1
2
3
4
5
6
7
8
--创建课程时间表
create table 课程时间
(
课程编号 varchar(10) not null,
教师编号 varchar(15) not null,
教师名称 varchar(10) not null,
上课时间 varchar(10) not null
)

修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
alter table 学生信息 add 密码 varchar(15)

alter table 课程时间 add 上课教室 varchar(5)

alter table 教室使用信息 add 开设课程 varchar(15) default '无'

alter table 学生信息 add 姓名 varchar(15)

alter table 教师信息
alter column 所属院系 varchar(15)

alter table 学生信息
alter column 院系号 varchar(15)

alter table 教室使用信息 add 课程编号 varchar(10)

约束

1
2
3
4
5
--将教师信息表中教师编号设置为主键约束,身份证号设为唯一约束
alter table 教师信息
add constraint PK_教师编号 primary key (教师编号)
alter table 教师信息
add constraint UQ_身份证号 unique(身份证号)
1
2
3
4
5
--将学生信息表中学号设置为主键约束,身份证号设为唯一约束
alter table 学生信息
add constraint PK_学号 primary key (学号)
alter table 学生信息
add constraint UQ_身份证号学生 unique(身份证号)
1
2
3
--将教室信息中教室编号设置为主键
alter table 教室信息
add constraint PK_教室编号 primary key(教室编号)
1
2
3
--将教学楼信息中教学楼编号设置为主键
alter table 教学楼信息
add constraint PK_教学楼编号 primary key(教学楼编号)
1
2
3
--将教学楼信息中的教学楼编号与教室信息中的教学楼编号添加外键
alter table 教室信息
add constraint FK_教学楼编号 foreign key(教学楼编号)references 教学楼信息(教学楼编号)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
--将教室使用信息表中教学楼编号与教学楼信息表中的教学楼编号添加外键
alter table 教室使用信息
add constraint FK_教学楼编号教室使用信息 foreign key (教学楼编号)references 教学楼信息(教学楼编号)

--将教室使用信息表中教室编号与教室信息表中的教室编号添加外键
alter table 教室使用信息
add constraint FK_教室编号教室使用信息 foreign key (教室编号)references 教室信息(教室编号)

--将教室使用信息表中教师状态做约束
alter table 教室使用信息
add constraint CK_状态 check(状态='有课' or 状态='讲座' or 状态='活动' or 状态='空闲' or 状态='其他')//删除掉该约束

--将教室使用信息表中教室状态添加默认约束空闲
alter table 教室使用信息
add constraint DF_状态 default '空闲' for 状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
--对课程信息表中课程编号添加主键约束
alter table 课程信息
 add constraint PK_课程编号 primary key (课程编号)




--对课程信息表中教师编号添加外键约束
alter table 课程信息
add constraint FK_教师编号课程信息 foreign key(教师编号)references 教师信息(教师编号)

--对课程时间表中教师编号添加外键约束
alter table 课程时间
add constraint FK_教师编号课程时间 foreign key(教师编号)references 教师信息(教师编号)

--对课程时间表中课程编号添加外键约束
alter table 课程时间
add constraint FK_课程编号课程时间 foreign key(课程编号)references 课程信息(课程编号)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
--对教师信息中的性别添加约束
  alter table 教师信息
  add constraint CK_性别教师 check (性别='男' or 性别='女')

--对教室使用信息的时间进行约束
alter table 教室使用信息
add constraint CK_时间 check (时间='周一一二' or 时间='周一三四' or 时间='周一五六' or 时间='周一七八' or
时间='周二一二' or 时间='周二三四' or 时间='周二五六' or 时间='周二七八' or
时间='周三一二' or 时间='周三三四' or 时间='周三五六' or 时间='周三七八' or
时间='周四一二' or 时间='周四三四' or 时间='周四五六' or 时间='周四七八' or
时间='周五一二' or 时间='周五三四' or 时间='周五五六' or 时间='周五七八' or
时间='周六一二' or 时间='周六三四' or 时间='周六五六' or 时间='周六七八' or
时间='周日一二' or 时间='周日三四' or 时间='周日五六' or 时间='周日七八'
)

修改

1
2
3
4
5
6
7
8
alter table 课程时间
add constraint FK_教室 foreign key(上课教室) references 教室信息(教室编号)

alter table 教室使用信息
alter column 状态 varchar(15) not null

alter table 学生信息
add constraint UQ_ID unique (身份证号)

插入的信息

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
insert into 教师信息
values('001','张三','男','计算机','教授','123456789')
insert into 教师信息
values('002','李四','女','地理与海洋','教授','123123123')
insert into 教师信息
values('003','王五','男','计算机','教授','456456456')

select * from 教师信息

insert into 教学楼信息
values('仙一','001')

insert into 教学楼信息
values('仙二','002')
select * from 教学楼信息

insert into 教室信息
values('1101','001','1')
insert into 教室信息
values('1102','001','1')
insert into 教室信息
values('1103','001','1')
insert into 教室信息
values('1104','001','1')
insert into 教室信息
values('1201','001','2')
insert into 教室信息
values('1202','001','2')
insert into 教室信息
values('1203','001','2')
insert into 教室信息
values('1204','001','2')

insert into 教室信息
values('2101','002','1')
insert into 教室信息
values('2102','002','1')
insert into 教室信息
values('2103','002','1')
insert into 教室信息
values('2104','002','1')
insert into 教室信息
values('2201','002','2')
insert into 教室信息
values('2202','002','2')
insert into 教室信息
values('2203','002','2')
insert into 教室信息
values('2204','002','2')
select * from 教室信息

插入课程信息

1
2
3
4
5
6
7
8
exec information_entry '数据库','001','周一三四','张三','001','001','1102'
exec information_entry '数据库','001','周二三四','张三','001','001','1102'
exec information_entry '地理综合认知','002','周三三四','李四','002','001','1202'
exec information_entry '地理综合认知','002','周四三四','李四','002','001','1202'
exec information_entry '机器学习','003','周一五六','张三','001','002','2102'
exec information_entry '机器学习','003','周二五六','张三','001','002','2102'
exec information_entry '机器学习','004','周四七八','王五','003','002','2202'
exec information_entry '机器学习','004','周五七八','王五','003','002','2202'

存储

插入课程信息存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
--插入课程信息

go
create procedure information_entry
@coursename varchar(15),--输入参数,课程名称
@coursenumber varchar(10),--输入参数,课程编号
@coursetime varchar(10),--输入参数,课程时间
@teachername varchar(10),--输入参数,教师名称
@teachernumber varchar(15),--输入参数,教师编号
@buildingnumber varchar(5),--输入参数,教学楼编号
@roomnumber varchar(5)--输入参数教室编号
AS
insert into 课程信息
values(@coursename,@coursenumber,@teachernumber)
insert into 课程时间
values(@coursenumber,@teachernumber,@teachername,@coursetime)
insert into 教室使用信息
values(@buildingnumber,@roomnumber,@coursetime,'有课')
go

修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
create procedure information_entry
@coursename varchar(15),--输入参数,课程名称
@coursenumber varchar(10),--输入参数,课程编号
@coursetime varchar(10),--输入参数,课程时间
@teachername varchar(10),--输入参数,教师名称
@teachernumber varchar(15),--输入参数,教师编号
@buildingnumber varchar(5),--输入参数,教学楼编号
@roomnumber varchar(5)--输入参数教室编号
AS
insert into 课程信息
values(@coursename,@coursenumber,@teachernumber)
insert into 课程时间
values(@coursenumber,@teachernumber,@teachername,@coursetime,@roomnumber)
insert into 教室使用信息
values(@buildingnumber,@roomnumber,@coursetime,'有课',@coursename,@coursenumber)
go

查询指定教室使用情况

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
--查询指定教室使用情况
create procedure classroom_query
@room varchar(5),
@time varchar(10),
@state varchar(10)='空闲' output
AS
declare @state1 varchar(10)
select @state=状态
from 教室使用信息
where 教室编号=@room and 时间=@time
if @state IS NULL
set @state='空闲'
go

修改
create procedure classroom_query
@room varchar(5),
@time varchar(10),
@state varchar(10)='空闲' output
AS

select @state=状态
from 教室使用信息
where 教室编号=@room and 时间=@time
if @state IS NULL
set @state='空闲'
else if @state='有课'
begin
select @state=开设课程
from 教室使用信息
where 教室编号=@room and 时间=@time

end
go

查询指定课程

1
2
3
4
5
6
7
8
9
10
create procedure course_query
@name varchar(10),
@state varchar(10) output
AS

select 课程信息.课程名称,课程信息.课程编号,课程时间.教师名称,课程时间.上课时间
from 课程时间 inner join 课程信息 on 课程信息.课程编号=课程时间.课程编号
where 课程信息.课程名称=@name
go

租借教室

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
go
create procedure borrow
@building varchar(5),
@room varchar(5),
@time varchar(10),
@reason varchar(10)
AS
declare @state varchar(10)
select @state=状态
from 教室使用信息
where 教室编号=@room and 时间=@time
if @state IS NULL
begin
set @state='空闲'
print '此时教室空闲,可以借用'
insert into 教室使用信息
values(@building,@room,@time,@reason)
end
else
print '此教室被占用,正在'+@state
go

修改为

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
declare @state varchar(10)
go
create procedure borrow
@building varchar(5),
@room varchar(5),
@time varchar(10),
@reason varchar(10),
@state varchar(10) output
AS
declare @state1 varchar(10)
select @state1=状态
from 教室使用信息
where 教室编号=@room and 时间=@time
if @state1 IS NULL
begin
set @state1='空闲'

print '此时教室空闲,可以借用'
insert into 教室使用信息
values(@building,@room,@time,@reason,'其他','其他')
end
else
print '此教室被占用,正在'+@state1
set @state=@state1
print @state
go

select *from 教室使用信息
declare @state varchar(10)
exec borrow '001','1102','周一三四','其他',@state output
print @state

判断密码是否正确

1
2
3
4
5
6
7
8
9
10
11
12
13
create procedure password_query
@user varchar(9),
@password varchar(15),
@state varchar(10)='false' output
AS
declare @password1 varchar(15)
select @password1=密码 from 学生信息
where 学号=@user
if @password1 IS NOT NULL and @password1=@password
set @state='true'
else
set @state='false'
go

删除

1
2
3
4
5
6
create procedure delete_course
@number varchar(10)
AS
delete from 课程信息 where 课程编号=@number
delete from 教室使用信息 where 课程编号=@number
delete from 课程时间 where 课程编号=@number

编写存储插入大量数据

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
--创建循环插入1000条记录的存储过程
CREATE PROCEDURE SP_CREATE_DATA1
AS
declare @cnt INT=0;
while @cnt<100
begin
declare @a varchar(8)
set @a=(SELECT LEFT(LOWER(NEWID()),8))
declare @b varchar(8)
set @b=(SELECT LEFT(LOWER(NEWID()),9))
declare @c INT
set @c=(SELECT 1 + RAND() * 2)
INSERT INTO 学生信息
VALUES
(
@a

,CASE @c --随机选取3个枚举值
when 1 then '001'
when 2 then '002'
when 3 then '003'
END
,@b
,@a
,@b

);
set @cnt=@cnt+1;
end;


GO
exec SP_CREATE_DATA1

CREATE PROCEDURE SP_CREATE_DATA3
AS
declare @cnt INT=0;
while @cnt<100
begin
declare @a varchar(8)
set @a=(SELECT LEFT(LOWER(NEWID()),8))
declare @b varchar(8)
set @b=(SELECT LEFT(LOWER(NEWID()),9))
declare @c INT
set @c=(SELECT 1 + RAND() * 2)
declare @d varchar(8)
set @d=replace(str(@cnt,8),' ','0')
INSERT INTO 学生信息
VALUES
(
@d

,CASE @c --随机选取3个枚举值
when 1 then '001'
when 2 then '002'
when 3 then '003'
END
,@b
,@a
,@b

);
set @cnt=@cnt+1;
end;
exec SP_CREATE_DATA3

declare @cnt INT=1
declare @d varchar(8)
set @d=replace(str(@cnt,8),' ','0')
print @d
select * from 学生信息

视图

创建视图,查询张三老师课程

1
2
3
4
5
6
7
8
--创建视图,查询计算机学院张三老师所有课程名称
go
create VIEW view_张三
as
select 课程名称
from 课程信息
where 教师编号='001'
go

例子

1
2
3
4
5
6
exec information_entry '机器学习','004','周六七八','王五','003','002','2202'
select *from 教室使用信息
declare @state varchar(15)
exec classroom_query '2202','周六七八',@state output
print @state

1
2
3
declare @state varchar(10)
exec password_query '191830076','0323',@state output
print @state

计算机网络和因特网

什么是因特网

具体构成描述

端系统通过通信链路和分组交换机连接到一起。

两种最著名的分组交换机为路由器和链路层交换机。链路层交换机通常用于接入网中,路由器通常用于网络核心中。

端系统通过 因特网服务提供商(Internet Service Provider,ISP)接入因特网。

TCP(Transmission Control Protocol,传输控制协议)和 IP(Internet Protocol,网际协议)是因特网中最为重要的两个协议。

因特网的主要协议称为 TCP/IP协议。

因特网工程任务组。Internet Engineering Task Force,IETF

服务描述

有些应用程序涉及多个相互交换数据的端系统,称为 分布式应用程序

与因特网相连的端系统提供了一套 套接字接口,该接口规定了运行在一个端系统上的程序请求因特网基础设施向运行在另一个端系统上的特定目的地程序交付数据的方式。

协议

协议定义了在两个或多个通信实体之间交换的报文的格式和顺序,以及报文发送和/或接受一条报文或其他事件所采取的动作。

网络边缘

端系统也被称为 主机,因为它们容纳应用程序,主机有时又被划分为客户和服务器。

接入网

家庭介入

宽带住宅接入有两种最流行的类型: 数字用户线(Digital Subscriber Line,DSL)和电缆。

企业(和家庭)接入:以太网和WIFI

局域网LAN

广域无线接入:3G和LTE

物理媒体

物理媒体分成两种类型:导引型媒体和非导引型媒体

网络核心

分组交换

存储转发传输

多数分组交换机在链路的输入端使用 存储转发传输机制。存储转发传输是指在交换机能够开始向输出链路传输该分组的第一个比特之前,必须接收到整个分组。

排队时延和分组丢失

每台分组交换机有多条链路与之相连。对于每条相连的链路,该分组交换机具有一个输出缓存,它用于粗出路由器准备发往那条链路的分组。

转发表和路由选择协议

每台路由器具有一个转发表,用于将目的地址映射成为输出链路。

电路交换

在电路交换网络中,在端系统通信会话期间,预留了端系统间沿路径通信所需要的资源。

电路交换网络中的复用

链路中的电路是通过 频分复用(FDM)或 时分复用(TDM)来实现的。

分组交换与电路交换的对比

趋势朝着分组交换方向发展。

网络的网络

今天的因特网是一个网络的网络,由十多个第一层ISP和数十万个较低层ISP组成。

分组交换网中的时延、丢包和吞吐量

分组交换网中的时延概述

这些时延最为重要的是 节点处理时延、排队时延、传输时延和传播时延,这些时延累加起来是节点总时延。

时延的类型

img

处理时延

$d_{proc}$

检查分组首部和决定将该分组导向何处所需要的时间是 处理时延的一部分。处理时延也能够包括其他因素,如检查比特级别的差错所需要的时间。

排队时延

$d_{queue}$

在队列中,当分组在链路上等待传输时,他经受排队时延。

传输时延

$d_{trans}$

用L比特表示该分组的长度,用R bps表示从路由器A到路由器B的链路传输速率。传输时延时L/R。这是将所有分组的比特推向链路所需要的时间。

传播时延

$d_{prop}$

从该链路的起点到路由器B传播所需要的时间是传播时延。

排队时延和丢包

令a表示分组到达队列的平均速率(a的单位是分组/秒)。R是传输速率,即从队列中推出比特的速率。假定所有分组都是由L比特组成。则比特到达队列的平均速率是La bps。比率La/R被称为流量强度。

设计系统时流量强度不能大于1

丢包

因为排队容量是有限的,随着流量强度接近1.排队时延并不是无穷大,相反,到达的分组将发现一个满的队列。由于没有地方存储,路由器将丢弃该分组。

计算机网络中的吞吐量

在任何时间瞬间的 瞬时吞吐量是主机B接受到该文件的速率。

img

协议层次及其服务模型

分层的体系结构

协议分层

各层的所有协议被称为 协议栈。因特网的协议栈由五个层次组成:物理层、链路层、网络层、传输层和应用层。

应用层

HTTP:提供了Web文档的请求和传送。

SMTP:提供了电子邮件报文的传送。

FTP:提供两个端系统间的文件传送。

报文:位于应用层的信息分组称为报文。

运输层

TCP/UDP

报文段:我们把运输层的分组称为报文段。

网络层

因特网的网络层负责将称为 数据报的网络层分组从一台主机移动到另一台主机。

链路层

为了将分组从一个节点移动到路径上的下一个节点,网络层必须依靠该链路层的服务。特别是在每个节点,网络层将数据报下传给链路层,链路层沿着路径将数据报传递给下一个节点。

:链路层分组

物理层

物理层的任务是将该帧中的一个个比特从一个节点传递到下一个节点。

OSI模型

开放系统互联模型:应用层、表示层、会话层、传输层、网络层、数据链路层、物理层。

封装

一个应用层报文被传送给传输层,在最简单的情况下,运输层收取到报文并附上附加信息,该首部将被接收端的运输层使用。应用层报文和运输层首部信息一道构成了运输层报文段。以此类推。我们可以看到,在每一层,一个分组具有两种类型的字段:首部字段和有效载荷字段。有效载荷字段通常来自上一层分组。

附加

计算机网络就是自治互联的计算机集合。

协议的三要素:语法、语义、同步/时序。

分组交换网络传输分组的基本工作方式是(存储-转发)。

计算机网络从结构上可以划分为网络核心,网络边缘和接入网。

OSI中应用层,表示层,会话层,传输层为端到端层。实现路由功能为网络层。

应用层

应用层协议原理

网络应用程序体系结构

应用程序体系结构由应用程序研发者设计,规定了如何在各种端系统上组织应用程序。

客户-服务器体系结构中,有一个总是打开的主机称为服务器,它服务于来自许多其他称为客户的主机的请求。

在这个体系中,客户之间不通信;并且服务器具有固定的周知的地址,称为IP地址。

image-20211205142034282

P2P体系结构中,对于位于数据中心的专用服务器有最小的依赖。相反,应用程序在间断连接的主机对之间直接通信,这些主机被称为

对等方。P2P具有自扩展性。

image-20211205142049905

进程通信

客户和服务器进程

在一个P2P文件共享系统中,文件从一个对等方中的进程传输到另一个对等方的进程。通常将这两个进程之一标识为客户,另一个标识为服务器。在P2P共享文件中,一个进程既是客户又是服务器。

进程与计算机网络之间的接口

进程通过一个称为套接字的软件接口向网络发送报文和从网络接收报文。套接字也称为应用程序和网络之间的应用程序编程接口。

应用程序开发者对于运输层的控制权限仅限于:选择运输层协议;也许能设定几个运输层参数。但是对于套接字的运输层段几乎没有控制权。

进程寻址

为标识该接收进程,需定义:主机的地址;在目的主机中指定接收进程的标识符。

在因特网中,主机由I地址标识。

发送进程还必须指定运行在接收主机上的接收进程,目的地端口号用于这个目的,

Web服务器端口号:80

邮件服务器进程:25

FTP:21

可供应用程序使用的运输服务

从四个方面分类:

可靠数据传输

运输层协议能够潜在的向应用程序提供的一个重要服务是进程到进程的可靠数据传输。

吞吐量

具有吞吐量要求的应用程序被称为带宽敏感的应用。

弹性应用能够根据当时可用的带宽或多或少地利用可供使用的吞吐量。

定时

一个保证的例子:发送方注入进套接字中的每个比特到达接收方的套接字不迟于100ms。

安全性

运输协议能够为应用程序提供一种或多种安全性服务。

因特网提供的运输服务

TCP服务

包括面向连接服务和可靠数据传输服务。

面向连接的服务:在应用处数据报文开始流动之前,TCP让客户和服务器互相交换运输层控制信息。这就是握手,在握手阶段后,一个 TCP连接就在两个进程的套接字之间建立。

可靠的数据传送服务:通信进程能够依靠TCP,无差错,按适当顺序交付所有发送的数据。

TCP协议还具有拥塞控制机制。

UDP服务

仅提供最小服务。UDP是无连接的。提供不可靠数据传送服务。

没有拥塞控制机制。

应用层协议

定义了运行在不同端系统上的应用程序进程如何相互传递报文。

特别是应用层协议定义了:

交换的报文类型;

各种报文类型的语法;

字段的语义;

确定一个进程何时以及如何发送报文,对报文进行响应的规则。

Web的应用层协议是HTTP。

电子邮件的主要应用层协议是SMTP。

涉及的网络应用

主要讨论:Web,文件传输,电子邮件,目录服务,流式视频和P2P。

Web和HTTP

HTTP概括

应用层协议为:超文本传输协议(HyperText Transfer Protocol,HTTP).

HTTP由一个客户程序和一个服务器程序实现。

WEB浏览器实现了HTTP的客户端。

Web服务器实现了HTTP的服务器端,用于存储Web对象,每个对象由URL寻址。

HTTP定义了Web客户向Web服务器请求Web页面的方式,以及服务器向客户传送Web页面的形式。

HTTP服务器并不保存关于客户的任何信息,所以我们说HTTP是一个 无状态协议

非持续连接和持续连接

非持续连接:每一个请求/响应是经一个单独的TCP连接发送。

持续连接:所有请求及其响应经相同的TCP连接发送。

往返时间(RTT):一个短分组从客户到服务器然后再返回客户所花费的时间。RTT包括分组传播时延,分组在中间路由器和交换机上的排队时延以及分组处理时延。

HTTP报文格式

HTTP请求报文

img

第一行叫请求行。有三个字段,方法字段,URL字段,HTTP版本字段。

之后的行叫做首部行。

第二行指明了对象所在的主机。

第三行该浏览器告诉服务器不要麻烦的使用持续连接,它要求服务器发送完之后就关闭该连接。

第四行指明用户代理,即向服务器发送请求的浏览器的类型。

第五行表示得到该对象的语言版本。

HTTP响应报文

img

一个初始状态行,六个首部行和实体体。

状态行有三个字段:协议版本字段,状态码,相应状态信息。

第二行告诉客户发送报文完后将关闭该TCP连接。

第三行DATE为服务器产生并发送该响应报文的日期和时间。这个时间是服务器从文件系统中检索到该对象,插入响应报文,并发送该响应报文的时间。

第四行指示该报文由什么服务器产生。

第五行指示了该对象创建或最后修改的时间和日期。

第六行指示了被发送对象中的字节数。

第七行指示了实体体对象是HTML文本。

一些常见的状态码:

200 OK:请求成功

301 Moved Permanently:请求的对象已经被永久转移。

400 Bad Request:一个通用差错码,指示该请求不能被服务器理解。

404 Not Found:被请求的文档不在服务器上。

505 HTTP Version Not Supported:服务器不支持请求报文使用的HTTP版本协议。

用户与服务器的交互:cookie

cookie技术有四个组件:

在HTTP响应报文中的一个cookie首部行;

在HTTP请求报文中的一个cookie首部行;

在用户端系统中保留有一个cookie文件,并由用户的浏览器进行管理;

位于Web站点的一个后端数据库。

Web缓存

也叫代理服务器。其既是客户又是服务器。

内容分发网络CDN

条件GET方法

因特网中的电子邮件

因特网电子邮件系统由三个主要组成部分:用户代理;邮件服务器;简单邮件传输协议(SMTP)。

发送邮件的为SMTP的客户端。

SMTP

SMTP一般不使用中间邮件服务器发送邮件。

与HTTP对比

HTTP是一个拉协议,即在方便的时候,某些人在Web服务器上装载信息,用户使用HTTP从该服务器拉取这些信息。

SMTP基本上是一个推协议,即发送邮件服务器把文件推向接收邮件服务器。

SMTP要求每个报文采用7比特ASCLL码格式。若包含非7比特ASCLL字符,则该报文必须按照7比特ACLL进行编码。

对于一个既包含文本又包含图形的文档。HTTP把每个对象封装到自己的响应报文,而SMTP则把所有报文对象放在一个报文中。

邮件访问协议

用户代理不能通过SMTP得到报文,因为取报文是一个拉操作,而SMTP为一个推操作。所以引入其他协议。

POP3第三版的邮局协议

随着TCP连接,POP3按照三个阶段进行工作:特许,事务处理以及更新。

特许阶段:用户代理发送(以明文形式)用户名和口令以鉴别用户。

事务处理阶段:用户代理取回报文。同时还可以做以下操作,对报文做删除标记,取消报文删除标记,以及获取邮件的统计信息。

更新阶段:出现在客户发出quit命令后,目的是结束POP3会话,这时,邮件服务器删除那些标记为删除的报文。

DNS:因特网的目录服务

我们需要一种能进行主机名到IP地址转换的目录服务。这就是 域名系统DNS的主要任务。DNS是:

一个由分层的DNS服务器实现的分布式数据库;一个使得主机能够查询分布式数据库的应用层协议。

DNS运行在UDP之上,使用53号端口。

DNS其他一些重要服务:

主机别名;邮件服务器别名;负载分配。

DNS工作机理概述

分布式、层次数据库

根DNS服务器

顶级域服务器:com,org,uk等

权威DNS服务器

另外有本地DNS服务器,但不属于该服务器层次结构。

DNS缓存

改善时延性能,减少在因特网上到处传输的DNS报文数量。

DNS记录和报文

共同实现DNS分布式数据库的所有DNS服务器存储了 资源记录(RR),RR提供了主机名到IP地址的映射。

资源记录是一个包含了下列字段的四元组:

1
(Name,Value,Type,TTL)

TTL是该记录的生存时间,它记录了资源记录应当从缓存中删除的时间。NAME和VALUE的取值取决于TYPE:

若TYPE=A,则Name为主机名,Value为该主机名对应的IP地址。

若Type=NS,则Name是个域,而Value是个知道如何获得该域中主机IP地址的权威DNS服务器的主机名。

若Type=CNAME,则Value是别名为Name的主机对应的规范主机名。

若Type=MX,则Value是个别名为Name的邮件服务器的规范主机名。

DNS报文

DNS只有查询和回答报文,并且有着相同的格式。

img

P2P文件分发

分发时间是所有N个对等方得到该文件的副本所需要的时间。

BitTorrent是一种用于分发的流行P2P协议。参与一个特定文件分发的所有对等方的集合称为洪流。

在决定请求哪些块的过程中,采用 最稀缺优先的技术。针对他没有的块在他的邻居中决定最稀缺的块(最稀缺的块就是那些在他的邻居中副本数量最少的块)。

为决定响应哪个请求,他根据当前能够以最高速率向他提供数据的邻居,给出其优先权。每过10秒,重新计算,每过30秒,随机选择一个。

附加

网络应用体系结构主要包括C/S、纯P2P、混合模式三种类型。

流量控制关注的是接收端数据接收处理与缓存能力;拥塞控制关注的是网络传输能力。

HTTP1.0与HTTP1.1的区别

1
2
1.0:非持续性,每个TCP连接最多允许一个传输对象,方法有GET,POST,HEAD
1.1:持续性连接,每个TCP连接允许传输多个对象,方法增加PUT,DELETE

HTTP无状态性:不记录用户信息

WEB缓存

1
缩短客户请求时间;减少机构/组织的流量;在大范围内实现有效的内容分发

递归查询与迭代查询

1
递归查询请求1次,迭代查询请求多次

FTP客户和服务器传递FTP命令时,用的是(建立在TCP之上的控制连接)

典型的邮件接收协议:POP3,IMAP,HTTP

运输层

概述和运输层服务

运输层协议为运行在不同主机上的应用程序之间提供了逻辑通信功能。

运输层和网络层的关系

网络层提供了主机之间的逻辑通信,而运输层为运行在不同主机上的进程之间提供了逻辑通信。

运输层协议只工作在端系统。

因特网运输层概述

UDP用户数据报协议

TCP传输控制协议

因特网网络层协议有一个名字叫IP,即网际协议。IP的服务模型是尽力而为交付服务,但并不做任何保证。故IP也被称为不可靠服务。

UDP和TCP最基本的责任是,将两个端系统间IP的交付服务扩展为运行在端系统上的两个进程之间的交付服务。

将主机间交付扩展到进程间交付被称为 运输层的多路复用多路分解

多路复用与多路分解

将运输层报文段中的数据交付到正确的套接字的工作称为多路分解

在源主机从不同套接字中收集数据块,并为每个数据块封装上首部信息从而生成报文段,然后将这些报文段传递到网络层,所有这些称为 多路复用

运输层多路复用要求:套接字有唯一标识符;每个报文段有特殊字段来暗示该报文段要交付的套接字。

img

如图,这些特殊字段是源端口号字段和目的端口号字段。端口号是一个16比特的数,大小在0-65535之间。0-1023范围的端口号称为周知端口号。

无连接的多路复用与多路分解

一个UDP套接字是由一个二元组全面标识的,该二元组包含一个目的IP地址和一个目的端口号。

如果两个UDP报文段有不同的源,但是具有相同的目的IP地址和目的端口号,那么这两个报文段将通过相同的套接字被定向到相同的进程。

面向连接的多路复用与多路分解

TCP套接字由一个四元组(源IP地址,源端口号,目的IP地址,目的端口号)来标识的。

与UDP不同的是,两个具有不同源IP地址或源端口号的到达TCP报文段将被定向到两个不同的套接字。

无连接运输:UDP

DNS采用UDP。

采用UDP原因:

关于发送什么数据以及何时发送的应用层控制更为精细;

无需建立连接;

无连接状态;

分组首部开销小。

UDP用于承载网络管理数据(SNMP)。

需要注意的是,使用UDP的应用是可能实现可靠数据传输的。

UDP报文段结构

img

UDP首部只有4个字段,每个字段由两个字节组成。长度字段指示了在UDP报文段中的字节数。接收方使用检验和来判断是否出差错。

UDP检验和

UDP提供检验和的原因是不能保证源和目的之间的所有链路能提供差错检验。在既无法确保逐链路的可靠性,又无法确保内存中的差错检验的情况下,如果端到端数据传输服务要提供差错检测,UDP就必须在端到端基础上在运输层提供差错检测。这是一个在系统设计中被称颂的 端到端原则的例子,该原则表述为因为某种功能必须基于端到端实现。

UDP对差错恢复无能为力。

可靠数据传输原理

rdt 可靠数据传输

udt 不可靠数据传输

构造可靠数据传输协议

经完全可靠信道的可靠数据传输:rdt1.0
经具有比特差错信道的可靠数据传输:rdt2.0

基于肯定确认和否定确认重传机制的可靠数据传输协议称为 自动重传请求协议(ARQ)

ARQ协议中还需要另外三种协议功能来处理存在比特差错的情况:

差错检测;接收方反馈(ACK,NAK);重传

停等:发送方将不会发送新数据,除非发送方确信接收方已正确接收当前分组。

考虑处理受损ACK和NAK时的三种可能:

(1)接收方复述其回答。

(2)增加足够的检验和比特。

(3)收到受损的ACK或NAK时,重传当前数据分组。但无法知道接收到的是新的还是重传。

解决这个问题的方法是在数据分组中添加一新字段,让发送方对其数据进行编号。

rdt2.1使用了从接收方到发送方的肯定确认和否定确认。当接收到失序的分组时,接收方对所接受的分组发送一个肯定确认。如果收到受损的分组,则接收方将发送一个否定确认。如果不发送NAK,而是对上次正确接收分组的一个ACK,也能实现与NAK一样的效果。即接收冗余ACK.

rdt2.2在有比特差错信道上实现的一个无NAK的可靠数据传输协议,

经具有比特差错的丢包信道的可靠数据传输:rdt3.0

基于时间重传,介入倒计时定时器。

rdt3.0又称为比特交替协议。

在数据传输中,检验和、序号、定时器、肯定和否定确定分组这些技术都起到了必不可少的作用。

流水线可靠数据传输协议

信道利用率:发送方实际忙于将发送比特送进信道的那部分时间与发送时间之比。

引入流水线,对可靠数据传输协议带来以下影响:

增加序号范围,每个传输分组必须有唯一的序号;

协议的发送方和接收方不得不缓存多个分组;

解决流水线差错恢复有两种方法,回退N步选择重传

回退N步

GBN协议。

我们将基序号(base)定义为最早未确认分组的序号。下一个序号(nextseqnum)定义为最小的未使用序号(即下一个待发分组的序号),则将序号范围分成四段:

1
2
3
4
[0,base-1]已经发送被确认
[base,nextseqnum-1]已发送但未被确认
[nextseqnum,base+N-1]可用还未被发送
最后 不可用

N常被称为窗口长度。GBN也被称为滑动窗口协议。

采用累积确认,若超时,则重发所有已发送但还未被确认过的分组。

在GBN协议中,接收方丢弃所有失序分组。

选择重传

SR

SR接收方将确认一个正确接收的分组而不管其是否按序。失序的分组将被缓存知道所有丢失分组皆被收到为止。

img

窗口长度必须小于或等于序号空间大小的一半。

总结

img

面向连接的运输:TCP

TCP连接

TCP被称为是 面向连接的。中间路由器对TCP连接完全视而不见,他们看到的是数据报,而不是连接。

TCP连接提供的是全双工服务。TCP连接也总是点对点的。

三次握手中前两次不承载有效载荷,第三次可以承载有效载荷。

TCP可从缓存中取出并放入报文段中的数据数量受限于 最大报文段长度(MSS)

MSS通常根据最初确定的由本地发送主机发送的最大链路层帧长度(即所谓的 最大传输单元MTU)来设置。

TCP为每块客户数据配上一个TCP首部,从而形成多个 TCP报文段

TCP报文段结构

img

与UDP一样,首部包含 源端口号目的端口号检验和字段

TCP报文段首部还包含以下字段:

32比特的 序号字段和32比特的 确认号字段。用来实现可靠数据传输服务。

16比特的 接收窗口字段,用于流量控制。

4比特的 首部字段长度,通常选项字段为空,所以TCP首部的典型长度是20字节。

可选与变长的 选项字段,用于发送方与接收方协商最大报文段长度。

6比特的 标志字段

序号和确认号

一个报文段的序号是该报文段首字节的字节流编号。

主机A填充进报文段的确认号是主机A期望从主机B收到的下一字节的序号。

TCP只确认该流中至第一个丢失字节为止的字节,所以TCP被称为提供 累积确认

可靠数据传输

TCP的可靠数据传输服务确保一个进程从其接收缓存中读出的数据流是无损坏、无间隙、非冗余和按序的数据流。

超时间隔加倍

在这种修改中,每次TCP重传时都会将下一次的超时间隔设为先前值的两倍。

快速重传

一旦收到三个冗余ACK,就进行快速重传。

对TCP的一种修改意见是所谓的 选择重传

流量控制

TCP为它的应用程序提供了 流量控制服务以消除发送方使接收方缓存溢出的可能性。

TCP发送方也可能因为IP网络的拥塞而被遏制,这种形式的发送方的控制被称为拥塞控制

TCP通过让发送方维护一个被称为 接收窗口的变量来提供流量控制。

当接收窗口等于0时,仍可发送一个较小的数据,以把窗口信息带回来。

TCP连接管理

img

确认y表明在y之前的所有字节都被正确接收。

拥塞控制原理

当一个分组沿一条路径被丢弃时,每个上游路由器由于转发该分组到丢弃该分组而使用的传输容量最终被浪费。

拥塞控制方法

端到端拥塞控制;

网络辅助的拥塞控制

TCP拥塞控制

指导原则:

1
2
3
一个丢失的报文段意味着拥塞,因此当丢失报文段时应当降低TCP发送方的速率。
一个确认报文段指示该网络正在向接收方交付发送方的报文。
带宽探测。

TCP拥塞控制算法

慢启动

cwnd(拥塞窗口)的值通常初始置为一个MSS的较小值。当传输的报文段首次被确认就增加一个MSS。成指数增长。

拥塞避免

当进入拥塞状态,cwnd值为上次拥塞的一半,然后线性增长。

快速恢复

阈值前指数,阈值后线性。

TCP拥塞控制

加性増乘性减(丢包由三个冗余ACK)

公平性

TCP具有公平性。

附加

典型的邮件接收协议有 POP,IMAP,HTTP。

实现文件分发应用时,采用P2P技术比典型的client/server技术更快。

发送窗口大小取决于min(rwnd,cwnd).

其中rwnd是接收缓存的空余大小,表示接收方还能接收多少。
cwnd就是我们常常画慢增长曲线,拥塞避免曲线等等分析的纵轴数值。

附一道题:

1
https://blog.csdn.net/aodubi0638/article/details/102144555

接收窗口 发送窗口 拥塞窗口

1
https://blog.csdn.net/ligupeng7929/article/details/79597423

image-20211205152701158

计算UDP校验和时,封装UDP报文段的IP数据报某些字段也会参与:源IP地址,目的IP地址,协议。

image-20211205163248158

image-20211205163258119

网络层

网络层能够被分为两个互相作用的平面:数据平面和控制平面。

网络层概述

网络层的作用:即将分组从一台发送主机移到一台接收主机。为此,需要使用两种重要的网络层功能:

转发:当一个分组到达某路由器的一条输入链路时,该路由器必须将该分组移动到适当的输出链路。

路由选择:当分组从发送方流向接收方时,网络层必须决定这些分组所采用的路由或路径。计算这些路径的算法被称为 路由选择算法

转发:将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地工作。

路由选择:确定分组从源到目的地所采取的端到端路径的网络范围处理过程。

每台路由器中有一个关键元素是它的 转发表

网络层核心功能

转发与路由

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

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

连接建立

某些网络的重要功能:ATM,X.25,帧中继

数据分组传输之前两端主机需要首先建立虚拟、逻辑连接

网络层连接是两个主机之间(路径上的路由器等网络设备参与其中),传输层连接为两个应用进程间(对中间网络设备透明)

网络层服务模型

无连接服务(connection-less service)

1
2
3
4
5
6
7
8
9
不事先为系列分组的传输确定传输路径;

每个分组独立确定传输路径;

不同分组可能传输路径不同;

数据报网络。


连接服务(connection service)

1
2
3
4
5
首先Wie系列分组的传输确定从源到目的经过的路径;
然后沿该路径(连接)传输系列分组;
系列分组传输路径相同;
传输结束后拆除连接
虚电路网络

虚电路与数据报网络

虚电路:一条从源主机到目的主机,类似于电路的路径。

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

通信过程:呼叫建立->数据传输->呼叫拆除

每个分组携带虚电路表示(VCID),而不是目的主机地址。

虚电路经过的每个网络设备,维护每条经过它的虚电路连接状态。

每条虚电路包括

1
2
3
4
从源主机到目的主机的一条路径
虚电路号,沿路每段链路一个编号(虚电路号会变化)
沿路每个网络层设备,利用转发表记录经过的每条虚电路
同一条VC,在每段链路的VCID不同

虚电路信令协议:

用于VC的建立,维护拆除

数据报网络

网络层无连接;每个分组携带目的地址;路由器根据分组的目的地址转发分组。

路由算法确定通过网络的端到端路径;咋混发表确定在本路由器如何转发分组。

最长前缀匹配优先。

数据报网络简化网络,复杂边缘。

VC网络简化边缘,复杂网络。

IPv4协议

IP数据报

img

版本:4比特

首部长度:4比特(以4字节为单位)

服务类型:8比特,区分服务(只有在网络提供服务时才使用,通常取0)

长度:IP分组的总字节数,最大长度65535B

寿命:TTL,占8位,标识IP分组在网络中可以通过的路由器数。TTL=0,则丢弃该分组。

协议:8位,指示封装的是哪个协议。

首部校验和:16位,计算校验和时,置全0。逐跳计算

最大传输单元MTU-链路层数据帧可封装数据的上限。

不同链路的MTU不同。

IP数据分片

IP分片到达目的主机后进行重组。

标识字段占16位:标识一个IP分组。每产生IP分组+1.

标志位:3位。保留|DF|MF

1
2
3
4
DF=1禁止分片
DF=0允许分片
MF=1非最后一片
MF=0最后一片或未分片

片偏移:13比特,相对偏移量。片偏移字段以8字节为单位。

分片时每个分片的标识复制原IP分组的标识。

image-20211204104154990

IP编址

32比特

IP地址

1
2
网络号-高位比特
主机号-低位比特

IP子网:IP地址具有相同网络号的设备接口

不跨越路由器可以彼此物理联通的接口。

有类IP地址

image-20211203200924251

image-20211203201114136

image-20211203201541925

IP子网与子网划分

image-20211203203222147

子网掩码:32比特

取值:NetID、SubID全取1

HostID全取0

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

image-20211203203919857

主机路由:子网掩码 255.255.255.255

CIDR与路由聚合

无类域间路由CIDR

消除传统的ABC类地址界限。

无类地址格式:

1
a.b.c.d/x x为前缀长度

提高IPV4地址空间分配效率;

提高路由效率

DHCP协议

动态主机配置协议。

从服务器动态获取:

1
2
3
4
IP地址
子网掩码
默认网关地址
DNS服务器名称与IP地址

默认网关:IP或数据报要离开时送到哪个接口

由于DHCP具有将主机连接进一个网络的网络相关方面的自动能力,故他又被称为 即插即用协议零配置

image-20211203210949264

NAT

网络地址转换。

所有离开本地网络去往Internet的数据报的源IP地址需替换为相同的NAT

动机:

1
2
3
4
只需从ISP申请一个IP地址,IPV4地址耗尽。
本地网络设备IP地址变更,无需告诉外界。
变更ISP,无需修改内部网络设备IP地址。
内部网络设备对外界网络不可见,即不可直接寻址。(安全)

互联网控制报文协议(ICMP)

支持路由器

1
2
差错报告
网络探寻

两类ICMP报文:

差错报告报文(5种)

1
2
3
4
5
目的不可达
源抑制
超时/超期
参数问题
重定向

网络探寻报文(2组)

1
2
回声请求与应答报文
时间戳请求与应答报文

image-20211204092543695

IPv6简介

最初动机:32位IPV4地址分配完

其他动机:改进首部格式

1
2
快速转发/处理数据报
支持QoS

IPV6数据报格式:

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

image-20211204093036564

其他改变:

1
2
检验和彻底移除,以减少每跳处理时间。
选项:允许,但是从基本首部移除

ICMPV6:

1
2
附加报文类型
多播组管理功能

image-20211204093735301

IPV6基本地址类型

1
2
3
4
单播:一对一通信
多播:一对多通信
任意播:一对一组之一通信
https://blog.csdn.net/weixin_40274679/article/details/106308577

隧道:IPV6数据报作为IPV4数据报的载荷进行封装,穿越IPV4网络。

路由算法

路由算法

image-20211204094231897

链路状态路由算法

image-20211204094325050

image-20211204094606037

image-20211204094739283

距离向量路由算法

image-20211204100125061

image-20211204100217247

会带来无穷计数问题

image-20211204100705477

毒性逆转

image-20211204100734803

定义最大度量

image-20211204100845755

层次化路由

管理自治:每个网络的管理可能都期望自主控制其网内的路由

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

同一AS内的路由器运行相同的路由算法

网关路由器:位于AS边缘;通过链路连接其他AS的网关路由器

转发表由AS内部路由算法与AS间路由算法共同配置。

image-20211204101931215

Internet路由

RIP协议

image-20211204102524132

image-20211204102601078

若180s没有收到通告,则邻居/链路失效

image-20211204102654450

OSPF协议

image-20211204103218720

优点(rip不具备)

image-20211204103322151

BGP协议

image-20211204103416370

image-20211204114223787

image-20211204114508159

image-20211204114632956

image-20211204115119242

附加

拥塞丢失时发送抑制源站报文。

RIP为UDP协议传输报文。

image-20211205192548473

image-20211205201933225

链路层和局域网

概述

节点:运行链路层协议的任何设备。包括主机,路由器,交换机和WiFi接入点。

链路层提供的服务

1
2
3
4
成帧
链路接入。MAC媒体访问控制 协议规定了帧在链路上传输的规则
可靠交付。链路层可靠交付目的是本地纠正一个差错,而不是通过运输层或应用层协议迫使进行端到端数据重传。
差错检测和纠正。

链路层在何处实现

链路层的主体部分是在 网络适配器中实现的,网络适配器有时也称 网络接口卡(NIC)。位于网络适配器核心的是链路层控制器。

差错检测和纠正技术(EDC)

奇偶校验

单个奇偶校验

1
发送信息有d比特,增加一个附加比特,使得d+1个比特中1的总数为偶数。

二维奇偶校验

img

接收方检测和纠正错误的能力被称为 前向纠错(FEC)

检验和方法

需要相对小的分组开销。

循环冗余检测

CRC,也称多项式编码。

考虑d比特的数据D。发送方和接收方首先必须协商一个r+1比特模式,称为 生成多项式,将其表示为G。G的最高有效位比特是1.对于一个给定的数据段D,发送方要选择r个附加比特R,并将它们附加到D上,使得得到的d+r比特模式用模二运算恰好能被G整除。接收方用G去除接收到的d+r比特,若余数为非零,则出现差错。

$D*2^rXOR\ R=nG$

即$D*2^r=nG\ XOR\ R$

$R=remainder\ \frac{D*2^r}{G}$

image-20211204135514798

多路访问链路和协议

多路访问控制MAC

MAC地址为链路层地址。

点对点链路:由链路一端的单个发送方和链路另一端的单个接收方组成。eg:点对点协议(PPP),高级数据链路控制(HDLC)。

广播链路:让多个发送和接收节点都连接到相同的单一的,共享的广播信道上。

信道划分协议

时分多路复用TDM;频分多路复用FDM

TMD的缺陷

1
2
节点被限制于R/Nbps的平均速率,即使他是唯一有分组要发送的节点。
节点必须总是等待他的轮次。

FDM将Rbps信道划分为不同的频段(每个频段具有R/N带宽)。同样也限制了带宽。

第三种信道划分协议是码分多址(CDMA)。

CDMA对每个节点分配一种不同的编码,然后每个节点用它唯一的编码来对它发送的数据进行编码。

随机接入协议

在随机接入协议中,一个传输节点总是以信道的全部速率进行发送。当有碰撞时,涉及碰撞的每个节点反复地重发它的帧,但是在重发之前会等待一个随机时延。

时隙ALOHA

image-20211204143122814

image-20211204143238161

ALOHA协议

非时隙ALOHA:更加简单,无需同步。

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

载波侦听多路访问CSMA

载波侦听:即一个节点在传输前先听信道,若来自另一个节点的帧正在向信道发送,节点则等待直到检测到一小段时间没有传输,然后开始传输。

P坚持CSMA:以概率P发送,一直侦听。

具有碰撞检测的载波侦听多路访问(CSMA/CD)

碰撞检测:当一个传输节点在传输时一直在侦听此信道。如果它检测到另一个节点在传输干扰帧,他就停止传输,在重复“侦听-当空闲时传输”循环之前等待一段随机时间。

CSMA/CD效率

定义为:当有大量的活跃节点,且每个节点有大量的帧要发送时,帧在信道中无碰撞地传输的那部分时间在长期运行时间中所占的份额。

image-20211204145626654

二进制指数后退算法

img

轮流协议

轮询协议:要求节点之一被指定为主节点。主节点以循环的方式轮询每个节点。

缺点:引入轮询时间;若主节点有故障,则整个信道不可操作。

令牌传递协议:没有主节点,一个被称为令牌的小的特殊帧在节点之间以某种固定的次序进行交换。

交换局域网

链路层寻址和ARP

MAC地址

并不是主机或路由器具有链路层地址,而是它们的适配器(即网络接口)具有链路层地址。

链路层地址也叫LAN地址,物理地址或MAC地址。

对大多数局域网而言,MAC地址长度为6字节。没有两块适配器具有相同的地址。

对于使用六字节地址的局域网(以太网和802.11)来说,广播地址为48个连续的1.

地址解析协议(ARP)

用于对网络层地址和链路层地址进行转换。

以太网

以太网:物理拓扑

1
2
总线:所有结点在同一冲突域
星型:目前主流网络拓扑。每一个结点一个单独冲突域。
1
2
3
无连接:发送帧的网卡与接收帧的网卡不握手
不可靠,差错帧直接丢弃
以太网MAC协议:采用二进制指数退避算法的CSMA/CD

以太网CSMA/CD算法

image-20211204155630443

img

数据字段:46-1500字节。MTU为1500字节,不包含头部

目的地址:6字节。目的适配器的MAC地址。

源地址:6字节。传输该帧到局域网上的适配器的MAC地址。

类型字段:2字节,允许以太网复用多种网络层协议。

CRC:4字节,循环冗余检测

前同步码:8字节

链路层交换机

交换机自身对子网中的主机和路由器是透明的。

交换机转发和过滤

过滤:决定一个帧应该转发到某个接口还是应当将其丢弃的交换机功能。

转发:决定一个帧应该被导向哪个接口,并把帧移动到那些接口的交换机功能。

这两个功能借助于 交换机表

表项包含

1
2
3
一个MAC地址;
通向该MAC地址的交换机接口;
表项放置在表中的时间

img

自学习

img

交换机是即插即用设备。

链路层交换机的性质

消除碰撞;异质的链路;管理。

交换机和路由器进行对比

image-20211204163023218

image-20211204163041260

虚拟局域网

VLAN

动态成员:端口可以动态分配给不同VLAN

在VLAN间转发:通过路由

多线缆连接

PPP

image-20211204165553120

image-20211204165606380

image-20211204165627410

image-20211204170545298

附加

MTU、IP MTU、TCP MSS设置上的区别及联系

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
1.MTU是一个二层的概念,即最大传输单元(Maximum Transmission Unit,MTU);以太网最大的mtu就是1500(它是不包含二层头部的,加上头部应该为1518 bytes,2bit的以太网类型+6bit的DMAC+6bit的SMAC+4bit的FCS),每个以太网帧都有最小的大小64bytes,最大不能超过1518bytes

注:

1)小于64Bytes的数据帧一般是由于以太网冲突产生的 “碎片”或者线路干扰或者坏的以太网接口产生的,对于大于1518Bytes的数据帧我们一般把它叫做Giant帧,这种一般是由于线路干扰或者坏的以太网口产生

2)以太网EthernetII最大的数据帧是1518Bytes,最小为64bytes,是指包含以太网帧的帧头(DMAC目的MAC地址 48bit=6Bytes+SMAC源MAC地址48bit=6Bytes+Type域2bytes)14Bytes和帧尾CRC校验部分4Bytes (这个部份有时候大家也把它叫做FCS)

2.IP MTU是一个三层概念,它包含了三层头部及所有载荷,根据下层为上层服务的,上层基于下层才能做进一步的扩展的原则,尽管IP MTU的变化范围很大(68-65535),但也不得不照顾以太网MTU的限制,说白了就是ip对以太网的妥协。

网络层IP协议会检查每个从上层协议下来的数据包的大小,并根据本机MTU的大小决定是否作“分片”处理

3.MSS是TCP里面的一个概念,它是TCP数据包每次能够传输的最大数据分段,不包含包头部分,它与IP MTU满足如下关系:

IP MTU=MSS+20bytes(IP包头)+20bytes(TCP包头)

当然,如果传输的时候还承载有其他协议,还要加些包头在前面。

注:为了达到最佳的传输效能,TCP协议在建立连接的时候通常要协商双方的MSS值,这个值TCP协议在实现的时候往往用MTU值代替(需要减去IP数据包报头的大小20Bytes和TCP数据段的包头20Bytes),所以往往MSS为1460。通讯双方会根据双方提供的MSS值得最小值确定为这次连接的最大MSS值。

4.简言之,mtu就是总的最后发出去的报文大小,MSS就是需要发出去的数据大小,比如PPPoE,就是在以太网上承载PPP协议(点到点连接协议),它包括6bytes的PPPoE头部和2bytes的PPP协议ID号,此时,由于以太网的MTU值为1500,所以上层PPP负载数据不能超过1492字节,也就是相当于在PPPOE环境下的MTU是1492字节,MSS是1452字节(1492字节-20-20)。



重点:

MTU 不包含 帧头(18byte) 指帧头后面的所有负载,与ip mtu的区别就是在帧头和ip头之间可能会有其他协议头(比如GRE头、pppoe头、MPLS标签,这些协议头都是在帧头后ip头前)

ip MTU 包含 ip头(20byte) 指ip头本身及后面的所有负载,一个普通的以太网数据包mtu=ip mut,只有封装了其他协议头部时mtu=ip mut+其他协议头部+负载(tcp头+tcp-mss)

TCP-MSS 不包含 tcp头(20byte) 指tcp头后面的所有负载

IP MTU=tcp-MSS+20bytes(IP包头)+20bytes(TCP包头)

image-20211204194239650

image-20211205195424849

image-20211205202022663

物理层

数据通信基础

image-20211204201851500

image-20211204202022742

image-20211204202733890

物理介质

image-20211204202951972

image-20211204203637959

image-20211204203616661

image-20211204203651460

image-20211204203704180

信道与信道容量

image-20211204203735096

image-20211204203744847

image-20211204203823712

基带传输基础

image-20211204203916364

频带传输基础

典型数字基带信号码型

image-20211205204044465

image-20211205204526302

image-20211205204553033

image-20211205204657865

image-20211205204718087

image-20211205204743795

image-20211205204811037

image-20211205204844547

image-20211205205637743

image-20211205205848891

  • 数据传输速率=波特率*log2(幅值相位组合)

image-20211205211421158

附加

CDMA

1
https://blog.csdn.net/qq_43262059/article/details/106201119

FTP

1
2
3
FTP协议运行在TCP连接上,保证了文件传输的可靠性。
FTP使用了两个并行的TCP来传输文件:一个是控制连接(port:21),一个是数据连接(port:20)。控制连接用于在两个主机之间传输控制信息,如口令,用户标识,存放、获取文件等命令。数据连接用于实际发送一个文件,发送完文件之后数据连接会关闭。因为FTP协议使用一个独立的控制连接,所以,也称FTP的控制信息是带外(out-of-band)传送的。
FTP支持两种方式的传输:文本(ASCII)方式和二进制(Binary)方式。

在划分VLAN的以太网交换机的Trunk端口间传输的帧是802.1帧。

利用链路控制协议,大多数的产品通过协商可以省略标志符和地址字段,并且把协议字段由 2个字节减少到 1个字节。

二进制数字调制系统中,频带利用率最低的是2FSK。

image-20211205231152187

image-20211205233856793

image-20211205234246885

Transact-SQL语言

DCL数据控制语言(进行安全性管理)

GRANT 授予权限

REVOKE 收回权限(不影响该用户从其他角色作为成员继承许可权限)

DENY 收回权限(禁止该用户从其他角色作为成员继承许可权限)

DDL数据定义语言(执行数据库任务)

CREATE 创建数据库或数据库对象

ALTER 修改——

DROP 删除——

DML数据操作语言(操作数据库中各对象)

select 从表或试图中检索数据

insert ——插入数据

update ——修改

delete ——删除

数据库

包含三个基本文件

(1)基本数据文件:有且只有一个 .mdf

(2)辅助数据文件:自由选择,0,1,2 .ndf

(3)日志文件:由于恢复数据库所需要的事务日志信息,至少一个。 .ldf

创建数据库

image-20211125152935936

img

附一个源码

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
create database DB2
on primary
(
name='f1',
filename='F:\sqlserve\sqlwj\f1.mdf',
size=3mb,
maxsize=unlimited,
filegrowth=3%
),
(
name='f2',
filename='F:\sqlserve\sqlwj\f2.ndf',
size=10mb,
maxsize=500mb,
filegrowth=6mb
)
log on
(
name='f3',
filename='F:\sqlserve\sqlwj\f3.ldf',
size=1mb,
maxsize=unlimited,
filegrowth=2%
)

修改数据库名字

1
2
3
--修改数据库的名字
alter database DB2
modify name=DB1

添加辅助文件

1
2
3
4
5
6
7
8
9
10
--在DB1中添加一个辅助文件日志文件
alter database DB1
add file
(
name='f2a',
filename='F:\sqlserver\sqlwj\f2a.ndf',
size=3mb,
maxsize=unlimited,
filegrowth=2mb
)

添加日志文件

add log file

删除数据库

drop database 数据库名

设计表

创建需要确定下列特征:

要包含的数据类型;

表中的列数,每一列中数据的类型和长度;

哪些列允许空值;

是否要使用以及何处使用约束;

哪些是主键,哪些为外键。

数据类型

Bigint 大整型 8字节

int 常用的整型 4字节

smallint 小整型 2字节

tinyint 微整型 1字节

Bit 位类型 其取值只有0/1

decimal[(p[,s])]和numeric[(p[,s])] p总位数,s小数位 p默认为18,s默认为0

Money存储的货币值由八个字节,前四个代表整数,后四代表小数

日期和时间

Datetime 长度8字节

1753.1.1-9999.12.31

Smalldatetime 四字节

1900.1.1-2079.12.31

字符串

Char(n) n单位为字节,表示输入字符串的最大值,若超过则不存,小于则添加空格

varchar(n) 变动长度

Unicode

Nchar

Nvarchar

二进制字符串

Binary:binary(n)存储图像等数据

varbinary(n)

创建表

切换数据库名字 use 数据库名字

1
2
3
4
5
6
7
8
--创建课程表(课程编号,课程名称,课程教师,上课时间)
create table 课程表
(
课程编号 varchar(15) not null,
课程名称 varchar(20) not null,
任课教师 char(10) not null,
上课时间 varchar(30)
)

修改表

添加列:

1
2
alter table 课程表
add 上课教室 varchar(20) not null

修改数据类型

1
2
alter table 课程表
alter column 任课教师 varchar(10) not null

删除列

1
2
alter table 课程表
drop column 任课教师

修改列名

1
exec sp_rename'表名.列名',‘新列名'

修改表名

1
exec sp_rename'原表名',‘新表名'

约束

主键约束PRIMARY KEY

唯一确定表中每一按条记录的表示符

外键约束FOREIGN KEY

用于建立和加强两个表数据之间的连接

唯一约束UNIQUE

指定一个列或多个列的值具有唯一性,可为空

检查约束CHECK

限制输入值

默认约束DEFAULT

插入操作中没有提供输入值时系统会自动添加指定值

创建约束
1
2
alter table 表名
add constraint 约束名 约束类型 具体的约束说明
1
2
3
-对表中的课程编号添加主键约束
alter table 课程表
add constraint PK_课程编号 primary key (课程编号)
1
2
3
--对课程名称添加一个唯一约束unique
alter table 课程表
add constraint UN_课程名称 unique(课程名称)
1
2
3
--给上课教室添加默认约束
alter table 课程表
add constraint DF_教室 default '正兴' for 上课教室
1
2
3
--给上课教室添加检查约束
alter table 课程表
add constraint CK_教室 check (上课教室='正兴' or 上课教室='诚意' or 上课教室='致知')

image-20211125213841519

外界约束前提,列中的数据类型必须保持一致。引用的列必须为主键约束或者唯一约束。两个表的列名尽量一致。

删除约束

alter table 表名

drop constraint 约束名

若被引用要先删除外界约束再删除主键约束

在定义时约束

image-20211126105437185

T-SQL语言

基本概念

标识符:数据库对象的名称

常规标识符与分隔标识符

常规标识符规则

第一个字符必须是英文大小写字母;_;@;#

后续字符除了第一字符,还有十进制数字,美元符号($)

批处理:一次处理多条语句

常量和变量

局部变量用DECLARE语句声明,作用范围仅在程序内部,局部变量的名称自己定义,以@开头。

声明语法

1
DECLARE @name datatype

对局部变量赋值

1
2
SET @NAME=expression
SELECT @name=expression[,..n]

SET只能对一个变量赋值

SELECT可以对多个赋值

PRINT输出

1
2
3
4
5
6
7
8
9
10
11
12
--声明两个变量
declare @name varchar(10),@age int

--赋值
set @name='张三'
set @age=18

--select
select @name='李四',@age=19

print @name
print @age

全局变量是事先定义好的,不允许创建修改,以@@开头

运算符

算数运算符

赋值运算符=

位运算符:两个整数类型表达式

比较运算符:除text,ntext.image数据类型外都可以用

逻辑运算符:

AND如果两个表达式都为true,则结果为true

BETWEEN如果操作数在某个范围,则结果为true

IN

LIKE

NOT

OR

一元运算符

流控制语句

BEGIN…END用于将多个语句组合为一个逻辑块

IF…ELSE

WHILE

BREAK

CONTINUE

CASE

1
2
3
4
case 
when ...then...
when ...then...
else

WAITFOR延迟语句可以将它之后的语句在一个指定的时间间隔后执行

1
Waitfor delay 'time'|time'time'
1
2
3
4
5
waitfor delay '00:00:03'
print '傻瓜你好'

waitfor time '17:34:59'
print '傻瓜你好'

GOTO

return无条件退出语句

数据库操作实例

查询数据

SELECT

1
2
3
--查询教师
select 任课教师,上课时间 --列名
from 课程表 --表名

select *为查询所有列

DISTINCT

删除重复行

1
2
3
--去重复
select distinct 任课教师
from 课程表

distinct后只能跟一个列

TOP

用于规定要返回的查询结果的数目

1
2
3
4
5
6
7
--返回前3行所有数据
select top 3 *
from 课程表

--返回前三行的任课教师和时间
select top 3 任课教师,上课时间
from 课程表

去掉重复数据后,后面的数据往前补

1
2
select distinct top 3 任课教师
from 课程表
别名
1
2
3
--别名查询,方式一
select 任课教师 '教师', 上课时间 '时间'
from 课程表
1
2
3
方式二
select '别名'=列名
from 表名
1
2
3
方式三
select 列名 as '别名'
from 表名
计算列
1
2
seclect '原始学号'=学号,'调整学号'=学号-10
from 表名

选择查询

基本语法

1
2
3
SELECT LIST
FROM TABLE
WHERE CONDITIONS
比较搜索条件
1
2
3
4
5
<>不等于

!=不等于
!>不大于
!<不小于
1
2
3
4
5
--查询任课教师为孙大烈的课程名称
select 课程名称
from 课程表
where 任课教师='孙大烈' 后可接逻辑运算符

范围搜索条件

包括范围

排他范围

1
2
3
4
select 课程编号
from 课程表
where 课程编号 (not) between 3 and 5

列表搜索条件

IN关键字使用户可以与列表中的任意值匹配。

1
2
3
select 课程编号
from 课程表
where 课程编号 in ('3','4')
搜索条件中的字符匹配符

LIKE搜索匹配指定模式字符串

通配符

1
2
3
4
% 替代0/多个字符
_ 替代一个字符
[] 代表指定范围内的单个字符,[]中可以是单个字符([acef]),也可以为范围([a-f])
[^] 代表不在范围内的单个字符[^]中可以是单个字符([^acef]),也可以为范围([^a-f])
1
2
3
4
查询出姓王的老师
select 任课教师
from 课程表
where 任课教师 like '王%'
涉及空置的查询

NULL在数据库中表示不确定的值

判断为空

1
列名 is (not) null

聚合函数

对一组值执行计算,并返回单个值。

1
2
3
4
5
6
7
SUM([distinct]<列名>)
AVG([distinct]<列名>)
MAX([distinct]<列名>)
MIN([distinct]<列名>)
COUNT (*)统计元组个数
COUNT ([distinct]<列名>)统计本列列值个数
除count外,其他函数均计算NULL
1
select 聚合函数 from 表名
1
2
select sum (grade) as '总成绩'
from stu

数据分组

group by根据一个或多个列对结果进行分组

1
2
3
4
select 年级,SUM(人数) as '总人数',
COUNIT(班级编号) as '班级总量'
from 班级信息
group by 年纪

having通常与group by子句一起使用。

后跟查询条件

having子句可以包含聚合函数,where不可以

1
2
3
4
select 学号,SUM(成绩) as '总成绩'
from 成绩表
group by 学号
having SUM(成绩)<100

order by

用于对指定结果进行排序,默认升序

降序排序可以用DESC关键字

1
2
3
4
查看成绩表
select *
from 成绩表
order by 成绩
1
2
3
select *
from 成绩表
order by 成绩 desc

image-20211130204224089

表连接

从多个相关表中查询数据

内部连接
1
2
3
4
5
select list from 表名1,表名2
where 表1.列=表2.列

select list from 表1 [inner] join 表2
on 表1.列=表2.列

查询学生的学号,姓名,性别,以及所在的班级名称和年级

1
2
3
select 学生信息.姓名,学生信息.学号,学生信息.性别,班级信息.班级名称,班级信息.年级
from 学生信息,班级信息
where 学生信息.班级编号=班级信息.班级编号
1
2
3
4
select 学生信息.姓名,学号,性别,//偷懒写法
班级信息.班级名称,年级
from 学生信息.inner join 班级信息
on 学生信息.班级编号=班级信息.班级编号

内部连接只有共同匹配到的结果才会有输出

外部连接

外部连接会返回from子句中提到的至少一个表的所有行。

分为左外部连接、右外部链接和全外部连接

左外部连接对连接条件中左边的表不加限制,其余同理。

先写为左表,后写为右表。

left outer join,若左表的某行在右表没有找到匹配的行,则结果集中的右表的相对应的位置为null

right outer join

full outer join

子查询

用来表示where子句的条件

子查询用圆括号括起来

嵌套子查询与相关子查询

嵌套子查询

一个子查询可以包含另一个查询

1
2
3
4
5
6
7
--查询计算机系学生选修了哪些课程
select *
from sc
where sno in
(select sno
from student
where sdept='计算机系')

where子句后条件要什么,子查询就查什么

1
2
3
4
5
6
7
8
select sno,grade
from sc
where cno='c02'
and grade >
(select AVG(grade)
from sc
where cno='c02'
)
相关子查询(单值子查询)

这样的子查询只返回一个值,然后将一列值与查询返回的值进行比较

在查询基础上创建新表

使用select …into语句可以在查询的基础上创建新表。

语法为

1
2
3
select list
into新表名
from表名

添加数据

使用Insert和values插入
1
2
insert[into] 表名[列名]
values(...)
使用insert和select插入行

使用select子句将一个表或多个表的值添加到另一个表中。

修改数据

update修改表中数据语法形式

1
2
update 表名 set 列名=表达式
where//加条件
1
2
3
4
update 成绩表
set 学号='3'
where 成绩='95'
and 课程编号 between '1002' and '1003'

如果条件不统一,更改的值也不一样,则分开来写。

1
2
3
update 成绩表
set 成绩='89'
where 课程编号='1001'

删除数据

1
2
delete from 表名
where 选择条件

(删除行)

1
2
3
删除固定行
delete top (20) percent from 表名//删除前20%
delete top (20) percent from 表名//删除前20行

视图

视图是基于某个查询结果的虚表。

标准视图、索引视图、分区视图。

视图的优点

着重于特定数据

简化数据操作

自定义数据

导出和导入数据

跨服务器组合分区数据

创建视图

1
2
3
create view [数据库名 ] 视图名
AS
select_statement
1
2
3
create view View_班级信息
as
select *from 班级信息

修改视图名字

sp_rename修改视图名字

1
exec sp_rename 'view_班级信息','view_班级信息2'

对于表的操作,视图同样可以使用。

管理视图

1
2
inbseret into view_学生信息
values('7','13','aa','nv','beijing')

视图信息更改,原表信息也会更改。

alter既能修改数据内容,修改数据结构。

删除视图

1
drop view 视图名1,视图名2

有条件删除

1
2
delete from 视图名
where 条件

索引

对数据库表中一个或多个列的值进行排序的结构。用来定位。

作用

加快数据检索;保持数据一致性;实现表与表之间参照完整性。

选择创建索引的数据列

定义有主键和外键的列;在指定范围中快速或频繁查询的列;连接中频繁使用的列;需要按排序顺序快速或频繁检索的列

类型

聚集索引:

索引的顺序决定了表中行的存储顺序,因此每个表中只能有一个聚集索引。

非聚集索引:

索引中的逻辑顺序并不等同与表中行的物理顺序。

事务

事务是作为单个逻辑单元执行的一系列操作。不可分割。

四大特性:

原子性;一致性;隔离性;永久性。

1
2
3
begin transaction
rollback transaction//恢复
commit transaction//提交

存储

系统存储过程

image-20211208074620892

exec执行

用户自定义存储过程

参数有输入和输出参数

1
2
3
4
5
create proc[edure] 存储过程名
@参数一 数据类型=默认值 output
AS
SQL语句
GO

参数可以设置默认值

image-20211208081112318

image-20211208102301639

数据库设计基础

E-R图

image-20211208081720924

MySQL

数据库基础

数据库系统概述

DB :database数据库

DBMS :Database Management System数据库管理系统

SQL :Structure Query Language专门用来与数据库通信的语言

数据模型

数据模型由数据结构,数据操作和完整性约束构成。

常见的数据模型

层次模型:用树形结构表示实体类型及实体间的联系的数据模型称为层次模型。

img

网状模型:用有向图结构表示实体类型以及实体间联系的数据模型称为网状模型。用网状模型编写应用程序及其复杂,数据的独立性较差。

img

关系模型:以二维表来描述数据。

img

img

关系数据库的规范化

根据满足规范的条件不同,可以分为五个等级:第一范式(1NF)、…,第五范式(5NF)。一般情况下,只要把数据规范到第三范式标准就可以。

第一范式

在第一范式中,数据表的每一行只包含一个实体的信息,并且每一行的每一列只能存放实体的一个属性。

img

第二范式

第二范式应该首先满足第一范式,第二范式要求数据库表中的每个实体必须可以被唯一的区分。为了实现区分各行记录,通常需要为表设置一个区分列,用以存储各个实体的唯一标识。

第三范式

第三范式要求一个关系表中不包含已在其他表中已包含的非关键字信息。

关系数据库的设计原则

○数据库内数据文件的数据组织应该获得最大限度的共享、最小的冗余度,消除数据及数据依赖关系中的冗余部分,是依赖于同一个数据模型的数据达到有效的分离。

○保证输入、修改数据时数据的一致性与正确性。

○保证数据与使用数据的应用程序之间的高度独立性。

实体与关系

一对一关系

一对多关系

多对多关系

数据库的体系结构

数据库三级模式结构

模式

也称逻辑模式或概念模式,是数据库中全体数据的逻辑结构和特征的描述,是所有用户的公共数据拼图。一个数据库只有一个模式,模式处于三级结构中的中间层。

外模式

也称用户模式,是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述,是数据库用户的数据视图,是与某一应用有关的数据的逻辑表示。外模式是模式的子集,一个数据库可以有多个外模式。

外模式是保证数据安全性的一个有力措施。

内模式

也称存储模式,一个数据库只有一个内模式。他是数据结构和存储方式的描述,是数据在数据库内部的表示方式。

三级模式之间的映射

数据库管理系统在三级模式之间提供了两层映射,分别为

外模式/模式映射

对于同一个模式可以由多个外模式。对于每一个外模式,数据库系统都有一个外模式/模式映射。当模式改变时,由数据库管理员作出改变,保证数据与程序的逻辑独立性。

模式/内模式映射

唯一,定义了数据库的全局逻辑结构与存储之间的对应关系。当数据库的存储结构改变时,有数据库管理员对其作出改变。保证数据与程序的物理独立性。

计算机系统概论

img

计算机的基本组成

冯诺依曼计算机的特点

(1)计算机由运算器,存储器,控制器,输入设备,输出设备五大部件组成。

(2)指令和数据以同等地位存放于存储器内,可按地址访问。

(3)指令和数据均用二进制数表示。

(4)指令由操作码和地址码组成,操作码用来表示操作的性质,地址码用来表示操作数在存储器中的位置。

(5)指令在存储器内顺序存放。

(6)机器以运算器为中心,输入输出设备与存储器间的数据传送通过运算器完成。

计算机的硬件框图

img

通常把运算器与控制器统称为中央处理器,即CPU。把输入/输出设备成为I/O设备,也可称为外部设备。

CPU与主存储器合起来称为主存。

img

控制元(CU)用来解释存储器中的指令,并发出各种操作命令来执行指令。

计算机硬件的主要技术指标

机器字长;

存储容量:MAR位数反映的存储单元的个数,MDR的位数反映了存储字长;

运算速度:MIPS(百万条指令每秒),CPI(执行一条指令所需的时钟周期);

附加

指令字长=存储字长=机器字长(三者可以相等也可以不等)

1
2
3
4
机器字长:CPU一次能处理的二进制数据的最大位数。通常与CPU内寄存器的位数有关。栗子:windows 64位/32位,这里的64位和32位指的就是该操作系统的机器字长。
存储字长指一个存储单元可存放的二进制代码的位数,即存储器中的MDR的位数。
指令字长是计算机指令字的位数,指令字是指用二进制表示的指令,
数据字长指的是计算机数据字的位数,数据字是指用二进制表示的数据

用以指定待执行指令所在地址的是程序计数器

磁盘驱动器具有输入及输出功能

完整的计算机系统应该包括配套的硬件设备和软件系统

计算机与日常使用的袖珍计算器的本质区别在于自动化程度的高低。

有些计算机将一部分软件永恒地存于只读存储器中,称为固件

计算机系统软件包括:

1
2
3
4
5
6
标准程序库,如监控程序,用于监视计算机工作
服务型程序,如连接、编辑、调试、诊断
语言处理程序,如编译程序、汇编程序、解释程序,将各种语言转换成机器语言
操作系统,用来控制和管理计算机
数据库管理系统
各种计算机网络软件

存储元件(又称存储基元、存储元)用来存放一位二进制信息。存储单元由若干个存储元件组成,能存放多位二进制信息。每个存储单元中二进制代码的组合即为存储字,它可代表数值、指令、地址或逻辑。每个存储单元中二进制代码的位数就是存储字长。

计算机系统量化分析基础

计算机体系结构的概念

计算机体系结构概念的演变

阿姆道尔首次明确计算机体系结构是程序员所看到的计算机的属性,即概念性结构与功能特性。

对于通用寄存器型机器,这些属性主要是指:

1
2
3
4
5
6
7
8
9
10
(1)数据表示:硬件能直接辨认和处理的数据类型
(2)寻址规则:最小寻址单元、寻址方式及其表示
(3)寄存器定义:寄存器的定义、数量和使用方式
(4)指令系统:机器指令的操作类型和格式、指令间的排序和控制机构等
(5)中断系统:中断的类型和中断响应硬件的功能等
(6)机器工作状态的定义和切换:如管态和目态等
(7)存储系统:程序员可用的最大存储容量
(8)信息保护:信息保护方式和硬件的支持
(9)I/O结构:I/O寻址方式、数据传送的方式等

计算机体系结构、组成和实现

体系结构包括以下三个方面

1
2
3
(1)计算机指令系统
(2)计算机组成
(3)计算机硬件实现

系列机

1
一种指令集结构可以有多种组成。同样,一种组成可以有多种物理实现。系列机就是指在一个厂家生产的具有相同的指令集结构,但具有不同组成和实现的一系列不同型号的机器。

兼容性

1
2
向上(下)兼容指的是按某档机器编制的程序,不加修改的就能运行于比它高(低)档的机器
向前(后)兼容指的是按某个时期投入市场的某种型号机器编制的程序,不加修改地就能运行于在它之前(后)投入市场的机器

image-20211214131042867

计算机体系结构的发展

并行性

1
计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。

从执行程序的角度来看,并行性等级从低到高可分为

1
2
3
4
5
6
7
指令内部并行:单条指令中各微操作之间的并行。
指令级并行:并行执行两条或两条以上的指令。
线程级并行:并行执行两个或两个以上的线程。
通常是以一个进程内派生的多个线程为调度单位。
任务级或过程级并行:并行执行两个或两个以上的过程或任务(程序段), 以子程序或进程为调度单元。
作业或程序级并行:并行执行两个或两个以上的作业或程序。

从处理数据的角度来看,并行等级从低到高可分为:

1
2
3
4
5
6
7
8
9
10
11
字串位串:每次只对一个字的一位进行处理。
最基本的串行处理方式,不存在并行性。
字串位并:同时对一个字的全部位进行处理,不
同字之间是串行的。
开始出现并行性。
字并位串:同时对许多字的同一位(称为位片)
进行处理。
具有较高的并行性。
全并行:同时对许多字的全部位或部分位进行处理。
最高一级的并行。

按照指令和数据的关系,把计算机系统的结构分为4类。Flynn分类法

1
2
3
4
5
6
7
8
单指令流单数据流SISD
(Single Instruction stream Single Data stream)
单指令流多数据流SIMD
(Single Instruction stream Multiple Data stream)
多指令流单数据流MISD
(Multiple Instruction stream Single Data stream)
多指令流多数据流MIMD
(Multiple Instruction stream Multiple Data stream)

提高并行性的技术途径

1
2
3
4
5
6
(1)时间重叠
引入时间因素,让多个处理过程在时间上相互错开,轮流重叠地使用同一套硬件设备的各个部分,以加快硬件周转而赢得速度。
(2)资源重复
引入空间因素,以数量取胜。通过重复设置硬件资源,大幅度地提高计算机系统的性能。
(3)资源共享
这是一种软件方法,它使多个任务按一定时间顺序轮流使用 同一套硬件设备。

耦合度 反映多机系统中各机器之间物理连接的紧密程度和交互作用能力的强弱。

量化设计的基本原则:

1
2
3
4
5
6
7
8
9
10
11
1.大概率事件优先原则
追求全局的最优结果

2.Amdahl定律
系统性能加速比,受限于该部件在系统中所占的重要性
可以定量计算

3.程序的局部性原理
程序执行时所访问存储器在时-空上是相对地簇聚
这种簇聚包括指令和数据两部分

具有高性能价格比的计算机系统是一个带宽平衡的系统,而不是看它使用的某些部件的性能

CPU性能公式

1
2
3
4
5
6
7
8
9
10
11
12
执行一个程序所需的CPU时间
CPU时间 = 执行程序所需的时钟周期数×时钟周期时间
其中:时钟周期时间是系统时钟频率的倒数。
每条指令执行的平均时钟周期数CPI
CPI = 执行程序所需的时钟周期数/IC
IC:所执行的指令条数
程序执行的CPU时间可以写成
CPU时间 = IC ×CPI ×时钟周期时间
时钟周期时间:取决于硬件实现技术和计算机组成
CPI:取决于计算机组成和指令系统的结构;
IC:取决于指令系统的结构和编译技术

image-20211214135037288

总线

总线的基本概念

总线是连接多个部件的信息传输线,是各部件共享的传输介质。在某一时刻,只允许有一个部件向总线发送信息,而多个部件可以同时从总线上接受相同的信息。

image-20211214142344175

M总线:存储总线

I/O总线:输入输出总线

image-20211214142357607

image-20211214142444806

总线的分类

片内总线

芯片内部 的总线

系统总线

计算机各部件之间 的信息传输线

数据总线
1
2
用来传输各功能部件之间的数据信息
双向 与机器字长、存储字长有关
地址总线
1
2
用来指出数据总线上的源数据或目的数据在主存单元的地址或I/O设备的地址。
单向 与存储地址、 I/O地址有关
控制总线
1
2
发出各种控制信号的传输线。
中断请求,总线请求,存储器读,存储器写,总线允许,中断确认等

通信总线

用于 计算机系统之间 或 计算机系统与其他系统(如控制仪表、移动通信等)之间的通信

有串行通信和并行通信两种。

总线特性及性能指标

总线特性

image-20211214143223473

总线的性能指标

image-20211214143356321

总线结构

单总线结构

image-20211214143726811

双总线结构

image-20211214143750521

三总线结构

image-20211214143816307

主存总线用于CPU与主存之间的传输;I/O总线供CPU与各类I/O设备之间传递信息;DMA总线用于高速I/O设备(磁盘,磁带等)与主存之间直接交换信息。

另一种三总线结构

image-20211214144022838

Cache可通过系统总线与主存传递信息;且I/O设备与主存之间的传输也不必通过CPU,还有一条扩展总线。

SCSI:小型计算机接口;MODEM:调制解调器

四总线结构

image-20211214144314504

高速总线上挂了一些告诉的I/O设备。

总线控制

总线判优控制

总线上所连接的各类设备,按其对总线有无控制功能可分为主设备(模块)和从设备(模块)两种。

image-20211214144718951

集中式判优控制将控制逻辑集中在一处,如CPU;后者将控制逻辑分散在与总线连接的各个部件或设备上。

image-20211214145237060

1
特点:只需要很少几根线就能按一定优先次序实现总线控制,并且很容易扩展设备,但对电路故障很敏感,且优先级别低的设备很难获得请求

image-20211214145747620

1
对电路故障不如链式查询方法敏感,但增加了控制线(设备地址)数,控制也较复杂。

image-20211214145903975

1
响应速度快,优先次序控制灵活,但控制线数量多,总线控制更复杂。

总线通信控制

目的:解决通信双方 协调配合 问题

总线传输周期(一次总线操作的时间)

1
2
3
4
申请分配阶段 主模块申请,总线仲裁决定
寻址阶段 模块向从模块 给出地址 和 命令
传数阶段 主模块和从模块 交换数据
结束阶段 主模块 撤消有关信息

总线通信的四种方式

1
2
3
4
同步通信 由统一时标 控制数据传送
异步通信 采用 应答方式 ,没有公共时钟标准
半同步通信 同步,异步结合
分离式通信 充分挖掘系统总线每个瞬间的潜力

同步式

image-20211214150834077

image-20211214150845552

异步

应答方式又分为三种

1
2
3
4
5
不互锁方式:
主模块发出请求后,不必等待接到从模块的回答信号,而是经过一段时间,确认从模块已收到请求信号后,便撤销其请求信号;从模块接到请求信号后,在条件允许时发出回答信号,并且经过一段时间(这段时间对不同设备不同)确认主模块已收到回答信号后,自动撤销回答信号。eg:CPU向主存写信息
半互锁方式:
主模块发出请求后,不许接到从模块的回答后再撤销;而从模块则不必,一方互锁,一方不互锁
全互锁方式:双方互锁

异步串行通信的数据传送速率用波特率来衡量。波特率是指单位时间内传送二进制数据的位数,单位用bps(位/s),记作波特。

同步传送速度高于异步传送。

半同步

1
2
同步   发送方 用系统 时钟前沿 发信号,接收方 用系统 时钟后沿 判断、识别
异步 允许不同速度的模块和谐工作,增加一条 “等待”响应信号

image-20211214152257639

适用于系统工作速度不高但又包含了由许多工作速度差异较大的各类设备组成的简单系统。半同步通信比异步通信简单,可靠性高。缺点是对系统时钟频率不能要求太高,故从整体看,系统工作速度还不是很高。

image-20211214152647243

分离式通信

1
2
3
一个总线传输周期
子周期1 主模块 申请 占用总线,使用完后即 放弃总线 的使用权
子周期2 从模块 申请 占用总线,将各种信息送至总线上

特点

1
2
3
4
5
1. 各模块有权申请占用总线
2. 采用同步方式通信,不等对方回答
3. 各模块准备数据时,不占用总线
4. 总线被占用时,无空闲
充分提高了总线的有效占用

附加

影响总线带宽的因素:总线宽度,传输距离,总线发送和接受电路工作频率的限制以及数据传输形式。

PCI总线是一个与处理器时钟频率无关的告诉外部总线。

AGP总线是显卡专用的局部总线。

计算机之间的远距离通信除了直接由网卡经网线传输外,还可用RS-232总线通过载波电话线传输。

总线管理主要包括判优控制和通信控制。

在高档PC机中,系统总线主要连接CPU和存储器;PCI总线主要连接多媒体卡,高速局域网适配器,高性能图形版等高速部件;ISA或EISA总线连接图文传真机、调制解调器,打印机等低速部件。系统总线和PCI通过PCI桥路相连,PCI总线又通过标准总线控制器与IS和EIS总线相连。

指令系统

机器指令

每一趟机器语言的语句称为机器指令,又将全部机器指令的集合称为机器的指令系统。

指令由地址码和操作码构成。操作码可固定可不固定。

1
扩展操作码技术:操作码的位数随地址数的减少而增加

四地址指令:image-20211215114537872

需进行四次访存,取指令一次,取两个操作数两次,存放结果一次

三地址指令:image-20211215114740842

下条指令地址隐藏在程序计数器PC中,同样也需要进行四次访存。

二地址指令:image-20211215114937575

一地址指令:image-20211215115213639

零地址指令:无地址码

早起计算机指令字长、机器字长和存储字长均相等。

操作数类型和操作类型

操作类型

1
2
3
4
5
6
数据传送;
算术逻辑操作;
移位;
转移;
输入输出;
其他:等待,停机,空等指令

寻址方式

分为数据寻址与指令寻址

指令寻址

分为顺序寻址和跳跃寻址。

数据寻址

指令地址码字段称为形式地址,记为A;而操作数的真实地址称为有效地址,记为EA。

立即寻址

1
2
3
形式地址A就是操作数
指令执行阶段不访存
A 的位数限制了立即数的范围

直接寻址

1
2
3
4
A=EA
执行阶段访问一次存储器
A 的位数决定了该指令操作数的寻址范围
操作数的地址不易修改(必须修改A)

隐含寻址

1
操作数地址隐含在操作码中

间接寻址

1
2
3
有效地址由形式地址间接提供
会多次访存
可扩大寻址范围,便于编制程序

寄存器寻址

1
2
3
4
EA=R_i
有效地址即为寄存器编号
执行阶段不访存,只访问寄存器,执行速度快
寄存器个数有限,可缩短指令字长

寄存器间接寻址

1
2
EA=(R_i)有效地址在寄存器中
操作数在存储器中,执行阶段访存

基址寻址

1
2
3
4
(1)采用专用寄存器作基址寄存器
EA = ( BR ) + A
BR 为基址寄存器
可扩大寻址范围,有利于多道程序,BR内容由操作系统或管理程序确定,在程序的执行过程中BR内容不变,形式地址A可变
1
2
3
4
(2) 采用通用寄存器作基址寄存器 R0 作基址寄存器
由用户指定哪个通用寄存器作为基址寄存器
基址寄存器的内容由操作系统确定
在程序的执行过程中 R0 内容不变,形式地址 A 可变

变址寻址

1
2
3
EA = ( IX ) +A IX 为变址寄存器(专用)
通用寄存器也可以作为变址寄存器
可扩大寻址范围,IX的内容由用户给定,在程序的执行过程中IX可变,形式地址A不变,便于处理数组问题

相对寻址

1
2
3
EA = ( PC ) + A
A 是相对于当前指令的位移量
A的位数决定操作数的寻址范围,程序浮动,广泛用于转移指令

堆栈寻址

多个寄存器可构成硬堆栈,指定的存储空间构成软堆栈。

image-20211215125935774

指令系统结构的分类

CPU中用来存储操作数的存储单元主要有

1
堆栈,累加器,一组寄存器

image-20211215131719796

寄存器-寄存器型

1
2
优点:指令字长固定,指令结构简洁,是一种简单的代码生成模型,各种指令的执行时钟周期数相近。
缺点:与指令中含存储器操作数的指令系统结构相比,指令条数多,目标代码不够紧凑,因而程序占用的空间比较大。

寄存器-存储器型

1
2
优点:可以在ALU指令中直接对存储器操作数进行引用,而不必先用load指令进行加载,容易对指令进行编码,目标代码比较紧凑。
缺点:由于有一个操作数的内容将被破坏,所以指令中的两个操作数不对称。在一条指令中同时对寄存器操作数和存储器操作数进行编码,有可能限制指令所能够表示的寄存器个数。指令的执行时钟周期因操作数的来源(寄存器或存储器)的不同而差别比较大。

存储器-存储器型

1
2
优点:目标代码最紧凑,不需要设置存储器来保存变量。
缺点:指令字长变换很大,特别是3个操作数指令。而且每条指令完成的工作也差别很大。对存储器的频率访问会使存储器成为瓶颈。这种类型的指令系统现在已经不用了。

指令系统的设计和优化

基本原则

包括指令的功能设计和指令格式的设计

在确定哪些基本功能用硬件来实现时,主要考虑3个因素:速度,成本,灵活性

1
2
硬件实现:速度快,成本高。灵活性差
软件实现:速度慢,价格便宜,灵活性好

对指令系统的基本要求

1
2
3
4
5
6
完整性,规整性,正交性,高效率,兼容性
完整性:在一个有限可用的存储空间内,对于任何可解的问题,编制计算程序时,指令系统所提供的指令足够使用。
规整性:主要包括对称性和均匀性。
正交性:在指令中各个不同含义的字段,如操作类型、数据类型、寻址方式字段等,在编码时应互不相关、相互独立。
高效率:指指令的执行速度快、使用频度高。
兼容性:主要是要实现向后兼容,指令系统可以增加新指令,但不能删除指令或更改指令的功能。

控制指令

image-20211215133256789

1
2
“调用者保存”(caller saving)方法:如果采用调用者保存策略,那么在一个调用者调用别的过程时,必须保存调用者所要保存的寄存器,以备调用结束返回后,能够再次访问调用者。
“被调用者保存”(callee saving)方法:如果采用被调用者保存策略,那么被调用的过程必须保存它要用的寄存器,保证不会破坏过程调用者的程序执行环境,并在过程调用结束返回时,恢复这些寄存器的内容。

指令操作码的优化

等长扩展码

1
便于分级译码

定长操作码

1
2
3
固定长度的操作码:所有指令的操作码都是同一的长度。
保证操作码的译码速度、减少译码的复杂度。
以程序的存储空间为代价来换取硬件实现上的好处。

指令系统的发展和改进

一个方向是强化指令功能,实现软件功能向硬件功能转移,基于这种指令集结构而设计实现的计算机系统称为复杂指令集计算机(CISC)。
八十年代发展起来的精简指令集计算机(RISC),其目的是尽可能地降低指令集结构的复杂性,以达到简化实现,提高性能的目的。

面向目标程序增强指令功能
提高运算型指令功能;
提高传送指令功能;
增加程序控制指令功能。
面向高级语言和编译程序改进指令系统
增加对高级语言和编译系统支持的指令功能;
高级语言计算机指令系统。

附加

img

零操作数来自栈顶和次栈顶。

img

寄存器间址有利于编制循坏程序。

在非立即寻址的一地址格式指令中,其中一个操作数通过指令的地址字段安排在寄存器或存储器中。

一个较完善的指令系统应该包括数据传送,算术逻辑运算,程序控制,输入输出,其他。

变址寻址只要用于处理数组程序;基址寻址支持多道程序的应用。

RR型指令,执行指令时不访问存储器。

RS型指令,执行指令时需访问存储器,且通过变址运算,时间最长。

CPU设计与实现

CPU的结构

CPU的寄存器

用户可见寄存器

1
2
3
4
5
6
7
(1) 通用寄存器
存放操作数 可作 某种寻址方式所需的 专用寄存器
(2) 数据寄存器
存放操作数(满足各种数据类型) 两个寄存器拼接存放双倍字长数据
(3) 地址寄存器
存放地址,其位数应满足最大的地址范围 用于特殊的寻址方式 段基值 栈指针
(4) 条件码寄存器 存放条件码,可作程序分支的依据 如 正、负、零、溢出、进位等

控制寄存器

1
2
其中 MAR、MDR、IR            用户不可见
PC 用户可见

状态寄存器

1
PSW寄存器 存放程序状态字

运算方法与ALU

算数移位运算

image-20211216135626230

有符号数移位称为算数移位,无符号数移位称为逻辑移位。

单符号位判断溢出与双符号位判断溢出。

image-20211216142115187

image-20211216142130087

浮点四则运算

浮点加减法

1
2
3
对阶:求阶差,小阶向大阶对其
尾数求和

image-20211216143446776

image-20211216143528988

image-20211216143806564

image-20211216144000786

多级时序系统

指令周期

取出并执行一条指令所需的全部时间

image-20211216144414073

微指令分析

1
2
3
4
取指阶段:
PC->MAR 1->R (MAR)->MDR MDR->IR OP(IR)->CU (PC)+1->PC
间址周期:

image-20211216145209138

image-20211216145229814

image-20211216145259482

image-20211216145315443

在机器周期所含时钟周期数 相同 的前提下,
两机 平均指令执行速度之比 等于 两机主频之比

一个指令周期包含若干个机器周期

一个机器周期包含若干个时钟周期

附加

流水线

概述

流水线特点

1
2
3
4
5
流水过程由多个相关的子过程组成,这些子过程称为流水线的“级”或“段”。段的数目称为流水线的“深度”。
每个子过程由专用的功能段实现。
各功能段的时间应基本相等,通常为1个时钟周期(1拍)。
流水线需要经过一定的通过时间才能稳定。
流水技术适合于大量重复的时序过程。

分类

1
2
3
4
5
6
7
单功能流水线和多功能流水线
按流水线所完成的功能分类
单功能流水线,是指只能完成一种固定功能的流水线。
例如:功能单元流水线
多功能流水线,是指各段可以进行不同的连接,从而完成不同的功能。
例如:TI ASC多功能流水线

1
2
3
4
5
6
7
静态流水线和动态流水线
按同一时间内流水段的连接方式划分
静态流水线,是指在同一时间内,流水线的各段只能按同一种功能的连接方式工作。
例如:TI ASC的流水线
适合于处理一串相同的运算操作
动态流水线,是指在同一时间内,当某些段正在实现某种运算时,另一些段却在实现另一种运算,会使流水线的控制变得很复杂

1
2
3
4
5
6
部件级、处理机级及处理机间流水线 
按流水的级别划分
部件级流水线,又叫运算操作流水线,是把处理机的算术逻辑部件分段,使得各种数据类型的操作能够进行流水。
处理机级流水线,又叫指令流水线,是把解释指令的过程按照流水方式处理。
处理机间流水线,又叫宏流水线,是由两个以上的处理机串行地对同一数据流进行处理,每个处理机完成一项任务。

1
2
3
4
5
6
7
标量流水处理机和向量流水处理机
按照数据表示来进行分类
标量流水处理机,是指处理机不具有向量数据表示,仅对标量数据进行流水处理。
例如:IBM 360/91,Amdahl 470V/6等
向量流水处理机,是指处理机具有向量数据表示,并通过向量指令对向量的各元素进行处理。
例如:TI ASC、STAR-100、CYBER-205、CRAY-1、YH-1等

1
2
3
4
5
6
7
线性流水线和非线性流水线
按照是否有反馈回路来进行分类
线性流水线是指流水线的各段串行连接,没有反馈回路。
非线性流水线是指流水线中除有串行连接的通路外,还有反馈回路。
存在流水线调度问题。
确定什么时候向流水线引进新的输入,从而使新输入的数据和先前操作的反馈数据在流水线中不产生冲突,此即所谓流水线调度问题。

基本流水线

image-20211219111100347

image-20211219111939127

image-20211219111951893

性能分析

吞吐率

1
2
3
4
吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。
最大吞吐率TPmax是指流水线在达到稳定状态后所得到的吞吐率。
设流水线由m段组成,完成n个任务的吞吐率称为实际吞吐率,记作TP。

1
2
3
4
最大吞吐率取决于流水线中最慢一段所需的时间,该段成为流水线的瓶颈
消除瓶颈的方法
细分瓶颈段
重复设置瓶颈段

image-20211219123308211

加速比

1
流水线速度与等功能的非流水线速度之比

效率

1
流水线的设备利用率

image-20211219123457264

效率是实际加速比S与最大加速比m之比。

当△t0不变时,流水线的效率与吞吐率呈正比。为提高效率而采取的措施,也有助于提高吞吐率。

1
2
3
4
5
6
7
流水线并不能减少(而且一般是增加)单条指令的执行时间,但能够提高吞吐率
增加流水线的深度可以提高流水线性能
流水线深度受限于流水线的延迟和额外开销
需要用高速锁存器作为流水线寄存器
Earle锁存器
指令之间存在的相关,产生了流水线的冲突,进而限制了流水线的性能

流水线冲突

流水线冲突是指相邻或相近的两条指令因存在某种关联,后一条指令不能在原先指定的时钟周期开始执行。

三种不同类型的冲突

1
2
3
结构冲突(Structural Hazard):当指令在重叠执行过程中,硬件资源满足不了指令重叠执行的要求而发生的冲突。
数据冲突(Data Hazard):因一条指令需要用到前面指令的结果,而无法与产生结果的指令重叠执行时发生的冲突。
控制冲突(Control Hazard):当流水线遇到分支指令和其它会改变PC值的指令所引起的冲突。

导致结构冲突的常见原因:

1
2
功能部件不是全流水
重复设置的资源数量不足

避免结构冲突的方法:

1
2
3
所有功能单元完全流水化
设置足够多的硬件资源
但是,硬件代价很大!

有些设计方案允许结构冲突存在

1
2
降低成本
减少功能单元的延迟

数据冲突

1
2
产生原因:当指令在流水线中重叠执行时,流水线有可能改变指令读/写操作数的顺序,使之不同于它们在非流水实现时的顺序,这将导致数据冲突。
消除方法:向流水线中插入暂停周期
1
2
3
4
5
通过定向技术减少数据冲突带来的暂停
进一步推广:一个结果不仅可以从某一功能单元的输出定向到其自身的输入,而且还可以定向到其它功能单元的输入。 (举例)
在MIPS中,任何流水寄存器到任何功能单元的输入都可能需要定向路径,将形成复杂的旁路网络。
两条指令访问同一存储单元,也可能引起数据冲突,例如访问数据Cache失效时。

编译调度

1
编译器可以通过重新排列代码的顺序来消除这种暂停,这种技术就是“流水线调度”或“指令调度”
1
2
3
4
5
6
指令发射(Issue):指令从流水线的译码段进入执行段的过程称为指令发射。
检测数据冲突
ID段可以检测所有数据冲突
也可以在使用一个操作数的时钟周期的开始(EX和MEM段的开始)检测相关,并确定必需的定向
流水线相关硬件可以检测到的各种冲突情况

指令级并行

记分牌的性能受限于以下几个方面:

1
2
3
4
5
6
7
8
程序代码中可开发的并行性,即是否存在可以并行执行的不相关的指令。
记分牌的容量。
记分牌的容量决定了流水线能在多大范围内寻找不相关指令。流水线中可以同时容纳的指令数量称为指令窗口。
功能部件的数目和种类。
功能部件的总数决定了结构冲突的严重程度。
反相关和输出相关。
它们引起计分牌中更多的WAR和WAW冲突 。

Tomasulo算法的优点

1
2
3
4
5
6
分布式硬件冲突检测。
利用寄存器换名,彻底消除WAW和WAR这两种名相关
如果多个保留站等待同一个操作数,当操作数在CDB上广播时,他们可以同时获得所需的数据
对于存储器访问,动态存储器地址判别技术可解决RAW冲突(取操作数时判断)、WAR和WAW冲突(存操作数时判断)。
能够达到很高的性能。

缺点

1
2
3
4
5
高复杂性:需要大量硬件
存在瓶颈:单个公共数据总线(CDB)引发竞争
额外的CDB:在每个保留站上需要为每条CDB设置重复的硬件接口
为了保证正确的异常行为,对指令的执行有一个限制:一旦有一条分支指令还没有执行完,其后的指令是不允许进入执行段

分支预测

1
2
3
4
5
6
最简单的分支预测策略
BPB也被称为BHT(Branch History Table,BHT)
分支预测缓冲是一个小的存储器阵列
每个单元最小可以只有1位,记录最近一次分支是否成功的信息
预测位为1时,表示预测分支成功,并从目标位置开始取指令
在预测错误时,要作废已经预取和分析的指令,恢复现场,并从另一条分支路径重新取指令。

绪论

奥卡姆剃刀:若有多个假设与观察一致,则选择最简单的那个。

NFL定理(No Free Lunch Theorem):所有学习算法期望性能相同。

Independent and identically distributed,独立同分布,IID

模型评估与选择

经验误差与过拟合

若在m个样本中有a个样本分类错误,则称错误率为E=a/m;

精度=1-错误率;

学习器在训练集上的误差称为训练误差或经验误差,在新样本的误差称为泛化误差。

过拟合:把训练样本自身的一些特点当成了所有潜在样本都会具有的一般性质,这样就会导致泛化性能下降。

欠拟合:训练样本的一般性质尚未学好。

评估方法

留出法

直接将数据集划分为两个互斥的集合,其中一个集合作为训练集,另一个作为测试集。

分层采样:保留类别比例的采样方式。

交叉验证法

先将数据集D划分为k个大小相似的互斥子集,每次用k-1个子集的并集作为训练集,余下的那个子集作为测试集,从而进行k次训练和测试,最终返回k个测试的均值。通常把交叉验证法称为k折交叉验证法。

当k=m时,得到交叉验证法的特例:留一法(Leave-One-Out,简称LOC)。留一法评估结果往往比较准确,但计算开销较大。

自助法

以自主采样为基础,给定包含m个样本的数据集,每次随机从中挑选一个并放回,重复执行m次,则得到一个包含m个样本的数据集$D’$,样本在m次采样中始终不被取得的概率取极限为0.368.这样的测试结果,也称为包外估计。

自助法在数据集较小,难以有效划分训练/测试集时很有用。但是自助法产生的数据集会改变初始数据集分布,这会引入估计偏差,因此,在数据量足够时,留出法和交叉验证法更加常用。

性能度量

在预测任务中,给定样例集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$,其中$y_i$是示例$x_i$的真实标记。

回归任务最常用的性能度量是均方误差。

下面是一些常用的性能度量。

错误率与精度

对样本集D,分类错误率定义为

精度定义为

查准率、查全率与F1

img

查准率P:$P=\frac{TP}{TP+FP}$

查全率R:$R=\frac{TP}{TP+FN}$

查准率与查全率为一对矛盾的度量。通常只有在一些简单任务中,才可能使查准率与查全率都很高。

img

若一个学习器的PR曲线完全被另一个学习器的曲线包住,则可断言,后者的性能优于前者。

平衡点(Break-Even Point,简称BEP)为查准率与查全率相等时的取值。

但BEP度量还是简单一点,更为常用的是F1度量:

F1度量的一般形式-$F_\beta$

$\beta$>1查全率有更大影响。

img

ROC与AOC

ROC曲线的纵轴是真正例率(True Positive Rate,TPR),横轴是假正例率(False Positive Rate,FPR)

img

若一个学习器的ROC曲线被另一个学习器的曲线完全“包住”,则可断言后者性能优于前者。但是当有交叉时,一般难以判断,此时较为合理的依据是比较ROC曲线下的面积,即AUC.(Area Under ROC Curve)

$l_{rank}$定义为

img

AUC=1-$l_{rank}$

以下为对$l_{rank}$的通俗解释:

假设我们在做一个手写数字识别,识别样本数字是否为5,输入12个数字,经过算法得出每个数字的打分从小到大如下(分越高表示算法认为这个数字越接近5,用A表示正例,B表示反例):B1,B2,B3,B4,A1,B5,A2,A3,B6,A4,A5,A6

对于第一个正例A1,有两个反例比他大,则为2,对于第二三个正例,有一个,其余没有,则分子为2+1+1+0+0+0=4,分母为正例数,反例数=6*6=36,则此时$l_{rank}$为4/36=1/9

代价敏感错误率与代价曲线

img

代价敏感错误率为

在非均等代价下,ROC曲线不能直接反映出学习器的期望总体代价,而代价曲线则可达到该目的。

代价曲线图的横轴是取值为[0,1]的正概率代价

代价曲线图的横轴是取值为[0,1]的正例概率代价

其中p是样例为正例的概率;纵轴是取值为[0,1]的归一化代价

代价曲线绘制很简单:ROC曲线上每一点对应了代价平面上的一条线段,设ROC曲线上点的坐标为(FPR,TPR),则可计算出FNR,然后在代价平面上绘制一条从(0,FPR)到(1,FNR)的线段,线段下的面积表示了该条件下的期望总体代价。

img

比较检验

本节默认以错误率为性能度量,用$\epsilon$表示

假设检验

泛化错误率为$\epsilon$的学习器在一个样本上犯错的概率是$\epsilon$;测试错误率$\hat{\epsilon } $意味着在m个测试样本中恰好有$\hat{\epsilon } $*m个被误分类。

我们可使用“二项检验”来对“$\epsilon$<=$\hat{\epsilon}_0$”这样的假设进行检验。

在很多时候我们并不是做一次留出法估计,而是通过多次重复留出法或是交叉验证法等进行多次训练和测试,这样会得到多个测试错误率,此时可用”t-检验”。平均测试错误率$\mu$和方差$\sigma^2$为

考虑到k个测试错误率可看作泛化错误率$\epsilon_0$的独立采样,则变量

服从自由度为k-1的t分布。

img

交叉验证t检验

对于两个学习器A和B,若我们使用k折交叉验证法得到的错误测试率分别为$\epsilon^A_1$…和$\epsilon_1^B$…,则可使用k折交叉验证”成对t检验”来进行比较检验。可根据差值来对学习器A与B性能相同这个假设做t检验,计算出插值的均值$\mu$和方差$\sigma^2$,在显著度$\alpha$下,若变量

小于临界值,则假设不能被拒绝。

McNemar检验

img

若我们做的假设是两学习器性能相同,则应有$e{01}=e{10}$,那么变量$|e{01}-e{10}|$应当服从正态分布。McNemar检验考虑变量

服从自由度为1的$\chi^2$分布

Friedman检验与Nemenyi后续检验

之前介绍的都是在一个数据集上比较两个算法的性能,而在很多时候,我们会在一组数据集上比较多个算法。此时可以使用基于算法排序的Friedman检验。

当所有算法性能相同这个假设被拒绝,则说明算法的性能显著不同,这时需要后续检验来区分,常用的有Nemenyi后续检验。

偏差与方差

偏差度量了学习算法的期望预测与真实结果的偏离程度,即刻画了学习算法本身的拟合能力。

方差度量了同样大小的训练集的变动所导致的学习性能的变化,即刻画了数据扰动所造成的影响。

噪声则表达在当前任务上任何学习算法所能达到的期望泛化误差的下界,即刻画了学习问题本身的难度,

泛化误差可分解为偏差、方差与噪声之和。

线性模型

基本形式

f(x)=w1x1+w2x2+…+wdxd+b

一般用向量形式写成

线性回归

线性回归试图学得

多元线性回归

对数线性回归

广义线性模型

对数几率回归

对数几率函数,“Sigmod函数”,将Z值转换为1个接近0或1的y值,并且其输出在z=0附近变化很陡。

带入得

将上述式子变换得

注:极大似然估计,梯度下降法,牛顿法,请参考实验。

线性判别分析

线性判别分析(Linear Discriminant Analysis,简称LDA)是一种经典的线性学习方法。

LDA的思想非常朴素:给定训练样例集,设法将样例投影到一条直线上,使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离;在对新样本进行分类时,将其投影到同样的这条直线上,再根据投影点的位置来确定新样本的类别。

img

img

img

定义类内散度矩阵

类间散度矩阵$S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T$

则有最大化目标

这就是LDA想要最大化的目标,即$S_b与S_w$的“广义瑞利商”。

上述式子只与$w$的方向有关,与长度无关,故不是一般性,令$w^TS_ww=1$,根据拉格朗日乘子法,等价于

注意到$S_bw$的方向恒为$\mu_0-\mu_1$

则令$S_bw=\lambda(\mu_0-\mu_1)$

代入得$w=S^{-1}_w(\mu_0-\mu_1)$

考虑到数值解的稳定性,在实践中通常是对$S_w$进行奇异值分解,即$S_w=U\Sigma V^T$

值得一提的是,LDA可从贝叶斯决策理论的角度来阐述,并可以证明,当两类数据同先验、满足高斯分布且协方差相等时,LDA可达到最优分类。

可将LDA推广到多分类任务。

多分类学习

多分类学习的基本思路是拆解法,即将多分类任务拆为若干个二分类任务求解 。最经典的拆分策略有三种,一对一(one vs one,OvO),一对其余(one vs rest,OvR),多对多(manay vs many,MvM)。

OvO将这N个类别两两配对,从而产生N(N-1)/2个二分类任务。

OvR则是每次将一个类的样例作为正例,所有其他类的样例作为反例来训练N个分类器。在测试时若仅有一个分类器预测为正类,则对应的类别标记作为最终分类结果。若有多个分类器预测为正类,则通常考虑各分类器的预测置信度,选择置信度最大的类别标记作为分类结果。

img

可以看出,OvR只需要训练N个分类器,而OvO需训练N(N-1)/2个分类器,因此,OvO的存储开销和测试时间开销通常比OvR大。但在训练时,OvR的每个分类器均使用全部训练样例,而OvO的每个分类器仅用到两个类的样例,因此,在类别很多时,OvO的训练时间开销通常比OvR更小。至于预测性能,多数情况下二者差不多。

介绍一种MvM最常用的技术,纠错输出码(Erroe Correcting Output Codes,ECOC),它是将编码的思想引入类别拆分,并尽可能在解码过程中具有容错性。EOOC工作过程主要分为两步:

编码:对N个类别做M次划分,每次划分将一部分划分为正类,一部分划分为反类,从而形成一个二分类训练器;这样一共产生M个训练集,可训练出M个分类器。

解码:M个分类器对测试样本进行预测,这些预测标记组成一个编码。将这个预测编码与每个类别各自的编码进行比较,返回其中距离最小的类别作为最终预测结果。

对于同一个学习任务,EOOC编码越长,纠错能力越强。

类别不平衡问题

一个基本策略是再缩放。

大体有三种做法:

欠采样:去除一些样例使得正反例数目接近

过采样:增加一些样例使得正反例数目接近

第三类是基于原始数据训练,,再进行阈值转移。

欠采样法的时间开销通常远小于过采样。过采样法不能简单对初始样本进行重复采样,否则会过拟合。

决策树

基本流程

决策树学习基本算法

img

划分选择

信息增益

信息熵为度量样本集合纯度最常用的一种指标。假定样本集合D中第k类样本所占的比例为$p_k$,则D的信息熵定义为

Ent(D)的值越小,则D的纯度越高。

假定离散属性有v个可能的取值,若使用a来对样本集D进行划分,则会产生V个分支结点,其中第v个分支结点包括了D中所有在属性a上取值为$a^v$的样本,记为$D^v$。则可又获得信息增益:

著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性的。

X和Y的交互信息

样本熵:各类样本熵之和

增益率

但是,显而易见,信息增益准则对于可取数目较多的属性有所偏好,所以我们引入增益率。著名的C4.5决策树算法便是使用增益率来哈分最优划分属性的。增益率定义为

需要注意,增益率准则对于可取纸2数目较少的属性有所偏好,因此C4.5并不是直接使用增益率准则来进行划分的,而是采用了一个启发式算法,先从候选划分属性中zhaochu1信息增益高于平均水平的属性,再从中选择增益率最高的。

基尼系数

CART决策树采用基尼指数来选择划分属性。数据集D的纯度可用基尼系数来度量:

直观理解的话,基尼系数反应了从数据集D中随机抽取两个样本,其分类不一致的概率。

属性a的基尼系数定义为

剪枝处理

剪枝(pruning)是决策树学习算法对应过拟合的主要手段。决策树基本策略有预剪枝(prepruning)和后剪枝(postpruning)。

预剪枝是在决策树生成过程中,对每个结点在划分前进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一颗完整的决策树,然后自底向上地对非叶结点进行考察,若将该节点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。

预剪枝使决策树很多分支都没有展开,降低了过拟合风险,减少了决策树训练时间开销和测试时间开销,但会带来欠拟合的风险。

后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树。

连续与缺失值

连续值处理

由于连续属性的可取数目不再有限,因此不能直接根据连续属性的可取值来对结点进行划分。此时,连续属性离散化技术派上用处。最简单策略就是采用二分法,正是C4.5决策树算法采用的机制。

缺失值处理

在以下三方面影响到决策树构建

影响杂质测量计算方式;影响如何将缺失值的实例分配到子节点;影响具有缺失值的测试实例如何被分配

原信息增益=去除缺失值信息增益*(去除后的样本数/总样本数)

多变量决策树

每个节点划分为线性分类器。对属性的线性组合进行测试。

考点

基于决策树分类的优点

构建过程计算资源开销小;

分类未知样本速度极快;

对于小规模的树比较容易解释;

在许多小的简单数据集合性能与其他方法相近。

TOP-DOWN决策树

image-20211117162908027

过拟合

pre-pruning

如果所有的实例都属于同一类别就停止;如果所有的属性值都一样就停止。

更加具有限制性的,如果实例的数量少于用户指定的阈值;如果实例的类别分布与可用的特征无关;如果扩展当前节点不能改善纯度。(基尼系数或信息增益)

post-pruning

将决策树增长到其全部内容,以自下而上的方式修剪。若修剪后泛化错误得到改善,则将子树替换为叶子。可使用MDL修剪。

MDL

最小描述长度准则—Minimum Description Length

image-20211117203144245

分发实例的过程,将缺失值按照权重分别分发给不同的分支。如下图:

image-20211117203735045

对于新实例有缺失值的情况下如何分类,也要利用概率来看。

惩罚项

惩罚项比重影响 :比重大时降低模型复杂度 ;比重适当时模型复杂度与问题匹配 ;比重小时、退化成原模型

支持向量机

support vector machine,SVM

间隔与支持向量

给定训练集样本D,分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面。

在样本空间中,划分超平面可通过如下线性方程来描述:$w^T x+b$

其中$w$为法向量,决定了超平面的方向,b为位移量。我们将该平面记做(w,b)

样本空间中任一点x到该超平面的距离可写为

假设超平面可将训练样本正确分类,对于$(x_i,y_i)$,若$y_i=1$,则有$w^T x+b>$0,若为-1则<0

如图所示,距离超平面最近的这几个训练样本使上述等号成立,他们被称为支持向量,两个异类支持向量,两个异类支持向量到超平面的距离之和为$\gamma=\frac{2}{||w||}$,它被称为间隔。

img

想要找到最大间隔,即找到最大$w与b$,使得$\lambda$最大。

显然,为了最大化间隔,仅需要最大化$||w||^{-1}$,这等价于最小化$||w||^2$,于是便有

这就是SVM的基本型。

对偶问题

对于SVM的基本型,添加拉格朗日乘子$\alpha\ge0$,则该问题拉格朗日函数可以写为

其中$\alpha_i=(\alpha_1,\alpha_2,…,\alpha_m)$

分别求偏导,$w=\sum{i=1}^{m}\alpha_i y_i x_i,0=\sum{i=1}^{m}\alpha_i y_i$

代入,可得对偶问题如下

解出$\alpha$后,求出w与b即可得到模型

因为上述过程需要满足KK条件,即要求

$\alpha_i\ge0$

$y_if(x_i)-1\ge0$

$\alpha_i(y_if(x_i)-1)=0$(13)

若$\alpha_i$=0,则该样本不会在12的求和中出现,也就不会对f(x)有影响‘

若后面等于0,则所对应的样本点位于最大间隔边界上,是一个支持向量。

如何求解11呢?我们介绍一种高效的SMO算法。

暂且跳过这部分。

核函数

若在原始样本空间内不存在一个能正确划分两类样本的超平面,面对这类问题,我们可将样本从原始空间映射到一个高维的特征空间,使得样本在这个高维空间内线性可分。并且若原始空间有限,则一定存在一个高维特征空间使样本可分。

令$\phi(x)$表示将x映射后的特征向量,于是,在特征空间中划分超平面所对应的模型可以表示为

$f(x)=w^T\phi(x)+b$

同上,其对偶问题是

求解21会涉及到计算$\phi(x_i)^T\phi(x_i)$,这是样本$x_i与x_j$映射到特征空间后的内积,计算困难,为了避开这个障碍,可以设想一个这样的函数

即$x_i与x_j$在特征空间的内积等于他们在原始样本空间中通过函数$\kappa$计算的结果。

则可进行求解,求解得

这里的$\kappa(,)$就是核函数,24显示出模型最优解可通过训练样本的核函数展开,这一展开式也称为“支持向量展式”。

关于核函数,我们有以下定理:

暂且略过

软间隔与正则化

大多数时候我们很难找到合适的核函数,所以为了缓解这一问题,我们会允许支持向量机在一些样本上出错。为此要引入软间隔的概念。

img

软间隔则是允许某些样本不满足约束

$y_i(w^Tx_i+b)\ge1$(28)

当然,在最大化间隔的同时,不满足约束的样本应尽可能少。于是,优化目标可以写为

贝叶斯分类器

贝叶斯决策论

[最大后验估计(Maximum-a-Posteriori (MAP) Estimation) ]

最大似然估计(MLE)选择值 使观察到的数据的概率最大化
最大后验估计(MAP) 选择在观察到的数据和先验条件下最有可能的值

缺点
MLE: 如果数据集太小,就会过度拟合
MAP: 两个有不同预设的人最终会导致不同的估计值

image-20211117223857004

img

img

极大似然估计

img

img

朴素贝叶斯分类器

img

半朴素贝叶斯分类器

img

其中$pa_i$为属性$x_i$所依赖的属性,称为$x_i$的父属性。问题的关键转换为如何确定每个属性的父属性,不同的做法产生不同的独依赖分类器。

最直接的做法是假设所有属性都依赖于同一个属性,称为“超父”,然后通过交叉验证等模型选择方法来确定超父属性,由此形成了SPODE(Super-Parent ODE)方法,例如(b)中,$x_1$是超父属性。

img

TAN则是在最大带权生成树算法的基础上,通过以下步骤化简为(c)的树形结构。

img

贝叶斯网

Directed Acyclic Graph(DAG):有向无环图

Conditional Probability Table(CPT):条件概率表

具体来说,一个贝叶斯网B由结构G和参数$\theta$两部分构成,即$B=$。

网络结构G为DAG,其每个结点对应于一个属性,若两个属性有直接依赖关系,则他们由一条边连接起来;参数$\theta$定量描述这种依赖关系,假设属性$xi$在G中的父节点为$\pi_i$,则$\theta$包含了每个属性的条件概率表$\theta{x_i|\pi_i}=P_B(x_i|\pi_i)$

结构

给定父节点集,贝叶斯网假设每个属性与它的非后裔属性独立。

img

为了分析有向图中变量间的条件独立性,可使用有向分离。我们先把有向图转变成为一个无向图:

*找出有向图中的所有V型结构,在V型结构的两个父节点之间加上一条无向边;

*将所有有向边改为无向边

由此产生的无向图称为道德图,令父节点相连的过程称为道德化。

若变量x和y能在图上z分开,即从道德图中将变量集合z去除后,x和y分属两个连通分支,则称x和y被z有向分离,$x\perp y|z$成立。

学习

贝叶斯网学习的首要任务就是根据训练数据集来找出结构最恰当的贝叶斯网。评分搜索是求解这一问题的常用办法。具体来说,我们先定义一个评分函数,以此来评估贝叶斯网与训练数据的契合程度,然后基于这个评分函数来寻找结构最优的贝叶斯网。

常用评分函数通常基于信息论准则,此类准则将学习问题看作一个数据压缩任务,学习的目标是找到一个能以最短编码长度描述训练数据的模型,此时编码的长度包括了描述模型自身所需的编码位数和使用该模型描述数据所需的编码位数。对于贝叶斯网学习而言,模型就是一个贝叶斯网,同时,每个贝叶斯网描述了一个在训练数据上的概率分布,我们应选择那个综合编码长度最短的贝叶斯网,这就是最小描述长度准则。(Minimal Description Length,MDL)

给定训练集D,贝叶斯网$B=$在D上的评分函数可写为

其中,|B|是贝叶斯网的参数个数;$f(\theta)$表示描述每个参数$\theta$所需的编码位数。而

是贝叶斯网B的对数似然。显然,28的第一项是计算编码贝叶斯网B所需的编码位数,第二项是表述B所对应的概率分布$P_B$对D的描述有多好。此时,学习任务转换为优化任务,寻找一个贝叶斯网B使得评分函数最小。

若$f(\theta)=1$,则得到AIC评分函数。

若$f(\theta) =\frac12log\ m$,则得到BIC评分函数。

当=0时,评分函数退化为负对数似然函数,学习任务退化为极大似然估计。

为最小化评分函数,只需要对网络结构进行搜索,而候选结构的最优参数可直接在训练集计算得到。

但是,在所有可能的网络空间搜索最优贝叶斯网络是一个NP问题。一般有两种策略在有限时间内求得近似解,第一种为贪心法,第二种是通过给网络结构施加约束来削减搜索空间。

推断

贝叶斯网络的近似推断常使用吉布斯采样来完成,这是一种随机采样方法。

img

img

EM算法

在现实中,会存在许多未观测变量。未观测变量的学名是隐变量,令X表示已观测变量集,Z表示隐变量集,$\theta$表示模型参数,若想要对$\theta$做极大似然估计,则应最大化对数似然

$LL(\theta|X,Z)ln\ P(X,Z|\theta)$

由于Z是隐变量,我们可通过对Z计算期望,来最大化已观测数据的对数“边际似然”

$LL(\theta|X)=ln\ P(X|\theta)=ln\sum_{Z}P(X,Z|\theta)$(35)

img

聚类

聚类任务

在无监督学习中,训练样本的标记信息是未知的,目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律,为进一步的数据分析提供基础,此类学习任务应用最广的是聚类。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集称为一个簇。

img

性能度量

聚类性能度量也称为聚类“有效性指标”。

聚类性能度量大致有两类,一类是将聚类结果与某个“参考模型”进行比较,称为“外部指标”;另一类是直接考察聚类结果而不利用任何参考模型,称为“内部指标”。

img

img

距离计算

对函数$dist$,若他是一个距离度量,则需要满足一些基本性质

非负性:$dist(x_i,x_j)\ge0$

同一性:$dist(x_i,x_j)=0当且仅当x_i=x_j$

对称性

直递性

对于给定样本

最常用的闵可夫斯基距离

当p=2时,闵可夫斯基距离即为欧氏距离

当p=1时,闵可夫斯基距离即为曼哈顿距离

定义域为{1,2,3}这样的属性为有序属性,而定义域为{飞机,轮船,火车}则为无序属性,闵可夫斯基距离用于有序属性。

对无序属性可采用VDM(Value Difference Metric)。令$m{u,a}$表示属性u上取值为a的样本数,$m{u,a,i}$表示在第i个样本簇中在属性u上取值为a的样本数,k为样本簇数,则属性u上两个离散值a与b之间的VDM距离为

于是,将闵可夫斯基距离和VDM结合即可处理混合属性。假定有$n_c$个有序属性、$n-n_c$个无序属性,不失一般性,令有序属性排列在无序属性之前,

当空间中不同属性的重要性不同时,可使用加权距离。

需要注意的是,通常我们是基于某种形式的距离来定义“相似度度量”,距离越大,相似度越小,然而用于相似度度量的距离未必一定要满足距离度量的所有基本性质。不满足直递性的距离称为非度量距离。

原型聚类

也称为基于原型的聚类,此类算法假设聚类结构能通过一组原型刻画。通常对原型进行初始化,然后对原型进行迭代更新求解。

k均值算法

给定样本集$D={x_1,x_2,..,x_m}$,“k均值”算法针对聚类所得簇划分$C={C_1,C_2,…,C_k}$最小化平方误差

k均值算法采用了贪心策略,通过迭代优化来近似求解式。

学习向量量化

Learning Vector Quantization(LVQ)与一般的聚类算法不同,LVQ假设数据样本带有标记类别,学习过程利用样本的这些监督信息来辅助聚类。

给定样本集

每个样本$xj$是由n个属性描述的特征向量$(x{j1};x{j2};…;x{jn})$,$y_i\in \gamma$是样本$x_j$的类别标记。LVQ的目标是学得一组n维向量${p_1,p_2,…,p_n}$,每个原型向量代表一个聚类簇,簇标记$t_i \in \gamma$。

img

高斯混合模型

参考下面这篇文章

https://zhuanlan.zhihu.com/p/30483076

密度聚类

此类算法假设聚类结构能通过样本分布的紧密程度确定。

DBSCAN是一种著名的密度聚类算法,它基于一组“邻域”参数$(\varepsilon,MinPts)$来刻画样本分布的紧密程度。给定数据集$D={x_1,x_2,…,x_m}$,定义以下概念

$\varepsilon-$邻域:对于x,其$\varepsilon$邻域包含样本集D中与$x_j$的距离不大于$\varepsilon$的样本

核心对象:若x的$\varepsilon$邻域至少包含MinPts个样本,则为一个核心对象

密度直达:若$x_j$位于$x_i$的$\varepsilon$邻域中,且$x_i$是核心对象,则称$x_j$由$x_i$密度直达

密度可达:对$x_i$与$x_j$,若存在样本序列

其中$p1=x_i,p_n=x_j$且$p{i+1}$由$p_i$密度直达,则称$x_j$由$x_i$密度可达

密度相连:对$x_i$与$x_j$,若存在$x_k$使得$x_k$使得二者均由$x_k$密度可达,则称二者密度相连。

DBSCAN将簇定义为:由密度可达关系导出的最大的密度相连样本集合。

img

层次聚类

层次聚类试图在不同层次上对数据集进行划分,从而形成树形的聚类结构。数据集的划分可采用“自顶向上”的聚合策略,也可采用“自顶向下”的分拆策略。

AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作一个初始聚类簇,然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并。

当聚类簇距离由

计算时,AGNES算法被相应地称为单链接,全链接和均链接算法。

img

降维与度量学习

k近邻学习

k-Nearest Neighbor,简称kNN学习是一种常用的监督学习方法。

其工作机制是:给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个邻居的信息来进行预测。

k近邻学习没有显示的训练过程,是“懒惰学习”的主要代表,此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为0,待收到测试样本后再进行处理;相应的,那些在训练阶段就对样本进行学习处理的方法称为急切学习。

k近邻的错误率小于贝叶斯的两倍。

低维嵌入

通过某种数学变换将原始高维属性空间转变为一个低维子空间。

若要求原始空间中样本之间的距离在低维空间中得以保持,即得到多维缩放(Multiple Dimensional Scaling,MDS)这样一种经典的降维方法。

主成分分析

Principal Component Analysis,PCA

Verilog

数字表示

基本格式:< 位宽 >’< 数制的符号 >< 数值 >

h十六进制

d十进制

o八进制

b二进制

向量

可直接进行加减等运算,方括号位于向量名前方。eg: reg [7:0] data

数组

方括号位于数组名的后面。括号内的第一个数字为第一个元素的序号,第二 个数字为最后一个元素的序号,中间用冒号隔开。

eg: wire array [15:0];

参数

可以通过 parameter 关键字声明参数以增强模块可拓展性和可读性。

在模块实例化时,可以使用 #() 将所需的实例参数覆盖模块的默认参数。

局部参数可以用 localparam 关键字声明,它不能够进行参数重载。

eg:

1
2
3
4
5
6
7
8
9
10
module adder #(
parameter WIDTH = 4 // 默认宽度为 4
) (
input [WIDTH - 1 : 0] a,
input [WIDTH - 1 : 0] b,
output [WIDTH - 1 : 0] c
);
assign c = a + b;
endmodule

在我们例化这个模块时,可以进行如下操作:

1
2
3
4
5
6
7
8
9
10
11
12
// 覆盖宽度,修改为 6
adder #( .WIDTH (6) ) U_adder_0(
.a (a ),
.b (b ),
.c (c )
);
// 使用默认的宽度 4
adder U_adder_1(
.a (a ),
.b (b ),
.c (c )
);

局部参数 localparam 和参数类似,但是不能在例化时被覆盖。

运算

按位运算

按位取反 ~

按位与 &

按位或 |

按位异或 ^

逻辑运算

• 逻辑取反!

• 逻辑与 &&

• 逻辑或 ||

缩减运算

• 缩减与 &:对一个多位操作数进行缩减与操作,计算所有位之间的与操作结果,例如:&(4’b1011) 的结果为 0

• 缩减或 |:对一个多位操作数进行缩减或操作,计算所有位之间的或操作结果。例如:|(4’b1011) 的结果为 1

• 缩减异或 ^:对一个多位操作数进行缩减异或操作,计算所有位之间的异或操作结果。例如: ^(4’b1011) 的结果为 1

缩减或非、缩减异或、缩减同或是类似的。

移位运算

• 逻辑右移>>:1 个操作数向右移位,产生的空位用 0 填充

• 逻辑左移<<:1 个操作数向左移位,产生的空位用 0 填充

• 算术右移>>>:1 个操作数向右移位。如果是无符号数,则产生的空位用 0 填充;有符号数则用其符号 位填充

• 算术左移<<<:1 个操作数向左移位,产生的空位用 0 填充

其他运算

• 拼接 {,}:2 个操作数分别作为高低位进行拼接,例如:{2’b10,2’b11} 的结果是 4’b1011

• 重复 {n{m}}:将操作数 m 重复 n 次,拼接成一个多位的数。例如:a=2’b01,则 {2{a}} 的结果 是 4’b0101

• 条件? ::根据? 前的表达式是否为真,选择执行后面位于: 左右两个语句。例如:assign c = (a > b) ? a : b,如果 a 大于 b,则将 a 的值赋给 c,否则将 b 的值赋给 c

组合逻辑

always

不推荐使用 always 块来表示组合逻辑。不正确的使用会生成大量锁存器。

下面的例子是一个 32-5 优先编码器,如果 tlb_hit_array 全为 0,那么 tlb_hit_index 也为 0。 always 块中被赋值的变量只能是 reg 类型,但是该编码器并不会综合出寄存器或者锁存器,这是因为 Verilog 中的寄存器 (reg) 和硬件上的寄存器不能完全等价。 如果去掉 tlb_hit_index = 5’d0; 一句,则会综合出锁存器。

1
2
3
4
5
6
7
8
9
10
11
reg [4 :0] tlb_hit_index;
wire [31:0] tlb_hit_array;
integer i;
always @(*) begin
tlb_hit_index = 5'd0;
for (i = 0; i < 32; i = i + 1) begin
if (tlb_hit_array[i]) begin
tlb_hit_index = i;
end
end
end

模块声明和例化

模块被包含在关键字 module、endmodule 之内。

1
2
3
4
5
6
7
module adder ( // 模块名称声明
input [31:0] a, // 输入输出声明
input [31:0] b,
output [31:0] c
);
assign c = a + b; // 变量声明、always 语句、assign 语句等
endmodule // 模块结束

Generate 块

这里只介绍 generate for 块。

generate for 的主要功能就是对模块或组件以及 always 块、assign 语句进行复制。 使用 generate for 的时候, 必须要注意以下几点要求

• 在使用 generate for 的时候必须先声明一个 genvar 变量,用作 for 的循环变量。genvar 是 generate 语句中的一种变量类型,用于在 generate for 语句中声明一个正整数的索引变量。

• for 里面的内嵌语句, 必须写在 begin-end 里

• 尽量对 begin-end 顺序块进行命名

generate for 的语法示例如下:

1
2
3
4
5
genvar i;
generate for (i = 0; i < 4; i = i + 1) begin: gen_assign_temp
assign temp[i] = indata[2 * i + 1 : 2 * i];
end
endgenerat

测试代码

时延语句

仿真中还经常使用时延来构造合适的仿真激励。它是不可综合的,仅能够在仿真中使用。时延分两类,一是 语句内部时延,二是语句间时延,其示例如下所示:

1
2
3
4
5
6
7
// 语句内部时延
A = #5 1'b1;
// 语句间时延
begin
Temp = 1'b1;
#5 A = Temp;
end

两种方式都表达在五个时间单位后,将 A 的值赋为 1。

initial 语句

一般用来生成复位信号和激励。只在仿真开始时执行一次。

1
2
3
4
5
6
7
8
9
// 测试代码中
// 假设`timescale 1ns / 1ps
reg rst_n, clk;
always #5 clk = ~clk;
initial begin
rst_n = 1'b0;
clk = 1'b0;
#50 rst_n = 1'b1;
end

会生成一个 100MHz 的时钟,一个 50ns 有效的复位信号。

系统任务

系统任务可以被用来执行一些系统设计所需的输入、输出、时序检查、仿真控制操作。所有的系统任务名称 前都带有符号 $ 使之与用户定义的任务和函数相区分。

常见的系统任务:

• $display:用于显示指定的字符串,然后自动换行(用法类似 C 语言中的 printf 函数)

• $time:可以提取当前的仿真时间

• $stop:暂停仿真

• $finish:终止仿真

• $random:生成随机数

• $readmemh:读入一个 16 进制数的文件以初始化 reg

测试设计

测试最基本的结构包括信号声明、激励和模块例化。 测试模块声明时,一般不需要声明端口。因为激励信号一般都在测试模块内部,没有外部信号。 声明的变量应该能全部对应被测试模块的端口。当然,变量不一定要与被测试模块端口名字一样。但是被测试模块输入端对应的变量应该声明为 reg 型,输出端对应的变量应该声明为 wire 型。 仿真过程中可以使用 $display 显示当前仿真进度或者测试结果。 在测试完成或者发现错误时可以使用 $finish; 或者 $stop; 来停止仿真。