CS 2일차

• ArrayList VS Linked List
• Selection Sort
• TCP UDP
• CPU 스케줄링 알고리즘

가변배열 VS Linked List

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

Selection Sort

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

• 선택 정렬은 unstable 정렬이다. 예를 들어 2 2 1 3 과 같은 배열을 선택 정렬을 하면, 1 2 2 3 이다. 
  이 때, 2 2 1 3 을 B b A C 라 치면, 선택 정렬 결과는 B와 A가 swap 되어 A b B C 가 된다.
  같은 값인 2 2 가 정렬되고 나서 기존의 순서 B b에서 b B 순서로 변경되었기 때문에 선택정렬은
  unstable sort 라고 한다. unstable 하다라는 뜻은 항상 순서가 변경된다가 아닌, 순서 유지를 보장하지 못한다는 뜻이다.
• 최선, 평균 시간 복잡도가 O(n^2) 로 느린 정렬이며, 같은 복잡도인 버벌소트보다는 항상 더 빠른 속도를 지닌다.
  ( swap 의 빈도가 현저히 적기 때문이다 )
• in-place 정렬이므로 공간복잡도는 O(n) 이다,
• i번 째 라운드에 i번 째 idx 부터 탐색하면서 제일 작은 값을 지닌 배열의 인덱스를 갱신고서,
  N-i 자리와 arr[minIdx] 값을 swap 한다. 한 라운드에 swap 이 1번만 일어난다!

TCP

• 연결형 서비스로 가상 회선 방식을 제공한다 - 소켓 통신과 같은 논리적 경로를 구축한다.
• 연결 시에 3 way handshaking 과정, 연결 해제 시에 4 way handshaking 과정을 거친다.
• 흐름 제어, 오류 대응, 혼잡 제어 등 을 제공한다. -> 높은 신뢰성 보장!
• UDP 보다는 속도가 느리다.
• 데이터 전송 시 크기가 무제한으로 가능하다.
• p to p 연결 방식이다.
• 연속성 보다 신뢰성 있는 전송이 중요할 때에 사용하는 프로토콜이다.

UDP

• 비연결형 서비스로 데이터 그램 방식을 제공한다 - ip 기반 통신
• TCP 와 달리 연결, 해제 과정이 없다.
• TCP 와 달리 오류 대응, 제어를 할 수 없고 checksum만을 통해 최소한의 오류만 검출한다.
• 따라서 신뢰성이 낮지만 속도가 빠르다.
• 1 대 1 연결이 아니라 서로 다른 경로로 데이터그램이 독립적으로 전달된다 - 순서보장이 안 된다.
• 크기에 제한이 있다.
• 파일 전송과 같은 신뢰성이 중요한 경우보다, streaming 같은 연속성, 신속성이 중요한 연결에 사용된다.

CPU 스케줄링 알고리즘 목표

• CPU Utilization - 시단당 프로세서 이용률, 한 마디로 CPU를 idle 타임 두지 않을 수록 높다.
• Throughput - 시간당 처리한 작업의 비율, 짧은 작업을 먼저 처리하거나 중간에 인터럽트가 안 걸리면 높다.
• Response Time - 프로세스가 요청되고서 처음 CPU를 할당 받기까지의 대기 시간.
• Running Time - CPU를 사용한 시간.
• Waitting Time - Ready Queue에서 대기한 시간들의 총합. ( Response Time 을 포함한다. )
• Turnarount Time - 실행시간과 반환시간의 총합으로, 프로세스 요청 후 부터 작업의 완료 후 반환까지의 총 시간.
• 시스템 입장에서는 CPU 이용률, 처리율을 높이는 것이 좋고, 사용자 입장에서는 응답시간, 대기시간, 반환시간을 줄이는 것이 좋다.
• CPU 스케줄링 알고리즘은 이러한 목표를 달성하기 위해 단기 스케줄러가 비선점형, 선점형 방식으로 프로세스에게 CPU를 할당한다.

Nonpreemptive Algorithm ( 비선점형 - FCFS, SJF, Priority, HRN )

• 비선점형 방식은 CPU를 프로세스에게 할당되면 작업을 완료할 때까지 독점하는 방식이다.
  ( I/O 인터럽트 발생과 같은 자발적인 양보도 가능 하다. )
• 장점 - Context Switching 이 잘 안일어난다. 일의 순서에 따라 처리율을 높일 수 있다.
            비교적 공정하게 CPU를 프로세스들이 이용할 수 있고, 응답과 반환시간 예측이 용이하다.
• 단점 - Convoy Effect( 짧은 작업이 뒤에 있으면 평균 반환시간이 비효율적이다 )
            Starvation ( 작업 완료 전까지 CPU 독점이기 때문에 우선순위가 낮다면 기아현상이 발생한다 )
            Dead Lock ( CPU 할당을 받은 프로세스가 특정 조건하에 교착상태에 빠지면 자원의 낭비이다 )
• 종류
  • FCFS ( first come first served - FIFO )
    • 일의 중요도, 작업 시간과 관계없이 요청받은 순서대로 처리한다.
    • 평균 응답시간, 반환시간이 길며 Convoy Effect 가 발생할 수 있다 ( 처리율이 낮다 ).
  • SJF ( Shortest Job First - 짧은 작업시간을 지닌 프로세스 우선)
    • 일종의 우선순위 기법으로 작업시간이 짧은 프로세스가 먼저 CPU 를 할당 받는다.
    • CPU Throughtput 을 높일 수 있다.
    • 최소 평균 대기 시간을 보장하지만, Starvation 문제가 발생할 수 있다.
  • HRN, aging (Highest Response ratio Next)
    • 우선순위 기법(SJF)의 기아 현상의 불공평한 상황을 해결하기 위한 기법이다.
    • HRN은 ( Waitting Time + 작업시간 ) / 작업시간 의 값이 높은 프로세스가 CPU를 차지한다.
    • 오래 기다릴수록 aging을 주는 개념이다.

Preemptive Algorthm ( 선점형, SRT, Priority, RR )

 

• 선점형 방식은 특정 조건하에 이미 사용중인 CPU를 빼앗아 선점할 수 있는 방식이다.
• 장점 - 시분할 시스템, deadline 처리에 적합하다. 응답시간이 비교적 빠르다.
• 단점 - 특정 조건하에 잦게 Context Switch가 발생하여 오버헤드가 크다.
            응답, 반환시간 예측이 어렵다.
• 종류
  • RR ( Round Robin )
    • 선점형 스케줄링 방식의 기본적인 개념.
    • Quantum 이라는 작업 시간 단위를 정하고,
      이 단위 시간 만큼 CPU를 프로세스에게 할당하고 후에 여러 조건에 따라 CPU를 재할당 한다.
    • RR방식은 FCFS + Quantum 이다.
    • 응답시간이 빠르고, 비교적 공정한 방식이다.
    • Quantum을 잘 정해야한다. 너무 길면 FCFS 방식과 유사하고, 너무 짧으면 오버헤드가 발생한다.
  • SRT ( Shortest Reamaining Time - 짧은 잔여 작업시간을 지닌 프로세스 우선)
    • 프로세스가 대기큐에 들어올 때마다 이미 CPU를 할당중이라도 잔여 작업시간을 비교하여
      제일 짧은 잔여 작업시간을 지닌 프로세스가 CPU를 차지한다.
      ( SRT도 RR 처럼 시간 단위만큼 처리 후 잔여 작업시간 비교하는 설명도 있다... )
    • Starvation 문제가 발생할 수 있으며 CPU 사용 시간을 정확히 예측하기 어렵다.
  • Priority
    
    • 작업 큐에 우선순위와 함께 프로세스를 넣고, CPU 사용중인 프로세스 보다 높은 우선순위가
      들어오면 선점한다.
    • 기아현상이 발생할 수 있지만 aging 기법으로 해결 가능하다!