OS 개념 정리 - 1

OS 정리

세마포어와 뮤텍스

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.

• 뮤텍스(Mutual Exclusion)
  • Lock을 가지고 있는 프로세스/스레드만이 lock해제가 가능하다
  • Locking Algorithm으로 락 가지고 있는 프로세스/스레드가 임계영역 나갈 때만 해제가 가능
  • Busy Waiting(SpinLock) - lock이 얻어질 때까지 계속 체크하는 것
• 세마포어
  • 카운터 변수 ⇒ 운영체제 또는 커널에 저장
  • wait() : 가능한지 체크, 가능하면 카운터변수 -1, signal(): critical section에서 나올때 s를 1 증가
  • 카운터 변수 값 자연수 가능 ⇒ 즉 여러 프로세스/스레드가 동시에 실행 가능함
• 뮤텍스 vs 세마포어?
  • 뮤텍스는 Lock을 가지고 있는 애만이 해제 가능(unlock)
  • 세마포어는 Signaling Algorithm으로, 세마포어를 소유하지 않는 스레드가 signal()을 호출해 세마포어를 해제 가능하다
  • 세마포어-시스템 범위에 걸쳐 있음/ 뮤텍스-프로세스의 범위를 가진다
  • 뮤텍스: busy-waiting
  • 세마포어: busy-waiting(spinlock), sleep-waiting 둘다 구현 가능
• busy waiting
  • spinlock이라고 불리며, lock을 얻을 때까지 계속해서 체크하는 것을 말함
  • 장점: context-switch 하지 않아도 된다, 자원을 얻는데 시간이 적게 소요될 경우 사용
  • 단점: CPU waste ..
• sleep waiting
  • 들어갈 수 없을때 sleep 상태, 즉 wait 상태가 된다
  • critical section을 사용중인 프로세스/스레드가 다 사용했을 때 대기중인 것이 있으면 wakeup 시킨다, 즉 wait → ready 상태가 된다
  • context-switch overhead 가 발생한다
• CPU 1개일때, sleep-waiting 사용, 멀티코어 환경에서는 busy waiting 사용(context switching overhead가 적다)

생산자-소비자 문제

• 프로세스 동기화에 관한 문제
• 공통변수 Buffer 임계구역에 대한 동시진입이 가능하므로 문제가 발생 (생산자-집어넣기, 소비자-빼기) ⇒ 동기화 처리가 필요하다
• 실행 순서에 따라 결과가 달라지는 상황 Race Conditon이 발생
• 해결 방법:
  • 생산자-버퍼와의 관계를 제어하는 세마포 empty: 초기치 버퍼 사이즈 n
  • 소비자-버퍼와의 관계를 제어하는 세마포 full: 초기치 0
  • 작업이 배타적으로 이루어지기 위해 필요한 세마포 semaphore (생산자 아니면 소비자만 공유 자원 이용할 수 있게) : 초기치 1
• 이렇게 semaphore 로 제어를 하게 되면 버퍼 차 있으면 생산자가 기다리고, 버퍼 비어있으면 ㅅ 소비자가 계속 기다리면서 check하는 busy-waiting을 방지할 수 있다

void producer() {
    while(T) {
        produce()
        wait(E)  //자료 넣을 수 있는 빈 공간이 있는지 체크 
        wait(S)
        append()
        signal(S)   
        signal(F)  //자료 넣으면 full 세마포 +1 증가시키기
    }
}

void consumer() {
    while(T) {
        wait(F)    //소비자 쪽에서 자료 있는지 확인 
        wait(S)
        take()
        signal(S)
        signal(E)   //자료 빼내고 난 후 빈자리 증가시키기
        use()
    }
}

데드락(DeadLock)

• 데드락: 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴때 무한 대기에 빠지는 상황
• 데드락의 발생 조건
  • 상호 배제(Mutual Exclusion): 한 번에 하나의 프로세스만 자원을 사용할 수 있다, 다른 프로세스가 사용중인 자원을 사용하려면 release 될때까지 기다려야
  • 점유 대기(Hold & Wait): 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 리소스를 점유하기 위해 대기하고 있는 상태여야 (lock 상태+다른 자원 기다리고 있는 상태)
  • 비선점: 할당된 자원을 강제로 빼앗을 수 없음⇒자원은 그 자원을 점유한 프로세스가 일을 끝낸 후에 release 해야 얻을 수 있음
  • 순환 대기: RAG(Resource Allocation Graph) 상에 사이클 존재해야
• 데드락 해결책
  1. Prevention:
     • 자원 요청을 제한하는 방식으로, 데드락 발생조건 4가지 중 하나라도 발생하지 않도록 하는 것
       • 상호배제 방지: 불가능 (동기화 문제 생김)
       • 점유대기 방지: 모든 자원 처음부터 한꺼번에 요구하고 끝난다음에 unlock ⇒ 성능저하(다른 프로세스는 자원 사용 못하고 wait, 어느자원이 필요한지 모를때(dynamic nature of requesting resource) 사용 불가)
       • 비선점 방지: preempt 당한 프로세스에 문제 발생
       • 순환대기 방지: 리소스에 순서 매기고+요청 시 순차적으로 요청하도록
     • 문제점: 성능 저하, 가장 보수적인 방법, 효율성 떨어트림
  2. Avoidance:
     • 자원 관리자가 자원 요청을 허용할 것인지/말건지 검사
     • safe state: 데드락 발생X, 프로세스가 요청하는 모든 자원을 모두에게 할당해 줄 수 있는 상태
     • safe sequence: 데드락이 발생하지 않는 순서
     • unsafe state: 데드락 발생 가능성이 있는 상황 ⇒ 이때 허용X
     • Banker’s Algorithm 사용 (https://jhnyang.tistory.com/102) - max, allocated, available 을 이용해 데드락을 발생시키지 않도록 자원 요청을 허용/비허용 하는 것
       • Max - 작업 마치기 위해 필요한 최대 리소스
       • Allocated - 현재 할당된 자원
       • Available: 자원 관리자가 현재 가지고 있는 자원
     • 단점: 매번 요청시 복잡한.. 알고리즘 돌려야 함, 필요한 자원의 최대개수 알아야 함 .. ⇒ 오버헤드 커짐
  3. Detection & Recovery:
     • 데드락 발생 시 감지(detection) 후 해결(recovery) (발생 후 처리하는 방식)
     • 감지(Detection): 데드락 발생했는지 여부 탐색 ⇒ 은행원 알고리즘과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악, 아니면 RAG 통해 파악
     • 회복(Recovery):
       • 프로세스를 1개 이상 중단시키기
         • 모든 프로세스 Abort: 데드락 싸이클을 깨지만, 계속 연산중이던 프로세스들도 모두 중단되어 부분 결과가 폐기됨, 즉 다시 재계산 해야함
         • deadlock cycle이 깨질 때까지 1개의 프로세스만 Abort: 이때 abort 대상인 프로세스인 victim 을 정하는 문제(주로 우선순위, 프로세스에 걸린 시간 등을 따짐)
       • 자원 선점하기(Resource Preemption):
         • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에게 할당해 주는 방법
         • Victim 을 구함 ⇒ Victim의 Rollback 문제 : preempt 당한 프로세스의 safe state 로 다시 롤백시키고, 그 시점(rollback point)에서부터 다시 시작해야 함
         • Victim의 Starvation 문제: victim 구하는 과정에서 priority 를 고려하는 방법을 쓰면 starvation 상태 놓인다

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

• 둘 다 처리방식의 일종

멀티코어

• 병렬 처리: 다수의 프로세서로 여러가지 일을 각 코어에서 진행

프로세스와 스레드 차이

https://www.youtube.com/watch?v=1grtWKqTn50

• 프로세스: 프로그램이 메모리에 로드되어 실행된 것/독립적인 개체/별도의 주소 공간에서 실행/다른 프로세스가 접근 불가능/자원 접근하기 위해서는 IPC 필요/각각의 독립된 메모리 영역 갖고 있어 Context Switching으로 인한 성능저하 발생/무거운 작업일 경우 오버헤드 발생
• 스레드: 경량화된 프로세스/스택, 레지스터만 가지며 나머지 공간(힙, 코드, 데이터)은 공유/공유 데이터 접근하는 문제(race condition)

메모리 관리(페이징/세그멘테이션)

1. Address Binding

• 논리적 주소: CPU가 생성하는 주소(instruction 상의 주소), 물리적 주소: 실제 메모리에서의 위치
• 즉 Address Binding이란 어떤 프로그램이 메모리의 어느 위치에(=물리적 주소 몇번째에) 로드될지를 결정하는 과정
  • Compile Time: 주소 이미 확정(논=물), absolute address
  • Load Time: 메모리에 올라오는 시점에 결정, base address 를 더해줌
  • Execution Time: 실행 시(런타임)에 결정 ⇒ 가상 메모리 사용시에 필요

1. Swapping

• 메모리는 크기가 크지 않으므로 프로세스를 임시로 디스크에 보냈다가 메모리에 로드하게 됨
  • Swap out: 메모리 → 디스크
  • Swap in: 디스크 → 메모리
• 페이지 단위로 스와핑 OK

1. 연속 할당

• 프로그램 전체가 하나의 커다란 공간에 연속적으로 할당됨
  • 고정 분할 기법: 고정된 파티션으로 분할(내부 단편화 발생)
  • 동적 분할 기법: 파티션이 동적 생성되며 자신의 크기와 같은 파티션에 존재(외부 단편화 발생⇒ Compaction으로 해결(한쪽으로 빈 공간 모아서 메모리 확보하는 방식))

1. 비연속 할당

• 프로그램 일부가 서로 다른 주소 공간에 할당되는 기법
  • Page: 논리주소 공간에서의 하나의 단위<고정 크기의 블록>
  • Frame: Page 와 같은 크기를 갖는 물리 주소(주기억장치 메모리) 단위<고정 크기의 블록>
  • Segment: 서로 다른 크기의 논리적 단위
• 페이징: 외부 단편화와 compaction의 비효율성을 해결하기 위한 기법, 메모리는 프레임, 프로세스는 페이지라 불리는 고정크기의 블록으로 분리
  • 한 프로세스가 사용하는 공간은 여러 page 로 나뉘어 관리되고/각 page는 frame과 mapping되어 저장
  • mapping 정보는 page table 에 저장 (MMU)

• paging을 그래서 왜 쓰는데?
  • page들이 연속할 필요 없어 외부 단편화 해결 가능
  • swap out이 간단, 할당, 해제 빠르다
  • 코드 쉽게 공유 가능(shared page ⇒ page table에 같은 프레임 넘버 갖고 있다

 

프로세스 상태

인터럽트/시스템 콜

https://velog.io/@hyun0310woo/7.-운영체제-인터럽트에-대해서

• 인터럽트는 CPU가 프로그램을 실행하고 있을때 입/출력 장치나 예외상황이 있을 경우에 CPU에게 알려서 처리하는 기술
• 인터럽트의 필요성: 스케줄러가 preempt 시킬 때/하드웨어 등의 장치 이슈(=파일 읽음 완료)가 발생시 OS에게 알려주고 OS는 waiting→ready로 변경, 예외사항 발생 시 OS에게 알려주고 해당 프로세스 중지, 에러 표시
• 인터럽트 종류
  • 외부 인터럽트: 입출력 인터럽트(입출력 종료 등을 이유로 CPU 수행 요청), 타이머 인터럽트(선점형 스케줄링에 사용)
  • 내부 인터럽트: 0으로 나누기, 오버플로우, 시스템 콜
• 인터럽트 처리 방식
  • CPU에 인터럽트가 걸리면 인터럽트 서비스 루틴(interrupt service routine)
    에 제어권을 넘겨준다. ISR은 인터럽트의 종류별로 인터럽트 핸들러(interrupt handler)
    의 주소가 담긴 테이블인 인터럽트 벡터(interrupt vector)
    를 보고 어떤 인터럽트가 발생했는지 결정한다. 그리고 해당하는 인터럽트 핸들러의 주소로 이동하여 예외처리를 실행한다.
• 시스템 콜
  • 사용자 모드 → 커널 모드로 변환
  • IDT 에 접근, 인터럽트 번호와 핸들러 주소 있음⇒이 80번 system_call 함수에서 시스템 콜 번호에 해당하는 함수를 호출하게 됨⇒핸들러 OK