CS 1일차

• Array VS Linked List
• Bubble Sort
• HTTP - GET vs POST
• 스케줄러

Array

• 논리적 저장 순서와 물리적 저장 순서가 일치.
• 특정 자료형들이 메모리 공간에 연속적으로 존재.
• 인덱스를 통해 .Random Access 가능 -> O(1)
• 삽입, 삭제 시에는 해당 인덱스 이후의 자료들이 Shift 됨 -> O(n)
• 일반적으로 Array 선언 시, Compile Time 에 정적 메모리 할당.
  + 가변 배열이 아닌 이상, 선언시의 Array Size 는 immuable.
  => 메모리 공간 활용 제약, 크기 초과시, 변경 시에 다른 주소에 재할당 필요!

Linked List

• 저장 공간상에 자료들이 흩어져 있고, 각 노드가 자신의 다음 노드의 주소를 지닌다 -> 자료 외에 별도의 포인터 저장 공간 필요.
  => 논리적 저장 순서와 물리적 저장 순서가 불일치.
• 첫 노드의 주소만을 저장 했다가 필요 시 Sequential Access 를 통해 접근.
• 검색, 삽입, 삭제 시 모두 O(n) 소요.
  => 해당 위치를 찾는 데에 O(n) 소요되고, Array와 달리 Shift는 불필요하다.
  => 따라서, 삽입과 삭제가 맨 앞 노드에서만 이루어지게되는 특성의 링크드리스트라면, 삽입 삭제는 O(1)이 될 수 있다.
• Run Time 에 동적 메모리 할당

Array VS Linked List

• 데이터 접근이 많이 일어나는 경우에는 배열 사용.
• 삽입 삭제가 많이 일어나는 경우에는 링크드 리스트 사용.
• 가변 배열 - 벡터, 리스트와 같은 자료형으로, 배열의 공간 활용 제약의 단점을 극복!
  => 공간에 여유가 있으면, append()를 사용하여 자료형 1개 크기 만큼 동적으로 사이즈 할당이 가능하고,
  공간 활용에 제약이 생기면, resize()를 통해 크기 재할당 후 모든 원소를 이주할 수 있다(비용이 발생).

Bubble Sort

void bubbleSort(int arr[], int n){
    int tmp;
 
    for(int i=0;i<n;++i){
        for(int j=1;j<n-i;++j){
            if(arr[j-1] > arr[j]){
                tmp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

• 최선, 평균, 최악의 시간복잡도가 모두 O(n^2)로 느린 정렬 기법이지만, 코드가 직관적이고 간단하다.
• in-place 기법이기 때문에 공간복잡도는 O(n)이다.
• 정렬시에 동등한 원소에 대하여 정렬 전과 후의 순서가 일치함을 보장하는 Stable Sort 이다.
• i번째 라운드에, 첫번 째 원소부터 N-i 번째 원소까지 순서대로 비교하면서, 제일 큰 원소를 찾아 N-i 에 위치시킨다.
• 평균 시간 복잡도 O(n^2)인 삽입, 선택 정렬에 비해 swap 연산이 비교적 많이 발생한다.

GET

• 데이터 조회시에 사용 되는 메소드. 아래와 같은 특성들 때문에 조회시에만 사용하도록 권장된다.
• URI, URL 에 쿼리스트링을 추가하여 데이터를 전송한다. ( 패킷의 헤더에 데이터를 포함하고, 바디는 빈 상태로 요청 )
  => 주소창에 데이터가 노출이 되는 특성 -> 보안에 취약하고 주소 제약으로 인해 아스키 코드만 사용 가능, 길이 제한 등이 있다.
• 주소창에 데이터 정보가 있어 브라우저의 history, bookmark, cache 에 저장이 가능하다.
  => 결과가 idempotent( 여러번 시행해도 결과가 일정함 ) 하기 때문에 가능!
  => 브라우저 캐시에 저장이 된 상태라면, 재요청시 재전송이 이루어지지 않음.
  => 따라서 일반적으로 POST 보다 속도가 빠르다.
• 조회여도 비밀번호와 같은 민감한 정보를 전송하는 일은 없어야 한다. 주소창과 히스토리에 플레인텍스트로 그대로 남기 때문!

POST

• 주로 새로운 데이터를 생성할 때 사용. PUT, PATCH, DELETE 메소드들이 있지만 POST의 Request Body를 통해 다 실행 가능.
• URI, URL 에 정보 노출 없이, POST의 Request Body 에 필요한 데이터를 작성하여 전송한다.
  ( 패킷의 헤더에 content-type 을 명시하고, 바디에 내용을 포함하여 요청 )
  => 주소창에 데이터 정보가 없어서 제약없는 크기, 형식을 활용할 수 있고, SSL을 사용하여 보안을 강화할 수 있다.
• 기록에 데이터 정보도 남지 않고, 메소드 결과가 idempotent 하지 않기 때문에 캐시될 수 없어서, 재요청시 재전송이 이루어진다.
• 데이터에 제약이 없으므로 대용량 업로드와 같은 파일 전송도 가능하고, 주소에 노출되지 않기 때문에 민감한 정보 전송에 유리하다.
  ( 여전히 부가적인 보안 장치는 필요하다.)

스케줄러

운영체제에서 어떠한 프로세스에게 CPU와 메모리 공간을 할당할 지를 결정하는 커널의 모듈.

프로세스 상태도에서 어떠한 프로세스를 어떠한 상황에서 자원을 할당하고 해제할 지를 결정해 주며,

각각의 프로세스가 어느 상태에 있고 어디로 이동할 지에 따라서 장기, 중기, 단기로 나뉜다.

 

장기 스케줄러

• new -> Ready 과정 조절.
• 현재 메모리에 너무 많은 프로세스가 올라가 있다면, 새 프로세스는 메모리(Ready Queue)가 아닌 디스크 영역에 임시로 저장된다.
• 현재 메모리 영역에 어느 정도의 프로세스 수(degree)가 존재하는 지를 확인하며, 
  여유가 생기면 디스크 영역에 존재하는 새 프로세스들 중 어떤 프로세스를 메모리 상(Ready Queue)에 등록 할 지 결정한다.
• 디스크 -> 메모리 이동이기 때문에 속도가 느리며 일반적으로 수십 초 내지 수 분 단위로 가끔 호출된다.
• 시분할 시스템에서는 장기 스케줄러 없이 곧 바로 메모리에 올라가서 Ready 상태가 된다.

단기 스케줄러

• Ready -> Running -> Wait -> Ready 과정 조절.
• CPU 스케줄러로서 어떤 프로세스가 CPU를 할당 받을지를 미리 정한 다양한 스케줄링 알고리즘을 통해 결정한다. ( Context Switch )
• 매우 빈번하게 호출 되기 때문에 속도가 충분히 빨라야 한다.

중기 스케줄러

• Wait -> Suspended Wait -> Wait, Ready -> Suspended Ready -> Ready 과정 조절.  
• 메모리 상에 프로세스가 너무 많이 올라가 부족할 때, 특정 메모리를 Swap out 하여 디스크 영역에 임시 저장 후 메모리에서 해제한다. 
• 현재 메모리 영역에 어느 정도의 프로세스 수(degree)가 존재하는 지를 확인하며, Suspend 상태에 있는 프로세스를 메모리상에 적재하는 것을 결정한다. ( Swapping )
• Wait 상태에 있는 블럭된 프로세스는 I/O 작업이 완료되면 스스로 Reday 로 이동할 수 있지만, Suspended 상태에 있는 프로세스들은 중기 스케줄러를 통해서만 메모리상으로 swap in 할 수 있다.