Operating System .md

Ch2. 컴퓨터의 구조와 성능 향상

CPU의 명령어 처리 과정

LOAD mem(100), register 2; //메모리의 100번지에 있는 값을 레지스터 2로 가져온다.
LOAD mem(120), register 3; //메모리의 120번지에 있는 값을 제리스터 3으로 가져온다.
ADD register 5, register 2, register 3; //레지스터 2와 레지스터 3에 저장된 값의 합을 레지스터 5에 저장
MOVE register 5, mem(160); //레지스터 5의 값을 메모리의 160번지로 옮긴다.

CPU가 연산을 하려면 필요한 데이터를 CPU로 가져와 임시로 보관해야 하는데, 이때 사용되는 장소가 레지스터.

제어장치는 명령어를 해석하여 제어 신호를 보내고 CPU 내의 데이터 흐름을 조절하는 역할

버스의 종류

버스는 CPU와 메모리, 주변 장치 간에 데이터를 주고받을 때 사용.

• 제어버스(control bus)

  제어장치와 연결된 버스로, CPU가 메모리와 주변 장치에 제어 신호를 보내기 위해 사용. 메모리와 주변 장치에서도 작업이 완료되거나 오류가 발생하면 제어신호를 보내기때문에 양방향이다.

• 주소버스(address bus)

  메모리 주소 레지스터와 연결된 버스로, 메모리나 주변장치에 데이터를 읽고 쓸 때 위치 정보를 보내기 위해 사용. 단방향

• 데이터버스(data bus)

  메모리 버퍼 레지스터와 연결된 버스로, 데이터의 이동이 양방향으로 이루어진다.

인터럽트

• polling : CPU가 직접 입출력장치에서 데이터를 가져오거나 내보내는 것.

• CPU작업과 저장장치의 데이터 이동을 독립적으로 운영함으로써 시스템의 효율을 높인다.

• Interrupt handler : 인터럽트 발생시 처리 과정이 정의되어 있는 함수

• 인터럽트 벡터

  • CPU는 입출력 관리자에게 여러 개의 입출력 작업을 동시에 시킬 수 있다.
  • 여러 작업이 동시에 완료되었을 때 효율적으로 인터럽트를 사용하기 위함.
  • 인터럽트 벡터에 넘버로 각각의 인터럽트 구분, 완료/비완료 상태를 백터 통째로 CPU에게 전송.

• DMA(Direct Memory Access, 직접 메모리 접근)

  메모리는 CPU만 접근 권한을 가진 작업공간이라 입출력 관리자는 접근이 불가하다.

  따라서 CPU의 허락 없이 메모리에 접근할 수 있는 권한을 DMA라고 한다.

• 동작 과정<입출력>

  1. CPU가 입출력 관리자에게 입출력 명령을 보낸다.

  2. 입출력 관리자는 명령받은 데이터를 메모리에 가져다놓거나 메모리에 있는 데이터를 저장장치에 옮긴다.

  3. 데이터 전송이 완료되면 입출력 관리자는 완료 신호(인터럽트)를 CPU에 보낸다.

  4. CPU는 하던 일을 중단하고 옮겨진 데이터를 처리한다.

  세부과정

  1. 인터럽트가 발생하면 현재 실행 중인 프로세스는 일시 정지 상태가 되며, 재시작하기 위해 현재 프로세스 관련 정보를 임시로저장한다.

  2. 인터럽트 컨트롤러가 실행되어 인터럽트 처리 순서를 결정한다. 이때 여러 개의 인터럽트가 동시에 발생했다면 우선순위를 고려하여 그에 따라 순서를 결정한다.

  3. 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행된다.

  4. 인터럽트 처리를 맞치면 일시 정지된 프로세스가 다시 실행되거나 종료된다.

     입출력 완료 -> 다시 실행 / 메모리 영역 침범이나 오류 -> 종료

병렬 처리(Parallel processing)

• 여러 개의 스레드를 동시에 처리하는 방법을 CPU multi-thread라고 한다.

• CPU에서 명령어가 실행되는 과정

  1. 명령어 패치(Instruction Fetch, IF) : 다음에 실행할 명령어를 명령어 레지스터에 저장
  2. 명령어 해석(Instruction Decode, ID) : 명령어를 해석
  3. 실행(EXecution, EX) : 해석한 결과를 토대로 명령어 실행
  4. 쓰기(Write Back,WB) : 실행된 결과를 메모리에 저장

• 병렬 처리 기법

  • 파이프라인 기법(pipeline) = 하이퍼스레드(Hyper-Thread)

    명령어를 읽어 순차적으로 실행하는 프로세서에 적용되는 기술로, 한 번에 하나의 명령어만 실행하는 것이 아니라 하나의 명령어가 실행되는 도중에 다른 명령어 실행을 시작하는 식으로 동시에 여러 개의 명령어를 실행하는 기법이다.

- 데이터 해저드(data hazard)

  데이터 의존성 때문에 발생하는 문제. 데이터 A를 필요로 하는 두번째 명령어는 앞의 명령어(A)가 끝날 때까지 동시에 실행되어서는 안된다. 

  파이프라인의 명령어 단계를 지연하여 해결.

- 제어 해저드(control hazard)

  if문 혹은 goto문 처럼 분기를 하는 명령에서 발생. 명령어가 순차적으로 실행되지 않고 다른 문장으로 이동하게 되면 현재 동시에 처리되고 있는 명령어들이 쓸모 없어진다. 

  분기 예측이나 분기 지연 방법으로 해결

- 구조 해저드(structural hazard)

  서로 다른 명령어가 같은 자원에 접근하려 할 때 발생하는 문제

• 슈퍼스칼라(super-scalar)기법

  파이프라인을 처리할 수 있는 코어를 여러 개 구성하여 복수의 명령어가 동시에 실행되도록 하는 방식.

  코어를 2개 구성하여 각 단계에서 동시에 실행되는 명령어가 2개.

Ch3. 프로세스와 스레드

프로그램은 저장장치에 저장되어 있는 정적인 상태이고, 프로세스는 실행을 위해 메모리에 올라온 동적인 상태이다.

프로세스의 상태

• 생성 : 프로그램을 메모리에 가져와 실행 준비가 완료된 상태
• 준비 : 실행을 기다리는 모든 프로세스가 자기 차례를 기다리는 상태. 실행될 프로세스를 CPU 스케줄러가 선택한다.
• 실행 : 선택된 프로세스가 타임 슬라이스를 얻어 CPU를 사용하는 상태. 프로세스 사이의 context switching 발생
• 대기 : 실행 상태에 있는 프로세스가 입출력을 요청하면 입출력이 완료될 때까지 기다리는 상태. 입출력이 완료되면 준비 상태로 간다.
• 완료 : 프로세스 종료. 정상종료 exit, 비정상 종료 abort

PCB(Process Control Block)

모든 프로세스는 고유한 PCB를 가진다. 프로세스 생성 시 만들어져 프로세스가 실행을 완료하면 폐기

포인터, 프로세스 상태, 프로세스 구분자, 프로그램 카운터, 우선순위, 각종 레지스터 정보 ...

문맥교환(Context Switching)

CPU를 차지하던 프로세스가 나가고 새로운 프로세스를 받아들이는 작업.

프로세스의 구조

• 코드영역

  프로그래머가 작성한 프로그램. 읽기 전용으로 처리. 자기 자신을 수정하는 프로그램은 존재X..

• 데이터영역

  프로그램이 사용하려고 정의한 변수(전역변수), 파일 등 각종 데이터. 읽기/쓰기 가능

==> 코드영역과 데이터 영역은 프로세스가 실행되기 직전에 위치와 크기가 결정되고 실행되는 동안 변하지 않으므로 정적할당 역역이라고 부른다.

• 힙 영역

  • 동적으로 할당되는 변수 영역 ex)malloc

    main(){
        int sarr[50];
        int *darr;
        
        darr=(int*)malloc(sizeof(int)*50);
        
        free(darr); //메모리 반환
    }

• 스택영역

  부수적으로 필요한 데이터. 복구 위치 등. 사용자에게는 보이지 않는다.

  • 호출한 함수가 종료되면 복귀 주소를 스택에 저장한다.
  • 변수 사용 범위에 영향을 미치는 영역을 구현할 때 사용. 지역변수 저장

==> 스택영역과 힙영역은 프로세스가 실행되는 동안 만들어지는 영역으로, 그 크기가 늘어났다 줄어들기도 하는 동적할당 영역이다.

fork()

실행 중인 프로세스로부터 새로운 프로세스를 복사하는 함수. 커널에서 제공. 시스템 호출의 일종

실행하던 프로세스는 부모프로세스, 새로 생긴 프로세스는 자식 프로세스로서 부모-자식 관계

• 장점

  • 프로세스의 생성 속도가 빠르다.
  • 추가 작업 없이 자원을 상속할 수 있다.
  • 시스템 관리를 효율적으로 할 수 있다.

exec()

기존의 프로세스를 새로운 프로세스로 전환하는 함수.

프로세스의 구조체를 재활용하기 위함이다. 새로운 프로세스를 만들려면 PCB를 만들고 메모리의 자리를 확보하는 과정이 필요하다. 이때 exec() 시스템 호출을 사용하면 이미 만들어진 PCB, 메모리 영역, 부모-자식 관계를 그대로 사용할 수 있어 편리하다.

스레드

프로세스의 코드에 정의된 절차에 따라 CPU에 작업 요청을 하는 실행 단위

• 프로세스 vs 스레드

  프로세스는 약하게 연결(독립적)되어 있는 반면 스레드기리는 강하게 연결되어있다.

  프로세스 : 죽 / 안심 / 케이크 스레드 : 고기 굽기 / 채소 굽기 / 소스 뿌리기

  • 멀티스레드

    프로세스 내 작업을 여러 개의 스레드로 분할함으로써 작업의 부담을 줄이는 프로세스 운영 기법.

  • 멀티태스킹

    운영체제가 CPU에 작업을 줄 때 시간을 잘게 나누어 배분하는 기법.

  • 멀티프로세싱

    CPU를 여러 개 사용하여 여러 개의 스레드를 동시에 처리하는 작업 환경. = 슈퍼스칼라 기법

  • CPU 멀티스레드

    파이프라인을 기법을 이용하여 도잇에 여러 스레드를 처리하도록 만든 병렬 처리 기법.

  ​ *정적영역 : 프로세스가 실행되는 동안 바뀌지 않는 영역

  • fork() 시스템 호출로 여러 개의 프로세스를 만들면 필요 없는 정적 영역이 여러 개가 된다. 이 문제를 해결하기 위해 하나의 프로세스 내에 여러 개의 스레드를 생성하는 멀티스레드는 코드, 파일등의 자원을 공유함으로써 자원의 낭비를 막고 효율성을 향상한다.
  

멀티스레드의 장단점

• 장점
  • 응답성 향상 : 한 스레드가 입출력으로 인해 작업이 진행되지 않더라도 다른 스레드가 작업을 계속하여 사용자의 작업 요구에 빨리 응답할 수 있다.
  • 자원 공유 : 프로세스가 가진 자원을 모든 스레드가 공유하게 되어 작업을 원활하게 진행할 수 있다.
  • 효율성 향상 : 자원의 중복을 막음으로써 효율 향상
  • 다중 CPU 지원 : 2개 이상의 CPU를 가진 컴퓨터에서 멀티스레드를 사용하면 프로세스의 처리 시간이 단축된다.
• 단점
  • 모든 스레드가 자원을 공유하기 때문에 한 스레드에 문제가 생기면 전체 프로세스에 영향을 미친다.

멀티스레드 모델

• 사용자 스레드(user-level thread)

  

  • 사용자 레벨에서 스레드를 구현하기 때문에 관련 라이브러리를 사용하여 구현.

  • 커널 입장에서 하나의 프로세스처럼 보인다. 사용자 프로세스 내에 여러개의 스레드가 존재하지만 커널의 스레드 하나와 연결된다.

  • 라이브러리가 직접 스케줄링하고 작업에 필요한 정보를 처리하기 때문에 context switching X

  • 장점 문맥교환과 같은 부가적인 작업이 줄어들어 속도가 빠르다.

  • 단점

    여러개의 스레드가 하나의 커널 스레드와 연결되기 때문에 커널 스레드가 입출력 작업을 위해 대기 상태에 들어가면 모든 사용자 스레드가 대기하게 된다.

    한 프로세스의 타임 슬라이스를 여러 스레드가 공유하기 때문에 여러 개의 CPU를 동시에 사용할 수 없다.

    보안에 취약하다.

• 커널 스레드(kernel-level thread)

  

  • 커널이 멀티스레드를 지원하는 방식으로, 하나의 사용자 스레드가 하나의 커널스레드와 연결된다.
  • 멀티 CPU 사용 가능, 하나의 스레드가 대기 상태에 있어도 다른 스레드는 작업을 계속 할 수 있다. 보안에 강하고 안정적
  • 문맥교환 오버헤드(단점)

• 멀티레벨 스레드

  • 사용자 레벨 스레드와 커널 레벨 스레드를 혼합한 방식으로 하이브리드 스레드라고도 한다.

CH4. CPU Scheduling

모든 프로세스가 공평하게 작업하도록 하는 것

선점형 스케줄링과 비선점형 스케줄링

• 선점형 스케줄링 "빼앗을 수 있음"

  어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식

• 비선점형 스케줄링 "빼앗을 수 없음"

  다른 프로세스가 빼앗을 수 없는 스케줄링 방식

  구분	선점형	비선점형
  작업 방식	작업을 중단시키고 새로운 작업을 실행할 수 있다.	실행 상태에 있는 작업이 완료될때까지 다른 작업 불가능
  장점	대화형이나 시분할 시스템에 적합	CPU 스케줄러의 작업량이 적고 문맥 교환 오버헤드가 적다
  단점	오버헤드 많다	기다리는 프로세스가 많아 처리율이 떨어진다.
  사용	시분할 방식 스케줄러	일괄 작업 방식 스케줄러
  중요도	높다	낮다

다중 큐

• 준비 상태의 다중 큐

  • 고정 우선순위 방식

    운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식

  • 변동 우선순위 방식

    프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식

• 대기 상태의 다중 큐

스케줄링 알고리즘

선점, 비선점 은 프로세스 기준으로 CPU를 뺏는지 안뺏는지,,

• 비선점형 알고리즘 "안뺏는다"

  FCFS, SJF, HRN

• 선점형 알고리즘 "뺏는다"

  라운드로빈, SRT, 다단계 큐, 다단계 피드백 큐

• 둘 다 가능

  우선순위 스케줄링

1. FCFS 스케줄링 (First Come First Served)

   준비큐에 도착한 순서대로 CPU를 할당하는 비선점형

   • 장점 : 단순하고 공평

   • 단점

     • convoy effect - 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려야한다.
     • 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업효율이 떨어진다.

2. SJF 스케줄링(Shortest Job First)

   준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 할당하는 비선점형.

   • 장점 : 작은 작업을 먼저 실행하기 때문에 시스템 효율성 up, FCFS보다 평균 대기 시간 짧음.

   • 단점

     • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.

     • 공평하지 못하다

       작업시간이 길어 계속 뒤로 밀리는 starvation(아사) 현상 발생.

       ==> aging 으로 해결 가능

3. HRN 스케줄링(Highest Response Ratio Next)

   SJF의 starvation 현상을 해결하기 위해 만들어진 비선점형 알고리즘. 서비스를 받기 위해 기다린 시간 + CPU 사용 시간을 고려하여 스케줄링 하는 방식

   우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간

4. 라운드 로빈 스케줄링 (Round Robin)

   한 프로세스가 타임 슬라이스 동안 작업 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식.

   선점형 알고리즘 중 가장 단순하고 대표적이며, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다.

   

5. SRT 스케줄링 (Shortest Remaing Time)

   SJF + Round Robin. SJF의 선점형 버전. CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.

   • 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산해야 함.
   • 종료시간을 예측하기 어렵고 아사현상 발생

6. 우선순위 스케줄링

   선점/비선점 둘다 가능

   • 문제점
     • 프로세스의 순서를 무시하므로 공평성 위배
     • 아사현상
     • 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드 발생

7. 다단계 큐 스케줄링

   우선순위에 따라 준비 큐를 여러개 사용하는 방식. 우선 순위 별 큐를 생성.

   각 단계의 큐에 라운드 로빈 방식을 사용, 우선 순위에 변화가 없다.

   상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다.

8. 다단계 피드백 큐 스케줄링

   우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식.

   CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 돌아간다.

   우선순위에 따라 타임 슬라이스의 크기가 다르다. 우선순위가 낮을 수록 해당 큐의 타임 슬라이스가 크다.

   결국 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스 == FCFS

Ch5. 프로세스 동기화

공유자원

• 여러프로세스가 공동으로 이용하는 변수, 메모리, 파일 등
• 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.

임계구역

• 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역

• 임계구역 해결 조건

  1. 상호배제(mutual exlusion)

  ​ 임계구역 내에는 한 번에 하나의 프로세스만 존재

  2. 한정 대기(bounded waiting)

  ​ 어떤 프로세스도 무한대기 하지 않아야 한다.

  ​ 즉 특정 프로세스가 임계구역에 진입하지 못하면 안된다.

  3. 진행의 융통성(progress flexibility)

  ​ 한 프로세스가 다른 프로세스의 진행을 방해해서는 안 된다.

임계구역의 해결 방법

임계구역의 기본 코드

#include <stdio.h>

bool lock = false;
int balance;

int main(){
    while(lock==true);
        lock=true;
        balance = balance+10; /* 임계구역 */
        lock = false;
    
}

• 피터슨 알고리즘

  //공유 변수
  bool lock1=false;
  bool lock2=false;
  int turn=1; //두 프로세스가 동시에 lock을 설정하여 임계구역에 못들어가는 상황을 대비하기 위한 장치.
  
  
  //Process 1
  lock1=true;
  turn=2;
  while(lock2==true && turn==2);
  
  /*~~~임계구역~~~*/
  
  lock1=false;
  
  
  //Process 2
  lock2=true;
  turn=1;
  while(lock1==true && turn==1);
  
  /*~~~임계구역~~~*/
  
  lock2=false;

• 데커 알고리즘

  //공유변수
  bool lock1=false;
  bool lock2=false;
  int turn=1;
  
  //P1
  lock1 = true;
  while(lock2==true){
      if(turn ==2){
          lock1=false;
          while(turn==2);
          lock1=true;
      }
  }
  /*~~~~~임계구역~~~~~*/
  turn=2;
  lock1=false;
  }

  1. P1은 우선 잠금을 건다.

  2. P2의 잠금이 걸렸는지 확인한다.

  3. 만약 P2도 잠금을 걸었다면 누가 먼저인지 확인한다.(turn)

     3-1. P1의 차례이면(turn==1) 임계구역 진입

     3-2. P2의 차례이면 4로 이동.

  4. P1은 잠금을 풀고, P2가 마칠때까지 기다린다.(while (turn==2);)

     P2가 작업을 마치면 잠금을 걸고 임계구역으로 진입한다.

• 세마포어

  • 임계구역에 들어가기 전에 스위치를 사용중으로 놓고 들어간다.

  • 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다.

  • 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.

  • 임계구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

  • 세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up신호를 받으면 큐에서 나와 임계구역에 진입.

  • 2개의 공유 자원을 가지고 3개의 프로세스가 작업 할 때 (Rs=2;)

    1. 프로세스 P1은 RS 값을 1 감소시키고 임계구역에 진입한다.
    2. 프로세스 P2도 RS 값을 1 감소시키고 임계구역에 진입한다.
    3. P3은 RS가 0이므로 대기.
    4. P1이 작업을 마치고 V()를 실행하면 RS값은 1이 되고 wake_up신호가 프로세스 P3에게 전달
    5. P3 임계구역 진입

  • 문제점

    세마포어를 잘못 사용하면 임계구역을 보호할 수 없다.

    (1) P() - P() : wake_up신호가 발생하지 않아 무한대기에 빠진다.

    (2) V() - P() : 상호배제가 보장되지 않는 경우

• 모니터

  • 시스템 호출과 같은 개념. 인터페이스만 제공한다.
  • 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
  • 모니터는 요청받은 작업으 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.
  • 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고, 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.

  monitor shared_balance {
      private:
      	int balance=10;  /*shared data*/
      	boolean busy=false;
      	condition mon; /*condition variable*/
      
      public:
          increase(int amount){
  			if(busy==true) mon.wait(); /*waiting in queue*/
              busy=true;
              balance=balance+amount;
              mon.signal(); /*wake up next waiting process*/
          }
  }

  임계구역 보호와 동기화를 위해 내부적으로 상태 변수를 사용한다.

  임계구역의 보호나 프로세스의 동기화가 모니터 내부에서 처리되므로 사용자는 increase()만 호출하면 된다.

Ch6. 교착상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태.

cf) starvation - OS가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

​ 교착상태 - 자연적으로 일어나는 문제

Ch7. 물리 메모리 관리