Youth-tory 유스토리

1주차(thread) 0218

프로세스와 스레드

프로세스

• 사전적 의미

  • "컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램"

  • 메모리에 올라와 실행되고 있는 프로그램의 인스턴스

  • 운영체제로부터 시스템 자원을 할당받는 작업의 단위

    • CPU시간
    • 운영되기 위해 필요한 주소 공간
    • 메모리 영역(Code, Data, Stack, Heap)

• 특징

  • 기본적으로 프로세스당 최소 1개의 스레드(메인스레드)를 가지고 있다.
  • 각 프로세스는 별도의 주소공간에서 실행되며, 한 프로세스는 다른 프로세스의 벼수나 자료구조에 겁근할 수 없다.
  • 한 프로세스가 다른 프로세스의 자원에 접근하려면 프로세스간의 통신(IPC, inter-process communication)을 사용해야 한다.(Ex. 파이프, 파일, 소켓 통신)

스레드

• 사전적 의미

  • "프로세스 내에서 실행되는 여러 흐름의 단위"
  • 프로세스의 특정한 수행 경로
  • 프로세스가 할당받은 자원을 이용하는 실행의 단위

• 특징

  • 스레드는 프로세스 내에서 각각 Stack만 따로 할당 받고 Code, Data, Heap 영역은 공유한다.
  • 스레드는 한 프로세스 내에서 동작되는 여러 실행의 흐름으로, 프로세스 내의 주소 공간이나 자원들을 같은 프로세스 내에 스레드끼리 공유하며 실행된다.
  • 각각의 스레드는 별도의 레지스터와 스택을 갖고 있지만, 힙 메모리는 서로 읽고 쓸 수 있다.
  • 한 스레드가 프로세스 자원을 변경하면, 다른 이웃 스레드(sibling thread)도 그 변경된 결과를 즉시 볼 수 있다.

멀티 프로세스

• 멀티프로세싱이란?

  • 하나의 응용프로그램을 여러 개의 프로세스로 구성하여 각 프로세스가 하나의 작업을 처리하도록 하는 것.

• 장점

  • 여러 개의 자식 프로세스 중 하나에 문제가 발생하면 그 자식 프로세스만 죽는 것 이상으로 다른 영향이 확산되지 않는다.

• 단점

  • Context Switching 오버헤드

    • Context Switching과정에서 캐쉬 메모리 초기화 등 무거운 작업이 진행되고 많은 시간이 소모되는 등의 오 버헤드가 발생하기 된다.
    • 프로세스는 각각의 독립된 메모리 영역을 할당받았기 때문에 프로세스 사이에서 공유하는 메모리가 없어, Context Switching이 발생하면 캐쉬에 있는 모든 데이터를 전부 리셋하고 다시 캐쉬정보를 불러와야 한다.

  • 하나의 프로그램에 속하는 프로세스들 사이의 변수를 공유할 수 없다.

멀티스레드

• 멀티스레드란?

  • 하나의 응용프로그램을 여러 개의 스레드로 구성하고 각 스레드로 하여금 하나의 작업을 처리하도록 하는 것.
  • 웹 서버는 대표적인 멀티 스레드 응용프로그램이다.
  • 윈도우, 리눅스 등 많은 운영체제들이 멀티 스레딩을 기본으로 멀티프로세싱을 지원한다.

• 장점

  • 시스템 자원 소모 감소(자원의 효율성 증대)

    • 시스템콜(프로세스를 생성하여 자원을 할당하는 과정)이 줄어들어 자원을 효율적으로 관리할 수 있다.

  • 시스템 처리량 증가(처리 비용 감소)

    • 스레드 간 데이터를 주고받는 것이 간단해지고 시스템 자원 소모가 줄어든다.
    • 스레드 사이의 작업량이 작아 Context Switching이 빠르다.

  • 스레드는 프로세스 내의 Stack영역을 제외한 모든 메모리를 공유하기 때문에 통신의 부담이 적다.

• 단점

  • 설계 / 디버깅이 까다롭다.
  • 단일프로세스 시스템의 경우 효과를 기대하기 어렵다.
  • 자원을 공유하므로 동기화 문제가 발생한다.
  • 하나의 스레드에 문제가 발생하면 전체 프로세스가 영향을 받는다.

멀티스레드 vs 멀티프로세스

• 멀티프로세스 대신 멀티 스레드를 사용하는 이유?

  • 프로그램을 여러 개 키는 것보다 하나의 프로그램 안에서 여러 작업을 해결하는 것이다.

• 멀티프로세스로 할 수 있는 작업을 멀티 쓰레딩으로 하는 이유?

  • 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리할 수 있다.
  • 프로세스 간의 Context Switching시 오버헤드가 크기 때문.
  • 스레드는 프로세스 내의 메모리를 공유하기 때문에 스레드간 데이터를 주고 받는 것이 간단해지고 시스템 자원소모가 줄어든다.

MergeSort

• 시간 복잡도 O(n lon n)

• list를 이용해 구현하기

x
/**
 * 
 * 병합정렬 - 리스트활용
 *
 */
​
import java.util.ArrayList;
import java.util.Arrays;
​
​
public class Z_MergeSort_List { //쪼개기
    public static ArrayList<Integer> MergeSort(ArrayList<Integer> m) {
        if(m.size()<=1) return m; //종료조건
        
        //반복조건
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right= new ArrayList<>();
        int mid = m.size()/2;  //중간인덱스 찾기
        
        for(int i=0;i<mid;i++) {
            left.add(m.get(i));
        }
        
        for(int i=mid;i<m.size();i++) {
            right.add(m.get(i));
        }
        
//      m.subList(0, mid); 왼쪽 리스트
//      m.subList(mid, m.size()); 오른쪽리스트
        
        left = MergeSort(left);
        right = MergeSort(right);
        
        return merge(left,right);
    }
    
    public static ArrayList<Integer> merge(ArrayList<Integer>left, ArrayList<Integer>right){
        ArrayList<Integer> rst=new ArrayList<Integer>(left.size()+right.size()); //두개를 합친 큰 리스트
        int l=0, r=0;
        
        while(l<left.size() && r<right.size()) { //둘다 원소가 있는 경우
            if(left.get(l) < right.get(r)) {
                rst.add(left.get(l++));
            } else {
                rst.add(right.get(r++));
            }   
        }
        
        while(l<left.size()) { //왼쪽만 남아있는 경우
            rst.add(left.get(l++));
        }
        
        while(r<right.size()) { //오른쪽만 남아있는 경우
            rst.add(right.get(r++));
        }
        
//      while(left.size() > 0 || right.size()>0) {
//          if(left.size()>0 && right.size()>0) {
//              if(left.get(0)<=right.get(0)) {
//                  rst.add(left.get(0));
//                  left.remove(0);
//              } else {
//                  rst.add(right.get(0));
//                  right.remove(0);
//              }
//          } else if(left.size()>0) {
//              rst.add(left.get(0));
//              left.remove(0);
//          } else if(right.size()>0) {
//              rst.add(right.get(0));
//              right.remove(0);
//          } 
//      }
        return rst;
    }
    public static void main(String[] llgs) {
        Integer[] arr = {6,4,8,5,7,2,9,3,0,1};
        ArrayList ll= new ArrayList(Arrays.asList(arr)); //배열을 리스트로 바꾸기
​
        System.out.println(ll); //정렬 전
        
        System.out.println(MergeSort(ll)); //정렬 후
    }
}
​

• 배열을 이용해 구현하기

xxxxxxxxxx
/**
 * 
 * 병합정렬 - 배열활용
 *
 */
​
import java.util.Arrays;
​
public class Z22_MergeSort_Array {
    
    public static void mergeSort(int[] arr, int left, int right) { //쪼개기
        if(right-left <= 1) { //종료파트 : 배열을 실제로 쪼개지 않고, index를 활용해 쪼갠 효과를 준다.
            return;
        } else { //재귀파트
            int mid = (left+right)/2; //중간 index
            mergeSort(arr,left,mid );
            mergeSort(arr,mid,right );
            
            merge(arr,left,mid,right); //mid를 중심으로 영역을 반 나눔
            
            return ;
        }
        
    }
    
    public static void merge(int[] arr, int left, int mid, int right) { //합쳐서 하나의 정렬된 덩어리로 만들기
        int[] tmp = new int[right-left]; //두 영역을 하나로 합칠 큰 배열
        
        int l = left; //왼쪽 배열의 index
        int r = mid; //오른쪽 배열의 index
        int idx = 0; //병합할 배열의 index
        
        while(l<mid && r<right) { //왼쪽 오른쪽 모두 남아있는 경우
            if(arr[l]<arr[r]) {
                tmp[idx++]=arr[l++];
            } else {
                tmp[idx++]=arr[r++];
            }
        }
        
        System.arraycopy(arr, l, tmp, idx, mid-l); // 왼쪽만 남은경우
        System.arraycopy(arr, r, tmp, idx, right-r); // 오른쪽만 남은경우
        
//      while(l<mid) { //왼쪽만 남은 경우
//          tmp[idx++]=arr[l++];
//      }
//      
//      while(r<right) { //오른쪽만 남은 경우
//          tmp[idx++]=arr[r++];
//      }
        
        //합쳐진 temp를 arr에 덮어쓰기.
        //swap이 많이 일어나 arr에 직접하지 않음.
        System.arraycopy(tmp, 0, arr, left, tmp.length);
        
    }
​
    public static void main(String[] args) {
        int[] arr= { 6,4,8,5,7,2,9,3,0,1};
        mergeSort(arr,0,arr.length);//원본 배열을 직접 변경
        
        System.out.println(Arrays.toString(arr));
    }
​
​
}
​