passion_man.log

[텍스트 마이닝] 13. Word Senses

Tue, 07 Jun 2022 06:39:54 GMT

=> bad 는 좋은 의미로 쓰일 수도 있고 나쁜 의미로 쓰일 수도 있다. 여러 의미를 가지는 단어 중에 어떤 뜻을 선택할 것인가? -> Word Sense 로 파악

Word senses

=> serve 의 여러 가지 의미 중에 무슨 의미일까? -> word sense 로 파악

Relationship between senses

Symomymy/antonymy (동의성/반의성)
Hypernymy (의미적 포함관계)
Metonymy (어떤 특정 단어로 전체 지칭하는 경우)
Meronymy (물리적 포함관계)
상위-하위 개념일 때, 상위개념이 하위개념을 포함 ex) bihike(상위) 와 car(하위), bike(하위)
전체-부분 관계일 때 ex) car(전체) 와 wheel(부분), window(부분)

Synonym

=> word sense로 big, large 중에 뭐 고를래?

Synonymy 는 cosine similarity 가 비슷

Antonymy

=> word sense로 long, short 중에 뭐 고를래?

Hyponymy

Meronymy

Dataset

WordNet

언어학자들이 명사/형용사/동사 .. 등 전부 다 분석해놓음
Lexical database for nouns, verbs and adjectives/adverbs
Each word sense is arranged in a synset and each synset is related to others in terms of their sense relations

Relations : word 와 word의 관계를 본다

![] (https://velog.velcdn.com/images/passion_man/post/5d6461de-02c3-4c4c-8354-f76dcad3d028/image.png)

Synsets : synymy 기반의 data word-sense

-> 위로 올라갈 수록 상위개념

WordNet

WordNet encodes human-judged measures of similarity. Learn distributed representations of words that respect WordNet similarities -> WordNet의 similarity 를 이용해서 Word vector 를 만듬

Semcor (dataset)

200K + words from Brown corpus tagged with WordNet senses.

=> 위의 그림에서 숫자 1, 숫자 2는 WordNet Problem의 1번째 혹은 2번째 problem을 사용한다 라는 뜻이다.

Word Sense Disambiguation (WSD)

WSD 의 여러 가지 방식 1) Dictionary methods (Lesk) 2) Supervised (machine learning) 3) Semi-supervised (Bootstrapping)

Dictionary methods

Predict the sense a given token that has the highest overlap between the token's context and sense's dictionary gloss -> Sense1,2,3 중 classification -> context와 gloss 사이에 overlap이 가장 큰 것으로 선택

=> 각 단어 word vector를 만들어서 bank1, bank2의 word vector 중 어떤 것과 가까운지 파악한다.

Lest Algorithm

Supervised WSD

We have labeled training data; let's learn from it
- Decision trees
  - Naive Bayes, long-linear classifiers, support vector machines
    - Bidirectional LSTM

Evaluation

=> 맨 아랫 줄(Baseline)의 MFS는 Most Frequent Sense 로 통계적으로 가장 많이 나온 단어를 선택했을 때 결과값이다. 어떤 방식을 쓰든 이것보단 값이 높아야 한다.

if a word appears multiple times in a document, it's usually with the same sense -> 언어의 특징 ex) Articles about finacial banks don't usually don't talk about river banks

hyponymy 의 word sense

Supersense tagging

=> 하위개념을 상위개념으로 Mapping 해준다

[운영체제] 9. 페이징 메모리 관리

Fri, 03 Jun 2022 06:15:10 GMT

페이징 메모리 관리 개요

페이징 개념

1) 페이지와 프레임

프로세스의 주소 공간을 0번지부터 동일한 크기의 페이지로 나눔
물리 메모리 역시 0번지부터 페이지 크기로 나누고, 프레임이라고 부름
코드, 데이터, 스택 등 프로세스의 구성 요소에 상관없이 고정 크기로 분할한 단위
페이지와 프레임에 번호 붙임
페이지의 크기
- 주로 4KB, 운영체제마다 다르게 설정 가능
페이지 테이블
- 각 페이지에 대해 페이지 번호와 프레임 번호를 1:1로 저장하는 테이블

2) 페이징 기법

프로세스의 주소공간과 물리 메모리를 페이지 단위로 분할하고, 프로세스의 각 페이지를 물리 메모리의 프레임에 분산 할당하고 관리하는 기법
프로세스의 주소공간
- 선형적인 주소공간(0에서 시작하여 연속적인 주소공간)
프로세스마다 페이지 테이블 있음
논리 주소의 물리 주소 변환 : MMU에 의해
물리 메모리의 빈 프레임 리스트 관리 필요
- 프레임 할당 알고리즘 : 빈 프레임 중에서 선택알고리즘 필요
내부 단편화 발생
세그먼테이션보다 우수

페이징의 우수성

용이한 구현
- 메모리를 0번지부터 고정 크기로 단순히 분할하기 때문
높은 이식성
- 페이징 메모리 관리를 위해 CPU에 의존하는 것 없음
  - 다양한 컴퓨터 시스템에 쉽게 이식 가능
높은 융통성
- 시스템에 따라 응용에 따라 페이지 크기 달리 설정 가능
메모리 활용과 시간 오버헤드면에서 우수
- 외부 단편화 없음
  - 내부 단편화는 발생하지만 매우 작음
  - 홀 선택 알고리즘을 실행할 필요 없음

페이지와 페이지 테이블(1)

[설명]

4GB의 주소 공간을 가지는 프로세스
페이지 크기 4KB
프로세스
- 코드 : 페이지0 ~ 페이지2에 걸쳐 있음
  - 데이터 페이지2 ~ 페이지3에 걸쳐 있음
  - 힙 : 페이지3 ~ 페이지4에 걸쳐 있음
  - 스택 : 사용자 공간의 맨 마지막 페이지에 할당, 1페이지 사용
현재 프로세스는 6개의 페이지를 사용하고 있음
- 프로세스의 크기 : 6 x 4KB = 24KB
페이지 테이블
- 페이지 테이블은 주소공간의 모든 페이지를 나타낼 수 있는 항목을 포함
  - 현재 6개의 항목만 사용. 대부분의 항목은 비어 있음

페이지와 페이지 테이블(2)

[설명]

1) 프로세스가 동적 할당 받을 때

char *p = (char*)malloc(200); // 프로세스의 힙 영역에서 200 바이트 동적 할당

200바이트 할당 요청
- 1페이지 (4KB) 할당
  - 논리 페이지 5할당, 물리 프레임 2할당 1) 페이지 5의 논리 주소 : 54KB = 20KB = 201024 =20480번지 2) 프레임 2의 물리 주소 : 2*4KB = 8192번지
  - malloc(200)은 페이지 번호 5의 논리 주소 20480을 리턴

*p = 'a';

프로세스 내에서 20480번지에 'a'를 저장하는 코드
- 논리 주소 20480이 MMU에 의해 물리 주소 8192로 바뀌어
  - 물리 메모리 8192 번지에 'a' 저장
```
free(p);
```
20480번지에서 할당 받은 200바이트 반환
- 반환 후 페이지 5 전체가 비게 되므로, 페이지 5와 프레임 2가 모두 반환

페이지와 페이지 테이블(3)

[설명]

프로세스가 시스템 호출을 실행할 때
- 커널 공간의 페이지 k에 담긴 커널 코드 실행
  - 커널 코드 역시 논리 주소로 되어 있음
  - 현재 프로세스 테이블에서 페이지 k의 물리 프레임 780090을 알아내고 물리 프레임 780090에 적재된 커널 코드 실행

[중요사항]

커널 코드도 논리 주소로 되어 있으며, 시스템 호출을 통해 커널 코드가 실행될 때 현재 프로세스의 페이지 테이블을 이용하여 물리 주소로 변환된다.

페이지와 페이지 테이블에 대한 정리

** 32비트 CPU에서, 페이지 크기가 4KB인 경우

물리 메모리의 최대 크기는?

물리 주소의 범위는 0 ~ 2³² -1
한 주소 당 한 바이트 크기이므로 물리 메모리의 최대 크기는 2³² = 4GB

프로세스의 주소 공간의 크기?

2³² 개의 주소들이므로, 총 4GB
물리 메모리는 1GB, 2GB, 4GB 등 다양하게 설치될 수 있지만, 프로세스의 주소 공간은 물리 메모리 크기에 상관없이 4GB

한 프로세스는 최대 몇 개의 페이지로 구성되는가?

4GB/4KB = 2³²/2¹² = 2²⁰개 = 1M개 = 약 100만 개

프로세스 당 하나의 페이지 테이블이 있다. 페이지 테이블의 크기는?

페이지 테이블 항목 크기가 32비트(4B)라면
4바이트*2²⁰ = 2²²바이트 = 4MB

응용프로그램이 하나의 프로세스라고 할 때, 응용프로그램의 최대 크기, 즉 개발자가 작성할 수 있는 프로그램의 최대 크기는?

운영체제가 설정한 사용자 공간의 크기

페이지 테이블 모양은

대부분이 비어 있는 희소 테이블

페이지 테이블은 어디에 존재하는가?

메모리에 저장

커널 코드가 논리 주소로 되어 있는가 물리 주소로 되어 있는가?

커널 코드 역시 논리 주소로 되어 있음. 그러므로 커널 코드가 실행될 때 역시 물리 주소로 바뀌어야 하는데 이때 사용되는 페이지 테이블은 현재 프로세스의 페이지 테이블이 사용됨

페이징에서의 단편화

외부 단편화 발생 없음
내부 단편화 발생
- 코드와 데이터가 주소 공간에서 연속되어 있다.
  - 스택이나 힙에 생성하는 페이지는 계속 변하므로 단편화 계산에서 제외한다면
  - 프로세스의 마지막 페이지에만 단편화 발생
  - 단편화의 평균 크기 = 페이지의 1/2 크기

페이징 개념 확인

** 32비트 CPU에서, 페이지의 크기가 2KB, 현재 설치된 메모리 1GB, 프로세스 A는 사용자 공간에서 54321바이트를 차지한다고 할 때

물리 메모리의 프레임 크기는?

2KB로 페이지 크기와 동일

물리 메모리의 프레임 개수는?

물리 메모리를 프레임 크기로 나누면 됨. 1GB/2KB = 2³⁰/2¹¹ = 2¹⁹개, 약 50만 개

프로세스 A의 주소 공간 크기와 페이지의 개수는?

프로세스의 주소 공간 크기는 2³² = 4GB. 페이지의 개수 = 2³²/2¹¹=2²¹개 = 2M개 = 약 2백만 개

프로세스 A는 몇 개의 페이지로 구성되는가? 프로세스 A를 모두 적재하기 위한 물리 프레임의 개수는?

프로세스 A의 실제 크기가 54321 바이트이므로, 2KB(2048)로 나누면 26.5이므로 27개 페이지(프레임)

페이지 테이블 항목의 크기가 4바이트라고 할 때, 프로세스 A의 페이지 테이블의 크기는?

테이블 항목이 총 2²¹개이므로 2²¹*4바이트 = 2²³바이트 = 8MB

페이징에서 단편화 메모리의 평균 크기는?

프로세스의 코드와 데이터 연속되어 있으므로, 마지막 페이지에만 단편화가 생긴다. 평균은 페이지의 반이므로 1KB

페이지의 크기와 단편화의 관계는?

페이지의 크기가 크면 단편화도 커진다. 하지만 극히 미미하다.

페이지의 크기와 페이지 테이블의 크기 관계는?

페이지 크기가 크면 페이지 개수가 작아지고 페이지 테이블의 크기도 작아진다.

페이징의 주소 체계

페이징의 논리 주소

논리 주소 구성

[페이지 번호(p), 옵셋(offset)]
- 페이지 크기가 4KB(=2¹²)라면, 페이지 내 각 바이트 주소 12비트
  - 옵셋 크기는 12비트
32비트 논리 주소 체계에서,
- 상위 20비트는 페이지 번호
  - 하위 12비트는 옵셋

논리 주소의 물리 주소 변환 개념

페이징 구현

하드웨어 지원

CPU의 지원
- CPU에 페이지 테이블이 있는 메모리 주소를 가진 레지스터 필요
  - Page Table Base Register (PTBR)
  - 이 레지스터는 운영체제에 의해 제어
MMU 장치
- 논리 주소의 물리 주소 변환
  - 페이지 테이블을 저장하고 검색하는 빠른 캐시 포함
  - 메모리 보호 - 페이지 번호가 페이지 테이블에 있는지, 옵셋이 페이지의 범위를 넘어가는지 확인

운영체제 지원

프레임의 동적할당/반환 및 페이지 테이블 관리 기능 구현
- 프로세스의 생성/소멸에 따라 동적으로 프레임 할당/반환
  - 물리 메모리에 할당된 페이지 테이블과 빈 프레임 리스트 생성 관리 유지
  - 컨텍스트 스위칭 때, PCB로부터 페이지 테이블의 물리주소를 CPU의 PTBR 레지스터에 로딩

페이지 테이블의 문제점과 TLB

2가지 문제점

1번에 메모리 액세스를 위한 2번의 물리 메모리 액세스

페이지 테이블은 몇 MB의 크기로 메모리에 저ㅏㅇ
CPU가 메모리를 액세스할 때마다, 2번의 물리 메모리 액세스 -> 실행 속도 저하
TLB 사용으로 해결

페이지 테이블의 낭비

프로세스의 실제 크기는 매우 작기 때문에
대부분의 페이지 테이블 항목이 비어 있는 문제
2레벨 페이지 테이블 등 방법으로 해결

C프로그램이 실행될 때 메모리 액세스 과정 분석

int n[100]; 
int sum = 0;

for(int i = 0; i< 100; i++)
    sum += n[i];

32비트 CPU, 페이지는 4KB
배열 n[100]의 논리 주소는 0x2000(페이지2)부터 시작
배열 n[100]의 물리 주소는 0x7000(프레임7)부터 시작
배열 n[100]의 크기는 400바이트이며 페이지2에 모두 들어 있음
페이지 테이블은 물리 메모리 0xA000번지부터 시작

TLB를 이용한 2번의 물리 메모리 액세스 문제 해결

1) 문제 해결 실마리

논리 주소를 물리 주소로 바꾸는 과정에서 페이지 테이블을 읽어오는 시간을 없애거나 줄이는 기법

2) TLB(Tranlation Look-aside Buffer) 사용

주소 변환 캐시(address translation cache) 로 불림
최근에 접근한 '페이지와 프레임 번호'의 쌍을 항목으로 저장하는 캐시 메모리
위치
현대 컴퓨터에서는 MMU내에 존재
TLB캐시의 구조와 특징
[페이지 번호 p, 프레임 번호 f]를 항목으로 저장
페이지 번호를 받아 전체 캐시를 동시에 고속 검색, 프레임 번호 출력, content-addressable memory, associative memory라고 불림(연관 메모리)
고가, 크기 작음(64~1024개의 항목 정도 저장)

TLB를 활용한 메모리 액세스

CPU로부터 논리 주소 발생
논리 주소의 페이지 번호가 TLB로 전달
페이지 번호와 TLB 내 모든 항목 동시에 비교

TLB에 페이지가 있는 경우, TLB hit
- TLB에서 출력되는 프레임 번호와 offset 값으로 물리 주소 완성
TLB에 페이지가 없는 경우, TLB miss
- TLB는 miss 신호 발생
  - MMU는 페이지 테이블로부터 프레임 번호를 읽어와서 물리 주소 완성
  - 미스한 페이지의 [페이지번호, 프레임번호] 항목을 TLB에 삽입

TLB가 있는 경우 C프로그램 실행 과정 분석

int n[100]; 
int sum = 0;

for(int i = 0; i< 100; i++)
    sum += n[i];

배열이 2개의 페이지에 걸쳐 있는 경우 TLB 활용 사례

int n[100]; 
int sum = 0;

for(int i = 0; i< 100; i++)
    sum += n[i];

배열 n[2000]의 논리 주소는 0x2000부터 시작하여 페이지 2,3에 걸쳐 존재
배열 n[2000]의 물리 주소는 0x7000부터 시작하여 프레임 7과 9에 나누어 할당
페이지 테이블이 메모리 0xA000번지에서 시작

TLB로 부터 얻는 교훈

1) TLB와 참조의 지역성

TLB는 참조의 지역성으로 인해 효과적인 전략임
TLB를 사용하면, 순차 메모리 액세스 시에 실행 속도 빠름
- TLB 히트가 계속됨(메모리의 페이지 테이블 액세스할 필요 없음)
TLB를 사용하면, 랜덤 메모리 액세스나 반복이 없는 경우 실행 속도 느림
- TLB 미스 자주 발생
  - TLB의 항목 교체(TLB 항목의 개수 제한되기 때문)

2) TLB의 성능

TLB 히트율 높이기 -> TLB 항목 늘이기(비용과의 trade-off)
페이지 크기
- 페이지가 클수록 TLB 히트 증가 -> 실행 성능 향상
  - 페이지가 클수록 내부 단편화 증가 -> 메모리 낭비
  - 이 둘 사이에는 trade-off 존재, 선택의 문제
  - 페이지가 커지는 추세 : 디스크 입출력의 성능 향상을 위해

3) TLB reach - TLB 성능 지수(figure of merit)

TLB 도달 범위
TLB가 채워졌을 때, 미스없이 작동하는 메모리 액세스 범위
TLB 항목 수 X 페이지 크기

TLB를 고려한 컨텍스트 스위칭 과정 재정리

CPU의 모든 레지스터를 PCB에 저장
PCB에 있는 프로세스의 페이지 테이블의 주소를 MMU(CPU)의 Page Table Base Register(PTBR)로 로딩

TLB 미스 시에 페이지 테이블을 액세스하여 물리 주소를 알아내고
TLB로 페이지 테이블 엔트리 이동하기 위함

TLB 내용 모두 지우기

새로운 프로세스의 실행이 시작되면 TLB 미스가 발생하고 TLB에 항목이 채워지기 시작함
큰 비용 대가

새 프로세스 컨텍스트(CPU레지스터)를 PCB에서 CPU로 로딩

페이지 테이블의 메모리 낭비 문제 해결

페이지 테이블의 메모리 낭비

1) 32비트 CPU 환경에서 프로세스 당 페이지 테이블 크기

프로세스의 주소 공간
- 4GB/4KB = 2³²/2¹² = 2²⁰ = 약 100만 개의 페이지로 구성
프로세스 당 페이지 테이블의 크기
- 한 항목이 4바이트이면 2²⁰ x 4바이트 - 4MB

2) 10MB의 메모리를 사용하는 프로세스가 있다고 하면

실제 활용되는 페이지 테이블 항목 수
- 10MB/4KB = 10 x 2²⁰/2¹² = 10 x 2⁸ = 2560개
실제 활용되는 페이지 테이블 비율
- 10 x 2⁸/2²⁰ = 10/2¹² = 0.0024
  - 매우 낮음

페이지 테이블 낭비 문제의 해결책

역 페이지 테이블(inverted page table, IPT)

시스템에 하나의 역 페이지 테이블만 둠
- 역 페이지 테이블 항목의 수 = 물리 메모리의 프레임 개수
역 페이지 테이블 항목
- [프로세스번호(pid), 페이지 번호(p)]
역 페이지 테이블의 인덱스
- 프레임 번호
역 페이지 테이블을 사용한 주소 변환
- 논리 주소에서 (프로세스번호, 페이지 번호)로 역 페이지 테이블 검색
  - 일치하는 항목을 발견하면 항목 번호가 바로 프레임 번호임
  - 프레임 번호와 옵셋을 연결하면 물리주소

멀티 레벨 페이지 테이블

페이지 테이블은 하나의 페이지에 넣고 페이지 테이블을 가리키는 페이지 구성
사용 중인 페이지들에 대해서만 페이지 테이블 구성

역 페이지 테이블의 크기

1) 역 페이지 테이블의 개수

시스템에 1개 존재 2) 역 페이지 테이블의 크기
역 페이지 테이블의 항목 크기
- 프로세스 번호와 페이지 번호로 구성
  - 프로세스 번호와 페이지 번호가 각각 4바이트라면, 항목 크기는 8바이트
역 페이지 테이블의 항목 수 = 물리 메모리 크기/프레임 크기
- 예) 물리 메모리가 4GB, 프레임 크기 4KB이면 역 페이지 테이블 항목 수 = 4GB/4KB = 2²⁰ 개 = 약 100만개
역 페이지 테이블의 크기는 컴퓨터에 설치된 물리 메모리 크기에 따라 달라짐
- 물리 메모리는 컴퓨터마다 서로 다르게 설치될 수 있음
  - 예) 물리 메모리가 4GB, 프레임 크기가 4KB, 한 항목의 크기가 8바이트라면 역 페이지 테이블의 크기는 = 2²⁰ 개 항목 x 8 바이트 = 8MB

3) 기존 페이지 테이블과 비교

예) 10개의 프로세스가 실행 중일 때, 기존 페이지 테이블 = 4MB x 10개 = 40MB 크기 역 페이지 테이블 = 8MB (기존의 1/5 수준)
역 페이지 테이블 구현
- Linear inverted page table
  - Hashed inverted page table - PID와 p를 키로 해싱하여 단번에 일치하는 항목을 찾고 물리 주소로 변환한다. - PowerpC, UltraSPAC

멀티레벨 페이지 테이블

1) 멀티레벨 페이지 테이블 개념

현재 사용 중인 페이지들에 대해서만 페이지 테이블 만드는 방식
- 기존 페이지 테이블의 낭비를 줄임
페이지 테이블을 수십~ 수백 개의 작은 페이지 테이블로 나누고 이들을 여러 레벨로 구성

2) 2-레벨로 멀티레벨 페이지 테이블을 구성하는 경우

논리 주소 구성
- [페이지 디렉터리 인덱스, 페이지 테이블 인덱스, 옵셋]
  - 페이지 크기 4KB
    - 논리 주소의 하위 12비트 : 페이지 내 옵셋 주소
  - 논리 주소의 상위 20비트 : 페이지 디렉터리 인덱스와 페이지 테이블 인덱스

1024개의 페이지마다 1개의 페이지 테이블 사용

2-레벨 페이지 테이블 : 페이지 디렉터리와 페이지 테이블로 구성

이 사례에서 페이지 테이블의 크기 = 페이지 데렉터리 1개(4KB) + 3개의 페이지 테이블(12KB) = 16KB

페이지 테이블의 크기가 대폭 감소됨

2-레벨 페이지 테이블의 크기

1) 2-레벨 페이지 테이블의 최대 메모리 소모량

페이지 디렉터리 1개 + 최대 1024개의 페이지 테이블
= 4KB + 1024* 4KB = 4KB + 4MB
하지만, 일반적으로 프로세스는 1024개의 페이지 테이블을 모두 사용하지 않음

2) 사례1 - 프로세스가 1000개의 페이지로 구성

1000개의 페이지는 1개의 페이지 테이블에 의해 매핑 가능
메모리 소모량
- 1개의 페이지 디렉터리와 1개와 1개의 페이지 테이블
  - = 4KB + 4KB = 8KB

3) 사례2 - 프로세스가 400MB 크기인 경우

프로세스의 페이지 개수 = 400MB/4KB = 100x1024개
- 100개의 페이지 테이블 필요
메모리 소모량
- 1개의 페이지 디렉터리와 100개의 페이지 테이블
  - = 4KB = 100 x 4KB = 404KB

4) 결론

기존 페이지 테이블의 경우 프로세스 크기에 관계없이 프로세스 당 4MB가 소모
2-레벨 페이지 테이블의 경우 페이지 테이블로 인한 메모리 소모를 확연히 줄일 수 있다.

이 글이 문제가 된다면 삭제하겠습니다.

[운영체제] 8. 메모리 관리

Mon, 30 May 2022 04:46:35 GMT

메모리 계층 구조와 메모리 관리 핵심

메모리 계층 구조

메모리는 컴퓨터 시스템 여러 곳에 계층적으로 존재
- CPU 레지스터 - CPU 캐시 - 메인 메모리 - 보조기억장치
  - CPU 레지스터에서 보조기억장치로 갈수록 1) 용량 증가 2) 가격 저렴 3) 속도 저하
  - 메모리 계층 구조의 중심 - 메인 메모리
메모리 계층화의 목적
- 빠른 프로그램 실행을 위해 CPU의 메모리 엑세스 시간을 줄이기 위함

메모리 계층구조의 특성

	CPU 레지스터	L1/L2 캐시	L3 캐시	메인 메모리	보조기억장치
용도	몇 개의 명령과 데이터 저장	한 코어에서 실행되는 명령과 데이터 저장	멀티 코어들에 의해 공유. 명령과 데이터 저장	실행 중인 전체 프로세스들의 코드와 데이터, 입출력 중인 파일 블록들 저장	파일이나 데이터베이스, 그리고 메모리에 적재된 프로세스의 코드와 데이터의 일시저장
용량	바이트 단위. 8~30개 정도. 1KB 미만	KB 단위 (Core i7의 경우 32KB/256KB)	MB 단위(Core i7의 경우 8MB)	GB 단위 (최근 PC의 경우 최소 8GB 이상)	TB 단위
타입		SRAM (static RAM)	SRAM (static RAM)	DRAM (Dynamic RAM)	마그네틱 필드나 플래시 메모리
속도	<1ns	<5ns	<5ns	<50ns	<20ms
가격		고가	고가	보통	저가
휘발성	휘발성	휘발성	휘발성	휘발성	비휘발성

메모리 계층화 - 성능과 비용의 절충

1) 계층화

계층화 과정
- CPU 성능 향상 -> 더 빠른 메모리 요구 -> 작지만 빠른 off-chip 캐시 등장 -> 더 빠른 액세스를 위해 on-chip 캐시 -> 멀티 코어의 성능에 적합한 L1, L2, L3 캐시
  - 컴퓨터의 성능 향상 -> 처리할 데이터도 대형화 -> 저장 장치(하드 디스크)의 대형화 -> 빠른 저장 장치 요구 -> SSD의 등장
성능과 비용의 절충
- 빠른 메모리일수록 고가이므로 작은 용량 사용

2) 계층화 성공 이유

참조의 지역성 때문
- 코드나 데이터, 자원 등이 아주 짧은 시간 내에 다시 사용되는 프로그램의 특성
  - CPU는 작은 캐시 메모리에 로딩된 코드와 데이터로 한동안 실행
  - 캐시를 채우는 시간의 손해보다 빠른 캐시를 이용하는 이득이 큼

3) 계층화의 미래

현재, 메모리와 하드디스크 사이에 또 다른 형태의 메모리가 구현되고 있음

메모리 관리

1) 메모리의 역할

메모리는 실행하고자 하는 프로그램의 코드와 데이터 적재
CPU는 메모리에 적재된 코드와 데이터만 처리

2) 운영체제에 의해 메모리 관리가 필요한 이유

메모리는 공유 자원
- 여러 프로세스 사이에 메모리 공유
- 각 프로세스에게 물리 메모리 할당
메모리 보호
- 프로세스의 독립된 메모리 공간 보장
  - 사용자 코드로부터 커널 공간 보호
메모리 용량 한계 극복
- 설치된 물리 메모리보다 큰 프로세스 지원 필요
  - 여러 프로세스의 메모리 합이 설치된 물리 메모리보다 큰 경우 필요
메모리 효율성 증대
- 가능하면 많은 개수의 프로세스를 실행시키기 위해
- 프로세스 당 최소한의 메모리 할당

메모리 주소

물리 주소와 논리 주소

1) 메모리는 오직 주소로만 접근 2) 주소의 종류

물리 주소
- 물리 메모리(RAM)에 매겨진 주소. 하드웨어에 의해 고정된 메모리 주소
  - 0에서 시작하여 연속되는 주소 체계
  - 메모리는 시스템 주소 버스를 통해 물리 주소의 신호 받음
논리/가상 주소
- 개발자나 프로세스가, 프로세스 내에서 사용하는 주소, 코드나 변수 등에 대한 주소
  - 0에서 시작하여 연속되는 주소 체계
  - CPU가 프로세스를 실행하는 동안 다루는 모든 주소는 논리 주소
    - 프로세스 내에서 매겨진 상대주소 (프로그램에서 변수 n의 주소가 100번지라면, 논리 주소가 100이고, 물리 주소를 알 수 없음)
    - 컴파일러와 링커에 의해 매겨진 주소 (실행 파일 내에 만들어진 이진 프로그램의 주소들은 논리 주소로 되어 있음)
  - 사용자나 프로세스는 결코 물리 주소를 알 수 없음 3) MMU (Memory Management Unit)
논리 주소를 물리 주소로 바꾸는 하드웨어 장치
- CPU가 발생시킨 논리 주소는 MMU에 의해 물리 주소로 바뀌어 메모리에 도달
오늘날 MMU는 CPU 안에 내장
- 인텔이나 AMD의 x86 CPU는 80286부터 MMU를 내장
  - MMU 덕분에 여러 프로세스가 하나의 메모리에서 실행되도록 됨

C 프로그램에서의 주소는 논리 주소인가 물리 주소인가?

[참고]

ASLR (Address Space Layout Randomization)
- 해커들의 메모리 공격에 대한 대비책
  - 주소 공간의 랜덤 배치
- 프로세스의 주소 공간 내에서 스택이나 힙, 라이브러리 영역의 랜덤 배치
- 실행할 때마다 이들의 논리 주소가 바뀌게 하는 기법 -> 실행할 때마다 함수의 지역 변수와 동적 할당 받는 메모리의 논리 주소가 바뀜
- 하지만, 코드나 전역 변수가 적재되는 데이터 영역의 논리 주소는 바뀌지 않음

물리 메모리 관리

메모리 할당

운영체제가 새 프로세스를 실행 시키거나 실행 중인 프로세스가 메모리를 필요로 할 때, 물리 메모리 할당
프로세스의 실행은 할당된 물리 메모리에서 이루어짐
- 프로세스의 코드, 변수, 스택, 동적 할당 공간 액세스 등

메모리 할당 기법

1) 연속 메모리 할당

프로세스별로 연속된 한 덩어리의 메모리 할당
고정 크기 할당
- 메모리를 고정 크기의 파티션으로 나누고 프로세스 당 하나의 파티션 할당
가변 크기 할당
- 메모리를 가변 크기의 파티션으로 나누고 프로세스 당 하나의 파티션 할당

2) 분할 메모리 할당

프로세스에게 여러 덩어리로 나누어 메모리 할당
고정 크기 할당
- 고정 크기의 동일한 덩어리 메모리의 분산 할당. 대표 방법 - Segmentation 기법
가변 크기 할당
- 가변 크기의 덩어리 메모리를 분산 할당. 대표 방법 - 페이징 기법

※ 왼쪽 오른쪽 그림 위치가 바뀜

연속 메모리 할당

1) 각 프로세스 영역(코드와 데이터)을 연속된 메모리 공간에 배치

메모리를 한 개 이상의 파티션으로 분할하고 파티션을 할당하는 기법
한 프로세스는 한 파티션으로 할당

2) 연속 메모리 할당은 초기 운영체제에서 사용

MS-DOS 와 같은 과거 운영체제
- MS-DOS는 단일 사용자 단일 프로세스 시스템, 한 프로세스가 전체 메모리 독점
고정 크기 할당
- IBM OS/360 MFT
  - 메모리 전체를 고정 크기의 n개로 분할. 프로세스마다 하나씩 할당. 수용가능 프로세스의 수 n 고정
  - 메모리가 없을 때, 프로세스는 큐에서 대기
가변 크기 할당
- IBM OS/360 MVT
  - 프로세스마다 가변 크기로 연속된 메모리 할당. 수용가능 프로세스 수 가변
  - 메모리가 부족할 때, 프로세스는 큐에서 대기
가상 메모리 지원 X

단편화

1) 단편화

프로세스에게 할당할 수 없는 조각 메모리들이 생기는 현상, 조각 메모리를 홀(hole)이라고 부름

2) 내부 단편화

할당된 메모리 내부에 사용할 수 없는 홀이 생기는 현상
- 파티션보다 작은 프로세스를 할당하는 경우 발생
  - IBM OS/360 MFT 사례

3) 외부 단편화

할당된 메모리들 사이에 사용할 수 없는 홀이 생기는 현상
- 가변 크기의 파티션이 생기고 반환되면서 여러 개의 작은 홀 생성
  - 홀이 프로세스의 크기보다 작으면 할당할 수 없음
  - IBM OS/360 MVT 사례

연속 메모리 할당 구현

1) 하드웨어 지원

CPU 레지스터 필요
- base 레지스터 : 현재 CPU가 실행 중인 프로세스에게 할당된 물리 메모리의 시작 주소
  - limit 레지스터 : 현재 CPU가 실행 중인 프로세스에게 할당된 메모리 크기
  - 주소 레지스터 : 현재 액세스하는 메모리의 논리 주소
주소 변환 하드웨어(MMU) 필요 - 논리 주소를 물리 주소로 변환하는 장치

2) 운영체제 지원

모든 프로세스에 대해 프로세스별로 할당된 '물리메모리 시작 주소와 크기 정보 저장' 관리
비어있는 메모리 영역 관리
새 프로세스를 스케줄링하여 실행시킬 때마다, '물리 메모리의 시작 주소와 크기 정보'를 CPU 내부의 base 레지스터와 limit 레지스터에 적재

3) 연속 메모리 할당의 장단점

장점 1) 논리 주소를 물리 주소로 바꾸는 과정이 단순. CPU의 메모리 액세스 속도 빠름 2) 운영체제가 관리할 정보량이 적어서 부담이 덜함
단점 1) 메모리 할당의 유연성이 떨어짐. 작은 홀들을 합쳐 충분한 크기의 메모리가 있음에도, 연속된 메모리를 할당할 수 없는 경우 발생 (-> 메모리 압축 기법으로 해결)

홀 선택 알고리즘 / 동적 메모리 할당

운영체제는 할당 리스트 유지
- 할당된 파티션에 관한 정보를 리스트로 유지 관리
  - 할당된 위치, 크기, 비어 있는지 유무
할당 요청이 발생하였을 때 운영체제의 홀 선택 전략 3가지 1) first-fit(최초 적합)
비어있는 파티션 중 맨 앞에 요청 크기보다 큰 파티션 선택
할당 속도 빠름/단편화 발생 가능성

2) best-fit(최적 적합)

비어 있는 파티션 중 요청을 수용하는 가장 작은 파티션 선택
크기 별로 파티션이 정렬되어 있지 않으면 전부 검색
가장 작은 홀 생성됨

3) worst-fit(최악 적합)

비어 있는 파티션 중 요청을 수용하는 가장 큰 파티션 선택
크기 별로 파티션이 정렬되어 있지 않으면 전부 검색
가장 큰 홀 생성됨

세그먼테이션 메모리 관리

세그먼테이션 개요

1) 세그먼트

세그먼트는 논리적 단위 - 개발자의 관점에서 보는 프로그램의 논리적 구성 단위
세그먼트마다 크기 다름

2) 프로그램을 구성하는 일반적인 세그먼트 종류

코드 세그먼트
데이터 세그먼트
스택 세그먼트
힙 세그먼트

3) 세그먼테이션 기법

프로세스를 논리 세그먼트 크기로 나누고, 각 논리 세그먼트를 한 덩어리의 물리 메모리에 할당하고 관리하는 메모리 관리 기법]
프로세스의 주소 공간
- 프로세스의 주소 공간을 여러 개의 논리 세그먼트들로 나누고
  - 각 논리 세그먼트를 물리 세그먼트에 매핑
  - 프로세스를 논리 세그먼트로 나누는 과정은 컴파일러, 링커, 로더, 운영체제에 의해 이루어짐

4) 논리 세그먼트와 물리 세그먼트의 매핑 - 시스템 전체 세그먼트 매핑 테이블을 두고 논리 주소를 물리 주소로 변환 5) 외부 단편화 발생

세그먼테이션의 구현

1) 하드웨어 지원

논리 주소 구성 : [세그먼트 번호, 옵셋]
- 옵셋 : 세그먼트 내 상대 주소
CPU
- 세그먼트 테이블의 시작 주소를 가리키는 레지스터 필요
MMU 장치
- 논리 주소를 물리 주소로 변환하는 장치
  - 논리 주소가 세그먼트 범위를 넘는지 판별(메모리 보호)
  - 논리 주소의 물리 주소 변환(메모리 할당)
세그먼트 테이블
- 메모리에 저장
  - 세그먼트별로 시작 물리 주소와 세그먼트 크기 정보

2) 운영체제 지원

세그먼트의 동적 할당/반환 및 세그먼트 테이블 관리 기능 구현
- 프로세스의 생성/소멸에 따라 동적으로 세그먼트 할당/반환
  - 물리 메모리에 할당된 세그먼트 테이블과 자유 공간에 대한 자료 유지
  - 컨텍스트 스위칭 때 CPU의 레지스터에 적절한 값 로딩 3) 컴파일러, 링커, 로더 지원
사용자 프로그램을 세그먼트 기반으로 컴파일, 링킹, 로딩

단편화

외부 단편화 발생
- 세그먼트들의 크기가 같지 않기 때문에 세그먼트와 세그먼트 사이에 발생하는 작은 크기의 홀
내부 단편화 발생 없음

[운영체제] 7. 교착상태

Mon, 30 May 2022 04:46:10 GMT

교착 상태 : 자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기

식사하는 철학자 문제

철학자들의 교착상태 원인과 해결

교착상태 원인 - 환형 요청/대기(circular wait)
- 5명 모두 왼쪽 포크를 가지고 오른쪽 포크를 요청하는 환형 고리
  - 환형 고리는 스스로 인식이나 해체 불가
교착 상태 해결 - '환형 대기'가 생기지 않도록
- 마지막 철학자(5번)만 오른쪽 포크를 먼저 잡고 왼쪽을 잡도록 규칙 수정

식사하는 철학자 문제는 교착 상태 문제를 비유

교착상태는 다중프로그래밍 시스템 초기에 노출된 문제점
- 철학자 : 프로세스
  - 포크 : 자원
  - 스파게티 : 프로세스가 처리할 작업

교착상태

1) 교착상태(deadlock)

자원을 소유한 스레드들 사이에서, 각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하고 있는 현상
- deadly embrace : 풀지 못하는 포옹
  - 교착상태 문제는 1965년 Dijkstra의 banker's algorithm research 에서 처음 제기 2) 교착상태 발생 위치
사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생
- 정교하지 못한 코딩에서 비롯
커널 내에서도 발생
- 거의 발생하지 않음, 매우 정교하게 작성되기 때문
교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없는 실상
- 막는데 많은 시간과 공간의 비용이 들기 때문
  - 교착상태가 발생하도록 두고, 교착상태가 발생한 것 같으면, 시스템 재시작, 혹은 의심스러운 몇몇 프로그램 종료

3) 교착생태의 전형적인 발생 상황

2개의 스레드가 각각 락 소유, 상대가 가진 락 요청하고 기다릴 때
- 단일 CPU/ 다중 CPU 모두에서 발생, T1과 T2가 서로 다른 CPU에서 실행될 때도 발생
락과 자원에 대한 경쟁이 있는 한 교착상태는 언제든 발생 가능

교착상태를 유발시킬 수 있는 컴퓨터 시스템의 잠재적 요인

자원

교착상태의 발생지
- 교착상태는 멀티스레드가 자원을 동시에 사용하려는 충돌이 요인
컴퓨터 시스템에는 많은 자원 존재
- 소프트웨어 자원 - 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스, 파일 락
  - 하드웨어 자원 - 프린터, 메모리, 프로세스 등

자원과 스레드

한 스레드가 여러 자원을 동시에 필요로 하는 상황이 요인

자원과 운영체제

한 번에 하나씩 자원을 할당하는 운영체제 정책이 요인

자원 비선점

할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺏지 못하는 정책이 요인
- 운영체제는 스레드가 가진 자원을 강제로 뺏지 못함
  - 만일 강제로 빼앗을 수 있다면? 교착상태가 발생하지 않게 할 수 있다.

교착상태 모델링

1) 자원 할당 그래프(Resource Allocation Graph, RAG)

그래프의 요소
- 꼭지점 - 스레드, 자원
  - 간선 - 소유/요청 관계. 할당 간선과 요청 간선 1) 할당 간선 : 자원에서 스레드로 향하는 화살표. 할당 받은 상태 표시 2) 요청 간선 : 스레드에서 자원으로 향하는 화살표. 요청 표시
자원에 대한 시스템의 상태를 나타내는 방향성 그래프
- 컴퓨터 시스템에 실행 중인 전체 스레드와 자원의 개수
- 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
- 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
- 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수

2) 자원할당 그래프를 통해 교착상태 판단

교착상태 예방, 회피, 감지를 위한 알고리즘 개발에 필요

교착상태가 발생하는 프로그램 만들기

#include 
#include 
#include 
#include 

int x = 0; //공유 변수
int y = 0; //공유 변수
pthread_mutex_t lock1; //뮤텍스 락 변수
pthread_mutex_t lock2; //뮤텍스 락 변수

void* worker1(void* arg){ //스레드 코드
    pthread_mutex_lock(&lock1); //x를 독점 사용하기 위해 lock1 잠그기
    printf("%s lock1 잠금\n", (char*)arg);
        x++;
        sleep(2); //2초 잠자기

        pthread_mutex_lock(&lock2); //y를 독점 사용하기 위해 lock2 잠그기
        printf("%s lock2 잠금\n", (char*)arg); 
        y++;
        pthread_mutex_unlock(&lock2); //lock2 풀기
        printf("%s lock2 해제\n", (char*)arg);

    pthread_mutex_unlock(&lock1); //lock1 풀기
    printf("%s lock1 해제\n", (char*)arg);
}

void* worker2(void* arg){ //스레드 코드
    pthread_mutex_lock(&lock2); //y를 독점 사용하기 위해 lock2 잠그기
    printf("%s lock2 잠금\n", (char*)arg);   
        y++;
        sleep(2); //2초 잠자기

        pthread_mutex_lock(&lock1); //x를 독점 하용하기 위해 lock1 잠그기
        printf("%s lock1 잠금\n", (char*)arg);
        x++;
        pthread_mutex_unlock(&lock1); //lock1 풀기
        printf("%s lock1 해제\n, (char*)arg);

    pthread_mutex_unlock(&lock2); //lock2 풀기
    printf("%s lock2 해제\n", (char*)arg);
}

int main(){
    char *name[] = {"황기태", "이찬수"};
    pthread_t tid[2];

    pthread_mutex_init(&lock1, NULL); //뮤텍스 락 변수 lock1 초기화
    pthread_mutex_init(&lock2, NULL); //뮤텍스 락 변수 lock2 초기화

    pthread_create(&tid[0], NULL, worker1, name[0]); //worker1 스레드 생성
    pthread_create(&tid[1], NULL, worker2, name[1]); //worker2 스레드 생성 

    pthread_join(tid[0], NULL);
    pthread_join(tid[1], NULL);

    pthread_mutex_destroy(&lock2);
    pthread_mutex_destroy(&lock1);

    printf("x = %d, y = %d\n", x, y);

    return 0;
}

교착상태 해결

교착상태가 발생하는 4가지 필요충분 조건

1) 코프만 조건

교착상태가 발생하는 4가지 필요충분 조건
- Computing Survey, Vol.3, No.2, June, 1971에 실린 논문

다음 4가지 상황이 허용되는 시스템은 언제든 교착상태 발생 가능 1) 상호배제

  - 각 자원은 한 번에 하나의 스레드에게만 할당
  - 자원이 한 스레드에게 할당되면 다른 스레드에게는 할당될 수 없음

2) 소유하면서 대기(Hold & Wait)

  - 스레드가 한 사원을 소유(lock) 하면서 다른 자원을 기다리기

3) 강제 자원 반환 불가(No Preemption)

  - 스레드에게 할당된 자원을 강제로 빼앗지 못함

4) 환형 대기(Circular Wait)

     - 한 그룹의 스레드들에 대해 각 스레드는 다른 스레드가 요청하는 자원을 소유하는 원형 고리 형성

** 4가지 조건 중 한 가지라도 성립되지 않으면 교착상태 발생 X

교착상태로 인해 시스템 전체가 중단되지는 않는다. 교착상태는 시스템 내에 몇몇 스레드들 사이에서 발생하므로 이들 스레드들만 실행이 중지된 채 대기상태에 머물며, 이들로 인해 시스템 전체가 불능 상태가 되는 것은 아니다. 시스템 관리자나 이들 스레드들을 제거하면 이들의 교착상태는 사라진다. 만일 많은 스레드들이 교착상태에 연루되어 있을 때는 시스템을 재시작 하는 것 좋다.

교착상태 예방

** 코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 함

상호배제 조건 -> 상호배제 없애기

동시에 2개 이상의 스레드가 자원을 활용할 수 있도록 함
컴퓨터 시스템에서 근본적으로 적용 불가능한 방법

소유하면서 대기 조건 -> 기다리지 않게

방법1 : 운영체제는 스레드 실행 전 필요한 모든 자원을 파악하고 실행시 한 번에 할당
당장 사용하지 않는 자원을 스레드에게 묶어 두기 때문에 자원 활용률이 떨어짐
다른 스레드는 필요한 자원을 할당 받지 못하고 실행 대기
방법2 : 스레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고, 한꺼번에 요청하여 할당

=> 방법1이나 방법2 모두 가능하지 않거나 매우 비효율적인 방법

강제 자원 반환 불가 조건 -> 선점 허용

자원을 강제로 반환하게 된 스레드가 자원을 다시 사용하게 될 때 이전 상태로 되돌아갈 수 있도록 상태를 관리할 필요
간단히 않고 오버헤드도 매우 큼

환형 대기 조건 -> 환형 대기 제거

모든 자원에게 번호를 매기고, 번호순으로 자원을 할당 받게 함

교착상태 회피

자원 할당 시, 미래에 환형 대기가 발생할 것으로 판단되면 자원 할당을 하지 않는 정책

banker's 알고리즘으로 해결 1) Edsger Dijkstra 에 의해 개발된 알고리즘. 자원 할당 전에 미래에 교착상태가 발생하지 않을 것인지 안전한지 판단하는 알고리즘

 - 은행에서의 대출 알고리즘

2) 안전한 상태

 - 현재 프로세스들을 어떤 순서로 실행시켰을 때, 모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있다면 안전한 상태

3) 불안전한 상태

 - 환형 대기에 빠질 수 있다면 불안전한 상태

4) 알고리즘

 - 각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알림
 - 자원을 할당할 때마다, 자원을 할당해주었을 때 교착상태가 발생하지 않을 만큼 안전한 상태인지 판단하여 안전한 상태일 때만 자원할당
 - 각 프로세스가 필요한 자원의 개수, 현재 각 프로세스가 할당 받은 자원의 개수, 그리고 시스템 내 할당 가능한 자원의 개수를 토대로 현재 요청된 자원을 할당해도 안전한지 판단

5) 비현실적

 - 각 프로세스가 실행 전에 필요한 자원의 개수를 아는 것은 불가능
 - 프로세스의 개수도 동적으로 변하기 때문에 미리 프로세스의 개수를 정적으로 고정시키는 것은 불가능

교착상태 감지 및 복구

1) 교착상태를 감지하는 프로그램을 통해, 형성된 교착상태를 푼다.

백그라운드에서 교착상태를 감지하는 프로그램 늘 실행

2) 교착상태를 감지하였을 때의 복구 방법

자원 강제 선점
교착상태에 빠진 스레드 중 하나의 자원을 강제로 빼앗아 다른 스레드에게 할당
롤백
운영체제는 주기적으로 교착상태가 발생할 것으로 예측도는 스레드의 상태를 저장하여 두고 교착상태가 발생하면 마지막으로 저장된 상태로 돌아가도록 하고, 다시 시작하면서 자원을 다르게 할당
스레드 강제 종료
교착상태에 빠진 스레드 중 하나 강제 종료
가장 간단하면서도 효과적인 방법
시간과 메모리 공간(rollback의 경우)에 대한 부담이 크기 때문에 잘 사용하지 않음

교착상태 발생위치 - 교착상태는 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생하며 개발자의 미숙한 멀티스레드 코딩에서 비롯된다. 교착상태는 커널 내에서도 발생할 수 있지만 거의 발생하지 않는다. 커널의 최고의 개발자들에 의해 매우 정교하게 작성되어 있기 때문이다.

교착상태 무시 : 타조 알고리즘

1) 교착상태를 해결할 필요가 있을까?

교착상태에 대한 통계치는 없다.
교착상태는 반드시 발생
- 하지만 교착상태의 발생 가능성이 극히 적고
  - 교착상태를 피하기 위한 비용이 많이 들어감

2) 타조알고리즘

Put your head in the sand 접근법
- 타조가 머리를 모래 속에 박조 자신이 보이지 않는 척하는 것
- 교착상태는 발생하지 않을 거야하고 아무 대책을 취하지 않는 접근법
Unix 와 Window 등 현재 거의 모든 운영체제에서 사용
- 의심가는 스레드를 종료시키거나 시스템 재시작
- 거의 발생하지 않거나 아주 드물게 발생하는 것에 비해 교착상태 해결에는 상대적으로 비용이 많이 들기 때문

3) 주의

핵 시스템, 비행기, 미사일 등 시스템 재시작이 파국을 초래할 hard real-time 시스템이나 환자 감지 시스템 등에서는 적합하지 않음
- 이런 시스템에서는 자원에 대한 프로세스의 할당 등에 대해 미리 알고 적절한 조치가 필요

교착상태를 다루는 현실적인 방안

대부분의 운영체제 : ostrich 알고리즘 사용
교착상태가 일어나지 않을 것으로 가정하고, 교착상태에 대한 아무 대책을 세우지 않음
- 교착상태가 발생할 확률은 극히 작음
교착상태 예방, 회피, 감지에는 많은 오버헤드가 소모되므로
교착상태가 발생하면 시스템 재시작 혹은 특정 프로세스/스레드 강제 종료
- 관련된 데이터를 잃어버릴 수 있음
  - 하지만 전체적으로 크지 않은 손실

이 글이 문제가 된다면 삭제하겠습니다.

[운영체제] 6. 스레드 동기화

Mon, 30 May 2022 04:44:51 GMT

스레드 동기화의 필요성

다수의 스레드가 동시에 공유 데이터에 접근하면
- 공유 데이터가 훼손되는 문제 발생
스레드 동기화
- 공유 데이터에 대한 다수의 스레드가 동시에 접근할 때 공유데이터가 훼손되는 문제의 해결책
  - 공유데이터를 접근하고자 하는 다수의 스레드가 충돌없이 공유데이터에 접근하기 위해 상호 협력하는 것

공유 데이터 접근 문제의 해결책

문제점
- 여러 스레드가 공유 변수에 접근할 때, 공유데이터 훼손
해결책 : 스레드 동기화
- 한 스레드가 공유데이터에 대한 접근을 마칠 때까지
  - 다른 스레드가 공유 데이터를 접근하지 못하도록 제어
멀티스레드의 경쟁 상황이 자주 발생하는가?
- 매우 자주 발생
  - 커널 코드에서 자주 발생 (커널에 공유데이터가 많기 때문)
    - 다중 코어에서 더욱 조심

임계구역과 상호배제

스레드 동기화와 관련된 2가지 중요 개념 : 임계구역과 상호배제
임계구역
- 공유데이터에 접근하는 프로그램 코드들
상호배제
- 임계구역이 오직 한 스레드만 배타독점적으로 사용되도록 하는 기술 1) 임계구역에 먼저 진입한 스레드가 임계구역의 실행을 끝낼 때까지 2) 다른 스레드가 진입하지 못하도록 보장

상호배제

상호배제를 포함하는 프로그램

일반코드(non-critical code)

공유데이터를 액세스하지 않는 코드

임계구역 진입 코드(entry code)

상호배제를 위해 필요한 코드
- 임계구역에 진입하기 전 필요한 코드 블록
현재 임계구역을 실행 중인 스레드가 있는지 검사
- 없다면, 다른 스레드가 들어오지 못하도록 조치
  - 있다면, 진입이 가능해질 때까지 대기

임계구역 코드(critical code)
임계구역 진출 코드(exit code)

상호배제를 위해 필요한 코드
- 임계구역의 실행을 마칠 때 실행되어야 하는 코드 블록
entry code에서 대기중인 스레드가 임계구역에 진입할 수 있도록 entry code 에서 취한 조치를 해제하는 코드

상호배제 구현

상호배제 구현 목표
- 임계구역에 오직 1개의 스레드만 진입
상호배제 구현 방법
- 소프트웨어적 방법 - Peterson's 알고리즘 등
  - 하드웨어적 방법 - 인터럽트 서비스 금지, 원자 명령 활용 (오늘날 대부분 하드웨어 솔루션 사용)
하드웨어적 방법
임계 구역 진입/진출 코드에 구현
방법1 - 인터럽트 서비스 금지
- 인터럽트가 발생해도 CPU가 인터럽트를 무시하도록 하는 CPU 명령 이용
방법2 - 원자 기계 명령 사용
- 상호배제 구현에 가장 많이 사용하는 방법
  - 임계구역에 진입할 때, 임계구역을 잠그고 들어가는 명령 하나(원자명령)로 다른 스레드가 들어오지 못하게 하는 방법

상호배제 구현 방법1 - 인터럽트 서비스 금지

1) 인터럽트 서비스 금지 방법

임계구역 entry 코드에서 인터럽트 서비스를 금지하는 명령 실행

cli ; entry 코드. 인터럽트 서비스 금지 명령 cli (clear interrupt flag) ... 임계구역 코드 ... sti ; exit 코드. 인터럽트 서비스 명령 허용 sti (set interrupt flag)

1) 장치로부터 인터럽트가 발생해도, CPU가 인터럽트 발생을 무시 2) 인터럽트가 발생해도 CPU는 인터럽트 서비스 루틴을 실행하지 않음 3) 인터럽트를 무시하면 임계구역을 실행하는 스레드가 중단되지 않음

2) 문제점

모든 인터럽트가 무시되는 문제 발생
멀티코어 CPU나 다중 CPU를 가진 시스템에서 활용 불가
- 한 CPU의 인터럽트 금지로 다른 CPU에게 까지 인터럽트 금지는 불가하다.
- 해결 방법 : CPU는 lock 접두어가 붙은 명령을 처리할 때, CPU의 LOCK핀에 신호를 발생시켜 현재 액세스하고 있는 메모리에 다른 프로세서들이 접근하지 않도록 한다. 그러므로 컴퓨터 설계자는 LOCK 신호를 이용하여 다른 프로세서의 공유 메모리 접근을 막도록 회로를 구성하여야 한다.

단순 lock변수로 상호배제 시도

locking/unlocking 방식으로 임계구역의 entry/exit 코드 작성하면 상호배제가 가능할까?
- lock 변수 : 1이면 잠금상태
- lock 변수 : 0이면 열린상태

상호배제구현 방법2 - 원자명령 사용

lock 변수를 이용한 상호배제의 실패 원인
- 실패 원인은 entry code에 있음
  - lock 변수 값을 읽는 명령과 lock 변수에 1을 저장하는 2개의 명령 사이에 컨텍스트 스위칭이 될 때 문제 발생
해결책 - 원자 명령 도입
- lock 변수를 읽어들이는 명령과 lock 변수에 1을 저장하는 2개의 명령을 한 번에 처리하는 원자 명령 필요
  - 원자 명령 : TSL (Test and Set Lock)
    - 1970년대 Intel Pentium에서 시작. 대부분의 CPU에서 제공

멀티스레드 동기화 기법

멀티스레드 동기화

1) 멀티스레드 동기화란?

상호배제 기반위에
자원을 사용하려는 여러 스레드들이 자원을 원활히 공유할 수 있도록 하는 기법
동기화 프리미티브(synchronization primitives)로 부름

2) 대표적인 기법

lock 방식 : 뮤텍스(mutex), 스핀락(spilock)
- 상호배제가 되도록 만들어진 락(lock)활용
- 락을 소유한 스레드만이 임계구역 진입
- 락을 소유하지 않은 스레드는 락이 풀릴 때까지 대기
wait-signal 방식 : 세마포(semaphore)
- n개의 자원을 사용하려는 m개 멀티스레드의 원활한 관리
- 자원을 소유하지 못한 스레드는 대기(wait)
- 자원을 다 사용한 스레드는 알림(signal)

뮤텍스

mutual exclusion 의 약자이다.

1) 뮤텍스

잠김/열림 중 한 상태를 가지는 lock 변수 이용
한 스레드만 임계구역에 진입시킴
다른 스레드는 큐에 대기
sleep-waiting lock 기법

2) 구성요소

락 변수

true/false 중 한 값
true : 락을 잠근다. 락을 소유한다.
false : 락을 연다. 락을 해제한다.

대기 큐

락이 열리기를 기다리는 스레드 큐

연산

lock 연산(임계구역은 entry code)
락이 잠김 상태(lock = ture) 이면, 현재 스레드를 블록 상태로 만들고 대기 큐에 삽입
락이 열린 상태이면, 락을 잠그고 임계구역 진입

뮤텍스의 특징

1) 뮤텍스를 이용한 동기화 특징

임계구역의 실행시간이 짧은 경우, 비효율적
- 락이 잠겨 있으면(컨택스트 스위칭되어) 대기 큐에서 대기, 락이 풀리면 다시(컨택스트 스위칭되어) 실행 -> 락이 잠겨 있는 시간보다 스레드가 잠자고 깨는데 걸리는 시간이 상대적으로 크기 때문

2) 뮤텍스 동기화를 위한 POSIX 표준 라이브러리

뮤텍스락 변수
- pthread_mutex_t lock;
뮤텍스 조작 함수들
- pthread_mutex_init() - 뮤텍스락 변수 초기화
  - pthread_mutex_lock() - 뮤텍스락 잠그기
  - pthread_mutex_unlock() - 뮤텍스락 풀기
  - pthread_mutex_destroy() - 뮤텍스락 변수 사용 종료

3) pthread를 이용한 뮤텍스 동기화 코딩 사례

pthread_mutex_t lock;                //뮤텍스락 변수 생성
pthread_mutex_init(&lock, NULL);    //뮤텍스락 변수 초기화
pthread_mutex_lock(&lock);            //임계구역 entry 코드. 뮤텍스락 잠그기

...임계구역 코드...

pthread_mutex_unlock(&lock);        //임계구역 exit 코드. 뮤텍스락 열기

pthread의 뮤텍스를 이용한 공유집계판의 스레드 동기화

#include 
#include 

int sum = 0;
pthread_mutext_t lock;

void* worker(void arg){
    printf("%s 시작 \t %d\n", (char*)arg, sum);

    for(int i = 0; i < 1000000 ; i++){
        pthread_mutex_lock(&lock);
        sum = sum + 10;
        pthread_mutex_unlock(&lock);
    }
    printf("%s 끝 \t %d\n", (char*)arg, sum);
}

int main(){
    char *name[] = {"황기태", "이찬수"};
    pthread_t tid[2];
    pthread_attr_t attr[2]; //스레드 정보를 담을 구조체

    pthread_attr_init(&attr[0]);
    pthread_attr_init(&attr[1]);

    pthread_mutex_init(&lock, NULL);

    pthread_create(&tid[0], &attr[0], worker, name[0]);
    pthread_create(&tid[1], &attr[1], worker, name[1]);

    pthread_join(tid[0], NULL);
    pthread_join(tid[1], NULL);

    printf("최종 sum = %d\n", sum);

    pthread_mutex_destroy(&lock);

    return 0;
}

스핀락

1) 스핀락

busy-waiting lock 기법
- 스레드가 큐에서 대기하지 않고 락이 열릴 때까지 계속 락 변수 검사
뮤텍스와 거의 같고 busy-waiting 이라는 점에서만 다름
- 대기큐 없음
  - busy-waiting 으로 인해 CPU를 계속 소모. CPU가 다른 스레드를 실행시킬 수 없음
lock을 소유한 스레드만 자원 배타적 사용하는 동기화 기법
- 공유자원 하나 당 하나의 스핀락 사용

2) 구성요소

락 변수
- true/false 중 한 값
  - true : 락을 잠근다. 락을 소유한다.
  - false : 락을 연다. 락을 해제한다.
연산

lock 연산
- 임계구역에 들어갈 때 실행되는 entry code
  - 락이 잠김 상태면, 락이 풀릴 때까지 무한 루프 돌면서 lock 연산 시도
  - 락이 열린 상태면, 락을 잠김 상태로 바꾸고 임계구역 실행
unlock 연산
- 임계구역을 나올 때 실행하는 exit code
  - 락을 열림 상태로 변경

스핀락 특징

1) 스핀락을 이용한 동기화 특징

뮤텍스의 non-blocking 모델
- 락이 잠겨 있을 때 블록되지 않고 락이 풀릴 때까지 검사 코드 실행
단일 CPU를 가진 운영체제에서 비효율적, 멀티코어에 적합
- 단일 코어 CPU에서 의미 없는 CPU 시간 낭비 (Lock을 갖고 있는 스레드를 풀어주려면 단일 코어 CPU에서는 어차피 컨택스트 스위칭을 해야하기 때문이다) -> 스핀락을 검사하는 스레드의 타임 슬라이스가 끝날 때까지 다른 스레드는 실행 안 됨. 다른 스레드의 실행 기회 뺏음 -> 락을 소유한 다른 스레드가 실행되어야 락이 풀림
  - 임계구역의 실행 시간이 짧은 경우 효과적

2) 스핀락 동기화를 위한 POSIX 표준 라이브러리

스핀락 변수
- pthread_spin_t lock;
스핀락 조작 함수들
- pthread_spin_init() - 스핀락 변수 초기화
  - pthread_spin_lock() - 스핀락 잠그기
  - pthread_spin_unlock() - 스핀락 풀기
  - pthread_spin_destroy() - 스핀락 변수 사용 종료

3) pthread를 이용한 스핀락 동기화 코딩 사례

pthread_spinlock_t lock;        //스핀락 변수 생성
pthread_spin_init(&lock, NULL);    //스핀락 변수 초기화
pthread_spin_lock(&lock);        //임계구역 entry code. 스핀락 잠그기

... 임계구역 코드 ...

pthread_spin_unlock(&lock);        //임계구역 exit code. 스핀락 열기

pthread의 스핀락을 이용한 공유 집계판의 스레드 동기화

#include 
#include 

int sum = 0;
pthread_spinlock_t lock;

void* worker(void arg){
    printf("%s 시작 \t %d\n", (char*)arg, sum);

    for(int i = 0; i < 1000000 ; i++){
        pthread_spin_lock(&lock);
        sum = sum + 10;
        pthread_spin_unlock(&lock);
    }
    printf("%s 끝 \t %d\n", (char*)arg, sum);
}

int main(){
    char *name[] = {"황기태", "이찬수"};
    pthread_t tid[2];
    pthread_attr_t attr[2]; //스레드 정보를 담을 구조체

    pthread_attr_init(&attr[0]);
    pthread_attr_init(&attr[1]);

    pthread_spin_init(&lock, PTHREAD_PROCESS_PRIVATE);
    //lock을 한 프로세스에 속한 스레드만이 공유하는 변수로 선언

    pthread_create(&tid[0], &attr[0], worker, name[0]);
    pthread_create(&tid[1], &attr[1], worker, name[1]);

    pthread_join(tid[0], NULL);
    pthread_join(tid[1], NULL);

    printf("최종 sum = %d\n", sum);

    pthread_mutex_destroy(&lock);

    return 0;
}

뮤텍스와 스핀락은 어떤 경우에 적합한가?

락이 잠기는 시간이 긴 응용 : 뮤텍스

락을 얻지 못했을 때, CPU를 다른 스레드에게 양보하는 것이 효율적
락이 잠기는 시간이 짧은 경우 : 스핀락이 효율적

단일 CPU를 가진 시스템 : 뮤텍스

단일 CPU에서 스핀락은 크게 의미 없음

멀티 코어(멀티 CPU)를 가진 시스템 : 스핀락

잠자고 깨는 컨택스트 스위칭 없이 바로 자원 사용
임계구역은 가능한 짧게 작성하므로

사용자 응용프로그램 : 뮤텍스, 커널 코드 : 스핀락

커널 코드나 인터럽트 서비스 루틴은 빨리 실행되어야 하고, 인터럽트 서비스 루틴 내에서 잠잘 수 없기 때문

스핀락을 사용하면 기아 발생 가능

스핀락은 무한 경쟁 방식이어서 기아가 발생 가능
- 락을 소유한 스레드가 락을 풀지 않고 계속 실행하거나 종료해버린 경우, 코딩이 잘못된 경우

뮤텍스와 스핀락 비교

	뮤텍스	스핀락
대기큐	있음	없음
블록 가능 여부	락이 작겨 있으면 블록됨	락이 잠겨 있어도 블록되지 않고 계속 락 검사
lock/unlock 연산 비용	저비용	CPU를 계속 사용하므로 고비용
하드웨어 관련	단일 CPU에서 적합	멀티코어 CPU에서 적합
주 사용처	사용자 응용 프로그램	커널 코드, 인터럽트 서비스 루틴

왜 알아야 하는가?

개발자로서 둘 중 하나를 선택하여야하고, 시스템의 성능 관점에서 볼 수 있어야 하기 때문이다.

세마포

세마포가 필요한 상황

1) 세마포의 정의

멀티스레드 사이의 자언 관리 기법
- n개의 공유 자원을 다수 스레드가 공유하여 사용하도록 돕는 자원 관리 기법 (n개의 프린터가 있는 경우, 프린터를 사용하고자 하는 다수 스레드의 프린터 관리)

2) 구성요소

자원 : n개
대기 큐 : 자원을 할당 받지 못한 스레드들이 대기하는 큐
counter 변수

사용 가능한 자원의 개수를 나타내는 정수형 전역 변수
n으로 초기화 (counter = n)

P/V 연산

P연산(wait 연산) - 자원 요청 시 실행하는 연산 (자원 사용 허가를 얻는 과정)
V연산(signal 연산) - 자원 반환 시 실행하는 연산 (자원 사용이 끝났음을 알리는 연산)

P연산과 V연산

P/V를 wait/signal 로 표기하기도 함
- P연산 : 자원 사용을 허가하는 과정, 사용 가능 자원 수 1 감소(counter--)
  - V연산 : 자원 사용을 마치는 과정, 사용가능 자원 수 1 증가(counter++)
세마포 종류 2가지 - 자원을 할당 받지 못한 경우의 행동에 따라 구분 1) sleep-wait 세마포

P연산 : 대기 큐에서 잠자기, V연산 : 사용가능 자원이 있으면 잠자는 스레드 깨우기

P 연산 { 
  counter--;
  if counter < 0 {
  ... 현재 스레드들 대기 큐에 삽입 ... 
  }
  ... 자원 획득 ...
}

V 연산 {
    counter++;
    if counter <= 0 {
    ... 대기 큐에서 한 스레드 깨움 ...
    }
}

2) busy-wait 세마포

P연산 : 사용 가능 자원이 생길 때까지 무한 루프, V연산 : counter--;

P 연산 {
    while counter <= 0;
    counter--;
}

V 연산 { 
    counter++;
}

세마포 활용을 위한 POSIX 표준 라이브러리

1) 세마포 구조체

sem_t s; // counter 변수 등을 가진 세마포 구조체

2) 세마포 조작 함수들

sem_init() - 세마포 초기화
sem_destroy() - 세마포 기능 소멸
sem_wait()
- P연산을 수행하는 함수 (blocking call)
  - sleep-wait 방식으로, 가용 자원이 없으면 대기 큐에서 잠을 잠
sem_trywait()
- p연산을 수행하는 함수(non-blocking call)
  - 가용 자원이 있으면, counter 값을 감소시키고 0 리턴
  - 없으면, counter 값을 감소시키지 않고 -1 리턴
sem_post() - V연산을 수행하는 함수
sem_getvalue() - 세마포의 현재 counter 값을 리턴하는 함수

세마포 활용 사례

#include 
#include 
#include 
#include 

sem_t toiletsem; // POSIX 세마포 구조체로 모든 스레드에 의해 공유

void* guestThread(void* arg){ // 고객의 행동을 묘사하는 스레드 코드
    int cnt = -1;

    sem_wait(&toiletsem); // P연산. 자원 사용 요청. 세마포의 counter 값 1 감소
    sem_getvalue(&toiletsem, &cnt); // 세마포의 counter 을 cnt 변수로 읽어오기
    printf("고객%s 화장실에 들어간다.. 세마포 conter = %d\n" ,(char*)arg, cnt); // 1초동안 화장실을 사용한다. 
    sem_post(&toiletsem); // V연산. 화장실 사용을 끝냈을음 알림
       sem_getvalue(&toiletsem, &cnt); // 세마포의 counter 값을 cnt 변수로 읽어오기
    printf("고객%s 화장실에서 나온다. 세마포 counter = %d\n", (char*)arg, cnt);
}

#define NO 0 // 자식 프로세스와 세마포 공유하지 않음
#define MAX_COUNTER 3 // 자원의 개수, 동시에 들어갈 수 있는 스레드의 개수

int main(){
    int counter = -1;
    char *name[] = {"1", "2", "3", "4", "5"};
    pthread_t t[5]; // 스레드 구조체

    //세마포 초기화 : MAX_COUNTER 명이 동시에 사용
    sem_init(&toiletsem, &counter);
    sem_getvalue(&toiletsem, &counter); // 세마포의 현재 counter 값 읽기
    printf("세마포 counter = %d\n", counter);

    for(int i = 0; i < 5; i++) pthread_create(&t[i], NULL, guestThread, (void*)name[i]); // 5명의 고객 스레드 생성

    for(int i = 0; i< 5; i++) pthread_join(t[i], NULL); // 모든 고객이 소멸할 때까지 대기

    sem_getvalue(&toiletsem, &counter); // 세마포의 현재 counter 값 읽기

    printf("세마포 counter = %d\n", counter);
    sem_destroy(&toiletsem); // 세마포 기능 소멸

    return 0;
}

-> 3개의 칸이 있는 화장실을 5명의 고객이 사용하고자 할 때 세마포를 이용하여 3칸의 화장실을 5명의 고객 스레드가 활용할 수 있게 관리하는 예시

카운터 세마포와 이진 세마포

1) 카운터 세마포

자원의 인스턴스가 여러 개인 경우 (앞서 설명) 2) 이진 세마포
자원이 1개 있는 경우 멀티스레드 사이의 자원 관리
1개의 자원에 대해 1개의 스레드만이 액세스할 수 있도록 보호
- 뮤텍스와 매우 유사

3) 이진 세마포의 구성 요소

세마포 변수 S

0과 1중 하나를 가지는 전역 변수, S는 1로 초기화

대기큐

사용 가능한 자원이 생길 때까지 스레드들이 대기하는 큐
스레드 스케줄링 알고리즘 필요

2개의 원자 연산

wait 연산(P연산) - 자원 사용 허가를 얻는 과정
- S가 1 감소 시키고, 0보다 작으면 대기 큐에서 잠듬 0보다 크거나 같으면 자원 사용하는 코드 실행
signal(V연산) - 자원 사용이 끝났음을 알리는 과정
- S를 1 증가시키고, 0보다 크면 그냥 리턴, 0보다 작거나 같으면 대기 큐에 있는 스레드 중 한 개를 깨움

동기화 이슈 : 우선순위 역전

우선 순위 역전(priority inversion)
- 스레드의 동기화로 인해 높은 순위의 스레드가 낮은 스레드보다 늦게 스케줄링 되는 현상 -> 우선순위를 기반으로 스케줄링하는 실시간 시스템에서 스레드 동기화로 인해 발생
우선 순위 역전의 문제점
- 실시간 시스템의 근본 붕괴 1) 우선 순위가 높다는 것은 중요한 일을 할 가능성, 높은 순위의 스레드가 늦게 실행되면 심각한 문제 발생 가능 2) 낮은 순위의 스레드가 길어지면 더욱 더 심각한 문제 발생

우선순위 역전 사례

우선순위 역전 해결책

1) 우선순위 올림(priority ceiling)

스레드가 공유 자원을 소유하게 될 때, 스레드의 우선순위를 미리 정해진 높은 우선순위로 일시적으로 올림
선점되지 않고 빨리 실행되도록 유도

2) 우선순위 상속(priority inheritance)

낮은 순위의 스레드가 공유 자원을 가지고 있는 동안
높은 순위의 스레드가 공유 자원을 요청하면
공유 자원을 가진 스레드의 우선순위를 요청한 스레드보다 높게 설정하여 빨리 실행시킴

생산자 소비문제

응용프로그램에 존재하는 생산자 소비자 문제 사례

생산자 소비자 문제는 많은 응용프로그램에서 발생하는 전형적인 동기화 문제

생산자 소비자 문제의 정의

1) 생산자 소비자 문제란?

공유버퍼를 사이에 두고, 공유버퍼에 데이터를 공급하는 생산자들과
공유버퍼에서 데이터를 읽고 소비하는 소비자들이 공유 버퍼를 사용할 때
공유버퍼를 문제 없이 사용하도록 생산자와 소비자를 동기화시키는 문제
멀티스레딩 응용프로그램 작성 시 자주 발생

2) 생산자 소비자 문제를 코딩할 때 구체적으로 해결해야하는 3가지 문제

문제1
- 상호 배제 해결
  - 생산자들과 소비자들의 공유 버퍼에 대한 상호 배제
문제2
- 비어 있는 공유 버퍼 문제(비어 있는 공유버퍼를 소비자가 읽을 때)
문제3
- 꽉 찬 공유버퍼 문제(꽉 찬 공유버퍼에 생산자가 쓸 때)

비어 있는 공유버퍼 문제 해결

세마포 R 활용(읽기 가능한 버퍼 개수) : 버퍼가 비어 있는지 살피는 P/V연산으로 해결

꽉 찬 공유버퍼 문제 해결

세마포 W(쓰기 가능한 버퍼 개수) 활용 : 버퍼가 꽉 차 있을 때 처리하는 P/V연산으로 해결

생산자와 소비자 알고리즘

생산자-소비자로 구성된 응용프로그램 만들기

생산자 스레드
- 0~9까지 10개의 정수를, 랜덤한 시간 간격으로, 공유버퍼에 쓴다.
소비자 스레드
- 공유버퍼로부터 랜덤한 시간 간격으로, 10개의 정수를 읽어 출력한다.
공유버퍼
- 4개의 정수를 저장하는 원형 큐로 작성
  - 원형 큐는 배열로 작성
2개의 세마포 사용
- semWrite : 공유버퍼에 쓰기 가능한 공간(빈 공간)의 개수를 나타냄(초기값이 4인 counter 소유)
  - semRead : 공유버퍼에 읽기 가능한 공간(값이 들어 있는 공간)의 개수를 나타냄(초기값이 0인 counter 소유)
1개의 뮤텍스 사용
- pthread_mutex_t critical_section
  - 공유버퍼에서 읽는 코드와 쓰는 코드를 임계구역으로 설정
  - 뮤텍스를 이용하여 상호배제

#include 
#include 
#include 
#include 
#include 

#define N_COUNTER 4 //공유 버퍼에 저장할 정수 공간의 개수
#define MILLI 1000

void mywrite(int n);
int myread();

pthread_mutex_t critical_section;
sem_t semWrite, semRead; //POSIX 세마포
int queue[N_COUNTER]; //공유버퍼
int wptr; //queue[]에 저장할 다음 인덱스
int rptr; //queue[]에서 읽을 다음 인덱스

void* producer(void* arg){ //생산자 스레드 함수
    for(int i = 0; i<10; i++){
        mywrite(i); //정수 i를 공유버퍼에 저장
        printf("producer : wrote %d\n", i); 

        //m 밀리초 동안 잠을 잔다.
        int m = rand()%10; //0~9 사이의 랜덤한 정수
        usleep(MILLI*m*10); //m*10 밀리초동안 잠자기
    }
    return NULL;

}

void* consumer(void* arg){ //소비자 스레드 함수
    for(int i =0; i<10; i++){
        int n = myread(); //공유버퍼의 맨 앞에 있는 정수 읽어 리턴
        printf("\tconsumer : read %\n", i);


        //m 밀리초동안 잠을 잔다
        int m = rand()%10; //0~9 사이의 랜덤한 정수
        usleep(MILLI*m*10); //m*10 밀리초동안 잠자기
    }
    return NULL;
}

void mywrite(int n){ //정수 n을 queue[]에 삽입
    sem_wait(&semWrite); //queue[]에 쓸 수 있는지 요청

    pthread_mutex_lock(&critical_section); //뮤텍스 락 잠그기
    queue[wptr] = n; //버퍼에 정수 n을 삽입
    wptr++;
    wptr% = N_COUNTER;
    pthread_mutex_unlock(&critical_section); //뮤텍스 락 열기
}

int myread() { //queue[] 맨 앞에 있는 정수를 읽어 리턴
    sem_wait(&semRead); //queue[]에서 읽을 수 있는지 요청

    pthread_mutex_lock(&critical_section); //뮤텍스 락 잠그기
    int n = queue[rptr]; //버퍼에서 정수를 읽는다.
    rptr++;
    rptr %= N_COUNTER;
    pthread_mutex_unlock(&critical_section); // producer 스레드 깨우기

    sem_post(&semWrite);
    return n;
}

int main(){
    pthread_t t[2]; //스레드 구조체

    srand(time(NULL)); //난수 발생을 위한 seed 생성

    pthread_mutex_init(&critical_section, NULL); //뮤텍스 락 초기화

    //세마포 초기화 : N_COUNTER 개의 자원으로 초기화
    sem_init(&semWrite, 0, N_COUNTER); //가용버퍼의 개수를 N_COUNTER로 초기화
    sem_init(&semRead, 0, 0); //가용버퍼의 개수를 0으로 초기화

    //producer와 consumer 스레드 생성
    pthread_create(&t[0], NULL, producer, NULL); //생산자 스레드 생성
    pthread_create(&t[1], NULL, consumer, NULL); //소비자 스레드 생성 

    for(int i = 0; i<2; i++)
        pthread_join(t[i], NULL); //모든 스레드가 소멸할 때까지 대기

    sem_destroy(&semRead); //세마포 기능 소멸
    sem_destroy(&semWrite); //세마포 기능 소멸
    pthread_mutex_destroy(&critical_section); //뮤텍스 락 소멸
    return 0;
}

이 글이 문제가 된다면 삭제하겠습니다.

[운영체제] 5. CPU 스케줄링

Mon, 30 May 2022 04:44:35 GMT

CPU 스케줄링 개요

운영체제에서 일어나는 다양한 스케줄링

자원에 대한 스케줄링
- 자원에 대한 경쟁이 있는 곳에는 경쟁자 중 하나 선택
컴퓨터 시스템 여러 곳에서 발생

컴퓨터 시스템 내 다양한 스케줄링

작업 스케줄링
- 배치시스템에서 대기 중인 배치 작업 중 메모리에 적재할 작업 결정
CPU 스케줄링
- 프로세스/스레드 중에 하나를 선택해서 CPU 할당
- 오늘날 CPU 스케줄링은 스레드 중 하나를 선택하는 스레드 스케줄링
디스크 스케줄링
- 디스크 장치 내에서 디스크 입출력 요청 중 하나 선택
프린터 스케줄링
- 프린팅 작업 중 하나 선택하여 프린터 할당
  다중프로그래밍과 스케줄링
다중프로그래밍의 도입 목적
- CPU 유휴시간 줄이기 -> CPU 활용률 향상
- 프로세스가 I/O를 요청하면 다른 프로세스에게 CPU 할당
다중프로그래밍과 함께 2가지 스케줄링 도입

1) 작업 스케줄링

디스크 장치로부터 메모리에 올릴 작업 선택
처음에 혹은 프로세스가 종료할 때마다

2) CPU 스케줄링

메모리에 적재된 작업 중 CPU에 실행시킬 프로세스 선택

CPU burst 와 I/O burst

프로그램의 일반적 실행 특성
- CPU 연산 작업과 화면 출력, 키보드, 입력, 파일 입출력 등 I/O 작업 섞여 있음
CPU burst
- 프로그램 실행 중 CPU 연산이 연속적으로 실행되는 상황
I/O burst
- 프로그램 실행 중 I/O 장치의 입출력이 이루어지는 상황
  CPU 스케줄링의 정의와 목표
프로그램의 실행의 특징
- CPU burst -> I/O burst -> CPU burst -> I/O burst ..
- 연산작업 - 입출력작업 - 연산작업 - 입출력작업
CPU 스케줄링 : 실행 준비 상태의 스레드 중 하나를 선택하는 과정
CPU 스케줄링의 기준
- 컴퓨터 시스템들은 기본 목표 외에 서로 다른 스케줄링 목표를 가질 수 있음
스케줄링 알고리즘의 다양한 목표와 평가 기준★ 1) CPU 활용률 - 전체 시간 중 CPU의 사용시간 비율 (운영체제 입장) 2) 처리율 - 단위 시간 당 처리하는 프로세스의 개수 (운영체제 입장) 3) 공평성 - CPU를 스레드들에게 공평하게 배분 (사용자 입장)
- 시분할로 스케줄링
- 무한정 대기하는 기아 스레드가 생기지 않도록 스케줄링 4) 응답 시간 - 대화식 사용자의 경우, 명령에 응답하는데 걸리는 시간 (사용자 입장) 5) 대기 시간 - 스레드가 준비 큐에서 머무르는 시간 (운영체제와 사용자 입장) 6) 소요 시간 - 프로세스(스레드)가 컴퓨터 시스템에 도착한 후 완료될 때까지 걸린 시간 (사용자 입장) - 배치 처리 시스템에서 주된 스케줄링의 기준 7) 시스템 정책 우선 - 컴퓨터 시스템의 특별한 목적을 달성하기 위한 스케줄링 (운영체제 입장)
- 예 : 실시간 시스템에서는 스레드가 완료 시한 내에 이루어지도록 하는 정책
- 예 : 급여 시스템에서는 안전을 관리하는 스레드 우선 정책 등 8) 자원 활용률

타임 슬라이스

대부분 운영체제에서 하나의 스레드가 너무 오래 CPU를 사용하도록 허락하지 않음
타임 슬라이스와 스케줄링
- 스케줄된 스레드에게 한 번 할당하는 CPU 시간
- 커널이 스케줄을 단행하는 주기 시간
타이머 인터럽트의 도움을 받아 타임 슬라이스 단위로 CPU 스케줄링
현재 실행 중인 스레드 강제 중단, 준비 리스트에 삽입
- 타임 퀀텀, 타임 슬롯이라고도 함
  CPU 스케줄링 기본
  
  CPU 스케줄링이 실행되는 4가지 상황★
  1) 스레드가 시스템 호출 끝에 I/O를 요청하여 블록될 때
스레드를 블록 상태로 만들고 스케줄링
CPU의 활용률 향상 목적

2) 스레드가 자발적으로 CPU를 반환할 때

yield() 시스템 호출 등을 통해 스레드가 자발적으로 CPU 반환
커널은 현재 스레드를 준비 리스트에 넣고, 새로운 스레드 선택
CPU의 자발적 양보

3) 스레드의 타임슬라이스가 소진되어 타이머 인터럽트 발생

균등한 CPU 분배 목적

4) 더 높은 순위의 스레드가 요청한 입출력 작업 완료, 인터럽트 발생

현재 스레드를 강제 중단시켜 준비 리스트에 넣고
높은 순위의 스레드를 깨워 스케줄링
우선순위를 지키기 위한 목적

CPU 스케줄링과 디스패치

CPU 스케줄링 코드의 위치와 실행 시점

스케줄링을 담당하는 커널 스레드나 프로세스는 없음
스케줄링 코드는 커널 내에 코드 형태로 위치
- 스케줄링 코드는 커널 코드의 일부
  - 별도로 실행되는 프로세스나 스레드 형태가 아님
  - 커널은 마치 응용프로그램을 컴파일(빌드) 하여 완성한 바이너리 모듈 같음, 메모리에 그대로 적재되는 한 덩어리의 바이너리
스케줄링 코드가 실행되는 시점
- 시스템 호출이나 인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행
디스패쳐 코드 실행
디스패쳐 코드 : 컨택스트 스위칭을 실행하는 커널 코드
- 스케줄러에 의해 선택된 스레드를 CPU가 실행하도록 하는 작업
- 커널 모드에서 사용자 모드로 전환
- 새로 선택된 스레드가 이전에 중단된 곳에서 실행하도록 점프

** 스케줄러와 디스패쳐 모두 실행 시간이 짧도록 작성

선점 스케줄링과 비선점 스케줄링

실행 중인 스레드의 강제 중단 여부에 따른 CPU 스케줄링 타입

1) 비선점 스케줄링

현재 실행 중인 스레드를 강제로 중단시키지 않는 타입
- 일단 스레드가 CPU를 할당받아 실행을 시작하면, 완료되거나 CPU를 더 이상 사용할 수 없는 상황이 될 때까지 스레드 강제 중단 시키지 않고 스케줄링도 하지 않는 방식
스케줄링 시점
- CPU를 더 이상 사용할 수 없게 된 경우 : I/O 로 인한 블록 상태, sleep 등
- 자발적으로 CPU를 양보할 때
- 실행 중 종료할 때

2) 선점 스케줄링

현재 실행 중인 스레드를 강제 중단 시키고 다른 스레드 선택, CPU 할당
스케줄링 시점
- 타임슬라이스가 소진되어 타이머 인터럽트가 발생될 때
- 인터럽트나 시스템 호출 종료 시점에서, 더 높은 순위의 스레드가 준비 상태일 때

비선점 스케줄링
- 이미 할당된 자원을 다른 프로세스가 강탈할 수 없음
- 응답시간의 예측이 편하며, 일괄처리 방식에 적합
- 단점으로는 덜 중요한 작업이 자원을 할당받으면 중요 작업이 와도 먼저 처리될 수 없음
- FCFS(FIFO구조 알고리즘), SJF, HRN, 우선순위, 기한부
선점 스케줄링
- 우선순위가 높은 프로세스를 빠르게 처리할 수 있음
- 어떤 프로세스가 자원을 사용하고 있을 때 우선순위가 더 높은 프로세스가 올 경우 자원을 강탈함
- 빠른 응답 시간을 요구하는 시스템에서 사용
- 오버헤드가 크다
- Round Robin, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백큐

기아와 에이징

1) 기아

스레드가 스케줄링에서 선택되지 못한 채 오랫동안 준비리스트에 있는 상황
사례
- 우선순위를 기반으로 하는 시스템에서 더 높은 순위의 스레드가 계속 시스템에 들어오는 경우
  - 짧은 스레드를 우선 실행시키는 시스템에서, 자신보다 짧은 스레드가 계속 도착하는 경우
    - 스케줄링 알고리즘 설계 시 기아발생을 면밀히 평가
  - 기아가 발생하지 않도록 설계하는 것이 바람직함

2) 에이징

기아의 해결책
스레드가 준비리스트에 머무는 시간에 비례하여 스케줄링 순위를 높이는 기법
- 오래 기다릴 수는 있지만 언젠가는 가장 높은 순위에 도달하는 것을 보장
  CPU 스케줄링 알고리즘
  
  다양한 CPU 스케줄링 알고리즘
  1) FCFS(First come First served) - 비선점 스케줄링
도착한 순서대로 스레드를 준비 큐에 넣고 도착한 순서대로 처리

2) Shortest Job First - 비선점 스케줄링

가장 짧은 스레드 우선 처리

3) Shortest remaining time first - 선점 스케줄링

남은 시간이 짧은 스레드가 준비 큐에 들어오면 이를 우선 처리

4) Round - robin - preemptive

스레드들을 돌아가면서 할당된 시간(타임슬라이스)만큼 실행

5) Priority Scheduling - 선점/비선점 스케줄링 둘 다 구현 가능

우선순위를 기반으로 하는 스케줄링. 가장 높은 순위의 스레드 먼저 실행

6) Multilevel queue scheduling - 선점/비선점 스케줄링 둘 다 구현 가능

스레드와 큐 모두 n개의 우선순위 레벨로 할당, 스레드는 자신의 레벨과 동일한 큐에 삽입
높은 순위의 큐에서 스레드 스케줄링, 높은 순위의 큐가 빌 때 아래 순위의 큐에서 스케줄링
스레드는 다른 큐로 이동하지 못함
예 : Background process, Foreground process

7) Multilevel feedback queue scheduling - 선점/비선점 스케줄링 둘 다 구현 가능

큐만 n개의 우선순위 레벨을 둠. 스레드는 레벨이 없이 동일한 우선 순위
스레드는 제일 높은 순위의 큐에 진입하고 큐타임슬라이스가 다하면 아래 레벨의 큐로 이동
낮은 레벨의 큐에 오래 있으면 높은 레벨의 큐로 이동

[참고]

여러 개의 큐

레디 큐를 여러 개로 분할
foreground
background
각 큐는 독립적인 스케줄링 알고리즘을 가짐
foreground - RR
background - FCFS
큐에 대한 스케줄링이 필요
포그라운드 큐 : 사용자와 소통 중심 백그라운드 큐 : 배치 프로그램

FCFS

선입선처리 알고리즘
- 먼저 도착한 스레드 먼저 스케줄링
스케줄링 파라미터 : 스레드 별 도착 시간
스케줄링 타입 : 비선점 스케줄링
스레드 우선 순위 : 없음
기아 : 발생하지 않음
- 스레드가 오류로 인해 무한 루프를 실행한다면 뒤 스레드의 기아 발생
성능 이슈
- 처리율 : 낮음
  - 호위 효과 발생 : 긴 스레드가 CPU를 오래 사용하면, 늦게 도착하면 짧은 소레드는 오래 대기

SJF

최단작업 우선 스케줄링 알고리즘
- 예상 실행시간이 가장 짧은 스레드 선택
  - 스레드가 도착할 때, 예상 실행시간이 짧은 순으로 큐 삽입, 큐의 맨 앞에 있는 스레드 선택
스케줄링 파라미터 : 스레드 별 예상 실행 시간
스케줄링 타입 : 비선점 스케줄링
스레드 우선 순위 : 없음
기아 : 발생 가능
- 지속적으로 짧은 스레드가 도착하면, 긴 스레드는 언제 실행 기회를 얻을지 예측할 수 없음
성능 이슈
- 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
문제점
- 실행 시간의 예측이 불가능하므로 현실에서는 거의 사용되지 않음

SRTF

최소 잔여 시간 우선 스케줄링 알고리즘
남은 실행 시간이 가장 짧은 스레드 선택
SJF의 선점 스케줄링 버전
- 실행시간이 짧은 순으로 스레드들을 큐에 삽입, 한 스레드가 끝나거나 실행시간이 더 짧은 스레드가 도착할 때, 가장 짧은 스레드 선택
  - 큐의 맨 앞에 있는 스레드 선택
스케줄링 파라미터 : 스레드 별 예상 실행 시간과 남은 실행 시간 값
- 이 시간을 아는 것은 불가능. 비현실적
스케줄링 타입 : 선점 스케줄링
스레드 우선 순위 : 없음
기아 : 발생 가능
- 지속적으로 짧은 스레드가 도착하는 경우 긴 스레드는 언제 실행 기회를 얻을 수 있을지 예상할 수 없음
성능 이슈
- 실행 시간이 짧은 프로세스가 먼저 실행되므로 평균 대기 시간 최소화
문제점
- 실행 시간 예측이 불가능하므로 현실에서는 거의 사용되지 않음

RR

스레드들에게 공평한 실행 기회를 주기 위해 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택하는 알고리즘
도착하는 순서대로 스레드들을 큐에 삽입
타임 슬라이스가 지나면 큐 끝으로 이동
스케줄링 파라미터 : 타임 슬라이스
스케줄링 타입 : 선점 스케줄링
스레드 우선 순위 : 없음
기아 : 없음
- 스레드의 우선순위가 없고, 타임 슬라이스가 정해져 있어, 일정 시간 후에 스레드는 반드시 실행
성능 이슈
- 공평하고, 기아현상 없고, 구현이 쉬움
  - 잦은 스케줄링으로 전체 스케줄링 오버헤드가 큼. 특히 타임슬라이스가 작을 때 더욱 큼
  - 균형된 처리율 : 타임슬라이스가 크면 FCFS에 가까움, 작으면 SJF/SRTF 에 가까움
- 늦게 도착한 짧은 프로세는 FCFS보다 빨리 완료되고, 긴 프로세스는 SJF보다 빨리 완료됨

Priority 스케줄링

우선순위에 따라 스레드들 실행시키기 위한 목적인 알고리즘
가장 높은 순위의 스레드 선택
- 현재 스레드가 종료되거나 더 높은 순위의 스레드가 도착할 때, 가장 높은 순위의 스레드 선택
  - 모든 스레드에 고정 우선 순위 할당, 종료 때까지 바뀌지 않음
  - 도착하는 스레드는 우선순위 순으로 큐에 삽입
스케줄링 파라미터 : 선점/비선점 스케줄링
- 선점 스케줄링 : 더 높은 스레드가 도착할 때 현재 스레드 강제 중단하고 스케줄링
  - 비선점 스케줄링 : 현재 실행 중인 스레드가 종료될 때 비로소 스케줄링
스레드 우선 순위 : 있음
기아 : 발생 가능
- 지속적으로 높은 순위의 스레드가 도착하는 경우 언제 실행 기회를 얻을 수 있을지 예상할 수 없음
  - 큐 대기 시간에 비례하여 일시적으로 우선순위를 높이는 에이징 방법으로 해결 가능
성능 이슈
- 높은 우선순위의 스레드일 수록 대기 혹은 응답시간 짧음
특징
- 스레드 별 고정 우선 순위를 가지는 실시간 시스템에서 사용

MLQ

설계 의도 : 스레드들을 n개의 우선순위 레벨로 구분, 레벨이 높은 스레드들을 우선적으로 처리하는 목적
알고리즘
- 고정된 n 개의 큐 사용, 각 큐에 고정 우선순위 할당
  - 각 큐는 나름대로의 기법으로 스케줄링
  - 스레드는 도착 시 우선 순위에 따라 해당 레벨 큐에 삽입. 다른 큐로 이동할 수 없음
  - 가장 높은 순위의 큐가 빌 때, 그 다음 순위의 큐에서 스케줄링
스케줄링 파라미터 : 스레드의 고정 우선순위
스케줄링 타입 : 비선점/선점 모두 가능
- 비선점 스케줄링 : 현재 실행중인 스레드가 종료할 때 비로소 스케줄링
  - 선점 스케줄링 : 높은 레벨의 큐에 스레드가 도착하면 중단하고 높은 순위의 레벨 큐에서 스케줄링
기아 : 발생 가능
- 지속적으로 높은 순위의 스레드가 도착하는 경우 언제 실행 기회를 얻을 수 있을지 예상할 수 없음
성능 이슈와 활용 사례
- 스레드의 고정 순위를 가진 시스템에서 활용
  - 예 : 전체 스레드를 백그라운드 스레드와 포그라운드 스레드의 2개의 그룹을 구성
  - 예 : 시스템 스레드, 대화식 스레드, 배치 스레드 등 3개의 레벨로 나누고 시스템 스레드를 우선적으로 스케줄링
  - 예 : 대학에서 교수, 교직원 , 대학원생, 학부생 등 사용자를 4개의 레벨로 나누고, 사용자에 따라 실행시킨 스레드 레벨로 스케줄링

[참고]

MLF 스케줄링
FIFO + RR 스케줄링
작업을 전면 작업(대화형, foreground task) 과 후면 작업(일괄처리형, background task) 로 분류한다면 두 유형의 반응 시간이 다르므로 서로 다르게 스케줄링 해야한다.
전면 작업은 후면 작업에 비해 높은 우선순위를 갖는 경우가 많다. 예를 들어, 쇼핑몰에서 쇼핑은 빠르게 백그라운드에서 다운로드는 느리게

MLFQ

설계 의도
- 1962년에 개발된 알고리즘
  - 기아를 없애기 위해 여러 레벨의 큐 사이에 스레드 이동 가능하도록 설계
  - 짧은 스레드와 I/O가 많은 스레드, 대화식 스레드의 우선처리. 스레드 평균대기시간 줄임
n개의 레벨 큐
- n개의 고정 큐. 큐마다 서로 다른 스케줄링 알고리즘
  - 큐마다 스레드가 머무를 수 있는 큐타임 슬라이스가 있음. 낮은 레벨의 큐일 수록 더 긴 타임 슬라이스
  - I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성이 높음
알고리즘
- 스레드는 도착 시 최상위 레벨의 큐에 삽입
  - 가장 높은 레벨의 큐에서 스레드 선택. 비어 있으면 그 아래의 큐에서 스레드 선택
  - 스레드의 CPU-burst가 큐 타임 슬라이스를 초과하면 강제로 아래 큐로 이동 시킴
  - 스레드가 자발적으로 중단한 경우, 현재 큐의 끝에 삽입
  - 스레드가 I/O로 실행이 중단된 겨웅, I/O가 끝나면 동일한 레벨 큐 끝에 삽입
  - 큐에 있는 시간이 오래되면 기아를 막기 위해 하나의 위 레벨 큐로 이동
  - 최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄. 스레드들은 다른 큐로 이동 못함
스케줄링 파라미터 : 각 큐의 큐 시간 할당량
스케줄링 타입 : 선점 스케줄링
스레드 우선 순위 : 없음
기아 : 발생하지 않음. 큐에 대기하는 시간이 오래되면 더 높은 레벨의 큐로 이동시킴(에이징 기법)
성능 이슈
- 짧거나 입출력이 빈번한 스레드, 혹은 대화식 스레드를 높은 레벨의 큐에서 빨리 실햄 -> CPU 활용률이 높음

멀티코어 CPU에서의 스케줄링

멀티코어 시스템의 구조

멀티코어 시스템에서의 멀티스레딩

멀티코어 시스템에서의 CPU 스케줄링

멀티코어 시스템에서 싱글코어 CPU의 스케줄링을 사용할 때 문제점

1) 컨텍스트 스위칭 오버헤드 증가문제

이전에 실행된 적이 없는 코어에 스레드가 배치될 때
캐시에 새로운 스레드의 코드와 데이터로 채워지는 긴 경과 시간
해결
- CPU 친화성 (CPU affinity) 적용
  - 스케드를 동일한 코어에서만 실행하도록 스케줄링
  - 코어 친화성 (Core affinity), CPU 피닝(pinning), 캐시 친화성(cache affinity) 라고도 부름

2) 코어별 부하 불균형 문제

스레드를 무작위로 코어에 할당하면, 코어마다 처리할 스레드 수의 불균형 발생
해결
- 부하 불균등 기법으로 해결
  - 푸시 마이그레이션 : 감시 스레드가 짧거나 빈 큐를 가진 코어에 다른 큐의 스레드를 옮겨놓는 기법
  - 풀 마이그레이션 : 코어가 처리할 스레드가 없게 되면, 다른 코어의 스레드 큐에서 자신이 큐에 가져와 실행시키는 기법

** 여러가지 스케줄링 기법 Youtube로 찾아보고 더 자세히 이해하기

이 글이 문제가 된다면 삭제하겠습니다.

[운영체제] 4. 스레드와 멀티태스킹

Mon, 30 May 2022 04:43:19 GMT

프로세스의 문제점

1) 프로세스 생성의 큰 오버헤드

프로세스 생성
- 프로세스를 위한 메모리 할당 - 부모프로세스로부터 복사
- PCB 생성, 매핑 테이블(페이지 테이블) 생성 등

2) 프로세스 컨텍스트 스위칭의 큰 오버헤드

컨텍스트 스위칭
- CPU가 참고할 매핑 테이블(페이지 테이블) 전화네 따른 지연 시간 등
- CPU 레지스터들을 프로세스 컨텍스트에 저장, 새 프로세스 컨텍스트를 CPU로 옮기는 시간
- CPU 캐시에 새로운 프로세스의 코드와 데이터가 채워지는데 걸리는 시간 등

3) 프로세스 사이 통신의 어려움

프로세스들은 완전한 독립적인 주소 공간을 가지고 있음
- 프로세스가 다른 프로세스의 메모리에 접근 불가
프로세스 사이의 통신을 위한 제3의 방법 필요
- 커널 메모리나 커널에 의해 마련된 메모리 공간을 이용하여 데이터 송수신 (신호, 소켓, 메시지 큐, 세마포, 공유메모리, 메모리맵 파일 등)
- 이 방법들은 코딩도 어렵고, 느린 실행 속도, 운영체제 호환성 부족
  스레드의 개념
  
  스레드의 출현 목적
- 프로세스를 사용하는 문제점 해결을 위해 고안
프로세스보다 더 작은 실행 단위 필요
- 실행 단위란 운영체제의 스케줄링 단위
- 스레드를 가벼운 프로세스(light- weight process, LWP)라고 부름
프로세스의 생성 및 소멸에 따른 오버헤드 감소
빠른 컨텍스트 스위칭
프로세스의 복잡한 통신 방법, 느린 실행 속도, 코딩의 어려움 해소

프로세스와 스레드 관리

멀티스레딩과 concurrency, parallelism

concurrency(동시성)

1개의 CPU에서 2개 이상의 스레드가 동시에 실행 중인 상태
- 입출력 때문에 중단하면 다른 스레드 실행
- 타임 슬라이스 단위로 CPU를 사용하도록 번갈아 스레드 실행 parallelism
2개 이상의 스레드가 다른 CPU에서 같은 시간에 동시에 실행 (멀티코어)

스레드 주소공간과 컨텍스트

스레드 주소공간

스레드 주소 공간 -스레드가 생성되고 실행되는 동안 접근 가능한 메모리 영역

스레드 주소 공간은 프로세스의 주소 공간 내에 형성
스레드 주소 공간을 구성하는 요소들
스레드 사적 공간
스레드 코드
- 스레드 로컬 스토리지 (TLS, Threead local storage)
스레드 사이의 공유 공간 (프로세스 내에 있음)
- 프로세스의 코드
- 프로세스의 데이터 공간(로컬 스토리지 제외)
- 프로세스의 힙 영역

1) 스레드 코드 영역

스레드가 실행할 작업의 함수
- 프로세스의 코드 영역 사용
스레드는 프로세스의 코드 영역에 있는 다른 모든 함수 호출 가능

2) 스레드 데이터 영역

스레드가 사용할 수 있는 데이터 공간
- 프로세스의 데이터 영역으로 사용
2개의 공간으로 구분
- 개별 스레드 전용 전역 변수 공간 (스레드 로컬 스토리지) - static __thread 와 같은 특별한 키워드로 선언, 컴파일러에 의해 결정
- 프로세스에 선언된 모든 전역 변수들은 모든 스레드에 의해 공유
- 스레드 사이의 통신 공간으로 유용하게 사용

3) 스레드 힙

모든 스레드가 동적 할당 받는 공간, 프로세스의 힙 공간 사용
스레드에서 malloc()를 호출하면 프로세스의 힙공간에서 할당받음

4) 스레드 스택

스레드가 생성될 때마다 프로세스의 사용자 스택의 일부분 할당
스레드가 시스템 호출로 커널에 진입할 때, 커널 내에 스레드를 위한 스택 생성 (커널 스택이라고 부름)

스레드 상태
스레드 일생
- 생성, 실행, 중단, 실행, 소멸의 여러 상태를 거치는 스레드 인생
- 스레드 상태는 TCB에 저장
- 스레드 상태 1) 준비 상태(Ready) - 스레드가 스케줄 되기를 기다리는 상태 2) 실행 상태(Running) - 스레드가 CPU에 의해 실행 중인 상태 3) 대기 상태(Blocked) - 스레드가 입출력을 요청하거나 sleep()과 같은 시스템 호출로 인해 커널에 의해 중단된 상태 4) 종료 상태(Terminated) - 스레드가 종료된 상태

스레드 운용

응용프로그램이 스레드에 대해 할 수 있는 운용의 종류

1) 스레드 생성

스레드는 스레드를 생성하는 시스템 호출이나 라이브러리 함수를 호출하여 다른 스레드 생성 가능
프로세스가 생성되면 자동으로 main 스레드 생성

2) 스레드 종료

프로세스 종료와 스레드 종료 구분 필요
프로세스 종료

프로세스에 속한 어떤 스레드라도 exit() 시스템 호출을 부르면 프로세스 종료( 모든 스레드 종료 ) 메인 스레드의 종료(C프로그램에서 main() 함수 종료) - 모든 스레드도 함께 종료 모든 스레드가 종료하면 프로세스 종료 -> 스레드 종료

pthread_exit() 과 같이 스레드만 종료하는 함수 호출 시 해당 스레드만 종료 main() 함수에서 pthread_exit()을 부르면 역시 main 스레드만 종료

스레드 조인
스레드가 다른 스레드가 종료할 때까지 대기
- 주로 부모 스레드가 자식 스레드의 종료 대기
스레드 양보
스레드가 자발적으로 yield() 와 같은 함수 호출을 통해 자신의 실행을 중단하고 다른 스레드를 스케줄하도록 지시

스레드 컨텍스트

1) 스레드 컨텍스트

스레드의 실행중인 상태 정보
- CPU 레지스터들의 값
- PC, SP, 데이터/상태 레지스터 등
- TCB에 저장됨

2) PC 레지스터

실행 중인 코드 주소

2) SP 레지스터

실행 중인 함수의 스택 주소

3) 상태 레지스터

현재 CPU의 상태 정보

4) CPU에는 수십 개의 레지스터

이들만 저장해두었다가 필요할 때 CPU에 복귀하면
이전에 실행하던 상태로 돌아갈 수 있음

스레드 제어블록

스레드 제어블록, TCB :스레드를 실행 단위로 다루기 위해 스레드에 관한 정보를 담은 구조체

스레드 엔터디, 스케줄링 엔터티 라고도 불림
커널 영역에 만들어지고, 커널에 의해 관리
- 스레드가 생성될 때 커널에 의해 만들어짐
- 스레드가 소멸되면 함께 사라짐

스레드와 TCB, 그리고 PCB의 관계

프로세스 : 스레드들이 생기고 활동하는 자원의 컨테이너
TCB : 링크드 리스트로 연결
준비리스트와 블록리스트
1) 준비리스트
준비 상태의 스레드들의 TCB를 연결하여 관리하는 링크드 리스트
스레드 스케줄링은 준비 리스트의 TCB 중에서 하나 선택

2) 블록리스트

블록 상태의 스레드들의 TCB를 연결하여 관리하는 링크드 리스트
스레드 컨텍스트 스위칭

스레드 컨텍스트 스위칭
스레드 컨텍스트 스위칭
현재 실행중인 스레드를 중단시키고, 다른 스레드에게 CPU 할당
- 스레드 스위칭이라고도 부름
- 현재 CPU 컨텍스트를 TCB에 저장하고, 다른 TCB에 저장된 컨텍스트를 CPU에 적재
  스레드 스위칭이 발생하는 4가지 경우
  스레드 스위칭이 발생하는 4가지 경우

스레드가 자발적으로 다른 스레드에게 양보

yield() 등의 시스템 호출(혹은 라이브러리 호출) 을 통해

스레드가 시스템 호출을 실행하여 블록되는 경우

read(), sleep(), wait() 등 I/O 가 발생하거나 대기할 수 밖에 없는 경우

스레드의 타임 슬라이스를 소진한 경우

타이머 인터럽트에 의해 체크

I/O 장치로부터 인터럽트가 발생한 경우

현재 실행 중인 스레드보다 더 높은 우선순위의 스레드가 I/O 작업을 끝낸 경우 등

** 상황에 따라 운영체제에 따라 이들 4가지 경우에도 스레드 스위칭이 일어날 수도 있고 아닐 수도 있음

스레드 스위칭이 발생하는 위치

스레드 스위칭이 이루어지는 위치는 2가지 1) 프로세스가 시스템 호출을 하여, 커널이 시스템 호출을 처리하는 과정에서 2) 인터럽트가 발생하여 인터럽트 서비스 루틴이 실행되는 도중 커널 코드에서
스레드 스위칭 과정
1) CPU 레지스터 저장 및 복귀
현재 실행 중인 스레드 A의 컨텍스트를 TCB-A에 저장
TCB-B 에 저장된 스레드 B의 컨텍스트를 CPU에 적재
- CPU는 스레드가 B가 이전에 중단된 위치에서 실행 재개 가능
- SP 레지스터를 복귀함으로서 자신의 이전 스택을 되찾게 됨

** 스택에는 이전 중단될 때 실행하던 함수의 매개변수나 지역변수들이 그대로 저장되어 있음

2) 커널 정보 수정

TCB-A와 TCB-B에 스레드 상태 정보와 CPU 사용 시간 등 수정
TCB-A를 준비 리스트나 블록 리스트로 옮김
TCB -B를 준비 리스트에서 분리

컨텍스트 스위칭 오버헤드
컨텍스트 스위칭에는 어떤 부담(오버헤드)이 있는가?
- 컨텍스트 스위칭은 모두 CPU작업 -> CPU 시간 소모
- 컨텍스트 스위칭의 시간이 길어나, 잦은 경우 컴퓨터 처리율 저하
구체적인 컨텍스트 스위칭 오버헤드
- 동일한 프로세스의 다른 스레드로 스위칭되는 경우
컨텍스트 저장 및 복귀
- 현재 CPU의 컨텍스트(PC, SP, 레지스터) TCB에 저장
- TCB로부터 스레드 컨텍스트를 CPU에 복귀
- TCB 리스트 조작
- 캐시 플러시와 채우기 시간
다른 프로세스의 스레드로 스위칭하는 경우
- 다른 프로세스로 교체되면, CPU가 실행하는 주소 공간이 바뀌는 큰 변화로 인한 추가적인 오버헤드 발생
- 추가적인 메모리 오버헤드
시스템 내에 현재 실행 중인 프로세스의 매핑 테이블을 새로운 프로세스의 매핑 테이블로 교체
- 추가적인 캐시 오버헤드

** 프로세스가 바뀌기 때문에, CPU 캐시에 담긴 코드와 데이터 무력화 새 프로세스의 스레드가 실행을 시작하면 CPU 캐시 미스 발생, 캐시가 채워지는데 상당한 시간 소요

커널 레벨 스레드와 사용자 레벨 스레드

스레드의 스케줄링 주체에 따라 2종류의 스레드로 구분 1) 커널 레벨 스레드 : 커널에 의해 스케줄링되는 스레드 2) 사용자 레벨 스레드 : 스레드 라이브러리에 의해 스케줄링되는 스레드

1) 커널레벨 스레드

응용프로그램이 시스템 호출을 통해 커널 레벨 스레드 생성
커널이 스레드에 대한 정보(TCB)를 커널 공간에 생성하고 소유
커널에 의해 스케줄
스레드 주소 공간(스레드 코드와 데이터) : 사용자 공간에 존재
main 스레드는 커널 스레드
- 응용프로그램이 적재되어 프로세스가 생성될 때 자동으로 커널은 main 스레드 생성

2) 사용자레벨 스레드

응용프로그램이 라이브러리 함수를 호출하여 사용자 레벨 스레드 생성
스레드 라이브러리가 스레드 정보(U-TCB)를 사용자 공간에 생성하고 소유
- 스레드 라이브러리는 사용자 공간에 존재
- 커널은 사용자 레벨 스레드의 존재에 대해 알 수 없음
스레드 라이브러리에 의해 스케줄
스레드 주소 공간(스레드 코드와 데이터) : 사용자 공간에 존재

3) 순수 커널레벨 스레드

부팅 때부터 커널의 기능을 돕기 위해 만들어진 스레드
커널 코드를 실행하는 커널 스레드
스레드의 주소 공간은 모두 커널 공간에 형성
커널 모드에서 작동, 사용자 모드에서 실행되는 일은 없음

1) 2개의 순수 커널 레벨 스레드

TCB1, TCB2
이들 스레드의 주소 공간은 커널에 있음.

2) 2개의 커널 레벨 스레드

프로세스 당 하나의 커널 레벨 스레드 (main 스레드) 자동 생성
TCB3
- 커널은 단일 스레드 프로세스1을 적재할 때 자동으로 main 스레드 TCB3 생성
- 커널이 프로세스를 실행시키기 위함
TCB4
- 커널은 멀티스레드 프로세스2를 적재할 때 자동으로 main 스레드 TCB4 생성
- 커널이 프로세스를 실행시키기 위함
TCB3와 TCB4의 스레드 주소 공간은 모두 사용자 공간에 있음

3) 3개의 사용자 레벨 스레드

멀티스레드 프로세스2의 main() 함수가 라이브러리 함수를 호출하여 자신을 사용자 레벨 스레드로 등록
- U-TCB1 생성
멀티스레드 프로세스2의 main() 함수가 라이브러리 함수를 호출하여 2개의 사용자 레벨 스레드 추가 생성
- U-TCB2, U-TCB3 생성

4) 스레드 스케줄링

커널에 의한 스케줄
- 코어1 : TCB2 실행 (TCB2가 가리키는 커널 스레드 코드 2 실행)
- 코어2 : TCB4 실행 (TCB4가 가리키는 프로세스 내의 코드 실행)

** 처음에는 main() 함수에서 실행되지만, 어떤 함수인지 알 수 없음 커널은 프로세스 내에 하나의 스레드만 있다고 생각함

5) 멀티스레드 프로세스2에서의 사용자 스레드 스케줄링

스레드 라이브러리가 3개의 사용자 스레드 스케줄
예 : main() 함수가 스레드 라이브러리의 yield() 함수를 호출하면 이 함수는 현재 대기중인 U-TCB2, U-TCB3 중에서 하나를 선택한다. 만약 U-TCB3가 선택되었다면, U-TCB1에 현재 실행 주소 등을 저장해두고, U-TCB3에 저장된 실행 시작 주소(스레드 코드3)로 점프하여 실행 시작 -> U- TCB3이 스케줄 되었음

항목	사용자 레벨 스레드	커널 레벨 스레드
정의	스레드 라이브러리에 의해 스케줄되는 스레드	커널에 의해 스케줄되는 스레드
구현	스레드 라이브러리에 의해 구현되고 다루어짐	커널에 의해 구현. 커널 API(시스템 호출) 필요
스레드 스위칭	사용자 모드에서 스레드 라이브러리에 의해 실행	커널 모드에서 커널에 의해 실행
컨텍스트 스위칭 속도	커널 레벨 스레드보다 100배 이상 빠르다고 알려짐	커널 내에서 상당 시간 지연
멀티스레드 응용프로그램	스레드 라이브러리를 이용하여 작성하기 쉽고, 스레드 생성 속도 빠름	시스템 호출을 이용하여 스레드 생성. 스레드 생성 속도 느림
이식성	운영체제 상관없이 작성 가능하므로 높은 이식성 스레드를 지원하지 않는 운영체제에서도 가능	스레드를 생성하고 다루는 시스템 호출이 운영체제마다 다르므로 이식성이 낮음
병렬성	멀티 CPU 컴퓨터나 멀티 코어 CPU에서 멀티스레드의 병령처리 안 됨	높은 병렬성. 커널 레벨 스레드들이 서로 다른 CPU나 서로 다른 코어에서 병렬 실행 가능
병렬성의 종류	concurrency	parallelism
블록킹	하나의 사용자 레벨 스레드가 시스템 호출 도중 입출력 등으로 인해 중단되면 프로세스의 모든 사용자 레벨 스레드가 중단됨	하나의 커널 레벨 스레드가 시시템 호출 도중 입출력 등으로 인해 중단되어도 해당 스레드만 중단
커널 부담	없음	커널 코드의 실행 시간 증가. 시스템 전체에 부담
스레드 동기화	스레드 라이브러리에 의해 수행	시스템 호출을 통해 커널에 의해 수행
관리의 효율성	커널 부담 없음	커널 부담
최근 경향	멀티 코어 CPU에 적합하지 않아 줄고 있는 추세	멀티 코어 CPU에서 높은 병렬성을 얻을 수 있어 많이 사용하는 추세

멀티스레드 구현

응용프로그램에서 작성한 스레드가 시스템에서 실행되도록 구현하는 방법
- 사용자가 만든 스레드가 시스템에서 스케줄 되고 실행되도록 구현하는 방법
- 스레드 라이브러리와 커널의 시스템 호출의 상호 협력 필요
3가지 방법 1) N:1 매핑(N개의 사용자 레벨 스레드를 1개의 커널 레벨 스레드로 매핑) 2) 1:1 매핑 (1개의 사용자 레벨 스레드를 1개의 커널 레벨 스레드로 매핑) 3) N:M 매핑 (N개의 사용자 레벨 스레드를 M개의 커널 레벨 스레드로 매핑)

N : 1 매핑
운영체제가 모든 프로세스를 단일 스레드 프로세스로 다룸
프로세스 당 1개의 커널 레벨 스레드(TCB) 생성
- 스케줄 가능한 엔터티라고 부름
- 프로세스의 모든 사용자 레벨 스레드가 1개의 커널 레벨 스레드에 매핑
사용자 레벨 스레드는 스레드 라이브러리에 의해 스위치 된다.

매핑의 뜻

사용자 레벨 스레드는 해당 커널 레벨 스레드가 스케줄되어야 실행 가능하도록 묶여 있음

N:1 매핑의 장단점 1) 장점
단일 코어 CPU에서 멀티스레드 응용프로그램의 실행속도가 전반적으로 빠르다.
- 스레드 생성, 스케줄, 동기화 등이 커널로의 진입없이 사용자 공간에서 이루어지므로

2) 단점

멀티 코어 CPU가 보편화된 현대 컴퓨터에서 비효율적
- 사용자 레벨 스레드의 병렬처리 안됨
하나의 사용자 레벨 스레드가 블록되면 프로세스 전체 블록
- 다른 사용자 레벨 스레드도 실행되지 못함
  1 : 1 매핑
사용자 레벨 스레드 당 1개의 커널 레벨 스레드(TCB) 생성
사용자 레벨 스레드는 매핑된 커널 레벨 스레드가 스케줄되면 실행
1:1 매핑의 장단점 1) 장점
개념이 단순하여 구현이 용이
멀티 코어 CPU에서 멀티스레드 응용프로그램에게 높은 병렬성제공
하나의 사용자 레벨 스레드가 블록되어도 응용프로그램 전체가 블록되지 않음

2) 단점

커널에게는 부담스러운 정책
사용자 레벨 스레드가 많아지면 모두 커널의 부담

N : M 매핑

N개의 사용자 레벨 스레드를 M개의 커널 레벨 스레드에 매핑
N:M 매핑의 장단점 1) 장점
1:1 매핑에 비해 커널 엔터티 개수가 작아 커널의 부담이 적음

2) 단점

구현하기 복잡하여 현대의 운영체제에서는 거의 사용되지 않음

이 글이 문제가 된다면 삭제하겠습니다.

[운영체제] 3. 프로세스와 프로세스 관리

Mon, 30 May 2022 04:42:47 GMT

프로세스 개요

** 프로그램 : 하드디스크 등의 저장 매체에 저장. 실행 파일의 형태

프로세스 : 프로그램이 메모리에 적재되어 실행 중인 상태
- 필요한 모든 자원 할당 받음
- 자원 : 코드공간, 데이터공간, 스택공간, 힙공간
  프로세스 특징
프로세스 특징

운영체제는 프로그램을 메모리에 적재하고 프로세스로 다룸
운영체제는 프로세스에게 실행에 필요한 메모리 할당, 이곳에 코드와 데이터 등 적재
프로세스들은 서로 독립적인 메모리 공간을 가짐. 다른 프로세스의 영역에 접근 불허
커널은 각 프로세스의 메모리 위치와 크기 정보를 관리한다.
커널은 프로세스마다 고유한 번호(프로세스 ID) 할당
프로세스에 관한 모든 정보는 커널이 관리
프로세스는 실행-대기-잠자기-대기-실행-종료 등의 생명주기를 가짐
프로세스를 만들고, 실행하고, 대기시키고, 종료시키는 모든 관리는 커널에 의해 수행

프로세스 관리

프로세스의 생성에서 종료까지 관리는 모두 커널에 의해 이루어짐
- 커널 영역에 프로세스 테이블을 만들고, 프로세스의 목록 관리
관리내용
- 프로세스 생성, 실행, 일시 중단 및 재개, 정보 관리, 프로세스 통신, 프로세스 동기화, 프로세스 중단, 프로세스 컨텍스트 스위칭
프로그램의 다중 인스턴스
- 한 프로그램을 여러 번 실행시켜 다중 인스턴스를 생성하면 어떻게 될까?
- 운영체제는 프로그램을 실행할 때마다 독립된 프로세스 생성
- 각 프로세스에게 독립된 메모리 공간 할당
- 운영체제는 다중 인스턴스 프로세스들을 별개의 프로세스들로 취급

CPU 주소 공간

** CPU가 주소선을 통해 엑세스할 수 있는 전체 메모리 공간

공간 크기
- CPU의 주소선의 수에 의해 결정
- 32비트 CPU -> 32개의 주소선 -> 232개의 주소 -> 4GB 공간
주소공간은 0번지부터 시작
- 1번지의 저장 공간 크기는 1바이트
  프로세스를 구성한 4개의 메모리 영역

코드 영역

실행될 프로그램 코드가 적재되는 영역
사용자가 작성한 모든 함수의 코드
사용자가 호출한 라이브러리 함수들의 코드

데이터 영역 (상수 공간)

전역 변수 공간, 정적 데이터 공간 ( 사용자 프로그램과 라이브러리 포함 )
프로그램에서 고정적으로 만든 변수 공간 (상수 공간)
프로세스 적재 시 할당, 종료 시 소멸

힙 영역

프로세스가 실행 도중 동적으로 사용할 수 있도록 할당된 공간
malloc() 등으로 할당받는 공간은 힙 영역에서 할당
힙 영역에서 아래 번지로 내려가면서 할당

스택 영역

함수가 실행될 때 사용될 데이터를 위해 할당된 공간
매개변수들, 지역변수들, 함수 종료 후 돌아갈 주소 등
함수는 호출될 때, 스택 영역에서 위쪽으로 공간 할당
함수가 return 하면 할당된 공간 반환

** 함수 호출 외에 프로세스에서 필요시 사용가능

프로세스 주소 공간

프로세스가 실행 중에 접근할 수 있도록 허용된 주소의 최대 범위
프로세스 주소 공간은 논리 공간(가상 공간) - 0번지에서 시작하여 연속적인 주소
프로세스 주소 공간 크기
- CPU 가 엑세스할 수 있는 전체 크기 ( 32비트 CPU의 경우, 4GB )
- 프로세스 주소 공간 크기는 프로세스의 현재 크기와 다름
- 프로세스 주소 공간의 크기 : 프로세스가 액세스할 수 있는 최대 크 기
- 프로세스 현재 크기 : 적재된 코드 + 전역변수 + 힙 영역에서 할당받아 사용 중인 동적 메모리 공간 + 현재 스택 영역에 저장된 데이터 크기

** 프로세스 주소 공간은 2부분으로 나뉘어짐

1) 사용자 공간

프로세스의 코드, 데이터, 힙, 스택 영역이 할당되는 공간
코드와 데이터 영역의 크기는 프로세스 시작 시 결정
힙과 스택 영역의 크기는 정해져 있지 않음
힙 영역은 아래로 자라고, 스택은 위로 자람

2) 커널 공간

프로세스가 시스템 호출을 통해 이용하는 커널 공간
커널 코드, 커널 데이터, 커널 스택(커널 코드가 실행될 때)
커널 공간은 모든 사용자 프로세스에 의해 공유 ( 프로세스나 스레드가 스택이나 힙을 소유 )

프로세스 주소 공간의 특징

** 프로세스의 주소 공간은 가상 공간

프로세스의 주소 공간은 사용자나 개발자가 보는 관점
- 자신이 작성한 프로그램이 0번지부터 시작하여,
- 연속적인 메모리 공간에 형성되고,
- CPU가 액세스할 수 있는 최대 크기의 메모리가 설치되어 있다고 상상
실제 상황
- 설치된 물리 메모리의 크기는 주소 공간보다 작을 수 있고,
- 프로세스의 코드, 데이터, 힙, 스택은 물리 메모리에 흩어져 저장됨 (연속적인 메모리 공간이 아님)

프로세스 주소 공간은 프로세스별로 주어지는가? YES

프로세스마다 주소 공간은 별개이다.

그러면, 프로세스 주소 공간은 충돌하는가? NO

프로세스 주소 공간은 가상 주소 공간이다.
가상 주소가 실제 주소로 매핑되므로, 물리 메모리에서는 충돌하지 않는다.

[가상 주소 공간의 물리 메모리로의 매핑]

사용자는 연속적인 공간(가상 주소 공간)으로 생각 -> 그러나 가상 주소의 데이터가 실제 메모리에 분산되어 있어 어느 번지에 있을지 알 수 없음

가상메모리 운영 방식 : LRU (least, recently, uses- 최근 최소 사용) 필요한 것만 RAM으로 가져오고 오래동안 사용하지 않는 건 하드디스크에 내려놓는다.

커널 공간의 의미

** 각 프로세스는 독립된 사용자 공간 소유, 커널 공간 공유

커널 공간
- 프로세스가 사용자 코드에서 시스템 호출을 통해 커널 코드 실행할 때 커널 공간 사용
  - 사용자 프로세스가 커널 모드에서 실행되고 있다고 함
  - 커널 코드를 실행하고 있는 것은 사용자 프로세스임
  - 커널 코드가 적재된 물리 메모리의 위치 역시 사용자 프로세스가 소유한 매핑 테이블 사용
사용자 공간과 커널 공간의 결론
- 프로세스마다 각각 사용자 주소 공간이 있다.
- 시스템 전체에는 하나의 커널 주소 공간이 있다.
- 모든 프로세스는 커널 주소 공간을 공유한다.
  커널의 프로세스 관리
  
  프로세스 테이블과 프로세스 제어 블록
  프로세스 테이블과 프로세스 제어 블록

1) 프로세스 테이블

시스템의 모든 프로세스들을 관리하기 위한 표
시스템에 한 개만 있음
구현 방식은 운영체제마다 다름

2) 프로세스 제어 블록(PCB : Process Control Block)

프로세스에 관한 정보를 저장하는 구조체
프로세스 당 하나씩 존재
프로세스가 생성될 때 만들어지고 종료되면 삭제
커널에 의해 생성, 저장, 읽혀지는 등 관리

nice 값 : Linux 상에서 Process 가 실행될 때, nice 라는 값을 가지고 실행되는데, nice 값은 process 간의 우선순위를 말함
프로세스 제어 블록에 저장되는 정보 (운영체제마다 프로세스 제어 블록에 저장되는 요소와 프로세스 상태 등이 다름)

프로세스 번호(PID, Process ID) : 정수, 유일한 번호, 이 번호로 프로세스 구분
부모 프로세스 번호(PPID, Parent Process ID) : 부모 프로세스의 PID
프로세스 상태(Process State) 정보
CPU 컨텍스트 정보

PC(Program Counter) : 선택되면 실행을 시작할 프로세스 내 코드 주소
- 사용자 모드에 있었던 경우, 사용자 공간의 코드 주소
- 커널 모드에 있었던 경우, 커널 공간의 코드 주소
- SP(Stack Pointer)
- 기타 레지스터

스케줄링 정보

우선 순위 값, nice 값, 스케줄 큐에 대한 포인터 등

프로세스 종료 코드(정수 0 ~ 255)

exit() 시스템 호출의 매개변수 값, return 문의 리턴 값. 부모 프로세스에게 전달

열어놓은 파일 디스크립터들이 저장되는 배열
메모리 관리 정보

페이지 테이블의 메모리 위치, 프로세스에게 할당된 물리 메모리의 주소 등

프로세스 사이의 통신 정보들
회계 정보

CPU의 사용 시간, 시간 제한, 프로세스의 총 경과시간 등

프로세스 소유자 이름

프로세스를 생성한 사용자의 로그인 이름 정보

프로세스의 생명주기

New(생성 상태)

프로세스가 생성된 상태. 메모리 할당 및 필요한 자원 적재

Ready(준비 상태)

프로세스가 스케줄링을 기다리는 준비 상태
프로세스는 준비 큐에서 대기
스케줄링 되면 Running 상태로 되고 CPU에 의해 실행됨

Running(실행 상태)

프로세스가 CPU에 의해 현재 실행되고 있는 상태
CPU의 시간할당량(타임슬라이스)가 지나면 다시 Ready 상태로 바뀌고 준비 큐에 삽입
프로세스가 입출력을 시행하면 커널은 프로세스를 Blocked 상태로 만들고 대기 큐에 삽입

Blocked/Wait(블록 상태)

프로세스가 자원을 요청하거나, 입출력을 요청하고 완료를 기다리는 상태
입출력이 완료되면 프로세스는 Ready 상태로 바뀌고 준비 큐에 삽입

Terminated/Zombie 상태

프로세스가 종료된 상태 (프로세스가 차지하고 있던 메모리와 할당받았던 자원들을 모두 반환, 열어 놓은 파일 닫힘)
프로세스가 PCB에 남긴 종료코드를 부모 프로세스가 읽어가지 않아 완전히 종료되지 않은 상태 - 좀비 상태라고 부름
아직 PCB가 남아있음

Terminated/Out 상태

프로세스가 종료하면서 남긴 종료코드를 부모 프로세스가 읽어 가서 완전히 종료된 상태
프로세스 테이블의 항목과 PCB가 시스템에서 완전히 제거된 상태

프로세스 스케줄링과 컨텍스트 스위칭
프로세스 스케줄링
- 과거 운영체제에서 실행단위는 프로세스였음
- Ready 상태의 프로세스 중에 실행 시킬 프로세스 선택
오늘날 운영체제는 스레드를 대상으로 스케줄링
- 오늘날 프로세스 스케줄링은 없음
- 오늘날 운영체제에서 실행 단위는 스레드
- Ready 상태의 스레드 중 실행시킬 스레드 선택
프로세스는?
- 프로세스는 스레드들에게 공유 자원을 제공하는 컨테이너로 역할이 바뀌었음
  프로세스 계층 구조
  
  프로세스 부모-자식 관계
- 프로세스는 일반적으로 부모-자식 관계 (윈도우에서 프로세스는 모두 동등 - 계층 관계 아님)
#0 프로세스가 시스템 부팅시 실행되는 최초의 프로세스, 조상 프로세스
부모 프로세스는 여러 개의 자식 프로세스를 가질 수 있음
모든 프로세스는 부모 프로세스를 가짐 (#0 프로세스 제외)
자식 프로세스 생성
- 모든 프로세스는 프로세스(부모)에 의해 생성
  - 프로세스 생성은 시스템 호출을 통해서만 가능

fork(), clone() 등의 커널 코드가 자식 프로세스 생성 예외 : PID 0,1,2 등의 몇몇 조상 프로세스는 시스템 호출이 아닌 수작업으로 생성

리눅스 사례 #0 프로세스 - swapper/idle 프로세스 (hand-crafted) #1 프로세스 - init 프로세스(hand-crafted) - 부팅 후 생성되는 모든 사용자 프로세스의 조상 #2 프로세스 - kthreadd 프로세스 - 커널 모드에서 커널 코드로만 실행되는 모든 커널 프로세스의 조상

#0과 #1 프로세스 : idle 프로세스와 init 프로세스

#0 프로세스
- 최고의 어른(조상) 프로세스
- Unix의 #0 프로세스
  - swapper 라고 불림, 부팅을 담당하고 #1 프로세스 생성
Linux의 #0 프로세스
- idle 프로세스, 부팅 관여 없이 아무 일도 하지 않고 루프
  - 우선 순위가 가장 낮은 프로세스, 다른 프로세스가 있으면 실행될 일 없음
  - 실행 중인 프로세스가 1개도 없는 상태에 빠지지 않게 하기 위해 만든 프로세스
  - Unix 시절의 관례에 따르기 위해 만들어진 프로세스
Windows의 #0 프로세스 : system idle process(시스템 유휴 프로세스)
- 아무 일도 하지 않고 루프를 도는 단순 프로세스
프로세스를 다루는 시스템 호출

fork() - 자식 프로세스를 생성하는 시스템 호출
exit() - 프로세스의 종료를 커널에 알리는 시스템 호출
wait() - 부모가 자식 프로세스의 종료를 기다리고 확인하는 시스템 호출

프로세스 종료

** 좀비 프로세스 : 종료 후 방치된 자식 프로세스

프로세스가 종료할 때
- PCB에, 종료 코드 저장
- PCB에 프로세스 상태를 Terminated 라고 표시
- 프로세스에게 할당된 모든 메모리 반환
  - PCB와 프로세스 테이블의 항목은 제거되지 않음
부모 프로세스의 의무
- wait() 시스템 호출을 통해 프로세스의 종료 코드를 읽어야 함
좀비 프로세스
- 종료하였지만, 부모가 종료 코드를 읽지 않은 상태의 프로세스
- 프로세스 리스트를 출력할 때(ps명령으로) 나타남
좀비 프로세스 제거
- 부모에게 SIGCHLD 핸들러가 없다면 좀비는 제거되지 못함
- 부모 프로세스를 강제 종료시키면,
- 좀비는 init 프로세스의 자식이 되고
- init이 wait() 호출하여 좀비 프로세스 제거
- 쉘에서 부모 프로세스에게 SIGCHLD 신호보내기
  - 부모 프로세스에서 wait() 함수를 호출하여 처리

고아 프로세스와 입양

고아 프로세스 : 부모가 먼저 종료한 자식 프로세스

부모 프로세스가 종료할 때
- 일반적으로
  - 커널(exit() 시스템 호출 코드)은 자식 프로세스가 있는지 확인
  - 커널은 자식 프로세스(고아)를 init 프로세스에게 입양

운영체제에 따라, 혹은 쉘의 경우

모든 자식 프로세스를 강제 종료시키기도 함
여러종류의 프로세스

1) 백그라운드 프로세스

터미널에서 실행되었지만, 터미널 사용자와 대화가 없는 채 실행되는 프로세스
사용자와 대화없이 실행되는 프로세스
사용자 입력을 필요로 하지 않는 프로세스
idle 상태로 잠을 자거나 디스크에 스왑된 상태의 프로세스

2) 포그라운드 프로세스

실행되는 동안 터미널 사용자의 입력을 독점하는 프로세스

3) CPU 집중 프로세스 vs. I/O 집중 프로세스

CPU 집중프로세스
- 대부분의 시간을 계산 중심의 일(CPU 작업)을 하느라 보내는 프로 세스
- 배열 곱, 인공지능 연산, 이미지 처리
- CPU 속도가 성능 좌우
I/O 집중 프로세스
- 입출력 작업을 하느라 대부분의 시간을 보내는 프로세스
- 네트워크 전송, 파일 입출력에 집중된 프로세스
- 파일 서버, 웹 서버
- 입출력 장치나 입출력 시스템의 속도가 성능 좌우
운영체제의 스케줄링 우선순위 : I/O 집중 프로세스 > CPU 집중 프로세스
- I/O 작업을 하는 동안 다른 프로세스에게 CPU 할당 가능
  프로세스 제어
  
  프로세스 생성
컴퓨터 시스템에서 프로세스가 생성되는 5가지 경우
- 시스템 부팅과정에서 필요한 프로세스 생성
- 사용자의 로그인 후 사용자와 대화를 위한 프로세스 생성(bash 등 쉘)
- 새로운 프로세스를 생성하도록 하는 사용자의 명령(vi a.c, vi hello.c)
- 배치 작업 실행 시(at, batch 명령, "몇 시에 ~해라")
- 사용자 응용프로그램이 시스템 호출로 새 프로세스 생성
프로세스 생성
- 프로세스가 프로세스를 생성
시스템 호출을 통해서만 프로세스 생성
- 커널만이 프로세스 생성가능
- 리눅스 : fork() 시스템 호출
- windows : CreateProcess() 등 시스템 호출
프로세스 생성 과정 1) 새로운 PID 번호 할당 2) PCB 구조체 생성 3) 프로세스 테이블에서 새 항목 할당 4) 새로운 프로세스를 위한 메모리 공간 할당
프로세스의 코드, 데이터, 스택, 힙 영역
할당받은 메모리 공간에 프로세스의 코드와 데이터 적재 5) PCB에 프로세스 정보 기록 6) PCB에 프로세스 상태를 ready 상태로 표시하고, 준비 큐에 넣어서 차후 스케줄되게 함

fork() 시스템 호출로 자식 프로세스 생성

int pid = fork();
자식 프로세스 생성
부모 프로세스의 모든 환경, 메모리, PCB 등을 복사
부모와 동일한 모양이지만, 독립된 주소 공간 소유

리턴값
부모 프로세스에게는 자식 프로세스의 PID 리턴
자식 프로세스에게는 0 리턴

프로세스 오버레이, exec()

프로세스 오버레이(process overlay)

현재 실행중인 프로세스의 주소 공간에 새로운 응용프로그램을 적재하여 실행시키는 기법

exec 패밀리 시스템 호출 -> execlp(), execv(), execvp() 시스텔 호출들 -> 실행 파일을 로딩하여 현재 프로세스의 이미지 위에 단순히 덮어쓰고 새로운 프로세스의 생성 과정을 거치지 않는다.

프로세스의 PID 변경 없음

프로세스의 코드, 데이터, 힙, 스택에 새로운 응용프로그램이 적재됨

보통 fork() 를 통해 생성된 자식 프로세스가 exec() 실행

프로세스 종료와 종료 대기

프로세스 종료
- exit() 시스템 호출
- C프로그램의 main() 에서 리턴
  - exit() 시스템 호출이 결국 실행되도록 컴파일 됨
종료 코드
- 부모 프로세스에게 전달하는 값
  - main() 함수의 리턴 값; return 종료 코드;
  - exit(종료코드)
exit() 시스템 호출로 프로세스 종료 과정

1) 프로세스의 모든 자원 반환 - 코드, 데이터, 스택, 힙 등의 모든 메모리 자원을 반환 - 열어 놓은 파일이나 소켓 등을 닫음

2) PCB에 프로세스 상태를 Terminated 로 변경, PCB 에 종료 코드 저장 3) 자식 프로세스들을 init 프로세스에게 입양 4) 부모 프로세스에게 SIGCHLD 신호 전송 - 부모가 SIGCHLD 신호 처리기를 작성하여 wait() 시스템 호출로 자식의 종료 코드 읽기 실행 - 혹은 언젠가 부모가 자식의 죽음 처리. 그동안 자식은 좀비 상태에 있음

종료코드의 의미와 범위

1) 종료 코드

프로세스가 종료한 상태나 이유를 부모에게 전달하기 위한 것
POSIX 표준에서 0 ~ 255 사이의 1바이트 숫자
- 정상종료는 0
- 1~255 : 개발자가 종료 이유를 임의로 정해 사용

2) 종료 코드 사용 시 유의할 점

main 이나 exit()에서 255 이상의 값을 사용할 때 유의

int main(){ return 300; // return 44; 와 같음 } void func(){ exit(300); // exit(44) 와 같음 }

-1을 리턴하는 경우 (return -1, 혹은 exit(-1))
-1 -> 0xff -> 양의 정수로 255. 그러므로 종료 코드로 255가 전달

프로세스 종료와 좀비 프로세스
1) 프로세스 종료
두 종류
- C언어에서 main() 함수의 종료나 exit() 을 호출한 정상 종료
- 다른 프로세스에 의해 강제 종료

2) 프로세스가 종료되면

차지하고 있던 메모리와 자원 모두 반환
PCB는 프로세스 테이블에서 제거되지 않음
프로세스 상태 : Terminated

** 죽은 프로세스가 wait(), 혹은 CloseHandle() 시스템 호출을 통해, 죽은 자식이 남긴 정보를 읽게 되면 자식 프로세스의 PCB 가 완전히 제거

좀비 프로세스 종료할 때 리턴한 정보(main() 함수에서 리턴값)를 부모 프로세스가 읽지 않을 때, 죽었지만 PCB만 남아 완전히 제거되지 못한 상태

이 글이 문제가 된다면 삭제하겠습니다.

[운영체제] 2. 컴퓨터 시스템과 운영체제

Mon, 30 May 2022 04:42:25 GMT

컴퓨터 시스템과 하드웨어

컴퓨터 시스템의 범위

컴퓨터 시스템의 계층
- 응용프로그램 층
- 운영체제 층
- 컴퓨터 하드웨어 층
컴퓨터 시스템 계층 구조의 특징
- 사용자는 응용프로그램/도구프로그램을 통해 컴퓨터 활용
- 하드웨어는 모두 운영체제의 배타적 독점적 지배를 받음
- 사용자나 응용프로그램의 하드웨어에 대한 직접 접근 불허 (반드시 운영체제를 통해서만 접근 가능)
계층 구조에서 보는 운영체제의 기능
- 사용자가 하드웨어에 대해 몰라도 컴퓨터를 사용할 수 있도록 함
- 응용프로그램과 하드웨어 사이의 중계
  컴퓨터 하드웨어 구성
  
  컴퓨터 하드웨어 설명
CPU (Central Processing Unit)
- 프로그램 코드, 기계 명령을 해석하여 실행하는 중앙처리장치
- 컴퓨터의 가장 핵심 장치
- 전원이 공급될 때 작동 시작, 메모리에 적재된 프로그램 실행
메모리
- 반도체 메모리 RAM
- CPU에 의해 실행되는 프로그램 코드와 데이터가 적재되는 공간
- 프로그램은 실행되기 위해서 반드시 메모리에 적재되어야 함
캐시 메모리(Cache Memory)
- CPU 처리속도가 메모리 속도에 비해 빠르게 향상 -> CPU는 느린 메모리 때문에 대기시간이 늘게 되었음
- CPU의 프로그램 실행 속도를 높이기 위해, CPU와 메모리 사이에 설치되는 소량의 빠른 메모리, 고가의 메모리 ※ 온칩 캐시 - CPU 내부에 설치되는 캐시 ※ 옵치 캐시 - CPU 외부에 설치되는 캐시
- 캐시 메모리가 있는 경우 CPU는 캐시 메모리에서만 프로그램 실행 (실행하고자하는 프로그램과 데이터는 먼저 메모리에서 캐시로 옮겨져야 함)
장치들
- 키보드, 프린터, 스캐너 등
버스
- 하드웨어들이 데이터를 주고받기 위해 0과 1의 디지털 신호가 지나가는 여러 가닥의 선을 다발로 묶어 부르는 용어
- 버스의 종류 : 주소 버스, 데이터 버스, 제어 버스
- 주소
  - 메모리나 입출력 장치나 저장 장치 내에 있는 저장소에 대한 번지
  - 가장 작은 번지는 0번지이고 그 외는 양의 정수
  - 주소 버스는 주소 값이 전달되는 여러 선의 다발을 부름 (16bit면 16가닥)
- CPU는 메모리나 입출력 장치에 값을 쓰거나 읽을 때 반드시 주소를 발생시킴

버스는 목적에 따라 구분

시스템 버스	입출력 버스
CPU, 캐시, 메모리 등 빠른 하드웨어들 사이에 신호 전송	상대적으로 느린 입출력 장치들로부터 입출력 데이터 전송
비유 : 고속도로	비유 : 일반도로

입출력 제어 장치 및 시스템 제어 회로
- 입출력 장치에게 명령을 하달
- 메모리와 입출력 장치 사이에 혹은 CPU와 입출력 장치 사이에 데이터가 전달 중계
- DMAC(Direct Memory Access Controller), 인터럽트 제어장치(Interrupt Controller, INTC) 등 포함

CPU와 메모리의 관계

CPU
- 능동적 소자, 메모리 액세스 시 주소 발생
- 32비트 CPU, 32비트 운영체제, 32비트 컴퓨터
- CPU에 32개 주소선
- CPU가 액세스하는 주소 범위 : 0~ 2³² -1 번지
- CPU가 최대 액세스할 수 있는 메모리의 크기 : 4GB
- 한 번지의 저장공간이 1바이트이므로, 2³² 바이트 = 4GB
- 32비트 CPU를 가진 컴퓨터에 4GB이상 메모리를 달아도 소용없음
- CPU에 입출력되는 32개의 데이터 선 ( 한 번에 32비트 읽고 쓰기 가능 )
- 32비트 CPU는 32개 데이터선을 통해 32비트를 한 번에 메모리에서 읽고 쓰고 한 번에 32비트 더하기를 한다.

[참고] -> 2¹⁰ = 1KB -> 2²⁰ = 2¹⁰ x 2¹⁰ = 1MB -> 2³⁰ = 2²⁰x 2¹⁰ = 1GB -> 2³² = 2² x 2³⁰ = 4 x 1GB = 4GB

CPU와 메모리는 시스템 버스를 통해서 소통을 하면서 데이터를 주고 받는다.
메모리의 역할은 CPU에게 데이터를 전달하거나 CPU에서 처리된 데이터를 저장하는 역할을 한다.
CPU와 메모리가 연결된 버스는 크게 3가지가 있다.
- 컨트롤 버스 : CPU가 메모리에게 데이터를 요청하거나 저장하라고 하는 정보를 주고받는 버스
- 주소 버스 : 메모리에서 해당 데이터의 주소 정보를 주고 받는 버스
- 데이터 버스 : 실제 주소에 저장되어 있는 데이터를 주고 받는 버스

명령

1) 명령 처리 과정

CPU 레지스터들
- PC(Program Counter) - 다음에 실행할 명령의 메모리 주소 저장
- IR(Instruction Register) - 현재 실행하기 위해 메모리로부터 읽어 온 명령 저장
- SP(Stack Pointer) - 스택의 톱 메모리 주소 저장
- 데이터 레지스터들(data registers) - 연산에 사용될 데이터들을 저장
- 상태 레지스터(status register) - CPU의 상태 정보나 인터럽트 금지 등의 제어 정보 저장
- 기타 여러 레지스터 - 페이지 테이블이 저장된 메모리 주소를 가리키는 레지스터 등
명령어 사이클(Instruction cycle)
- CPU 하나의 명령을 실행하는 과정. CPU는 전원이 켜진 후 단순하게 명령 사이클 반복
명령어 사이클 사례 : 메모리 100번지에 저장된 다음 명령을 실행하는 사례

2) 명령 처리 과정 예시

- mov eax, [300] ; 메모리 300 번지 값을 읽어 eax 레지스터에 저장

1) CPU는 PC 레지스터가 가리키는 주소(100)을 주소 버스에 싣는다. 2) 메모리는 100번지에 저장된 데이터(mov eax, [300])을 데이터 버스에 싣는다. 3) CPU는 데이터 버스에 담긴 바이너리 값들은 IR 레지스터에 저장. PC는 다음 번지로 수정한다. 4) CPU는 연산에 필요한 데이터를 읽기 위해 데이터의 주소(300)을 주소 버스에 싣는다. 5) 메모리는 300번지에 저장된 50을 데이터 버스에 싣는다. 6) CPU는 데이터 버스로부터 50을 임시 데이터 레지스터에 저장한다. 7) 이제 CPU는 명령을 해석하고 명령을 실행한다. 명령 실행 결과, 50이 eax 레지스터에 저장된다.

스택은 어디 있는가?

프로그램이 실행되기 위해 운영체제에 의해 메모리에 할당되는 4개 공간 - 코드 공간 - 프로그램 코드 적재 - 데이터 공간 - 전역 변수들이 적재되는 공간 - 힙 공간 - 프로그램 동적으로 저장할 데이터를 위한 공간 - 스택 공간 - 함수가 호출될 때 매개변수, 지역변수 등 저장

스택 : 운영체제에 의해 프로그램마다 메모리에 할당된 일부 영역
- 스택이라는 별도의 하드웨어 메모리가 있는 것은 아님
- 메모리의 일부를 스택으로 사용하도록 할당된 공간
- 각 프로그램에게 자신만의 스택 공간 할당
- CPU의 SP 레지스터가 현재 프로그램의 스택 꼭대기 주소를 가리킴
- 스택에 저장되는 내용
- 함수의 지역변수들
- 함수가 호출될 때 전달받은 매개변수 값들
- 함수를 실행한 후 돌아갈 주소
- 함수 코드가 의도적으로 저장해 두기 위한 값
  
  컨택스트
컨텍스트 : 프로그램이 실행 중인 일체의 상황 혹은 상황 정보 -> 메모리 (프로그램 코드와 데이터, 스택, 동적할당 받아 저장한 값)
- CPU 레지스터들의 값
- PC에는 코드의 주소
  - SP에는 스택의 주소
  - 다른 레지스터는 이전의 실행 결과나 현재 실행에 사용될 데이터들
축소정의 : 현재 CPU에 들어 있는 레지스터들의 값들
컨텍스트 스위칭
- 현재 실행중인 프로그램의 컨텍스트(CPU레지스터들의 값)를 저장
- 다른 프로그램의 저장된 컨텍스트(CPU레지스트들의 값)를 CPU에 복귀
- 발생
- CPU가 현재 프로그램 실행을 중지하고 다른 프로그램을 실행할 때
  
  멀티코어 CPU
2001년 IBM에 의해 PowerPC라는 멀티코어 CPU 개발
- CPU 내부에 2개의 프로세서 포함
- 2개의 프로그램을 동시에 실행
  - 코어는 완벽한 처리기, 과거 개념의 CPU
    컴퓨터 시스템과 운영체제
    
    컴퓨터 시스템이 계층 구조로 설계된 이유
    : 계층 간 독립성 확보를 위해
사용자 : 운영체제나 하드웨어에 대해 몰라도 응용프로그램으로 컴퓨터 활용 가능

1) 응용프로그램

컴퓨터 하드웨어 타입이나 구조, 제어 방법을 몰라도 개발 가능
- CPU 크기, 메모리 크기가 얼마인지 모르고 프로그램 작성
- 저장 장치가 하드디스크인지 SSD인지, 저장 장치의 크기는 얼마인지, 디스크 헤드는 몇 개 있는지 몰라도 파일 입출력 프로그램 작성
운영체제에게 요청하여 해결
컴퓨터 하드웨어가 바뀌어도 응용프로그램을 다시 작성할 필요 없음

2) 운영체제

운영체제는 장치 관련된 모든 작업을 디바이스 드라이버에게 요청
응용프로그램과 하드웨어 사이의 인터페이스

왜 운영체제가 필요한가?
운영체제가 없다면
- 응용프로그램이나 사용자가 직접 하드웨어를 제어해야 함
- 하드웨어에 대한 지식, 충돌, 관리, 보안의 문제 발생
운영체제의 필요성 : 자원에 대한 충돌 해결, 성능 최적화, 사용자의 시스템 사용의 효율화

운영체제와 응용프로그램 사이의 관계

1) 응용프로그램
워드, 웹브라우저 등 사용자가 컴퓨터를 활용하도록 작성된 다양한 프로그램들

2) 응용프로그램에 대한 운영체제의 역할

응용프로그램이 직접 하드웨어를 다루지 못하도록 차단
- 운영체제가 하드웨어 완벽히 독점 장악
- 이유 : 응용프로그램들 사이의 하드웨어 사용 충돌을 막기 위함

3) 응응프로그램은 하드웨어를 사용하고자 할 때

반드시 운영체제에게 요청 -> 운영체제가 대신하여 하드웨어 조작
유일한 요청 방법 : 시스템 호출

4) 응용프로그램과 하드웨어 사이의 인터페이스

5) 응용프로그램들의 실행 순서 제어

6) 응용프로그램들 사이의 통신 중계

운영체제와 사용자의 관계

사용자는 응용프로그램을 통해 컴퓨터 활용 : 탐색기, 메모장 등
사용자에 대한 운영체제의 역할
- 사용자가 하드웨어에 관한 지식이 없어도 컴퓨터 다루기 용이
- 사용자가 하드웨어를 설치하거나 변경하는 것에 도움
- 사용자에게 컴퓨터 시스템을 사용할 때 편리한 인터페이스 제공 ( UI, 마우스, 음성 명령 등 )
- 컴퓨터의 사용을 돕는 여러 도구 응용프로그램(유틸리티) 제공 ( Windows 의 탐색기와 작업관리자 )
- 사용자 계정관리
- 사용자의 컴퓨터 사용 시간 계산, 과금 처리 등

운영체제와 하드웨어의 관계

하드웨어를 제어하는 것은 전적으로 운영체제의 몫
- 응용프로그램에서 printf("hello") : 디스플레이 장치에 "hello"를 출력하는 일을 운영체제가 함
- 응용프로그램에서 scanf() : 키보드로부터 문자를 입력받는 일은 운영체제가 함
  운영체제
운영체제
- 사용자/응용프로그램과 하드웨어 사이의 매개체
- 하드웨어 제어는 전적으로 운영체제의 기능
  - 하드디스크에서 파일을 읽거나 쓰기
  - 마우스의 클릭
  - 키보드의 입력 받기
  - 네트워크를 통한 데이터 전송 혹은 수신
    - 디스플레이에 텍스트나 이미지, 그래픽 등 출력
운영체제의 전체기능

1) 프로세스와 스레드 관리

프로세스/스레드의 실행, 일시 중단, 종료, 스케줄링, 컨텍스트 스위칭, 동기화

2) 메모리 관리

프로세스나 스레드에게 메모리 할당, 메모리 반환, 다른 프로세스/스레드로부터 메모리 보호
메모리를 하드 디스크의 영역까지 확장하는 가상 메모리 기술

3) 파일 관리 혹은 파일 시스템 관리

파일 생성, 저장, 읽기, 복사, 삭제, 이동, 파일 보호

4) 장치 관리

키보드, 마우스, 프린터 등 입출력 장치, 하드 디스크 등 저장 장치 제어
입출력

5) 사용자 인터페이스

라인 기반 명령 입출력 창, 마우스와 그래픽 사용 GUI 인터페이스

6) 네트워킹

네트워크 인지, 연결, 닫기, 데이터 송수신

7) 보호 및 보안

바이러스나 웜, 멀웨어, 해킹 등의 외부 공격이나 무단 침입으로부터 보호

운영체제의 구성 요소와 커널

운영체제 구성

운영체제 = 커널 + 툴 + 디바이스 드라이버

1) 커널

운영체제의 핵심 부분, 좁은 의미의 운영체제
부팅 후 메모리에 상주하는 코드와 데이터
커널 코드는 함수들의 집합의 구성
커널 기능을 이용하려면 응용프로그램은 반드시 시스템 호출을 사용

2) 도구(tool) 소프트웨어와 GUI

사용자가 컴퓨터를 편리하게 사용할 수 있도록 제공하는 툴 소프트웨어 혹은 툴 응용프로그램
Windows 경우, 바탕화면 GUI, 탐색기, 명령창, 작업 관리자, 제어판

3) 디바이스 드라이버

장치를 직접 제어하고 입출력하는 소프트웨어
장치마다 전담 디바이스 드라이버 있음
일반적으로 장치 제작자에 의해 작성되어 배포됨
사례 : 키보드 드라이버, 디스크 드라이버, SCSI 드라이버, 마우스 드라이버, 그래픽 드라이버, 네트워크 드라이버 ...

** 운영체제 커널 인터페이스 : 시스템 호출과 인터럽트

시스템 호출

커널과 응용프로그램 사이의 인터페이스
응용프로그램에서 커널 기능을 사용할 수 있는 유일한 방법
- 시스템 호출 라이브러리를 통해 다양한 시스템 호출 함수 제공
- 예 : open(), close(), read(), write(), fork(), exit(), wait() 등의 시스템 함수 호출

인터럽트

커널과 하드웨어 장치 사이의 인터페이스
장치들이 입출력 완료, 타이머 완료 등을 CPU에게 알리는 하드웨어적 방법 (인터럽트 하드웨어 신호가 직접 CPU에 전달)
CPU는 하는 일을 중단하고 인터럽트 서비스 루틴 실행
- 인터럽스 서비스 루틴은 커널이 적재된 메모리 영역에 있는 코드
- 인터럽트 서비스 루틴은 일반적으로 디바이스 드라이버 내에 있음 예 : 키를 입력하면 커널의 키보드 인터럽트 서비스 루틴 실행, 키를 읽어 커널 버퍼에 저장
- 인터럽트 서비스 루틴의 실행을 마치면 하던 작업 계속
인터럽트 활용
- 운영체제가 장치에게 지시한 입출력 작업의 완료, 예고 없는 네트워크 데이터의 도착, 키모드나 마우스의 입력, 부족한 배터리의 경고등 장치와 관련된 모든 이벤트 처리
  커널과 시스템 호출
  
  응용프로그램의 자원 접근 문제
오늘 날 운영체제는 다중프로그래밍 운영체제
- 응용프로그램이 직접 컴퓨터 자원에 접근하면 충돌과 훼손 발생
다른 응용프로그램이 적재된 메모리 훼손 가능
다른 응용프로그램이 만든 파일 삭제 및 훼손 가능
응용 프로그램이 커널이 적재된 영역 훼손 가능

해결책

응용프로그램의 자원 접근 불허
메모리 공간을 사용자 공간과 커널 공간으로 분리
CPU의 실행 모드를 사용자 모드와 커널 모드로 분리
- 응용프로그램은 사용자 모드에서만 실행
- 커널 코드는 커널 모드에서만 실행
- 사용자 모드에서 커널 코드를 접근하면 응용프로그램 강제 종료
  사용자 공간과 커널 공간
- 운영체제는 컴퓨터 메모리를 두 공간으로 분리
사용자 공간 : 모든 응용프로그램들이 나누어 사용하는 공간 (응용프로그램들이 적재되는 공간)
커널 공간 : 커널만 사용할 수 있는 공간
- 커널 코드, 커널 데이터 등 커널에 의해 배타적으로 사용되는 공간
- 디바이스 드라이버 포함

사용자 공간 크기

한 응용프로그램의 최대 크기
- 프로그램 코드 + 데이터(전역변수) + 동적할당 + 스택을 합친 크기 예 : 32비트 Windows 운영체제에서 사용자 공간 2GB -> 응용프로그램의 크기가 최대 2GB
사용자 공간의 주소 범위
- 응용프로그램은 운영체제가 설정한 사용자 공간의 주소 범위를 넘어설 수 없음
  주소 공간은 가상 주소 공간

[참고] Memory Management는 CPU가 가상주소체계를 통해 실제물리주소에 존재하는 프로그램을 읽고 실행시키기 위해 필요한 과정을 관리해주는 알고리즘을 말한다. 만약 MMU가 지원되지 않으면 물리메모리에 직접 접근해서 프로그램을 동작시켜야 하기 때문에, 가상메모리만으로도 물리 메모리를 신경쓰지 않고 해결할 수 있도록 해주는 것이 MMU이다.

가상메모리를 통해 우리는 우리에게 실제로 할당된 물리메모리 이상을 사용할 수도 있고, 또한 메모리를 어떻게 할당해주어야 할지에 대한 고민없이 프로그래밍을 할 수 있다. 즉, 아래 3가지가 가능해진다.

1) 사용자가 기억장소를 일일이 할당하는 불편을 없애준다. 2) 프로세스의 크기가 실제 메모리의 총량을 초과해도 사용할 수 있다. 3) 설사 물리적 메모리의 용량이 충분히 크다고하더라도 다중 프로그래밍이 가능하다.

그러니까, 실제적으로 각 프로그램의 일부만이 메모리로 계속 올라가는 것이므로, 어느 시점에서 보면 프로세스의 개수는 많다고 하지만, 실제로 메모리로 올라가는 크기의 총합은 결코 메모리를 초과하지 않는다. 그렇지 만들지 않는다. 설사 메모리가 가득차게 된다고 하더라도 swapping 기술이 적용되어 해결된다.

RAM 공간이 부족할 때 HDD에 파일 형태로 따로 확장하는 가상 메모리 공간

사용자 모드와 커널 모드

** CPU는 사용자 모드와 커널 모드 중 한 모드로 실행 (CPU 내부에는 모드 상태를 나타내는 모드 레지스터가 있음)

1) 사용자 모드

CPU의 모드 비트 = 0
CPU는 사용자 공간에 있는 코드나 데이터를 액세스 하는 중
CPU의 커널 공간 접근 불허 -> 응용프로그램으로부터 커널 영역 보 호
특권 명령 실행 불허

** 특권 명령 : 입출력 장치 등 하드웨어나 시스템 중단 등 시스템 관련 처리를 위해 설계된 특별한 명령

2) 커널 모드

CPU의 모드 비트 = 1
CPU가 커널 공간에서 실행하는 중, 혹은 사용자 코드를 실행하는 중
- 특권 명령 사용 가능

3) 사용자 모드에서 커널 모드로 변경되는 경우

시스템 호출과 인터럽트 발생의 2가지 경우에만 변경
시스템 호출 과정은 커널 모드로 변경하는 특별한 기계 명령 사용
- CPU의 '모드 레지스터'의 값을 커널 모드로 수정
- int 0x80/sysenter/trap/syscall 등 CPU 마다 다름

	사용자모드	커널모드
CPU의 메모리 액세스 범위	사용자 공간에 국한, 커널 공간 액세스 불가	커널 공간을 포함한 모든 메모리 공간
CPU의 하드웨어 액세스 여부	불가	모든 하드웨어 액세스 가능
CPU가 처리 가능한 명령	특권 명령을 제외한 모든 CPU 명령	특권 명령을 포함한 모든 CPU 명령
오류 발생 시 처리	사용자 프로그램만 실행 종료. 시스템이 종료되지 않으므로 안전	시스템에 심각한 오류가 발생한 것으로 시스템 종료

특권 명령

** 특권 명령 : 커널 모드에서 실행할 특별한 목적으로 설계된 CPU 명령

특권 명령 종류 ( 운영체제만 할 수 있는 것들 )

1) I/O 명령

하드웨어 제어 및 장치로부터의 입출력 예 : in eax, 300 : I/O 포트 300번지에서 값을 읽어 eax 레지스터에 저장 out 301, eax : eax 레지스터에 있는 값을 I/O 포트 301번지에 쓰기

2) Halt 명령

CPU의 작동을 중지 시키는 명령. CPU를 유휴 상태로 만듬

3) 인터럽트 플래크 켜고 끄는 명령

CPU 내에 있는 인터럽트 플래그 비트를 제어하여 CPU가 인터럽트를 허용하거나 무시하도록 지시 예 : cli / sti 명령

4) 타이머 설정 명령

5) 컨텍스트 스위칭 명령

6) 메모리 지우기 명령

7) 장치 상태 테이블 수정 등의 명령

실행 모드와 관련된 다양한 이슈

사용자 모드와 커널 모드는 CPU의 기능인가 아니면 운영체제의 기능인가?

모드는 CPU의 기능이다.
CPU 내부에 모드를 나타내는 레지스터 존재
운영체제는 CPU 모드 레지스터를 이용하여 커널 영역 지킴

사용자 응용프로그램이 커널 코드를 호출할 일이 있는가?

사용자 응용프로그램은 직접 커널 코드 호출 불가
시스템 호출을 통해서만 가능

CPU가 평균적으로 커널 모드에서 많이 실행될까 사용자 모드에서 많이 실행될까?

커널 모드에서 많이 실행

운영체제가 사용자 모드와 커널 모드로 나누어 작동시키는 이유는?

커널공간에 대한 보안과 보호
악의적 사용자와 오류 프로그램으로 커널 공간 지킴
사용자 응용프로그램은 사용자 모드에서 아무리 심각한 오류가 발생해도 사용자 프로그램만 종료. 시스템을 중단시키는 못함

커널

** 커널의 실체

커널은 부팅 시에 커널 공간에 적재 함수들과 데이터의 집합
- 커널은 컴파일된 바이너리 형태, 하드디스크 특정 영역에 저장
- 부팅 시에 커널 공간의 메모리에 적재
커널 코드는 함수들의 집합

커널은 스스로 실행되는 프로세스인가? NO

커널은 단순함수들의 집합, 시스템 호출을 통해 호출되는 함수들
커널이 스케줄링한다 ( X )
- 커널 프로세스가 실행되면서 주기적으로 스케줄링 하는게 아니고 시스템 호출과 인터럽트 서비스 루틴에 의해 필요한 경우 스케줄러 함수 실행

커널은 실행 중이다? NO

커널은 프로세스도 스레드도 아니므로 NO
커널이 실행 중인 게 아니고 응용프로그램이 시스템 호출을 실행하면 커널 코드가 실행되는 것
인터럽트가 발생하면 인터럽트 서비스 루틴이 실행

커널은 스택이나 힙을 가지는가? NO

프로세스나 스레드가 스택이나 힙 소유함
커널 공간에 스레드를 위한 스택이 만들어진다. 스레드가 커널 코드를 실행하고 있을 때 커널 스택 형성
커널의 존재
- 커널은 스스로 실행되는 코드(프로세스)가 아님
커널이 스케줄링 한다 -> (커널 속의)스케줄링 함수가 실행된다.

응용프로그램 빌딩

라이브러리
- 응용프로그램에서 활용하도록 미리 함수들을 작성하여 컴파일하고 바이너리 형태로 만든 파일 ( 바이너리 형태면 CPU 가 바로 이해할 수 있어서 Memory 에 탑재했을 때 바로 사용 가능하다 )
- 라이브러리를 활용하지 않고 응용프로그램 작성이 불가능

-응용프로그램이 활용하는 라이브러리는 2가지 유형

표준 라이브러리

운영체제나 컴퓨터 하드웨어에 상관없이 이름과 사용법 동일
사용자가 작성하기 힘든 함수 제공

시스템 호출 라이브러리

시스템 호출을 진행하여 커널 모드로 바꾸고 커널로 진입하여 커널에 만들어진 함수 실행 ( 커널의 다양한 기능 수행 )
운영체제마다 함수의 이름이 서로 다름
커널 API(Application Programming Interface) 라고도 부름
함수 호출과 시스템 호출

1) 함수 호출

사용자 공간에 적재된 함수가 다른 함수나 라이브러리 함수 호출
사용자 공간에서, 사용자 모드에서 실행
실행 과정
- 사용자 공간의 스택에 돌아올 주소, 매개변수 전달, 호출된 함수의 지역변수 생성
- 호출된 함수가 끝나면 함수를 호출한 곳으로 복귀

2) 시스템 호출

응용프로그램이 운영체제의 기능을 사용하고자 하는 경우
커널에 작성된 함수를 실행하고자하는 경우
시스템 호출 라이브러리에서 커널 기능 요청
사용자 모드에서 커널 모드로 변경된 후 커널 함수 실행
실행 과정
- 시스템 호출을 일으키는 특별한 기계 명령 실행 ( 커널 함수마다 매겨진 고유 번호 전달, 사용자 모드에서 커널 모드로 변경 )
- 커널의 시스템 호출 핸들러 실행 ( 이 핸들러가 커널 함수의 고유 번호를 분석하여 해당 커널 함수 호출 )

	함수 호출	시스템 호출
메모리 영역	사용자 영역의 코드에서 사용자 영역의 함수 호출	사용자 영역의 코드에서 커널 함수 호출
CPU 실행 모드	사용자 모드	사용자 모드에서 커널 모드로 전환
비용	함수 호출에 따른 비용	커널 모드로 전환하는 등 함수 호출에 비해 큰 비용

시스템 호출

1) 시스템 호출

사용자 공간의 코드에서 커널 서비스를 요청하는 과정
- 사용자 공간의 코드가 커널 함수를 호출하는 과정
- 커널 콜, 트랩으로도 불림
- 응용프로그램에서 커널 기능을 활용하도록 만들어놓은 기능
시스템 호출 라이브러리 제공
- 시스템 호출 함수 혹은 커널 API
- Unix/Linux 의 커널 API - open(), read(), write(), fork(), exit()
- Windows의 커널 API - CreateProcess(), WaitForSinlgeObject()
- 대략 200개 이상
시스템 호출을 일으키는 기계 명령

CPU마다 시스템 호출을 실행하는 특별한 기계 명령 제공

2) 사례

int 0x80 - 인텔의 x86 계열의 CPU, 32비트에서 사용
syscall/sysret - ADM에서 최초 구현, 64비트에서만 작동
sysenter/sysexit - Intel 에서 최초 구현, X86/64 CPU, AMD

3) 라이브러리를 통해 간접적으로 이루어지는 시스템 호출

응용프로그램 -> 시스템 호출 라이브러리의 시스템 호출 함수 -> 시스템 호출 CPU 명령
응용프로그램 -> 표준 라이브러리 함수 -> 시스템 호출 라이브러리의 시스템 호출 함수 -> 시스템 호출 CPU 명령

printf() 가 직접 디스플레이에 출력할까?

printf() 함수는 표준 라이브러리 함수이다.
printf() 함수를 호출하면 시스템 호출이 일어날까?
- 디스플레이에 접근하는 것은 커널만 가능
- printf() 함수는 디스플레이에 직접 출력 불가능
- printf()는 C 표준 라이브러리의 버퍼에 출력
- 버퍼가 꽉 차 있으면 printf()는 시스템 호출 함수 write() 함수 호출 ( printf() 함수가 시스템 호출 함수인 write() 함수 호출해서 운영체제(커널)에 의해서 디스플레이에 출력 )
- write() 함수는 '시스템 호출 CPU 명령' 실행
- 커널에 작성된 함수가 디스플레이에 "hello" 출력

[참고 : 버퍼의 개념]

단순히 메모리상에 있는 값을 화면에 바로 출력하거나 입력한 값을 메모리상에 바로 저장하기전에 겉으로 보이지않는 *버퍼(buffer) *라는 것을 통하게 된다. 버퍼란 사전적의미 그대로 데이터 전송시 양쪽의 속도차를 보완하기 위해 만들어진 개념이다. 버퍼가 없다면 컴퓨터는 바이트단위로 데이터를 읽거나 출력하기위해 메모리에 접근하는 횟수가 엄청나게 늘어나게되고 CPU에도 부하가 많이 걸리게 될 것이다. 그래서 버퍼라는 공간에 입출력할만큼 데이터를 받아놓고 전송하게 되는 것이다.

시스템 호출 비용 : fread() 와 read() 의 비교

시스템 호출은 함수 호출에 비해 많은 시간 비용
- 시스템 호출을 많이 할 수록 프로그램 실행 속도 저하
파일에서 100바이트를 읽는 2가지 유형의 코드. 실행 비교 결과는?

1) 함수 호출 fread()와 시스템 호출 read() 비교

표준 라이브러리 함수, fread(fp, buf, size) 동작
- fread() 를 처음 호출하면 라이브러리 내 버퍼가 비어 있음
- read() 를 호출하여 라이브러리 내 버퍼를 채운다
- 라이브러리 버퍼에서 요청한 size 만큼 buf 로 복사한다.
- 라이브러리 버퍼가 비거나 부족하면 그때 read() 호출
시스템 호출 함수, read(fd, buf, size) 동작
- 시스템 호출을 이용하여 커널 코드 실행
- 커널 코드에서 디스크 읽기
- 라이브러리를 거치지 않고 바로 buf로 읽어들임

운영체제와 인터럽트

인터럽트

** 인터럽트 : CPU가 현재 하는 일을 중단하고 다른 일을 하도록 시키는 비동기적 방법

1) 하드웨어 인터럽트

장치들이 어떤 상황 발생을 CPU에게 알리는 하드웨어 신호
인터럽트 발생 -> CPU는 인터럽트 서비스 루틴 실행

2) 소프트웨어 인터럽트

CPU 명령어에 의해 하드웨어 인터럽트를 수신한 것과 동일한 처리

3) 컴퓨터에서 인터럽트 활용

마우스를 움직이거나 클릭하는 등 마우스 조작
키보드 입력
네트워크로부터 데이터 도착
하드디스크의 쓰기 종료
시스템 클럭으로부터 일정한 시간 간격으로 알림
컴퓨터의 리셋 버튼 누르기
USB 메모리 부착 혹은 해제

인터럽트 서비스 루틴

** 인터럽트 핸들러라고도 부른다. 위치 : 디바이스 드라이버나 커널 코드, 임베디드 컴퓨터 ROM

인터럽트는 다중프로그래밍의 key

다중 프로그래밍이란?
- 여러 프로세스를 동시에 실행
- 한 프로세스가 입출력을 시행하면 다른 프로세스로 교체 실행
- 입출력이 완료될 때, 장치로부터 입출력 완료 통보를 받는 방법 필요 -> 인터럽트
  - 입출력 완료를 계속 검사하는 폴링(Polling)방법은 CPU에 의해 이루어지므로 매우 비효율적 (반면 인터럽트는 CPU가 아니라 디바이스 드라이버에서 이루어짐)

이 글이 문제가 된다면 삭제하겠습니다.

[텍스트 마이닝] 14. Coreference

Tue, 24 May 2022 11:25:59 GMT

Discourse

Discourse covers linguistic expression beyond the boundary of the sentence -> 문장의 밖에서도 의미가 전달 됨 1) Dialogues : the structure of turns in conversation -> 대화 2) Monologues : the structure of entire passages, documents -> 하나의 문장이 쭉 이어진 독백

Coreference

=> You!, your father, you, him, I, your father 이 각각 누구를 가르키는지를 알아내는 게 coreference 이다.

=> she, her, it, that 등이 고유명사 entities(VICTORIA CHEN, MEGABUCKS, LOTSABUCKS) 중에서 뭐를 가리키는지 => company, 37-year-old, president ... 등이 뭐를 가리키는지

Event Coreference

Verb semantics

=> 지칭하는 대상이 다를 수도 있다.

Selectional restrictions

=> 파란색 동그라미 = mention

Mention Detection

Mention 후보들을 다 뽑아놓기 (고유명사 후보를 뽑기)
All NPs, possessive pronouns, and named entity mentions are candidate mentions. Recall is more important that precision -> 재현율이 정밀도 보다 더 중요하다.

Mention 방법 : rule-base

=> 여러 단계의 filter 를 거쳐서 결과를 낸다. => Speaker Sieve : 화자, String Match : John-John, Relaxed String Match : 애칭, Strict Head Match B,C : 같은 문장 구조

Mention-ranking models

=> 처음부터 끝까지 내려가면서 link 인지 not-link인지 확인하면서 classification 한다.

The core machinery in a mention-ranking model is parameterizing the probability of a link between two mentions

Featurized

=> i : feature, a_i : mention, x : input

Features use information about the mention type(nominal, proper, pronoun), first/last word of mention, complete mention string, words immediately to left/right of mention, distance between mentions.
Decision to link to antecedent a_i is based on a linear scoring function involving a set of learned weights w and a feature function f.
Mention 과 input의 연관성을 볼 건데, 여러 feature를 넣어주고 weight 를 조정해준다.

Neural coref

=> LSTM : 순차적으로, 두 Mention이 연결됐는지 아닌지 확인한다.

Representation for mention =
- BiLSTM output for first token in mention
  - BiLSTM output for last token in mention
  - Attention over BiLSTM output for all tokens in mention
  - Features : size of the mention

Representaion for mention pair (mi, mj) :
- m_i representaiton g_i
  - m_j representation g_j
  - elementwise
```
  product of g_i and g_j    
```
    - Features scoped over pair : distance between m_i and m_j

=> LSTM의 여러 과정을 score 매겨서 softmax 로 classification 한다.

=> 0 ~ 8 로 갈수록 distance가 멀어짐 - 그 때마다 weight parameter

[참고]

Evaluation

=> 왼쪽이 예측, 오른쪽이 정답 -> 하나씩 내려가면서 정확도/정밀도 등 평가

[텍스트 마이닝] 12. Semantic Roles

Tue, 24 May 2022 07:46:30 GMT

Why is syntax important?

Foundation for semantic analysis

Why is syntax insufficient?

syntax encodes the structure of language but doesn't directly address meaning
syntax alone doesn't "grab" in an action to take in the world

Lexical semantics

Vector representation that encodes information about the distribution of contexts a word appears in
Words that appear in similar contexts have similar representations
We can represent what individual words "mean" as a function of what other words they're related to

"Grab" = execute GrabbingFunction() -> 코드화해서 의미 전달
"the cup" = object ID 9AF1948A81CD22 -> representation

semantics

Lexical semantics is concerned with representing the meaning of words
Logical semantics is concerned with representing the meaning of sentences

Meaning representaion

A meaning representation should be unambiugous; each statement in a meaning representation should be have one meaning

First-order logic (FOL)

We want to representation every sentence as an umambiguous proposition in FOL

How we map a natural language sentence to FOL is the task of semantic parsing; but we define the FOL relations and entities to be sensitive to what matters in our model

Relations

N-art relations hold among FOL terms (constants, variables, functions) -> 더 복잡하게 가능하다.

Event semantics

[방법1]

[방법2]

[방법3]

shallow semantics

[뉴스 - twitter ... 에 따라 방법이 다를 수 있다.]

Thematic rolse

Thematic roles capture the semantic commonality among arguments for different ralations

John broke the window

The window was broken by John
이 두 문장은 syntax로만 보면 완전히 다른 문장이다.

근데, Thematic role 까지 보면 같은 문장이다.

=> "창문이 깨졌다" 가 핵심이고 위의 features 을 이용해서 부가적인 정보를 더 붙임

Thematic roles are very useful but difficlt to formally difine AGENT, THEME, etc.
At the same time, they may be too coarse for som applications

Coarsening : Proto-roles

좀 더 '일반적'으로 role을 부여 (피상적 Level)
Proto-roles = generalize thematic roles

2가지 Data

Propbank

Sentences from the Penn Treebank annotated with proto-roles, along with lexical entries for each sense of a verb identifying the specific meaning of each proto-role that verb sense
Verb-sepcific argument structures lets us map the commonalities among the different surface forms

FrameNet

Propbank maps argument structure for individual verb senses
FrameNet maps argument structure for frames, which are evoked by a lexical unit
"A frame is a data-structure for representing a stereotyped situation" - Minsky 1975

Semantic Frame

=> Lexical units 를 이용해서 Destroy 에 Frame 을 씌울 수 있다.

=> 서로 같은 뜻이지만 문장 구조가 다른 두 문장에 Frame 을 씌워서 같은 문장으로 바라볼 수 있게 된다. => 같은 sell 과 bought 가 각 문장에서 같은 것을 의미한게 된다.

[텍스트 마이닝] 11. Neural Sequence Labeling

Wed, 18 May 2022 04:27:04 GMT

sequence labeling 할 때, 이제는 HMM 안쓴다! RNN으로 다 할 수 있다!

RNNs for POS

To make a prediction for y, RNNs condition on all input seen through time t
But knowing something about the future can help -> BiRNN
BiRNN 을 가지고 POS를 수행한다.
data 가 최소 10만 개 정도 labeled 되어 있으면 RNN 이 더 강력해진다.
softmax 를 사용한다.

[참고] - OOV 같은 경우는?

OOV, unseen, unknown, word embedding 이 없다 ... 다 같은 의미
- We saw Subword information used for creationg embedding
- Another alternative is to use standard word embeddings and reason about subword information within a model.

RNNs for POS

"amazon and spotify's streaming services are going to devour apple and its music purchasing model
문장에서 멀리 있는 information 이 효과적으로 전달될 수 있나?
error 가 다시 맨 앞까지 잘 전달될 수 있나?
Recurrent networks are deep in that they involve on layer for each time step -> error 가 모든 곳에 다 전달되어야 한다.
Vanishing gradient problem : as error is back propagated through the layers of a deep netword, they tend toward 0. -> layer가 많고 깊을 수록 error 가 0에 수렴 ( 기울기 소멸 문제 )

Long short - term memory network (LSTM)

RNN 의 변형

[텍스트 마이닝] 10. Parts Of Speech

Wed, 18 May 2022 04:19:36 GMT

Parts Of Speech

parts of speech are categories of word defined distributionally by the morphological and syntactic contexts a word appears in. -> POS는 words의 category 분류인데, 형태학적, 문법적인 기준도 기준으로 들어간다.

Morphological distribution

POS often defiend by distributional properties; verbs = the class of words that each combine with the same set of affixes.

Syntatic distribution

Subsitution test : if a word is replaced by another word, does the sentence remain grammatical?
These can often be too strict ; some contexts admit subsitutability for som pairs but not others.

POS

OOV -> Out Of Vacabulary , training set 에 존재하지 않는 새로운 단어도 예측

POS tagging

state of the art
- 같은 형태여도 news 냐 literature 냐 등의 domain에 따라 달랐다.

Why is POS tagging useful?

POS indicative of syntax (문법의 척도)
POS is indicative of pronunciation (발음의 척도) : 예 ; 음성인식
Tagsets
Penn Treebank
Universal Dependencies
Twitter POS

관사 같은 경우에는 Stop words 를 이용해서 관사를 제외하기도 한다. 아무런 의미없이 개수가 많기 때문이다.
Sequence labeling
For a set of inputs x with n sequential time step, one corresponding label y for each x 1) 고전적인 방법 : HMM, HEMM, CRF -> 우리는 간단하게 HMM만 알아볼 것 2) Neural Network : RNN, LM, Transformer

Named entity recognition

wikipedia 에 등장할 만큼 상징적인 것
Named entity 를 하면 apple 이 사과가 아니라 회사라는 걸 알고, 더 많은 정보를 알려줄 수 있으므로 Named entity를 한다. ( Entity Labeling )

HMM

단순히 확률로만 판단
Pick the label each word is seen most often with in the training data

Sequences

순서가 있는 데이터에 어떻게 확률분포를 구할 것인가?

[참고] Generative vs. Discriminative models

Generative models specify a joint distribution over the labels and the data. With this you could generate new data
P( x, y ) = P( y ) P( x | y )
Naive Bayes, HMM, GAN
확률분포를 찾자!
Discriminative models specify the conditional distribution of the label y given the data x. These models focus on how to discriminate between the classes.
P ( y | x )
logistic regression, RNN, softmax
이진분류 모델을 학습시키자!

HMM

HMM은 Generative 모델

[Hidden Markov Model : HMM의 기본이론]

Markov Assumption - 이전 혹은 직전의 Context는 현재를 반영한다.
output Independent - 현재의 y는 x에 영향을 준다.

P(y)P(x|y)
P(y) : label 끼리의 관계
P(x|y) : 현재 label과 현재 word의 관계

이미 확률이 다 계산되어 있다.

Decoding

Greedy : proceed left to right, committing to the best tag for each time step (given the sequence seen so far)

Information later on in the sentence can influence the best tags earlier on. -> 이미 best 라고 구했던 tag 가 다른 문장 요소에 영향을 줄 수 있다.
Ideally, what we want is to calculate the joint probability of each path and pick the one with the highest probability. But for N time steps and K labels, number of possible paths = KN

[텍스트 마이닝] 9. Embedding(3)

Wed, 18 May 2022 04:00:36 GMT

ELMo

Learn parameters to combine the RNN output across all layers for each word in a sentence for a specific task(NER, semantic role labeling, question answering etc.). Large improvements over SOTA(State Of The Arts) for lots of NLP problems.

BERT

Learn the parameters of this model with two objectives : 1) Masked language modeling 2) Next sentence prediction

-Masked LM - Masked one word from the input and try to predict that word as the output - More powerful than an RNN LM since it can reason about context on both sides of the word being predicted - A BiRNN models context on both sides, but each RNN only has access to information from on direction.

전부 다 masked 하는 건 아니고 한 15% 정도만 하고 예측한다.

[참고]

모든 sentence의 첫번째 token은 언제나 [CLS](special classification token) 이다. 이 [CLS] token은 transformer 전체층을 다 거치고 나면 token sequence의 결합된 의미를 가지게 되는데, 여기에 간단한 classifier를 붙이면 단일 문장, 또는 연속된 문장의 classification을 쉽게 할 수 있게 됩니다. 만약 classification task가 아니라면 이 token은 무시하면 됩니다.
또한 CLS 로 같은 문서에서 왔는지 다른 문서에서 왔는지를 classification 할 수 있다.

Next sentence prediction

For a pair of sentences, predict from [CLS] representation whether they appeared sequentially in the training data

[텍스트 마이닝] 8. Embedding(2)

Wed, 18 May 2022 02:46:34 GMT

Word Embedding

pre-traiend word embeddings great for words that appear frequently in data
Unseen words are treated as UNKs and assigned zero or random vectors; everything unseen is assigned the same representation

Shared structure

Even in languages like English that are not agglutinative and aren't highly inflected, words share important structure
Even if we never see the word "unfriendly" in our data, we should be able to reason about it as: un + friend + ly

Subword Model

Rather than learning a single representation for each word type w, learn representation z for the set of ngrams that comprise it -> 분자단위 n-gram으로 쪼개서 학습시킴

How do we use word embeddings for document classification?

[참고]

Attention

weighted sum 을 이용해서 word embeddings 을 사용할 때 사용하는 개념
어떤 단어에 더 집중해야할 지에 따라 비중을 달리한다.
Define v to be a vector to be learned; think of it as an "important word" vector. The dot product here measures how similar each input vector is to that "important word" vector
Lots of variations on attention 1) Linear transformation of x into before otting with v (선형변환) 2) Non-linearities after each operation (비선형) 3) "Multi-head attention" : multiple v vectors to capture different phenomena that can be attended to in the input 4) Hierarchical attention (sentence representation with attention over words + document representation with attention over sentences (word 레벨에서 한 번보고 sentence 레벨에서 한 번 보고 ...)
Attention gives us a normalized weight for every token in a sequence that tell us how important that word was for the prediction -> 어떤 단어가 중요했는지 역으로 파악 가능
- This can be useful for visualization

RNN

With an RNN, we can generate a representation of the sequences as seen through time t.
This encodes a representation of meaning specific to the local context a word is used in.
What about the future context?
- RNN 을 이용해서 다음에 나올 단어를 예측해볼 수도 있다.
  Bidirectional RNN
A powerful alternative is make predictions conditioning both on the past and the future.
Two RNNs 1) One running left- to- right 2) Oner right- to- left
The forwadr RNN and backward RNN each output a vector of size H at each time step, which we concatenate into a vector of size 2H.

Stacked RNN

Multiple RNNs, where the output of one layer becomes the input to the next.

Contextualized embeddings

Models for learning static embeddings learn a single representation for a word type -> 지금까지 한 거
예 : word2vec, glove
단어에 대한 문맥 (순서 X) , 단어자체만 임베딩으로 이용
- 동물 bears, 과일 bears, 야구팀 마스코드 bears 가 모두 같은 벡터로 변환되는 것이 static embedding 이다.
Contextualized word representations
예 : elmo, bert, gpt
단어에 대한 문맥 (순서 O), 언어적 구조, 구조적 특징, domain의 특징 등 학습
- Big idea : transform the representation of a token in a sentence to be sensitive to its local context in a sentence and trainable to be optimized for a specific NLP task

BERT는 모든 상관관계를 Attention 을 고려하여 학습
BERT는 Transformer-besed model 인데 빈칸채우기를 하기위해서 Bidirectional RNN 을 이용하기도 하고 문장을 쪼개서 이어지는 게 말이 맞는지를 확인하기도 한다.

[텍스트 마이닝] 7. Vector Semantic

Wed, 18 May 2022 02:34:51 GMT

Vector semantics

"You shall know a word by the company it keeps"
- 문맥(context)에 의해서 단어를 파악한다.
앞서 봤던 모델들에 넣는 벡터를 어떻게 만드는지 생각해보자

Distributed representation (<-> one - hot vector)
Vector representation that encodes information about the distribution of context a word appears in
Words that appear in similar contexts have similar representations -> 비슷한 문맥은 비슷한 representation 을 가진다.
We have several different ways we can encode the notion of "context"

Term - document matrix

Cosine Similarity

We can calculate the cosine silmilarity of two vectors to judge the degree of their similarity
Euclidean distance measures the magnitude of distance between two points
Cosine similarity measures their orientation
Cosine similarity 가 0.7 ~ 0.8 정도면 비슷한 단어라고 할 수 있다.
-1 : 역방향 일치, 0 : 불일치, 1 : 일치
TF - IDF
Term frequency -inverse document frequency ( TF-IDF )
A scaling to representation a features as function of how frequently it appears in a data point but accounting for its freqency in the overall collection -> 예를 들어, a와 the 같은 관사는 별의미는 없는데 여러 문서에 많이 등장하기는 한다.

like 는 별의미가 없지만 정보가 없지만 문서에 많이 등장한다. 즉, 특정 문서를 구분할 단서가 되지 않기 때문에 like 에 대한 정보를 떨어트린다. 즉, IDF를 0으로 만들어버린다.

Intrinsic Evaluation

Relatedness : correlation between vector similarity of pair of words and human judgments -> vector similarity 와 human judgment 두 벡터의 연관성을 분석한다.
Analogical reasoning (Mikolov et al. 2013). For analogy Germany : Berlin :: France : ???, find closest vector to v("Berlin") - v("Germany") + v("France")

Sparse vectors -> Dense vectors (Word embedding)

Learning low-dimensional(약 50~300차원) representations of words by framing a predicting task : using context to predict words in a surrounding window
Transform this into a supervised prediction problem; similar to language modeling but we're ignoring order whitin the context window

Dense vectors from prediction

skipgram model(Mikolov et al. 2013) : give a single word in a sentence, predict the words in a context window around it.
- 먼저 임의의 값으로 벡터들을 초기화한 후, 특정 단어가 주어졌을 때 그 주변 단어들의 등장 확률을 증가시키는 방향으로 학습하는 알고리즘이다. 가량 I love him but he hates me. 라는 문장을 생각해보자. 여기서 him 이라는 단어를 기준으로 앞 뒤 두 단어들인 I, love, but, he의 발생 확률을 증가시키는 방향으로 학습하게 된다. ( 여기서 앞 뒤 두 단어라고 했으니 window size = 2 이다. )

비슷한 문맥에서 등장하는 context -> skip-gram 등의 방법으로 word embedding 을 만든다. -> 비슷한 context 는 비슷한 vector 값을 가지게 된다.
Mikolov et al. 2013 show that vector representations have some potential for analogical reasoning through vector arithmetic ( = Analogical inference = analogy reasoning )

Low - dimensional distributed representation

Low-dimensional, dense word representations are extradrdinarily powerful
Lets your representation of the input share statistical strength with words that behave similarly in terms of their sidtributional properties (often synonyms or words that belong to the same class)

Two kinds of training data
The labeled data for a specific task (e.g., labeled sentiment for movie reviews) : 2K labels/reviews, ~ 1.5M words-> used to train a supervised model
General text ( Wikipedia, the web, books, etc .), -> ~trillions of words -> used train word distributed representation

using dense vectors
In neural models (CNNs, RNNs, LM), replace the V-demensional sparse vector with the much smaller K-dimensional dense one.
Can alse take the derivative of the loss function with respect to those representations to optimize for a paricular task. -> dense vector로 특정 task 를 최적화하기 위해서 손실함수를 미분할 수도 있다.

[텍스트 마이닝] 6. Language Model(2)

Wed, 18 May 2022 02:18:39 GMT

Logistic regression : Classification

LM : We can use multiclass logistic regression for language modeling by treating the vocabulary as the output space
여러 가지 LM 모델들

[참고] Richer representations

Log-linear models give us the flexibility of encoding richer representations of the context we are conditioning on.
We can reason about any observations from the entire history and not just the local context

Neural LM : Classification

input x = vector concatenation of a conditioning context of fixed size k
단어 vector 를 이어붙여서 x input을 만들 수 있다.
softmax : multi classification 할 때 사용하고, 모든 y개 class 확률분포의 합이 1이 되는 함수이다.

Recurrent neural network (RNN) : Classification

Sequential data 이용할 때, RNN 주로 사용
RNN 은 순서의 특징을 잘 잡아낸다.
이전 history 를 중요도에 따라 차등 적용한다.
각 state 마다 output 출력이 가능하다. -> 번역에 사용 가능
RNN은 bigram, trigram, ... 을 넘어서 x1이 x5에 영향을 더 많이 준다면 x1의 β 값을 높인다.
s1은 이전까지의 상태의 정보를 다 담아둔 학습 벡터 -> 중요한 정보는 많이 기억하고, 관사 같이 덜 중요한 건 덜 담는다.
s1 : Current state
s0 : Previous state
x1 : Current input
g = tanh or relu / O = softmax

Training RNNs

Back Propaganda 를 통해서 학습한다.
True y와 y햇의 loss 를 매 step마다 loss가 작아지는 방향으로 update한다.
Current input 을 변형시켜서 넣어줄 수도 있다.
RNN : Generation -> RNN 이 Generation 모델로도 사용될 수 있다.
RNN은 각각의 state마다 output 을 알 수 있으니까 이 output을 위의 그림과 같이 활용하면 Generation의 방법으로 사용할 수 있다.

출처 : https://people.ischool.berkeley.edu/~dbamman/nlp21.html

[텍스트 마이닝] 5. Language Model(1)

Wed, 18 May 2022 02:06:13 GMT

Language Model

Language models provide us with a way to quantify the likelihood fo a sequence -- i.e., plausible sentences. -> 말이 되면 확률값이 높다.
P("Call me Ishmael") = P(w1 = "call", w2 = "me", w3 = "Ishmael") X P(STOP) -> v+ is the infinite set of sequences of symbols from v; each sequence ends with STOP
Language modeling is the task of estimating P(w)
예시 1) OCR : Image to Text ( Optical character recognition ) 2) Machine translation -> 1. 원본의 문장을 얼마나 추실하게 전달했느냐(충실도, Fidelity to source text) 와 2.번역된 게 얼마나 정확하냐(Fluency of the translation) 를 본다. 3) Query auto completion : 검색어 자동완성 ( 확률이 높은 순서대로 나열 ) 4) Speech recognition -> 시리, 빅스비, 아리아, 알렉사, ...

Markov assumption : Estimation

현재 혹은 다음에 올 상태는 이전의 상태(단어)들에 의해 결정된다.

Markov assumption : Generating

어떤 단어 다음에 특정 단어가 나올 확률을 Language model을 통해서 미리 계산해서 둔다.
What we learn in estimating languege models is P(word | context), where context -- at least here -- is the previous n-1 words
We have one multinomial over the vocabulary (including STOP) for each context
LM 또한 확률분포를 다루기 때문에 확률분포 값이 0이 되는 곳이 있다면 전체 확률이 0이 된다. 따라서 Smoothing 을 통해서 해결한다. -> How can best re-allocate probability mass가 또 하나의 이슈이다.

Interpolation

As ngram order rises, we have the potential for higher precision but also higher variablilty in our estimates. -> ngram에서 n이 커질 수록 정확도가 커지지만 다양성이 늘어난다.
A linear interpolation of any two language models p and q is also a valid language model -> 여러 모델을 비중을 다르게 하여 동시에 사용할 수도 있다. (예1. p= bigram, q= trigram / 예2. p = the web, q = pollitical speeches) ..
꼭 2개가 아니고 더 많은 개수를 같이 쓸 수도 있다.
- how do we pick the best values of λ? : λ -> 사람이 개입해서 바꿀 수 있다. hyper parameter 1) Grid search over development corpus 2) Expectation-Maximization algorithm

여러 가지 LM 모델들

Unigram, bigram, trigram, 4gram model, ..

Evaluation

The best evaluation metrics are external - how does a better language model influence the application you care about? -> 외부의 특정 조건 (Accuracy, Precision, ... 등등 외부 지표가 좋다)
Speech recognition (word error rate), machine translation (BLEU score) topic models (sensemaking) -> BLEU 스코어 : 번역이 잘 되었는지 평가하는 외부 지표
A good language model should judge unseen real language to have high probability
Perplexity = inverse probability of test data, averaged by word
To be reliable, the test data must be truly unseen

-> Perplexity 는 외부 지표가 없을 때 사용할 수 있는 지표인데, test set으로 검증했을 때 확률이 높아야 한다. 꼭 test set 으로 검증해야 한다.

perplexity 는 Generation의 성능을 판단하는 지표로 낮을 수록 좋다.
ngram에서 n이 커질 수록 perplexity 가 낮아진다.

출처 : https://people.ischool.berkeley.edu/~dbamman/nlp21.html

[텍스트 마이닝] 4. Classification - Neural Network

Wed, 18 May 2022 02:00:30 GMT

Neural Networks

Prediction 과 Backpropagation 의 반복이다. 처음에 Weight 값을 임의의 값으로 설정하고 y-y햇이 최소화되게끔 업데이트한다.

[참고]

Discrete, high-dimensional representation of inputs (one-hot vectors, indicator vector) -> low-dimensional distributed representation
Static representation -> contextual representations, where representations of words are sensitive to local context
Non-linear interactions of input features
Multiple layers to capture hierarchical structure

[참고] Activation function : 앞에서 주어진 신호를 다음 레이어로 보낼지 말지 결정

y-y햇 즉, 오차를 줄여나가는 과정에서 기울기 소멸 문제가 발생한다. 이 때 LeLU 함수를 활성화 함수로 사용하면 기울기 소멸 염려도 없다. 또한 가장 대중적이고 속도가 빠르다.
ReLU and tanh are both used extensively in modern system.
Sigmoid is useful for final layer to scale output between 0 and 1, but is not often used in intermediate layers

Neural Networks 의 장점

Tremendous flexibility on design choices (exchange feature engineering for model engineering) -> Model을 바꾸기 쉽다.
Articulate model structure and use the chain rule to derive parameter updates

문제점
컴퓨터로 무한정 노드를 늘릴 수가 있다. 하지만 쓸 데 없고 상대적으로 덜 중요한 곳에 계산을 사용하지말고 필요한 x에 β를 잘 (적당히) 할당할 수 있게 해야한다.
Regularization : Increasing the number of parameters = Increasing the possibility for overfitting to training data -> 과대적합을 막기 위해서 규제를 한다. 1) L2 Regularization 2) Dropout : When training on a pair, randomly remove some node and weights 3) Early stopping : Stop backpropagation before the training error is too small

Neural Networks 를 이용한 여러 가지 h를 학습시키는 방법 : Classification

다 계산하면 복잡하니까 hidden-layer의 큰 값만 뽑아내서 진행

모든 hidden layer에서 가장 큰 값으로 진행

CNN
- We can specify multiple filters; each filter is a separate set of parameters to be learned
- With max pooling, we select a single number for each filter over all tokens
- If we specity multiple filters, we can also scope each filter over different window sizes

출처 : https://people.ischool.berkeley.edu/~dbamman/nlp21.html

[텍스트 마이닝] 3. Classification - Logistic Regression

Wed, 18 May 2022 01:53:08 GMT

Logistic regression 모델로 h를 학습시키는 방법 : Classification

확률이 0이 되는 것을 막기 위해서 BIAS를 주고 이런 방식으로 h햇을 학습시킨다.

[참고]

Features
- As a discriminative classifier, logistic regression doesn't assum features are independent like Naive Bayes does. -> 독립X
- Its power partly comes in the ability to create richly expressive features without the burden of independence.
- We can represent text through features that are not just identities of individual words, but any feature that is scopred over the entirety of the input
- Features are where you can encode your won domain understanding of the problem. ( unigram, bigram .. ngram, prexies(words that start with "un-", has word that shows up in positive sentiment dictionary)
  - 단어의 단순한 유무 말고, input에 대한 정보 추가가 가능하다.
[참고] Conditional likelihood
For all training data, we want the probability of the true label y for each data point x to be high
This principle gives us a way to pick the values of the parameters β that maximize the probability of the training data -> y를 잘 근사하기 위한 파라미터 β를 잘 설정해야 한다.

[참고] β

The value β of that maximizes likelihood also maximizes the log likelihood (최대우도법)
log 를 사용하면 확률값을 다룰 때 더 용이하다.
이렇게 β 값을 최적화 하는 과정에서 기울기 감소 문제가 발생할 수 있다. -> lr 을 잘 조정해서 극복할 수 있다.

문제점

β 값을 최적화 하는 과정에서 기울기 감소 문제
- Calculate the derivative of some loss function with respect to parameters we can change, update accordingly to make predictions on training data a little less wrong next time.

상대적으로 그다지 중요하지 않은 feature 들이 영향을 크게 줄 수도 있다.

문제 해결

We could threshold features by minimun count but that also throws away information
We can take a probabilistic approach and encode a prior belief that all β should be 0 unless we have strong evidence otherwise
포괄적으로 문장을 설명할 수 있도록 한다. (너무 자세하지 않게)
L2 regularization -> feature 복잡도를 낮춘다.
L1 regularization -> 필요없는 feature 는 0으로 바꿔버린다.

출처 : https://people.ischool.berkeley.edu/~dbamman/nlp21.html