Race Condition

• S-box(Memory Address Space)를 공유하는 E-box(CPU Process)가 여럿 있는 경우 Race Condition의 가능성이 있음
• Multiprocessor system에서 공유 메모리를 사용하는 프로세스들이 커널 내부 데이터를 접근하는 루틴들 간에 발생할 수 있음

OS에서 Race Conditoin이 발생하는 경우

1. kernel 수행 중 인터럽트 발생 시
2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
3. Multiprocessor에서 shared memory 내의 kernel data

Case1. interrupt handler v.s kernel

• 커널 모드 running 중 interrupt가 발생하여 인터럽트 처리 루틴이 수행

  양쪽 다 커널 코드이므로 kernel address space를 공유하기 때문에 Race Condition이 발생할 수 있다

  커널 모드 running중에는 interrupt가 걸리는 것을 막아서 Race Condition을 피할 수 있다

Case2. Preempt a process running in kernel?

• 두 프로세스의 address space 간에는 data sharing이 없음

• 그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨(share)

• 커널 작업 중간에 CPU를 preempt하면 Race Condition 발생

  

• 해결책: 커널 모드에서 수행 중일 때는 CPU를 preempt하지않고, 커널 모드에서 사용자 모드로 돌아갈 때 preempt한다

Case3. Multiprocessor

• 여러 CPU가 한 자원에 동시 접근한다 -> Race Condition

• Multi Processor인 경우 서로 다른 CPU가 접근하기 때문에 interrupt를 enable/disable로 해결되지 않는다

• 해결 방법

  1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
  2. 커널 내부에 있는 각 공유 데이터를 접근할 때마다 그 데이터에 대한 lock/unlock하는 방법

Process Synchronization 문제

• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있다

• 일관성(consistency) 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 매커니즘이 필요하다

• Race Condition

  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황

  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

    

    race condition을 막기 위해서는 concurrent process는 동기화(synchronize) 되어야 한다

The Critical-Section Problem

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• 하나의 프로세스가 critical section에 있을때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다

프로그램적 해결법의 충족 조건

• Mutual Exclusion : 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다
• Progress : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다
• Bounded Waiting(유한 대기) : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야한다

해결 알고리즘 Case 1

• Synchronization variable

  • int turn;

  • initially turn = 0;

    

• mutual exclusion은 만족하나, progress를 만족하지 못함

  반드시 한번씩 교대로 들어가야만 한다. 임계 구역에 작업하는 프로세스가 없어도, 한 프로세스가 연속해서 들어가지 못한다

해결 알고리즘 Case 2

• Synchronization variable

  • boolean flag[2];

  • initially flag[] = false;

    

• mutual exclusion은 만족하나, progress를 만족하지 못함

  프로세스 둘 다 2행까지 수행 후에 끊임없이 서로에게 양보하는 상황 발생 가능

해결 알고리즘 Case 3 (Peterson’s Algorithm)

• algorithm 1 2 번을 조합함

  

• 두 프로세스의 임계영역 문제 해결조건을 모두 만족한다

  하지만 Busy Waiting!이다 (계속 CPU와 memroy를 쓰면서 wait)

Synchronization Hardware

• 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

  

• Mutual Exclusion with Test & Set

  

Semaphores

• 앞의 방식들을 추상화 시킴

• Semaphores S

  • integer variable

  • S는 자원의 갯수

  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

    

• 세마포어의 두가지 종류

  1. Counting Semaphore
     • 도메인이 0 이상인 임의의 정수값
     • 주로 resource counting에 사용
  2. Binary Semaphore (=mutex)
     • 0 또는 1 값만 가질 수 있는 semaphore
     • 주로 mutual exclusion (lock/unlock)에 사용

Critical Section Of n Processes

위의 방식은 busy-wait 방식으로 임계구역이 오래걸리는 작업일 경우 효율적이지 못하다 따라서 Block & Wake up 방식을 사용하는 방법도 있다

Block And Wake Up 구현

• Semaphore를 다음과 같이 정의한다

  <img width=”400” alt=”스크린샷 2021-07-23 오후 10 02 04” src=”https://user-images.githubusercontent.com/12459864/126785511-2912b40c-b763-4646-a1ea-

  

• block과 wakeup을 다음과 같이 가정

  • block : 커널은 block을 호춝한 프로세스를 suspend시키고, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup(P) : block된 프로세스 P를 wakeup 시킴, 이 프로세스의 PCB를 ready queue로

• Semaphore 연산

  

  value는 block과 wake up의 기준

Busy-wait vs Block/wakeup

• Critical section의 길이가 긴 경우 Block/wakeup이 적당
• Critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
• 일반적으로는 Block/wakeup 방식이 더 좋음

Deadlock and Starvation

• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의행 충족될 수 있는 event를 무한히 기다리는 현상

  

• Starvation : indefinite blocking, 프로세스가 suspend된 이후에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

대표적인 Race Condition 문제

Bounded-Buffer Problem

• shared data

  • buffer 자체
  • buffer 조작 변수 (empty/full buffer의 시작 위치)

• Synchronization variables

  • mutual exclusion -> Need binary semaphore (Buffer의 사용 여부)

  • resource count -> Need integer semaphore (남은 empty/full buffer의 수 표시)

    

Readers-Writers Problem

• 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안됨

• read는 동시에 여럿이 해도 됨

• solution

  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
  • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다
  • 일단 Wrtier가 DB에 접근 중이면 Reader들은 접근이 금지된다
  • Wrtier가 DB에서 빠져나가야만 Reader의 접근이 허용된다

• shared data

  • DB 자체
  • readcount; -> 현재 DB에 접근 중인 Reader의 수

• Synchronization variables

  • mutex -> 공유 변수 readcount의 mutual exclusion을 보장

  • db -> reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

    

Dining-Philosophers Problem

• 위의 solution의 문제점

  • Deadlock 가능성이 있다
  • 모든 철학자가 동시에 배가 고파져서 왼쪽 젓가락만 집을 경우

• 해결 방안

  • 4명의 철학자만이 동시에 테이블에 앉을 수 있도록 한다
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집도록한다
  • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록한다

Monitor

• Semaphore의 문제점

  • 코딩하기 힘들다

  • 정확성의 입증이 어렵다

  • 자발적 협력이 필요하다

  • 한 번의 실수가 모든 시스템에 치명적인 영향을 미친다

    

• 모니터란?

  • 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

    

  • 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능하다

  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음

  • 프로세스가 모니터 안에서 대기할 수 있도록 하기 위해 conditional variable 사용

    • condition x, y;

  • condition variable은 wait와 signal 연산에 의해서만 접근 가능

    • x.wait(); : x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지는 suspend된다

    • x.signal(); : x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다

      

      monitor에 프로세스가 작업중이면 외부 entry queue에서 대기한다

      monitor내부에서 condition x가 없으면 x에 관한 queue에서 대기한다

      내부에서 작업중인 프로세스가 없거나 작업중인 프로세스가 condition 대기 queue에서 sleep하고 있으면 외부 작업 큐에서 프로세스가 monitor를 작업한다

Monitor를 적용한 Bounded Buffer Problem

Monitor를 적용한 Dining-Philosophers Problem

참고

• 반효경 교수님 운영체제 강의

Comment and share

CPU and I/O Burst Time

• CPU burst time: CPU 실행시간

• I/O burst time: I/O 작업 대기 시간

  

• 프로세스 특성에 따른 분류

  • I/O bound process
    • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
    • (many short CPU bursts)
  • CPU bound process
    • 계산 위주의 job
    • (few very long CPU bursts)

• 여러 종류의 process이 섞여 있기 때문에 CPU 스케줄링이 필요하다

  • Interactivce job에게 적절한 response 제공
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

• CPU Scheduler

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

• Dispatcher

  • CPU 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다
  • 이 과정을 context switching(문맥 교환)이라고 한다

• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다

  1. Running -> Blocked (예: I/O 요청하는 시스템 콜)

  2. Running -> Ready (예: 할당 시간 만료 timer interrupt)

  3. Blocked -> Ready (예: I/O 완료 후 인터럽트)

  4. Terminate

     1, 4에서 스케줄링은 nonpreemptive, 나머지는 preemptive

Scheduling Criteria

• CPU utilization(이용률) : CPU가 놀지 않고 사용하는 비율

• Throughput(처리량) : 주어진 시간안에 몇 개의 작업을 완료하였는가?

• Turnaround time(소요시간) : CPU를 대기하고 다 쓰고 반환하는 시간

• Waiting time(대기시간) : CPU를 대기하는 시간

• Response time(응답시간) : CPU를 처음으로 얻기까지 걸린 시간

  이용률, 처리량은 시스템 입장에서

  소요시간, 대기 시간, 응답 시간 프로세스(사용자) 입장에서 기준이다

Scheduling Algorithm

• CPU를 누구한테 줄 것 인가?
• CPU를 오래 잡고있으면 뺐을 것인가?

FCFS(First-Come First-Served)

• 프로세스 도착 순서대로 스케줄링 한다
• 오래걸리는 프로세스가 먼저 도착하면 전체 평균 응답시간이 느리다
  • 소요시간이 긴 프로세스가 먼저 도착할 경우
  • 소요시간이 짧은 프로세스가 먼저 도착할 경우

SJF (Shortest-Job-First)

• CPU burst time이 가장 짧은 프로세스를 먼저 스케줄링 한다

• SJF 종류

  • Nonpreemptive(비선점형)

    • CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

  • Preemptive(선점형)

    • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
    • Shortest-Remaining Time-First(SRTF)이라고도 부른다

    SJF는 최적의 스케줄링 알고리즘으로 주어진 프로세스에게 minmum average waiting time을 보장한다

• 문제점

  • starvation : CPU burst time이 긴 프로세스는 CPU를 얻기 힘들다.

  • 실제 프로세스들의 CPU burst time 예측하기 어려움

    • 과거의 CPU burst time을 이용하여 추정만이 가능하다

      

      최근의 CPU burst time 측정값이 현재의 추정치에 영향을 더 미친다

Priority Scheduling

• 우선순위가 높은 것 먼저 스케줄링한다
• 선점형 비선점형 두가지 종류가 있다
• SJF도 priority = predicted next CPU burst time인 일종의 priority scheduling이다
• 문제점으로 우선순위가 낮은 프로세스가 실행되지 않는 Starvation 문제가 있다
• 따라서 Aging 방식을 통해서 프로세스의 우선순위를 시간이 지남에 따라 증가시켜 주는 방식으로 해결한다

Round Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다
• 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에서 다시 줄 선다.
• n개의 프로세스가 ready queue에 할당 시간이 q time unit인 경우
  • 어떤 프로세스도 (n - 1)q time unit 이상을 기다리지 않는다
  • 응답시간이 빨리진다

time quantum이 많이 길어지면 FCFS Scheduling 처럼 동작하고

time quantum이 짧아지면 짧아질수록 context switching 오버헤드가 커진다

Multilevel Queue

• 우선순위가 높은 큐의 작업을 우선시 한다
• Ready queue를 여러 개로 분할
  • foreground (interactive)
  • background (batch - no human interactive)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐간의 스케줄링이 필요
  • Fixed priority scheduling
    • foreground에 작업을 우선으로 하고 foreground에 작업이 없으면 background 작업 시작
    • starvation의 가능성이 있다
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당한다
    • 80% foregound in RR, 20% to background in FCFS

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동가능하다
• Scheduling
  1. new job이 queue Q0로 들어감
  2. CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
  3. 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
  4. Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
  5. 16ms에서 끝내지 못한 경우 queue Q2로 쫓겨남

Multiple-Processor Scheduling

• Homogeneous processor 인 경우
  • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Load sharding
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Symmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

• Hard real-time systems : 정해진 시간 안에 반드시 스케줄링해야 함
• Soft read-time systems : 정해진 시간에 반드시 스케줄링하지 않지만, 일반 프로세스에 비해 높은 prioty를 갖도록 해야함

Thread Scheduling

• Local Scheduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• Global Scheduling : Kernel level tthrea의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

참고

• 반효경 교수님 운영체제 강의

Comment and share

프로세스 생성 (Process Creation)

• 부모 프로세스가 자식 프로세스를 생성합니다 (복제 생성)
• 프로세스의 트리 형성
• 프로세스는 자원을 필요로 합니다
  • 운영체제로 받는다
  • 부모와 공유한다
• 자원의 공유
  • 부모와 지식이 모든 자원을 공유하는 모델
  • 일부를 공유하는 모델
  • 전혀 공유하지 않는 모델
• 수행 (Execution)
  • 부모와 자식은 공존하며 수행되는 모델
  • 자식이 종료(terminate)될 때까지 부모가 기다리는(wait)모델
• 주소 공간 (Address space)
  • 자식은 부모의 공간을 복사함 (binary and OS data)
  • 자식은 그 공간에 새로운 프로그램을 올림
• 유닉스의 예
  • fork() 시스템 콜이 새로운 프로세스를 생성
    • 부모를 그래로 복사 (OS data except PID + binary)
    • 주소 공간 할당
  • fork 다음에 이어지는 exec() 시스템 콜을 통해 새로운 프로그램을 메모리에 올림

프로세스 종료 (Process Termination)

• 프로세스가 마지막 명령을 수행한 후 운영체제에게 이를 알려줌 (exit)
  • 자식이 부모에게 output data를 보냄 (via wait)
  • 프로세스의 각종자원들이 운영체제에게 반납됨
• 부모 프로세스가 자식의 수행을 종료시킴 (abort)
  • 자식이 할당 자원의 한계치를 넘어섬
  • 자식에게 할당된 태스크가 더 이상 필요하지 않음
  • 부모가 종료(exit)하는 경우
    • 운영체제는 부모 프로세스가 종료하는 경우 자식이 더 이상 수행되도록 두지 않는다
    • 단계적인 종료

fork() 시스템 콜

• 자식 프로세스는 부모 프로세스에서 Program Counte도 복제해서 fork한 이후부터 실행

exec() 시스템 콜

• 프로세스에 새로운 프로그램을 덮어서 다른 프로그램으로 만들어 실행

wait() 시스템 콜

• 프로세스 A가 wait() 시스템 콜을 호출
  • 커널은 child가 종료될 때까지 프로세스 A를 sleep시킨다 (block 상태)
  • child process가 종료되면 커널은 프로세스 A를 깨운다 (ready 상태)

exit() 시스템 콜

• 프로세스 종료
  • 자발적인 종료
    • 마지막 statement 수행 후 exit() 시스템 콜을 통해
    • 프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치에 컴파일러가 넣어줌
  • 비자발적 종료
    • 부모 프로세스가 자식 프로세스를 강제 종료시킴
      • 자식 프로세스가 한계치를 넘어서 자원 요청
      • 자식에게 할당된 태스크가 더 이상 필요하지 않음
    • 키보드로 kill, break 등을 친 경우
    • 부모가 종료하는 경우
      • 부모 프로세스가 종료하기 전에 자식들이 먼전 종료됨

프로세스 간 협력

• 독립적 프로세스

  • 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 미치지 못합

• 협력 프로세스

  • 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있음

• 프로세스 간 협력 메커니즘 (IPC: Interprocess Communication)

  • message passing : 커널을 통해서 메시지 전달됨

  • shared memory

    • 프로세스간 메모리 공유 요청을 커널에게 요청한 후, 커널을 통해서 특정 물리 메모리 공간을 공유합니다
    

thread : 프로세스 간의 협력은 아니지만 동일한 process를 구성하는 thread간에는 주소공간을 공유하므로 협력이 가능하다

Message Passing

• Message System : 프로세스 사이에 공유 변수를 일체 사용하지 않고 통신하는 시스템
• Direct Communication
  • 통신하려는 프로세스의 이름을 명시적으로 표시
• Indirect Communication
  • mailbox (또는 port)를 통해 메시지를 간접 전달
  • 특정 대상이 아니라 임의의 대상들이 메시지를 확인하고 가져감

참고

• 반효경 교수님 운영체제 강의

Comment and share

Thread란

A thread (or lightweight process) is a basic unit of CPU utilization

• Thread의 구성
  • program counter
  • register set
  • stack space
• Thread가 동료 thread와 공유하는 부분(=task)
  • code section
  • data section
  • OS resources
• heavyweight process는 하나의 thread를 가지고 있는 task로 볼 수 있습니다

Thread의 장점

1. 다중 스레드로 구성된 태스크 구조에서는 하나의 서버 스레드가 blocked(waiting) 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행(running)되어 빠른 처리를 할 수 있습니다
   • ex) 웹 브라우저가 웹 페이지를 불러올 때 html과 text를 먼저 불러오고 text만으로 사용자가 작업할 수 있게 한 다음, 다른 스레드가 image를 불러오는 작업을 할 수 있습니다
2. 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율(throughput)과 성능 향상을 얻을 수 있습니다.
3. 자원 낭비를 막는다 (프로세스 각각으로 돌리면 각 프로세스당 메모리가 필요하게 되서 더 많은 메모리를 차지합니다)
4. 스레드를 사용하면 병렬성을 높일 수 있습니다(멀티 코어일 경우)

참고

• 반효경 교수님 운영체제 강의

Comment and share

Process Concept

• Process is a program in execution
• 프로세스의 문맥 (context)
  • CPU 수행 상태를 나타내는 하드웨어 문맥
    • Program Counter(PC)
    • 각종 register
  • 프로세스의 주소 공간
    • code, data, stack
  • 프로세스 관련 커널 자료 구조
    • PCB (Process Control Block)
    • Kernel stack

Process State

• 프로세스는 상태(state)가 변경되며 수행됩니다

• Running : CPU를 잡고 instruction을 수행중인 상태

• Ready : CPU를 기다리는 상태(CPU만 얻으면 실행할 수 있는 상태)

• Blocked(wait, sleep)

  • CPU를 주어도 당장 instruction을 실행할 수 없는 상태
  • Process 자신이 요청한 event(I/O)가 즉시 만족되지 않아 이를 기다리는 상태
  • 디스크에서 file을 읽어와야 하는 경우

• New: 프로세스가 생성중인 상태

• Terminated: 수행이 끝난 상태

  

• 각 작업의 큐는 Kernel의 Data영역에서 관리되어집니다

  

PCB

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

• 다음의 구성 요소를 가집니다 (구조체로 유지)

  1. OS가 관리상 사용하는 정보

     • Process state, Process ID
     • scheduling information, priority

  2. CPU 수행 관련 하드웨어 값

     • program counter(PC), registers

  3. 메모리 관련

     • code, data, stack의 위치 정보

  4. 파일 관련

     • Open file descriptiors…
     

문맥 교환 (Context Switching)

• CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정

• CPU가 다른 프로세스에게 넘어갈 때 운영체제는 운영체제는 다음을 수행합니다

  • CPU를 내어주는 프로세스의 상태를 그 프로세스의 PCB에 저장

  • CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어옴

    

• System Call이나 Interrupt 발생시 반드시 Context switching이 일어나는 것은 아닙니다

  
  • 1번의 경우에도 CPU 수행 정보 등 context의 일부를 PCB에 save해야 하지만 문맥교환을 하는 2번의 경우 cache memory flush가 발생하기 때문에 성능 부담이 훨씬 큽니다

프로세스를 스케줄링하기 위한 큐

• Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합 (Process Queue + Device Queue)

• Ready Queue: 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합

• Device Queue: I/O device의 처리를 기다리는 프로세스의 집합

  프로세스들은 각 큐를 오가며 수행됩니다

스케줄러

• 장기 스케줄러 (job scheduler)

  • 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정합니다
  • 프로세스에 memory(및 각종 자원)을 주는 문제
  • degree of multiprogramming을 제어
  • time sharing system에는 보통 장기 스케줄러 없이 무조건 ready 상태가 됩니다

• 단기 스케줄러 (cpu scheduler)

  • 어떤 프로세스를 다음번에 running 시킬 지 결정합니다
  • 프로세스에 CPU를 주는 문제

• 중기 스케줄러 (swapper)

  • 여유 공간 마련을 위해 프로세스를 통째로 메모레에서 디스크로 쫓아냅니다

  • 프로세스에게서 memory를 뺏는 문제

  • degree of multiprogramming을 제어

  • 현재 시스템은 프로그램을 무조건 메모리에 올리고 swapper를 이용해서 메모리에서 쫓아낸다 (장기 스케줄러대신 중기 스케줄러를 사용한다)

    중기 스케줄러로 인해서 Suspended라는 프로세스의 상태가 추가됩니다

새로운 프로세스 상태

• Running
• Ready
• Blocked
• Suspended (stopped)
  • 외부적인 이유로 프로세스의 수행이 정지된 상태
  • 프로세스는 통째로 디스크에서 swap out 됩니다
  • (예) 메모리에 너무 많은 프로세스가 올라와서 성능이 저하되었을 때 사용자가 직접 process를 중단시거나 시스템이 중단시킵니다

Block은 자신이 요청한 event가 만족되면 Ready 상태가 되어집니다

Suspended는 외부에서 다시 resume해 주어야 Activce됩니다

참고

• 반효경 교수님 운영체제 강의

Comment and share

컴퓨터 시스템 구조

• Computer

  • CPU
    • mode bit : 사용자 모드 (0 : 커널, 1 : 사용자)
    • registers : CPU가 일시적으로 데이터를 저장하는 기억장치 입니다
    • interrupt line : 들어온 인터럽트를 확인하는 공간입니다
  • Memory: CPU의 작업 공간입니다

• timer : 한 작업 당 CPU를 일정시간 동안만 사용할 수 있도록하는 하드웨어 입니다 (인터럽트를 CPU에 겁니다)

• DMA controller: CPU의 interrupt 작업을 대신해줍니다 (I/O 작업의 결과를 메모리에 반영하고 완료하면 CPU에 Interrupt를 한 번만 작업합니다)

• memoery controller : DMA, CPU의 메모리 접근을 제어합니다 (DMA와 CPU가 동시에 같은 메모리를 작업하지 않도록 합니다)

• I/O device

  • device controller : 각 device를 제어합니다

  • local buffuer : device controller 작업 공간입니다

    

Device Controller

• 해당 I/O 장치유형을 관리하는 일종의 작은 CPU입니다
• 제어 정보를 위해 control register, status register를 가집니다
• 일종의 data register인 local buffer를 가집니다
• I/O 작업은 실제 device와 local buffer 사이에 일어나고 I/O 작업이 완료되면 Device Controller는 Interrupt로 CPU나 DMA에 완료됨을 알려줍니다
• device driver VS device controller
  • device driver는 OS 코드 중에서 각 장치별 처리루틴을 작성한 software 입니다
  • device controller는 각 장치를 통제하는 일종의 작은 CPU인 hareware 입니다

Timer

• 정해진 시간이 흐른 뒤 운영체제에게 제어권이 넘어가도록 인터럽트를 발생시키는 하드웨어 입니다
• 타이머는 매 클럭마다 1씩 감소되고 0이 되어지면 타이머 인터럽트가 발생합니다
• CPU를 특정 프로그램이 독점하는 것으로부터 보호합니다
• 타이머는 time sharing을 하기위해 많이 사용되어집니다

DMA (Direct Memory Access)

• CPU의 중재 없이 device controller가 device의 buffer storage의 내용을 메모리에 block 단위로 직접 전송하도록 해줍니다
• 바이트 단위가 아니라 block 단위로 인터럽트를 발생시키기 때문에 CPU에 인터럽트가 적게 걸립니다

인터럽트 (Interrupt)

• 인터럽트 : 인터럽트를 당한 시점의 레지스터와 program counter를 저장한 후 CPU의 제어를 인터럽트 처리 루틴에 넘깁니다
• 인터럽트의 종류
  • Interrupt (하드웨어 인터럽트): 하드웨어가 발생시킨 인터럽트입니다
  • Trap (소프트웨어 인터럽트)
    • Exception: 프로그램이 오류를 범한 경우
    • System call: 사용자 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출하는 것
• 인터럽트 관련 용어
  • 인터럽트 벡터 : 해당 인터럽트의 처리 루틴 주소를 가지고 있습니다
  • 인터럽트 처리 루틴(Interrupt Service Routine, 인터럽트 핸들러) : 해당 인터럽트를 처리하는 커널 함수입니다

I/O System Call 흐름 자세히 보기

1. 사용자 프로그램은 I/O 명령은 특권 명령이여서 OS의 도움이 필요합니다.
2. 따라서 System Call을 사용하여 운영체제에게 I/O를 요청하게 됩니다.
3. trap을 사용하여 인터럽트 벡터의 특정 위치로 이동하고 인터럽트 벡터가 가리키는 인터럽트 서비스 루틴으로 이동합니다
4. 이 I/O 요청이 올바른 요청인지 확인후 I/O를 수행합니다
5. I/O 완료 시 제어권을 시스템 콜 다음 명령으로 옮깁니다

작업 흐름 - I/O 작업

1. CPU가 Program A를 작업하고 있습니다
2. Program1에서 I/O 작업을 요청하기 위해 시스템 콜을 실행합니다
3. 해당 시스템 콜로 인해서 인터럽트가 걸려서 CPU 제어권이 OS로 넘어갑니다
4. OS에서 I/O 작업을 처리하도록 해당 device에 요청합니다
5. OS에서 스케쥴링하여 다음 작업인 Program B에 CPU를 넘겨줍니다
6. 이후에 해당 device에서 I/O 작업을 마치고 CPU의 interrupt line에 완료 인터럽트를 겁니다
7. CPU는 instruction을 실행하면서 interrupt line에 인터럽트가 들어온 것을 확인하고 CPU 제어권이 OS로 넘어갑니다
8. OS에서는 완료된 I/O 작업을 확인하고 Program1을 실행 가능 상태로 전환하여 스케쥴링합니다.

작업 흐름 - Timer

1. OS에서 스케쥴링하여 Program A에 CPU 제어권을 넘겨주고 Timer를 설정합니다.
2. Program A가 작업하고 있다가 작업이 완료되기 전에 Timer에 시간이 만료되어서 CPU에 Interrupt가 걸립니다.
3. CPU는 Interrupt를 확인하고 CPU의 제어권이 OS로 넘어갑니다
4. OS는 동일하게 다음 스케쥴링된 프로그램에게 CPU 제어권을 넘겨주고 Timer를 설정합니다

동기식 입출력과 비동기식 입출력

• 동기식 입출력 (synchronous I/O)
  • I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램으로 넘어갑니다
  • 구현 방법 1
    • I/O가 끝날 때까지 CPU를 가지고 있습니다
    • CPU낭비가 심하고 매시점 하나의 I/O만 일어날 수 있습니다
  • 구현 방법 2
    • I/O가 완료될 때까지 해당 프로그램에게서 CPU를 빼앗습니다
    • I/O 처리를 기다리는 줄에 그 프로그램을 줄 세우고 다른 프로그램에게 CPU를 줍니다
• 비동기식 입출력 (asynchronous I/O)
  • I/O가 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 다시 원래의 사용자 프로그램에게 넘어갑니다
• 두 경우 모두 I/O 완료는 인터럽트를 통해서 알려줍니다

프로그램의 실행 (메모리 load)

• File System에 존재하는 프로그램이 메모리에 load될 때 code, data, stack 영역으로 구분되어지는 Virtual memory로 형성되어 지고, 실제 메모리에 올라가는 부분은 Virtual memory와 매핑되어지는 일부분만 올라갑니다. 이후에 메모리의 일부분은 File System에 존재하는 Swap area와 교체가 일어나면서 메모리에 올라갔다가 내려오게 됩니다.

  

커널 주소 공간의 내용

• code

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

• data

  • PCB
  • CPU, Memory, Disk에 관한 데이터

• stack

  • 각 프로세스에 관한 커널 스택

    

참조

• 반효경 교수님 운영체제 강의

Comment and share

운영체제란 무엇인가?

• 운영체제 : 컴퓨터 하드웨어 바로 위에 설치된 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분입니다
  
• 운영체제의 목표
  • 컴퓨터 시스템을 편리하게 사용할 수 있는 환경을 제공합니다
    • 동시 사용자/프로그램들이 각각 독자적 컴퓨터에서 수행되는 것 같은 환상을 제공합니다
    • 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행해줍니다
  • 컴퓨터 시스템의 자원(프로세서, 기억장치, 입출력 장치)을 효율적으로 관리해줍니다
    • 사용자간의 형평성 있게 자원을 분배해줍니다
    • 주어진 자원으로 최대한의 성능을 내도록 합니다
• 운영 체제의 분류
  • 동시 작업 가능 여부
    • 단일 작업(single tasking)
    • 다중 작업(multo tasking)
  • 사용자의 수
    • 단일 사용자(single user)
    • 다중 사용자(multi user)
  • 처리 방식
    • 일괄 처리(batch processing)
      • 작업 요청의 일정량을 모아서 한꺼번에 처리하며, 따라서 작업이 완전 종료될 때까지 기다려야 합니다
    • 시분할(time sharing)
      • 여러 작업을 수행할 때 컴퓨터 처리 능력을 일정한 시간 단위로 분할하여 사용하여, 일괄 처리 시스템에 비해
        짧은 응답시간을 가지고, interactive한 방식입니다.
    • 실시간(Realtime OS)
      • 정해진 시간 안에 어떠한 일이 반드시 종료됨이 보장되어야하는 실시간 시스템을 위한 OS입니다.
      • 예) 미사일 제어, 반도체 장비, 로보트 제어
      • 실시간 시스템의 개념의 확장
        • Hard realtime system : 데드라인이 존재하며 데드라인안에 작업이 완료되어야 합니다
        • Soft realtime system : 데드라인은 존재하지만 완벽하게 지켜지지 않아도 되는 시스템 입니다
• 용어 정리
  • 컴퓨터에서 여러 작업을 동시에 수행하는 것을 강조한 용어
    • Multitasking : 하나의 프로그램이 끝나기전에 다른 프로그램을 실행시킬 수 있습니다
    • Multiprogramming : 메모리에 여러 프로그램이 올라갈 수 있는 부분을 집중한 용어입니다
    • Time sharing : cpu를 강조한 측면의 유사한 용어입니다
    • Multiprocess
  • Multiprocessor : 하나의 컴퓨터에 CPU (processor)가 여러 개 붙어 있음을 의미합니다

참조

• 반효경 교수님 강의

Comment and share