워밍업클럽CS2기 2주차 발자국: 운영체제

운영체제

CPU 스케줄링

SJF (Shortest Job First)

• Burst Time이 짧은 프로세스를 먼저 실행한다

   

• SJF 문제

  • 어떤 프로세스가 얼마나 실행될지 예측하기 힘듦 => 종료시간 예측 어려움

  • Burst Time이 긴 프로세스는 오랫동안 실행 안될 수 있음

  • BUrst Time이 짧은 프로세스가 계속 추가되면 추가되는 만큼 지연됨

     

RR (Round Robin)

• 프로세스에서 일정시간만큼 CPU를 할당하고 할당 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하고 강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려남

   

• 알고리즘 성능

  • 타임슬라이스(프로세스에게 할당하는 일정시간, 타임퀀텀이라고도 부름) 에 따라 다름

  • 타임 슬라이스가 작은 경우

    컨텍스트 스위칭이 자주 일어나고 타임 슬라이스에서 처리되는 프로세스 처리량보다 컨텍스트 스위칭 처리량이 더 많아짐 => 오버헤드가 더 크다

     

FIFO와 Round Robin 비교

• 평균 대기 시간이 비슷하다면

  • FIFO가 더 효율적

  • Round Robin은 컨텍스트 스위칭이 있어 컨텍스트 스위칭 시간이 더 추가됨

     

MLFQ (Multi Level Feedback Queue)

• RR의 업그레이드 된 알고리즘

• CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택함

  • 우선 순위를 가진 큐를 여러 개 준비한 후 우선순위가 클수록 타임 슬라이스가 작고 우선순위가 낮을수록 타임 슬라이스가 커짐

  • 타임 슬라이스 크기를 오버해서 CPU를 뺏기면 우선순위가 더 낮은 큐로 이동 => 최종적으로 무한대에 가까운 타임슬라이스를 할당 받아 FIFO처럼 연속적으로 작업을 마칠 수 있음.

     

   

프로세스 동기화

프로세스 간 통신

• 한 컴퓨터 내에서 프로세스 간 통신

  • 파일을 이용하는 방법: 통신하려는 프로세스들이 하나의 파일을 읽고 쓰는 것

  • 파이프를 이용하는 방법: 운영체제가 생성한 파이프를 이용해 데이터를 읽고 씀

• 쓰레드를 이용한 방법

  • 한 프로세스 내에서 쓰레드 간 통신

  • 쓰레드의 데이터 영역에 있는 전역변수나 힙을 이용하면 통신가능

• 네트워크를 이용한 방법

  • 운영체제 제공 소켓 통신

  • RPC 통신

공유자원과 임계구역

• 공유자원

  • 프로세스 간 통신할 때 공동으로 이용하는 변수나 파일

  • 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음

  • 컨텍스트 스위칭으로 시분할 처리를 하므로 어떤 프로세스가 먼저 실행되는지 예측하기 어려움 => 연선 결과 예측 어려움 => 동기화 문제 발생

• 임계구역

  • 여러프로세스가 동시에 사용하면 안되는 영역

• 경쟁조건

  • 공유자원을 서로 사용하기 위해 경쟁하는 것

• 상호배제메커니즘

  • 임계구역 문제 해결 방법

  • 요구사항

    • 임계영역엔 동시에 하나의 프로세스만 접근

    • 여러 요청에도 하나의 프로세스의 접근만 허용

    • 임계구역에 들어간 프로세스는 빠르게 나와야함

세마포어

• 상호배제 메커니즘 중 하나

   

모니터

• 세마포어의 단점을 해결한 상호배제 메커니즘

   

데드락

데드락이란?

• 교착상태 (데드락)

  • 여러 프로세스가 서로 다른 프로세스가 끝나기를 기다리다가 아무 작업도 진행 못하는 상태

  • 공유 자원으로 인해 발생

  • 필요조건 (한 가지라도 충족되지 않으면 교착 상태가 발생하지 않음)

    • 상호배제 : 프로세스가 한 리소스를 점유했다면 다른 프로세스에게 공유되면 안됨

    • 비선점: 프로세스A가 리소스를 점유하고 있을 때 프로세스 B가 리소스를 뺏을 수 없어야함

    • 점유와 대기: 어떤 프로세스가 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야함

    • 원형대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음

       

데드락 해결

• 교차상태 회피

  • 프로세스들에게 자원을 할당할 때 어느 정도 할당해야 교착 상태가 발생하는지 파악해서 교착 상태가 발생하지 않는 수준으로 할당함

  • 전체 자원의 수와 할당된 자원의 수로 안정상태와 불안정 상태로 나눔

    • 운영체제는 최대한 안정상태를 유지하려고 자원할당함

    • 불안정상태

      • 사용 가능한 자원이 적어 프로세스 요청 예상 자원을 충족시키지 못하는 상태

      • 교착 상태에 빠질 확률 높음

      • 은행원 알고리즘(각 프로세스가 현재 요청이 예상되는 자원을 구함) 은 비용이 비싸고 비효율적임

• 타이머 이용

  • 가벼운 교착 상태 검출에 이용

  • 일정 시점마다 체크 포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크 포인트로 롤백

  • 억울하게 종료되는 프로세스 발생할 수 있음

• 자원 할당 그래프

  • 무거운 교착 상태 검출에 이용

  • 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태 발생 시 해결

  • 지속적으로 자원할당 그래프 유지 및 검사 -> 오버헤드 발생

  • 교착상태 일으킨 프로세스 강제종료 후 다시 실행 시 체크포인트로 롤백

  • 타이머 이용 시 발생했던 억울하게 종료되는 프로세스 발생 안 함

메모리

메모리 종류

• 레지스터

  • 가장 빠른 기억 장소로 CPU에 위치

  • 컴퓨터가 꺼지면 데이터가 사라짐 => 휘발성 메모리

  • CPU가 계산할 때 메인 메모리 값을 가져와서 계산하고 결과는 다시 메인 메모리에 저장시킴

• 캐시

  • 레지스터와 속도 차이가 많이 나는 메인 메모리가 필요할 데이터를 예측해 가져온 데이터를 저장하는 곳

  • 레지스터와 메인 메모리 사이에 위치

  • 휘발성 메모리

  • 성능의 이유로 여러 개 있음.

• 메인메모리

  • 속도는 빠르지만 비싸기 때문에 실행중인 프로그램만 올림

  • 휘발성 메모리

• 보조저장장치

  • 비휘발성 메모리

메모리와 주소

• 주소

  • 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매김

  • 32bit보다 64bit가 한 번에 처리할 수 있는 양이 많아 속도가 빠름

• 물리주소공간

  • 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소공간

• 논리주소공간

  • 사용자 입장에서 바라본 주소공간

  • 사용자는 물리주소를 몰라도 논리주소로 접근할 수 있음

• 상대주소(논리주소)

  • 컴파일러는 0x0번지라고 가정해서 프로그램을 만듦

• 절대주소(물리주소)

  • 메모리 관리자가 바라본 실제 프로그램이 올라간 번지

• 경계레지스터

  • 하드웨어적으로 운영체제 공간과 사용자 공간을 나눔

  • 메모리 관리라는 사용자 프로세스가 경계 레지스터를 벗어났는지 검사하고 종료시킴

• 재배치 레지스터

  • 프로그램의 시작 주소가 저장되어있음

메모리 할당방식

• 메모리 오버레이

  • 큰 프로그램을 잘라서 당장 실행시켜야할 부분만 메모리에 올리고 나머지는 용량이 큰 하드디스크의 스왑영역에 저장하는 기법

• 스왑

  • 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮김

• 가변분할방식

  • 프로세스의 크기에 따라 메모리를 나누는 방식

  • 프로세스 크기에 맞게 할당되기 때문에 낭비 공간인 내부 단편화가 없음

  • 단점

    • 외부단편화: 연속되지 않은 공간은 새로운 프로세스에게 메모리를 할당할 수 없음

    • 외부단편화가 발생한 공간을 합쳐주는 조각모음을 하면 됨

    • 조각모음을 할 경우 프로세스를 일시중지 해야하고 메모리를 옮겨야해서 오버헤드 발생

       

• 고정분할방식

  • 비연속 메모리할당

  • 프로세스 크기와 상관없이 메모리를 정해진 크기로 나누는 방식

  • 구현이 간단하고 오버헤드가 없음

  • 단점

    • 내부단편화: 분할되는 크기를 조절해서 내부 단편화를 최소화

• 버디시스템

  • 2의 승수로 메모리를 분할해 할당함

  • 가변분할방식과 고정분할방식을 합쳐 단점을 최소화함

  • 프로세스 크기에 따라 할당되는 메모리 크기가 달라짐

  • 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단함

  • 내부 단편화가 발생해도 많은 공간의 낭비가 발생하지 않음