Lifeignite

OSI 참고 모델

OSI 7계층은 데이터를 송수신하기 위한 규칙이다. 다시말해 프로토콜인데, 이는 데이터의 송수신을 하기 위한 규칙을 표준화 시키기 위해 ISO에서 선언한 것이다.

OSI는 데이터 통신의 단계구성도로 Open Systems interconnection Reference Model의 약자로, 데이터 통신을 7단계로 나누어서 프로토콜들을 관리한다. 이 때 각각의 계층(Layer)들은 서로 독립되어 있다는 것이 중요하다. 이 각각의 계층들은 단계 마다의 복수의 프로토콜로 실현된다. 여기서 독립되어 있다는 것은 어떤 계층의 프로토콜 변경은 다른 계층에 영향을 끼치지 않는다는 것이다. 

일반적으로  OSI  참조 모델은 송신 측은 7계측에서 1계층의 순서로, 수신측에서는 1계층에서 7계층의 순서대로 수행한다.

이 때, 각각의 계층에서 원래의 데이터 이외에도 필요로하는 추가적인 데이터(예컨데, 어디로 도착해야하는지-IP와 같은-같은 것들)를 붙일 필요성이 있는데, 이렇게 필요한 데이터를 붙여서 만든 새로운 데이터를 프로토콜 데이터 유닛, 즉 PDU(Protocol Data Unit)라고 부른다.

이 때, 각각의 계층별 PDU를 따로부르는 이름이 있는데, 5~7계층은 메세지(Message), 4계층은 세그먼트 혹은 데이터 그램, 3계층의 PDU는 데이터그램 혹은 패킷, 2계층은 프레임 1계층은 신호라고 부른다. 

이때 3~7계층의 데이터는 대체로 모두 앞부분에 추가적인 정보가 붙는데 이를 헤더라고 부르고, 2계층에는 앞부분과 뒷부분 모두에 추가적인 데이터가 붙는데 앞부분은 헤더, 뒷부분은 trailer라고 부른다. 이러한 각 계층별 추가로 붙는 정보는 TCP 헤더, 4계층 헤더 라는 식으로 부르기도 한다.

하지만 이러한  계층 사이에서도 상하를 연결할 필요성이 있다. 완전히 제각각이라면 처리가 불가능하기 때문이다. 따라서 이렇게 처리하기 위해 상하 계층 구조간 연결하는 역할을 하는 것이 인터페이스인데, 이렇게 7계층부터 1계층까지 연결된 프로토콜 그룹을 프로토콜 군(Protocol Suite)이라고 부른다. 즉, 데이터 통신은 같은 프로토콜 군을 사용하는 컴퓨터나 기기끼리만 가능한 것이다. 

현재 OSI표준 프로토콜군은 사실상 실패하여 표준화 시키지 못했다. 현실적으로 가장 많이 사용되는 것은 TCP/IP프로토콜군으로 현재 인터넷에서 사용되는 프로토콜군이다. TCP/IP는 사설 표준(De Facto Standard)이다. 사설 표준이란 제정된 프로토콜이 아니라, 사용하는 기기 및 컴퓨터가 압도적으로 많아서 표준 처럼 사용할 수 있게 된 상태가 된 것을 말하는 것이다.

TCP/IP 모델

이 TCP/IP는 IETF(the internet Enginerring Task Force) 라는 단체가 제정한 프로토콜 군으로, 국제 인터넷 표준화 기구라고 부른다. 여기에서 제정하는 문서는 RFC(Request For Comments)라고 불리는데 이것이 규격이 되어 TCP/IP모델의 베이스가 됐다. 

사실상 TCP/IP 모델이 위와 같이 OSI참조 모델과 1:1로 대응 되는 것은 아니다. 이는 데이터 전송 프로토콜군으로서 비교를 하는 것이라 유사한 특징들이 있을 뿐이다. 자세히 들여다 볼 경우에는 차이점 이있다.

TCP/IP프로토콜군의 프로토콜들

4계층(애플리케이션 계층) : HTTP, FTP, SMTP등

3계층(트랜스포트계층): TCP, UDP

2계층(인터넷 계층): IP, ARP

의미상으로는 Point to Point 네트워크는 두개의 단말은 1:1로 연결한 형태를, 멀티 액세스 네트워크는 허브를 이용하여 여러개의 단말을 연결하는 형태로 구성한 네트워크라고 보면 된다. 이 때, 멀티 액세스 네트워크 구조를 가지는 네트워크 형태에서 패킷 교환없이 케이블 분배기로 연결되는 범위를 세그먼트(Segment)라고 부르는데, 이 세그먼트 범위 내에 있는 컴퓨터는 패킷 교환 없이 데이터를 송수신 할 수 있다.

참고 : 하루 3분 네트워크 교실

어떤 PC와 PC사이에서 통신이 발생하기 위해서는 PC와 PC사이를 이어주는 파이프를 필요로한다. 두개의 PC를 연결하는데는 1가지의 파이프만 필요로 하지만, 만약 3개의 PC를 연결하게 될 경우는 어떨까? 그렇다면 A-B, A-C, B-C를 연결하는 파이프가필요하다. 즉 N개의 PC를 연결하려면 N(N-1)/2개의 파이프를 필요로한다. 이런식으로 연결하는 방식은 이렇게 매우 비효율적이다.

회선 교환 방식

이를 해결하기 위해서 회선 교환방식이 나타났다. 전화해서 이런 방식을 채택하고 있는데, 중간에 어떤 교환기가 있어서 변경해주는 방식을 말한다. 주로 전화기에서 자주 사용한다. 이 회선교환 방식은 교환기와 교환기 사이의 회선 숫자에 따라 한꺼번에 연결 가능한 통화의 개수가 제한되게 된다. 

회선 교환의 문제점 사진 참고(그림4-2)

패킷 교환 방식

이 회선 교환의 문제점을 해결 할 수 있는 대안 중 하나로 패킷 교환이라는 방식이 있다. 

패킷 교환은 데이터를 한꺼번에 한쌍의 연결이 점유하는 방식이 아니라, 데이터를 잘게 쪼개서 보내는 방식이다. 따라서, 회선이 하나 뿐이라고 하더라도 하나의 연결이 회선을 점유하지 않기 때문에 효율적으로 데이터를 송수신 할 수 있다. 이 통신 방식은 인터넷등에서 많이 사용한다. 여기서 패킷교환기는 라우터라는 다른 이름으로 불린다.

참고 : 하루 3분 네트워크 교실

링크드리스트에 관한 포스팅에 들어가기전에 대부분의 자료구조에서 사용되는 자기참조구조체에 관해서 알아보도록 하자.

 자기참조구초제(Self-referential structure)는 링크드리스트 뿐만 아니라 여러 자료구조에서(이를테면 그래프의 표현이나, 트리등의 자료구조를 작성할 때) 사용한다. 

아주 중요한 개념이라고 할 수 있는데 실질적으로 작성해보면 어렵지 않다. 

자기참조구조체를 사용하는 자료구조에서는 대부분 하나의 데이터 단위를 자기참조구조체로 관리하게 되는데 기본적으로 자기가 관리하는 데이터 정보와 자신의 타입의 레퍼런스를 가지고 있다. 모양을 보면 다음과 같다.

여기서 이런 공부를 처음 시작하는 사람들이 자주 혼동하는 개념이 있다.

이게 다 이름을 저 모양으로 지어놔서 그렇다. ㅡㅡ.. 

자기참조구조체면 마치 나 스스로를 참조할 것 같아 보이지만 참조의 대상이 나라는 구조체가 아니라 나와 같은 타입이다. 즉, 나와 같은 타입의 다른 구조체를 가르킨다고 보면 된다.( 물론 구현에 따라 자기 스스로를 가르킬... 수도 있다.)

여기서 자기참조구조체는 참조하는 대상이 한개일 수도 있지만 여러개일 수 있다. 이것도 어떤 자료구조를 구현할지에 따라서 달라진다. 예를들면 double linked list 를 구현하게 될경우 레퍼런스를 두개 사용해야하고, 자식의 갯수가 n개인 n-진트리를 작성하게 될 경우 레퍼런스가 n개가 될 것이다. 

double linked list의 자기참조 구조체를 잠깐 살펴보면 아래와 같다.

서론이 너무 길었던 것 같다. 다음번 포스트는 정말로 링크드리스트에 관하여 다루겠다.

스터디 때도 진행된적이 있는 포스팅에 앞선 기본 지식들을 점검하는 시간이다. 

앞으로 C로 자료구조를 구현하는데 있어서 기본이 되는 

C를 처음 배우는 친구들이 모를 것 같은 문법과 기초 지식들을 소개해본다. 

1. 구조체(Structure Types)

구조체는 서로 다른 기본 자료형들을 한데 묶어 관리할 수 있게 도와주는 놈이다. 

구조체 없이도 자료구조를 구현하는데 문제 없을 수 있다. 

순수하게 배열과 동적할당, 그리고 로직들을 사용하여 자료구조를 구현할 수 있는데 그런 방식으로 코드를 작성하게 될 경우 코드도 읽기 힘들고, 짜는데도 시간이 오래걸릴 수 있다. 

즉 구조체는 여러가지 구현에 있어서 우리를 편리하게 해준다. 

구조체는 우리가 직접 정의한다는 관점에서 사용자 정의 자료형이라고 볼 수도 있는데 형태는 다음과 같다.

구조체에 대해 더 자세한 내용을 알고 싶은 분들은 다른 블로그나 구글을 참고하길 바란다.

2. 동적할당

동적 할당이란 런타임중에 원하는 메모리 공간을 할당받는 것을 말한다. 

막 프로그래밍을 시작한 사람들에게 말이 조금 어려울 수 있는데, 간단히 원하는 크기 만큼 그때 그때 메모리를 받을 수 있는 것이다...(전혀 간단하지 않은 것 같다..)

하지만 역시 이 포스트는 C언어의 사용법을 다루는 것이 아니므로 자세한 설명은 생략하도록 하겠다.

C언어 에서는 이 동적할당을 편하게 이용하기 위해서 대표적으로 2가지 함수를 제공하고 있는데 

malloc과 calloc이 그 두개다.

C언어에서 이 두 함수가 작동하는 방식은 다음과 같다.

시스템에게 원하는 만큼 메모리 요청하면 그 메모리만큼을 미리 힙에 할당하고 메모리의 시작 주소를 반환

단, malloc과 calloc의 차이점은 malloc은 해당하는 메모리 영역을 초기화 하지 않고 사용자에게 반환하고, calloc은 초기화(0으로) 시키고 사용자에게 반환한다는 사실이다. 

해당하는 메모리 영역을 어떤 방식으로 활용할지는 전적으로 사용자에게 위임하기 때문에 return형은 void * 형이다. 그래서 대부분 원하는 타입으로 케스팅해서 다시 사용한다.

이 두함수는 모두 stdlib.h 라는 헤더에 존재한다.

자세한 함수의 원형을 알고 싶은 사람은 

malloc <-클릭

calloc <-클릭

사용방식은 다음과 같다. 

 이 함수를 사용할 때 주의 할 사항은 일반 기본자료형과 다르게 구조체의 크기는 시스템마다 할당하는 크기가 다를 수 있다는 것이다. 그렇기 때문에 일반적으로 해당 자료형의 사이즈를 반환해주는 sizeof 연산자와 함께 사용한다.

  또 사용이 끝난 공간은 메모리를 해제 해 주기 전까지 영원히 남아있다. 반드시 사용이 종료되면 메모리를 해제해 주어야 한다. 이는 free함수로 메모리 해제를 시스템에 알릴 수 있다.

3. 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

시간 복잡도와 공간복잡도에 대해서는 굉장히 많은 내용을 설명해야 한다. 주로 다룰 내용은 빅-오 표현이 굉장히 중요하다.(사실 평균도 나름 중요하다.)

그래서 안할꺼다.  간단히 설명하자면 상수 때고 가장 크게 영향을 주는 식만을 시간 복잡도로 나타낸다. 보통 O(n),O(lgn) 등과 같이 나타낸다.

역시 구글과 다른 블로그들을 참조하길 바란다. 앞으로 대부분의 자료구조에서 연산을 정의할 때 그 정의된 연산이 얼만큼의 시간복잡도와 공간복잡도를 가지는 지를 소개할 텐데 꼭필요한 부분이다. 학습하고 오시길 ^ㅇ^ 

이부분은 나중에 따로 포스팅 할 수도 있다. 

잘못된 내용은 덧글로 알려주세요. 수정하도록 하겠습니다.

현재 학교 소모임에서 자료구조를 스터디 하고 있는데

학년도 4학년이기도 하고 다시 자료구조를 스터디하거나 

심도있게 다룰 것 같지는 않습니다. 

마지막이라는 심정으로 자료구조를 포스팅하도록 할게요.

아마 겨울 방학 때는 알고리즘 쪽 스터디를 맡을 수도 있는데

그렇게 되면 아마 알고리즘 관련 포스팅도 진행할 것 같아요.

자료구조 관련 포스팅은 기본적으로 C로 진행됩니다.

후반부로 가면  C++을 사용하긴 할 것 같습니다만... 가봐야 알겠네요.

포스팅 순서는 아마도

링크드 리스트

스택

큐

트리

힙

------------------------------------ 요기까지 C

그래프

최단거리알고리즘

MST알고리즘

------------------------------------ 요기까지 C++ 

이런 것들을 다룰 것 같습니다. 더 다룰수도 있고 아닐수도 있고...