: 컴퓨터가 메인 메모리에서 사용하기 위해 2차 기억 창치로부터 데이터를 저장하고 검색하는 메모리 관리 기법.

내가 실행하고자 하는 프로그램의 용량이 5GB인데, 메모리는 4GB이다. 어떻게 실행할까?

• 올리는 것도 문제이지만, 올린다고 하더라도 해당 프로그램이 실행될 때는 다른 작업은 아무것도 하지 못하게 된다. 이럴 때, 사용하는 기술이 바로 가상 메모리이다.
• 가상 메모리는 각 프로세스당 메인 메모리와 동일한 크기로 하나씩 할당된다. 그 공간은 보조기억장치 공간을 이용한다. 프로세스의 일부만 메모리에 로드하고 나머지는 보조기억장치에 두는 형태이다.

1) 페이징(paging) 기법

• 고정 분할 방식으로 메모리를 분할하여 가상 주소를 물리 주소로 변환하는 방법

• 이때의 일정한 크기를 가진 블록을 페이지(page)라고 한다.

• 주소공간을 페이지 단위로 나누고 실제기억공간은 페이지 크기와 같은 프레임으로 나누어 사용

• 프레임(Frame) : 물리 메모리를 일정한 크기로 나눈 블록

• 페이지(Page) : 가상 메모리를 일정한 크기로 나눈 블록

• 페이지가 하나의 프레임을 할당 받으면, 물리 메모리에 위치하게 된다. 프레임을 할당 받지 못한 페이지들은 외부 저장장치에 저장되며, 이때도 프레임과 같은 크기 단위로 관리된다.

2) 세그먼테이션(Segmentation) 기법

• 프로세스를 서로 크기가 다른 논리적인 블록 단위인 '세그먼트(Segment)'로 분할하고 메모리에 배치하는 것을 말하며, 각 세그먼트의 크기는 일정하지 않다. => 가변 분할 방식

• 프로세스를 Code + Data + Stack 영역으로 나누는 것 역시 세그멘테이션의 모습이다. 물론, code, data, stack 각각 내부에서 더 작은 세그먼트로 나눌 수도 있다.

• 세그먼트를 메모리에 할당할 때는 페이지를 할당하는 것과 동일하다. 하지만, 테이블은 조금 다르다. 세그먼테이션을 위한 테이블은 세그먼트 테이블이라고 한다.

• 세그먼트 테이블은 세그먼트 번호와 시작 주소, 세그먼트 크기를 엔트리로 갖는다.

• 세그먼트에서 주소변환 역시, 페이징과 유사하다. 한 가지 주의할 점은 세그먼트의 크기는 일정하지 않기 때문에, 테이블에 limit 정보가 주어진다. 그리고 CPU에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해서 해당 프로세스를 강제로 종료시킨다.

페이징과 세그먼테이션의 차이점

• 페이징은 프로세스를 물리적으로 일정한 크기로 나눠서 메모리에 할당하는 반면에, 세그먼테이션은 프로세스를 논리적 내용을 기반으로 나눠서 메모리에 배치하므로 페이징은 내부 단편화, 세그먼테이션은 외부 단편화가 발생할 수 있다.
  
• 페이징은 code+data+stack 영역이 있을 때, 이를 일정한 크기로 나누므로 두 가지 영역이 섞일 수 있다. 그러면 비트를 설정하기가 매우 까다롭다.
  공유에서도 마찬가지다. 페이징에서는 code 영역을 나눈다해도 다른 영역이 포함될 확률이 매우 높다. 하지만, 세그먼테이션은 정확히 code 영역만을 나누기 때문에 더 효율적으로 공유를 수행할 수 있다.
  
• 세그먼테이션은 보호와 공유에서 효율적이고, 페이징은 외부 단편화 문제를 해결할 수 있다. 그러므로 두 가지를 합쳐서 사용하는 방법이 나왔다. 두 장점을 합치기 위해서는 세그먼트를 페이징 기법으로 나누는 것이다.(Paged segmentation) => 하지만 이 역시 단점이 존재한다. 세그먼트와 페이지가 동시에 존재하기 때문에 주소 변환도 두 번해야한다. 즉 CPU에서 세그먼트 테이블에서 주소 변환을 하고, 그 다음 페이지 테이블에서 또 주소 변환을 해야한다.

참고 링크텍스트 링크텍스트 링크텍스트

프로세스가 필요로 하는 페이지가 없는 경우(page-fault) 하드 디스크에서 페이지를 찾아 빈 프레임에 로딩하는데, 여기서 ‘페이지를 올릴 빈 프레임이 없을 경우’ 교체할 희생 프레임을 찾는 알고리즘 => 페이지 교체 알고리즘

FIFO(first in first out)

이해가 쉽고 구현이 간단하지만, 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있다.

• 가장 간단한 알고리즘
• 메모리에 올라온 지 가장 오래된 페이지를 교체
• 이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐(Queue)에 저장하는 방식 등을 사용

최적(Optimal) 페이지 교체

모든 알고리즘 중 가장 페이지 교체 수가 적지만, 실제로 구현이 불가능하기 때문에 다른 알고리즘과 비교 연구 목적으로 주로 사용된다.

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘
• 선행되어야 할 전제조건 : 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 것 => 구현이 불가능한 알고리즘

LRU(least-recently-used)

최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다. 미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 가장 오랜 기간 사용되지 않은(least recently used) 페이지를 교체하는 방식을 사용하는 것 -> 따라서 많은 운영체제가 채택하는 알고리즘이며, 좋은 알고리즘이라고 평가 받고있다.

• 가장 오래 사용되지 않은 페이지를 교체하는 알고리즘
• 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘

계수-기반(Counting-Based) 페이지 교체

: 페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅하는 방법

LFU(least-frequently-used)

• 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘
• 만약 교체 대상인 페이지가 여러 개 일 경우, LRU 알고 리즘을 따라 가장 오래 사용되지 않은 페이지로 교체
• LFU 알고리즘은 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문에 성능이 저하될 우려가 있다.

MFU(most-frequently-used)

• LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
• 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단

=> LFU와 MFU는 구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문에 실제 사용에 잘 쓰이지 않는다.

참고 링크텍스트

메모리(Memory)는 데이터를 기록하거나 읽기 위한 저장공간으로 크게 램(RAM)과 롬(ROM), 플래시 메모리로 분류할 수 있다.

1) 램(RAM)

• 읽고 쓰기가 가능한 주 기억장치
• 전원이 끊어지면 기억되어있는 데이터들이 소멸 : 휘발성 메모리
• 데이터를 읽는 속도와 기록하는 속도가 같음
• 주기억장치, 프로그램 로딩, 데이터 임시 저장 등과 같은 곳에 사용됨.

2) 롬(ROM)

• 전원이 끊어져도 기록된 데이터들이 소멸되지 않음 : 비휘발성 메모리
• 데이터를 저장한 후 반영구적으로 사용 가능
• 보통의 ROM은 데이터를 한번 저장하면 수정이 불가하지만, PROM(1번 다시쓰기 가능), EPROM(무한), EEPROM(무한) => 특수한 방법을 통해 데이터를 삭제한 후 데이터를 다시 기록할 수 있음.

3) 플래시(Flash) 메모리

• 플래시 메모리는 전기적으로 데이터를 지우고 다시 기록할 수 있는 비휘발성 컴퓨터 기억 장치
• EEPROM과 다르게 여러 구역으로 구성된 블록 안에서 지우고 쓸 수 있음.
• EEPROM 보다 훨씬 저렴하기 때문에 비휘발성 고체 상태 저장 매체가 상당량 필요한 곳에서 많이 사용됨.
• MP3, 디지털 카메라, 휴대폰, USB에 플래시 메모리가 사용됨.

출처 링크텍스트

• 도메인 네임 시스템(Domain Name System, DNS)은 호스트의 도메인 이름을 호스트의 네트워크 주소로 바꾸거나 그 반대의 변환을 수행할 수 있도록 하기 위해 개발되었다.
• 특정 컴퓨터(또는 네트워크로 연결된 임의의 장치)의 주소를 찾기 위해, 사람이 이해하기 쉬운 도메인 이름을 숫자로 된 식별 번호(IP 주소)로 변환해 준다. 도메인 네임 시스템은 흔히 "전화번호부"에 비유된다.
• 인터넷 도메인 주소 체계로서 TCP/IP의 응용에서, www.example.com과 같은 주 컴퓨터의 도메인 이름을 192.168.1.0과 같은 IP 주소로 변환하고 라우팅 정보를 제공하는 분산형 데이터베이스 시스템이다.

즉 DNS Server는 웹 서버 주소에 해당하는 IP 주소 테이블을 가지고 있는 서버라고 보면 됩니다. DNS 과정을 풀어 설명하면 다음과 같습니다.

1. DNS Query DNS 서버에서 Domain Name 이용하여 IP 를 받아옵니다. 이때 Domain Name Server 접속하는 유저에 대해서 Round Robin 방식으로 IP 를 할당합니다.

2. IP Communication IP 를 받아온 유저는 리퀘스트 메시지 발송을 통하여 정상적으로 네트워크 통신을 실시합니다.

DNS Round Robin

round robin 이란 DNS 서버 구성 방식 중 하나입니다. Domain 에 대한 IP 요청 쿼리 시 round-robin 방식으로 IP 를 반환합니다.

시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘입니다. 쉽게 말하면 자바에서 스레드가 운영체제의 스케쥴러에 의하여 컴퓨터 자원을 사용할 수 있는 기회를 할당 받는 것과 같은 맥락입니다. 각 프로세스에 일정시간을 할당하고, 할당된 시간이 지나면 그 프로세스는 잠시 보류한 뒤 다른 프로세스에게 기회를 주고, 또 그 다음 프로세스에게 하는 식으로, 돌아가며 기회를 부여하는 운영방식이라 풀어 말할 수 있겠습니다.

즉 DNS 서버에 대한 Round Robin 형식으로 구성할 경우 로드 벨런서가 필요가 없습니다. 부하에 대한 걱정을 할 필요가 없다는 뜻입니다. (왜냐? 자동적으로 시간에 따라서 스케쥴링이 변환되기 때문에!)

하지만 이러한 방식은 여러가지 단점을 가지고 있습니다.

1. 서버의 수 만큼 공인 IP 주소가 필요합니다. 부하 분산을 위해 서버의 대수를 늘리기 위해서는 그 만큼의 공인 IP 가 필요합니다.

2. 균등하게 분산되지 않습니다. 모바일 사이트 등에서 문제가 될 수 있는데, 스마트폰의 접속은 캐리어 게이트웨이 라고 하는 프록시 서버를 경유 합니다. 프록시 서버에서는 이름변환 결과가 일정 시간 동안 캐싱되므로 같은 프록시 서버를 경유 하는 접속은 항상 같은 서버로 접속됩니다. 또한 PC 용 웹 브라우저도 DNS 질의 결과를 캐싱하기 때문에 균등하게 부하분산 되지 않습니다. DNS 레코드의 TTL 값을 짧게 설정함으로써 어느 정도 해소가 되지만, TTL 에 따라 캐시를 해제하는 것은 아니므로 반드시 주의가 필요하다.

3. 서버가 다운되도 확인이 불가능합니다. DNS 서버는 웹 서버의 부하나 접속 수 등의 상황에 따라 질의결과를 제어할 수 없다. 웹 서버의 부하가 높아서 응답이 느려지거나 접속수가 꽉 차서 접속을 처리할 수 없는 상황인 지를 전혀 감지할 수가 없기 때문에 어떤 원인으로 다운되더라도 이를 검출하지 못하고 유저들에게 제공됩니다. 이때문에 유저들은 간혹 다운된 서버로 연결이 되기도 하죠. DNS 라운드 로빈은 어디까지나 부하분산 을 위한 방법이지 다중화 방법은 아니므로 다른 S/W 와 조합해서 관리할 필요가 있다.

이를 위한 극복 방법은 다음과 같습니다.

• 다중화 구성 방식 (Synchronous Time-Division Multiplexing) AP 서버에 VIP(Virtual IP)를 부여해서 다중화를 구성한다. 각 AP 서버를 Health Check후 이상이 감지되면 VIP를 정상 AP 서버로 인계하는 방식을 사용한다. 즉 DNS Server Table 에 실시간으로 AP 서버의 상태를 확인할 수 있는 칼럼 및 함수를 추가하여 요청될 경우 서버 상태를 확인하여 우회루트를 제공하거나 에러를 전송하는 방식을 말합니다.

• 가중치 편성 방식 (Weighted round robin) 각각의 웹 서버에 가중치를 가미해서 분산 비율을 변경한다. 물론 가중치가 큰 서버일수록 빈번하게 선택되므로 처리능력이 높은 서버는 가중치를 높게 설정하는 것이 좋다.

또 다른 방법으로는 로드 밸런서의 도입을 통하여 다음과 같은 구성도 가능합니다.

• 최소 연결 방식 (Least connection) 접속 클라이언트 수가 가장 적은 서버를 선택한다. 로드밸런서에서 실시간으로 connection 수를 관리하거나 각 서버에서 주기적으로 알려주는 것이 필요하다.

출처 및 참고 링크텍스트 링크텍스트

• HTTP란 서버/클라이언트 모델을 따라 데이터를 주고 받기 위한 프로토콜이다.
• 즉, HTTP는 인터넷에서 하이퍼텍스트를 교환하기 위한 통신 규약으로, 80번 포트를 사용하고 있다. 따라서 HTTP 서버가 80번 포트에서 요청을 기다리고 있으며, 클라이언트는 80번 포트로 요청을 보내게 된다.
• HTTP는 1989년 팀 버너스 리에 의해 처음 설계되었으며, WWW(World-Wide-Web) 기반에서 세계적인 정보를 공유하는데 큰 역할을 하였다.
• HTTP는 상태를 가지고 있지 않는 Stateless 프로토콜이며 Method, Path, Version, Headers, Body 등으로 구성된다.
• 하지만 암호화가 되지 않은 평문 데이터를 전송하는 프로토콜이므로, 보안에 취약하다. -> HTTPS 등장의 배경

< HTTP 의 문제점 >

• HTTP 는 평문 통신이기 때문에 도청이 가능하다.
• 통신 상대를 확인하지 않기 때문에 위장이 가능하다.
• 완전성을 증명할 수 없기 때문에 변조가 가능하다.

위 세 가지는 다른 암호화하지 않은 프로토콜에도 공통되는 문제점들이다.

• TCP/IP 는 도청 가능한 네트워크이다.
• TCP/IP 구조의 통신은 전부 통신 경로 상에서 엿볼 수 있다. 패킷을 수집하는 것만으로 도청할 수 있다. 평문으로 통신을 할 경우 메시지의 의미를 파악할 수 있기 때문에 암호화하여 통신해야 한다.

-> 보완 방법

: 통신 자체를 암호화 SSL(Secure Socket Layer) or TLS(Transport Layer Security)라는 다른 프로토콜을 조합함으로써 HTTP 의 통신 내용을 암호화할 수 있다. SSL 을 조합한 HTTP 를 HTTPS(HTTP Secure) or HTTP over SSL이라고 부른다.

콘텐츠를 암호화 말 그대로 HTTP 를 사용해서 운반하는 내용인, HTTP 메시지에 포함되는 콘텐츠만 암호화하는 것이다. 암호화해서 전송하면 받은 측에서는 그 암호를 해독하여 출력하는 처리가 필요하다.

• 통신 상대를 확인하지 않기 때문에 위장이 가능하다.
• HTTP 에 의한 통신에는 상대가 누구인지 확인하는 처리는 없기 때문에 누구든지 리퀘스트를 보낼 수 있다. IP 주소나 포트 등에서 그 웹 서버에 액세스 제한이 없는 경우 리퀘스트가 오면 상대가 누구든지 무언가의 리스폰스를 반환한다. 이러한 특징은 여러 문제점을 유발한다.

1. 리퀘스트를 보낸 곳의 웹 서버가 원래 의도한 리스폰스를 보내야 하는 웹 서버인지를 확인할 수 없다.
2. 리스폰스를 반환한 곳의 클라이언트가 원래 의도한 리퀘스트를 보낸 클라이언트인지를 확인할 수 없다.
3. 통신하고 있는 상대가 접근이 허가된 상대인지를 확인할 수 없다.
4. 어디에서 누가 리퀘스트 했는지 확인할 수 없다.
5. 의미없는 리퀘스트도 수신한다. —> DoS 공격을 방지할 수 없다.

   -> 보완 방법

   : 위 암호화 방법으로 언급된 SSL로 상대를 확인할 수 있다. SSL 은 상대를 확인하는 수단으로 증명서 를 제공하고 있다. 증명서는 신뢰할 수 있는 제 3 자 기관에 의해 발행되는 것이기 때문에 서버나 클라이언트가 실재하는 사실을 증명한다. 이 증명서를 이용함으로써 통신 상대가 내가 통신하고자 하는 서버임을 나타내고 이용자는 개인 정보 누설 등의 위험성이 줄어들게 된다. 한 가지 이점을 더 꼽자면 클라이언트는 이 증명서로 본인 확인을 하고 웹 사이트 인증에서도 이용할 수 있다.

• 완전성을 증명할 수 없기 때문에 변조가 가능하다

여기서 완전성이란 정보의 정확성 을 의미한다. 서버 또는 클라이언트에서 수신한 내용이 송신측에서 보낸 내용과 일치한다라는 것을 보장할 수 없는 것이다. 리퀘스트나 리스폰스가 발신된 후에 상대가 수신하는 사이에 누군가에 의해 변조되더라도 이 사실을 알 수 없다. 이와 같이 공격자가 도중에 리퀘스트나 리스폰스를 빼앗아 변조하는 공격을 중간자 공격(Man-in-the-Middle)이라고 부른다.

-> 보완 방법

: MD5, SHA-1 등의 해시 값을 확인하는 방법과 파일의 디지털 서명을 확인하는 방법이 존재하지만 확실히 확인할 수 있는 것은 아니다. 확실히 방지하기에는 HTTPS를 사용해야 한다. SSL 에는 인증이나 암호화, 그리고 다이제스트 기능을 제공하고 있다.

HTTPS(HyperText Transfer Protocol Secure)란?

• HTTP에 데이터 암호화가 추가된 프로토콜
• HTTPS는 HTTP와 다르게 443번 포트를 사용하며, 네트워크 상에서 중간에 제 3자가 정보를 볼 수 없도록 공개키 암호화를 지원하고 있다.

HTTPS의 동작과정

HTTPS는 SSL(Secure Socket Layer) or TLS(Transport Layer Security)와 같은 프로토콜을 사용하여 공개키/개인키 기반으로 데이터를 암호화하고 있다. 데이터는 암호화되어 전송되기 때문에 임의의 사용자가 데이터를 조회하여도 원본의 데이터를 보는 것은 불가능하다.

그렇다면 이제 서버는 클라이언트가 요청을 보낼 때 암호화를 하기 위한 공개키를 생성해야 하는데, 일반적으로는 인증된 기관(Certificate Authority) 에 공개키를 전송하여 인증서를 발급받고 있다. 자세한 과정은 다음과 같다. 1. A기업은 HTTP 기반의 애플리케이션에 HTTPS를 적용하기 위해 공개키/개인키를 발급함 2. CA 기업에게 돈을 지불하고, 공개키를 저장하는 인증서의 발급을 요청함 3. CA 기업은 CA기업의 이름, 서버의 공개키, 서버의 정보 등을 기반으로 인증서를 생성하고, CA 기업의 개인키로 암호화하여 A기업에게 이를 제공함 4. A기업은 클라이언트에게 암호화된 인증서를 제공함 5. 브라우저는 CA기업의 공개키를 미리 다운받아 갖고 있어, 암호화된 인증서를 복호화함 6. 암호화된 인증서를 복호화하여 얻은 A기업의 공개키로 데이터를 암호화하여 요청을 전송함 7. 암호화된 인증서는 CA의 개인키로 암호화되었기 때문에, 신뢰성을 확보할 수 있고, 클라이언트는 A 기업의 공개키로 데이터를 암호화하였기 때문에 A기업만 복호화하여 원본의 데이터를 얻을 수 있다.

HTTPS는 이러한 공개키/개인키 기반의 대칭키 암호화 방식을 활용하여 안전성을 확보하고 있다.

HTTP와 HTTPS의 장단점

• 보안이 중요한 개인정보 같은 데이터가 오가는 곳 -> HTTPS
• 데이터의 노출이 상관없고 속도가 빠른게 중요하다면 -> HTTP
• 또한 HTTPS는 인증서를 발급하고 유지하기 위한 추가 비용이 발생한다.
• 따라서 민감한 데이터를 주고 받는 곳이 아니라면 비용이나 속도적인 측면에서 HTTP가 더 유리하다. (하지만 요즘엔 속도는 별 차이가 안난다고 한다.)

출처 및 참고 링크텍스트 링크텍스트

TCP란?

• TCP(전송 제어 프로토콜 : Transmission Control Protocol)는 IP의 핵심 프로토콜 중 하나로, IP와 함께 TCP/IP라는 명칭으로도 널리 불린다.
• TCP는 전송 계층에 위치하는 네트워크의 정보 전달을 통제하는 프로토콜이다.
• TCP는 근거리 통신망이나 인트라넷, 인터넷에 연결된 컴퓨터에서 실행되는 프로그램 간에 일련의 옥텟을 안정적으로, 순서대로, 에러없이 교환할 수 있게 한다.
• TCP는 웹 브라우저들이 www에서 서버에 연결할 때 사용되며, 이메일 전송이나 파일 전송에도 사용된다.

UDP란?

• UDP(사용자 데이터그램 프로토콜 : User Datagram Protocol)는 TCP와 마찬가지로 IP의 주요 프로토콜 중 하나이며, 전송계층에 속한다.
• UDP의 전송 방식은 너무 단순해서 서비스의 신뢰성이 낮고, 데이터그램 도착 순서가 바뀌거나, 중복되거나, 심지어는 통보 없이 누락시키기도 한다.
• 따라서 UDP는 일반적으로 오류의 검사와 수정이 필요 없는 애플리케이션에서 수행할 것으로 가정한다.

TCP와 UDP의 차이

• TCP는 데이터를 주고 받을 양단 간에 먼저 연결을 설정하고 설정된 연결을 통해 양방향으로 데이터를 전송하지만, UDP는 연결을 설정하지 않고 수신자가 데이터를 받을 준비를 확인하는 단계를 거치지 않고 단방향으로 정보를 전송한다.
• 신뢰성 : TCP는 메시지 수신을 확인하지만 UDP는 수신자가 메시지를 수신했는지 확인할 수 없다.
• 순서 정렬 : TCP에서는 메시지가 보내진 순서를 보장하기 위해 재조립하지만 UDP는 메시지 도착 순서를 예측할 수 없다.
• 부하 : TCP보다 UDP의 속도가 일반적으로 빠르고 오버헤드가 적다.

참고 링크텍스트 링크텍스트

: 프로세스(process)는 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램을 말한다. 종종 스케줄링의 대상이 되는 작업(task)이라는 용어와 거의 같은 의미로 쓰인다.

• 여러 개의 프로세서를 사용하는 것 = 멀티프로세싱
• 같은 시간에 여러 개의 프로그램을 띄우는 시분할 방식 = 멀티태스킹

프로세스의 상태

커널 내에는 준비 큐, 대기 큐, 실행 큐 등의 자료 구조가 있으며 커널은 이것들을 이용하여 프로세스의 상태를 관리한다.

• 생성(create) : 프로세스가 생성되는 중이다.
• 실행(running) : 프로세스가 CPU를 차지하여 명령어들이 실행되고 있다.
• 준비(ready) : 프로세스가 CPU를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태로, CPU가 할당되기를 기다리고 있다. 일반적으로 준비 상태의 프로세스 중 우선순위가 높은 프로세스가 CPU를 할당받는다.
• 대기(waiting) : 보류(block)라고 부르기도 한다. 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태를 말한다.
• 종료(terminated) : 프로세스의 실행이 종료되었다.

스레드(thread)

: 스레드(thread)는 어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위

• 일반적으로 한 프로그램은 하나의 스레드를 가지고 있지만, 프로그램 환경에 따라 둘 이상의 스레드를 동시에 실행할 수 있다 : 멀티스레드(multithread) (↑ : 두 개의 스레드를 실행하고 있는 하나의 프로세스)

프로세스와 스레드 비교

- 공통점 : 멀티프로세스와 멀티스레드는 양쪽 모두 여러 흐름이 동시에 진행됨

- 차이점 : 멀티프로세스에서 각 프로세스는 독립적으로 실행되며 각각 별개의 메모리를 차지 <-> 멀티스레드는 프로세스 내의 메모리를 공유해 사용

- 프로세스 간의 전환 속도보다 스레드 간의 전환 속도가 빠르다.

참고 링크텍스트 링크텍스트

-> 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 모듈을 지칭

스케줄러의 종류

1. 장기 스케줄러 (= 작업 스케줄러)

: 어떤 프로세스를 준비 큐에 삽입할지 결정 (메모리와 디스크 사이의 스케줄링을 담당) 디스크에서 하나의 프로그램을 가져와 커널에 등록하면 프로세스가 되는데, 이때 디스크에서 어떤 프로그램을 가져와 커널에 등록할지(준비 큐에 등록할지) 결정

• 수십 초 내지 수 분 단위로 가끔 호출되므로 상대적으로 느린 속도를 허용

프로세스의 상태 : new -> ready (in memory)

2. 단기 스케줄러 (= CPU 스케줄러)

: 준비 상태의 프로세스 중에서 어떤 프로세스를 다음 순서로 실행할 것인지 결정 (cpu와 메모리 사이의 스케줄링을 담당)

• 일반적으로 스케줄러 = 단기 스케줄러
• 단기 스케줄러는 미리 정한 스케줄링 알고리즘에 따라 cpu를 할당할 프로세스를 선택
• 단기 스케줄러는 밀리 세컨드(ms) 이하의 시간 단위로 매우 빈번하게 호출 -> 수행 속도가 충분히 빨라야 함

프로세스의 상태 : ready -> running -> waiting -> ready

3. 중기 스케줄러

: 너무 많은 프로세스에게 메모리를 할당해서 시스템의 성능이 저하되는 경우 이를 해결하기 위해 메모리에 적재된 프로세스의 수를 동적으로 조절하기 위해 추가된 스케줄러

• 메모리에 많은 수의 프로세스가 적재하면 프로세스 당 보유하고 있는 메모리량이 극도로 적어짐
• CPU 수행에 당장 필요한 프로세스의 주소 공간조차도 메모리에 올려놓기 어려운 상황이 발생
• 디스크 I/O가 수시로 발생
• 시스템의 성능이 심각하게 저하됨
• 메모리에 올라와 있는 프로세스 중 일부의 메모리를 통째로 빼앗아 그 내용을 디스크의 스왑 영역에 저장

  -> 스왑 아웃(swap out)

중기 스케줄러의 등장으로 프로세스의 상태에는 중지 상태가 추가되었으며, 중지 상태의 프로세스는 메모리를 통째로 빼앗기고 디스크로 스왑 아웃된다.

중지 준비 상태 : 준비 상태의 프로세스가 중기 스케줄러에 의해 디스크로 swap out

봉쇄 중지 상태 : 봉쇄 상태의 프로세스가 중기 스케줄러에 의해 디스크로 swap out

중지 봉쇄 상태이던 프로세스가 봉쇄 되었던 조건을 만족하게 되면 이 프로세스의 상태는 중지 준비 상태로 바뀌게 된다 중지 상태에 있는 프로세스들은 중지 준비 상태이든 중지 봉쇄 상태이든 관계없이 메모리를 조금도 보유하지 않고 디스크에 통째로 스왑 아웃된 상태로 존재하게 된다.

프로세스의 상태 : ready -> suspended

참고 링크텍스트 링크텍스트

- 힙은 형제 노드 간의 규칙이 없으며, 부모와 자식의 크기 비교만 있기 때문에 자식으로 들어오는 순서는 왼쪽, 오른쪽 순서로 들어오게 된다.

- 배열로 구현

- 왼쪽 자식 인덱스 = 부모인덱스*2

- 오른쪽 자식 인덱스 = 부모인덱스*2+1

최소 힙 (min heap)

부모 노드 값 < 자식 노드 값 : 루트가 최솟값

최대 힙 (max heap)

부모 노드 값 > 자식 노드 값 : 루트가 최댓값

Heapify

: insert 또는 delete 연산 수행 시 heap의 속성을 유지하기 위한 과정 heap의 속성에 따라 부모와 자식 간의 값 비교를 통해 heap에 위배되면 값을 바꿔주며 heap의 속성이 만족할 때까지 반복한다.

get, insert, delete : O(logn), 전체 정렬 O(nlogn)

Tree Map은 앞서 포스팅한 Red-Black Tree의 구조로 이루어져 있다.

따라서 Key의 값을 기준으로 레드블랙 트리의 규칙에 따라 정렬이 이루어져 있다.

Tree Set도 Red-Black Tree의 구조로 이루어져있지만, Tree Set은 값만 저장되어 있다면, Tree Map은 Map의 구조가 더해져서 key-value의 쌍으로 값이 저장된다.

레드블랙 트리에 따라 부모노드보다 작은 것은 왼쪽 자식, 큰 것은 오른쪽 자식이 된다.

자동으로 정렬을 해주기 때문에 Map보다는 성능이 떨어지지만, 정렬이 필요한 경우에는 더 효율적으로 활용할 수 있다.

Priority Queue (Heap)

우선순위 큐는 Heap 기반으로 부모는 자식 노드보다 항상 작아야 한다.(최소 힙 기준)

이런 힙의 특성을 따라 데이터의 최소 또는 최대값을 항상 O(1)의 시간으로 찾을 수 있다.

저장하는 데이터에 따라 우선순위가 되는 기준을 정하여 관리할 수 있지만, 전체 데이터의 탐색은 불가능하다.

하지만 우선순위 큐는 형재 노드간의 규칙은 없기 때문에 최소힙이라면 최솟값, 최대힙이라면 최댓값은 O(1)이지만, 하나의 우선순위 큐로 최소와 최대를 한번에 O(1)로 구할 순 없다. 이렇게 하려면 하나의 데이터를 가지고 최소힙과 최대힙 2가지를 만들어서 사용해야 한다. (<-> Tree Map은 최소와 최대를 한번에 둘 다 구할 수 있다.)

이진탐색 트리 : 부모노드보다 값이 작은 것은 왼쪽 자식, 값이 더 크다면 오른쪽 자식으로 값을 저장한다. (문제점 : 20, 30, 40, 50 순서로 들어온다면 오른쪽으로 치우친 트리가 된다.)

일반적인 이진탐색 트리는 트리의 높이만큼 시간이 필요하므로, 데이터의 삽입이 한쪽으로만 치우치는 경우 트리의 높이가 높아져서 성능이 저하되는 문제가 발생한다.

레드 블랙 트리는 이를 보완하기 위해 정해진 규칙에 따라 트리를 관리하며 트리의 균형을 맞추어 높이를 효율적으로 만들어준다. -> Balanced binary search tree

레드 블랙 트리에는 4가지 규칙이 존재한다.

1. 루트는 블랙이다.

2. 모든 리프(NIL)는 블랙이다.

3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

4. 루트부터 리프노드까지의 블랙 노드의 개수는 같다.

이진탐색 트리는 트리의 높이에 따라 시간복잡도가 좌우되므로 트리의 높이를 균형있게 관리할 수 있다는 것에 따라 레드블랙트리가 현존하는 이진 탐색 트리 중 성능이 가장 좋다고 한다.

• 루트부터 리프까지의 블랙노드의 수가 동일하다는 규칙에 따라 트리의 가장 짧은 높이(모두 블랙노드일 경우)와 가장 긴 높이(블랙-레드의 반복)의 차이는 최대 2배가 안된다는 것이 보장된다.

• 따라서 삽입, 삭제의 경우에도 최선의 상황에서는 O(1), 최악의 상황(아래의 예시)이 오더라도 시간복잡도는 O(logn)으로 좋은 성능을 자랑한다.

• 삽입 시, 삽입되는 노드는 무조건 레드로 삽입된다. 삽입되는 노드의 부모노드가 블랙노드일 경우에는 괜찮지만, 레드노드일 경우에는 3번 규칙에 위배되므로 재배열 또는 색상변경이 필요하다. 이 경우는 부모노드의 형제노드가 블랙인 경우와 레드인 경우에 따라 다르게 처리된다.

<부모노드의 형제노드가 블랙인 경우 - 재배치>

1. 나(삽입노드)와 부모, 부모의 부모 노드 3개를 정렬하여 가운데 값을 부모로 설정한다.
2. 부모로 설정된 노드는 블랙, 자식은 레드로 설정한다.
3. 형제노드인 w노드를 왼쪽아래에 삽입한다.

-> 변환 후에도 블랙노드의 수가 변하지 않기 때문에 한번의 Restructuring으로 해결 가능 Restructuring : O(1), 삽입 : O(logn) 이므로 총 O(logn)의 시간복잡도가 생김

<부모노드의 형제노드가 레드인 경우 - 색상변경>

1. 나(삽입노드)의 부모와 부모형제 노드를 블랙으로 만들고, 부모의 부모를 레드로 바꿈

• 하지만 부모의 부모가 루트였다면? 1번 규칙이 위배 -> 루트를 블랙으로 변환
• 루트가 아니지만 부모의 부모의 부모가 또 레드라면? 3번 규칙이 위배 -> 다시 Recoloring -> 이것이 루트까지 반복될 수 있음

따라서 Recoloring은 한번으로 끝나지 않을 수 있다. Recoloring : O(logn), 삽입 : O(logn) 이므로 결과적으로는 O(logn)이 성립된다.

:: 결국 Restructuring이 생기든 Recoloring이 생기든 O(logn)으로 처리 가능