Jun 개발노트

운영체제 05

2020-03-09

운영체제 5

1. 운영체제 프로세스 관리 중에서 가장 중요한 두가지 기능

  • 프로세스 스케줄링
    • 레디큐에서 대기중인 여러 프로세스 중에 누가 cpu 서비스를 받게 할것인가?
  • 프로세스 동기화
    • Context 스위칭 단위가 Thread이기 때문에 Thread 동기화라고 불러도 된다.
    • 프로세스들은 독립적인 것보다는 협조적인 관계다(같은 자원을 공유한다 => 다른 프로세스에 영향이 발생한다.)
    • 은행문제
      • 공통된 자원 : 은행 계좌
      • 프로세스 : 입금 / 출금
      • 공통된 자원을 동시 업데이트를 하게 되면 임계구역 문제 발생 (공통된 자원이 업데이트로 인해서 발생)
      • 해결책 : 오직 한 쓰레드만 접근, 진입 결정은 유한 시간 내에, 어느 쓰레드도 유한 시간내에
    • 순서문제
      • 문제1 : cpu 스케줄링에 상관없이 s1, s2 중 s2가 먼저 실행되게 만들어라
      • s1 앞에 acquire를 통해 permit number를 변경하여 s1이 실행되지 않게 한다
      • s2 뒤에 release를 통해 permit number를 변경하여 s1을 process를 깨어서 실행시킨다.
      • 문제2 : cpu 스케줄링에 상관없이 s1, s2, s1, s2.... 순서대로 실행되게 만들어라
      • s, s1, s2 세마포를 만들어주고 s1 실행이 되고 s1.acquire(); s2.release(); => s1을 블락 시키고 s2를 실행
      • s2뒤에는 s2.acquire(); s1.release(); => s2를 블락 시키고 s1를 실행
      • s를 문제 1처럼 세마포를 설정해준다.
    • 세마포로 임계구역 문재 해결(소프트웨어 도구)
      • acquire / release 함수와 조건식을 통하여 세마포 안에 있는 큐로 프로세스 조절한다.
      • 조건식 => permit Num 변경을 통해 프로세스가 두개가 동시에 실행될수 없게 만들었다.
    • 결론
      • 프로세스로 통해 공통된 자원이 올바른 값이 나오게 만드는것 (은행문제)
      • 프로세스가 우리가 원하는 대로 작동 (순서문제 1, 2)

2. 전통적 동기화 예제

  1. 생산자-소비자 문제

    • 생산자가 데이터를 생산하면 소비자는 그것을 소비
      • 예) 컴파일러 -> 어셈블러, 파일서버 -> 클라이어트, 웹서버 -> 웹 클라이언트
      • 생산자와 소비자의 속도차이로 인해 창고(버퍼)에 저장하여 생산자는 생산해서 창고에 저장, 소비자는 창고에서 꺼내어 소비
      • 컴퓨터 속에서는 창고 => 버퍼라고 하며, 메모리 상에 위치해 있어서 용량은 한정되있다.
      • 버퍼가 가득차면 생산자는 버퍼에 담지 못하고
      • 버퍼가 비어있다면 소비자는 버퍼에서 꺼내지 못한다.
    • 잘못된 결과 도출
      • 실행불가 또는 생산된 항목의 숫자 !== 소비된 항목의 숫자
      • 이유 : 공통변수 업데이트로 인해 임계구역에 도달
      • 해결방법 : 세마포를 통해 동시에 접근못하게 상호배타 적용
    • Busy-wait 방지(퍼포먼스 증가)
      • Busy-wait이란 ? 버퍼가 비었는지, 가져올수잇는지 계속해서 확인하면 기다리면서 메모리의 자원을 소비하는 거다
      • 해결법 : 세마포를 만들어, 버퍼가 가득차잇다면, acquire로 생상자를 세마포 큐로 넘겨 기달리게 하고 버퍼가 0이면 다시 release를 통해 꺠워 생산한다(소비자도 동일)
  2. 공유 데이터베이스 접근

    • 데이터베이스에 접근하는 두개의 프로세스 (Read, Write)
    • 공통된 자원은 데이터 베이스지만, Read, Write를 세마포를 통해 한번에 하나의 프로세스만 접근하는것은 비효율적이다.
    • Read 같은 경우, DB를 수정하지 않기 때문에, 공통된 자원은 언제나 일정한 상태를 유지하고 있다.
    • Write는 정보를 수정하기 때문에, 세마포를 통해 프로세스를 제한해줘야 한다.
    • Read가 프로세스가 있다면 Write는 접근못하게 한다. Write 프로세스가 있다면, Read는 대기하여 정보의 일관성을 유지한다.
  3. 생각하는 철학자 문제

    • 조건 : 5개의 철학자, 5개의 젓가락 2개의 젓가락을 통해 식사할수있다.
    • 세마포의 초기값 : 1(젓가락)
    • 결과 : 일정시간이 지나면, 결과를 리턴 못함
    • 이유 : 모든 철학자가 배가 고파서 젓가락을 들어서, 다른 젓가락이 내려질때까지 대기하면, 굻어서 죽음(starvation) => Deadlock
    import java.util.concurrent.Semaphore;
    class Philosopher extends Thread {
      int id; // philosopher id
      Semaphore lstick, rstick; // left, right chopsticks
      
      Philosopher(int id, Semaphore lstick, Semaphore rstick) {
        this.id = id;
        this.lstick = lstick;
        this.rstick = rstick;
      }
      public void run() {
        try {
          while (true) {
          lstick.acquire();
          rstick.acquire();
          eating();
    
          lstick.release();
          rstick.release();
          thinking();
        }
        }catch (InterruptedException e) { }
      }
    
      void eating() {
        System.out.println("[" + id + "] eating");
      }
      
      void thinking() {
        System.out.println("[" + id + "] thinking");
      }
    }
    
    class Test {
      static final int num = 5; // number of philosphers & chopsticks
      public static void main(String[] args) {
        int i;
        /* chopsticks */
        Semaphore[] stick = new Semaphore[num];
        for (i=0; i<num; i++)
        stick[i] = new Semaphore(1);
        /* philosophers */
        Philosopher[] phil = new Philosopher[num];
        for (i=0; i<num; i++)
        phil[i] = new Philosopher(i, stick[i], stick[(i+1)%num]);
        /* let philosophers eat and think */
        for (i=0; i<num; i++)
        phil[i].start();
      }
    }
    

3. 교착상태

  • 동기화를 하다보면 교착상태로 빠른다.
  • 프로세스는 실행을 위해 여러 자원을 필요로 한다.
  • 운영체제는 소프트웨어 / 사용자가 하드웨어(자원)를 사용하려고 할때 배분해준다. 순서를 정해준다. 운영체제의 위치
  • 교착상태 필요조건(조건을 모두 충족하면, 일어날 가능성 있음, 하나라도 충족이 안되면, 일어날 가능성 제로)
    • 상호배타 : 1번 프로세스가 1번 하드웨어를 사용하면 2번 프로세스는 접근 못함
    • 보유 및 대기 : 철학자 문제처럼 다른 자원을 사용하려고 계속해서 대기하고 있다.
    • 비선점 : 다른 프로세스가 점유한 자원을 뺏어오지 못한다.
    • 환영대기 : 철학자 문제처럼 꼬리물기 / 원형의 형태로 이루어져 교착상태의 빠질수도 있다.
  • 자원할당도
    • 동일한 자원은 여러개의 인스턴스로 구성될수있다. (프린터는 2개 그러면 인스턴스 2개)

    • 자원을 요청 사용 반납순으로 이용하고 아래같은 그림으로 나타낼수있다. 자원할당도

    • 자원할당도가 원형으로 된다면 데드락이 발생가능성이 높음 데드락

    • 철학자 문제 데드락 해결 방법

      • 자원할당도를 원에서 비원으로 변경
      • 짝수번은 오른쪽 / 왼쪽 순으로 젓가락을 들게하고
      • 홀수번은 왼쪽 / 오른쪽으로 바꾼다.
      public void run() {
        try {
          while (true) {
          if(id % 2 == 0) {
            rstick.acquire();
            lstick.acquire();
          }else{
            lstick.acquire();
            rstick.acquire();
          }
          eating();
      
          lstick.release();
          rstick.release();
          thinking();
        }
        }catch (InterruptedException e) { }
      }
      

4. 결론

  • 운영체제에서 가장 중요한 프로세스 관리 그 안에서 두 가지 역할 스케줄링 및 동기화
  • 공통변수 및 자원에 대해 세마포와 자원활동도를 이용해 동기화를 하자