요구사항분석 시스템개발자는사용자들의요구사항을만족시키기위하여하드웨어및소프트웨어시스템설계및구현 ( 예 ) 1 Km 거리에 200Kbps 급데이터를전송할수있는양방향무선데이터통신모듈을개발 어떤무선통신채널 ( 예 : 2.4GHz 또는 900MHz) 을사용할것인가? 관련하드웨어모듈 /Chipset 은? 사용가능한임베디드프로세서는? 무선통신채널을제어하고관리하기위한운영체제 (OS) 는? ( 예 : Embedded Linux, uc/os-iii) 무선통신채널의데이터전송프로토콜은? ( 예 : stop & wait, sliding window) 요구사항명세서 (spec) 사용자의요구조건을만족하도록시스템하드웨어및소프트웨어기능및제약조건, 성능목표등을포함 ch 20-12
기능블록다이어그램 (Functional Block Diagram) 전체시스템의기능블록 ( 하드웨어, 소프트웨어모두포함 ) 을표현 User A (Client mode: Account User or Follower) Input Message using MFC GUI Simple Twitter Client Display received Message using MFC GUI User B (Server mode) Simple Twitter Server Receive Message, Classify Message, and multi-cast or uni-cast message StreamApp StreamApp SendMsg() - create AppPDU - calculate checksum - enqueue() TxQueue TCB wnd, rwnd,cwnd, accmack,elps_t, SeqNo, ThreadSendPDU() - dequeue() -SendTo() - delete Acked PDUs - retransmit time-out PDUs Thread Timer ACK Flow & Error Control ThreadReassemblePDU() -dequeue() -displaymsg() ThreadRecvPDU() -RecvFrom() - verify checksum - enqueue() RxQueue SendMsg() - create AppPDU - calculate checksum - enqueue() TxQueue TCB wnd, rwnd,cwnd, accmack,elps_t, SeqNo, ThreadSendPDU() - dequeue() -SendTo() - delete Acked PDUs - retransmit time-out PDUs Thread Timer ACK Flow & Error Control ThreadReassemblePDU() - dequeue() - displaymsg() ThreadRecvPDU() -RecvFrom() - verify checksum - enqueue() RxQueue Datagram UDP Socket Datagram UDP Socket SendTo() RecvFrom() SendTo() RecvFrom() Tx Rx Tx Rx ch 20-13
Functional Block Diagram ( 기능블록다이어그램 ) 하드웨어및소프트웨어기능블록을모두포함 기능블록단위 Sub-system: e.g.) 1:1 chatting messaging subsystem Module: e.g.) SimpleTwitterClient, SimpleTwitterServer, StreamApp, DatagramUDPSocket Unit: sendmsg(), ThrdSendPDU(), ThrdRecvPDU(), ThrdReassemblePDU(), sendto(), recvfrom() 각기능블록간의인터페이스를표시 기능블록도의기능블록은 Sequence Diagram에서 interaction의기준단위가됨 기능블록간의 interaction의예 H/W 기능블록 <-> H/W 기능블록 : 하드웨어전기신호 S/W 기능블록 <-> H/W 기능블록 : Control register setting, status register reading S/W 기능블록 <-> S/W 기능블록 : 함수호출 ch 20-14
Modeling as a Design Technique Modeling testing a physical entity before building it communication with customers Visualization: e.g., storyboards of movies Reduction of complexity Abstraction a selective examination of certain aspects of a problem goal of abstraction is to isolate those aspects that are important for some purpose and suppress those aspects that are unimportant pseudo code of functional module Three Models class model: describes the structure of objects in a system -> Class Diagram interaction model: describes interactions between objects -> Sequence Diagram state model: describes those aspects of objects concerned with time and the sequencing of operations -> State Transition Diagram ch 20-15
UML (Unified Modeling Language) UML is a language for visualizing specifying constructing documenting: requirements, architecture, design, source code, project plans, tests, prototypes, releases UML diagrams classes interfaces sequence, collaborations use cases ch 20-16
Define Classes Design of Classes Define classes for Major functional modules Class in appropriate size: not too large, not too small Examples of classes in StreamApp SimpleTwitter StreamApp StreamAppPDU RingBuffer ListNode TransmissionControlBlock(TCB) SocketUDP ch 20-17
Class design Attributes Methods inheritance containment Class Diagram class Name TempSensor +curtemp: Float #notithreshold: Int -pollingperiod: Int Attributes (Data Members) + : public attributes # : protected attributes - : private attributes +reset() #setnotithreshold() -setpollingperiod() Operations (Member Functions) + : public method # : protected method - : private method ch 20-18
Example of Modeling a Schema with UML School name: Name address: String phone: Number addstudent() removestudent() getstudent() getallstudent() adddepartment() removedepartment() getdepartment() getalldepartment() Has 1 1..* Department name: Name location: String phone: Number addfaculty() removefaculty () getfaculty () getfaculty () 1..* 0..1 1..* AssignedTo 1..* Member * Student name: Name studentid: Number Attends * * 1..* Course name: Name couseid: Number * Teaches 1..* 1..* Faculty name: Name office: String phone: Number 0..1 chairperson ch 20-19
Class relationships, inheritance, containments (1) StreamAPP Twitter Server 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* CSimpleTwitterDig m_str_loginputoutput : CString PrintReceivedMessage() <<virtual>> PreTranslateMessage() <<virtual>> OnInitDialog() <<afx_msg>> Onpaint() ListNode seqno : unsigned short statusflags : unsigned short timeout : unsigned int datasize : int dataptr : char* ListNode() ~ListNode() getseqno() getstatusflags() gettimeout() getdatasize() getdataptr() NextNodeptr & PreNodeprt 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() 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 StreamAPPTwitterServer StreamAPPTwitterServer() <<virtual>> ~StreamAPPTwitterServer() Verifychecksum_16() ActiveOpen() <<static>> TimerThreadProc() <<static>> RecvThreadProc() <<static>> SendThreadProc() Close() makepdu() Timecheck() makeackpdu() initstreamappsess() ConfigStreamAppSess() CloseStreamAppSess() AddUser() DeleteUser() 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() ch 20-20
Class 설계 (1) Class RingBuffer 1. Data Members (Attributes) Access Attribute Description specifier private int ringsize capacity of ring buffer (maximum number of packets that can be stored in the ring buffer) used by private int queuelength ch 20-21
Class 설계 (2) 2. Member Functions (Behaviors) Access specifier public public Member function name void enqueue( Pkt * ppkt, int numpkt ) Pkt * dequeue( void ) Input arguments/ return data Pkt* ppkt Description input arguments pointer to a buffer that contains a packet int numpkt number of packet to be transmitted void no return data 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 ch 20-22
Sequence Diagram ( 순서도 ) Necessary sequence diagram in StreamApp Passive Session Open: server side of SimpleTwitter Active Session Open: client side of SimpleTwitter Session Close: requested by client side or server side 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 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 Error Control: duplicate ACKs for out-of-order packet arrival, fast retransmit, retransmit at time out Congestion Control: Adjust cwnd at duplicate ACKs, Adjust cwnd at time out ch 20-23
Sequence Diagram : Session Open(1) SYN : Client->Server ch 20-24
Sequence Diagram : Session Open(2) SYN+ACK : Server->Client ch 20-25
Sequence Diagram Sequence diagram에서는기능블록간의상호연동 (interaction) 을표시함 S/W 기능블록으로화살표가도착하는경우해당 S/W 기능블록의함수호출이이루어지며, 해당 S/W 기능블록 ( 예 : C 프로그램모듈, C++ Class) 에해당함수가지정되어있어야하며, 관련 input arguments가정확하게정의되어있어야함 Sequence diagram 에서각주요기능의처리절차를확인할수있으며, 관련모듈 / 객체의설계에서해당멤버함수들과데이터멤버들이정확하게설계되어있는지를확인할수있음 ch 20-26
State Transition Diagram ( 상태천이도 ) State transition diagram of a Stream APP PDU Object ( 객체 ) 의상태변화에대한설계 어떤 object가어떤함수호출에의하여어떤상태로변화하는지에대하여설계 Object의생성에서부터소멸에까지의전과정이포함되어야함 C/C++ 프로그램의동적메모리할당에서언제메모리가할당되는지, 언제메모리가반납되는지에대하여정확하게관리될수있어야 memory leak 문제를해결할수있음 SendMsg() Instantiated enqueue() EnQueued start dequeue() / transmission Deleted Ack() Transmitted stop timeout() / retransmission ch 20-27
함수의내부알고리즘설계 함수의내부실행알고리즘 각함수 (thread 포함 ) 는지정된기능을수행하기위하여적합한자료구조를사용하며, 알고리즘에따라순차적으로수행 각함수에서실행되는알고리즘의설계에따라성능에큰차이가날수있음 예 ) 100,000개이상의데이터 sorting에서 bubble sorting 방식과 selection sorting 방식의성능차이 예 ) 100,000개이상의데이터가저장되어있고, 동적으로새로운데이터가추가되거나삭제되는환경에서전체데이터를순서에따라 sorting된상태로유지하여신속하게 search 기능이실행되어야하는경우에서이를 linked list로관리하는방식과 binary search tree로관리하는방식의성능차이 ch 20-28
알고리즘의개발 프로그램실행에서의핵심적인골격 (skeleton) 을정리 어떤단계를밟아서어떤순서로작업을처리할것인지를설계 순서도와의사코드 (pseudo code) 를표현도구로사용 알고리즘은실제프로그램구현에서사용되는프로그래밍언어 ( 예 : C, C++, Java) 에제한받지않음 알고리즘은원하는결과를얻기위하여밟아야하는단계에집중적으로초점을맞추는것 알고리즘과함께사용될자료구조 (data structure) 가중요 프로그램을작성하기전에먼저알고리즘을구상합니다. ch 20-29
알고리즘을만드는방법 문제를한번에해결하려고하지말고더작은크기의문제들로분해한다. 문제가충분히작아질때까지계속해서분해한다. ( 예 ) 주어진정수 k 가소수 (prime) 인가아닌가를판별하는알고리즘을만들어보자. STEP 1-1: 정수 k 를 1 로나누어서떨어지면약수의개수를증가 STEP 1: 정수 k 의약수의개수를구한다. STEP 1-2: 정수 k 를 2 로나누어서떨어지면약수의개수를증가... 문제 : 주어진정수 k 가소수인지를판별하라 STEP 1-k: 정수 k 를 k 로나누어서떨어지면약수의개수를증가 STEP 2: 약수의개수가 2 이면소수이다. ch 20-30
알고리즘의표현 1. 영어와국어와같은자연어 (natural language) 2. 순서도 (flowchart) 3. 의사코드 (pseudo-code) 예제 : 숫자들의리스트에서최대값을구하는문제 12 26 35 최대값 컴퓨터앞에바로앉지말고알고리즘을구상하여야합니다. 12 26 9 35 3 18 노트 ch 20-31
순서도 (flow chart) 프로그램에서의논리순서또는작업순서등을그래픽으로표현하기위한형식 알고리즘이복잡하면기술하기가힘들어진다. ch 20-32
의사코드 (pseudo code) 자연어보다는더체계적이고프로그래밍언어보다는덜엄격한언어로서알고리즘의표현에주로사용되는코드 Simplified list of instructions to show the overall process of algorithm not following the details of programming language the skeleton of the algorithm should be shown ch 20-33
Pseudo code 의예 : 주어진숫자목록 (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() ch 20-34
Source Coding 알고리즘의각단계를프로그래밍언어를이용하여기술 어떤프로그래밍언어로도가능 알고리즘을프로그래밍언어의문법에맞추어기술한것을소스프로그램 (source program) 소스프로그램은주로텍스트에디터나통합개발환경을이용하여작성 (Q) 알고리즘개발과코딩중어떤것이더어려울까? (A) 알고리즘개발이더창의적인작업이고더어렵다 드디어코딩을시작합니다. ch 20-35
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 * ======================================================== */ ch 20-36
설계문서 ( 양식 ) ch 20-37
ch 20-38
ch 20-39
ch 20-40
ch 20-41
ch 20-42
설계프로젝트평가 ch 20-43
ch 20-44
ch 20-45