💻 Code Editor 2

1) 문자열 곱하기

• 문제 문자열 my_string과 정수 k가 주어질 때, my_string을 k번 반복한 문자열을 return 하는 solution 함수를 작성해 주세요.

• 입출력 예

  • [my_string | k | result]
  • "string" | 3 | "stringstringstring"
    • "love" | 10 | "lovelovelovelovelovelovelovelovelovelove"

• 코드

// case 1
function solution(my_string, k) {
    var answer = '';

    for(var i=0; i<k; i++) {
        answer += my_string;
    }

    return answer;
}

// case 2
function solution(my_string, k) {
    return my_string.repeat(k)
}

// console.log(solution('love', 3));

2) n보다 커질 때까지 더하기

• 문제 정수 배열 numbers와 정수 n이 매개변수로 주어집니다. numbers의 원소를 앞에서부터 하나씩 더하다가 그 합이 n보다 커지는 순간 이때까지 더했던 원소들의 합을 return 하는 solution 함수를 작성해 주세요. 제한사항) 1 ≤ numbers의 길이 ≤ 100 1 ≤ numbers의 원소 ≤ 100 0 ≤ n < numbers의 모든 원소의 합

• 입출력 예

  • [numbers | k | result]
  • [34, 5, 71, 29, 100, 34] | 123 | 139
    • [58, 44, 27, 10, 100] | 139 | 239

• 코드

// case 1
function solution(numbers, n) {
    var answer = 0;

    for(var i=0; i<numbers.length; i++) {
        answer += numbers[i];

        if(answer > n) return answer;
    }
}

// case 2
function solution(numbers, n) {
    var answer = 0;

    let i = 0;
    while(answer <= n) {
        answer += numbers[i++]
    }

    return answer;
}

// console.log(solution([58, 44, 27, 10, 100], 139))

3) 특수문자 출력하기

• 문제 다음과 같이 출력하도록 코드를 작성해 주세요.
• 출력 예시 !@#$%^&*('"<>?:;
• 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('close', function () {
  console.log(`!@#$%^&*(\\'"<>?:;`);
});

규칙을 일일이 프로그래밍하지 않아도 자동으로 데이터에서 규칙을 학습하는 알고리즘을 연구하는 분야

일반적인 프로그래밍은 특정한 프로그램을 만들어 데이터를 처리하고 내보내 결과를 만들어 낸다.

ex) 기존의 이미지 처리 : 물체의 이미지 정보를 읽어 사람이 직접 함수를 거는 것

이와 반대로 머신러닝은 전통적인 프로그래밍으로는 접근하기 어려운 여러 다양한 유형의 데이터들(ex. 글, 이미지, 동영상 등의 비정형데이터)을 이용하여 기계에 학습시켜 특정한 결과물(규칙, 아이디어 등)을 만들어낸다.

ex) 이미지 처리 with 머신러닝 : 사람이 하던 함수 설정을 컴퓨터가 학습(training)을 통해 러닝 함수 f(x)를 찾아가고 새로운 데이터를 러닝 함수 f(x)에 입력하면 예측(predict)을 통해 output을 도출하는 것

기계 학습을 위한 방법

• 지도 학습 (Supervised Learning)
• 비지도 학습 (Unsupervised Learning)
• 강화 학습 (Reinforcement Learning)

딥러닝

머신러닝 알고리즘 중에 인공 신경망(artificial neural network)을 기반으로 한 방법들을 통칭

머신러닝 기법 중 하나로 말 그대로 기계를 "심화학습"시키는 것을 의미하며,

머신러닝 모델은 학습을 통해 점차적으로 향상되지만, 이러한 AI 알고리즘이 부정확한 예측을 반환하면 엔지니어가 개입하여 조정해야한다. 그러나 딥러닝 모델을 사용하면 알고리즘이 머신러닝으로 쌓아올린 자체 신경망을 통해 예측의 정확성 여부를 스스로 판단할 수 있습니다.

인간의 신경망 원리를 모방한 인공신경망을 통해 사람의 도움없이 기계가 스스로 학습하고 판단을 내린다는 것이 가장 큰 특징이다.

딥러닝 모델 종류

인간의 논리 구조인 인공 신경망에 얼마나 근접한 알고리즘 구조를 갖췄는가 ?

• CNN

  • Convolutional Neural Network, 합성곱 신경망

  • 인간의 시신경 구조(퍼셉트론)를 모방한 기술

  • 노드 간 연결 갯수가 기하급수적으로 증가하여 크기가 작은 필터를 사용함

  • 이로 인해 가중치의 개수를 줄여주며 국부 영역에 대한 특징에 집중할 수 있는 특성이 있음

  • 위의 특징으로 학습이 가능해 비전 분야에서 성능이 우수함

  • 이미지를 인식하기 위해 패턴을 찾는데 특히 유용함

  • 데이터를 직접 학습하고 패턴을 사용해 이미지를 분류함

  • 자율주행자동차, 얼굴인식과 같은 객체인식에 사용되고 있음

  • 사람이 여러 데이터를 보고 기억한 후에 무엇인지 맞추는 것과 유사함

• RNN

  • Recurrent Neural Network, 순환 신경망
  • 순차적 정보가 담긴 데이터에서 규칙적인 패턴을 인식하고 추상화된 정보를 추출함
  • 텍스트, 음성, 음악, 영상 등 순차적 데이터를 다루는데 적합함
  • 마치 우리가 적성검사의 추론 영역을 푸는 것과 유사함

• GAN

  • Generative Adversarial Network, 생성 대립 신경망
  • 비지도 학습 방법으로 학습된 패턴을 이용해 이미지나 음성을 생성함
  • 이미지 및 음성 복원에 주로 적용됨
  • 누군가를 성대 묘사, 얼굴 묘사하는 것과 유사함

• RL

  • Reinforcement Learning, 강화학습
  • 구글의 딥마인드에서 개발한 것으로 관계형 추론을 지원함
  • 지금까지 딥러닝은 분류, 이미지 인식, 음성 인식, 번역, 이미지 생성에만 국한된 한계가 있었음
  • RL은 딥러닝 기술을 인간의 사고에 근사한 논리적 추론이 가능한 분야까지 확대시킴
  • 정해진 규칙이 없는 관계를 추론 하는 것과 유사함

딥러닝과 머신러닝의 차이

머신러닝

: 사람이 동물의 특징을 분류하여 어떤 동물인지 알 수 있도록 학습시켜야 함

딥러닝

: 단순 사진만을 보고 기계가 인공신경망을 통해 스스로 학습하여 어떤 동물인지 분류하게 됨

딥러닝이 필요한 이유

• 데이터에 너무나 많은 기능이 있을 경우
• 데이터가 방대할 경우
• 높은 수준의 정확도가 필요한 경우

대용량 데이터를 활용, 분석하여 가치있는 정보를 추출하고 생성된 지식을 바탕으로 능동적으로 대응하거나 변화를 예측하기 위한 정보화 기술이다.

빅 데이터의 5V

• Volume (용량)
  • 기업이 관리하고 분석하는 빅 데이터 크기와 양
• Velocity (속도)
  • 회사가 데이터를 수신, 저장 및 관리하는 속도 ex) 특정 기간 내에 수신된 특정 소셜 미디어 게시물 또는 검색 쿼리 수
• Variety (다양성)
  • 비정형 데이터, 반정형 데이터 및 원시 데이터를 포함하는 다양한 데이터 유형 ex) 스마트폰, 사내 장치, SNS 채팅 프로그램, 주식 시세 데이터 및 금융 거래 데이터
• Veracity (진실성)
  • 경영진들의 신뢰도에 영향을 미치는 데이터 및 정보 자신의 진실 또는 정확성
• Value (가치)
  • 비즈니스 관점에서 가장 중요한 'V'인 빅 데이터의 가치는 일반적으로 보다 효과적인 운영, 더 강력한 고객 관계 및 기타 명확하고 수량화 가능한 비즈니스 이점으로 이어지는 통찰력 발견 및 패턴 인식에서 나옴

빅데이터 기술

Hadoop & NoSQL

웹 서버에서 생성된 데이터는 RDB나 NoSQL에 텍스트 데이터 형태로 저장되고, 그 후 모든 데이터가 Hadoop에 모여서 대규모 데이터처리가 실행된다.

Hadoop

다수의 컴퓨터로 대량의 데이터를 처리하기 위한 시스템

방대한 데이터를 저장할 스토리지와 이를 순차적으로 처리할 수 있는 구조가 필요해 ! → 이를 가능하게 해주는 툴이 Hadoop이고, 구글에서 개발된 분산 처리 프레임워크인 ‘MapReduce’를 기반으로 제작됨

NoSQL

NoSQL은 기존의 RDB의 정형화된 데이터 형태에서 벗어난 데이터베이스의 총칭을 의미한다. 대표적인 3가지는 Key-Value, Document, wide-column 이다.

• Key-value: 문자 그대로 키값 밸류값이 한쌍으로 저장되어지는 데이터 베이스
• Document: Json과 같은 복잡한 데이터 구조를 저장
• Wide-column: 여러 키를 사용하여 확장성에 장점이 있는 데이터베이스

ETL 파이프라인

ETL은 Extraction Transform Loading의 약자로, 데이터를 추출하고 가공한 뒤 적재하는 일련의 과정을 의미한다.

하기 그림은 추출한 데이터를 데이터 웨어하우스에 저장하기까지의 과정이다.

데이터 레이크 (Data Lake) : 다양한 형태와 경로에서 생성된 데이터를 한 곳에 가공 없이 그대로 저장하는 것 ex) 아마존 - S3

데이터 가져오기 (Data Ingestion) : 데이터를 활용할 수 있는 형태로 저장하는 과정 (=전처리 과정)

데이터 웨어하우스 (Data Warehouse) : '데이터 가져오기'가 완료된 데이터를 저장하는 장소 ex) 아마존 - Redshift / 구글 - BigQuery / IBM - Db2

데이터 마트 (Data Mart) : '데이터 웨어하우스'의 하위 영역 데이터를 실제로 사용하는 부서의 레벨이나 관련 주제 위주로 접근할 수 있도록 가공한 시스템

커넥터 (Connector) : '데이터 웨어하우스'의 데이터가 각 사용처로 흘러들어가 다양한 용도로 사용될 수 있도록 DB와 각종 어플리케이션을 연결하는 과정 ex) 실시간으로 품절된 상품을 고객이 구매하지 못하도록 표시하는 데에 사용

BI (Business Intelligence) : 데이터를 정리하고 분석해, 비스니스 의사결정을 돕는 시각화 기술

빅 데이터 실행

Data에서 Insight를 도출하여 Value를 창출해내는 일련의 과정을 의미한다.

즉, 데이터에서 사업적 가치를 창출하는 것을 말한다. ex) 아마존 - 고객의 구매정보를 이용한 고객 추천 서비스 제작 -> 매출 40% 향상

연속 메모리 할당

메모리 공간에 프로세스를 연속적으로 할당하는 방식을 연속 메모리 할당 이라고 한다.

프로세스들을 실행하다보면 메모리 공간이 가득 차게 되는데 그러면 새로운 프로세스를 할당할 수 없게 된다. 이 때, 오랫동안 사용하지 않은 프로세스를 보조기억장치 일부 영역으로 임시로 쫒아내고 그렇게 마련된 빈 공간에 새 프로세스를 적재하곤 하는데 이릘 스와핑(swapping) 이라고 한다.

• 스왑 영역 (swap space) 쫒겨난 프로세스를 임시로 보관하는 보조기억장치의 일부 영역

• 스왑 아웃 (swap out) 현재 실행되지 않는 프로세스를 메모리에서 스왑 영역으로 옮기는 것

• 스왑 인 (swap in) 스왑 영역에 있던 프로세스를 다시 메모리로 옮겨오는 것 기존의 물리 주소와는 다른 곳에 적재될 수 있다

이를 통해 프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 큰 경우에도 문제 없이 프로세스를 동시에 실행할 수 있다.

메모리 내 빈 공간이 여러 개 있을 때 프로세스를 할당하는 방식은 여러 가지가 있지만 그 중 대표적인 세 가지를 알아보도록 하겠다.

• 최초 적합 (front fit) 운영체제가 메모리 내 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 배치 검색을 최소화하여 빠른 할당 가능

• 최적 적합 (best fit) 운영체제가 메모리 내 빈 공간을 모두 검색해본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 배치 잉여 공간의 최소화 가능

• 최악 접합 (worst fit) 운영체제가 메모리 내 빈 공간을 모두 검색해본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 배치

연속 메모리 할당은 단순하고 간편하지만 외부 단편화 (external fragmentaion) 문제를 내포하고 있다. 이것은 프로세스를 할당하기 어려울 만큼 작은 공간들로 인해 메모리가 낭비되는 현상이다. 이러한 잉여 공간들이 쌓이면 낭비되는 공간이 상당히 많기 때문에 반드시 해결해야 하는 문제다.

외부 단편화 문제를 해결하기 위해 메모리를 압축 (compaction) 할 수 있는데, 잉여 공간을 한 데 모으는 동안의 오버헤드가 크기 때문에 단점이 많다.

이 문제를 해결하는 다른 방법으로는 페이징 기법이 있다.

더 알아보기 [컴퓨터 공학 기초 강의] 37강. 연속 메모리 할당

페이징을 통한 가상 메모리 관리

프로세스의 일부만 메모리에 적재하여 실제 물리 메모리보다 더 큰 프로세스를 실행할 수 있는 기법을 가상 메모리(virtual memory) 라고 하며, 크게 페이징, 세그멘테이션의 두 가지 기법이 있다.

현재 대부분의 운영체제는 페이징 기법을 통해 가상 메모리를 구현한다.

페이징(paging) 은 메모리와 프로세스를 일정한 단위로 자르고 프로세스를 메모리에 불연속적인 조각 단위로 할당하는 기법이다.

• 페이지 (page) 프로세스의 논리 주소 공간을 일정한 크기 단위로 자른 것

• 프레임 (frame) 메모리의 물리 주소 공간을 일정한 크기 단위로 자른 것

페이지와 프레임은 동일한 크기로 설정되며, 이 크기 단위로 메모리 할당이 이루어진다.

프로세스 크기가 페이지 단위의 배수로 나누어 떨어지지 않기에 마지막 페이지에는 잉여 공간이 생길 수 있는데
이를 내부 단편화(internal fragmentation) 라고 하지만, 외부 단편화보다는 훨씬 적은 양이다.

페이지 또한 스왑 인/아웃 될 수 있는데, 이 때는 프로세스 단위가 아닌 페이지 단위로 이동한다. 프로세스 단위의 이동과 구분하여 페이지 아웃 (page out), 페이지 인 (page in) 이라고도 한다.

페이지를 사용하면 외부 단편화 문제를 해결할 수 있을 뿐만 아니라, 물리 메모리보다 큰 프로세스도 실행할 수 있다.

페이지는 메모리에 불연속적으로 적재되기 때문에 그대로 사용하기 어려운데 논리 주소의 연속성을 유지한 채 불연속적인 페이지와 맵핑하기 위해 페이지 테이블(page table) 을 이용한다.

페이지 테이블은 페이지 번호와 프레임 번호를 맵핑해둠으로써 CPU가 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 해준다. 이를 통해 CPU는 프로세스들이 메모리에 분산되어 있더라도 논리 주소를 통해 순차적으로 실행한다.

각각의 프로세스는 고유의 페이지 테이블을 메모리에 가지고 있으며 PCB의 페이지 테이블 베이스 레지스터(PTBR) (page table base register) 에 그 시작 주소가 담긴다.

페이지 테이블은 메모리에 저장되기 때문에, 이를 통해 페이지에 접근하면 메모리 접근을 두 번 해야 한다는 문제가 있어 참조 지역성에 근거한 일종의 캐시 메모리를 두는데 일반적으로 MMU 내에 존재하며 TLB (translation lookaside buffer) 라고 부른다. 캐시 메모리와 마찬가지로 참조하고자 하는 페이지 존재 유무를 TLB 히트/미스 (TLB hit/miss) 라고 하며 TLB 미스 시 페이지 테이블을 참조하기 위해 메모리에 접근한다.

특정 주소에 접근하기 위해서는 두 가지 정보가 필요한데, 이에 따라 페이징 시스템의 논리 주소는 두 부분으로 이루어져 있다.

• 페이지 번호 (page number) 접근하고자 하는 페이지가 무엇인지 나타내는 N 비트
• 변위 (offset) 접근하고자 하는 주소가 페이지 내 어디에 저장되어 있느닞 나타내는, N 비트를 제외한 나머지 비트

<페이지 번호, 변위>로 구성된 논리 주소는 페이지 테이블을 거쳐 <프레임 번호, 변위>로 구성된 물리 주소로 변환된다.

페이지 테이블의 각각의 행들은 페이지 테이블 엔트리(page table entry) 라고 하는데 페이지 번호, 프레임 번호 외에도 유효 비트, 보호 비트, 참조 비트, 수정 비트 등의 정보가 포함되어 있다.

• 유효 비트 (valid bit) 현재 해당 페이지에 접근 가능한지 여부 아직 적재되지 않았거나 스왑 아웃되었을 경우 0이 되며, 접근 시도 시 페이지 폴트 page fault 예외 발생

• 보호 비트 (protection bit) 읽고 쓰기가 가능한 페이지인지 여부 쓰기가 가능하면 1, 읽기 전용일 경우 0의 값 읽기/쓰기/실행하기의 3개 비트로 보다 상세한 권한을 설정하도록 구현할 수도 있다

• 참조 비트 (reference bit) CPU가 접근한 적 있는지 여부

• 수정 비트 (modified bit) 해당 페이지에 데이터를 쓴 적 있는지 수정 여부 더티 비트 dirty bit 라고도 한다 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지 결정

프로세스의 모든 테이블 페이지 엔트리를 메모리에 유지하는 것은 비효율적이기 때문에 계층적 페이징 hierarchical paging 을 통해 여러 단계의 페이지를 두기도 한다.

더 알아보기 [컴퓨터 공학 기초 강의] 38강. 페이징을 통한 가상 메모리 관리

페이지 교체와 프레임 할당

프로세스를 메모리에 적재할 때 모든 페이지를 적재하지 않고 필요한 페이지만 적재하는 기법을 요구 페이징(demand paging) 이라고 한다.

그 중에서도 처음엔 아무 페이지도 적재하지 않은 채 실행부터 하고서 페이지 폴트가 발생할 때마다 하나씩 적재하는 방식을 순수 요구 페이징(pure demand paging) 이라고 한다.

요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당이 잘 이루어져야 한다.

요구 페이징 기법으로 페이지를 적재하다보면 메모리가 가득 차게 되어 스왑 아웃을 해야 하는데 어떤 페이지를 스왑 아웃 할 것인지 결정하는 방법을 페이지 교체 알고리즘 이라고 한다. 페이지 교체 알고리즘은 페이지 폴트를 적게 일으킬수록 좋은 알고리즘이다.

페이지 교체 알고리즘의 성능 측정 지표가 되는 페이지 폴트 횟수는 페이지 참조열(page reference string) 을 통해 알 수 있다. CPU가 참조하는 페이지 중 연속된 페이지를 생략한 페이지열을 페이지 참조열이라고 한다.

대표적인 페이지 교체 알고리즘으로는 다음과 같은 것들이 있다.

• FIFO 페이지 교체 알고리즘 (First-In First-Out page replacement algorithm) 가장 단순한 방법으로, 메모리에 가장 먼저 올라온 페이지부터 교체 대상으로 삼는 방식 초기에 적재된 페이지는 초반에만 실행되고 말 수도 있지만, 프로그램 실행 내내 사용할 내용을 포함할 경우 비효율적일 수 있다

• 2차 기회 페이지 교체 알고리즘 (Second Chance page replacement algorithm) FIFO 페이지 교체 알고리즘을 보완하여 두 번째 기회를 주는 방식 교체 대상 페이지가 참조된 적 없는 페이지일 경우 그냥 교체하지만 참조된 적 있는 경우 참조 비트를 0으로 만든 후 현재 시각을 적재 시각으로 설정하여 오래되었지만 자주 쓰이는 페이지가 쫒겨나지 않도록 한다

• 최적 페이지 교체 알고리즘 (Optimal page replacement algorithm) CPU에 의해 참조되는 횟수를 고려하는 방식 자주 사용될 페이지는 남기고 앞으로 오랫동안 사용하지 않을 페이지는 교체할 수 있도록 한다 "앞으로 오랫동안 사용하지 않을 페이지"를 예측하기 어려워 실제적으로 사용되기 보다는 이론 상의 성능 지표

• LRU 페이지 교체 알고리즘 (Least Recently Used page replacement algorithm) 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라고 예측하는 방식 마지막 사용 시각을 토대로 사용한지 가장 오래된 페이지를 교체

비효율적인 페이지 교체 알고리즘을 사용할 때뿐만 아니라 프로세스가 사용할 수 있는 프레임 수가 적은 경우에도 페이지 폴트가 자주 발생한다. 이게 과해지면 프로세스 실행 시간보다 페이징에 더 많은 시간을 소요하여 성능 저하가 발생하는데 이러한 문제를 스레싱(thrashing) 이라고 한다.

메모리에서 동시 실행되는 프로세스가 늘어 멀티프로그래밍의 정도(degree of multiprogrammming) 가 높아지면 어느 정도까지는 CPU 이용률이 높아지며 성능이 좋아지다가 어느 순간 스레싱이 발생하여 성능이 저하된다. 그 근본적인 원인 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.

• 정적 할당 방식 프로세스의 실행 과정은 고려하지 않고 단순히 프로세스 크기와 물리 메모리의 크기만 고려한 프레임 할당 방식

  • 균등 할당 (equal allocation) 프로세스 개수에 따라 정확히 1/N 하여 할당하는 방식
  • 비례 할당 (proportional allocation) 프로세스 크기에 따라 비례하게 할당하는 방식

• 동적 할당 방식 프로세스의 실행을 보고 할당할 프레임 수를 결정하는 방식

  • 작업 집합 모델 (working set model) 을 이용하는 방식 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 작업 집합 working set 을 만들고 이 작업 집합의 크기에 따라 프레임을 할당하는 방식
  • 페이지 폴트 빈도 (page fault frequency) 를 이용하는 방식 페이지 폴트율이 높으면 프레임 수가 적다고 판단하여 늘리고 페이지 폴트율이 낮으면 프레임 수가 많다고 판단하여 줄이는 방식

더 알아보기 [컴퓨터 공학 기초 강의] 39강. 페이지 교체와 프레임 할당 [컴퓨터 공학 기초 강의] 40강. 페이징의 이점과 계층적 페이징

CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 하며, CPU 스케줄링(CPU scheduling) 은 CPU 스케줄러가 하는 모든 작업을 가리킨다.

운영체제는 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하기 위해 CPU 스케줄링_(CPU scheduling)_을 수행한다.

입출력 집중 프로세스 vs CPU 집중 프로세스

• 입출력 집중 프로세스 (I/O bound process)

  • 입출력 작업이 많은 프로세스
  • 대표적으로 비디오 재생이나 디스크 백업 작업 등을 담당하는 프로세스

• CPU 집중 프로세스 (CPU bound process)

  • CPU 작업이 많은 프로세스
  • 대표적으로 복잡한 수학연산, 컴파일, 그래픽 처리 작업 등을 담당하는 프로세스

  ✔️ 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU 자원을 요구할 경우 ?

  입출력 집중 프로세스를 먼저 실행하여 입출력 장치를 끊임없이 작동시키고 해당 프로세스가 입출력 작업을 하며 대기 상태로 존재하는 동안 CPU 집중 프로세스에 CPU를 집중적으로 할당하는 것이 효율적이다.

  → 일반적으로 입출력 집중 프로세스의 우선순위가 더 높다.

스케줄러의 종류

• 장기 스케줄러(Long-term scheduler) : 어떤 프로세스를 준비 큐에 넣을 것인지 결정

• 중기 스케줄러(Medium-term scheduler, Swapper) : 메모리에 적재된 프로세스 수 관리하여 과부하 예방

• 단기 스케줄러(Short-term scheduler, CPU scheduler) : 메모리 내의 준비 상태에 있는 작업 중 실행할 프로세스를 선택하여 CPU를 할당, 타임 슬라이스 등을 지정하는 가장 핵심적인 역할을 기능을 담당

스케줄링의 목적

• 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되면 안된다.

• 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.

• 안정성 : 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.

• 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.

• 반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.

• 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

스케줄링 알고리즘 선택 기준

• CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법

• 처리량 : 단위 시간당 작업을 마친 프로세스의 수

• 대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간

• 응답 시간 : 프로세스 시작 후 첫번째 출력 또는 반응이 나올 때까지 걸리는 시간

• 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간

선점형 스케줄링 & 비선점형 스케줄링

선점형 스케줄링

프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링 방식

타이머 인터럽트에 따라 CPU 자원을 뻇어 다음 프로세스에게 전달하는 것도 여기에 포함되며 대부분의 운영체제에서 차용하고 있는 방식이다.

• 장점

  • 프로세스들에게 골고루 자원을 배분할 수 있음
  • 프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합

• 단점

  - 문맥 교환 과정에서 오버헤드 발생

ex) 라운드 로빈(RR), 최소 잔류 시간 우선 스케줄링(SRT), 다단계 큐 ..

비선점형 스케줄링

하나의 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

• 장점

  • CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적음

• 단점

  • 프로세스가 자원을 골고루 사용 불가
  • 기다리는 프로세스가 많아 처리율이 떨어짐

ex) 선입 선처리 스케줄링(FCFS), 최단 작업 우선 스케줄링(SJF), 우선순위 스케줄링, HRN ..

선점형 스케줄링 vs 비선점형 스케줄링

스케줄링 알고리즘

선입 선처리 알고리즘 (First Come First Serve, FCFS)

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식

• 모든 프로세스의 우선순위가 동일
• 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 증가

💡 콘보이 효과 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리게 된다.

최단 작업 우선 스케줄링 (Shortest Job First, SJF)

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식

• 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꾸어 실행해서 FCFS의 콘보이 효과를 완화할 수 있음
• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움

최소 잔류 시간 우선 스케줄링 (Shortest Remaining Time, SRT)

CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 짧은 프로세스부터 우선적으로 선택하는 선점형 방식

• 평균 대기 시간과 평균 응답 시간을 최소화할 수 있어, 시스템의 처리량을 높이고 사용자의 만족도를 향상시킬 수 있음
• 실행 시간이 긴 프로세스는 우선순위에서 계속해서 밀려 무한 대기하는 기아 현상이 발생할 수 있음

→ SJF(최단 작업 우선 스케줄링) + RR(라운드 로빈 스케줄링)

우선순위 스케줄링 (Priority)

프로세스들에게 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행하는 선점/비선점 방식

• 우선순위가 같은 프로세스들은 FCFS 방식 적용
• 우선순위가 낮은 프로세스의 실행이 계속 연기되어 기아 현상 발생 가능

💡 기아 현상 (starvation) 실행시간이 짧은 프로세스가 계속 들어오면 실행시간이 긴 프로세스는 계속 뒤로 밀려 실행 시간이 긴 프로세스의 작업이 무한 연기되는 현상

💡 에이징 (aging) 어떤 자원을 오래 대기할수록 해당 프로세스의 우선순위를 높여주는 방법

라운드 로빈 스케줄링 (Round Robin, RR)

여러 프로세스들을 할당된 시간 (타임 슬라이스) 만큼 돌아가면서 실행하는 선점형 방식

• 선점형 알고리즘 중 가장 단순하고 대표적인 방식
• 작업을 완료하지 못할 경우 준비 큐의 맨 뒤로 가서 자기 차례를 기다림
• 타임슬라이스가 큰 경우 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보임
• 타임 슬라이스가 작은 경우 문맥 교환이 빈번하게 일어나 오버헤드 발생

다단계 큐 스케줄링 (Multilevel Queue Scheduling)

우선순위에 따라 준비 큐를 여러개 사용하는 비선점형 방식

• 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입되어 실행
• 우선 순위가 낮은 프로세스의 작업이 연기되는 문제가 발생

다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

변동 우선순위 알고리즘의 전형적인 예로 CPU를 사용하고 난 프로세스가 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어가는 방식

• 오늘 날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식
• 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
• 우선순위에 따라 타임 슬라이스의 크기가 다른데, 낮을수록 점점 커지고 마지막 큐는 무한대의 타임 슬라이스를 가짐 (* FCFS 방식)

전통적인 관점에서 보면 하나의 프로세스는 한 번에 하나의 일만을 처리하였으나 스레드(thread) 라는 개념이 도입되면서 한 번에 여러 일을 처리할 수 있게 되었다.

• 프로세스를 구성하는 실행 단위
• 프로세스 내에서 각기 다른 스레드 ID, 프로그램 카운터 값, 레지스터 값, 스택으로 구성
• 힙, 데이터, 코드 영역 등 다른 프로세스 자원은 공유

한 번에 하나의 일만 처리하는 프로세스는 단일 스레드 프로세스라고 칭한다.

멀티 프로세스 (multi-process)

• 여러 프로세스를 동시에 실행하는 것
• 기본적으로 프로세스끼리 자원을 공유하지 않는다
• 하나에 문제가 생겨도 서로에게 영향력이 적다
• IPC, 공유 메모리 등으로 통신은 가능하지만 오버헤드 존재

독립적인 메모리 공간으로 컨텍스트 스위칭이 발생한다. 프로세스간의 통신을 위해서는 IPC가 필요하다.

-> 이 두 가지 문제점을 한 번에 해결할 수 있는게 스레드_(thread)_이다.

멀티 스레드 (multi-thread)

스레드는 프로세스가 할당 받은 자원을 이용하는 실행의 단위로서, 스레드가 여러 개 있으면 파일을 다운받으며 동시에 웹 서핑을 할 수 있게 해준다.

스레드끼리 프로세스의 자원을 공유하면서 프로세스 실행 흐름의 일부가 되기에 동시 작업이 가능한 것이다.

• 프로세스 내에 여러 스레드를 동시에 실행하는 것
• 같은 프로세스 내의 스레드 끼리 프로세스 자원을 공유한다 (코드, 데이터, 힙, 스택 영역)
• 여러 프로세스를 병행 실행하는 것보다 메모리를 더 효율적으로 사용 가능
• 협력과 통신에 유리
  

Multi Processing VS Multi Threading

→ 멀티 프로세스 : 크롬 창 내의 여러 탭이나 여러 창을 동시에 실행하는 것 → 멀티 스레드 : 크롬 창 내의 단일 탭에서 네트워크 처리, I/O 및 기타 작업을 동시에 수행하는 것

프로세스란 ?

실행 중인 프로그램을 프로세스(process) 라고 한다.

컴퓨터가 부팅되는 순간부터 수많은 프로세스들이 실행되는데, 유닉스 체계의 운영체제에서는 ps 명령어를 통해 실행 중인 프로세스를 확인할 수 있다.

(ps 명령어는 현재 터미널에서 실행 중인 프로세스만 확인할 수 있으며, 시스템 내 전체 프로세스를 확인하려면 -ef 와 같은 옵션을 설정해야 한다.)

아래는 ps -ef 명령어의 출력 예시이다.

여기엔 직접 실행한 프로세스 외에도 운영체제에 의해 실행되는 다양한 프로세스가 존재한다.

• 포그라운드 프로세스 (foreground process) 사용자가 볼 수 있는 공간에서 실행되는 프로세스

• 백그라운드 프로세스 (background process) 보이지 않는 공간에서 실행되는 프로세스 그 중에서도 사용자와 상호작용하지 않고 정해진 작업을 수행하는 것을 데몬(deamon) 이라 한다.

  
  

💡 프로그램과 프로세스의 차이

프로세스 제어 블록 (PCB)

여러 개의 프로세스가 한정된 시간동안 CPU를 돌아가며 사용하기 위해 타이머 인터럽트가 사용되는데, 타이머 인터럽트가 발생하면 프로세스가 자신의 차례를 양보하고 다음 차례를 기다린다. 그리고 이러한 작업을 하기 위해 운영체제는 프로세스와 관련된 정보를 저장하는 자료구조인 프로세스 제어 블록_ (PCB - process control block)_ 을 이용한다.

PCB에는 각각의 프로세스를 식별하기 위해 필요한 정보가 포함되어 있으며, 커널 영역에 존재한다. PCB에 담기는 정보는 운영체제마다 상이하지만 대표적으로 아래와 같은 것들이 있다.

• 프로세스 ID (PID) 프로세스를 식별하기 위해 부여하는 고유한 번호 같은 프로그램도 두번 실행하면 PID가 다른 두 개의 프로세스 생성

• 레지스터 값 자신의 실행 차례가 돌아오면 복원할 레지스터 값들을 백업한 것

• 프로세스 상태 프로세스가 CPU를 이용하고 있는지, 기다리고 있는지, 입출력장치를 사용하려 하는지 등의 정보

• CPU 스케줄링 정보 프로세스가 언제, 어떠한 순서로 CPU를 할당받을지에 대한 정보

• 메모리 관리 정보 프로세스가 어느 주소에 저장되어 있는지에 대한 정보

   베이스 레지스터 한계 레지스터 값과 페이지 테이블 정보

• 사용한 파일과 입출력장치 목록 어떤 입출력장치가 이 프로세스에 할당되었는지, 어떤 파일을 열었는지 등의 정보

  
  

문맥 교환 (Context Switch)

Context ? 기존에 실행되던 프로세스에서 다른 프로세스에게 CPU 자원을 양보하는 상황에서 이전 프로세스가 사용하던 레지스터 값, 메모리 정보 등 중간 정보를 백업해야 하는데 이처럼 프로세스 수행을 재개하기 위해 기억해야 할 중간 정보 를 문맥(context) 이라고 한다.

문맥은 CPU 사용 시간이 다 되거나 인터럽트가 발생하면 해당 프로세스의 PCB에 백업되며, 프로세스 수행이 재개될 때 PCB에 기록되어 있는 context를 복구한다.

Context Switch ? 이전 프로세스의 context를 해당 프로세스의 PCB에 백업하고 다음 프로세스의 context를 해당 프로세스의 PCB로부터 복구하여 새로운 프로세스를 실행하는 과정을 문맥 교환(context switch) 이라고 한다.

프로세스의 메모리 구조

하나의 프로세스는 사용자 영역에 크게 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 나뉘어 저장된다.

• 정적 할당 영역 프로그램이 실행되는 동안 크기가 변하지 않는 영역

  • 코드 영역 (code segment)

    • 텍스트 영역(text segment) 이라고도 불린다.
    • 기계어로 이루어진 명령어가 저장되는 읽기 전용 공간 ex) 실행할 프로그램의 코드

  • 데이터 영역 (data segment)

    • 전역 변수와 같이 프로그램이 실행되는 동안 유지할 데이터가 저장되는 공간 ex) 전역 변수, 정적 변수

• 동적 할당 영역 프로그램이 실행되는 동안 크기가 변할 수 있는 영역

  • 힙 영역 (heap segment)

    • 프로그래머가 직접 공간을 할당, 반환하는 메모리 공간
    • 프로그래밍 과정에서 힙 영역에 메모리 공간을 할당했다면 언젠가는 반환해야함
    • 반환하지 않는다면 메모리 낭비가 생기는데 이를 메모리 누수(memory leck)이라고 함
    • 일반적으로 메모리의 낮은 주소에서 높은 주소로 데이터가 쌓임 ex) 사용자의 동적 할당

  • 스택 영역 (stack segment)

    • 데이터를 일시적으로 저장하는 공간
      • 함수의 실행이 끝나면 사라지는 매개 변수, 지역 변수 등이 저장됨
      • PUSH로 데이터를 저장하고 POP으로 데이터를 인출함
      • 일반적으로 메모리의 높은 주소에서 낮은 주소로 할당됨 ex) 지역 변수, 매개 변수

오버 플로우란 한정된 메모리 공간이 부족하여 메모리 안에 있는 데이터가 넘쳐 흐르는 현상으로,
힙이 스택을 침범하는 경우를 힙 오버 플로우 라 하고, 스택이 힙을 침범하는 경우를 스택 오버 플로우 라고 한다.

운영체제의 핵심 서비스를 담당하는 부분이다.

동작 방식

운영체제는 응용 프로그램이 시스템 자원에 접근하려고 할 때 오직 자신을 통해서만 접근하도록 하여 자원을 보호하는데 이 때 이중 모드와 시스템 호출이 사용된다.

이중 모드 (dual mode)

응용 프로그램이 하드웨어 자원에 직접 접근하지 않고 운영체제를 거치도록 하는 방식

CPU가 명령어를 실행하는 모드는 두가지로 나뉜다.

1. 유저 모드 (user mode)

   • 커널 영역의 코드 실행 불가
   • 운영체제 서비스를 제공받을 수 없는 모드
   • 일반적인 응용 프로그램의 기본 실행 모드
   • 입출력 명력어를 포함하여 하드웨어 자원에 접근하는 명령어 실행 불가

2. 커널 모드 (kernal mode)

   • 커널 영역의 코드 실행 가능
   • 운영체제 서비스를 제공받을 수 있는 모드
   • 시스템 자원에 접근 가능

   

시스템 콜 (system call)

이중 모드의 커널 모드로 전환하는 방법

• 사용자 모드로 실행 중인 프로그램이 운영체제 서비스를 받기 위해 운영체제에 보내는 요청

• 시스템 호출 명령어 실행 시 CPU는 기존 작업을 백업하고 커널 내 시스템 호출을 수행하는 코드를 실행한 뒤 기존 작업으로 복귀

• 소프트웨어 인터럽트로, 처리 순서는 하드웨어 인터럽트와 유사

  > 인터럽트란, CPU가 프로그램을 실행하고 있을 때 입출력, 파일 읽기 등의 예외상황이 발생하여 처리가 필요할 경우에 CPU에게 알려 처리할 수 있도록 하는 것을 말한다.

운영체제의 핵심 서비스

프로세스 관리

• 실행 중인 프로그램 == 프로세스
• 동시다발적으로 생성/실행/삭제되는 다양한 프로세스를 일목요연하게 관리

자원 접근 및 할당

• CPU : 프로세스들에 공정하게 CPU를 할당하기 위한 스케줄링

• 메모리 : 새로운 프로세스가 적재될 때 어느 주소에 적재해야 할지 결정 : 메모리 공간이 꽉 차 있거나 프로세스를 적재하지 못하는 상황 발생시 처리

• 입출력장치

파일 시스템 관리

• 보조기억장치 속 데이터를 파일과 디렉토리로 관리하는 파일 시스템

컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 사용자 및 다른 모든 소프트웨어와 하드웨어의 연결을 담당한다.

운영체제는 컴퓨터가 부팅될 때 메모리 내 커널 영역(kernal space)이라는 공간에 적재되며, 커널 영역을 제외한 공간은 사용자 영역(user space)으로, 일반적인 응용 프로그램이 적재된다.

→ 커널 영역에 적재된 운영체제가 사용자 영역에 적재된 프로그램들에 자원을 할당하고 실행을 돕는 것

운영체제의 목표

운영체제에는 크게 두 가지의 목표가 있다.

• 컴퓨터 하드웨어 ↔ 운영체제
• 운영체제 ↔ 사용자

사용자의 입장 : 컴퓨터 시스템을 편리하게 사용할 수 있는 환경을 제공 (즉, 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행해줌)

전공자의 입장 : 컴퓨터 시스템의 자원을 효율적으로 관리하는 것

여기서 말하는 자원이란 *프로세스(CPU), 메모리, 기억장치, 입출력 장치 *등을 말한다.

자원의 효율적 관리란 ?

• 사용자 간의 형평성 있는 자원 분배
• 주어진 자원으로 최대한의 성능을 내도록

운영체제의 목적

• 자원의 효율적 관리
• 사용자 및 운영체제 자신의 보호
• 프로세스, 파일, 메세지 등을 관리

운영체제의 분류

동시 작업 가능 여부

• 단일 작업 한 번에 하나의 작업만 처리 (ex: MS-DOS 프롬프트)

• 다중 작업 동시에 두 개 이상의 작업을 처리 (ex: UNIX, MS Windows 등)

  • 시분할 시스템 : CPU의 작업시간을 여러 프로그램들이 조금씩 나누어 쓰는 시스템

  • 다중 프로그래밍 시스템 : 메모리 공간을 분할해 여러 프로그램을 동시에 메모리에 올려놓고 CPU가 항상 작업을 수행할 수 있도록 하는 시스템

  • 다중처리기 시스템 : 하나의 컴퓨터 안에 CPU가 여러 개 설치된 시스템

사용자의 수

• 단일 사용자 (Single User)

  • MS-DOS, MS Windows
  • 단일 작업만 지원해주는 운영체제의 경우 단일 사용자만 지원

• 다중 사용자 (Mulit User)

  • UNIX, NT Server
  • 서버에 계정을 여러 개 만들고 원격으로 여러 명이 동시에 접근할 수 있는 것

처리 방식

• 일괄 처리 (Batch Processing)

  • 작업 요청의 일정량을 모아서 한꺼번에 처리
  • 작업이 완전히 종료될 때까지 기다림

    현대의 운영체제에 적합하지 않음

• 시분할 (Time Sharing)

  • 여러 작업을 수행할 때 컴퓨터 처리 능력을 일정한 시간 단위로 분할하여 사용
  • 일괄 처리 시스템에 비해 짧은 응답 시간을 가짐
  • interactive한 방식

    현대의 운영체제

• 실시간 (Realtime OS)

  • 정해진 시간 안에 어떠한 일이 반드시 종료됨이 보장되어야하는 실시간시스템을 위한 OS
  • ex) 미사일 제어, 반도체 장비, 로봇 제어

    시분할과 비슷해보이지만, 프로그램이 동작하기 위해 정확한 시간이 필요로 하는 운영체제

몇가지 용어

• Multitasking : 컴퓨터 전반에서 하나의 프로그램이 끝나기 전에 다른 프로그램이 컴퓨터에서 실행 가능한 것

• Multiprogramming : 여러 프로그램이 메모리에 올라가 있음을 강조

• Time sharing : CPU의 시간을 분할하여 나누어 쓴다는 의미 강조

• Multiprocess : 여러 프로그램이 동시에 실행

• MultiProcessor : 하나의 컴퓨터에 CPU가 여러 개 붙어있음을 의미

운영체제의 예

• 유닉스 (UNIX) - 초창기의 목적은 대형 컴퓨터를 위한 운영체제
• DOS - 개인용 컴퓨터를 위한 운영체제 (단일 사용자용 운영체제)
• MS Windows - 다중 작업용 GUI 기반 운영 체제

운영체제의 구조

CPU가 한개일때 작업이 긴 것이 있으면 나머지 작업은 오래 기다려야 하는데 이를 해결하는 방법 ?

CPU 스케줄링

• 어떤 프로그램부터 CPU를 이용하게 할지 결정
• 얼마나 오랫동안 CPU를 이용하게 할지 결정

프로그램이 많아지만 각 프로그램이 갖는 메모리 공간이 작아져서 프로그램이 원활하게 실행되지 않는 경우 ?

메모리 관리의 필요성

• 실행할 프로그램을 메모리에 적재
• 더 이상 실행되지 않는 프로그램을 메모리에서 삭제

디스크를 읽을 때 헤드의 움직임을 최소화하면서 효율적으로 읽어들이는 방법 ?

파일 관리를 효율적으로 하는 방법

• 엘리베이터 스케줄링과 유사한 방법 (먼저 버튼을 눌러도 우선 탑승이 가능하지 않은 방식)

I/O device를 관리하기 위해 인터럽트를 사용하여 CPU에게 작업 사항이 있음을 알림

입출력 관리

• 복수의 프로그램이 동일한 입출력장치 접근 시도 시 동시 접근 방지