요구 사항 분석
시스템 개발자는 사용자들의 요구사항을 만족시키기 위하여 하드웨어 및 소프트웨어 시스템 설계 및 구현
(예) 1 Km 거리에 200Kbps급 데이터를 전송할 수 있는 양방향 무선 데이터 통신모듈을 개발
z 어떤 무선 통신 채널 (예: 2.4GHz 또는 900MHz)을 사용할 것인가 ? z 관련 하드웨어 모듈/Chipset은 ?
사용가능한 임베디드 프로세서는 ?
z 무선 통신 채널을 제어하고 관리하기 위한 운영체제 (OS)는 ? (예: Embedded Linux, uC/OS-III)
z 무선 통신 채널의 데이터 전송 프로토콜은 ? (예: stop & wait, sliding window)
요구 사항 명세서 (spec)
z 사용자의 요구 조건을 만족하도록 시스템 하드웨어 및
소프트웨어 기능 및 제약 조건, 성능 목표 등을 포함
기능블록다이어그램
(Functional Block Diagram)
전체 시스템의 기능 블록 (하드웨어, 소프트웨어 모두 포함) 을 표현
User A (Client mode: Account User or Follower)
Input Message using MFC GUI
Display received Message using MFC GUI Simple Twitter Client
SendMsg() - create AppPDU - calculate checksum - enQueue()
ThreadSendPDU() - deQueue() - SendTo()
- delete Acked PDUs - retransmit time-out PDUs TxQueue
SendTo() RecvFrom()
ThreadRecvPDU() - RecvFrom() - verify checksum - enQueue()
RxQueue ThreadReassemblePDU() -deQueue()
-displayMsg()
Datagram UDP Socket Flow &
Error Control
ACK StreamApp
Thread Timer TCB
wnd, rwnd,cwnd, accmAck,elps_t, SeqNo,
User B (Server mode)
Receive Message, Classify Message, and multi-cast or uni-cast message
Simple Twitter Server
SendMsg() - create AppPDU - calculate checksum - enQueue()
ThreadSendPDU() - deQueue() - SendTo()
- delete Acked PDUs - retransmit time-out PDUs TxQueue
SendTo() RecvFrom()
ThreadRecvPDU() - RecvFrom() - verify checksum - enQueue()
RxQueue ThreadReassemblePDU() - deQueue()
- displayMsg()
Datagram UDP Socket Flow &
Error Control
ACK StreamApp
Thread Timer TCB
wnd, rwnd,cwnd, accmAck,elps_t, SeqNo,
Functional Block Diagram (기능블록다이어그램)
z 하드웨어 및 소프트웨어 기능 블록을 모두 포함 z 기능블록 단위
Sub-system: e.g.) 1:1 chatting messaging subsystem
Module: e.g.) SimpleTwitterClient, SimpleTwitterServer, StreamApp, DatagramUDPSocket
Unit: sendMsg(), ThrdSendPDU(), ThrdRecvPDU(), ThrdReassemblePDU(), sendTo(), recvFrom()
z 각 기능블록간의 인터페이스를 표시
z 기능블록도의 기능블록은 Sequence Diagram에서 interaction의 기준 단위가 됨
z 기능블록간의 interaction의 예
H/W 기능블록 <-> H/W 기능블록: 하드웨어 전기신호
S/W 기능블록 <-> H/W 기능블록: Control register setting, status register reading
S/W 기능블록 <-> S/W 기능블록: 함수 호출
Modeling as a Design Technique
Modeling
z testing a physical entity before building it z communication with customers
z Visualization: e.g., storyboards of movies z Reduction of complexity
Abstraction
z a selective examination of certain aspects of a problem
z goal of abstraction is to isolate those aspects that are important for some purpose and suppress those aspects that are unimportant
z pseudo code of functional module
Three Models
z class model: describes the structure of objects in a system -> Class Diagram
z interaction model: describes interactions between objects -> Sequence Diagram
UML (Unified Modeling Language)
UML is a language for
z visualizing z specifying z constructing
z documenting: requirements, architecture, design, source code, project plans, tests, prototypes, releases
UML diagrams
z classes z interfaces
z sequence, collaborations
z use cases
Design of Classes
Define Classes
z Define classes for Major functional modules
z Class in appropriate size: not too large, not too small
Examples of classes in StreamApp
z SimpleTwitter z StreamApp
z StreamAppPDU z RingBuffer
z ListNode
z TransmissionControlBlock(TCB)
z SocketUDP
Class design
z Attributes z Methods z inheritance z containment
Class Diagram
TempSensor +curTemp: Float
#notiThreshold: Int -pollingPeriod: Int
+reset()
#setNotiThreshold() -setPollingPeriod()
class Name
Attributes (Data Members) + : public attributes
# : protected attributes - : private attributes
Operations (Member Functions) + : public method
# : protected method - : private method
Example of Modeling a Schema with UML
School name: Name address: String phone: Number addStudent() removeStudent() getStudent() getAllStudent() addDepartment() removeDepartment() getDepartment() getAllDepartment()
Department name: Name location: String phone: Number addFaculty() removeFaculty () getFaculty () getFaculty ()
Faculty name: Name office: String phone: Number Course
name: Name couseID: Number Student
name: Name
studentID: Number
1 1..*
Has
0..1
0..1
chairperson 1..*
1..*
1..*
1..*
AssignedTo
* 1..*
Teaches
* *
Attends
* 1..*
Member
Class relationships, inheritance, containments (1)
z StreamAPP Twitter Server
Follower_Node
follower_number : int statusFlags : unsigned short follower_data : struct follwer
Follower_Node()
~Follower_Node() getfollower_number() getstatusFlags()
getfollower_data()Next_followerNodeprt & Pre_followerNodeprt
ListNode
seqNo : unsigned short statusFlags : unsigned short timeout : unsigned int dataSize : int dataPtr : char*
ListNode()
~ListNode() getseqNo() getstatusFlags() gettimeout() getdataSize() getdataPtr()
NextNodeptr & PreNodeprt StreamAppPDU
uchType : unsigned char uchStreamid : unsigned char ushSequenceNumber : unsigned short ushACK : unsigned short
ACK : unsigned char SYN : unsigned char PUSH : unsigned char unused : unsigned char Length : unsigned char windowSize : unsigned short Checksum : unsigned short userData : unsigned char*
Follower_table
Myaddress : SOCKADDR_IN Myprot : unsigned short Myid : CString Followercount : int
getnewfollower() Follower_table()
~Follower_table() enFollower() deFollower()
Delete_From_Follower_table() isFollower_Empty() isFollower_Full()
RingBuffer
ringsize : int queueLength : int
getnewListNode() RingBuffer()
~RingBuffer() enQueue() deQueue() DeleteFromBuffer() isQueueEmpty() isQueueFull()
sockUDP
m_iSenderAddrSize : int m_chBuf : char[MAX]
s_wsaData : WSADATA m_ushPort : unsigned short m_SenderAddr : SOCKADDR_IN m_RecvAddr : SOCKADDR_IN
init() RecvFrom() SendTo() SockUDP()
~SockUDP()
CSimpleTwitterDig
m_str_LoginputOutput : CString
PrintReceivedMessage()
<<virtual>> PreTranslateMessage()
<<virtual>> OnInitDialog()
<<afx_msg>> Onpaint()
StreamAPPTwitterServer
StreamAPPTwitterServer()
<<virtual>> ~StreamAPPTwitterServer() Verifychecksum_16()
ActiveOpen()
<<static>> TimerThreadProc()
<<static>> RecvThreadProc()
<<static>> SendThreadProc() Close()
makePDU() Timecheck() makeAckPDU() initStreamAppSess() ConfigStreamAppSess() CloseStreamAppSess() AddUser()
DeleteUser()
Class 설계 (1)
Class RingBuffer
1. Data Members (Attributes) Access
specifier Attribute Description
private int ringSize • capacity of ring buffer (maximum number of packets that can be stored in the ring buffer)
• used by private int queueLength
Class 설계 (2)
2. Member Functions (Behaviors) Access
specifier Member function
name Input arguments/
return data Description
public
void enQueue(
Pkt * pPkt, int numPkt )
Pkt* pPkt • input arguments
• pointer to a buffer that contains a packet int numPkt • number of packet to be transmitted
void • no return data
public Pkt * deQueue(
) void
void • no input argument
Pkt* • return a pointer to packet
public
boolean isQueu eEmpty(
) void
void • no input argument
boolean • return data type
• true: Queue is empty;
• false: Queue is not empty
Sequence Diagram (순서도)
Necessary sequence diagram in StreamApp
z Passive Session Open: server side of SimpleTwitter z Active Session Open: client side of SimpleTwitter
z Session Close: requested by client side or server side z Message Transmission:
AppPDU from A to B: processing in sender side, processing in receiver side
management of ACK counter at receiver for piggy-back or ACK message
ACK from B to A: processing in PDU receiver side, processing in PDU sender side
z Flow Control: AppPDU from A to B, manage ACK counter from B to A, send piggy back ACK or ACK message from B to A, Adjust wnd (window size) by rwnd (ACK) and cwnd
z Error Control: duplicate ACKs for out-of-order packet arrival, fast retransmit, retransmit at time out
z Congestion Control: Adjust cwnd at duplicate ACKs, Adjust cwnd at time out
Sequence Diagram : Session Open(1) SYN : Client->Server
Sequence Diagram : Session Open(2) SYN+ACK : Server->Client
Sequence Diagram
z Sequence diagram에서는 기능블록간의 상호 연동 (interaction)을 표시함 z S/W 기능블록으로 화살표가 도착하는 경우
해당 S/W 기능블록의 함수 호출이 이루어 지며,
해당 S/W 기능블록 (예: C 프로그램 모듈, C++ Class)에 해당 함수가 지정되어 있어야 하며, 관련 input arguments가 정확하게
정의되어있어야 함
z Sequence diagram에서 각 주요 기능의 처리 절차를 확인할 수 있으며, 관련 모듈/객체의 설계에서 해당 멤버 함수들과 데이터 멤버들이
정확하게 설계되어 있는지를 확인할 수 있음
State Transition Diagram (상태천이도)
State transition diagram of a Stream APP PDU
z Object (객체)의 상태 변화에 대한 설계
z 어떤 object가 어떤 함수 호출에 의하여 어떤 상태로 변화하는 지에 대하여 설계
z Object의 생성에서 부터 소멸에 까지의 전 과정이 포함되어야 함
z C/C++ 프로그램의 동적 메모리 할당에서 언제 메모리가 할당되는지, 언제 메모리가 반납되는지에 대하여 정확하게 관리될 수 있어야
memory leak 문제를 해결할 수 있음
start
Instantiated EnQueued
Transmitted Deleted
SendMsg() enQueue()
deQueue() / transmission Ack()
함수의 내부 알고리즘 설계
함수의 내부 실행 알고리즘
z 각 함수 (thread 포함)는 지정된 기능을 수행하기 위하여 적합한 자료구조를 사용하며, 알고리즘에 따라 순차적으로 수행
z 각 함수에서 실행되는 알고리즘의 설계에 따라 성능에 큰 차이가 날 수 있음
예) 100,000개 이상의 데이터 sorting에서 bubble sorting 방식과 selection sorting 방식의 성능 차이
예) 100,000개 이상의 데이터가 저장되어 있고, 동적으로 새로운 데이터가 추가되거나 삭제되는 환경에서 전체 데이터를 순서에 따라 sorting된 상태로 유지하여 신속하게 search 기능이 실행되어야 하는 경우에서 이를 linked list로 관리하는 방식과 binary search tree로 관리하는 방식의 성능 차이
알고리즘의 개발
프로그램 실행에서의 핵심적인 골격 (skeleton)을 정리
어떤 단계를 밟아서 어떤 순서로 작업을 처리할 것인지를 설계
순서도와 의사 코드 (pseudo code)를 표현 도구로 사용
알고리즘은 실제 프로그램 구현에서 사용되는 프로그래밍 언어 (예:
C, C++, Java)에 제한 받지 않음
알고리즘은 원하는 결과를 얻기 위하여 밟아야 하는 단계에 집중적으로 초점을 맞추는 것
알고리즘과 함께 사용될 자료구조 (data structure)가 중요
프로그램을 작 성하기 전에 먼 저 알고리즘을 구상합니다.
알고리즘을 만드는 방법
문제를 한 번에 해결하려고 하지 말고 더 작은 크기의 문제들로 분해한다.
문제가 충분히 작아질 때까지 계속해서 분해한다.
(예) 주어진 정수 k가 소수(prime)인가 아닌가를 판별하는 알고리즘을 만들어보자.
문제:주어진 정수 k가 소 수인지를 판별하라
STEP 1: 정수 k의 약수의 개수를 구한다.
STEP 2:약수의 개수가 2 이면 소수이다.
STEP 1-1: 정수 k를 1로 나누어서 떨어지면 약수
의 개수를 증가
STEP 1-2: 정수 k를 2로 나누어서 떨어지면 약수
의 개수를 증가
STEP 1-k:정수 k를 k로 나누어서 떨어지면 약수
의 개수를 증가 ...
알고리즘의 표현
1. 영어와 국어와 같은 자연어 (natural language) 2. 순서도(flowchart)
3. 의사 코드(pseudo-code)
예제: 숫자들의 리스트에서 최대값을 구하는 문제
컴퓨터앞에 바로 앉지말 고 알고리즘 을 구상하여 야 합니다.
12 26 9 35 3 18
12 26
35 최대값
순서도 (flow chart)
프로그램에서의
논리순서 또는 작업순서 등을 그래픽으로
표현하기 위한 형식
알고리즘이 복잡하면
기술하기가 힘들어진다.
의사 코드 (pseudo code)
자연어보다는 더 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘의 표현에 주로 사용되는 코드 z Simplified list of instructions to show the overall
process of algorithm
z not following the details of programming language
z the skeleton of the algorithm should be shown
Pseudo code의 예:
z 주어진 숫자 목록 (list)에서 제일 큰 값 찾기
Procedure FindLargest()
1: int dataArray[0..N-1] // array of data with N elements 2: int largest;
3: int index = 0;
4: largest = dataArray[index];
5:
6: while (index < N) {
7: if (largest < dataArray[index]) 8: largest = dataArray[index];
9: index = index + 1;
10: } // end while 11:
12: printout largest;
13: end // end of Procedure FindLargest()
Source Coding
알고리즘의 각 단계를 프로그래밍 언어를 이용하여 기술
어떤 프로그래밍 언어로도 가능
알고리즘을 프로그래밍 언어의
문법에 맞추어 기술한 것을소스 프로그램(source program)
소스 프로그램은 주로 텍스트 에디터나 통합 개발 환경을 이용하여 작성
(Q) 알고리즘 개발과 코딩
중 어떤 것이 더 어려울까?
드디어 코 딩을 시작 합니다.
(A) 알고리즘 개발이 더 창의적인 작업이고 더 어렵다
Source code documentations
Standard comment at each source code file produced in this course
/**
* File Name: "???.c" or "xxx.h", or "yyy.cpp"
* Description:
* - This program is . . .
*
* Programmed by Gil-Dong Hong,
* Last updated: Version 2.0, March 1, 2011 (by Young-Chul Kim).
*
* ========================================================
* Version Control (Explain updates in detail)
* ========================================================
* Name YYYY/MM/DD Version Remarks
* John Doe 2009/11/15 1.0 1:1 Chatting on UDP
* socket, 2 threads
* John Doe 2010/05/01 1.1 User interface has been
* updated with GUI
* Mark Kim 2010/08/03 2.0 Major change in the
* program structure
* ========================================================
*/
