KOCW에 공개된 이화여대 반효경 교수님 운영체제 강의를 수강 후 정리한 내용입니다.

• Process Synchronization (프로세스 동기화)를 Concurrency Control (병행 제어)라고 부르기도 함
  • 프로세스가 동시에 무언가를 실행하면서 발생하는 문제를 해결하는 것을 의미

Race Condition

• Execution-Box: 연산이 수행되는 곳
• Storage-Box(S-box): 데이터가 저장되어 있는 곳

• Race Condition: S-Box(Memory Address Space)를 공유하는 E-box(CPU Process)가 여러 개 있는 경우

  • 발생 가능한 경우
    1. Multiprocessor system에서 메모리를 공유하고 있는 경우
    2. 공유메모리를 사용하는 프로세스들 사이에서 발생 가능
    3. 커널 내부 데이터를 접근하는 루틴들(ex. 커널 모드 수행 중 인터럽트로 커널모드 다른 루틴 수행시) 사이에서 발생 가능

• OS에서 race condition이 발생하는 경우

  1. kernel 수행 중 인터럽트 발생 시

  

  • 커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행 -> 양쪽 다 커널 모드이므로 kernel address space 공유
  • 해결방법: interrupt가 들어와도 instruction이 끝날 때까지 disable시켰다가 instruction 작업이 끝난 후 인터럽트 처리루틴을 수행
  1. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우

  

  • system call을 하는 동안에는 kernel address space의 data를 access하게 되는데 이 작업 중간에 CPU를 preempt해가면 race condition 발생
  • 해결방법: 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음. 커널 모드에서 사용자 모드로 돌아갈 때 preempt
  1. Multiprocessor에서 shared memory 내의 kernel data

  • interrupt enable/disable로 해결되지 않음

  • 해결방법: 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법 (비효율적) / 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock 혹은 unlock을 하는 방법

1. Process Synchronization 문제

• 공유 데이터의 동시 접근(concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있음
• 일관성(consistency) 유지를 위해 협력 프로세스(cooperation process) 간의 실행 순서를 정해주는 메커니즘 필요

Race condition

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

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

• race condition을 막기 위해 concurrent process는 동기화(synchronize)되어야 함

The Critical-Section Proble

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section(임계 구역)이 존재

• 문제

  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함

    

Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정하면 프로세스들의 일반적인 구조는 그림처럼 구성됨

    - 공유 데이터를 접근하거나 접근하지 않거나 => 두 구역으로 구성됨
    - 프로세스들은 수행의 동기화(Synchronize)을 위해 몇몇 변수를 공유할 수 있음 (Synchronization variable)
  

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

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

2. Process Synchronization 문제 해결 알고리즘

Algorithm 1

• turn: critical section에 들어갈 차례를 나타내주는 변수 (0인 경우 0번 프로세스, 1일 경우 1번 프로세스)
• while문을 통해 내 차례가 아닌 경우에는 대기하고 turn이 0으로 변경되면 critical secetion에 들어가고, 나오면 상대방의 차례로 변경해줌
• Mutual Exclusion은 만족하지만 Progress는 만족하지 못함
  • critical section은 반드시 교대로 돌아가도록 구성되어 있음. 따라서 두 프로세스가 critical section에 들어가는 횟수가 비슷하지 않으면 어느 프로세스는 critical section에 아예 들어가지 못할 수 있음

Algorithm 2

• flag: 프로세스마다 각각의 flag를 가짐. 본인이 critical section에 들어가고자 한다는 의중을 표현하는 변수
• critical section에 들어가고자 한다면 본인의 flag를 true로 변경해준 뒤 상대방의 flag를 체크. 상대방의 flag가 true일 경우 while문을 돌면서 기다리고 false일 경우 critical section에 들어가고, 나올 때 본인의 flag를 false로 변경해줌
• mutual exclusion은 만족하지만 progress는 만족하지 못함
  • critical section에 들어갔다 나와야 flag의 값이 false로 변경되는데 critical section에 들어가기 전 두 프로세스의 flag의 값이 모두 true이면 아무로 critical section에 들어가지 못함
  • 두 프로세스 모두 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능

Algorithm 3 (Peterson’s Algorithm)

• turn과 flag 모두 사용
• critical section에 들어가고자 할 때, 가장 먼저 flag를 true로 변경하고 turn을 상대방 turn으로 변경. 상대방의 flag가 true이고 상대방의 turn이면 while문을 돌며 대기. 상대방의 flag가 false이거나 turn이 내 turn이라면 critical section에 들어가고 나올 때 flag 값을 false로 변경
• 세 가지 조건 모두 만족
  • 두 프로세스 모두 critical section에 들어가고자 할 경우 turn 값을 보고 critical section에 먼저 들어갈 프로세스를 정함
• Busy Waiting (= spin lock): 계속 CPU와 memory를 쓰면서 wait
  • 내가 CPU를 잡아서 and 조건을 만족해 while문을 돌고 있는 경우 while문을 빠져나갈 수 없으므로 CPU 할당시간이 끝날 때까지 while문만 돌다가 CPU를 반납 => 비효율적

Synchronization Hardware

• Synchronization 문제가 발생했던 이유: 데이터를 읽는 과정과 쓰는 과정을 하나의 instruction으로 처리할 수 없었기 때문

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

  

  • Test_and_set(a): a의 원래의 값을 읽어내고 원하는 값으로 a의 값을 다시 세팅
    • ex) a의 값이 0인 경우, Test_and_set(1)을 수행하면 원래 a의 값인 0을 읽어오고 a의 값을 1로 세팅해줌

3. Semaphores

• 일종의 추상 자료형

• 공유 자원을 획득하고 반납하는 것을 semaphore가 관리

• Semaphore S가 있다고 하면 이 변수는 정수 값(자원의 개수를 의미)을 가질 수 있고 연산은 두 가지로 정의됨

  P(S):	while (S <= 0) do no-op;	// wait
  		S--;
    
  V(S):	S++;
  

  • P(S): 자원을 획득하는 연산 / V(S): 자원을 반납하는 연산
  • automic 연산에 의해서만 접근 가능
  • busy-wait 발생: 자원이 없을 때, P 연산을 하게되면 자원이 없기 때문에 while문을 계속 돌다가 CPU 시간을 모두 쓰고 반납하게 됨

Critical Section of n Processes

• Semaphore 추상 자료형이 지원된다면, 프로그래머는 앞에서처럼 일일이 코딩해줄 필요없이 P와 V 연산만 수행해주면 됨
• busy-wait(= spin lock)은 효율적이지 못함
• Block & Wakeup 방식(= sleep lock)으로도 구현 가능

Block & Wakeup Implementation

• Semaphore를 획득할 수 없는 경우 그 프로세스를 block시키고, 다른 프로세스가 shmaphore를 반납하면 block된 프로세스 중 하나를 깨움

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

• 여기에서의 S는 자원의 개수를 의미하지 않음. S의 값이 0보다 작다는 것은 누군가가 자원을 기다리고 있다는 의미이고, 양수인 경우 자원을 기다리고 있는 프로세스가 없다는 의미

• V 연산에는 자원을 기다리면서 잠들어 있는 프로세스가 있다면 그 프로세스를 깨워주는 작업이 포함되어 있어야 함

Block/wakeup overhead vs critical section 길이

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

Two Types of Semaphores

Counting semaphore

• 도메인이 0 이상인 임의의 정수값
• 주로 resource couting에 사용

Binary semaphore (= mutex)

• 자원의 개수가 하나인 경우
• 0 또는 1 값만 가질 수 있는 semaphore
• 주로 mutual exclusion (lock/unlock)에 사용

Semaphore 사용 시 발생할 수 있는 문제점

• 어떤 일을 하기위해 semaphore 두 자원(S, Q)을 모두 획득해야 한다고 가정
• Deadlock: 본인이 가진 자원은 내놓지 않고 상대방이 가진 자원을 얻기 위해 영원히 기다려야 하는 상황
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
  • 해결 방법: 자원을 획득하는 순서를 똑같게 맞춰주면 해결 가능
• Starvation: 특정 프로세스가 영원히 자원을 얻지 못하고 무한히 기다려야 하는 현상
  • indefinite blocking. 프로세스가 suspend된 이유에 해당하는 semaphore 큐에서 빠져나갈 수 없는 현상

• 모든 사람은 본인의 왼쪽, 오른쪽 사람과 젓가락을 공유
• 아래쪽 세 자리를 왼쪽부터 1, 2, 3번이라 가정
• Deadlock 발생
  • 모든 사람이 동시에 본인의 왼쪽 젓가락을 든 경우
• Starvation 발생
  • 2번에 앉은 사람이 젓가락을 들기 전 1번에 앉은 사람이 본인의 오른쪽 젓가락을 들고 식사를 시작하고, 1번에 앉은 사람이 젓가락을 내려놓기 바로 직적엔 3번에 앉은 사람이 본인의 왼쪽 젓가락을 들고 식사를 시작하고, 3번에 앉은 사람이 젓가락을 내려놓기 직전에 1번에 앉은 사람이 다시 젓가락을 드는 상황이 반복되면 2번의 경우 starvation이 발생

4. Classical Problems of Synchronization

Bounded-Buffer Problem (Producer-Consumer Problem)

• buffer의 크기가 유한함
  • circle 형태로 buffer가 구성됨
  • 주황색은 내용이 들어있는 버퍼, 회색은 내용이 비어있는 버퍼를 의미

• 생산자-소비자 문제: 프로세스가 두 가지 종류가 있음

  • Producer, Consumer가 각각 여러 개 존재
  • Producer는 공유 버퍼에 데이터를 하나 만들어서 집어넣는 역할을 하고, Consumer는 데이터를 꺼내는 역할을 함

• 문제점 1) 공유 버퍼에 lock을 걸어줘야하는 경우

  • 경우 1) 공유 버퍼이기 때문에 여러 생산자가 동시에 같은 빈 버퍼를 채우고자 하면 문제가 발생

  • 경우 2) 여러 소비자가 동시에 같은 버퍼의 내용을 꺼내가고자 할 때 문제 발생

  • 공유 버퍼에 데이터를 쓰거나 꺼내갈 때는 producer가 lock을 걸어 다른 producer가 접근하지 못하도록 막은 뒤에 데이터를 쓰거나 꺼내간 뒤 lock를 풀어줌

• 문제점 2) 공유 버퍼가 가득 차거나 빈 경우

  • 여러 생산자가 동시에 도착해 버퍼를 가득 채웠는데, 소비자는 오지 않고 생산자만 계속 와서 버퍼를 채우려고 하는 경우
  • 생산자 입장에서 버퍼가 가득 찬 경우, 소비자가 와서 버퍼의 내용을 꺼내갈 때까지 기다려야 함 (생성자 입장에서의 자원은 비어있는 버퍼)
  • 소비자 입장에서 다른 소비자들이 먼저 버퍼의 내용을 모두 꺼내가고 버퍼가 비었을 경우, 생산자가 와서 버퍼를 채워줄 때까지 기다려야 함 (소비자 입장에서의 자원은 채워져있는 버퍼)

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

• Synchronization variables

  • mutual exclusion: lock을 해주기 위해 binary semaphore 변수가 필요
  • resource count: 가용 자원의 개수를 세기 위한 integer semaphore 변수가 필요
• Bounded-Buffer 의사코드

​

Readers-Writers Problem

• 문제점 1) 한 프로세스가 DB(공유 데이터)에 write 중일 때 다른 process가 접근하면 안됨. 단, read는 여럿이 동시에 가능
  • 누군가 쓰는 경우에는 lock를 걸어 아무도 접근하지 못하게 막지만, 누군가 읽고 읽는 도중에 다른 reader가 도착하면 동시에 읽을 수 있게 해줘야 함
  • 누군가 읽고 있는 도중 writer가 도착하면 writer는 기다려야함. writer는 다른 작업이 아무 것도 없는 동안 배타적(독립적)으로 작업을 수행
• Shared data: DB 자체, readcount(현재 DB에 접근 중인 Reader의 수)
• Synchronizaion variables
  • mutex: 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용
    • readcount에 접근할 때 lock를 걸어주는 변수
  • db: Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
• Solution

• reader의 경우에도 lock은 걸어줘야 함. 읽고 있는 도중에 writer가 들어와서 lock을 걸 수 있기 때문
  • reader가 들어왔을 때 다른 reader가 읽고 있지 않다면 lock을 걸고 읽기 수행
  • reader가 들어왔을 때 다른 reader가 읽고 있다면 lock을 걸지 않고 읽기 수행
  • 마지막 reader가 읽고 나갈 때는 처음 걸어줬던 lock을 풀어줘야 함
• reader가 읽고 있는 도중에 writer가 들어오면 writer는 reader가 읽기를 수행한 뒤 lock을 풀어줄 때까지 기다려야 함
  • 만약, readcount가 1이었을 때 writer가 들어와서 대기하고 있는 도중, 1000개의 reader가 들어오면 writer는 1000개의 reader가 읽기를 수행하고 마지막 reader가 lock을 풀어줄 때까지 대기 해야 함
  • 즉, writer가 너무 오래 기다리기 때문에 starvation이 발생 가능
  • 큐에 우선순위를 줘서 writer가 너무 오래 기다리지 않도록 해줄 수 있게 구현할 수 있음 (일상생활에서의 ex. 신호등)

Dining-Philosophers Problem

• 철학자들은 생각하는 일과 밥 먹는 일을 수행

• 밥을 먹기 위해서는 왼쪽 젓가락과 오른쪽 젓가락을 모두 잡아야 함
• 문제점) Deadlock 가능성이 있음. 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
• 해결 방법 1) 4명의 철학자만이 테이블에 동시에 앉을 수 있게 함
• 해결 방법 2) 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 함
• 해결 방법 3) 비대칭 (짝수 철학자는 왼쪽 젓가락부터 잡도록, 홀수 철학자는 오른쪽 젓가락부터 잡도록 함)

5. Monitor

Semaphore의 문제점

• 코딩하기 힘듦
• 정확성(correctness) 입증이 어려움
• 자발적 협력(voluntary cooperation)이 필요
• 한번의 실수가 모든 시스템에 치명적 영향을 미침

• high-level synchronization construct
  • 동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 construct
• 공유 데이터에 대한 동시접근을 모니터가 막아줌

• 공유 데이터에 접근하기 위해서는 monitor 내부에 정의된 procedure를 통해야만 접근 가능
• 모니터 안에 공유 데이터와 공유 데이터 접근에 필요한 procedures를 정의

• Semaphore와의 차이점: 모니터는 기본적으로 모니터에 동시 접근이 불가능하도록 만들어져 있기 때문에 lock를 걸어줄 필요가 없음

• Semaphore와의 공통점: 자원의 개수를 세주는 변수가 필요

  • semaphore 변수와 비슷한 역할을 하는 condition variable이 있음

• condition variable (condition x, y;)

  • x라는 자원이 여분이 있으면 바로 접근하게 해주고, 여분이 없어 기다려야 하는 경우 wait(x.wait();) 연산 수행
  • 접근을 마치고 빠져나갈 때에는 signal(x.signal();) 연산을 통해 잠들어 있는 프로세스가 있으면 깨워줌
  • signal 연산은 깨워주는 연산이므로 깨워줄 프로세스가 없는 경우 아무 일도 일어나지 않음

Bounded-Buffer Problem

• 공유 버퍼가 모니터 내부에 정의되어 있기 때문에 생산하거나 소비하는 작업을 수행하기 위해서는 모니터 내부 코드를 실행해야 함
  • 생성자 혹은 소비자 모두 하나의 프로세스만 모니터 안에서 활성화되기 때문에 굳이 lock를 걸어줄 필요가 없음
  • 즉, 공유 데이터를 읽거나 쓰는 작업 앞뒤에 lock을 걸거나 풀어주는 코드가 없음
• 생산자 입장에서는 비어있는 버퍼가 필요
  • 비어있는 버퍼가 없다면 비어있는 버퍼를 기다리는 줄(empty)에 줄서서 기다리도록 함
  • 비어있는 버퍼가 있다면 비어있는 버퍼를 채워준 후, 버퍼가 비어있었기 때문에 잠들어있던 소비자가 있다면 깨워줌
• 소비자 입장에서는 내용이 들어있는 버퍼가 필요
  • 내용이 들어있는 버퍼가 없다면 내용이 들어있는 버퍼를 기다리는 줄(full)에 줄서서 기다리도록 함
  • 내용이 들어있는 버퍼가 있다면 버퍼의 내용을 꺼내간 후, 빈 버퍼를 기다리는 생산자가 있다면 깨워줌

Dining Philosophers Problem

• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 했을 때의 코드

Chapter 6 끝 !!!

게시물에 사용한 사진은 강의 내용을 캡쳐한 것입니다.

1. JAVA

• 자바의 정석의 “Chapter 11. 컬렉션 프레임웍” 부분을 공부했다.
• 컬렉션 프레임웍의 핵심 인터페이스와 그 인터페이스를 구현한 클래스들을 배움
  • ArrayList, LinkedList 클래스
  • Stack, Queue 인터페이스
  • Iterator
  • Arrays
  • Comparator, Comparable

2. CS (운영체제)

Process Synchronization 부분 강의를 수강했다.

오늘 배운 내용

• Process Synchronization 문제
  • race condition, critical-section problem
• Process Synchronization 문제 해결 알고리즘
  • Pererson’s Algorithm, Synchronization Hardware
• Semaphore와 Monitor
• Classical Problems of Synchronization
  • Bounded-Buffer Problem(Producer-Consumer Problem), Readers-Writers Problem, Dining-Philosophers Problem

3

오늘 생일이라 점심 식사를 가족들과 함께 먹고 나니 시간이 많이 흘러가 있어 알고리즘 문제를 풀지 못했다..

내일 오늘 풀지 못한 문제까지 두 문제를 풀어야겠다!

1. 날짜와 시간

1.1 Calendar와 Date

• Date는 날짜와 시간을 다룰 목적으로 JDK1.0부터 제공된 클래스
• Date 클래스의 기능이 부족해 Calendar라는 새로운 클래스를 JDK1.1부터 제공
• Calendar 클래스의 단점을 보완하기 위해 JDK1.8부터 ‘java.time 패키지’로 단점들을 개선한 새로운 클래스들이 추가됨

Calendar와 GregorianCalendar

• Calendar는 추상클래스이기 때문에 직접 객체를 생성할 수 없고, 메서드를 통해 완전히 구현된 클래스의 인스턴스를 얻어야 함

Calendar cal = new Calendar();	// 에러! 추상클래스는 인스턴스 생성 불가
Calendar cal = Calendar.getInstance();	// getInstance()는 Calendar 클래스를 구현한 클래스의 인스턴스를 반환

• getInstance() 메서드
  • 시스템의 국가와 지역설정을 확인해 태국인 경우 BuddhistCalendar의 인스턴스를 반환하고, 그 외에는 GregorianCalendar의 인스턴스를 반환
    • GregorianCalendar는 Calendar를 상속받아 전세계 공통으로 사용하고 있는 그레고리력에 맞게 구현한 것
  • static 메서드인 이유: 메서드 내의 코드에서 인스턴스 변수를 사용하거나 인스턴스 메서드를 호출하지 않기 때문 + static이 아닐 경우 객체를 생성한 다음에 호출해야하는데 Calendar는 추상클래스이기 때문에 객체를 생성할 수 없기 때문
• 메서드를 통해 인스턴스를 반환받게하는 이유: 최소한의 변경으로 프로그램이 동작할 수 있도록 하기 위한 것

Date와 Calendar간의 변환

• Calendar가 새로 추가되면서 Date는 대부분의 메서드가 ‘deprecated’되어 잘 사용되지 않음
• Date를 필요호하는 메서드들이 있는 경우 Calendar를 Date로 변환하거나 그 반대로 변환할 일이 생김

1. Calendar를 Date로 변환

   Calendar cal = Calendar.getInstance();
   	...
   Date d = new Date(cal.getTimeInMillis());	// Date(long date)
   

2. Date를 Calendar로 변환

   Date d = new Date();
   	...
   Calendar cal = Calendar.getInstance();
   cal.setTime(d);
   

2. 형식화 클래스

• java.text 패키지에 포함되어 있음
• 숫자, 날짜, 텍스트 데이터를 일정한 형식에 맞게 표현할 수 있는 방법을 객체지향적으로 설계하여 표준화함
• 형식화 클래스는 형식화에 사용될 패턴을 정의
  • 데이터를 정의된 패턴에 맞춰 형식화할 수 있고, 형식화된 데이터에서 원래의 데이터를 얻어낼 수도 있음
  • 형식화된 데이터의 패턴만 정의해주면 복잡한 문자열에서 substring()을 사용하지 않고 원하는 값을 얻을 수 있음

2.1 DecimalFormat

• 숫자를 형식화하는데 사용
• 숫자 데이터를 정수, 부동소수점, 금액 등의 다양한 형식으로 표현 가능하며, 일정한 형식의 텍스트 데이터를 숫자로 쉽게 변환하는 것도 가능

• 원하는 출력형식의 패턴을 작성해 DecimalFormat 인스턴스를 생성한 다음, 출력하고자 하는 문자열로 format메서드를 호출하면 원하는 패턴에 맞게 변환된 문자열을 얻게 됨

  double number = 1234567.89;
  DecimalFormat df = new DecimalFormat("#.#E0");
  String result = df.format(number)
  

2.2 SimpleDateFormat

• DateFormat은 추상클래스로 SimpleDateFormat의 조상
• DateFormat는 추상클래스이므로 인스턴스를 생성하기 위해서는 getDateInstance()와 같은 static 메서드를 이용해야 함
• getDateInstance()에 의해 반환되는 것은 DateFormat을 상속받아 완전하게 구현한 SimpleDateFormat 인스턴스

• 원하는 출력형식의 패턴을 작성하고 SimpleDateFormat 인스턴스를 생성한 다음, 출력하고자 하는 Date인스턴스를 가지고 format(Date d)를 호출하면 지정한 출력형식에 맞게 변환된 문자열을 얻게 됨

Date today = new Date();
SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd");

// 오늘 날짜를 yyyy-MM-dd 형태로 변환하여 반환
String resu;t = df.format(today);

• Calendar 인스턴스는 format 메서드 사용 불가. Calendar 인스턴스를 Date 인스턴스로 변환한 뒤 사용해야 됨

2.4 MessageFormat

• 데이터를 정해진 양식에 맞게 출력할 수 있도록 도와줌
• 데이터가 들어갈 자리를 마련해 놓은 양식을 미리 작성하고 프로그램을 이용해서 다수의 데이터를 같은 양식으로 출력할 때 사용하면 좋음
  • 고객들에게 보낼 안내문을 출력할 때 같은 안내문 양식에 받는 사람의 이름과 같은 데이터만 달라지도록 출력할 때
  • 하나의 데이터를 다양한 양식으로 출력할 때
• parse를 이요하면 지정된 양식에서 필요한 데이터만 추출 가능

3. java.time 패키지

• 위의 패키지들에 속한 클래스들의 가장 큰 특징은 ‘불변(immutable)’
  • 날짜나 시간을 변경하는 메서드들은 기존의 객체를 변경하는 대신 항상 변경된 새로운 객체를 반환
• 멀티 쓰레드 환경에서는 동시에 여러 쓰레드가 같은 객체에 접근할 수 있기 때문에, 변경 가능한 객체는 데이터가 잘못될 가능성이 있음 => 쓰레드에 안전(thread-safe)하지 않다

3.1 java.time 패키지의 핵심 클래스

• 날짜와 시간을 별도의 클래스로 분리해 놓음
  • 시간을 표현할 때는 LocalTime 클래스를, 날짜를 표현할 때는 LocalDate 클래스를 사용
  • 날짜와 시간이 모두 필요할 때는 LocalDateTime 클래스 사용
  • 날짜와 시간, 시간대(time-zone)을 다뤄야한다면 ZonedDateTime 클래스 사용

Period와 Duration

• Period = 날짜 - 날짜
• Duration = 시간 - 시간

객체 생성하기 - now(), of()

• now(): 현재 날짜와 시간을 저장하는 객체를 생성
• of(): 해당 필드의 값을 순서대로 지정해주면 됨. 각 클래스마다 댜앙한 종류의 of()가 정의되어 있음

Temporal, TemporalAccessor, TemporalAdjuster를 구현한 클래스

• LocalDate, LocalTime, LocalDateTime, ZonedDateTime, Instant 등

TemporalAmount를 구현한 클래스

• Period, Duration

3.2 LocalDate와 LocalTime

• 객체를 생성하는 방법은 현재의 날짜와 시간을 LocalDate와 LocalTime으로 각각 반환하는 now()와 지정된 날짜와 시간으로 LocalDate와 LocalTime 객체를 생성하는 of()가 있으며, 둘 다 static 메서드

• 특정 필드의 값 가져오기 - get(), getXXX()
• 필드의 값 변경하기 - with(), plus(), minus()
• 날짜와 시간 비교 - isAfter(), isBefore(), isEqual()

3.3 Instant

• 에포크 타임(EPOCH TIME, 1970-01-01 00:00:00 UTC)부터 경과된 시간을 나노초 단위로 표현
  • 단일 진법으로만 다루기 때문에 계산하기 쉬움
• Instant를 생성할 때는 now() 와 ofEpochSecond()를 사용
• Instant는 시간을 초 단위와 나노초 단위로 나누어 저장

3.6 Period와 Duration

between()

• 두 날짜의 차이를 나타내는 Period를 얻고자 할 때 사용

• date1이 date2보다 날짜 상으로 이전이면 양수, 이후면 음수로 Period에 저장

• 시간 차이를 구할 때는 Duration을 사용

get()

• 특정 필드의 값을 얻을 때
• Duration에는 getHours(), getMinites() 같은 메서드가 없음
  • Chrono.SECONDS, Chrono.NANOS를 사용해야 함
• Duration을 LocalTime으로 변환한다음, LocalTime이 가지고 있는 get메서드들을 사용하면 더 간단함

between()과 until()

• 같은 일을 하지만, between()은 static 메서드이고 until()은 인스턴스 메서드

3.7 파싱과 포맷

• 형식화와 관련된 클래스들은 java.time.format 패키지에 들어있는데 이 중 DateTimeFormatter가 핵심

• 날짜와 시간의 형식화에는 format()이 사용되는데, 이 메서드는 DateTimeFormatter뿐만 아니라 LocalDate나 LocalTime 같은 클래스에도 존재
• ofPattern() 으로 원하는 출력형식 직접 작성 가능

문자열을 날짜와 시간으로 파싱하기

• 문자열을 날짜 또는 시간으로 변환하려면 static메서드 parse()를 사용

• parse() 오버로딩 메서드

  static LocalDateTime parse(CharSequence text)
  static LocalDateTime parse(CharSequence text, DateTimeFormatter formatter)
  

KOCW에 공개된 이화여대 반효경 교수님 운영체제 강의를 수강 후 정리한 내용입니다.

1. CPU and IO Bursts in Program Execution

• CPU burst: CPU만 연속적으로 사용하면서 명령어를 실행하는 단계
• IO burst: IO를 실행하는 단계
• 프로그램이 실행되면 CPU burst와 IO burst를 번갈아가며 실행
  • 프로그램의 종류에 따라 CPU burst와 IO burst의 빈도와 길이가 달라짐

CPU burst Time의 분포

• IO bound job process: 중간에 IO 작업이 많아 CPU를 짧게 쓰기 때문에 CPU burst의 빈도가 높음
  • CPU를 잡고 계산하는 시간보다 IO에 많은 시간이 필요한 job
  • many short CPU bursts
• CPU bound job process: CPU를 오래 사용하기 때문에 CPU burst의 빈도가 낮음
  • 계산 위주의 job
  • few very long CPU bursts
• 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요
  • Interactive job에게 적절한 response 제공 요망
  • CPU와 IO 장치 등 시스템 자원을 효율적으로 사용

2. CPU Schedular & Dispatcher

CPU Scheduler

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름
• 운영체제 안에 CPU 스케줄링을 하는 코드가 있음

Dispatcher

• CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘기는 운영체제 안의 특정 기능
• 이 과정을 context switch라고 함

CPU 스케줄링이 필요한 경우

1. Running -> Blocked (ex. IO 요청하는 시스템 콜): 강제로 빼앗지 않고 자진 반납(nonpreemptive, 비선점형)
2. Running -> Ready (ex. 할당시간만료로 timer interrupt): 강제로 빼앗음(preemptive, 선점형)
3. Blocked -> Ready (ex. IO 완료 후 인터럽트): 강제로 빼앗음(preemptive, 선점형)
4. Terminate: 강제로 빼앗지 않고 자진 반납(nonpreemptive, 비선점형)

3. Scheduling Algorithms

Scheduling Criteria (성능 척도)

CPU utilization (이용률)

• 시스템 입장에서의 성능 척도
• 전체 시간 중에서 CPU가 일한 시간의 비율

Throughput (처리량)

• 시스템 입장에서의 성능 척도
• 주어진 시간 동안 몇 개의 작업을 완료했는지를 나타냄

Turnaround time(소요시간, 반환시간)

• 프로세스 입장에서의 성능 척도
• CPU를 사용하러 들어와서 다 쓰고 나갈 때까지 걸리는 시간 (대기 시간도 포함)

Waiting time (대기 시간)

• 프로세스 입장에서의 성능 척도
• CPU를 기다리는 시간

Response time (응답 시간)

• 프로세스 입장에서의 성능 척도
• ready queue에 들어와서 처음으로 CPU를 얻기까지 걸리는 시간

1. FCFS(First-Come First-Served)

• 먼저 온 순서대로 처리. 효율적이지는 않음
• 비선점형 스케줄링
• 프로세스 도착 순서를 바꿔보면
  • wating time이 많이 줄어드는 것을 확인할 수 있음
• convoy effect: burst time이 긴 프로세스가 먼저 도착해서 짧은 프로세스가 오래 기다리게 되는 현상

2. SJF(Shortest-Job-First)

• 각 프로세스와 다음번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• SRTF 알고리즘은 average waiting time을 최소화한 알고리즘 (optimal)

nonpreemptive

• 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
• 하나의 프로세스가 CPU를 다 쓰고 나가는 시점에 스케줄링을 할지 안할지 결정

preemptive

• SRTF(Shortest-Remaining-Time-First): 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
• 새로운 프로세스가 도착하는 시점에 언제든지 스케줄링이 이루어짐

예시

문제점

• starvation(기아 현상): CPU 사용 시간이 긴 프로세스는 CPU를 할당받는데 너무 오래 걸리거나 아예 실행되지 않을 수 있는 현상
• CPU 사용 시간을 미리 알 수 없다는 문제점이 있음
  • 단, 과거 사용 시간을 통해 추정이 가능하므로 SJF 알고리즘을 사용할 수 있는 것

3. Priority Scheduling

• 우선순위 스케줄링
• 우선순위가 가장 높은 프로세스에게 CPU를 할당
  • 각각의 프로세스에 우선순위를 나타내는 숫작가 할당됨
  • 가장 높은 우선순위 프로세스는 가장 작은 수가 할당된 프로세스
• nonpreemptive 방식과 preemptive 방식이 있음
• SJF는 우선순위 스케줄링의 일종이라고 볼 수 있음
  • SJF는 우선순위를 CPU의 burst time으로 정의한 것
• 문제점
  • Starvation: 우선순위가 낮은 프로세스가 CPU 할당받는데 너무 오래 걸리거나 아예 실행되지 않을 수 있는 현상
• 해결방법
  • Aging: 아무리 우선순위가 낮은 프로세스라도 오래 기다리는 경우 우선순위를 조금씩 높여주는 방법

4. Round Robin (RR)

• 현대에서 사용하는 스케줄링 방식은 RR에 기반됨
• preemptive 방식
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐. 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 섬
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻음
  • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음
  • q를 너무 크게 잡으면 FCFS와 비슷해지고, 너무 작게 잡으면 context switch 오버헤드가 커짐
• CPU를 길게 쓰는 프로세스는 기다리는 시간도 길어지고, 짧게 쓰는 프로세스는 기다리는 시간도 짧음
  • wating time이 CPU burst time과 비례
• 장점: 응답 시간(response time)이 빠름

예시

• SJF보다 average turnaround time이 길지만 response time은 더 짧음

4. Multilevel Queue

• 줄마다 우선순위가 존재
• 위에있는 줄일수록 높은 우선순위를 가짐
• 출신에 따라 우선순위가 달라짐
• 줄이 여러 개인데 CPU는 하나이므로 고려해야할 사항이 생김
  • Process를 어느 줄에 넣을 것인가
  • 우선순위가 높은 줄에만 CPU를 줄 경우 우선순위가 낮은 줄에서는 starvation이 발생할 수 있음

1. Multilevel Queue

• 본인의 출생을 극복하지 못함 (프로세스가 다른 큐로 이동 불가)
• Ready queue를 여러 개로 분할
  • foreground (interactive)
  • background (batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR (사용자와 interaction을 하므로 응답시간이 빠른 RR를 사용)
  • background - FCFS (사용자와 interaction을 하지 않으므로 context switch 오버헤드를 줄이기 위해 FCFS를 사용)
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling: 우선순위가 높은 큐에게 먼저 CPU를 할당
  • Time slice: 각 큐에 CPU time을 적절한 비율로 할당

2. Multilevel Feedback Queue

• 본인 출생 극복 가능 (프로세스가 다른 큐로 이동 가능)
• aging을 이와 같은 방식으로 구현 가능
• CPU burst time이 짧은 프로세스에게 우선순위를 많이 주는 방식
• Multilevel-feedback-queue scheduler를 정의하는 파라미터
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 보내는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
• 일반적으로
  1. 처음으로 들어오는 프로세스를 우선순위가 높은 큐에 주고 RR 알고리즘의 quantum를 짧게 줌
  2. 아래 큐로 갈수록 quantum를 길게 줌
  3. 제일 아래 큐는 FCFS 알고리즘 사용

5. 여러 Scheduling 방법

1. Multiple-Processor Scheduling

• CPU가 여러 개인 경우의 스케줄링

Homogeneous processor인 경우

• Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음
• 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 더 복잡해짐

Load sharing

• 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘이 필요
• 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법

Symmetric Multiprocessing(SMP)

• 모든 CPU가 대등한 관계
• 각 프로세서가 각자 알아서 스케줄링 결정

Asymmetric multiprocessing

• 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

2. Real-Time Scheduling

• deadline은 보장해줘야 함

Hard real-time systems

• 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함

Soft real-time computing

• 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

3. Thread Scheduling

Local Scheduling

• User level thread(운영체제가 모르는 thread)의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• 운영체제가 아닌 사용자 프로세스가 직접 어느 thread에게 cpu를 줄지 경정

Global Scheduling

• Kernel level thread의 경우 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

6. Algorithm Evaluation

• server: CPU
• arrival rate: 프로세스 도착률
• service rate: 프로세스 처리률 (CPU가 단위시간당 처리하는 프로세스의 비율)

Queueing models

• 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각 종 performance index 값을 계산

Implementation(구현) & Measurement(성능 측정)

• 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

Simulation (모의 실험)

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
  • trace: simulation 프로그램에 input으로 들어갈 데이터
  • 만들 수도 있고 실제 프로그램을 돌리면서 뽑아낼 수도 있음

Chapter 5 끝!!!

게시물에 사용한 사진은 강의 내용을 캡쳐한 것입니다.

bronze 2. 거스름돈(5585)

출처 : https://www.acmicpc.net/problem/5585

문제

잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔 1엔이 있을 때, 1000엔을 지불하고 받은 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성

입력: 타로가 지불해야할 돈 1개가 쓰여져 있음

출력: 잔돈에 포함된 매수

풀이

• 아이디어: 가장 큰 화폐 단위부터 거슬러줌

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int count = 0;	// 잔돈 개수
        int num = 1000 - sc.nextInt();	// 받아야할 거스름돈
        int[] coinTypes = {500, 100, 50, 10, 5};	// 거스름돈 동전 종류
        
        // 가장 큰 화폐 단위부터 거슬러줌
        for (int i=0; i<coinTypes.length; i++){
            int coin = coinTypes[i];
            count += num / coin;
            num %= coin;
        }
        
        // 남은 돈이 1엔 단위일 경우 따로 처리
        if (num != 0){
            count += num;
        }
    }
}