태양 만세!

3.1 스케줄링 성능 평가 기준

• 스케줄링 성능 평가 기준
  • 평균 대기시간
    • 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균값

• 평균 반환시간
  • 각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간의 평균값

       

-> 각 프로세스들의 대기/반환시간을 알아야….

3.2 다양한 스케줄링 알고리즘

• FCFS 스케줄링
  • FCFS(First-Come First-Served) 스케줄링
    • 비선점 스케줄링 알고리즘
    • 준비 큐에 도착한 순서에 따라 디스패치
  • 장점
    • 가장 간단한 스케줄링 기법
  • 단점
    • 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음
    • 프로세스들의 도착 순서에 따라 평균 반환시간이 크게 변함

         

• SJF 스케줄링
  • SJF(Shortest Job First) 스케줄링
    • 비선점 스케줄링 알고리즘
    • 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상된 것을 먼저 디스패치

         

  • 장점
    • 일괄처리 환경에서 구현하기 쉬움
  • 단점
    • 실행 예정시간 길이를 사용자의 추정치에 의존하기 때문에 실제로는 먼저 처리할 작업의

      CPU 시간을 예상할 수 없음

         

• SRT 스케줄링
  • SRT(Shortest Remaining Time) 스케줄링
    • 선점 스케줄링 알고리즘
    • 실행이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치
  • 장점
    • SJF보다 평균 대기시간이나 평균 반환시간에서 효율적
    • 대화형 운영체제에 유용
  • 단점
    • 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등 SJF보다 오버헤드가 큼

      (문맥교환에도 시간 소요)

         

• RR 스케줄링
  • RR(Round Robin) 스케줄링
    • 선점 스케줄링 알고리즘
    • 준비 큐에 도착한 순서에 따라 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한
    • 시간 할당량 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치
  • 장점
    • CPU를 독점하지 않고 공평하게 이용
    • 대화형 운영체제에 유용
  • 단점
    • 시간 할당량이 너무 크면 FCFS 스케줄링과 같아짐
    • 시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함

         

• HRN 스케줄링
  • HRN(Highest Response Ratio Next) 스케줄링
    • 비선점 스케줄링 알고리즘
    • 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
    • 예상 실행시간이 짧을수록, 대기시간이 길수록 응답비율이 커짐

         

      *응답비율 = (대기시간+예상실행시간)/예상실행시간=대기시간/예상실행시간 + 1

  • 장점
    • SJF의 단점을 보완

         

• 다단계 피드백 큐 스케줄링
  • 다단계 피드백 큐 스케줄링
    • 선점 스케줄링 알고리즘
    • I/O 중심 프로세스와 CPU 중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여
    • n개의 단계(단계 1~ 단계 n)
    • 각 단계마다 하나씩의 큐 존재
    • 단계가 커질수록 시간 할당량도 커짐

         

      

         

  • 스케줄링 방법
    • 신규 프로세스는 단계 1의 큐에서 FIFO 순서에 따라 CPU 점유
    • 입출력 같은 이벤트가 발생하면 CPU를 양보하고 대기상태로 갔다가

      다시 준비상태가 될 때에는 현재와 동일한 단계의 큐에 배치

    • 마지막 단계 n에서는 RR 스케줄링 방식으로 동작
    • 단계 k의 큐에 있는 프로세스가 CPU를 할당 받으려면 단계 1부터 단계 k - 1 까지 모든 큐가 비어있어야만 함

       

  • 장점
    • I/O위주의 프로세스(대화형)는 높은 우선권 유지
    • 연산위주의 CPU 중심 프로세스는 낮은 우선권이지만 긴 시간 할당량 가짐

         

  • 적응적 다단계 피드백 큐 스케줄링
    • 시간 할당량을 다 쓰기 전에 CPU를 반납하는 경우 하나 작은 단계의 큐로 이동 배치
    • 연산 위주의 프로세스가 I/O 위주로 바뀐다면 점점 작은 단계로 배치 가능

       

• 스케줄링 알고리즘 요약

     

  

     

2.1 프로세스

• 프로세스(process) : 실행 중인 프로그램
  • 프로그램: 동작을 하지 않는 정적,수동적 개체
  • 프로세스: 동작을 하는 능동적 개체

       

• 운영체제로부터 자원을 할당받아 동작
  • 자원: CPU, 메모리, 입출력장치, 파일 등
  • 동작: CPU가 프로세스의 명령을 실행

       

• 사용자 및 시스템 프로세스 존재

• 프로세스와 운영체제
  • 프로세스 관리자의 역할
    • 프로세스를 생성 및 삭제
    • 프로세스를 실행(CPU 할당)을 위한 스케줄 결정
    • 프로세스의 상태를 관리하며 상태 전이를 처리

         

• 프로세스의 상태
  • 5-상태 모델

    

       

    • 생성: 처음 작업이 주어진 상태, 프로세스를 운영하기 위한 필요자원 파악.
    • 준비: 실행 준비가 되어 CPU할당을 기다리는 상태,
    • 실행: 프로세스가 처리되는 상태
    • 대기: 프로세스가 특정자원을 할당 받을 때까지 또는 I/O작업이 끝날 때까지 작업이 보류되는 상태
    • 종료: 모든 처리가 완료되어 사용자에게 반환되는 상태

       

  • 프로세스의 상태변화
    • 디스패치: 준비상태에 있는 프로세스를 실행상태로 전이시키는 작업을 수행하는 운영체제 내의 모듈
    • 할당시간 만료: 더 우선순위가 높은 프로세스가 들어왔을 때 혹은 지정된 할당시간을 초과했을 때.
    • 이벤트 대기: 다른 자원이나 입출력작업이 필요해 졌을 때.
    • 재개조건 만족

         

• 프로세스 제어 블록
  • 프로세스 제어 블록(Process Control Block, PBC)

    

       

    • 프로세스의 관리를 위한 목적
    • 프로세스의 정보를 보관
    • 각 프로세스마다 존재
    • 프로세스가 진행함에 따라 내용 변경

         

• 프로세스의 생성과 종료
  • 프로세스 생성 작업
    • 프로세스의 이름(번호, PID)결정
    • 준비 큐에 삽입
    • 초기 우선순위 부여
    • 프로세스 제어 블록(PCB) 생성 등
  • 프로세스 생성 방법 : 시스템 호출

• 프로세스 생성 시스템 호출
  • 하나의 프로세스가 프로세스 생성 시스템 호출을 통해 새로운 프로세스를 생성

    Ex) fork()

  • 호출하는 프로세스: 부모 프로세스
  • 생성되는 프로세스: 자식 프로세스
  • 시스템 프로세스와 사용자 프로세스 모두 부모 프로세스가 될 수 있음

• 생성되는 프로세스의 자원
  • 운영체제로부터 직접 얻는 경우
  • 부모 프로세스 자원의 일부를 얻는 경우

       

• 자식 프로세스의 자원은 부모 프로세스의 자원으로 제한
  • 과도한 자식 프로세스 생성에 따른 시스템 과부하 방지

• 프로세스 종료
  • 프로세스의 마지막 명령이 실행을 마치는 경우
  • 프로세스 종료 시스템 호출(ex: exit( ) )을 통하는 경우
  • 프로세스 종료 후 부모 프로세스에게 실행결과를 되돌려 줌

       

• 프로세스 종료 시스템 호출
  • 부모에 의해서만 호출
  • 자식 프로세스가 할당된 자원의 사용을 초과할 때 혹은 더 이상 필요치 않을 때.

       

       

• 프로세스 간의 관계

2.2 쓰레드

• 프로세스와 쓰레드
  • 전통적인 프로세스
    • 처리의 기본 단위
    • 자원 소유의 단위(하나의 주소공간) 및 디스패칭의 단위(하나의 제어흐름)
    • 단일 프로세스 내에서 동시처리 불가능 -> 쓰레드 등장

         

      

  • 쓰레드(Thread)
    • 프로세스 내에서의 다중처리를 위해 제안된 개념
    • 하나의 프로세스 내에는 하나 이상의 쓰레드가 존재
    • 하나의 쓰레드 내에서는 하나의 실행점만 존재(디스패칭의 단위)
    • 실행에 필요한 최소한의 정보만을 가지며, 자신이 속해 있는 프로세스의 실행환경을 공유

      * <--- 실행점(프로그램 카운터)

      

         

      ->전통적인 프로세스에서는 프로세스 하나가 자원 소유의 단위이자 디스패칭의 단위였지만

      쓰레드 개념의 도입으로 디스패칭의 단위는 쓰레드 단계로 내려감

         

         

  • 다중 쓰레드의 장점
    • 멀티CPU 혹은 멀티코어 시스템에서는 병렬처리 가능
    • 처리 속도 별로 쓰레드가 나눠진 경우 효율적인 처리 가능

         

      

         

         

         

2.3 스케줄링

• 스케줄링 단계

  

• 상위단계 스케줄링
  • 시스템에 들어오는 작업들을 선택하여 프로세스를 생성한 후 프로세스 준비 큐에 전달
  • 선택 기준: 시스템의 자원을 효율적으로 이용할 수 있도록 하는 것
  • 입출력(I/O) 중심 작업과 연산 중심 작업을 균형있게 선택

       

• 하위단계 스케줄링
  • 사용가능한 CPU를 준비상태의 어느 프로세스에세 배당할지를 결정
  • CPU를 배당받은 프로세스는 결국 실행상태가 되어 프로세스가 처리됨
  • 수행 주체는 디스패처(dispatcher)

       

• 중간단계 스케줄링
  • 프로세스를 일시적으로 메모리에서 제거하여 중지시키거나 다시 활성화시킴
  • 시스템에 대한 단기적인 부하를 조절

• 스케줄링 정책
  • 스케줄링 기본 목표
    • 공정성: 모든 프로세스가 적정 수준에서 CPU 작업을 할 수 있게 함
    • 균형: 시스템의 자원들이 충분히 활용될 수 있게 함

         

    

       

       

  • 선점(Preemptive) 스케줄링 정책
    • 진행중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당하는 스케줄링 전략
    • 높은 우선순위의 프로세스를 긴급하게 처리하는 경우에 유용
    • 대화식 시분할 시스템에서 빠른 응답시간을 유지하는데 유용
    • 문맥 교환에 따른 오버헤드 발생

         

      *문맥

      CPU의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스의 상태

      *문맥교환

      CPU가 현재 실행하고 있는 프로세스의 문맥을 PCB에 저장하고, 다음 프로세스의 PCB로부터 문맥을 복원하는 작업

         

  • 비선점(Nonpreemptive) 스케줄링 정책
    • 프로세스가 CPU를 할당받아 실행이 시작되면

      작업 자체가 I/O 인터럽트를 걸거나 작업을 종료할 때까지 실행상태에 있게 됨

    • 모든 프로세스가 공정하게 순서에 따라 실행됨(응답시간 예측 가능)
    • 짧은 프로세스가 긴 프로세스를 기다리게 될 수 있음

1. 운영체제(Operation System)

   컴퓨터의 시스템 자원을 관리하고 컴퓨터 프로그램이 동작하기 위한 서비스를 제공하는 시스템 소프트웨어(S/W, 펌웨어, H/W)

      

• 컴퓨터 시스템의 구성

  사용자-응용 소프트웨어- 시스템 소프트웨어 - 하드웨어

     

  

     

• 운영체제의 역할

  - 컴퓨터 시스템의 운영

  컴퓨터 시스템의 자원을 제어 및 관리

  응용프로그램들의 실행을 도와주는 소프트웨어

   

  - 사용자 지원

  사용자의 명령을 해석하여 실행

  사용자와 하드웨어 사이의 매개체 역할 수행

     

     

• 컴퓨터 시스템과 운영체제

     

  

     

  -> 운영체제가 없던 초기의 컴퓨터 시스템

  • 응용프로그램 개발자는 하드웨어 제어방법을 잘 알고 있어야 했음
  • 여러 응용프로그램이 하드웨어를 공유하는 경우 자원 분할이 어려움

     

     

     

  

     

  -> 운영체제가 하드웨어와 응용프로그램 사이에 위치

  • 하드웨어에 대한 제어는 운영체제만 함
  • 응용프로그램은 운영체제를 통해서만 하드웨어 이용

       

• CPU의 동작모드
  • 슈퍼바이저 모드(*커널 모드)
    • 운영체제의 커널이 동작되는 모드
    • 하드웨어를 직접 제어할 수 있는 CPU 명령어 사용 가능

       

  • 보호 모드(사용자모드)
    • 응용프로그램이 동작되는 모드
    • 하드웨어를 직접 제어할 수 있는 CPU 명령어 사용 불가능

         

사용자가 응용프로그램 사용시에는 보호 모드로 동작, 하드웨어가 필요한 시점이 되면 운영체제에 모드변환을 요청하여 슈퍼바이저 모드로 동작함

이때 모드 변환은 시스템 호출을 통해 이루어짐

• 시스템 호출 -> 보호 모드에서 슈퍼바이저 모드로 변경 -> 커널동작 -> 하드웨어 제어

     

  • 시스템 호출
    • 응용프로그램이 운영체제에게 서비스를 요청하는 메커니즘

     

  • 커널(kernel)
    • 운영체제의 핵심 요소.
    • 응용프로그램과 하드웨어 수준의 처리 사이의 가교 역할

         

    • 일체형 커널(monolithic kernel) -> 유닉스, 리눅스 등
      • 운영체제의 모든 서비스가 커널 내에포함됨

        -장점: 커널 내부 요소들이 서로 효율적으로 상호작용을 할 수 있음

        -단점: 한 요소에 있는 오류로 인해 시스템 전체에 장애가 발생할 수 있음

    • 마이크로 커널(microkernel)
      • 운영체제의 대부분의 요소들을 커널 외부로 분리
      • 커널 내에는 메모리 관리, 멀티태스킹, 프로세스간 통신(IPC) 등 최소한의 요소만을 남김

        -장점: 새로운 서비스를 추가하여 운영체제를 확장하기 쉬움, 유지보수 용이, 안정성 우수

        -단점: 커널 외부 요소들 사이는 IPC를 통해야만 하므로 성능 저하가 발생함

     

     

  1.1 운영체제의 구성요소

  • 컴퓨터 시스템 자원의 성격에 따라 구분
  • 프로세스, 메모리, 장치, 파일 관리자

     

  • 프로세스 관리자
    • 프로세스를 생성, 삭제, CPU할당을 위한 스케줄 설정
    • 각 프로세스의 상태를 모니터링
    • 프로세서를 한 번 할당하면 필요한 레지스터와 테이블을 작성,

      작업을 마치거나 한계 허용시간을 초과하면 프로세서를 반환함

     

  • 메모리(주기억장치) 관리자
    • 메모리(주기억장치) 공간에 대한 요구의 유효성 체크
    • 메모리 할당 및 회수
    • 메모리 공간 보호
    • 복수 사용자 환경에서는 누가 주기억장치의 어느 부분을 이용 중인지 계속 체크하기 위해

      테이블을 만듦

         

  • 장치 관리자
    • 스케줄링 기법을 기반으로 컴퓨터 시스템의 모든 장치, 채널, 제어장치를 모니터링
    • 시스템의 장치를 할당, 작동 시작, 반환

       

  • 파일 관리자
    • 컴파일러, 인터프리터, 데이터 파일과 응용프로그램을 포함하는 시스템의 모든 파일을 모니터링
    • 파일의 접근 제한 관리
    • 파일을 열어 자원을 할당하거나 파일을 닫아 자원 회수

     

  1.2 운영체제의 유형

  응답시간의 속도, 데이터 입력방식에 따라 분류

     

  • 일괄처리(batch processing) 운영체제
    • 작업을 모아서 처리
    • 사용자와 상호작용 없이 순차적으로 실행
    • 효율성 평가 기준 -> 처리량, 반환시간

      *처리량: 주어진 시간 안에 처리된 작업의 수

      반환시간: 작업의 생성 시점부터 종료 시점까지의 소요시간

    • OMR 카드

         

  • 대화형(interactive) 운영체제
    • 시분할 운영체제라고도 함
    • 일괄처리 운영체제보다 빠르지만 실시간 운영체제보다는 느린 응답시간
    • 이용자에게 즉각적인 피드백을 제공

      *응답시간: 요청한 시점으로부터 반응이 시작되는 시점까지의 소요시간

     

  • 실시간(real-time) 운영체제
    • 가장 빠른 응답시간
    • 처리의 결과가 현재의 결정에 영향을 주는 환경에서 사용
    • 증권거래, 미사일 제어 시스템 등

         

  • 하이브리드 운영체제
    • 일괄처리와 대화형 운영체제 결합
    • 이용자는 터미널을 통해 접속하고 빠른 응답시간을 얻음
    • 대화형 작업이 많지 않은 경우 백그라운드에 배치 프로그램 실행
    • 현재 사용되고 있는 대부분의 대형 컴퓨터 시스템

         

         

  1.3 운영체제의 역사

     

  • 1940년대 : 초기 전자식 디지털 컴퓨터
    • 운영체제가 존재하지 않음
    • 기계적 스위치에 의해 작동

         

  • 1950년대 : 단순 순차처리 및 단일흐름 일괄처리
    • 한번에 오직 하나의 작업만 수행
    • 최소의 운영체제 등장(IBM 701)

     

  • 1960년대 : 멀티프로그래밍
    • 멀티프로그래밍, 시분할 처리 개념
    • 다중 대화식 사용자 지원
  • 1970년대 : 멀티모드 시분할
    • 일괄처리, 시분할 처리, 실시간 처리를 지원하는 멀티모드 시분할의 보편화
    • 근거리 지역 네트워크(LAN)의 실용화
    • 정보보호 및 보안문제의 증대로 암호화의 중요성 대두
  • 1980년대 : 병렬처리 및 분산처리
    • 순차처리를 벗어나 분산 및 병렬처리 발전
    • 그래픽 사용자 인터페이스(GUI)의 강화
    • 선점형 멀티태스킹, 멀티쓰레딩, 가상 메모리의 보편화

         

  • 2000년대와 그 이후 : 모바일 및 임베디드 운영체제
    • 시스템은 고기능, 고속화, 경량화 방향으로 발전
    • 다양한 통신망의 확대와 개방형 시스템의 발달
    • 다양한 기능 지원, 확장성, 호환성 극대화, 사용자 편의성 증대
    • 네트워크 기반의 분산 및 병렬 운영체제의 보편화
    • 클라우드 환경의 운영체제
    • 64비트 CPU에 호환되는 64비트용 운영체제
    • 모바일 및 임베디드 운영체제 보편화