CyannyLive

Reliability, Scalability and Availability are the most important three features for a distributed file system. In HDFS, persistent metadata, using the Secondary NameNode to create checkpoint against data loss, using block replication across the cluster against DataNode failure, all of these brings HDFS high reliability. And the master slave architecture wins HDFS great scalability. [more…]
However, HDFS has always had a well-known Single Point of Failure (SPOF) which impacts HDFS’s availability. HDFS fits well for ETL or batch-processing workflows, but in the past few years HDFS begin to be used for real time job, such as HBase. To recover a single NameNode, an administrator starts a new primary NameNode with FsImage and replays its EditLog, waits for Blockreport from DataNodes to leave safe mode. On large clusters with many files and blocks, it will take 30 minutes or more time to recovery. Long time recovery will impact the productivity of internal users and perhaps results in downtime visible to external users.
For these reasons, Hadoop community began a new feature for HDFS called High Availability Name Node (HA Name Node) in 2011. The HA makes use of an active and a standby NameNode. When the active NameNode fails, the hot standby NameNode will take over serving the role of an active NameNode without a significant interruption.

HA Architecture

Figure1 HDFS High Availability Architecture
As shown in Figure 1, HA architecture has several changes

• The NameNodes must use highly available shared storage to share EditLog, such as Network File System (NFS), or BookKeeper. The active NameNode will write its EditLog on the Shared dir, and the Standby NameNode polls the shared log frequently and then applies to its in-memory so as to has the most complete and up-to-date file system state in memory.
• DataNodes must send Blockreports with block locations to both active and standy NameNodes. Because the block mappings are stored in a NameNode’s memory and not on a disk to increase data access performance.
• Clients must be configured to handle NameNode failover, using a mechanism that is transparent to users.
  The HA guarantees if the active NameNode fails, the standby one will take over quickly in tens of seconds, since it has the latest state available in memory: the latest EditLog entries and an up-to-date block mapping.

Failover

The transition from the active NameNode to the standby NameNode is controlled by the failover controller. Each NameNode runs a failover controller to monitor its namenode failure, which is a heartbeating mechanism. Failover is triggered when a NameNode fails.

After NameNode failover, the Client must be informed which is active NameNode now. Client Failover is handled transparently by the client library. The HDFS client supports the configuration for multiple network addresses, one for each NameNode. The NameNode is identified by a single logical URI which is mapped the two network addresses of the HA Name Nodes via client-side configuration. The client will retry the two addresses until the active NameNode is found.

Fencing

After Failover, HDFS makes use of the fencing technique to make sure that the previous died active NameNode is prevented from doing any damage and causing corruption. These mechanisms includes killing the NameNode’s process, revoking its access to the shared storage directory and disabling its network port via a remote management command. If these techniques fail, HDFS will use STONITH, that is “shoot the other node in the head”, which uses a specialized power distribution unit to forcibly power down the host machine.

Resources:
Part 0 Hadoop Overview
Part 1 Hadoop HDFS Review
Part 2 Hadoop HDFS Federation
Part 3 Hadoop HDFS High Availability(HA)
Part 4 Hadoop MapReduce Overview
Part 5 Hadoop MapReduce 1 Framework
Part 6 Hadoop MapReduce 2 (YARN)
Part 7 Hadoop isn’t Silver Bullet

In traditional HDFS architecture, there is only one NameNode in a cluster, which maintains all of the namespace and block map. Regarding that Hadoop cluster is becoming larger and larger one enterprise platform and every file and block information is in NameNode RAM, when there are more than 4000 nodes with many files, the NameNode memory will reach its limit and it becomes the limiting factor for cluster scaling. In Hadoop 2.x release series, Hadoop introduces HDFS Federation, which allows a cluster to scale by adding NameNodes, each of which manages a portion of the filesystem namespace.[more…]
Figure1 HDFS Federation
As shown in Figure1, there are many federated NameNodes which manages its own namespace. The NameNodes are independent and don’t require coordination with each other. The DataNodes are used as common storage for blocks. Each DataNode registers with all the NameNodes in the cluster and send periodic heartbeats and block report and handles commands from the NameNodes.
Each NameNode is responsible for two tasks: Namespace management and Block Management. For the two tasks, mange NameNode manages its own Namespace Volume, which consists of two parts:

• Namespace: the metadata for each file and block
• Block Pool: it is a set of blocks that belong to a single namespace. The Block Pool is in charge of block management task, including processing block reports and maintaining location of blocks.
  Block pool storage is not partitioned , so DataNodes register with each NameNode in the cluster and store blocks from multiple block pools. The NameNode namespace must to generate block ID for new blocks.
  A NameSpace Volume is a self-contained uinit . Each NameNode has no need to contact other NameNode and it’s failure will not influence other NameNode.
  To access a federated HDFS, clients use client-side mount tables to map file paths to NameNodes. A new identifier ClusterID is added to all the nodes in the cluser. Federated NameNodes is configured by ViewFileSystem and the viewfs://URIs.
  The HDFS Federation brings several benefits:

• NameSpace Scalability: It will support large clusters with many files, just add more NameNode to scale namespace.
• Performance: Break the limitation of single node, more NameNodes means more read/write operations and the throughput is improved.
• Isolation: A single NameNode has no isolation in multi user environment. While multiple NameNodes can provide isolated NameSpace for both production and experiment application.

Resources:
Part 0 Hadoop Overview
Part 1 Hadoop HDFS Review
Part 2 Hadoop HDFS Federation
Part 3 Hadoop HDFS High Availability(HA)
Part 4 Hadoop MapReduce Overview
Part 5 Hadoop MapReduce 1 Framework
Part 6 Hadoop MapReduce 2 (YARN)
Part 7 Hadoop isn’t Silver Bullet

HDFS Basic Concepts

Hadoop Distributed File System, know as HDFS, is a distributed file system designed to store large data sets and streaming data sets on commodity hardware with high scalability, reliability and availability.

HDFS is written in Java based on the Google File System (GFS). HDFS has many advantages compared with other distributed file systems:

1. Highly fault-tolerant

Fault-tolerant is the core architecture for HDFS. Since HDFS can run on low-cost and unreliable hardware, the hardware has a non-trivial probability of failures. HDFS is designed to carry on working without a noticeable interruption to the user in the face of such failure. HDFS provides redundant storage for massive amounts of data and Heartbeat for failure detection.
When one node fails, the master will detect it and re-assign the work to a different node. Restarting a node doesn’t need communicating with other data node. When failed node restart it will be added the system automatically. If a node appears to run slowly, the master can redundantly execute another instance of the same task, know as ‘speculative execution’.[more…]

2. Streaming Data Access

HDFS is designed with the most efficient data processing pattern: a write once, read-many times pattern. HDFS split large files into blocks, usually 64MB or 128MB. HDFS performs best with a modest number of large files. It prefers millions, rather than billions of files, and each of which is 100MB or more. No random writes to files is allowed. Also HDFS is optimized for large, steaming reads of files. No Random reads is allowed.

A data set is generated and copied from source and replicated spread the HDFS system. It is efficient to load data from HDFS for big data analysis.

3. Large data sets

Large data means files that are MB, GB or TB in size. There are Hadoop clusters today that store PB data. HDFS support high aggregate data bandwidth and scale to hundreds of nodes in a single cluster. It also supports tens of millions of files processing.

HDFS NameNode and DataNodes Architecture

HDFS has a master/slave architecture. As shown in Figure1.

The master node is the NameNode, which managers the file system namespace, file metadata and regulates the access interface for files by clients. A cluster has only one NameNode, which maintain the map of file metadata and the location of blocks.

The slave nodes are the DataNodes. A cluster has many DataNodes, which holds the actual data blocks.

Figure1 HDFS Architecture

NameNode

NameNode maintains the namespace tree, which is logical location and the mapping of file blocks to DataNodes, which is the physical location.

The NameNode executes file system namespace operations like opening, closing, and renaming files and directories. It provides POSIX interface for client, so that user can access HDFS data with Unix like commands and no need to know about the function of NameNode and DataNodes. It is kind of abstraction which decrease the complexity for data access.

The NameNode is the pivot in a cluster. A single NameNode greatly simplifies the architecture of HDFS. NameNode holds all of its metadata in RAM for fast access. It keeps a record of change on disk for crash recovery.

However, once the NameNode fails, the cluster fails. The Single Point of Failure, known as SPOF is really a bottleneck for NameNode. Hadoop 2.0 introduces NameNode Federation and High Availability to solve the problem. We will discuss these in later section.

NameNode Data Persistent

In case of NameNode crash, the namespace information and metadata updates are stored persistently on the local disk in the form of two files: the namespace image called FsImage and the EditLog.

FsImage is an image file persistently stores the file system namespace, including the file system tree and the metadata for all the files and the directories in the tree, the mapping of blocks to files and file system properties.

EditLog is a transaction log to persistently record every change that occurs to file system metadata.

However, we have to know there is one thing that is not persistent. The block locations we can call it Blockmap, which is stored in NameNode in-memory, not persistent on the local disk. Blockmap is reconstructed from DataNodes when the system starts by the Blockreport of DataNodes.

When the system starts up, NameNode will load FsImage and EditLog from the local disk, applies the transactions from the EditLog to the in-memory representation of the FsImage, and flushes out the new version of FsImage on disk. Then it truncates the old EditLog since its transactions has been applied to the FsImage. This process is called a checkpoint.

Secondary NameNode

To increase the reliability and availability of the NameNode, a separate daemon known as the Secondary NameNode takes care of some housekeeping tasks for the NameNode. Be careful that the Secondary NameNode is not a backup or a hot standby NameNode.

The housekeeping wok is to periodically merge the namespace image FsImage with the EditLog to prevent the EditLog becoming to large. The Secondary NameNode runs on a single Node, which is a separate physical machine with as much memory and CPU requirements as the NameNode.

The Secondary NameNode keeps a copy of the merged namespace image in case of the NameNode fails. But the time lags will result in data loss certainly. And during the NameNode recovery, the reconstruction of the Blockmap will cost too much time. So Hadoop works out the problem with Hadoop High Availability solution.

DataNodes

The DataNodes holds all the actual data blocks. In sum up, it has three functions:

• Serves read and requests from the file system clients.
• Provides block operations, like creation, deletion and replication upon instruction from the NameNode.
• Make data Blockreport to NameNode periodically with lists of blocks that they are storing.

In enterprise Hadoop deployment, each DataNode is a java program run on a separate JVM, and one instance of DataNode on one machine.

In addition, NameNode is a java program run on a single machine. Written in java provides Hadoop good portability.

The Communication Protocols

HDFS client, NameNode and DataNodes communication protocols are TCP/IP. Client Protocol is TCP connection between a client and NameNode. The DataNode Protocol is the connection between the NameNode and the DataNodes. HDFS makes an abstraction wraps for the Client Protocol and the DataNode Protocol, which called Remote Procedure Call (RPC). NameNode never initiates any RPCs, only responds to RPC requests from clients or DataNodes.

HDFS Files Organization

In traditional concepts, a disk has a block size, which is the minimum amount of data that it can read or write. Disk blocks are normally 512 bytes. While HDFS has the concept of block as well, which is a much larger unit – 64MB by default.

HDFS large files are chopped up into 64MB or 128MB blocks. This brings several benefits:

• It can take advantage of any of the disks in the cluster, when the file is larger than any single disk.
• Making the unit of abstraction of a block simplifies the storage subsystem. HDFS will deal with blocks, rather than a file. Since blocks are a fixed size, it’s easy to calculate how many can be stored on a give disk and eliminate metadata concerns.
• Normally, a map task will operate on one local block at a time. Bocks spare the complexity of dealing with files.
• It’s easy to do data replication with blocks for providing fault tolerance and availability. Each block is replicated multiple times. Default is to replicate each block 3 times. Replicas are stored on different nodes.
• Block data fits well for streaming data. Files are written once and read many times. Blocks minimize the cost of seeking files.

Although files are split into 64MB or 128MB blocks ， if a file is smaller than this full 64MB/128MB will not be split.

HDFS Data Replication

HDFS each data block has a replica factor, which indicates how many times it should be replicated. Normally, the replica factor is three. Each block is replicated three times and spread on three different machines across the cluster. This provides efficient MapReduce processing because of good data locality.
Figure2 Block Replication
As shown in Figure2, the NameNode holds the metadata for each map of file and blocks, including filename, replica factor and block-id etc. Block data are spread on different DataNodes.

Data Replica Placement

Block replica placement is not random. Regarding of the reliability and the performance, HDFS policy is to put one replica on one node in the local rack, the second one on a node in a different remote rack and the third one on a different node in the same remote rack.
Figure 3 HDFS Racks
As shown in Figure 3, different DataNodes on different racks, Rack 0 and Rack1. Large HDFS instance run on a cluster of machines that commonly spread across many racks. Network bandwidth for intra-racks is greater than inter-racks. So the HDFS replica policy cuts the inter-rack write traffic and improves write performance. One third of replicas are on one node, two third of replicas are on one rack, the other third are distributed across the remaining racks. This policy guarantees the reliability.

Data Replication Pipeline

Figure 4 Data Replication Pipeline
As shown in Figure 4, it is the data flow of writing data to HDFS. A client request to request a file does not reach the NameNode immediately. It will follow the steps:
Step 1, the HDFS client caches the file data into a temporary local file until the local file accumulates data worth over one HDFS block size.
Step 2, the client contacts the NameNode, requests add a File.
Step 3, the NameNode inserts the file name into the file system tree and allocates a data block for it. Then responds to the client request with the identity of the DataNodes and the destination data block.
Step 4, suppose the HDFS file has a replication factor of three. The client retrieves a list of DataNodes, which contains that will host a replica of that block. The clients flushes the block of data from the local temporary file to the first DataNode.
Step 5,.the first DataNode starts receiving the data in small portions like 4KB, writes each portion to its local repository and transfers that portion to the second DataNode. Then the second DataNode retrieves the data portion, stores it and transfers to the third DataNode. Data is pipelined from the first DataNode to the third one.
Step 6, when a file is closed, the remaining un-flushed data in temporary local file is transferred to the DataNode. Then the client tells the NameNode that the file is closed.
Step 7, the NameNode commits the file creation operation into a persistent one. Be careful if the NameNode dies before the file is closed, the file is lost.
So far, we can see that file caching policy improves the writing performance. HDFS is write-once-read-many-times. When a client wants to read a file: It should contacts the NameNode to retrieves the file block map, including block id, block physical location. Then it communicates directly with the DataNodes to read data. The NameNode will not be a bottleneck for data transfer.

Resources:
Part 0 Hadoop Overview
Part 1 Hadoop HDFS Review
Part 2 Hadoop HDFS Federation
Part 3 Hadoop HDFS High Availability(HA)
Part 4 Hadoop MapReduce Overview
Part 5 Hadoop MapReduce 1 Framework
Part 6 Hadoop MapReduce 2 (YARN)
Part 7 Hadoop isn’t Silver Bullet

The motivation for Hadoop

Apache Hadoop is an open source distributed computing framework for large-scale data sets processing. Doug Cutting, who is the creator of Apache Lucene Project, creates it.

The name of Hadoop is a made-up name, which is the nickname of a stuffed yellow elephant of the kid of Doug. Hadoop has its origins in Apache Nutch, an open source web search engine, and it is built based on work done by Google in early 2000s, specifically on Google papers describing the Google File System (GFS) published in 2003, and MapReduce published in 2004.

Hadoop moved out of Nutch to form an independent in Feb. 2006. Up to now, Hadoop has been powered by many companies, such as Yahoo who claims it has the biggest Hadoop cluster in the world with more than 42000 nodes, LinkedIn who has 4100 nodes, Facebook who has 1400 nodes, Taobao who has the biggest cluster in China with more than 2000 nodes. [more…]

The problems for traditional big data processing

Why these companies adopt Hadoop? The reason is simple, that we live in a big data age. We are flooded with big data every day on the Internet. Consider that: Facebook hosts approximately 10 billion photos, taken up on PB storage. Every second on eBay, a total merchandise value of 1400 dollars is traded and 10 million new items are listed on eBay every day. Ancestry.com, the genealogy site, store around 2.5 PB of Data.

How to make use of these big data to make analysis? For traditional methods, use only one machine to process computation, which needs faster processor and RAM. Even though the CPU power doubles every 18 months according to Moores’s Law, it hasn’t meet the big data analysis needs. Yet distributed system evolved to allow developers to use multiple machines for a single job, like MPI, PVM and Condor. However, programing for these traditional distributed systems is complex, you have to deal with these problems:

• It’s difficult to deal with partial failures of the system. Developers spend more time designing for failure than they do actually working on the problem itself.
• Finite and precious bandwidth must be available to combine data from different disks and transfer time is very slow for big data volume.
• Data exchange requires synchronization.
• Temporal dependencies are complicated.

How can Hadoop save big data analysis

What really counts is big data. Traditional distributed computing can’t handle big data in a decent way, but Hadoop can. Lets see what Hadoop brings to us:

• Hadoop provide partial failure support. Hadoop Distributed File System (HDFS) can store large data sets with high reliability and scalability.
• HDFS provide great fault tolerance. Partial Failure will not result in the failure of the entire system. And HDFS provide data recoverability for partial failure.
• Hadoop introduce MapReduce, which spares programmers from low-level details, like partial failure. The MapReduce framework will detect failed tasks and reschedule them automatically.
• Hadoop provide data locality. The MapReduce framework tries to collocate data with the compute nodes. Data is local, and tasks are separated with no dependence on each other. So the shared-nothing and data locality architecture can save more bandwidth and solve the complicated dependence problem

In summary, Hadoop is a great big data processing tool.

Hadoop Basic Concepts and Core Concepts

The core concepts for Hadoop are to distribute the data as it is initially stored in the system. That is data locality, individual nodes can work on data local to these nodes, and no data transfer over the network is required for initial processing.
Here are the basic concepts for Hadoop:

• Applications are written in high-level code. Developers don’t worry about network programming, temporal dependencies etc.
• Nodes talk to each other as little as possible. Developers should not write code which communicates between nodes, that is ‘Shared-Nothing’ architecture.
• Data is spread among machines in advance. Computation happens where the data is stored, wherever possible, just as near the node as possible. Data is replicated multiple times on the system for increased availability and reliability.

Hadoop High-Level Overview

Hadoop consists of two important components: HDFS and MapReduce.
HDFS is Hadoop Distributed File System, which is a distributed file system designed to store large data sets and streaming data sets on commodity hardware with high scalability, reliability and availability.

MapReduce is a distributed processing framework designed to operate on large data stored on HDFS, which provides a clean interface for developers.

A set of machines running HDFS and MapReduce is known as a Hadoop Cluster. An individual machine in a cluster is known as nodes. The nodes play different roles. There are two kind important nodes: Master Nodes and Slave Nodes.

There are 5 important daemons on these nodes.

Figure1 Hadoop High-Level Architecture

As shown in Figure, Hadoop is comprised of 5 separate daemons:

• NameNode, which holds the metadata for HDFS.
• Secondary NameNode, which performs housekeeping functions for NameNode, and isn’t a backup or hot standby for the NameNode.
• DataNode, which stores actual HDFS data blocks. In Hadoop, a large file is split into 64M or 128M blocks.
• JobTracker, which manages MapReduce jobs, distributes individual tasks to machines running.
• TaskTracker, which initiates and monitors each individual Map and Reduce tasks.

Each daemon runs on its own Java Virtual Machine (JVM), no Nodes can run 5 daemons at the same time.

Master Nodes runs the NameNode, Secondary NameNode, JobTracker daemons. And only one of each of these daemons runs on the cluster.
Slave Nodes run the DataNode and TaskTracker daemons. A slave node will run both of these daemons. All of these Slave Nodes run in parallel, each on their own part of the overall dataset locally.

Just for very small clusters, the NameNode, JobTracker and the Secondary NameNode run on a single machine. However, when there are beyond 20-30 nodes. It’s better to run each of them on individual nodes.

Hadoop Ecosystem

Hadoop has a family of related projects based on the infrastructure for distributed computing and large-scale data processing. The core projects are apache open source projects. Except for HDFS and MapReduce, some hadoop related projects are:

• Ambari, a Hadoop management and cluster monitoring system.
• Avro, a serialization system for efficient, cross-language RPC and persistent data storage.
• Pig, a data flow language and execution environment for exploring very large datasets, which runs on HDFS and MapReduce clusters.
• HBase, provide random, realtime read/write access to BigData. The project built a column-oriented database, host very large tables —- billions of rows X millions of columns. The project is based on Google’s paper BigTable: A Distributed Storage System for Structured Data.
• Hive, which is distributed data warehouse. Hive manages data stored in HDFS and provides a query language based on SQL, which is translated by runtime engine to MapReduce Job.
• Zookeeper, a distributed, highly available coordination service. It provides centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services, which make build distributed applications more efficient.
• Oozie, a service for running and scheduling workflows of Hadoop jobs, which includes MapReduce, Pig, Hive and sqoop jobs.
• Mahout, a scalable machine learning libraries based on Hadoop HDFS and MapReduce.

Resources:
Part 0 Hadoop Overview
Part 1 Hadoop HDFS Review
Part 2 Hadoop HDFS Federation
Part 3 Hadoop HDFS High Availability(HA)
Part 4 Hadoop MapReduce Overview
Part 5 Hadoop MapReduce 1 Framework
Part 6 Hadoop MapReduce 2 (YARN)
Part 7 Hadoop isn’t Silver Bullet

图论是一个重要的部分，以前数据结构课上过，没有作为考试要求，所以很不太熟悉，尤其是没有实现。考完试，无聊中重新看了看，想起以前在eBay，某帅哥突然开玩笑说DFS和BFS嘛，当然要会呀，Cyanny你会的吧，我说忘了，其实细细想起来，还真没有写过代码。In my view，没有实现过，就等于不会，今天实现了BFS和DFS，深深赞一个算导，说得明白和透彻，现在的算法书太多，这算是一本很不错的经典，厚了点，但要是能厚着脸皮看完确实受益匪浅。

广度优先搜索BFS

其算法思想简介：
1. 利用队列
2. 每一个Vertex引入三个变量
color：WHITE 表示没有访问过，GREY 表示发现，BLACK 表示完成访问
parent: 父亲
d: 表示从root到该顶点的长度
3. 为了实现方便，我采用int来标识每一个顶点，采用邻接表来表示graph
深度优先搜索可以生成深度优先树，生成单源最短路径，即从root到每一个顶点的长度是最短路径。[more…]
BFS可以采用邻接矩阵表示，其复杂度较高为O(n^2)
如果采用邻接表表示，其复杂度为O(E+V),即顶点个数+边的个数
[java]
public void BFS(int root) {
vertexes = new Vertex[n];
// Initialize each vertex,
// Each vertex has three segment: parent, d, color
for (int i = 0; i < n; i++) {
vertexes[i] = new Vertex(i);
}

Vertex rootv = vertexes[root];
rootv.d = 0;
rootv.color = Color.GREY;
queue.add(rootv);

while (!queue.isEmpty()) {
    Vertex u = queue.remove(0);
    ArrayList<Integer> list = graph.get(u.vertex);
    for (int i = 0; i < list.size(); i++) {
        Vertex temp = vertexes[list.get(i)];
        // Make sure each vertex enqueue only once
        if (temp.color == Color.WHITE) {
            temp.parent = u;
            temp.d = u.d + 1;
            temp.color = Color.GREY;
            queue.add(temp);
        }                
    }
        u.color = Color.BLACK;
    res.add(u);
}

}
[/java]
BFS Source Code

深度优先搜索DFS

广度优先搜索DFS，基本算法思想
1. 采用递归，或stack来实现
2. 每一个Vertex引入四个变量
color：WHITE 表示没有访问过，GREY 表示发现，BLACK 表示完成访问
parent: 父亲
timestamp1: 表示第一次访问该顶点的时间戳
timestamp2:表示访问结束时的时间戳
3. 为了实现方便，我采用int来标识每一个顶点，采用邻接表来表示graph

DFS采用邻接表表示Graph来实现，复杂度O(V+E), 矩阵复杂度依然不好，为O（n^2）
DFS是从多个源开始，最终会生成由多个源作为root的森林，即深度优先树（深度优先森林）。
同时引入时间戳，是为了获得DFS的进展情况，如果不需要时间戳，只是想简单地打印每一个顶点，可以不用。

以下是递归的实现方法：
[java]
public void DFS() {
int i = 0;
for (i = 0; i < n; i++) {
vertexes[i] = new Vertex(i);
}
for (i = 0; i < n; i++) {
Vertex u = vertexes[i];
if (u.color == Color.WHITE) {
visitDFS(u);
}
}
}

private void visitDFS(Vertex u) {
    res.add(u);
    u.color = Color.GREY;
    timer++;
    u.timestamp1 = timer;
    ArrayList<Integer> adjList = graph.get(u.vertex);
    for (int i = 0; i < adjList.size(); i++) {
        Vertex v = vertexes[adjList.get(i)];
        if (v.color == Color.WHITE) {
            v.parent = u;
            visitDFS(v);
        }
    }
    u.color = Color.BLACK;
    timer++;
    u.timestamp2 = timer;
}

[/java]

以下是采用栈的实现方法改写 “visitDFS”：
[java]
/**
* DFS with iterative method
* Make use of stack
* @param u
*/
private void visitDFSIterative(Vertex u) {
res.add(u);
u.color = Color.GREY;
timer++;
u.timestamp1 = timer;
stack.add(u);
while(!stack.isEmpty()) {
Vertex v = stack.remove(stack.size() - 1);
ArrayList<Integer> adjList = graph.get(v.vertex);
for (int i = 0; i < adjList.size(); i++) {
Vertex temp = vertexes[adjList.get(i)];
if (temp.color == Color.WHITE) {
temp.parent = v;
temp.color = Color.GREY;
timer++;
temp.timestamp1 = timer;
res.add(temp);
stack.add(temp);
}
}
v.color = Color.BLACK;
timer++;
v.timestamp2 = timer;
}
u.color = Color.BLACK;
timer++;
u.timestamp2 = timer;
}
[/java]

DFS Source Code

最终发现，起始实现起来代码不多，重在想法。

9. 数据库设计

9.1.基本概念

1.数据库与文件系统的区别
传统的文件系统：是扁平文件，无结构的文件，存储简单地数据，读取速度快，存储形式单一；存在数据冗余，更新时间长，不一致性，安全性的问题，冗余会带来插入、更新、删除异常。
数据库系统：是堆文件，采用数据表存储，数据存放随机且没有特定的顺序，每一个表需要提供主键；数据库提供索引功能；可以通过范式来保证数据的一致性；有事务处理功能,ACID；可以避免插入、更新、和删除异常；提供安全功能。[more…]

2.数据库设计的目标：
a)能向用户提供数据
b)准确性，一致性，完整性
c)有效的存储数据以及有效的更新和检索
d)有目的的检索数据，获取的数据要有利于管理和决策。

3.有效性目标
a)保证数据能被各种应用程序的用户共享。
b)维护数据的准确性，一致性，完整性
c)确保当前的和未来的应用程序所需的所有数据能立即可用
d)允许数据库随用户需求的增加而不断演进。
e)允许用户建立自己的数据视图，而不用关心数据的实际存储方式。

4.ERD图,要会画，可以看书中的例子
实体：任何由某人为手机数据而选择的对象或事件叫做实体。包括：一般实体，关联实体，属性实体。
关系：1对1，1对多，多对多
属性：实体的特征

5.键的类型：基于模式而不基于实例
a)主键：唯一标识一条记录
b)候选键：一个或一组可当作主键使用的键
c)辅助键：不能唯一标识一条记录，可以唯一，也可以标识多重记录
d)链接键(组合键)：可以选择两个或多个数据组成一个键
e)外键：一个属性，它是另外一个表的键

9.2.规范化

合理规范化的模型可应对需求变更，规范化数据重复降至最少.
1.第一范式1NF：数据原子性，每一列只有单值属性

2.第二范式2NF：没有部分依赖，每一个属性不能依赖主键的部分
如 (学号, 课程名称) → (姓名, 年龄, 成绩, 学分) ，不符合2NF
因为 (课程名称) –> (学分)，(学号)->(姓名，年龄)，存在部分依赖
此时存在数据冗余，插入异常，删除异常，更新异常

分解为：学生：Student(学号, 姓名, 年龄)；
Course(课程名称, 学分)
SelectCourse(学号, 课程名称, 成绩)

3.第三范式3NF：没有传递依赖，不存在非主属性依赖于非主属性
例如： (学号) → (姓名, 年龄, 所在学院, 学院地点, 学院电话),符合2NF， 但不符合3NF，因为 (所在学院) -> (学院地点, 学院电话)是传递依赖，分解为：
(学号) → (姓名, 年龄, 所在学院)
(所在学院) -> (学院地点, 学院电话)

4.BCNF(Boyce-Codd Normaml Form): nothing but the key, 首先要满足3NF，在此基础上在候选键之间不能有传递依赖。
如：(仓库ID, 存储物品ID) →(管理员ID, 数量)
　　 (管理员ID, 存储物品ID) → (仓库ID, 数量)
(仓库ID, 存储物品ID)和(管理员ID, 存储物品ID)都是候选关键字，表中的唯一非关键字段为数量，符合3NF。但是，由于存在如下决定关系：
　　 (仓库ID) → (管理员ID) 　 (管理员ID) → (仓库ID)
候选键之间有依赖，不符合BCNF。

分解为：
(仓库ID) –> (存储物品ID，数量)
(仓库ID) -> (管理员ID)
BCNF分解过细，导致查询连接性能低，所以一般3NF就可以了。

数据库范式详解

9.3.3NF无损连接分解方法

分解要做到无损连接，依赖保持。
考虑 关系 R= {ABCDEFGHI}
H -> GD E->D HD->CE BD -> A
1. Right reduced
H -> G
H->D
E->D
HD->C
HD->E
BD->A

2. Left reduced
H->G
H->D
E->D
H->C
H->E
BD->A

3. Find minimal cover
尝试删除一个依赖，然后验证是否无损和依赖保持，直到不能再删除
可以删除H->D,就不能再删了
H->G
E->D
H->C
H->E
BD->A
Minimal cover R’={H->GCE, E-D, BD->A}

4. 补充没有的依赖
我们发现I还没有在R’中，因此，提取出R’中的键HB构造关系HB->I

5. 最终结果
R = { H->GCE, E-D, BD->A , HB->I}

9.4.主文件/数据库关系设计指导原则

1. 指导原则
每个单独的数据实体应创建一个主数据表。
一个特定的数据字段只应出现在一个主文件中。
每个数据表支持CRUD操作

2. 完整性约束
实体完整性：主键不能有空值，唯一键可以有空值
引用完整性：一对多关系中，“一端”是父表，“多端”是子表，子表的外键必须在父表中有匹配记录；父表记录只在没有子表记录关联时才能删除；父表主键更新，要进行级联更新，即对应的子表外键要更新。
域完整性：对数据进行有效性检验，如数据必须大于0

3. 异常
数据冗余：可以通过3NF解决
插入异常：如果主键重复，或未知，导致插入异常，因为违反实体完整性。
删除异常：删除导致相关数据丢失导致
更新异常：更新导致不一致性。

4. 检索和显示数据的步骤
1)从数据库中选择一个关系

2)连接两个关系: join(inner join, outer join, left join, right join)
a)inner join： A join B 只有交集会出现在结果中
b)left (outer) join: A 中与B没有匹配的记录会保留
c)right(outer) join: B中与A没有匹配的会保留
d)outer join, 又叫full outer join = left join 与right join的并集，所有匹配和未匹配的记录都有

3)从关系中投影出列
4)从关系中选择所需的行
5)导出新的属性
6)行索引或排序
7)计算总计值和进行性能测量
8)显示数据

9.5.反规范化

1. 原因
规范化的方式可以减少数据冗余，但查询速度会下降，一定的冗余，可以提升查询响应速度，避免重复引用检查表。
2. 反规范化的6种方法
1)合并1：1关系
2)部分合并1：关系，不复制外关键字而复制非key的常用的字段
3)在1：关系中复制FK（外关键字），减少join的表数量，将另一个表的主键复制变成外键。
4)在：关系中复制属性，避免3表join
5)引入重复组，将多值属性写在主表里：例如user表中多个电话号码的列，常用地址和常用电话
6)为了避免查询和更新这两个不可调和的矛盾，可以将更新和查询放在两张表中，从工作表提取出查询表，专门用于查询。这个方法演化成了数据仓库。这个方法只适用于查询的实时性要求不高的情况

10. 设计准确的数据输入规程

数据输入准确性的目标：
•为数据创建有意义的代码
•设计有效的数据获取方法
•保证数据的完整性和有效性
•通过有效性检查确保数据的质量

10.1 有效的编码

10.1.1.基本概念

1.优点：
a)提高数据处理效率
b)有助于数据的排序
c)节约内存和存储空间
d)提高数据输入的准确性和效率
e)特定类型的编码允许我们按特定的方式处理数据

2.目的
a)记录某些事物
b)分类信息
c)隐蔽信息
d)展示信息
e)请求相应地处理

3.编码的一般指导原则
a)保持代码简洁，短代码比长代码更容易输入和记忆
b)保持代码稳定，不应虽每次接收新数据而变化
c)代码要独一无二
d)允许排序代码
e)避免使人迷惑的代码
f)保持代码统一
g)允许修改代码
h)代码要有意义

10.1.2.编码的类型

1.记录某些事物
a)简单地顺序码
•优点：减少指派重复数字的可能性；让使用者估计出订单合适收到
•适用于：作业按顺序处理，需要知道数据项输入系统的顺序，需要知道事件的发生顺序。
•缺点：容易泄露商业信息，泄露当前已经指派了多少编码

b)字母衍生码
•例如：名字的编码： 取前2个辅音字母+名字长度+一个随机数
•例如编码女装：考虑品牌，类别，产地，生产日期，款号，尺码，颜色，价格
•常用于标识一个账号，邮寄地址标签
•注意：避免重复，分布要均匀
•缺点：如果采用名字的前三个辅音字母，当辅音字母少于3个，就会生成“RXX”这样的类型； 如果一些数据发生变化，如名字或地址变化，就会改变字母衍生码，而改变文件中的主键

2.分类信息
a)分类码
•目的：将一组具有特殊信息的数据从其他数据中区分出来，可以由单个字母或数字组成。是描述人物、位置、事物或事件的一种简写形式
•例如：计算所得税，分类有支付利息，医药费，税，捐款，应付款，生活用品支出，给每一个分类指派一个字母；
•使用单个字母标识分类可能会存在扩展瓶颈，可使用两个以上的字母，如计算机中的快捷键。

b)块顺序码
•是顺序码的扩展，对数据分类，对每一个分类分配一个编码范围，在该类别的项目按顺序编码
•例如浏览器分配100999， 数据库 200299
•优点：根据普通的特征对数据分类，还能简单地为下一个需要标识的项目（在同一块）指派一个可用的数字代码

3.隐藏信息
密码，隐藏信息，如医药处方，凯撒密码对称加密，Hash密码单向加密

4.展示信息：为用户展示信息，使数据输入更有意义
a)有效数字集编码
•例如衣服采用有效数字集描述产品信息，“414-219-19-12:表示浅褐色冬季外套，款式219，尺码12”
•优点：让员工方便的定位产品类别；查询效率高；有助于销售

b)助记码
•帮助记忆，结合字母和符号，醒目而又清晰的编码产品，例如国家简称
c)Unicode：显示我们不能输入和看到的字符， 国际标准组织ISO定义Unicode字符集，包括所有标准语言字符，还有65535个空位

5.请求相应的处理
a)功能码：用简短的数字或字母来标识一个计算机对数据执行的功能，通常采用顺序码或助记码的形式
优点：执行功能只需输入功能码，提高输入效率

10.2.快速而高效的数据获取

1.决定要获取什么样的数据
如果输入无用，输出也会无用
输入的数据分类：随每个事务而改变的数据；能简明的将正在处理的项目与所有其他项目区分出来的数据

2.让计算机完成数据处理：处理重复的任务，如记录事务时间，根据输入计算新值，随时保存和检索数据

3.减少瓶颈和减少额外输入步骤：步骤越少，引入错误的机会就越少

4.选择有效的数据输入方法
a)键盘
b)扫描仪
c)视频，音频
d)磁性墨水
e)标记识别表单：如答题纸，但缺点是用户可能会一时大意填图出错
f)条形码：准确度高
g)RFID：射频识别技术

资源：
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4

6. 设计有效的输出

6.1.输出设计目标

1.设计满足特定用途或组织目标的输出
输出要面向用户，考虑用户的年龄、收入和文化层次。

2.制作对用户有意义的输出
设计要满足特定用户的需求，决定什么是内容，什么是途径。
考虑输出的时间和地点 [more…]

3.交付合适数量的输出
决定要给用户多少信息，根据对用户的调查来决定，根据对象的重要性，数量和个数来决定
如：搜索后的结果

4.合理分配输出，确保重要信息是必不可少的
如商店的门户网站，分类信息要展示
对必不可少的信息进行版本化，如计算器的科学性和普通型

5.按时提供输出
In-Time 按时，及时的展现，考虑输出的时效性
如每年南大的主页在高考时很重要
如滴滴打车，采用语音输出

6.选择最有效的输出方式：报表，屏幕输出，音频或视频输出。

6.2.选择输出技术时需要考虑

1)谁将使用，看到输出。
2)多少人需要输出
3)哪里需要输出，如配送部门和后勤部门
4)输出的目的
5)输出的速度是多少
6)访问输出的频率如何
7)输出将必须存储多长时间
8)产生、存储和分发输出必须遵循的特殊规则是什么
9)维护和供应的最初与后续的成本是什么
10)输出技术的环境需求是什么：易接近性、噪声吸收、温度控制、设备空间、电缆架设以及WiFi发射机的接近程度。 例如：打印输出噪声很大。

6.3.常见的输出技术

补充如下：
1. 打印机输出：如报表行程单、化验单、信用卡账单、财务单，具有持久性，需要考虑浪费纸张的成本，噪声，采用合适的表格形式
2. 视频输出：
补充静态的打印输出。
远程协作，将那些不能经常见面的人联系在一起
教学，帮助，培训视频
记录当前事件，方便以后的输出
保存一个重要情节，收藏，存档

3. 动画输出：增强web站点的演示效果；比抽象的图像带来更好地决策支持。
4.电子邮件输出：可以用于私密信息。
5. 输出技术两种分类：
推技术：向用户推送信息，如推送流量统计，可以采用短信或电子邮件的方式。
拉技术：用户主动发起请求数据，如web上点击链接

6.4.避免输出的偏差

1.偏差的来源
a)信息排序的方式
b)可接受的边界值引入的偏差
c)使用图形引入的偏差

2.如何避免偏差
a)明确偏差来源
b)在测试Web文档的外观过程中，设计交互式输出，让各种用户参与测试，并使用各种不同的系统配置测试输出。
c)让用户参与输出设计，使它们认识到输出信息中可能存在的偏差
d)创建灵活的输出，使得用户能修改边界值和范围。
e)训练用户依靠多种输出对系统输出执行“逼真测试”

6.5.印制报表的设计原则

1.确定报表设计约定
设计表单时要遵循的约定包括：每个位置上出现的数据类型，表单大小，以及表明连续表上数据延续部分的方式。
2.纸张质量、类型和大小
3.功能、风格和美观程度
4.报表的功能属性：标题、页码、准备日期、列标题、相关数据项的集合、控制分割行的使用

6.6.设计屏幕输出

1.原则
a)保持屏幕简单
b)保持屏幕显示的一致性
c)方便用户在屏幕间移动
d)创建吸引人的屏幕

2.在屏幕输出时使用图形要考虑
a)图形的用途
b)需要显示什么样的数据
c)读者对象
d)不同图形输出对读者的影响

3.选择仪表盘输出时考虑：
a)确保数据有上下文
b)显示合理的汇总的精度
c)选择合适的工作指标进行显示
d)公正地表现数据
e)选择正确的图表样式进行显示
f)使用精心设计的显示媒体：大小、图片、颜色、标签
g)限制项目类型的多样性
h)突出显示重要数据
i)将数据按有意义的小组进行编排
j)保持屏幕简洁
k)使整个仪表板保持在一个单独的屏幕上

4.Wedget和Gadeget输出
a)窗口小部件，可以个性化桌面
b)证券报价机、天气预报、RSS反馈可以采用widget
c)但widget会分散用户对系统支持的任务的注意力。

7.设计有效的输入

7.1.对输入的质量要求

1.输入的质量
1)有效性：输入表单、输入屏幕和Web上的输入窗体在信息系统中服务于具体的目的。
2)准确性：所作出的设计能保证用户准确输入数据。
3)易用性：表单和屏幕简单易懂
4)一致性：所有输入窗体，在不同的程序中按类似的方式组织数据。
5)简单性：设计简洁，让用户集中注意力输入数据。
6)有吸引力：精心设计表单，让用户喜欢

2.输入还需要保证
完整性
输入顺序要合理：从主体到客体，重要到次要
如简历：先基本信息，再个人获奖，个人工作经历

7.2.良好的表单设计(纸质表单)

1.设计原则
a)使表单容易填写
b)满足用户的需求
c)保证输入的完整性，准确性
d)有吸引力

2.使表单容易填写
a)表单流：从左到右，从上到下
b)表单的7个部分
i.标题
ii.标识和访问控制
iii.用法说明
iv.主体
v.签名和确认
vi.总结
vii.评论

c)加标题：行标题，行下标题，加框标题，垂直选择标记，水平选择标记。
标题要有相关注释。
标题风格保持一致。

3.满足用户的需求
创建表单目的：记录、处理、保存和获取商业所需信息。

4.确保完整性和输入的准确性
这样可以让与收集数据相关的错误率大幅度降低。

5.表单设计要有吸引力
按预期顺序组织信息：姓名、街道地址、城市、州(省)、邮政编码
吸引力来自于正确的表单布局和流向。
字体样式和线条粗细也是有用的设计元素。

6.表单设计软件：如scansoft

7.业务表单控制：
a)确保表单的输入是为了达到特定的需求，并且该需求是组织功能不可分割的。
b)避免重复信息，避免使用重复表单。
c)设计高效的表单。
d)以尽可能低的成本制作表单

7.3 良好的Web屏幕和Web窗体设计

7.3.1.屏幕设计原则

1.电子、web表单与静态表单的区别：
有光标，指示当前的数据输入位置
可以在上下文加入相关帮助

2.设计原则
a)保持简洁
b)一致性
c)易于用户在屏幕间移动
d)创建有吸引力和满意的屏幕

3.保持屏幕的简洁
屏幕输出的三个部分：
•标题：文件名称、下拉菜单和执行某些任务的图标
•主体：输入数据，从左到右，从上到下
•评论和用法说明
另一种保持简洁的方法是：使用上下文相关帮助和其他弹出窗口，利用超链接

4.保持屏幕一致性：
a)与相关的纸质表单保持一致性
b)每次访问新屏幕时信息出现在同一个区域
c)逻辑上不可分割的信息始终组织在一起

5.易于用户在屏幕间移动
a)易于用户从在不用web页之间移动
b)“三次单击”规则：用户应能在三次单击鼠标或按键之内，转到他们所需的屏幕。
c)使用向下箭头滚动屏幕
d)上下文相关的弹出窗口
e)屏幕对话

6.设计有吸引力的屏幕
a)足够的留白，让用户集中注意力到数据上
b)使用逻辑流计划屏幕信息，按用户处理问题的方式组织屏幕信息，让他们容易找到所需信息
c)将信息划分为3个部分，参见简洁性，划分遵循一致性原则
d)采用粗细不同的线条划分不同的类目
e)反转影像，闪烁光标，但要慎用。
f)使用不同的字体

7.屏幕设计中使用图标
a)每个应用程序使用的图标控制在20个之内
b)相关图标要一起出现，保持连续性和易懂性
c)图标含义越丰富，越有用。

7.3.2.GUI元素的设计

1.文本框：大小要能容纳所有的字符。要有标题。
2.复选框：标签放在复选框的右边；如果超过10个，要将他们组成一个组，并框起来。
3.单选按钮：选项文本放在右边；如果选项按钮超过6个，考虑下拉菜单。
4.下拉菜单和列表框
5.滑动块按钮和旋转按钮
6.图像映射
7.文本区
8.消息框
9.命令按钮

10.表单控件和数值：GUI界面包括的每个控件必须有某种方法来存储与控件相关的数据。 Web页面上，可以采用名称和值对来实现。 每个Web表单控件获取数值的方法是不同的。
11.隐藏字段：表单中，对用户不可见，但需发送到服务器的数值
12.事件响应图：当GUI交互很复杂时，可以采用事件响应图列出各种可能发生的事件，概要的建立商业事件和响应的模型。
13.动态web网页：根据用户操作改变网页内容，基于JavaScript，可以用来显示临时的信息。但对需要加密，提供安全保护的数据，不要采用动态web的形式。而缺点是用户禁用JavaScript后，网页不可用。
14.Ajax，异步更新，web运行更快，更流畅。缺点是JavaScript必须启用，安全性问题。

15.选项卡控件对话框设计原则：
a)为每个独特的特性创建一个分离的选项卡
b)将最常用的选项卡放在前面，并首先显示
c)可以考虑在设计的选项卡控件对话框中包含三个基本按钮：OK，Cancel，Help

16.Web中使用色彩
a)色彩搭配要协调：对比前景和背景，突出表单上重要字段，显示错误。

b)容易辨认的搭配：前景明亮，背景用不太明亮的。
i.黑底文字在黄色背景上
ii.绿色文字在白色背景上
iii.蓝色文字在白色背景上
iv.白色的文字在蓝色的背景上
v.黄色的文字在黑色的背景上

c)色彩不宜超过4种，对于有经验的用户，不要超过7种。

7.4.内联网和互联网页设计

指导原则
1)提供清楚的用法说明
2)演示窗体的逻辑填写顺序，特别是因为用户滚动而看不到的部分
3)为特殊功能增加窗体的吸引力，使用各种文本框，按钮，下拉菜单、复选框和单选按钮
4)如果我们不能确定用户响应某个问题时将在字段中输入多少个字符，或者不能确定用户使用什么语言、结构或窗体输入数据，提供一个可滚动的文本框
5)为每个Web输入窗体准备两个基本按钮：Submit 和 Clear Form
6)如果窗体很长，且用户进行滚动之外别无它法，那么最好将窗体分成几个简单地窗体，放在不同的网页上
7)创建一个错误反馈屏幕
对于电子商务应用程序还需要达到目标：阐明有关信任、隐私和退货方面公司的任务和价值；建立高效的事务处理过程；建立良好的客户关系。

8. HCI人机交互

8.1.基本概念

1.HCI是指确保系统的功能和可用性，提供有效的用户交互与支持，以及增强用户快乐体验。总体目标是实现组织和个人用户的效率和有效性。
2.主要策略：不断引出用户对原型设计（屏幕、表单、界面等）的使用经验反馈，根据修改建议提炼设计，然后再让用户试用，直到用户满意，最后由分析员固定下来。面谈就是一种获得HCI反馈的重要方式。
3.技术接受模型：感知有用性和感知易用性
4.可用性：包括产品使用的有效性、效率和在特定环境下使用的满意度、用户界面交互，开发产品的过程，组织应用以用户为中心的设计的能力
5.HCI设计中考虑用户的身体因素：视觉，听觉，触觉，考虑人的缺陷、残障和意图。

6.良好的HCI进行系统设计的指导原则
1)界面与任务相匹配
2)提高界面效率
3)提供适当的反馈
4)生成有用的查询
5)提高工作者的效率

7.评价UI的原则
1)较短的学习时间
2)用户不用多加考虑或者不用查阅手册和帮助菜单，就可以输入指令
3)界面应该与实际功能“无缝”连接，确保出出错概率小
4)用户和系统出错后恢复时间尽可能短
5)偶尔使用的用户重新学习系统时要尽可能快
6)界面提供信息准确，界面友好

8.2.对话设计的指导原则

1.交流要让用户和计算机都能理解，意义明确

2.最小化用户的行为，减少不必要的操作，可以采用以下方式：
1)输入时用代码代替词组
2)只输入系统中没有存储的数据
3)提供缺省信息
4)提供help信息，不要让用户乱操作
5)提供符合常规的快捷键

3.操作的规范化和一致性
1)界面的标题、日期、时间、操作提示和反馈信息固定在相同位置
2)使用相同的键位或者菜单退出程序
3)采用一致的方法取消事务
4)用标准化的方法获得帮助，如F1
5)屏幕采用标准化的色彩
6)GUI中使用标准化的图标
7)网站中术语要一致
8)提供一致的方法实现对话导航
9)文字大小、颜色和对齐方式保持一致

8.3.用户界面类型

1.自然语言界面：实现复杂，如ask.com自然语言查询，对资源有特殊要求
2.问答式界面，对话框，适用于不熟悉特定应用或不了解某个主体的用户

3.菜单：
优点：分类显示，不杂乱；减少界面无关信息；嵌套菜单可以提高用户的操作速度。
指导原则：
•层次和分类要清晰，不能混淆，
•主菜总是单停留在导航栏
•子菜单的层数不要超过3层
•下拉菜单按功能特征分区或者分组
•元素不要太拥挤，不重复，不遗漏，先主后次。
•选中主菜单的词后，弹出下拉菜单。
•不可用的选项灰色表示

4.Form表单
用于输入和输出
•原则：
屏幕窗体要说明应该输入什么信息，以及在哪里输出。
在空白字段中输入数据时，输入内容应该反白或闪烁显示。
为简化窗体数据的输入，可预先给出默认值。
•优点：打印出的表单内容是极好的文档
•缺点：让有经验的用户厌烦，总希望找到一种更有效的数据输入方法。

5.命令行:专业、学习难

6.对话框
采用标准的操作，保证一致性，交流要有意义，提供最少的操作交互和行为。

7.其他类型的用户界面
指示笔、触摸屏、语音识别与合成、触摸屏
语音交互的优点：让用户能腾出手来完成其他事项的同时，如驾驶，可以极大的提高数据输入速度。为有视觉或行为障碍的用户提供方便。

8.4.为用户提供反馈

1.反馈类型
a)确认接受了输入数据
b)确认输入格式正确

c)提示输入格式不正确
反馈可以是新的界面、消息框、音频反馈
反馈要保证效率和准确性

d)解释系统运行中的延迟
e)确认请求完成
f)提示用户请求无法完成
g)为用户提供更详细的反馈

2.在系统设计中包含反馈
a)提供各种帮助选项，F1，
b)下拉菜单帮助
c)鼠标悬停的提示文本
d)帮助向导
e)帮助热线

8.5.电子商务网站的设计原则

1.在网站上采用各种方法从客户处获得反馈
在用户启动电子邮件程序的同时，自动把公司的邮件地址放在“收件人”处
添加反馈按钮，点击后打开信息模板

2.采用4种方法提供一次点击的导航，以确保用户容易地在网站中导航，并易于返回原来的网页。
1)建立卷滚菜单
2)在主页上按分层关系建立网站链接集，显示关键主题框架。
3)把网站地图放在主页上，并突出到该地图的链接，提高导航效率。
4)在网站内每一个页面上设置导航条，重复首页上的条目。

资源：
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4

4. 分析：使用数据流图

4.1.数据流图功能和优点

概念化数据在整个组织是如何流动的，数据经历的过程和变换，以及输出。
优点：
(1) 不必过早着手系统和技术的实现。
(2) 进一步了解系统和子系统的相互关系。
(3) 通过数据流图与用户交流当前系统的知识。
(4) 更好地了解业务，分析建议的系统以确定是否定义了必要的数据和过程。[more…]

4.2.数据流图的图例规范

1. 实体的命名：名词
2. 数据流命名：名词
3. 过程命名
在上下文图中，赋予整个系统的名称， 如“选课系统”
命名子系统时，使用诸如“预定子系统”， “Web用户执行系统”
具体过程命名：动词+形容词+名词 “计算净工资”，每一个过程要有一个唯一编号，指出它在图中的层次。

4.3.开发数据流图步骤

1. 步骤
1)制定一个业务活动列表：实体，数据流，过程，数据存储
2)创建上下文图，外部实体+输入+输出+系统，没有过程和数据存储
3)0层图：分解系统，展示高层的过程和数据存储，过程一般不超过9个，为避免数据流线交叉，同一个实体和数据存储可以出现多次。
4)画0层图中每个过程的子图
注意编号与父过程相同
纵向平衡——不能有父过程没有的输入和输出。
子图中通常不显示实体，显示接口数据流。
可以有父过程中没有显示的数据存储。
5)检查错误：编号正确，命名正确，输入输出清晰，没有back hole, 没有miracle
6)根据逻辑数据流图，开发物理数据流图：通过名字描述真实地文件和报表的物理存储，增加控制以指出合适过程完成或发生错误。
7)分割物理数据流图。

2. 注意点

1. 图例和标识的准确性
2. 数据流：不能从实体到实体，不能存储到存储，可以从实体到过程，过程到过程，过程到存储
3. 数据流图的层次性
4. 尽量不要有线性流，即一个输入和输出的过程，出现通常是遗漏了数据流，一个过程输入和输出总数在>=4个以上最好。
5. 用户要能理解

4.4 如何向用户解释数据流图

1. 数据流图的标记要具体而有意义、
2.可以通过举例，类比和问询，让用户了解DFD的原理
3.每个DFD的过程控制在9个以内，太大的图，则要分解，保证在一页纸内
4.结合表格和图表向用户解释

4.5.逻辑数据流图 vs 物理数据流图

1. 二者的区别
   

2)逻辑数据流图优势
a)更好地与用户交流
b)系统更稳定
c)更好地了解业务
d)灵活、更易维护
e)消除冗余，更容易创建物理模型

3)物理数据流图优势
a)澄清哪些过程是手工的，哪些是自动的
b)更详细的描述过程
c)标识临时数据存储
d)指定真实地文件名和打印输出名
e)增加确保正确地完成过程的控制。
物理数据流图创建方法：事件建模法，用例法.

5. 使用数据字典分析系统

5.1.数据字典的基本概念

1.数据字典定义
是一种关于数据的数据参考书，指导系统的分析与设计，包括数据流，数据结构，数据元素和数据存储。

2.数据字典的必要性
a)作为数据的记录文档
b)消除冗余，保证数据的一致性
c)验证DFD的完备性和准确性
d)为开发界面和报表提供切入点
e)找出数据流图中过程的逻辑
f)创建XML

3.DFD与数据字典的关系

5.2 数据流的描述

通过DFD确定系统的输入和输出，对每个数据流描述如下，具体实例可以看书。
1)ID：可选标识符
2)数据流名称
3)数据流描述
4)数据流来源
5)数据流目标
6)数据流类型：文件、界面、报表、表格或内部数据(中间的临时数据)
7)包含的数据结构
8)单位时间的流量
9)备注

5.3.数据结构描述

1.描述
1)= 表示组成
2)+ 表示“和”
3){} 表示重复元素，一定有至少一个 1n，可以包含固定重复次数，或上限与下限
4)[] “非此即彼”，互斥的选择
5)() 表示可选元素 01

2.逻辑数据结构和物理数据结构
逻辑数据结构是业务上，用户看到的数据。物理数据结构是软件实现所需要的数据。
物理数据结构需要增加：
1)键字段，唯一标识一条记录
2)标识主记录的状态代码，诸如一个雇员当前被雇佣或否。
3)如果一个文件包含不同的记录类型，则可以用交易码标识记录的类型。例如，包含返还项的记录和支付记录的信用文件。
4)重复组数据项，包含该组中有多少个数据项的计数。
5)重复组中数据项多少的限制
6)客户访问一个安全Web站点的密码。

5.4 数据元素描述

1)ID, 可选的
2)元素名称
3)别名
4)简短描述
5)是基本元素还是派生元素

6)元素长度：
对于数值金额的长度，给出最大数额。
名称和地址，给出合适的长度
对于其他字段，参照历史数据

7)数据类型：数值，日志，字母，varchar，字符
8)如果用特殊编码符号表明应当如何表示数据，则应包含输入和输出的格式。

9)验证标准，保证数据的精确性，对于离散或连续的数据有以下标准
a)某个值范围适合包含连续数据，如GPA 0.00~4.00
b)如果数据式离散的，则指出一组值
c)如果值的列表是泛指的，则可以采用一个代码表
d)对于键或者索引元素，通常包含一个校验位

10)提供某些元素的默认值
11)备注区域

5.5.数据存储描述

1)ID，必须有
2)数据存储名
3)文件的别名
4)简短描述
5)文件类型：人工文件或计算机文件
6)如果是计算机文件，则文件格式指明是数据库文件，还是传统的平面文件
7)文件上记录的最大记录数和平均记录数
8)文件或数据名指定的文件名(如果已知)
9)数据结构应使用数据字典中的名字，提供与此数据存储的元素的连接

5.6.创建数据字典

1.先创建DFD，自顶向下开发数据字典和数据流图。可以为每一个层次的DFD创建数据字典。

子数据流图上的数据流名称，包含在父过程上的数据流的元素或结构化记录中

2.分析输入输出
输入输出分析表包括：
1)输入或输出的描述名
2)负责进一步澄清细节、设计反馈和最后核准的用户联系信息
3)输入数据还是输出数据
4)数据流的格式。逻辑DFD，可以处于未确定
5)表明报表上或者界面上的数据顺序的元素
6)一个元素列表，包括元素的名称、长度，是基本元素还是派生元素，编辑标准。

3.开发数据存储
确定永久信息或临时信息。

5.7.使用数据字典

数据字典可以用来创建界面、报表和表单
1.使用数据字典产生计算机语言时要考虑
1)输出数据流中的基本元素必须出现在产生该输出数据流过程的输入数据流中。基本元素由键盘输入，而不由某一个过程创建
2)派生元素必须由过程创建，并且至少应当由一个不是该元素自身为输入的过程输出
3)输入或者输出某个数据存储的数据流中的元素，必须包含在该数据存储中

2.使用数据字典可以创建XML文档
XML是一种可用来在企业中交换数据的语言，是一种对数据进行定义、排序、过滤并把它转换成一种每个人都可以使用的统一数据语言的方法。

资源：
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4

系统分析与设计，感觉上是一个需求和软工的大汇总，不温不火，方面很多，只能算是对软件工程的overview。

1.信息收集交互式方法

交互式信息收集有：面谈、联合应用程序设计JAD和调查问卷.

1.1 面谈

1. 面谈的概念
面谈是一种面对面的会谈，目的明确，一般采用问答形式。面谈时，需要获取面谈对象的观点，他们对系统当前状态、组织和个人目标、以及非正规过程的感受。[more…]

• 调查面谈对象的观点。
• 尽力获取面谈对象的感受。
• 目标是尽力收集重要信息，组织的目标。
• 面谈也是考察HCI问题的宝贵时机。
• *2.面谈的5各步骤**

1)阅读背景材料：与面谈对象建立共同词汇
2)确定面谈目标：问题中应该有4-6个与HCI、信息处理和决策行为有关。
3)决定面谈对象：按层次和影响力选择谈话对象。
4)准备面谈对象：打电话或者邮件提前预约
5)决定问题的类型和结构：金字塔结构、漏斗结构或者菱形的结构

3.问题类型
1)开放式问题
优点：
•让用户谈话自在
•可以收集面谈对象使用的词汇，这能反映其教育背景、价值标准、态度和信念
•提供丰富的细节，广度
•对尚未的进一步的提问方法有启迪作用。
•让面谈对象更感兴趣
•允许更多的自发性
•会见者更容易措辞
•在会见者没有准备的紧要关头采用这种类型
缺点：
•容易不切题，产生太多不相干的细节
•时间冗长，花费大量时间才能获得有用的信息
•可能会让用户觉得你没有准备，不够专业
•留下不好的印象，用户会觉得你在做没有实际意义的调查
•后期数据分析较难

2)封闭式问题
优点
•有针对性，切中要点
•能获得准确、贴切的数据
•时间上可控，节省时间，可以快速探讨大范围问题。
•保持对面谈的控制权
•数据分析容易
缺点：
•让用户厌烦
•得不到丰富的细节，失去主要思想
•不能建立和面谈对象友好的关系

4.问题结构
1)金字塔：先封闭后开放，先具体后一般化，用于用户需要预热，开始拘谨的情况
2)漏斗：先一般后具体，适用用户一开始就有激情的情况
3)菱形：具体——一般——具体，缺点是费时，优点是：具体的问题开始为面谈做好铺垫，再问一般化问题可以收集丰富的信息，再用具体的问题收尾，为面谈提供了结束的时机。

1.2 JAD联合应用程序设计

由IBM开发，一种一对多的面谈方法，目的是节省个人面谈所需的时间，减少成本；改善信息需求评估结果的质量；通过多方一起参加的过程，获得用户对新信息系统的更多的认可。
1.条件
•用户时间有限，一对一面谈不行
•公司文化允许不同层次的职员间联合问题求解
•用户想有点新东西，创新意愿强，而一对一面谈难以得到统一的意见
•组织允许关键职员离职24天
2.涉众：
分析员、用户、主管等，
一个沟通能力好的主持人
812位不同阶层的用户
需要有两名置身事外的观察员，保证JAD的进行。
3.召开会议地点：一般式24天的脱产会议，在远离单位的舒服环境下
4.优点
•比面谈节省时间
•联合协作，可以实现快速软件开发。
•改善信息系统所有权的可能性。让用户早日参与系统，获得用户反馈
•创造性的开发设计，类似头脑风暴
5.缺点
•要求所有参与者抽出大块时间，24天
•任何一方准备不充分，或者后续报告和规范文档没有完成，最终得到的设计会不尽人意
•可能还没有充分发展必须得组织技能和组织文化，组织可能还不支持JAD

1.3 问卷调查

问卷调查是一种信息收集技术，它允许系统分析员研究组织中若干关键人物的态度、信念、行为和特征，而这些关键人物可能会受到当前建议系统的影响。
1.使用条件
•组织成员分布广泛
•系统项目涉及许多人
•推荐方案之前必须做探索性工作，希望在确定系统项目具体方向之前评估总体意见。
•希望在后续的面谈中标识并解决当前系统的所有问题。

2.问题类型
1)开放式问题：
要估计开发式问题答复的种类，不能太宽泛
开放式问题适合想了解公司成员对系统的产品方面，或对系统的过程方面的看法的情况，如果不能有效的列出所有可能的答复，考虑开发式问题。
优点：探索性好，广度和深度广，准备问题容易
缺点：完成速度慢，分析数据难
2)封闭式问题
如果要调查大量人员的样本，采用封闭式，数据好统计。
如果能有效的列出问题可能的相互排斥的所有答复，采用封闭式问题。
优点：完成速度快，分析数据容易
缺点：广度和深度窄，准备问题不容易，探索性低

3.措辞的选择
使用一致的和企业业务相关的术语
•保持措辞简练
•使用明确字眼，但避免过度明确问题，如收入等敏感信息
•保持问题简短
•不要选择低水平的语言，不要用高人一等的口气
•避免措辞的偏差
•向合适的人发放问卷，不要采用太多专业知识
•确保问题中涉及的技术的准确
•使用软件检验阅读水平是否合适回答者

4.在问题中的标度的使用
定标：为了度量属性或者特征而为他们分配编号或其他符号的过程。
1)度量：类别标度，区间标度
2)构造定标时要考虑：
有效性：度量的内容的程度
可靠性：度量的一致性，如果相同条件下两次调查一致，就是外部一致性
3)避免的问题
不严格的标度：可以把平均水平移到中心的左边或右边来避免
集中趋势：回答者都回答中间值，可以通过减少两个端点的差异，调整描述符的强度，创建一个更多结点的尺度来改善
光圈效应：避免在一个问题中印象带入下一个问题

5.问卷调查表的设计准则：
•留出充足的空白空间
•留出充足的空间来填写或输入答复
•使回答者能够清楚地标出他们的答复
•保持风格的一致
•提问顺序的选择：
（i）把重要问题放在前面，问题要先人后己，先问用户最关心的问题，再问系统或者调查目的需要的问题
（ii）把相似内容的问题放在一起
（iii）首先提出非敏感和非争议的问题

6.管理问卷调查表
1)回答者：按照调查对象的级别，在公司服务的年限，工作职责和对建议系统的兴趣来选择代表，要选择足够多的代表
2)管理调查问卷的方法：
a)同时召集所有有关回答者
b)亲自发放问卷，并回收
c)允许回答者自我处理，并放入中央的箱子里，如web问卷和email问卷，常用的方法，但是回收率可能低
d)邮寄给职员，并提供截止日期，填写说明和寄回邮资
e)email和web的方式管理

2. 信息收集非干扰性方法

包括：采样、调查、观察决策者行为和物理环境

2.1.采样

1. 定义：从某一种群的系统中选择有代表性的个体
2. 必要性：节约成本、加快数据搜集过程、提高效率、减少偏差
3. 四个步骤

• 确定要收集或要描述的数据：考虑数据收集方法（调查、面谈、调查问卷和观察等），考虑研究目标
• 确定采样种群：硬数据（两个月或全年的报表），采样的客户
• 选择采样类型
• 决定采样规模
  4. 采样类型：

1. 便利采样：容易安排，五约束的非概率型采样，最不可靠
2. 目的采样：选择对系统了解，感兴趣的人，这是非概率型采样，只有适度的可信度
3. 简单随机采用：每个个体的机会相同，产生一个随机编号表，在文档和报表采用中不切实际。
4. 复杂采样是最好的

• 系统采样：在名单中每个K个人选择一个，缺点是存在周期问题，引入偏差，采样大量不成比例的职员
• 分层采样：最重要的方式，在不同的层次，如管理层，社会阶层，在不同层次中按比例选择。当想对不同层次用户采用不同数据收集方法时采用分层采样。
• 聚类采样：选择一组人或文档进行研究

5. 采样规模

1. 确定采样属性
2. 定位能查找到的属性的数据库或报表
3. 分析属性，估计p，一般取0.1或0.5
4. 主观是定一个值，i 作为区间估计
5. 选择置信度 z，如 95%时 z=1.96
6. 计算种群比例的标准差 σ=i/z
7. 计算采样规模：n=(p(1-p))/σ^2 + 1
   置信度越高采样规模越大
   确定面谈时的采样规模： 至少与组织中每个阶层的3个人进行面谈，3个人种至少有一个来自组织中的不同部门。

2.2 调查

调查法：发现数据并对数据进行分析的行为。需要研究不同的硬数据。

2.2.1 分析定量文档

1.用于决策的报表
通常是与库存状态、销售量和生产有关的纸质报表
生产报表：包括最近价格、当前库存、最近劳动力和设备等信息
总结报表：提供公司的背景和战略信息

2.业绩报表： 估计实际业绩和预期业绩的差距

3.记录
a)检查数量和总数的错误。
b)寻找改善记录表格设计的机会
c)观察交易的数目的类型
d)寻求能用计算机简化工作的实例（即，计算和其他数据处理）

4.数据收集表格：有助于理解企业的信息流
a)收集所有正在使用的表格样品
b)标出表格类型：内部，手写，web表等
c)记录打算采用的分发方式
d)将打算采用的分发方式和实际收到表格的人做比较
数据收集表格的分析耗时，还可以对已经填好的数据表格进行采样，需要记住5个问题：
•表格填写完整了么？缺了什么
•有从未使用过的表格么？为什么？
•所有表格都向相应地人做了详细说明么？没有，为什么？
•如果有纸质的表格，和web表格，比较填写速度
•经常使用非官方的表格么？

2.2.2 分析定性文档

电子邮件、备忘录，留言板、工作区的签名、web页面、程序指南和战略手册
5个指导原则：
•检查文档中的关键比喻或主导比喻
•在文档中寻找局内人与局外人或“我们反对他们”的思想状况
•列出褒义或贬义的术语，文档中重复出现的术语
•查找在公共区域Web页面上公布的有意义的图形、标识语和图标的用法。
•识别出幽默感。

1.备忘录： 了解组织成员对价值、态度和信念的看法
2. 公告板或者工作区的标语与海报：体会公司的主流文化
3. 公司中的Web站点：分析网站内容的比喻、幽默和使用的特性（颜色、图形、动画和超级链接），从技术、美学和管理方面调查。 调查web站点和站点间的交互性、消息的可访问性和明显的安全性
4. 指南：程序指南和在线指南，指南很少会保持更新
5. 政策手册：价值观、态度和信念。
老师说不考但是上课说道物理环境，也是调查的一部分：办公设备、布置、公司文化，楼层安排，布告栏，email 论坛，公司色调。

3. 原型化方法

3.1 原型化方法

1. 原型：是实际运行的有产品的主要特征，基于软件最初版本的演习。不需要反映所有的功能，只需有软件功能的子集。
原型化方法是通过原型来获取有关建议系统和系统如何迅速满足用户信息需求的反馈的极好办法。
2. 原型分类一：
水平原型：多种功能的展示
垂直原型：对某一个功能进行详细展示

3.原型分类二(书中的分类)
•拼凑原型：构件一个可以运行，但又是经过修补或者拼凑而得到的系统。
•非操作原型：为了试验设计方案的某些方面而建立的一个非工作比例模型。如汽车实物模型。当编码成本高时采用
•系列首发原型：创建系统的第一个实物工作模型，即试验模型，是可以工作的原型。
•精选特征原型：建立一个包含最终系统部分特性而不是全部特性的可工作模型。

4.原型分类三
•抛弃式原型：尽可能快速开发
•试用型原型：最终的开发平台和原型相同
•试验型原型：最终开发平台与原型不同。

5.原型化方法的优点
•根据用户反馈，不断调整修改
•开发周期短，成本低
•缩短产品和需求的差别，开发出更贴近用户需求和期望的系统
•界面原型在获取用户反馈时有很大优势
•可以在系统开发早期改变系统
•可以中止一个不能工作的系统开发

6.原型化方法的缺点：
•需求不充足，开发者对用户需求不清楚，误解，过早的形成一个系统
•原型和最终系统之间存在差别，用户会误以为是最终系统
•开发者容易依赖原型，不愿意放弃原型
•原型开发成本高时会过度占用开发周期宝贵的时间，最初原型不能超过20%的时间
•经济损耗

7.原型化方法不适用的地方：
嵌入式系统：界面简单，与硬件太接近，需求明确
实时控制软件：搜索引擎，
科学计算：matlab，因需求明确，精度，效率，时间要求明确，模块太多，重要性均等，无法明确判定哪些是重要的需要原型化的。
但是很多应用，如游戏是适用于原型开发的。

3.2 原型开发

1. 原型化方法的要求：
用户是熟练的专家，可以给出反馈
重视界面，如手持设备
成本低，不会占用太长的开发周期

2.开发准则
•引进便于管理的模块：但不用建立完整的工作准则
•快速建立原型
•用连续迭代来修改原型
•强调用户界面：用户可以和原型轻松交互

3.原型开发流程
听取用户意见，修改原型，用户测试，不断循环迭代。

3.3 RAD快速应用程序开发

1. 定义：是一种面向对象的系统开发方法，包括开发方法和开发工具。目标是缩短传统SDLC方法中信息系统的设计和实践之间漫长的时间，反映需求的变更，是原型化方法的一种特殊实现。

2. RAD的阶段

1)需求规划阶段：确定系统的业务目标和信息需求
2)RAD设计研讨会：RAD的核心，与用户共同合作设计系统，讨论设计的非技术方面，并对构建的工作原型给出反馈
3)实现阶段：根据设计，建立、优化、测试新系统

3. Jame Martin RAD 四个阶段

1)需求规划：高级用户决定系统的功能
2)用户设计：与用户交互讨论系统的非技术方面
3)构建阶段：根据设计，用RAD工具构建，并向用户展示新系统，让他们交互、评论和检查。
4)转换阶段：新系统取代旧系统，测试新系统，培训用户

4.优势
•传统SDLC采用的是有序的、系统的开发方法，保证系统的完整性和精确性，
但抵制变更，不能很好地处理需求的变更。
•RAD缩短SDLC，更欢迎变更。

5.使用条件
•团队中有用过RAD的程序员和分析员
•由于商业压力，要求加快应用程序某部分的开发
•从事一项全新的电子商务应用程序，并且开发团队相信，如果应用程序是第一个或第一批出现在web上，则企业作为一个创新者取得竞争优势。
•用户经验丰富，对公司的组织目标高度负责。

6.缺点：缺乏文档

资源：
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4

Petri网

1. 以生产者消费者为例子

Petri三元组PN=(P,T,F)即，库所，变迁，转换弧

Preset表示前集,如果x是变迁，那么preset表示某个变迁的输入库所集合，如果x是某个库所那么preset表示某个库所的输入变迁。

Postset表示后集，如果x是变迁，那么postset表示某个变迁的输出库所集合，如果x是库所，那么postset表示某个库所的输出变迁集合。[more…]

2. Marking， Enable， Firing

M(p)表示当前所有库所的Token数量, 是一个快照.

通过这个图，可以很简单地看出 M(p)的计算等式.
当库所的token都到位后，变迁就enable了，如上图左边t2是enable的, t1没有enable， 如果Firing点火，就会转到另一个Marking下，如图中右边的图是点火后的Marking。

3.Handle

PP—handled : 某一个Place到另一个Place有两条不相交的路径

TT handled：某一个Transition和另一个Transition有两条不相交的路径

PT—handled：某一个Place到另一个Transition有两条不相交的路径

TP—handled：某一个Transition到另一个Place有两条不相交的路径

Well-handled：只有TT和PP，没有PT，TP。 因为PT会有死锁的风险， TP会造出某一个Place内部的Token无限增长

4.State Machine和Marked Graph

• Marked Graph：库所只有单个输入和单个输出
• State Machine: 每个变迁只有单个输入和单个输出，这是一个有限状态机
• T-component：如果一个大的Petri可以找到一个子网符合marked graph的要求，就是 T-component, 如果所有的T-component的集合可以覆盖整个Petri网，就是T-coverability。
• P-component：是一个大的网络中的一个Petri子网，满足state machine的，如所有的P-component可以覆盖整个Petri网，则称Petri网P-coverability

5. 活性和有界性

• 活性：从M0状态出发，对于任何一个M和t转换后的M’，可以让任何变迁T有可能点火enable.什么是不活呢，就是死锁，但是不死锁，不等价于活性
• 有界性：不论状态如何变化，token数量都不会无限增长，保持在一定数量
• Petri是well-formed的：存在M0使这个Petri网有活性并且有界

6. Free-choice structure

自由选择结构：如果两个输入库所交集不为空，蕴含两个输入库所相等

t1和t2是对等的选择关系.

自由选择结构可以表达并发关系和同步关系

给定一个自由选择结构，可以很好地决定它的活性和有界性。

7. 哲学家吃通心粉

有五个哲学家围坐在一圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后，欲吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。

资源

分布式系统总结part1 中间件，进程迁移，移动通信失效，名称解析，移动实体定位

分布式系统总结part2 Lamport同步与向量时间戳，两大选举算法，三大互斥算法

分布式系统总结part3 复制和一致性(以数据和以客户为中心的一致性)，容错（拜占庭将军问题，两阶段与三阶段提交）

分布式系统总结part4 Petri网解决哲学家问题和生产者、消费者问题