운영체제 강의 정리2

배추·2023년 4월 21일
운영체제
0

운영체제

목록 보기
2/4

커널 주소 공간의 내용

1. code(커널 코드)

  • 시스템콜, 인터럽트 처리 코드
  • 자원 관리를 위한 코드
  • 편리한 서비스 제공을 위한 코드

2. data

  • PCB

3. stack

  • 커널 스택은 process 별로 따로 사용

프로세스

실행 중인 프로그램

프로세스의 상태

  • Running
    • CPU를 잡고 instruction을 수행중인 상태
  • Ready
    • CPU를 조건을 모두 만족하고 기다리는 상태
  • Blocked(wait, sleep)
    • CPU를 주어도 당장 instruction을 수행할 수 없는 상태
    • Process 자신이 요청한 event가 즉시 만족되지 않아 이를 기다리는 상태
  • New
    • 프로세스가 생성중인 상태
  • Terminated
    • 수행이 끝난 상태
  • Suspended(stopped)
    • 외부적인 이유로 프로세스의 수행이 정지된 상태
    • 프로세스는 통째로 디스크에 swap out 된다.

Blocked : 자신이 요청한 event가 만족되면 Ready
Suspended : 외부에서 반드시 resume해 주어야 Active

PCB(Process Control Block)

운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보

구성 요소

  • (1) OS가 관리상 사용하는 정보
    • Process state, Process ID
    • scheduling infomation, priority
  • (2) CPU 수행 관련 하드웨어 값
    • Program counter, registers
  • (3) 메모리 관련
    • Code, data, stack의 위치 정보
  • (4) 파일 관련
    • Open file descriptors

Context Switch

  • CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정
  • CPU가 다른 프로세스에게 넘어갈 때 운영체제는 다음을 수행
    • CPU를 내어주는 프로세스의 상태를 그 프로세스의 PCB에 저장
    • CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어옴
  • 바꿀 때 cache memory flush로 인해 큰 overhead 발생
  • timer interrupt 또는 I/O 요청 system call의 경우 context switch가 일어남
  • System call이나 Interrupt 발생시 반드시 context switch가 일어나는 것은 아님

Scheduler

  • Long-term scheduler(Job scheduler)

    • 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정
    • 프로세스에 memory(및 각종 자원)을 주는 문제
    • degree of Multiprogramming(메모리에 올라가 있는 프로그램의 수)을 제어
    • new 프로세스 상태에서 admitted될 때 실행됨(이전의 시스템)
    • time sharing system에는 보통 장기 스케줄러가 없음(무조건 ready) -> Medium-Term Scheduler 사용

  • Short-term scheduler(CPU scheduler)

    • 어떤 프로세스를 다음번에 running시킬지 결정
    • 프로세스에 CPU를 주는 문제
    • 충분히 빨라야 함(millisecond 단위)

  • Medium-Term scheduler(Swapper)

    • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄
    • 프로세스의 memory을 뺏는 문제
    • degree of Multiprogramming을 제어

Thread

프로세스 중에서 CPU 수행 단위

Thread의 장점

  • Responsiveness
    • multi-thread를 사용하여 빠른 응답성을 제공하는 효과
  • Resource Sharing
    • 동일 Proess 안에 있는 Thread끼리 공유
  • Economy
    • Process 한 개를 만드는 것보다 Overhead가 매우 작아 효율적
  • 병렬적으로 작업 수행 가능

IPC(Interprocess Communication)

  • 메시지를 전달하는 방법
    • message passing: 커널을 통해 메시지 전달
      • 사실상 서로 메시지를 직접 전달할 수 없기 때문에 kernel을 통해 메시지 전달
  • 주소 공간을 공유하는 방법
    • shared memory: 서로 다른 프로세스 간에도 일부 주소 공간을 공유
      • 다른 프로세스를 신뢰할 수 있어야 함

thread: thread는 사실상 하나의 프로세스이므로 IPC로 보기는 어렵지만 동일한 process를 구성하는 thread들 간에는 주소 공간을 공유하므로 협력이 가능하다.

CPU Scheduler

  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

다음의 상태변화는 CPU 스케줄링이 필요한 경우
1. Running -> Blocked(Nonpreemptive)
2. Running -> Ready(Preemptive)
3. Blocked -> Ready(Preemptive)
4. Terminate(Nonpreemptive)

Dispatcher

  • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에 넘긴다.(context switch)

Scheduling Criteria

  • CPU utilization(이용률)
  • Throughput(처리량)
  • Turnaround time(소요시간, 반환시간
  • Waiting time(대기 시간)
  • Response time(응답 시간)

Scheduling Algorithms

분류
Nonpreemptive: FCFS, SJF, Priority Scheduling, Multilevel Queue
Preemptive: SRTF, Priority Scheduling, RR, Multilevel Queue

  • FCFS(First-Come First-Served)
    • 선착순
    • Convoy effect 발생

Convoy effect
long process 때문에 short process가 기다리는 시간이 길어져 비효율적인 상황

  • SJF(Shortest-Job-First)
    • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
    • Minimum average waitin time을 보장
    • Starvation 발생 가능
    • CPU burst를 알 수 없음 →{\rightarrow} 예측(Exponential Averaging)
    • Preemptive, Nonpreemptive 두 가지 종류가 있으나 Preemptive한 방법이 optimal하다.

Exponential Averaging = τn+1=αtn+(1−α)τn{\tau}_{n+1}={\alpha}t_{n}+(1-{\alpha}){\tau}_{n}
1. tnt_{n} = actual length of nthn^{th}CPU burst
2. τn+1={\tau}_{n+1}= predicted value for the next CPU burst
3. 0≤α≤10{\le}{\alpha}{\le}1

  • SRTF(Shortest-Remaining-Time-First)

    • SJF의 Preemptive 방법

  • Priority Scheduling

    • 높은 우선순위를 가진 프로세스에게 CPU 할당
    • Starvation 발생 가능 →{\rightarrow} Aging
    • Preemptive, Nonpreemptive 두 가지 종류

Aging
시간이 증가함에 따라 의 우선순위를 높여준다.

  • RR(Round Robin)
    • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐(일반적으로 10-100 milliseconds)
    • 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 Ready queue의 제일 뒤에 가서 다시 줄을 선다.
    • n개의 프로세스가 Ready queue에 있고 할당 시간이 q time unit{q\,time\,unit}인 경우 어떤 프로세스도 (n−1)×q time unit(n-1){\times}{q\,time\,unit} 이상 기다리지 않아도 된다.
    • 일반적으로 SJF보다 average turnaround time은 길지만 response time은 더 짧다. ⇒{\Rightarrow} 짧은 Job, 긴 Job이 섞여서 있을때 효과적

Performance
qq large ⇒{\Rightarrow} FCFS
qq small ⇒{\Rightarrow} context switch 오버헤드가 커진다.

  • Multilevel Queue

    • Ready queue를 여러 개로 분할
      • foreground(interactive) - RR
      • background(batch-no human interaction) - FCFS
    • Queue에 대한 스케줄링 필요
      • Fixed priority scheduling
        • 모든 foreground를 서비스 후 background 서비스
        • Starvation 발생 가능
      • Time slice
        • 각 queue에 CPU time을 적절한 비율로 할당

  • Multilevel Feedback Queue

    • 프로세스가 다른 queue로 이동 가능
    • Multilevel-feedback-queue scheduler를 정의하는 파라미터들
      • Queue의 수
      • 각 큐의 scheduling algorithm
      • Process를 상위 큐로 보내는 기준
      • Process를 하위 큐로 내쫓는 기중
      • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

Reference

KOCW - 운영체제 이화여대 반효경 교수님

profile
배추
배추도사
이전 포스트

운영체제 강의 정리1

다음 포스트

운영체제 강의 정리3

0개의 댓글