기억보단 기록을

프로세스가 실행되기 위해서는 해당 프로그램이 물리적 메모리에 적재되어 있어야 한다.

하지만 프로세스는 물리적 메모리가 적재되어있는 주소 외에 별도로 논리적주소, 혹은 가상주소를 가지고 있는데 어떻게 논리적 주소가 물리적주소와 매핑(mapping)되고 또 물리적메모리를 어떻게 할당하는지도 알아보자.

먼저 메모리에 적재되는 물리적 메모리리의 주소와 프로세스의 논리적주소를 연결시켜주는 작업을 

주소 바인딩(address binding) 이라고 한다. 

주소바인딩은 프로그램이 적재되는 물리적 메모리의 주소가 언제 결정되느냐에 따라 세가지로 분류할 수 있다.

먼저, 물리적 메모리 주소가 프로그램을 컴파일할 때에 결정되는 주소 바인딩방식을 컴파일타임 바인딩(Compile time binding) 이라고한다. 프로그램이 절대주소로 적재된다는 뜻에서 절대코드를 생성하는 바인딩 방식이라고도 한다.

다만 프로그램이 올라가있는 물리적 메모리의 위치를 변경하고자 할때는 컴파일을 다시해야한다는 수고가 발생한다.

두번째로 프로그램의 실행이 시작될때에 물리적 메모리주소가 결정되는 주소 바인딩 방식을 로드타임 바인딩(Load time binding) 이라고 한다. 이방식에는 로더의 책임하에 물리적 메모리 주소가 부여되며  프로그램이 종료될때까지 물리적 메모리상의 위치가 고정된다.

로더란 사용자 프로그램을 메모리에 적재시키는 프로그램을 말한다.

로드타임 바인딩은 컴파일러가 재배치 가능 코드를 생성한 경우에 가능한 주소 바인딩 방식이다.

세번째로 실행시간 바인딩(Execution time binding)은 프로그램이 실행을 한 후에도 물리적 메모리 상의 주소가 변경될 수 있는 방식이다.

이 방식에서는 CPU가 주소를 참조할 때마다 해당 데이터가 물리적 메모리의 어느 위치에 존재하는지 주소 매핑 테이블을 이용해 바인딩을 점검해야한다. 또 기준레시스터와 한계레지스터를 포함해 MNU(Memory Management Unit)의 지원이 뒷받침 되어야한다.

<물리적 메모리의 할당 방식>

물리적 메모리는 운영체제의 영역과 사용자 프로세스의 영역으로 나뉜다. 그중, 우리가 살펴봐야 할것은 사용자 프로세스 영역에서, 어떻게 프로세스가 메모리에 올라가는지, 그 관리기법에 대해 알아보자.

연속 할당 방식은 프로세스를 물리적 메모리의 연속적 공간에 올리는 방식이다.

연속할당방식에서는 물리적 메모리를 분할하여 하나의 분할에 하나의 프로세스가 적재되도록 한다.

또 이때 분할방식에 따라 고정분할방식과 가변분할방식이 있는데, 고정분할방식을 사용하면 프로세스크기가 분할된 크기보다 크거나 작을때 조각이 발생한다. 따라서 공간의 낭비가 발생되는 것이다.

 이에 비해 가변분할방식은 적어도 내부조각(프로세스크기가 분할크기보다 작아서 생기는 조각)은 발생하지 않지만, 프로세스를 메모리에 올릴때 여러 공간들중 할당을 해야하는 문제가 발생한다(dynamic storage-allocation problem).

따라서 가장 최적의 방법으로는 가용공간을 살펴보며 프로세스와 가장 가까운 크기의 분할공간을 채택하는 최적 적합 방법이 효과적이나 경우에따라 가용공간중 먼저찾아지는 최초 적합 방법을 따르기도한다.

불연속 할당 기법에는 프로세스가 물리적 메모리의 여러위치에 분산되어 올라갈 수 있는 메모리 관리 기법이다.

페이징 기법, 세그먼테이션 기법, 두가지를 혼용하는 페이지드 세그먼테이션 기법이 존재한다.

데이터가 많아지면 그룹 관리의 필요성 ---> 자료의 열거형 표현

- 배열 : 하나의 변수에 여러정보를 담기 가능, 반복문등과 결합해 처리 용이, 인덱스를 가지며

               따라서 자료의 빠른 조회가 가능하다. 자료의 접근에 시간복잡도 O(1)이다.

- 리스트 : 배열은 크기가 고정적이며, 값의 수정이 번거롭다.(수정시 수정인덱스 이후의 값의 인덱스를 조정해야함)

                위의 한계를 해결하는것이 연결리스트(Linked List). 값을 동적으로 생성된 노드에 저장해 자료들간의 연결관 계  구성.  공간적제                  약을 덜 받고 자료의 수정삭제가 쉽다. 하지만 자료의 접근성에있어 시간복잡도 O(N)을 띄게 된다.

연결리스트의 각노드에는 data값과 다음 노드의 주소를 가지게 된다.

head부분은 데이터가 있어도되고 없어도되며 없을경우가 코드를 구성하기 더 쉽다.

이경우 head는 어떤 기능도 하지않는 더미노드(dummy node)가 된다.

아래코드와 함께 살펴보자

먼저 연결리스트의 정의부분이다.

listNode라는 것을 구조체로 선언하는데 위에보면 listNode 형의 포인터인 listPointer가 선언된다.

이렇게 포인터변수를 하나 선언해놓으면 프로그램작성이 조금더 간단해진다고 할 수 있다.

struct listNode *= listPointer 이다.

먼저 프로그램은 임의의 수들을 파일입력으로 넣는데, 이를 오름차순정렬인 리스트로 만드는 프로그램이다.

find는 리스트 노드가 한개 들어갈때마다 들어갈 위치를 정해준다. 여기선 계속해서 link(=next)로 넘어가다가

자신보다 높은 값을 가진 노드를 만나면 그 앞에 넣으면 된다. 반환은 넣을위치 이전노드를 반환해야 insert가 쉽게

가능. 처음에는 first가 비었기때문에 NULL을반환.

더미노드를 만들지 않아, 상당히 까다로워졌다.

first가 맨첫 노드인데, 맨 첫노드를 넣을때 x가 null 이면 first가 첫노드로 생성, 또 x가 first라면 first다음에 노드를

넣어주기 위해 경우의수 하나를또 생성한다. 그 이후엔 반복문을 통해 할 수 있다.

delete를 통해 50이하의 항목들은 모두 지워보았다.

delete작업또한 first가 첫번째 항목이므로 이또한 예외처리를 해주었다.

물론 다른방식으로도 작성할 수있다. 이방식으로 하면 delete함수의 else함수가 쓸모없게된다.

더미노드 방식으로 하면 훨씬 간단해진다.

이전에 했던 많은 경우의수가 사라지고, 그냥 first다음부터 차례대로 넣어주면 된다.

우리가 알고있는 식, 즉 (A+B)*C 와같은 식들은 Infix notation, 즉 중위표기법이라 부른다.

후위표기식은 위의 식을 AB+C* 와 같이 표현한다. 

후위표기식으로 바꾸는 법은 모든 항에 괄호를 씌우고 큰괄호부터 지워나가며 연산자를 그의 오른쪽 괄호와 바꿔주면 된다.

ex) ((A+B)*C) --> (A+B)C* --> AB+C*

왜 이런식이 존재할까.

후위표기식은 계산을 할때 괄호가 없어도 계산 순서가 일정하여 중위표기법 계산보다 후위표기법이 빠르다.

계산기나 컴퓨터 내부에서도 스택을 활용하여 중위표기법을 후위표기법으로 변환하여 연산한다.

아래는 컴퓨터 내부의 후위표기식을 중위표기식으로 계산하는 원리이다.

typedef enum 이라는 열거형 자료형으로 멋들어지게(?) 표현해놓았다.

간단히 말해 피연산자(즉,숫자)는 스택에 들어가게되며, 연산자의 경우 앞선 두개의 숫자를 POP 하여 계산을 하면된다.

이번에는 중위표현식을 입력받아 후위표기식으로 바꾸는 프로그램을 만들어보자.

중위 표기식에는 후위표기식과 다르게 우선순위라는것이 존재한다.

가령 4*2+3 이란 식이 들어왔을때

operand 라면 바로 출력하고, operator 라면 스택에 넣는데

4출력 ->2출력 ->3출력

스택 : * +

이렇게 하면 423*+ 가 된다. 따라서 이식의 결과는 4+2*3이다. 처음 들어온 식과 다르다.

결론적으로 스택에 우선순위가 더 높은 operator 가 있다면 pop해서 출력해야한다.

또 lparen, 즉 개괄호의 경우 우선순위가 스택안(isp)에서와 밖(icp)에서가 다른데, 개괄호는 스택에 들어올때는 우선순위를 가장 높게 만들어 무조건 스택에 들어갈수있게하고, 스택안에서는 오히려 우선순위를 낮게해 폐괄호가 나오기 전까지는 스택에서 나가지 못하게해 다시말해 괄호연산자의 우선순위를 보장하는 것이다.

이번에는 스택을 이용해 미로찾기 게임을 만들어보자.

이는 추후 그래프에서 깊이우선탐색과도 큰 연관이 있는데,

미로는 이와같이 주변 벽을 1, 갈수있는 통로를 0, 그리고 시작점을 (1,1)로 두는 미로로 주어진다.

원리는 이렇다

방향을 8등분하여 각각의 이동하는 좌표를 만들어준다. 우리는 N(북쪽방향)부터 시계방향으로 탐색할 것이다.

시작점해서 출발하면 일단 들린곳은 mark 하게 될것이다.

앞으로 시계방향으로 탐색하며, 0인 부분은 일단 들어가고 본다.

또한 들리자마자 mark하게 될텐데, 이는 mark하지않으면 이전 통로로 이동하는 무한반복 Loop에 빠지게 된다.

에를들어 위와같은 상태에서 direction이 3일때 통로가 발견되었으면, 

이렇게 그지점을 방문표시하고 방향까자 포함해 스택에 넣는다. (다음에 돌아왔을때 저장된 방향부터 다시 탐색하기 위함이다.)

이번에는 이전 큐의 단점을 보완한 원형큐를 구현하되

일정 할당량을 넘게되면 계속해서 새로운 할당을 받아 계속 add할 수 있게

하는 큐를 구현해보았다.

원형큐는 front  = rear 일때 완전히 비어있음을 의미하게 되고,

front = rear+1 이 되는 순간 꽉차있는 것을 의미한다. 

front와 rear사이에는 하나의 공간이 비어있게되는데, 이는 큐가 비어있음과 꽉차있음을 구분하기 위해서이다.

원형큐를 사용하다보면 윗그림과 같은 경우가 발생한다. 이때, 큐를 동적할당으로 capacity를 늘려주고, front와 rear를 newQueue 를 사용해 다시한번 정리하게 된다.

코드를보면 다 똑같은데 COPY부분이 이해하기 어렵다.

단순히 front와 rear를 정리하는것인데, 배열 시작점과 끝점을 인자값으로 줘야해서 헷갈린다.

스택(Stack) : 선입후출 혹은 후입선출 , LIFO 구조

시스템 스택에도 스택개념이 사용

스택구현

void printStack(); 스택출력
void stackFull();  스택이 가득차 더이상넣을수 없음을 알리고, 스택요소들을 출력후 종료
student stackEmpty(); 스택이 비어 뺄수없음을 알리고, 에러값 반환
void push(student item); 스택 push
student pop(); 스택 pop 하고 값 반환

큐(Queue) : 선입선출, FIFO 구조

os의 스케쥴링 및 그래프 탐색 알고리즘 등에 사용

void printQueue();
student queueEmpty();
void addq(student item);
student deleteq();
void queueFull(student item);

함수의 구성은 스택과 동일하다.

하지만 큐는 front와 rear가 존재함으로써 rear에 계속해서 데이터가 들어오게 되면 front 쪽에서 데이터가 빠진 자리는 

낭비되기 마련이다. 따라서 array shifting 을통해 큐가 정말꽉차지 않는 이상 계속해서 배열을 쓸수 있도록

하였다. 이러한 문제점을 원형큐를 통해 더 쉽게 해결할 수 있다.