학습한 내용

edwith 컴퓨터 과학 교양 cs50

비트와 바이트

비트

• 이진 숫자 (binary digit)
• 0과 1 두가지 값만 가질 수 있는 측정 단위
• n비트로 2의 n 제곱 만큼의 정보를 표현 가능

비트열

• 바이트
  • 여덟 개의 비트가 모인 것

디지털 논리회로

조합논리회로 - 반가산기 전가산기

출처 : 유튜브 대멀쌤

자바의 정석 ch2 변수

진법(42p)

2진수를 8진수, 16진수로 변환

• 2진수를 8진수로 변환하려면 뒤에서부터 3자리씩 끊어서 해당하는 8진수로 바꾸면 된다.
• 2진수에서 16진수는 뒤에서부터 4자리씩

10진수를 n진수로 변환

• 해당 진수로 끝까지 나누어 준 다음, 마지막 몫과 나머지들을 순서대로 적으면 n진수로 변환 된다.

n진수를 10진수로 변환

• 각 자리수의 해당 단위값을 다 더한다.
• 예) 110018
  $(2^0 * 1) + (2^1 * 0) + (2^2 * 0) + (2^3 * 1) + (2^4 * 1) = 25$

---

운영체제 강의 5차시 CPU scheduling1

http://www.kocw.or.kr/home/cview.do?mty=p&kemId=1046323
출처 : kocw 이화여대 운영체제 (반효경 교수님)

• 공평한 스케쥴링도 중요하지만 효율적인 스케쥴링도 중요

Scheduling criteria (Performance index = performance Measure, 성능척도)

→ Scheduling Algorithms 이 어떤게 좋은지 평가하는 방법

• 시스템 입장에서 성능척도

  →시스템 입장에서는 최대한 CPU에게 일을 많이 시키면 좋다.

  • CPU utilization (이용률)
    • keep the CPU as busy as possible
    • CPU가 놀지 않고 일한 시간의 비율
  • Throughput(처리량)
    • 주어진 시간동안 몇개의 작업을 완료했느냐
    • #of processes that complete their execution per time unit

• 프로그램 입장에서 성능 척도

  → 프로세스 입장에서 성능 척도, 내가 CPU를 빨리 얻어서 빨리 끝나면 좋다, 시간을 얼마나 빨리 처리 할 수 있느냐

  • Turnaround time(소요시간, 반환시간) → waiting time 포함

    • amount of time to execute a particular process

    • CPU를 쓰러 들어와서 다 쓰고나서 빠져나갈때 까지 걸리는 시간

      → process의 총 실행시간이 아님, CPU 사용의 총 소요시간

  • Waiting time(대기시간)

    • 순수하게 기다리는 시간
    • amount of time a process has been waiting in the ready queue

  • Response time(응답 시간)

    • Ready queue 에 들어와서 처음으로 CPU를 얻기까지 걸리는 시간
    • amount of time it takes from when a request was submitted until the first response is produced not output (for time-sharing environment)

Scheduling Algorithms

• FCFS (First come first served)
• SJF(Shortest-Job-First)
• SRTF(Shortest-Remaining-Time-First)
• Priority Scheduling
• RR(Round Robin)
• Multilevel queue
• Multilevel feedback Queue

FCFS (First come first served)

• 먼저 온 순서대로 처리하는 것
• 비선점형 nonpreemptive
• 시간적으로 그닥 효율적이지 않음
• convoy effect
  • short process behind long process
  • 긴 프로세스가 먼저 도착해서 짧은 프로세스들이 오랜시간 기다려야하는 현상

SJF(Shortest-Job-First)

• 각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 활용

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴

• 전체적으로 짧은 average waiting time이 보장됨(모든 스케쥴링 중 minimum 보장) → preemptive의 경우

• Two schemes

  • Nonpreemptive
    • 일단 CPU를 잡으면 더 짧은 프로세스가 도착하더라도 해당 프로세스가 CPU사용권을 보장받는 것
    • 해당 프로세스가 CPU 사용권을 보장받는 것
  • Preemptive
    • CPU를 잡더라도 더 짧은 프로세스가 도착하면 CPU를 뺏어서 더 짧은 프로세스에게 넘겨주는 것
    • 이 방법을 shortest-Remaining-Time-Frist(SRTF) 라고도 부른다.

• 문제점

  1. CPU 사용시간이 긴 프로세스는 영원히 실행하지 못할 수도 있다.

     (starvation : 기아현상)

  2. CPU 사용시간을 미리 알 수 없다.

다음 CPU burst time의 예측

• CPU burst time : CPU가 일을 수행하는 시간
• 다음번 CPU burst time을 어떻게 알 수 있는가?
• 추정(estimate)만 가능
• 과거의 CPU burst time을 이용해서 추정

Priority Scheduling

• 우선 순위가 제일 높은 프로세스에게 CPU를 주는 것
• highest priority를 가진 프로세스에게 CPU를 할당
  • preemptive → 더 높은 우선순위의 프로세스가 도착하면 CPU를 빼앗음
  • nonpreemptive → 더 높은 우선순위의 프로세스가 도착해도 CPU를 빼앗기지 않음
• SJF도 일정의 priority scheduling 임
  • priority = predicted next CPU burst time
• 문제점
  • starvation(기아현상) : 우선순위가 낮은 프로세스는 영원히 CPU를 얻지 못할 수도 있다.
• solution
  • Aging(노화) : 아무리 낮은 우선순위의 프로세스이더라도 오래 기다리면 우선순위를 높여주는 것

Round Robin(RR)

• 현대적인 CPU스케쥴링은 RR을 기반으로 함

• CPU를 줄때 할당 시간을 셋팅해서 넘겨주고, 할당시간이 끝나면 Timer interrupt 가 걸려서 CPU를 뺏어간다.

• 각 프로세스는 동일한 크기의 할당시간(time quantum)을 가짐

• 할당시간이 지나면 프로세스는 선점(preempted) 당하고, ready queue의 제일 뒤에 가서 다시 줄선다.

• 응답시간이 빠르다는 장점

• n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU시간의 1/n 을 얻는다.

  → 대기시간은 본인이 CPU를 사용하는 시간에 비례한다.

• Performance

  • q time (할당 시간) 큰 경우 : FCFS
  • q time (할당 시간) 작은 경우 : context switch 가 너무 빈번해서 오버헤드가 커져서 시스템 전체 성능 저하
  • 결론 : 적당한 시간의 할당시간 부여 필요

오늘 한 일

• 반효경 교수님 운영체제 강의 5주차 CPU scheduling 1 강의 마저 수강하고 노트 정리
  • 뒤로 갈수록 더 복잡해진다. 설명을 쉽게 해주셔서 이해만 가는 수준이다. 전체적인 그림이 희미하게 그려지는 것 같다.

reminder

• 좀 더 의식적인 학습 하도록 노력하기
• 반효경 교수님 운영체제 강의를 들으면서 비전공자이기 때문에 PPT내용과 교수님이 설명해주시는 말을 다 받아 적어서 최대한 이해하려했고, 노션에 다시 정리했지만 점점 많은 수의 강의를 듣다 보니 일일히 펜으로 다 받아 적는건 힘든 것 같다. 일단 노션으로 필기 받아적고 잘 정리해서 복습하는 방향으로 해보자.
  • 뒤로 갈수록 강의 내용이 어렵다. 운영체제 책을 구매해서 병행학습 하자.