츈츈's Spring

그래프 정리 

위의 벨로그에 그래프에 대한 개념정리가 매우 잘되어있어서, 읽어보면 좋을것 같다

•  노드 = 정점
•  간선 = 엣지 : 노드 사이를 연결하는 선 (두 노드 사이의 연결관계)

그래프를 구현하는 방법

1️⃣ 엣지 리스트 

엣지 리스트란  엣지를 중심으로 그래프를 표현하는 방법이다. 

엣지리스트는 배열에 출발노드, 도착노드를 저장하여 그래프를 표현한다. 엣지에 가중치가 있는경우 출발노드, 도착노드, 가중치를 저장하여 그래프를 표현한다. 

• 가중치가 없는 경우

가중치가 없는 그래프인 경우,  출발노드와 도착노드만을 저장하면 되므로 배열의 열은 2개면 충분하다. 

1에서 2로 뻗어나가는 엣지는 [1,2] 

2에서 5로 뻗어나가는 엣지는 [2,5] 

이처럼, 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다. 

각각의 행은 두 노드의 연결관계를 나타내고 있으므로 엣지를 의미한다. 

이렇게 노드를 배열에 저장하여 엣지(연결관계) 를 표현하므로 엣지 리스트라 한다. 

• 가중치가 있는 경우

가중치가 있는 경우는 가중치를 저장하는 열을 하나 더 추가하면 된다. 

하지만 엣지리스트의 경우, 특정 노드와 관련된 엣지를 탐색하기는 쉽지 않다. 

특정 노드와 관련된 엣지를 탐색하기 위해선 엣지 리스트 전체를 순회(출발노드와 도착노드 모두 확인해야함) 하며 특정 노드를 찾아야한다. 

따라서 그래프에 N개의 엣지가 있는 경우,  특정 노드와 관련된 엣지를 찾기 위해선 O(N) 이 필요하다. 

이러한 시간복잡도는 엣지의 개수가 많아질수록, 특정 노드와 관련된 엣지를 찾는것은 매우 많은 시간이 걸리게 될 것이다. 

2️⃣ 인접행렬

인접행렬은 엣지 리스트와 반대로 노드를 중심으로 그래프를 표현하는 방법이다. 

노드의 개수를 N 이라고 할때, NxN 크기의 2차원 배열을 이용하여 노드 사이의 관계를 나타낸다. 

• 가중치가 없는 경우

1에서 2로 향하는 엣지를 1행2열에 1을 저장하는 방식으로 표현한다. 

1을 저장하는 이유는 가중치가 없기 때문이다. 가중치가 있는 엣지라면 가중치의 값을 저장하면 된다. 

이처럼 인접행렬로 그래프를 표현하는 것은, 엣지를 노드를 기준으로 표현한다. 

• 가중치가 있는 경우 

인접행렬로 그래프를 나타내는것은, 엣지의 여부와 가중치의 값을  배열에 접근하면 바로 확인 할 수 있다는 장점이 있다. 

예를 들어, 3에서4로 향하는 엣지의 가중치를 알고 싶다면 A[3][4] 의 값을 읽으면 되므로 시간복잡도는 O(1) 이 된다. 

하지만, 특정 노드와 관련되어있는 모든 엣지를 탐색하려면 엣지리스트와 동일하게  N번 접근해야하므로 시간복잡도는 O(N)이 걸린다. 

또한 노드의 개수가 엄청나게 많을 경우, 2차원 배열 선언 자체를 할 수 없는 문제점도 있다.  ( N*N개가 필요한데 N이 10만개만 되어도 엄청나게 많은 메모리공간을 필요로하게 됨) 

3️⃣ 인접 리스트 

인접 리스트는 ArrayList 자료형을 사용하여 그래프를 표현한다. 노드의 개수만큼 ArrayList를 선언한다. 

ArrayList 배열을 만들어, 특정 노드와 연결관계가 있는 노드들을  차례대로 저장한다. 

🧐 ArrayList를 쓰는 이유? 

특정 노드와  연결되어있는 노드들을 저장하는 방식이 인접 리스트 방식이다. 

이런 경우 2차원 배열을 이용해서도 구현 할 수 있을 것이다. 그런데 ArrayList를 이용해서 배열을 만들어 쓰는 이유가 뭘까? 

배열의 경우, 생성과 동시에 크기가 선언되어야한다. 그렇기 때문에 그래프 전체를 파악하여 특정 노드에 연결된 엣지의 개수(노드의 개수와 동일)를 파악 할 수 있다면 크기를 선언해줄 수 있지만, 그렇지 않은 경우 공간을 비효율적으로 사용하게 될 수 있다.

그래서 크기가 가변적인 ArrayList를 이용한 배열을 만들어서 노드를 추가해주는 것이다. 

ArrayList에 대한 내용은 아래 블로그를 읽어보면 될 것 같다

• 가중치가 없는 경우 

가중치가 없는 경우, 노드와 연결되어있는 노드들만 차례대로 저장해준다. 

• 가중치가 있는 경우 

가중치가 있는 경우 자료형으로 클래스를 사용한다. 

도착노드, 가중치를 갖는 클래스를 선언하여 ArrayList에 저장한다. 

public class Node{
int startNode; // 출발노드 
int value; // 가중치 

Node(int startNode,int value){
this.startNode=startNode;
this.value=value; 
}

인접 리스트를 이용한 그래프 구현 방법은, 위에서 제시한 두 방법들이 가지고 있는 문제점들을 보완한다. 

• 특정 노드와 관련된 모든 엣지를 탐색하기 매우 용이하다 (1번의 값을 모두 읽으면 된다) 
• 공간 효율이 좋아  노드의 개수가 많아지더라도 메모리 초과 에러가 발생하지 않는다

그래서 일반적으로 그래프를 구현할때는 인접 리스트를 이용한다. 

🐸 출처 

그래프 개념 정리 벨로그 :  https://velog.io/@kwontae1313/트리와-그래프에-대해-알아보자

노드와 엣지 이미지  : 더북 모두의 인공지능 기초 수학 https://thebook.io/080246/0171/ 

그래프 그림 : Do it! 알고리즘 코딩 테스트 자바 편 

문제 

[백준] 1929번 소수구하기 문제

방법1- 일반적인 소수 구하는 방법으로 풀기  

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static StringBuilder sb;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        // 기본적인 방법으로 소수 판별하기
        sb = new StringBuilder();
        for(int i=M;i<=N;i++){
            checkPrimeNumber(i);
        }

        // 결과 출력
        bw.write(String.valueOf(sb));
        bw.flush();

        br.close();
        bw.close();
    }

    // 소수인지 판별하는 메서드
    public static void checkPrimeNumber(int num){
        if(num<=1) return;
        for(int i=2;i<= Math.sqrt(num);i++){
            if(num%i==0) return; // 소수가 아님
        }
        // 소수인 경우
        sb.append(num).append("\n");
    }


}

방법2- 에라토스테네스의 체 방법 적용하기 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] arr = new boolean[N+1];

        // 배열 초기화
        for(int i=2;i<=N;i++){
            arr[i]=true;
        }

        // 에라토스테네스의 체
        for(int i=2;i<=Math.sqrt(N);i++){
            if(!arr[i]) continue; // 이미 지워진 수는 건너뛰기
            for(int j=i+i;j<=N;j+=i){ // 배수 지우기
                if(!arr[j]) continue; 
                arr[j]=false;
            }
        }

        // 남은수 -> 소수 출력하기
        for(int i=M;i<=N;i++){
            if(arr[i]){
                bw.write(i+"\n");
            }
        }
        br.close();
        bw.flush();
        bw.close();

    }
}

소수를 구하는 방법 3가지를 정리해보고자 한다. 

첫번째는 기본적인 방법이고, 두번째는  첫번째 방법을 약간 변형한것, 세번째는 에라토스테네스의 체를 이용하는 방법이다. 

아무래도 두번째 방법이 시간 복잡도를 고려하지 않는 상황에서는 구현하기 좋기 때문에 상황에 맞게 적절하게 사용하면 될 것 같다. 

✔️ 소수 

자기 자신보다 작은 두 자연수의 곱으로 나타낼 수 없는 1보다 큰 자연수를 소수 라고 한다. 

쉽게 말해, 1과 자기자신 외에 약수가 존재하지 않는 수 이다. 

🐙 첫번째 방법 : N 보다 작은 자연수들로 모두 나눠본다 

어떤 임의의 수 N이 소수인지, 아닌지를 구별하는 가장 쉬운 방법은 N 보다 작은 자연수들로 모두 나눠보는것 이다. 

 1< x <N 의 범위를 가지는 x의 값 중에서 나누어떨어지는 수가 있는지 확인하면 된다. 

아래의 코드와 같이 반복문을 이용하여 직접 값을 나눠보면서 나머지가 0이 되는지 확인해보면 된다. 

🚨 주의할 것은 "num <= 1" 인 경우 대한 처리를 해줘야한다.

왜냐하면 num <=1인 경우, 해당 if문이 없다면  1이하의 수가 들어왔을때 for문이 수행되지 않기 때문에 return true 코드가 실행되어  잘못된 결과가 나오게 된다.  따라서 입력값에 대한 검증이 필요하다는 것에 주의하자. 

public static boolean isPrimeNumber(int num){
        if(num<=1) return false; 
        for(int i=2;i<num;i++){
            if(num%i==0) return false; // 소수가 아님 
        }
        return true; // 소수인 경우 
 }

이 코드의 경우 데이터의 개수가 N개 일때 시간복잡도가 O(N*N) 이므로,  num의 값이 매우매우 큰 수라면 반복문이 실행되는데 굉장히 오랜 시간이 걸릴 것이다. 

시간 제한이 없다면 상관없겠지만,  일반적인 알고리즘 문제의 경우 시간제한이 존재하기 때문에  이런 코드는 비효율적인 코드 이다. 

🐙 두 번째 방법 : √N 이하의 자연수들로 모두 나눠본다. 

소수가 아닌 수는 1과 자기자신 이외에, 서로 다른 두 자연수의 곱으로 표현된다. 

서로 다른 두 자연수, 즉 약수는 항상 쌍으로 존재한다.

따라서  위의 코드처럼 1< x < N의 범위에 있는 모든 자연수를  나눠볼 필요없이, 약수는 쌍으로 존재하기 때문에 둘 중 하나의 값으로 나눠떨어진 것을 확인했다면 굳이 나머지 하나의 값까지 나눠서 확인할 필요가 없다. 

예를들어, 약수의 쌍이 (a,b) 라고 하자. N이 a로 나누어 떨어졌다는건 몫이 b일텐데 굳이 N을 다시 한번 b로 나눠야할 이유가 있을까? 

또한,  서로 다른 두 자연수 이기 때문에 하나의 값은 다른 하나의 값보다 항상 작다. 

예를 들어, 약수의 쌍이 (5,5)  처럼 같은 값이 중복해서 존재 할 수 있을까?  12의 약수를 생각해보자 (1,12) (2,6) (3,4) 처럼 하나의 값은 다른 하나의 값보다 무조건 작거나 같다

N = a x b 일때, a와 b는 N의 약수이다. (N,a,b는 모두 자연수) 

a ≤ b 라 한다면  a = b 인 경우에 a는 최댓값, b는 최솟값을 가지게 된다. 

 a ≤ √N 이며 , a의 최댓값은 √N  이고,  b ≥ √N 이며, b의 최솟값은 √N 이다. 

이것을 수학적인 표현을 이용해서 설명해본다면, 약수의 쌍에서 어떤 하나의 값은, 해당 수의 제곱근의 값보다 무조건 작거나 같다  라고 생각해볼 수 있다. 

 √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면, N의 약수가 존재한다는 뜻이다. 

따라서 반복문의 범위를  N까지 반복 하는 것이 아닌, √N 이하의 자연수들로 나눠서 소수인지 판별해보자 

왜? 약수 중 하나의 값은 반드시 제곱근의 값보다 작거나 같기 때문에, 제곱근의 값보다 작은 범위에서 나눠떨어지는 수가 있다면 제곱근의 값보다 큰 범위에서 나눠떨어지는 수가 반드시 존재한다. 

🪸 제곱근이하의 값만 조사하기 

// 소수인지 판별하는 메서드
    public static boolean isPrimeNumber(int num){
        if(num==1) return false; 
        for(int i=2;i<= Math.sqrt(num);i++){
            if(num%i==0) return false; // 소수가 아님 
        }
        return true; // 소수인 경우 
    }

이 메서드를 이용하여 소수를 판별하면, 데이터의 개수가 N개 일때 시간복잡도가 O (N√N ) 이 된다. 

위의 메서드 처럼 소수인지 판별하기 위해 값을 직접 나눠주는 방식이지만, 범위를 줄여서 더욱 효율적으로 소수인지 판별 할 수 있다. 

하지만, 이 방법의 경우에도 N의 값이 매우매우 커진다면   O (N√N ) 의 시간복잡도로 풀지 못하는 문제가 존재할 것이다. 

그래서 필요한것이 바로 에라토스테네스의 체를 이용한 방법이다. 

🐙 세번째 방법 - 에라토스테네스의 체 

에라토스테네스의 체를 이용하면 일정 범위 안에 있는 모든 소수들을 매우 쉽고, 빠르게 찾아낼 수 있다.

소수란 약수가 오로지 1과 자기 자신인 수 이다. 즉, 1과 자기자신을 제외한 수의 배수가 되는 수는 소수가 아니다.
에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘이다.

임의의 수 n 까지  소수를 구하고자 할 때,  2부터 √N 까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다.

이때 왜 제곱근 까지만 값을 확인하는지는 아래의 글을 참고해서 이해하면 된다. 

n 이하의 모든 수에 대해서 만족하는 이유는  n보다 작은 자연수 중 가장 큰 수인 n-1만 해도  √n   >  √(n-1)  이다.

즉, n보다 작은 수중 소수가 아닌수는 항상  √n 보다 작은 값을 약수로 가지게 되므로,  제곱근의 범위까지만 확인해보면 된다. 

에라토스테네스의 체의 시간복잡도는O(NloglogN) 으로  매우 빠르다고 한다. 왜 그런 시간 복잡도를 가지는지는 아래의 문헌을 참고해서 이해해보면 좋을것 같다.

나무위키- 에라토스테네스의 체 

반복문의 범위를 제곱근까지만 확인하는 이유에 대해서 정리한 글

에라토스테네스의 체 알고리즘 시간복잡도

문제 

https://www.acmicpc.net/problem/11047

동전의 종류와 금액이 주어질때, 해당 동전들을 가지고 금액을 만들기 위한 동전의 최소 개수를 구하는 문제이다. 

동전의 개수가 최소가 되어야하므로 가장 큰 값들로 먼저 계산하면 최솟값을 구할 수 있을것이다. 

import java.io.*;
import java.util.StringTokenizer;

public class P32_동전개수의최솟값 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 동전의 종류
        int total = Integer.parseInt(st.nextToken()); // 금액
        int count=0; // 필요한 동전의 개수

        int[] money = new int[n];
        for(int i=0;i<n;i++){
            money[i] = Integer.parseInt(br.readLine());
        }

        // 가장 큰 금액부터 계산하기
        for(int i=money.length-1;i>=0;i--){
            if(total==0) break;
            count += (total / money[i]);
            total%=money[i];
        }
        bw.write(count+" ");

        bw.flush();
        bw.close();
        br.close();
    }
}

🐟 코드 수정할 부분 

큰 값들로 먼저 몫을 구해야 최소의 개수가 나오기 때문에 반복문을 이용해서 큰값 부터 차례대로 나누어서 계산하는 코드를 작성했다. 

위의 코드로 작성하더라도 상관은 없지만,  아래의 코드를 사용한다면 의미 없는 반복이 있을 수 있다는 문제점이 있다. 

 // 가장 큰 금액부터 계산하기
        for(int i=money.length-1;i>=0;i--){
            if(total==0) break;
            count += (total / money[i]);
            total%=money[i];
        }

예를들어, 아래와 같은 입력이 주어졌다고 하자.

10 4200 // 동전의 종류 수, 금액
1
5
10
50
100
500
1000
5000
10000
50000

위의 for문에 따르면 가장 큰 금액 순서대로 계산이 되기 때문에 50000 → 10000 →   5000 →   1000 →  ..... 순으로 계산이 된다. 

그런데 total= 4200 이기 때문에 4200 보다 큰 50000,10000,5000은 계산 할 필요가 없다. 

결국, total값 보다 큰 값으로는 나눌 수 없기 때문에 단순히 반복문을 이용해서 구현한다면 의미 없는 연산이 반복된다. 

따라서 " total >= money[i]  "  인 경우에만 연산을 수행하도록 조건을 추가해주면 더욱 효율적인 코드가 될 것 같다. 

🐙  수정한 코드 

for(int i=money.length-1;i>=0;i--){
    if(total==0) break; // total값이 0이 되면 바로 종료하기
    else if (total>=money[i]) {
        count += (total / money[i]);
        total %=money[i];
    }
}

🪸 두 코드의 실행시간 비교 

밑에 있는 결과가 첫번째 코드, 위에 있는 결과가 수정 후 코드이다. 역시 수정 후 코드가 조금 더 빠르다. 

물리주소와 논리주소 

• 물리 주소

실제 물리 메모리에서 사용하는 주소 

• 논리 주소 (가상 주소) 

프로세스 내에서 컴파일러에 의해 매겨지는 주소 

논리 주소는 사용자에게 모든 메모리의 주소를 사용하고 있다는 착각과, 프로세스의 코드와 데이터가 0번지 무터 메모리에 적재된다는 착각을 불러일으킨다. 

논리 주소의 물리 주소 변환 

메인 메모리에 엑세스하여 명령어나 데이터를 얻기 위해서는 논리주소를 물리주소 로 변환해야한다. 

이때, 논리 주소를 물리 주소로 바꾸는 방법은 " MMU( 주소 변환 하드웨어) "  를 이용한다. 

MMU가 CPU 외부에 있다면, CPU가 발생시키는 주소는 논리 주소이다. 

하지만 현재 컴퓨터는 대부분 MMU가 CPU 패키지 내부에 존재하기 때문에, CPU 패키지 바깥으로 나오는 주소는 물리주소이다. 

컴파일과 논리주소, 논리 주소가 사용되는 이유 

컴파일러는 사용자가 작성한 프로그램을 논리 주소로 컴파일 한다. 

프로그램이 실행을 시작할때, 운영체제는 프로세스를 생성하고 코드와 데이터를 메인 메모리에 적재한 후 

프로세스 별로 코드와 데이터가 적재된 물리주소의 매핑 테이블을 만들어 놓는다. 

MMU는 이 매핑 테이블을 이용하여 CPU로 부터 출력된 논리주소를 물리 주소로 바꾼다

매핑 테이블과 MMU 덕분에 컴파일러는 논리 주소로 컴파일 하는데 부담이 없고, 운영체제 역시 물리 메모리의 빈공간 아무데나 할당하더라도 상관없다. 

개발자 역시 프로그램이 물리 메모리의 몇번지에 할당되는지 주소를 알 필요도 없어지게 된다. 

메모리 공간을 더욱 효율적으로 사용, 실제 주소를 몰라도 되는 편리함 (보안성↑) 

🚨 출처 

논리 주소 물리주소 변환 이미지 출처: https://cstaleem.com/memory-management-unit-in-os

메모리 계층 구조 

메모리

CPU가 실행할 코드와 데이터를 저장하는 장치를 메모리 라고 한다.

포괄적으로 컴퓨터 시스템 내에 모든 기억 공간들을 지칭한다. 

메모리 계층 구조 

컴퓨터 시스템 내에서 메모리는 매우 다양한 곳에 존재한다. cpu레지스터, 메인 메모리, 보조 기억 장치, 캐시 메모리등의 기억 장치들은 읽기 쓰기의 속도와 용량에 따라 계층 구조를 이루고 있는데 이것을 " 메모리 계층 구조 "라고 한다. 

레지스터에서 하드 디스크로 갈수록 용량은 커지고,  가격은 싸지며, 읽기쓰기 속도는 느려진다. 

• 캐시메모리 

• 캐시 메모리는 더 빠른 cpu의 작업 처리를 위해 도입된 저장장치이다. 
• 캐시 메모리가 있는 컴퓨터에서 cpu는 캐시로부터만  코드와 데이터를 읽어서 실행하기 때문에, 코드와 데이터들은 메인 메모리에서 캐시로 복사 되어야한다.  
• 캐시 메모리는 메인 메모리로 부터 "당장 실행" 을 위해 필요한 코드와 데이터를 복사하여 저장해두는데, 사용자 프로그램과 운영체제 커널을 구분하지 않고 복사한다. 
• 캐시 메모리는 응답 속도와 위치에 따라 여러 레벨로 나누어 사용된다. 
• 멀티 코어환경의 경우, cpu에는 코어별로 내부에 L1,L2 캐시를 두고 모든 코어들이 공유하는 L3 캐시를 가지고 있다. 

메모리 계층 구조의 필요성 

 cpu의 명령 처리 속도에 비해, 메모리의 읽기쓰기 작업은 매우 느리다. 따라서 cpu는 메모리로 부터 명령과 데이터를 가져오는 메모리 엑세스 시간을 단축 시키기 위해 메인 메모리 보다 더 빠른 캐시 메모리를 cpu와 메인 메모리 사이에 설치하여 사용하였다. (off-chip 캐시) 

그런데 cpu의 처리 속도가 더욱 빨라지며 더 빠른 메모리가 필요하였고, 그 결과 캐시 메모리를 cpu 내부에 넣어 cpu의 메모리 엑세스 시간을 단축하였다. (on-chip 캐시) 

메모리 계층구조와 프로그램 실행과정 

응용 프로그램의 실행은 보조기억장치(하드디스크)에서 메인 메모리로 실행파일(또는 필요한 코드나 데이터)를 적재하는것으로 시작한다. 

• 응용프로그램 실행을 위한 코드와 데이터가 복사되는 경로 

       CPU ← L1/L2 ←  L3  ←  메인 메모리 ← 하드디스크  

캐시가 없는 컴퓨터에서 cpu는 메인 메모리로 부터 실행을 위해 필요한 코드와 데이터를 가져오지만, 

캐시가 있는 컴퓨터에서 cpu는 실행을 위한 코드와 데이터를 캐시메모리에서만 확인하기 때문에 반드시 메인 메모리에서 캐시 메모리로 필요한것들을 복사해두어야한다. 

메인 메모리와 캐시

캐시가 있는 컴퓨터에서 CPU는 캐시 메모리로부터만 프로그램의 코드와 데이터를 읽고 실행한다고 했다. 

하지만 캐시는 속도가 빠른 만큼 가격이 비싸고, CPU 내부에 위치하기 위해 크기에 제한이 있다. 따라서 저장용량은 몇KB 밖에 되지 않기 때문에, 당장 필요한 코드와 데이터만을 저장할 수 있다. 

그런데 지금 당장 cpu가 실행해야할 코드와 데이터가 캐시 메모리에 없는 것을 " 캐시 미스 " 라고 한다. 

캐시 미스 상황이 발생하면 캐시메모리의 단계를 내려가며 아래에 있는 캐시에서 원하는 데이터값이 있는지 확인한다. 

L1/L2 그리고 L3 캐시에도 값이 없다면 메인 메모리로 부터 다시 복사하는 과정이 필요하다. 

또한, 실행중인 스레드에서 수정된 데이터는 다시 L3캐시나 메인 메모리에 기록 되어야한다.

메인 메모리와 보조기억장치 

메인 메모리의 용량이 부족해지는 경우, 메인 메모리에 적재된 코드나 데이터의 일부분을 하드디스트나 SSD에 저장하고 메인 메모리에 빈 공간을 확보한다. 

이런식으로 메인 메모리 영역을 보조 기억 장치까지 확장하는 기법을 " 가상 메모리 " 라고 한다. 

메모리 계층화의 성공 이유, 참조 지역성 

캐시는 저장공간이 적기때문에 당장 실행할 코드와 데이터 만을 저장할수 있다. 캐시 미스가 발생하면, 다음 코드나 데이터가 캐시로 복사되는 시간동안 CPU는 기다려야한다. 

그렇다면 캐시가 아무리 빠르더라도 잦은 캐시 미스로 인하여 오히려 프로그램의 성능이 나빠지진 않을까? 

" 메모리를 계층화 하는것이 정말 효율적일까? " 

결론부터 말하자면, 메모리 계층화는 효율적이다

그 이유는" 참조 지역성  "이라는 일반적인 프로그램의 실행 특성에 있다. 

참조 지역성이란 코드나 데이터등이 아주 짧은 시간 내에 다시 사용되는 것을 말한다. 예를들어 반복문의 경우, 짧은 시간내에 동일한 변수들이 반복적으로 사용된다. 이런 코드나 데이터를 캐시에 저장하여 반복문을 수행한다면 매우 빠른 속도로 실행결과를 얻을 수 있다. 이러한 참조 지역성의 종류에는 공간 지역성과 시간 지역성이 있다. 

• 공간 지역성

CPU가  접근한 메모리 공간 근처를 접근하려는 경향 

ex) 프로그램이 실행될때 관련있는 데이터들은 서로 근처에 모여있다. 

• 시간 지역성 

CPU가  최근에 접근했던 메모리 공간에 다시 접근하려는 경향 

ex) 프로그램 내에서 선언된 변수는 한번만 사용되는 경우 보단, 여러번 사용되는 경우가 더 많다 

✔️ 결론적으로 빠른 캐시를 사용함으로써 얻는 이득이,  캐시미스로 인한 오버헤드보다 훨씬 크다 

🚨 참고한 사이트

메모리 계층 구조 이미지

https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EB%A6%AC%20%EA%B3%84%EC%B8%B5%20%EA%B5%AC%EC%A1%B0

캐시 메모리 이미지 참고

https://kyungtaek.tistory.com/100

트리의 지름이란, 트리의 노드 중에서 가장 먼 두 정점사의 거리 혹은 경로를 의미한다. 

트리의 지름을 구하는 방법은 아래와 같다. 

1. 임의의 정점 x에서 가장 먼 정점 y를 찾는다
2. 정점 y에서 가장 먼 정점 z를 찾는다
3. 정점 y ~ 정점 z 사이의 거리를 구한다

이 문제의 핵심은 정점 y ~ 정점 z 가 트리의 지름이 되는 이유를 이해하는 것이다. 

정점 y~ 정점z가 트리의 지름의 양 끝점이 된다는 말의 의미는, 임의의 한점에서 찾은 가장 먼 점은 항상 지름의 양 끝점 중 하나라는 뜻이다. 

따라서 그 점에서 가장 멀리 있는 점은 트리의 양 끝점의 또 다른 한 점 이므로, 두 정점 사이의 거리가 트리의 지름이 되는것이다. 

임의의 한점에서 가장 멀리 있는점은, 트리 지름의 양 끝점중 하나이다. 

임의의 한 점에서 가장 멀리 있는 점은, 항상 트리 지름의 양끝점 중 한점이 될까? 

정점 u와 정점v를 연결하는 경로가 트리의 지름이라고 하고,  임의의 정점x에서 가장 먼 정점은 y라고 할때, 

이 정점들의 관계는 3가지로 표현될 수 있다. 

1. x가 u또는 v인 경우
2. y가 u또는 v인 경우 
3. x,y 그리고 u,v가 모두 다른 정점인 경우 

1,2의 경우를 생각해보자. x에서 가장 먼 점은 y이다.

만약 x가 u또는 v라면, x에서 가장 먼점은 트리의 지름중 나머지 한 점이 된다. 2번의 경우도 마찬가지이다. 

문제는 3번의 경우이다. 

3의 경우 두 가지 경우로 나누어서 생각할 수 있다. 

a) x~y의 경로와 u~v 경로가 한 점이상을 공유하는 경우 (경로가 겹치는 경우) 

d(a,b)를 a에서부터 b까지의 거리라고 하자. 

정점 x에서 가장 먼 정점은 y이다. 이 말의 뜻은 점 t를 기준으로 x에서 가장 멀리 떨어져있는 점이 y라는 뜻이다 

따라서 t~y까지의 거리가 u~t 또는 t~v까지의 거리 보다 크거나 같아야 , x에서 가장 먼 점이 y가 될 수 있다. 

이를 수식으로 표현하면  d(t,y) >= max(d(u,t),d(t,v)) 이다. 

•  d(t,y) > max(d(u,t),d(t,v)) 인 경우 

정점 u에서 가장 먼점은 v이다. 이 말의 뜻은 점t가 갈 수 있는 경로중 가장 멀리 있는 점이 v라는 것인데 , 위의 가정에 따르면 t에서 가장 멀리 있는 점은 y가 되어야한다. 따라서 이 경우는 존재할 수 없다. 

•  d(t,y) = max(d(u,t),d(t,v)) 인 경우 

이 가정이라면 정점x에서 가장 먼 정점은 y가 될 수 있고, 정점u에서 가장 먼 정점은 v가 될 수 있다. 

∴  y는 u 또는 v 이다. 

b)  x~y의 경로와 u~v 경로가  독립적인 경우 

이 그림에서 x~y와 u~v가 독립적인 경로라고 하였는데, 두 경로를 연결해놓은 이유는 트리의 특징 때문이다. 
트리는 사이클이 없이 모든 노드가 연결된 그래프이다. 모든 정점은 루트 노드를 통해 연결된다.
따라서 트리의 어딘가에 이 두 경로가 만나는 공통 조상 노드가 반드시 존재하게된다. 

정점 x에서 가장 먼 정점이 y라면, d5 >= d3+ max(d1,d2) 임을 알 수 있다. 

또한 u에서 가장 먼 점이 v라는 것은 d2 >= d3+ max(d4,d5) 임을 알 수 있다. 

그런데 이 두 식은 동시에 성립할 수 없다. 첫번째 식에 따르면 d5>d2 이고, 두번째 식에 따르면 d2>d5이다. 

따라서 이 경우는 존재할 수 없다. 

결론

(트리 구조에서) 임의의 한 점에서 가장 멀리 있는 점은, 항상 트리 지름의 양끝점 중 한점이다. 

출처

https://velog.io/@zioo/트리의-지름-구하기

스레드 동기화 

다수의 스레드들이 공유 데이터에 동시에 접근하여 쓰기를 수행하면 공유 데이터가 훼손되어 문제가 발생 할 수 있다. 

공유 데이터에 대한 스레드들의 동시 접근시 발생하는 문제를 해결하는 방법이 바로 스레드 동기화이다. 

스레드 동기화란 다수의 스레드가 공유 데이터를 동시에 쓰는 충돌 상황에서, 공유 데이터가 훼손되지 않도록 스레드의 실행을 제어하는 방법이다. 

1. 스레드 동기화의 필요성 

공유 데이터에 동시 접근시 발생 할 수 있는 문제 

왜 다수의 스레드들이 동시에 공유 데이터에 쓰기 작업을 할 때 문제가 발생할까? 

예를들어 아래의 코드를 실행한다고 하자. 

sum= sum+10 

이러한 코드는 사람을 위한 코드로  컴퓨터는 이해 할 수 없기 때문에 컴퓨터의 언어로 바꿔서 알려줘야한다. 따라서 아래의 3개의 기계 명령으로 번역된다. 

mov ax,sum : sum 변수값을 읽어 ax 레지스터에 저장
add ax,10     : ax 레지스터 값을 10 증가
mov sum,ax : ax 레지스터 값을 sum 변수에 저장 

사실상 코드가 한줄이 아닌 세 개의 명령으로 이루어져있는 것이다. 

이러한 명령을 두개의 스레드 t1,t2가 동시에 실행한다고 생각해보자. (초기 sum의 값은 0이라고 가정하자)

먼저 t1이 첫번째 mov 연산을 통해 sum 변수의 값인 0을 ax에 저장했다. 그런데 갑자기 인터럽트가 발생하여 t1 스레드의 작업이 중단되고 t2가 실행되었다고 하자. 

t2는 첫번째 mov연산을 통해 sum의 초기값인 0을 ax에 저장하고, ax에 10을 더하여 다시 sum 변수에 저장한다. 따라서 t2 스레드의 작업이 종료되고 난 후 sum의 값은 10이 되었다. 

그렇다면 일반적인 생각으로는 작업이 중단되었던 t1에서는 t2가 끝난후 다시 시작되는 것이므로, sum=10의 값에 다시 10을 더하여 20이 되겠구나 라고  생각할 수 있으나, t1은 첫번째 mov 연산을 끝낸 이후에  작업이 중단 되었다. 

즉, 변경된 결과가 반영되기 전의 값을 이미 읽어온 상태이므로 t2의 결과가 t1 스레드에는  반영되지 않는다 

따라서 t2의 작업이 끝난 뒤 다시 시작된 t1 스레드의 작업에 의해 최종적으로  sum의 값에는 10이 저장된다. 

만약 위의 상황이 은행계좌에 돈을 입금하는 상황이었다고 생각해보자. 나와 친구가 동시에 나의 계좌에 10억씩 넣는다고 하자.

그렇다면 입금이 끝난 후, 나의 계좌에는 20억이 들어있어야하는데 , 10억만 들어있는 상황인것이다. 분명 둘다 10억씩 입금 했는데도 불구하고 고 10억만 들어있다는것은 누군가의 10억이 증발 했다는 것인데 이건 정말 큰 문제가 아닐 수 없다!! 

이러한 문제는 두 스레드가 동시에 작업을 하며 발생한 충돌상황 때문에 발생하게 되는것이다. 

공유 데이터에 대한 동시 접근 문제의 해결책 

위에서 보았듯이, 여러 스레드가 공유 데이터에 동시에 접근하여 쓰기를 수행할때 충돌이 발생하여 문제가 발생할 수 있다. 

이에 대한 해결책은 하나의 스레드가 공유 데이터를 사용하고 있을때 다른 스레드는 그 공유 데이터를 사용하지 못하도록 막는것이다. 

즉, 공유 데이터에 대한 독점권을 부여해주는 것이다. 

• 임계 구역과 상호배제 

사용자가 작성한 프로그램 중, 공유 데이터를 이용하는 코드 블록을 임계 구역 이라고 한다. 

임계 구역은 공유 데이터를 다루고 있는 코드 블록이므로, 반드시 한 스레드만 배타적 독점권을 가지고 실행 될 수 있도록 관리되어야한다. 그리고 이를 상호배제 라고 한다. 

상호배제의 핵심은 임계 구역에 먼저 접근한 스레드가 도중에 작업이 중단되지 않도록, 작업을 보장해주는 것을 말한다. 

상호배제가 없는 임계구역은 존재 할 수 없다. 반드시 임계구역에 대한 상호배제가 이뤄질 수 있도록 설정해줘야한다. 

이러한 임계구역은 개발자의 판단에 따라 이뤄질 수 있다.  스레드 동기화를 위해 제공되는 멀티스레드 라이브러리나 시스템 호출을 이용하여 작성 할 수 있다. 

2. 상호배제 

상호 배제란 하나의 스레드가 임계구역 전체를 독점적으로 실행할 수 있도록 보장해주는 방법이다. 

상호배제 위치 

임계구역 전후에 상호배제 코드가 작성된다. 

이 두 코드를 각각 임계구역 진입코드(entry코드) , 임계구역 진출코드(exit코드)라고 한다. 

• 일반코드

공유 데이터가 존재하지 않는 코드 영역이다. 이 부분의 코드는 스레드가 동시에 실행되든, 그렇지 않든 큰 영향을 미치지 않는 부분이다. 

• 임계구역 진입코드(entry 코드) - 상호배제 코드 

공유 데이터를 다루는 구역안으로 들어가기 전의 코드로, 이곳에서 먼저 임계구역에서 실행중인 스레드가 있는지 확인한다. 

실행중인 스레드가 있다면 해당 스레드의 작업이 끝날때 까지 현재 스레드를 대기 시키고 , 없다면 작업을 하는 동안 다른 스레드가 들어오지 못하도록 조치를 취한다.  

• 임계구역 코드

공유 데이터를 다루고 있는 코드 영역으로, 한번에 한 스레드만 실행되도록 보장되어야하는 부분이다. 

임계구역은 짧을 수록 좋기 때문에, 임계구역은 최소한의 코드로 만드는것이 좋다. 

임계구역을 넓게 설정하면 스레드들이 작업할때 마다 lock 이 걸리는 시간이 늘어나기 때문에 작업효율이 떨어진다. 

• 임계구역 진출코드 (exit코드) - 상호배제 코드 

스레드가 임계구역의 실행을 마칠때 실행되는 코드로, 대기하고 있는 다른 스레드들이 임계구역 코드를 사용할 수 있도록 조치를 취해야한다. 

상호배제 코드 구현 

상호배제를 하는 방법은 결국 임계구역에 한 스레드만 들어가게 하는 방법이다. 

상호배제를 구현하는 방법에는 소프트웨어적인 방법과 하드웨어적인 방법이 있다. 

소프트웨어적인 방법은 알고리즘 수준에서 제시 된것들 이기 때문에 실제 사용하기에는 많은 문제점이 있다. 

오늘날에는 하드웨어적인 방법을 이용하며, 그중에서 원자명령을 활용하는 방법을 이용하고 있다. 

이제 entry 코드와 exit코드를 어떻게 구현하는지 알아보자. 

 방법1- 인터럽트 서비스 금지하기 

임계구역 안에서는 인터럽트가 실행되지 않도록 하는 방법이다. 

입출력 장치나 타이머가 인터럽트를 걸 수 있도록 허용 해놓고, 임계구역을 실행하는 동안만 CPU가 인터럽트 서비스를 못하도록 한다. 임계구역을 벗어난 이후에는 다시 인터럽트 서비스가 실행될 수 있도록 한다. 

이를 위해 entry 코드에서는 CPU가 인터럽트를 못하도록 명령을 작성하고, exit코드에서는 다시 인터럽트를 허용하도록 기계 명령 작성한다. 

이렇게 하면, 스레드가 임계구역에 있는 동안에는 인터럽트가 무시되기 때문에 임계구역을 독점적으로 사용할 수 있다. 

cli  : entry코드. 인터럽트 서비스 금지 명령 (cli : clear interrupt flag) 
=============
임계구역 코드
=============
stl : exit코드. 인터럽트 서비스 허용 명령 (sti : set interrupt flag)

• cli 명령은 CPU 내부의 인터럽트 플래그(IF)를 0으로 만들어, 인터럽트가 발생해도 CPU가 인터럽트를 무시하고 현재 작업을 수행하도록 한다. 
• sti 명령은 CPU 내부의 인터럽트 플래그(IF)를 1로 설정하여, 인터럽트가 발생하면 CPU가 하던일을 멈추고 ISR(인터럽트 서비스 루틴) 을 실행하게 한다. 

임계구역에 진입하기 전에 인터럽트 서비스를 중지시켜 상호배제가 성공하였다. 하지만 이 방법에는 2가지 문제점이 있다. 

첫번째 문제점은, 임계구역을 실행하는 동안 모든 인터럽트가 무시된다는 것이다. 

만약 임계구역을 실행하는 도중 문제가 발생하여 실행시간이 매우 길어지게 되더라도 인터럽트를 실행할 수 없기 때문에 다른 스레드들은 무한정 대기해야하는 상황이 발생할 수 있다. 

두번째 문제점은, 이 방법은 멀티코어를 비롯한 다중 CPU 환경에서는 사용할 수 없다. 각각의 CPU는 인터럽트 서비스를 수행 할 수 있는데 하나의 CPU에서 인터럽트 서비스를 금지 시킨다 하더라도 다른 코어의 인터럽트 서비스까지 금지시키지는 못한다. 

따라서 작업중인 스레드가 인터럽트로 인해 도중에 중단되지는 않지만, 다른 코어에서 실행되는 스레드가 임계구역에 들어오는것은 막지 못하는 문제가 발생한다. 

 방법2- 원자명령 

원자명령 없이는 상호배제가 근본적으로 불가능하다. 그 이유를 알아보자

• 원자명령없이 lock변수를 이용한 상호배제 -   locking/unlocking 방법 

화장실에 들어갈때 문을 잠그고(lock=1), 나올때 문을 열어 놓아(lock=0) 다른 사람이 들어갈 수 있도록 하는 방법 처럼

임계구역에 들어가기전에 lock 변수의 값을 1로 설정하여 다른 스레드들이 들어오지 못하게 막고, 작업을 끝내고 나오면서 lock 값을 0으로 설정하여 다른 스레드가 작업을 할 수 있도록 한다.  

entry 코드 // locking
=============
임계구역 코드
=============
exit 코드 // unlocking

entry 코드에서 문을 잠그고, 작업을 마치고 나오면서 exit코드에서 화장실 문을 열자 

이를 기계명령어로 작성하면 아래와 같다  

L1:
 mov ax,lock // lock 변수값 읽기
 mov lock,1  // locking
 cmp ax,0    // 문이 잠겼는지 확인한다 
 jne L1      // jump not equal... ax가 0이 아니라면 L1으로 다시 돌아간다
 ==========================
 임계구역
 ==========================
 mov lock,0 // unlocking

임계구역에서 실행중인 스레드가 있다면, 대기중인 스레드는 lock의 값이 0이 될때까지 L1명령을 계속 반복한다. 

하지만 이 방법에도 문제가 있다. 

lock 변수의 값을 읽어오는 과정과 lock변수의 값을 1로 바꾸는 명령이 하나의 단위로 실행되지 않기 때문에 먼저 실행중이던 스레드가 lock 변수의 값을 읽어온뒤 작업이 종료된다면, 이후에 작업을 시작한 다른 스레드에서는 lock의 값이 0이 었기 때문에 임계구역에 진입할 것이다. 

그때 앞선 스레드의 작업이 다시 실행된다면, 이전에 읽어온 값에서는 lock 의 값이 0 이었기 때문에 임계구역으로 진입할것이다. 

그래서 임계구역에서 충돌이 발생하게 된다. 

• 원자명령

이 문제의 해결방법은 lock 변수의 값을 읽어오고 lock 변수의 값을 1로 바꾸는 명령 사이에 컨텍스트 스위칭이 일어나지 않도록 두 명령을 하나의 명령으로 만드는 것이다. 이런 명령을 원자명령 혹은 TSL(test amd set lock)이라고 한다. 

두 명령을 하나의 명령으로 설정한다면 두 명령은 동시에 일어나기 때문에 변수의 값을 읽어오는 과정에 다른 스레드가 끼어들수 없다

L1:
 TSL ax,lock // 원자명령
 cmp ax,0    // 문이 잠겼는지 확인한다 
 jne L1      // jump not equal... ax가 0이 아니라면 L1으로 다시 돌아간다
 ==========================
 임계구역
 ==========================
 mov lock,0 // unlocking

멀티스레드 응용프로그램을 작성할때 개발자가 직접 원자명령을 이용한 상호배제 코드를 만드는것은 무리이다. 

이런건 동기화 라이브러리를 이용하자. 

3. 멀티스레드 동기화 기법

상호배제의 기반 위에, 여러 스레드들이 문제없이 공유 자원을 활용하도록 돕는 멀티스레드 동기화 기법에 대하여 알아보자. 

동기화 기법들은 겉으로 드러나지는 않지만, 임계구역에 진입할때 상호배제를 위해 원자명령을 사용한다. 

이러한 방법들은 멀티스레드 응용프로그램에서 반드시 사용되어야하므로  "동기화 프리미티브" 로 부른다. 

뮤텍스 동기화 기법 

락 변수를 이용하여, 한 스레드만 임계구역에 진입시키고 다른 스레드들은 큐에 대기시키는 방법이다. 

임계구역을 이용중인 스레드가 있다면(락이 잠겨있다면) , 해당 스레드의 작업이 끝날때까지(락이 풀릴때까지) 스레드가 블록 상태로 대기큐에서 잠을 자기 때문에 블로킹 락 또는 수면 대기 락이라고 한다. 

뮤텍스는 임계구역의 실행시간이 짧은 경우 비효율적이다. 왜냐하면 실행시간보다 스레드가 잠자고 깨는데 걸리는 시간이 더 클 수 있기 때문이다. 

스핀락 기법 

뮤텍스와 같이 락 변수를 기반으로 하지만, 대기 큐가 없다. 

락이 잠겨있다면, 락이 풀릴때까지 락 검사를 무한으로 반복한다. 그래서 스핀락은 공격적인 뮤텍스 또는 바쁜 대기 락이라고도 한다, 

스핀락은 단일 CPU환경에서는 매우 비효율적인 동기화 방법이다.  왜냐하면 지속적인 락 검사에 CPU를 활용해야하기 때문에, 새로운 스레드에게 주어진 타임 슬라이스가 끝날때 까지 무의미한 검사가 계속된다. 

하지만 멀티 코어 CPU환경이라면 경쟁을 하는 스레드 각각에게 코어를 분산 시킬 수 있으므로 효과적인 방법이 될 수 있다. 

스핀락 방법의 경우 뮤텍스와 달리, 스레드를 재우고 깨우지 않기 때문에 임계구역의 실행시간이 짧은 경우에 적용하기 좋은 방법이다. 

세마포

세마포는 n개의 자원을 다수의 스레드가 공유하여 사용하도록 돕는 자원 관리 기법이다.

뮤텍스나 스핀락 기법은 한 스레드에게 임계구역을 배타적으로 사용하도록 하는데 목적이 있지만, 세마포는 n개의 자원이 있고 여러 스레드들이 자원을 사용하고자 할때  원활하게 관리하는 것이 목적이다. 

예를들어 12개의 방이 있는 세미나 실이 있을때 현재 8개의 방이 사용중이라고 하자. 

그럼 사용가능한 방의 수는 4개이므로 한 학생이 방을 빌리러 오면 사용 가능한 방의 수를 3으로 고치고 세미나 방을 사용하면 된다.  

만약 12개의 방이 모두 사용중이라면 대기자 수를 1로 고치고 대기줄에서 기다리면 된다. 

여기서 사용가능한 방의 개수는 카운터 변수로, 방을 사용하기 위해 대기하는 학생의 줄은 대기 큐로 나타낸다. 

세마포는 자원을 다 사용한 스레드가 자원을 반납했을때 이를 대기 중인 스레드에게 알려 자원을 사용할 수 있도록 관리해주는 일을 한다. 

세마포가 하는일 

• 세마포는 자원의 개수 n을 알고, 스레드의 요청을 받아 자원의 사용을 허락한다. 
• 자원이 모자랄때 요청한 스레드를 대기큐에서 잠을 재운다. 
• 자원 사용을 끝낸 스레드가 세마포에게 알리면, 대기 큐에서 기다리고 있는 스레드를 깨워 자원을 사용하도록 허락한다. 

세마포의 구성요소 

• 자원 
• 대기 큐 - 자원을 할당 받지 못한 스레드가 잠을 자는 곳
• 카운터 변수 - 사용가능한 자원의 개수를 나타내는 변수. 카운터 변수가 음수이면 자원을 기다리는 스레드의 개수를 의미한다
• P/V연산 
  P연산 자원 요청시, 세마포가 스레드에게 자원 사용을 허가하는 과정 
  V연산은 자원 반환시, 스레드가 세마포에게  자원 사용이 끝났음을  알리는 과정

P/V연산은 wait/signal 연산이라고도 불린다. 

자원을 사용하려는 스레드는 대기 큐에 있든 무한 루프를 돌든 자원을 얻을때까지 대기(wait)하고

자원 사용이 끝난 스레드는 세마포에게 신호를 보내 세마포가 다른 스레드에게 자원을 사용 할 수 있도록 하기 때문이다. (signal) 

세마포의 종류

세마포는 자원을 할당 받지 못한 스레드를 다루는 방법에 따라 2종류로 나뉘며, P/V연산이 다르게 작동한다. 

• 수면 대기 세마포
• 바쁜 대기 세마포 

수면 대기 세마포
 P연산 중 자원 사용을 허락 받지 못한 스레드를 대기 큐에서 잠 재우고, V연산에서 사용 가능한 자원이 생기면 스레드를 깨워 자원 사     용을 허락하는 방법이다. 

바쁜 대기 세마포
P 연산에서 사용을 허락 받지 못한 스레드가 사용 가능한 자원이 생길때까지 무한 루프를 돌면서 검사하다가, V 연산에 의해 사용 가능한 자원이 생기면 P연산을 통과한 후 자원을 획득하는 방식이다. ( 따라서 대기큐가 없다 ) 

 이진 세마포 

세마포는 관리하는 자원이 1개인 경우와 여러개인 경우에 따라 아래와 같이 구분된다. 

• 이진 세마포 - 자원이 1개인 경우
• 카운터 세마포  - 자원이 여러개인 경우 

이진 세마포의 구성요소 

• 세마포 변수 S - 0또는 1의 값을 가지는 변수. 1로 초기화됨 
• 대기 큐
• P/V연산 
  P연산: 자원 사용의 허가를 얻는 과정
  V연산: 자원 사용이 끝났음을 알리는 과정

이진 세마포는 하나의 자원에 대해 여러 스레드가 사용하고자 할때 관리하는 기법으로 뮤텍스와 매우 유사하다. 

동기화 이슈: 우선순위 역전

우선순위 역전이란  스레드 동기화로 인해, 우선순위가 높은 스레드가 낮은 스레드보다 늦게 실행되는 상황을 말한다.

우선순위 역전의 해결방법

• 우선순위 올림
  스레드(T1)가 공유자원을 소유하게 될때 우선순위를 일시적으로 미리 정해진 우선순위(T3)로 높이는 방법이다. 공유 자원에 대한 엑세스가 끝나면 원래 우선순위로 되돌린다. 

• 우선순위 역전 
  스레드(T1)가 공유 자원을 획득하고 실행하는 동안, 높은 순위의 스레드(T3)가 자원을 요청하면 요청한 스레드 보다 높게 변경하여 계속 실행시키고 공유 자원에 대한 사용이 끝날때 원래 순위로 되돌린다. 

4. 생산자 소비자 문제

생산자 소비자 문제는, 유한한 크기의 공유버퍼에 데이터를 공급하는 생산자와 공유버퍼에서 데이터를 읽고 소비하는 소비자가 공유버퍼를 문제없이 사용하도록 생산자와 소비자를 동기화 시키는 문제이다. 

생산자 소비자 문제는 유한한 크기의 버퍼로 인해 발생하므로 유한 버퍼 문제라고도 한다. 

생산자 소비자 문제는 구체적으로 3가지 문제가 있다. 

• 문제1- 상호배제 (생산자들과 소비자들가 공유버퍼에 동시에 접근할때)
• 문제2 - 비어있는 공유버퍼 문제
• 문제3- 꽉찬 공유버퍼 

해결방법

• 상호배제 해결 

공유 버퍼에 대한 동시 접근 문제는 생산자와 소비자뿐만 아니라, 생산자와 소비자가 각각 여러명있는 경우에는 생산자들 사이에 혹은 소비자들 사이에도 발생할 수 있다. 

공유하는 하나의 자원에 대한 배타적 독점권을 위해 뮤텍스나 세마포를 이용하도록 한다. 

• 비어있는 공유 버퍼 문제 해결

소비자 스레드가 공유 버퍼를 읽을때 읽을 데이터가 없다면, 생산자 스레드를 공유 버퍼에 데이터를 기록하고 기다리고 있는 소비자 스레드를 깨운다. 

이 과정은 소비자 스레드가 대기하고, 생산자 스레드가 대기하는 스레드를 깨어나도록 알리는 방식 (wait/signal)이므로 세마포 방식으로 해결한다. 

세마포R을 만들고 세마포R에 대한 P연산은 소비자 스레드가, V연산은 생산자 스레드가 실행한다.

• 꽉 찬 공유 버퍼 해결 

생산자 스레드는 공유 버퍼에 기록하기 전에 반드시 버퍼가 꽉 차 있는지 확인한다. 만약 버퍼가 꽉 차 있다면, 생산자 스레드는 소비자 스레드가 하나의 버퍼라도 비울때까지 기다려야한다. 

소비자 스레드는 버퍼에서 데이터를 읽은 후, 기다리고 있는 생산자 스레드를 깨운다. 생산자 스레드는 깨어나서 버퍼에 데이터를 쓴다. 

이 과정은 세마포W로 구현한다.  세마포W에 대한 P연산은 버퍼에 쓰기 위해 생산자 스레드가, V연산은 소비자 스레드가 실행한다.

생산자와 소비자 알고리즘 

생산자와 소비자를 구현하기 위해선 2개의 카운팅 세마포가 필요하며, 카운터 변수의 최댓값은 공유 버퍼의 개수이다. 

• 세마포R : 읽기 가능한 버퍼의 개수가 0이면 대기 
• 세마포W : 쓰기 가능한 버퍼의 개수가 0이면 대기 
• 뮤텍스M : 생산자와 소비자 두 스레드에 의해 사용(상호배제) 

✅문제

10진법으로 첫번째값으로 주어진다. 이 수를 두번째 값으로 주어진 진법으로 변환하여 출력하는 문제이다

✅풀이

🧁풀이과정 

예를 들어 25를 2진법으로 변환해보자. 

25 / 2  ===> 몫: 12 , 나머지:1 

12/2   ===>  몫:6 ,    나머지:0

6/2     ===>  몫:3 ,   나머지: 0

3/2    ===>  몫:1,    나머지: 1

1/2    ===>  몫:0,    나머지:1 

몫이 0이 되었을때 나머지 값들을 역순으로 읽는다 11001 

10 진법의 수를 몫이 0이 되기 전까지 계속 n 의 값으로 나누면서 나머지를 저장한다. 

그리고 몫이 0이 되었을때 역순으로 값을 읽는다. 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int num = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        while(num>0){

            int k=num%n; // 나머지
            num=num/n;  // 몫

            if(k>=10){ // 나머지 10이상인 경우 문자로 치환
                sb.append((char)(k+55));
            }
            else {
                sb.append(k);
            }
        }

        // 역순으로 출력
        bw.write(sb.reverse().toString());

        bw.flush();
        bw.close();
        br.close();
    }
}

처음에 몫=0 이 되었을때 값을 역순으로 읽기 때문에 스택에서 값을 빼내는 방식으로 생각했었다. 하지만 스택에 넣은 값을 빼내는 것도 좋지만 문자열에 넣고 값을 거꾸로 꺼내는 방식도 괜찮은 것 같다. 

✅정리 

StringBuilder 에서 reverse 메서드를 사용하면 값을 거꾸로 꺼낼 수 있다.  이후 toString 메서드를 이용하여 문자열로 바꿔서 출력하면 된다. 

✅ 문제

✅ 풀이

문제를 보았을때 배열을 조건에 맞는 범위 만큼 자르는 문제였기 때문에 투 포인터를 사용하여 범위만 지정해주고 마지막에 해당 범위의 값들만 출력해주면 되겠다고 생각했다. 

class Solution {
    public int[] solution(int n, int[] slicer, int[] num_list) {


        int start=0; // 시작 인덱스 
        int end=num_list.length-1;   // 끝 인덱스 
        int plus=1; // 증가량 

        switch(n){
            case 1:
                end= slicer[1]; 
                break; 

            case 2:
                start=slicer[0]; 
                break; 

            case 3:
                start=slicer[0]; 
                end=slicer[1];
                break; 

            case 4: 
                start=slicer[0];
                end=slicer[1];
                plus=slicer[2];
                break;  
        }

         // 배열의 크기 계산
        int size = (end - start) / plus + 1;
        int[] answer = new int[size]; 

        // 슬라이싱한 요소들을 answer에 복사
        int idx = 0; // answer 배열의 인덱스
        for(int i = start; i <= end; i += plus) {
            answer[idx++] = num_list[i];
        }
        return answer; 
    }
}

문제의 풀이를 생각해내는 과정은 어렵지 않았으나, answer 배열의 크기를 정하는 부분에서 고민을 했어야하는 문제 같다. 

🍄 answer 배열의 크기를 구하는 방법

answer 배열이 단순히 start~end까지 1씩 증가했다면 배열의 크기는 (end-start) +1 이 되었을것이다. 하지만 증가량이 1이 아닌 N(임의의 자연수)라면 어떨까? 

예를들어 n=2 라고 해보자. n=2일때 선택되는 배열의 개수는 (전체배열의 길이) / n 이다. 2씩 증가한다는 것은 결국 n으로 나눈 몫을 구하는 값과 같다. 하지만 여기서 생각해야할것이 1을 추가하지 않으면  start를 포함하지 않고 start에서 end까지 이동하는 데 걸리는 '단계' 수만 계산하게 된다. 

따라서 (end-start)/plus +1 이 answer 배열의 사이즈가 된다. 

🍀 참고 

class Solution {
    public int[] solution(int n, int[] slicer, int[] num_list) {
        int start = n == 1 ? 0 : slicer[0];
        int end = n == 2 ? num_list.length - 1 : slicer[1];
        int step = n == 4 ? slicer[2] : 1;
        int[] answer = new int[(end - start + step) / step];
        for (int i = start, j = 0; i <= end; i += step) {
            answer[j++] = num_list[i];
        }
        return answer;
    }
}

나의 경우는 n에 따라 구분하기 위해 switch-case 를 사용했지만 삼항 연산자를 이용해 푸는 풀이도 있다.