the-ze

페이지 교체 정책(Page Replacement Policy)은 가상 메모리 시스템에서 메모리가 꽉 찼을 때, 어떤 페이지를 제거하고 새 페이지를 물리 메모리에 적재할지 결정하는 방법이다. 이 정책은 시스템의 성능과 효율성에 중요한 영향을 미친다. 여러 페이지 교체 알고리즘이 있으며, 각기 다른 상황에 적합하다.

FIFO(Fist-In, Fist-Out)은 가장 오래 전에 메모리에 적재된 페이지를 먼저 교체한다. 구현이 간단하지만, 자주 사용되는 페이지를 교체할 위험이 있다.

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체한다. 최근 사용 패턴을 기반으로 효율적인 페이지 교체를 제공하지만, 구현이 복잡하다.

페이지 참조 시퀀스가 123412512345일 때:

LFU(Least Frequently Used)는 가장 적게 사용된 페이지를 교체한다. 사용 빈도를 기반으로 하지만, 최근 사용 패턴을 반영하지 못하는 단점이 있다.

NRU(Not Recently Used)는 페이지가 최근에 사용되었는지 여부를 기준으로 교체 대상을 결정한다. 각 페이지마다 참조 비트(reference bit)를 두어, 페이지가 접근되면 이 비트를 설정한다. 주기적으로 운영 체제는 이 비트를 클리어하여, 어떤 페이지가 최근에 사용되지 않았는지를 판단한다. 교체 시점에, 참조 비트가 클리어된 페이지(즉, 최근에 사용되지 않은 페이지) 중에서 교체 대상을 선택한다. NRU는 구현이 간단하고 효율적이지만, 최적의 페이지 교체를 보장하지는 않는다.

NFU(Not Frequently Used)는 각 페이지가 시스템 내에서 얼마나 자주 사용되었는지를 기준으로 교체 대상을 결정한다. 페이지마다 카운터를 두고, 시간이 지날 때마다 페이지가 참조되면 해당 페이지의 카운터를 증가시킨다. 교체가 필요할 때, 가장 카운터 값이 낮은 페이지(즉, 가장 자주 사용되지 않은 페이지)를 교체 대상으로 선택한다. NFU는 사용 빈도를 기반으로 하므로 시간이 지남에 따라 정확도가 높아지지만, 오랜 시간 동안 시스템에 머물렀던 페이지가 불이익을 받을 수 있다는 단점이 있다.

최적 페이지 교체 알고리즘(Optimal Page Replacement)는 미래에 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이상적인 알고리즘이지만, 실제 시스템에서는 미래의 접근 패턴을 예측할 수 없어 구현이 불가능하다.

Clock(Circular Queue)는 FIFO와 유사하되, 각 페이지에 사용 여부를 나타내는 플래그를 사용한다. '시계' 방식으로 순환하며, 사용되지 않은 페이지(플래그가 0인 페이지)를 찾아 교체한다. LRU의 근사 알고리즘으로, 구현이 비교적 간단하면서도 효과적이다.

페이지 참조 시퀀스가 123412512345일 때:

벨라디의 역설(Belady's Anomaly)은 페이지 교체 알고리즘에서 관찰될 수 있는 현상으로, 가상 메모리 시스템에서 물리 메모리의 프레임 수를 증가시킬 때, 예상과 달리 페이지 폴트의 수가 증가하는 상황을 말한다. 이 역설은 특히 FIFO(First-In, First-Out) 페이지 교체 알고리즘에서 두드러지게 나타난다.

일반적으로, 물리 메모리의 크기가 커지면 더 많은 페이지를 저장할 수 있게 되어 페이지 폴트의 수가 감소할 것으로 예상된다. 그러나 벨라디의 역설에서는 메모리 프레임의 수를 증가시키는 것이 오히려 페이지 폴트 수를 증가시킬 수 있음을 보여준다. 이 현상은 FIFO 알고리즘의 특성상, 메모리에 더 많은 페이지를 보관할 수 있게 되면서, 최근에 사용된 페이지가 아닌 오래된 페이지를 메모리에 유지하는 경향 때문에 발생한다.

벨라디의 역설은 모든 페이지 교체 알고리즘에서 발생하는 것은 아니다. LRU(Least Recently Used)나 OPT(Optimal Page Replacement) 같은 일부 알고리즘은 이러한 역설적인 상황을 겪지 않는다. 이 알고리즘들은 각각 최근에 가장 적게 사용된 페이지, 또는 미래에 가장 오랫동안 사용되지 않을 페이지를 교체함으로써 메모리 프레임의 수가 증가함에 따라 페이지 폴트 수가 감소하거나 최적화되는 경향을 보인다.

벨라디의 역설은 페이지 교체 전략을 설계하고 선택할 때 주의해야 할 중요한 이론적 관점을 제공한다. 이 역설을 통해 알 수 있는 교훈은 물리 메모리의 크기를 증가시킨다고 해서 항상 시스템의 성능이 향상되는 것은 아니라는 점이다. 따라서, 효과적인 메모리 관리 전략을 위해서는 적절한 페이지 교체 알고리즘의 선택이 중요하다.

교체 알고리즘이 FIFO이고 페이지 참조 시퀀스가 123412512345일 때:

output :

[[1], [1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 1], [4, 1, 2], [1, 2, 5], [1, 2, 5], [1, 2, 5], [2, 5, 3], [5, 3, 4], [5, 3, 4]] 페이지 폴트 수 : 9

프레임 크기가 3일 때, 페이지 폴트 수가 9개가 나온다. 

output : [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 1], [4, 5, 1, 2], [5, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5]] 페이지 폴트 수 : 10

프레임 크기를 4로 늘렸는데도 불구하고, 페이지 폴트 수가 10으로 더 늘어난 모습이다.

Demand-zero 페이지는 컴퓨터 시스템에서 가상 메모리 관리 기법 중 하나이다. 프로세스가 실제로 페이지를 참조하기 전까지는 해당 페이지를 물리적 메모리에 할당하지 않는다. 대신, 프로세스가 특정 페이지에 접근을 시도할 때 해당 페이지가 물리적 메모리에 없으면 페이지 폴트(page fault)가 발생한다. 이때 운영 체제는 요청된 페이지를 디스크에서 찾아 물리적 메모리에 로드하고, 프로세스는 그 페이지를 사용할 수 있게 된다.

Demand-zero 페이지의 주요 장점은 메모리 사용의 효율성을 높일 수 있다는 것이다. 실제로 필요할 때까지 메모리를 할당하지 않기 때문에, 미사용 페이지에 대한 메모리 낭비를 줄일 수 있다. 이 방식은 특히 메모리 자원이 제한적인 시스템이나 많은 수의 프로세스를 동시에 실행해야 하는 시스템에서 유용하다. 다만, 페이지 폴트가 발생했을 때 디스크에서 메모리로 페이지를 로드하는 과정이 필요하기 때문에, 페이지 폴트 처리 시간이 시스템의 성능에 영향을 줄 수 있다. 따라서, 시스템 설계 시 메모리 관리 전략을 잘 선택하고, 페이지 폴트 발생 빈도를 최소화하는 최적화 작업이 중요하다.

파일-백드 페이지(file-backed page)는 가상 메모리 시스템에서 사용되는 개념으로, 가상 주소 공간의 페이지가 실제 파일의 내용으로 백업되는 경우를 말한다. 이러한 페이지는 일반적으로 실행 가능 파일이나 라이브러리 파일 같은 영구 저장소에 있는 데이터로 채워진다. 파일-백드 메커니즘은 특히 메모리 매핑 파일(memory-mapped file) 기술과 밀접하게 연관되어 있다.

파일-백드 페이지는 디스크 상의 파일에 대응되므로, 프로세스 간에 공유될 수 있으며, 시스템이 재부팅되어도 데이터가 유지된다. 이 기법을 사용하면, 파일의 일부를 메모리에 로드하고 접근하는 과정이 최적화될 수 있어, 파일 I/O 작업이 줄어들고 성능이 향상될 수 있다.

프로세스가 파일-백드 페이지에 접근하려 할 때 해당 페이지가 메모리에 없으면 페이지 폴트가 발생한다. 운영 체제는 해당 파일의 적절한 부분을 메모리로 로드하여 페이지 폴트를 해결한다. 메모리 매핑된 파일을 사용하여, 다른 프로세스들이 파일의 내용을 통해 데이터를 공유하고 통신할 수 있다.

프로그램이 파일을 메모리에 매핑할 때, 해당 파일의 내용은 파일-백드 가상 페이지로 관리된다. 이를 통해 파일 내용에 대한 읽기와 쓰기 작업을 메모리 접근처럼 수행할 수 있다. 운영 체제는 공유 라이브러리나 실행 가능 파일을 프로세스의 가상 주소 공간에 매핑하여, 필요한 코드와 데이터를 메모리로 로드한다. 이 과정에서 파일-백드 페이지가 사용된다.

파일-백드 페이지는 필요한 경우에만 메모리로 로드되기 때문에, 스왑 공간의 사용을 줄이고 시스템의 전반적인 성능을 개선할 수 있다.

Anonymous 페이지는 가상 메모리 시스템에서 사용되는 용어로, 파일이나 다른 백업 스토리지에 직접 매핑되지 않는 메모리 페이지를 의미한다. 이러한 페이지는 주로 프로세스의 힙(heap)이나 스택(stack)과 같이 실행 중에 동적으로 할당되는 데이터를 저장하는 데 사용된다. 예를 들어, 프로그램에서 동적 할당을 통해 메모리를 요청하면 운영 체제는 이러한 요청을 충족시키기 위해 anonymous 페이지를 할당할 수 있다.

Anonymous 페이지는 디스크 상의 파일에 매핑되지 않기 때문에, 프로그램의 실행 파일이나 데이터 파일과는 직접적인 관련이 없다. 대신, 이 페이지들은 실행 시간에 프로세스의 메모리 요구에 의해 동적으로 생성된다.

대부분의 운영 체제는 안전성을 위해 anonymous 페이지를 할당할 때 'zero-fill' 정책을 사용하여 페이지 내용을 0으로 초기화한다. 이는 새로 할당된 메모리가 이전에 사용되었던 데이터를 포함하지 않도록 보장한다.

메모리가 부족할 때, 운영 체제는 스왑(swap) 영역이나 페이지 파일을 사용하여 anonymous 페이지를 디스크로 스왑 아웃할 수 있다. 나중에 해당 페이지에 다시 접근할 필요가 있을 때, 운영 체제는 디스크에서 해당 페이지를 다시 메모리로 스왑 인한다.

프로그램에서 malloc, calloc, new 등의 함수를 사용하여 메모리를 동적으로 할당할 때, 이러한 할당은 대개 anonymous 페이지를 통해 이루어진다.

Lazy loading은 컴퓨터 프로그래밍에서 자주 사용되는 최적화 기법 중 하나로, 객체, 데이터, 또는 다른 리소스를 실제로 필요로 하는 순간까지 로딩을 지연시키는 방식이다. 이 기법은 주로 웹 개발, 소프트웨어 개발, 그리고 운영 체제의 메모리 관리에서 사용된다. Lazy loading의 주 목적은 시스템의 성능을 향상시키고, 리소스 사용을 최적화하여 사용자 경험을 개선하는 것이다.

웹 개발에서 lazy loading은 특히 이미지, 스크립트, 비디오 등의 리소스를 페이지 로드 시점이 아닌, 사용자가 해당 리소스를 필요로 하는 순간에 로드하는 데 사용된다. 예를 들어, 사용자가 스크롤을 내려 이미지가 보여야 할 위치에 도달했을 때 해당 이미지를 로드한다. 이 방식은 초기 페이지 로딩 시간을 줄이고, 네트워크 트래픽을 줄이며, 서버의 부하를 경감하는 데 도움을 준다.

소프트웨어 개발에서는 객체나 모듈을 실제로 사용할 때까지 로딩을 지연시키는 방식으로 리소스 사용을 최적화한다. 예를 들어, 특정 기능이 사용자에 의해 요청될 때만 해당 기능을 구현하는 클래스의 인스턴스를 생성하거나, 모듈을 로드한다. 이는 메모리 사용을 줄이고, 애플리케이션의 시작 시간을 단축시키는 효과를 가진다.

운영 체제의 메모리 관리에서도 lazy loading 기법이 사용될 수 있다. 예를 들어, 프로그램이 시작될 때 모든 데이터와 코드를 메모리에 로드하는 대신, 실제로 필요한 부분만 메모리에 로드하고, 나머지는 필요해질 때까지 로딩을 지연시킨다. 이는 효율적인 메모리 사용을 가능하게 하며, 전체 시스템의 성능을 향상시킬 수 있다.

페이지 테이블(Page table)은 가상 메모리 시스템에서 중요한 구성 요소로, 가상 주소를 실제 물리 메모리 주소로 매핑하는 정보를 담고 있다. 컴퓨터 시스템에서 프로그램은 가상 주소 공간에서 실행되며, 이 가상 주소 공간은 실제 물리 메모리에 매핑된다. 페이지 테이블은 이러한 매핑 정보를 제공하며, 운영 체제의 메모리 관리 부분에 의해 관리된다.

• 가상 페이지 번호(Virtual Page Number, VPN): 가상 주소를 페이지로 나누었을 때, 해당 페이지의 번호.
• 물리 프레임 번호(Physical Frame Number, PFN): 실제 물리 메모리에서 해당 페이지가 위치하는 프레임의 번호.
• 접근 권한: 페이지에 대한 읽기, 쓰기, 실행 권한을 정의한다.
• 유효 비트(Valid Bit): 해당 페이지가 물리 메모리에 존재하는지 여부를 나타낸다. 유효하지 않은 경우 페이지 폴트가 발생한다.
• 수정 비트(Modified Bit or Dirty Bit): 해당 페이지가 수정되었는지 여부를 나타내며, 페이지 교체 정책에서 중요하게 사용된다.

CPU가 발생시킨 가상 주소는 페이지 번호와 오프셋으로 구분된다. 페이지 테이블은 이 페이지 번호를 사용하여 해당 페이지가 물리 메모리의 어느 프레임에 매핑되어 있는지 확인한다. 변환된 물리 주소(물리 프레임 번호 + 오프셋)를 사용하여 실제 메모리에 접근한다. 요청된 페이지가 메모리에 없을 경우(유효 비트가 설정되지 않음), 페이지 폴트가 발생하고, 운영 체제는 해당 페이지를 디스크에서 물리 메모리로 로드한다.

대규모 가상 메모리를 관리하기 위해, 페이지 테이블은 종종 계층적 구조로 구성되거나, TLB(Translation Lookaside Buffer)와 같은 캐시 메커니즘을 사용하여 주소 변환 과정을 최적화한다. 이러한 최적화는 메모리 접근 시간을 줄이고, 시스템의 전반적인 성능을 향상시킨다.

매핑(Mapping)은 소프트웨어나 하드웨어에서 사용하는 가상 주소와 물리적 주소 사이의 관계를 설정하는 과정입니다. 가상 메모리 시스템에서, 프로그램이 사용하는 가상 주소를 실제 메모리(RAM)의 물리적 주소로 변환하는 것이 대표적인 예이다.

페이징(Paging)은 가장 흔히 메모리 관리에서 사용되는 페이징은 가상 메모리 시스템에서 실제 메모리(RAM)를 더 효율적으로 사용하기 위해 고안된 기법이다. 이는 메모리를 고정된 크기의 블록(페이지)으로 나누고, 프로그램이 사용하는 가상 주소 공간을 이 페이지에 매핑하여 관리한다. 페이징을 통해, 시스템은 필요한 페이지만 메모리에 적재하고, 나머지는 디스크에 저장함으로써 메모리 사용을 최적화할 수 있다.

페이지 폴트(page fault)는 가상 메모리 시스템에서 발생하는 현상이다. 프로세스가 접근하려는 페이지가 물리 메모리(RAM)에 없을 때 발생한다. 이는 해당 페이지가 디스크에 위치하거나, 아직 메모리에 할당되지 않은 상태일 수 있다. 페이지 폴트가 발생하면, 운영 체제는 필요한 페이지를 디스크에서 찾아 물리 메모리로 로드한다. 이 과정을 통해 프로그램은 계속 실행될 수 있다.

페이지 폴트는 모든 가상 메모리 시스템에서 자연스러운 현상이지만, 빈번하게 발생하면 시스템의 성능에 부정적인 영향을 미칠 수 있다. 페이지 폴트가 많이 발생한다는 것은 프로세스가 필요로 하는 데이터나 코드가 물리 메모리에 적절히 위치하지 않고, 디스크 접근이 잦다는 것을 의미한다. 이러한 상황을 최소화하기 위해, 운영 체제는 페이지 교체 알고리즘을 사용하여 어떤 페이지를 메모리에 유지하고 어떤 페이지를 디스크로 내보낼지 결정한다.

세그멘테이션 폴트(segmentation fault)는 프로그램이 자신에게 허용되지 않은 메모리 영역에 접근하려고 할 때 발생하는 오류다. 이는 프로그램의 안정성과 보안을 위협할 수 있으며, 일반적으로 운영 체제에 의해 프로그램이 비정상적으로 종료된다.

세그멘테이션 폴트는 기화되지 않은 포인터나 이미 해제된 메모리를 참조할 때, 배열의 범위를 넘어서는 위치에 접근하려고 할 때, 혹은 읽기 전용 메모리에 쓰기 시도나 실행할 수 없는 메모리 영역에서 코드를 실행하려고 할 때 발생한다.

스와핑(swapping)은 메모리 관리 기법 중 하나이다. 이 기법은 시스템의 가용 메모리가 부족할 때, 메모리에 있는 데이터나 프로세스를 하드 디스크와 같은 보조 저장 장치로 옮기는 과정을 말한다. 스와핑을 통해, 시스템은 메모리를 더 효율적으로 사용할 수 있게 된다.

운영 체제는 메모리가 부족하다고 판단할 때, 현재 메모리에서 사용 빈도가 낮은 데이터나 프로세스를 선정한다. 선정된 데이터나 프로세스는 보조 저장 장치로 이동된다. 이 과정을 스와핑 아웃(swap out)이라 한다. 필요할 때, 보조 저장 장치에 저장된 데이터나 프로세스를 다시 메모리로 가져온다. 이 과정을 스와핑 인(swap in)이라 한다.

스와핑은 시스템의 전반적인 성능에 영향을 줄 수 있다. 보조 저장 장치는 메모리에 비해 접근 속도가 느리기 때문에, 스와핑 작업이 빈번하게 발생하면 시스템의 반응 시간이 길어질 수 있다. 이를 스와핑 스트레스라고 하며, 시스템의 성능 저하의 원인이 될 수 있다.

스레싱(thrashing)은 운영체제에서 멀티태스킹 환경에서 발생할 수 있는 문제로, 시스템의 자원을 대부분 페이지 교체나 스왑 아웃, 스왑 인 같은 메모리 관리 작업에 사용하게 되어 실제 유용한 작업 처리량이 급격히 감소하는 현상을 말한다. 이는 시스템에 너무 많은 프로그램이 동시에 실행되어 메모리 요청이 메모리 용량을 초과할 때 주로 발생한다. 결과적으로 CPU는 대부분의 시간을 유효한 데이터를 찾아 메모리와 스왑 공간(swap space) 사이를 이동하는 데 소비하게 되며, 이로 인해 시스템의 전반적인 성능이 크게 저하되는 것을 말한다.

캐시(Cache)는 컴퓨터 아키텍처에서 데이터나 명령어를 미리 복사해 놓는 임시 저장 공간을 말한다. 이 저장 공간은 CPU 내부나 그와 매우 가까운 곳에 위치하여, CPU가 주기억장치(RAM)이나 다른 보다 느린 저장 장치보다 빠르게 데이터에 접근할 수 있도록 돕는다. 캐시의 주된 목적은 시스템의 성능을 향상시키는 것이며, 이는 데이터 접근 시간을 줄임으로써 가능해진다.

캐시는 매우 빠른 속도로 데이터를 제공할 수 있는데, 이는 CPU가 필요로 하는 데이터를 캐시에서 직접 가져올 수 있기 때문이다. 캐시는 주기억장치에 비해 상대적으로 작은 용량을 가지고 있다. 이는 높은 속도의 메모리가 비싸기 때문이다. 캐시는 CPU에 매우 가까이 위치하여 빠른 데이터 전송을 가능하게 한다.

현대의 컴퓨터 시스템에서는 보통 여러 레벨의 캐시(L1, L2, L3)를 사용한다. 이 레벨은 캐시의 속도와 크기, CPU로부터의 거리에 따라 다르다. 캐시는 자주 사용되는 데이터나 명령어를 저장함으로써, CPU가 같은 데이터나 명령어에 대해 반복적으로 느린 주기억장치에 접근하는 것을 방지한다. 이러한 방식으로 시스템의 전반적인 성능을 향상시킨다.

MMU(Memory Management Unit)는 CPU와 메모리 사이에 위치하여 물리적 및 가상 메모리 주소 간의 변환을 담당한다. 가상 메모리 주소를 물리적 메모리 주소로 변환한다. 이는 프로그램이 물리적 메모리 위치를 직접 알 필요 없이 실행될 수 있게 한다.

다른 프로그램의 메모리 영역에 무단으로 접근하는 것을 방지하여 시스템의 안정성과 보안을 유지한다. 가장 효율적인 메모리 접근을 위해 캐시의 사용을 관리한다.

TLB (Translation Lookaside Buffer)는 MMU의 일부로, 가장 최근에 사용된 주소 변환의 결과를 저장하는 작은 캐시다. 가상 주소를 물리적 주소로 변환하는 데 필요한 시간을 줄이기 위해, 자주 사용되는 변환 정보를 저장한다. TLB를 통해 메모리 접근 시간을 줄이고, 시스템의 전반적인 성능을 향상시킨다. TLB가 변환 정보를 가지고 있지 않은 경우에만 MMU가 전체 메모리 변환 과정을 수행한다.

TLB의 효율성은 'TLB hit rate'라는 메트릭으로 측정되는데, 이는 전체 메모리 접근 중 TLB가 변환 정보를 이미 가지고 있어 바로 제공할 수 있는 비율을 의미한다. TLB hit rate가 높을수록 시스템 성능이 더 좋다. MMU와 TLB는 함께 작동하여 메모리 접근 시간을 최적화하고, 프로그램이 효율적으로 실행되도록 한다.

가상 메모리는 컴퓨터 시스템에서 물리적 메모리(주기억장치) 크기를 초과하는 프로그램을 실행할 수 있게 해주는 메모리 관리 기법이다. 이 기술은 물리적 메모리와 보조기억장치(예: 하드 드라이브, SSD)의 일부를 결합해, 마치 더 큰 단일 메모리 공간이 있는 것처럼 운영 체제와 응용 프로그램에게 제공한다.

가상 메모리는 페이지(데이터의 작은 블록)를 기반으로 작동한다. 필요한 페이지는 물리적 메모리로 로드되고, 필요하지 않은 페이지는 보조기억장치로 이동된다. 프로그램은 가상 주소를 사용해 메모리에 접근한다. CPU 내부의 메모리 관리 장치(MMU)는 이 가상 주소를 물리적 주소로 변환한다.

프로그램은 실제 물리적 메모리보다 더 큰 메모리 공간을 사용할 수 있어, 복잡한 작업과 큰 데이터 집합을 처리할 수 있다. 각 프로그램은 독립적인 가상 메모리 공간을 가지므로, 한 프로그램의 오류가 다른 프로그램이나 운영 체제에 영향을 미치지 않는다.

가상 주소를 물리적 주소로 변환하는 과정과 페이지 교체 과정은 시간이 소요되며, 이는 시스템의 전반적인 성능 저하로 이어질 수 있다.

레지스터와 메모리는 컴퓨터 시스템에서 데이터를 저장하고 처리하는 데 필수적인 두 가지 리소스이며 휘발성이라는 공통점을 가진다. 이 두 리소스들은 용량, 용도, 속도 등 여러 면에서 차이점을 가진다.

​

메모리(RAM)는 레지스터와 달리 CPU의 외부에 위치하며, 레지스터에 비해 접근속도가 상대적으로 느리다. 메모리는 데이터와 프로그램 코드를 저장하는 데 사용되며 CPU와 시스템 버스를 통해 이루어진다. 그리고 물리 메모리 초과를 방지하기 위해 가상 메모리를 사용한다.

​

레지스터는 cache보다 CPU 코어에 근접해 있다. CPU코어 - 레지스터 - 캐시 - 메모리 순으로 위치 하여 있으며 가까울 수록 임시 저장 및 처리를 더 빠르게 하고 있는 것이다.

​

레지스터는 계산 중간 결과나 계산에 자주 사용되는 임시 값들을 저장한다. 운영체제는 context switching시 레지스터의 상태를 저장하고 복원하는 작업을 한다.

​

레지스터는 PC와 스택 포인터 등 특수목적 레지스터를 포함하여 상태 레지스터,작업 레지스터, 범용 레지스터, 명령어 레지스터를 일괄하여 말한다. 이 중 범용 레지스터는 프로그램의 실행 동안 가장 일반적이고 자주 사용되는 레지스터이다.

​

PC(Program Counter)는 CPU가 현재 실행하고 있는 명령어의 메모리 주소를 저장하는 레지스터이다. CPU가 다음에 실행할 명령어의 위치를 알려주며, 일반적으로 명령어가 실행될 때 마다 자동으로 증가하여 다음 명령어의 주소를 가리킨다. 프로그램의 실행 흐름을 변경하는 분기나 점프 명령어가 실행될 때, 프로그램 카운터는 새로운 주소로 업데이트되어 CPU가 새로운 위치에서 명령어를 계속해서 실행할 수 있게 한다.

​

명령어 레지스터는 현재 CPU가 실행중인 명령어를 저장하여 CPU가 현재 어떤 작업을 하고 있는지 알고 싶을 때 사용된다.

​

상태 레지스터는 보통 몇 비트로 이루어져 있으며, 각 비트는 특정 상태나 조건 (예 : 캐리 아웃, 오버플로우, 언더플로우, 제로, 음수 등)을 나타낸다. 이런 단일 연산 결과에 대한 정보를 제공하므로 상태 레지스터의 크기는 상대적으로 작다.

​

작업 레지스터는 특정 아키텍처에선 범용 레지스터라고 불리며, 일시적으로 데이터를 처리하기 위한 임시 저장소이다.

​

범용 레지스터는 데이터 연산, 임시 데이터 저장, 메모리 주소의 저장 등 다양한 목적으로 사용된다. 이들은 프로그램의 데이터를 처리하고, 메모리와의 데이터 교환을 위한 주요 저장소 역할을 한다.

디스크는 컴퓨터에서 데이터를 저장하는 장치를 말한다. 크게 두 종류로 나뉜다

HDD(Hard Disk Drive)는 자기 저장 방식을 사용해 데이터를 저장하는 장치로, 내부에는 회전하는 디스크(플래터)가 있으며, 이 위에 데이터를 읽고 쓰는 헤드가 움직이며 작동한다. 대용량 데이터를 저장할 수 있고, 가격이 상대적으로 저렴하지만, 움직이는 부품이 있어 충격에 약하고, SSD에 비해 속도가 느리다.

SSD(Solid State Drive)는 반도체 칩을 사용해 데이터를 저장하며, 움직이는 부품이 없어 충격에 강하고 빠른 데이터 읽기와 쓰기 속도를 제공한다. HDD에 비해 가격이 높지만, 성능과 내구성 면에서 우수하다.

M.2는 SSD의 한 형태로, 소형화된 카드 형태의 설계로 제공된다. PCIe 또는 SATA 인터페이스를 통해 데이터 전송을 지원하며, 특히 NVMe 프로토콜을 사용하는 PCIe M.2 SSD는 매우 높은 속도를 제공한다. 노트북이나 소형 PC에서 공간 절약과 고속 데이터 전송이 필요할 때 사용된다.

이들은 다 보조기억 장치로 분류된다. 보조기억장치는 컴퓨터에서 데이터를 영구적으로 저장하는 역할을 하며, 주기억장치(RAM)과 달리 전원이 꺼져도 정보를 유지한다.(비휘발성) 이러한 장치들은 대용량 데이터 저장, 시스템 부팅, 소스트웨어 실행 등 다양한 목적으로 사용된다.

ROM(Read-Only Memory)은 읽기 전용 메모리로, 주로 컴퓨터나 전자기기의 펌웨어나 시스템 부트로더 등이 저장되는 곳이다. 전원이 꺼져도 데이터를 유지한다는 점에서 보조기억장치의 특성을 가지고 있지만, 일반적으로 사용자가 데이터를 저장하고 변경할 수 있는 HDD, SSD와 같은 저장 장치와는 구분된다. ROM은 보통 한 번 프로그래밍되면 변경이 어렵거나 불가능한 데이터를 저장하는 데 사용되므로, 전통적인 의미에서의 보조기억장치와는 조금 다른 역할을 한다. 그럼에도 불구하고 넓은 의미에서는 데이터를 저장하는 장치로서 보조기억장치의 범주에 포함시킬 수 있다.

하이퍼바이저는 가상화 기술을 구현하는 소프트웨어다. 물리적 하드웨어 위에서 여러 운영체제를 동시에 실행할 수 있게 해준다. 하이퍼 바이저는 크게 두 가지 유형이 있다.

https://aws.amazon.com/ko/compare/the-difference-between-type-1-and-type-2-hypervisors/

타입 1 하이퍼바이저는 하드웨어에 직접 설치되어 운영체제 없이 작동하며, 고성능 가상화 환경을 제공한다. 기본 물리적 호스트 머신 하드웨어에서 실행되며, 대규모, 리소스 집약적 또는 고정용 워크로드에 적합하다. 시스템 관리자 이는 수준의 지식이 필요하다. 예시로 VMware ESXi, Microsoft Hyper-V, KVM이 있다.

타입 2 하이퍼바이저는 기존 운영체제 위에 설치되어, 일반적인 애플리케이션처럼 실행된다. 가상머신을 만들고 관리하는 데 사용된다. 기본 운영 체제에서 실행되고 데스크톱 및 개발 환경에 적합하다. 예시로 Oracle VM VirtualBox, VMware Workstation, Microsoft Virtual PC가 있다.

애뮬레이션은 하나의 시스템이 다른 시스템의 기능을 모방하게 하는 기술이다. 이는 소프트웨어, 하드웨어, 또는 둘의 조합을 통해 이루어질 수 있다. 예를 들어, 특정 비디오 게임 콘솔용으로 개발된 게임을 PC에서 실행할 수 있게 해주는 소프트웨어 애뮬레이터가 이에 해당한다. 애뮬레이션은 다양한 용도로 사용되며, 오래된 시스템의 소프트웨어를 새로운 하드웨어에서 실행하거나, 소프트웨어 개발 과정에서 다른 플랫폼을 대상으로 하는 애플리케이션의 테스트에 사용되기도 한다.

하이퍼바이저(가상화)는 물리적 하드웨어 위에 직접 구축되며, 하드웨어 자원을 여러 가상 머신 간에 분할한다. 이는 주로 성능 저하 없이 효율적인 자원 분배와 관리를 목표로 한다. 하이퍼바이저는 주로 같은 아키텍처 내에서의 가상화에 초점을 맞춘다.

따라서, 하이퍼바이저는 가상 머신을 생성하고 관리하는 역할을 하며, 가상 머신은 이러한 환경에서 실행되는 독립적인 컴퓨터 시스템이라 할 수 있다.

애뮬레이터는 하드웨어, 소프트웨어, 또는 둘의 조합을 모방하는 소프트웨어로, 한 플랫폼에서 다른 플랫폼의 시스템을 실행할 수 있게 한다. 예를 들어, 한 종류의 프로세서 아키텍처를 가진 시스템에서 다른 종류의 프로세서 아키텍처를 사용하는 시스템을 모방할 수 있다. 애뮬레이션은 주로 호환성이나 구형 시스템의 소프트웨어를 새 시스템에서 실행하기 위해 사된다.

QEMU는 오픈소스 가상화 소프트웨어로, 다양한 하드웨어 아키텍처에서 가상 머신을 생성하고 실행할 수 있다. 하이퍼바이저 기능과 함께 애뮬레이션 기능도 제공하여, 하나의 플랫폼에서 다른 플랫폼의 운영 체제를 실행할 수 있게 해준다. 예를 들어, x86 프로세서를 사용하는 컴퓨터에서 ARM 프로세서를 사용하는 운영 체제를 실행할 수 있다. QEMU는 개발자들이 소프트웨어를 다양한 하드웨어 환경에서 테스트하거나, 가상화 환경을 구축할 때 널리 사용된다.

Pint OS의 Project 1이 구현되기 전에는 단일 큐로 idle tick이 없고 오로지 ready list로만 관리된다. kernel단 까지 들어갈 필요가 없는 thread도 block 되지 않고 yield()가 되는게 busy wait 이라는 문제가 된다.

그래서 sleep_list를 만들어 준 뒤에, 당장에 불 필요한 thread들을 sleep 시켜줘야 한다.

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	if(timer_elapsed(start) < ticks){
		thread_sleep(start + ticks);
	}
}

timer를 활용하여 sleep을 시키는데 이 때 thread를 block시키고, sleep list로 들어가면 해당 자원을 양보시켜줘야한다.

void
thread_sleep(int64_t ticks){
	struct thread *curr = thread_current();
	enum intr_level old_level;	

	ASSERT(!intr_context());

	old_level = intr_disable();
	curr->status = THREAD_BLOCKED;
	curr->wakeup_tick = ticks;
	
	if(curr!= idle_thread)
		list_insert_ordered(&sleep_list, &curr->elem, sleep_less , NULL);
	schedule();
	intr_set_level(old_level);
}

sleep을 시켰으니, 적당한 타임이 되면 thread를 깨워줘야한다. 인터럽트가 발생할 때마다, 틱을 증가시키는데, 이 때 thread가 깨어날 타이밍이라면 깨운다.

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_wakeup(ticks);
}

이 때, 깨울 타임이 같은 thread 중 우선순위가 높은 순서대로 ready_list에 들어가야 우선순위가 높은 thread 부터 실행이 될 수 있다. 고로, sleep된 thread 중 깨웠을 때 greater_list에 우선순위 순으로 정렬해서 넣고 그 greater_list가 ready_list에 들어간다면 될 것 이다.

void
thread_wakeup(int64_t ticks)
{
	if(list_empty(&sleep_list))
		return;

	enum intr_level old_level;
	struct thread *sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);
	struct thread *sleep_pop_front_thread;

	while(sleep_front_thread->wakeup_tick <= ticks)
	{
		old_level = intr_disable();
		sleep_front_thread->status = THREAD_READY;
		sleep_pop_front_thread = list_entry(list_pop_front(&sleep_list), struct thread, elem);
		list_insert_ordered(&greater_list, &sleep_pop_front_thread->elem , cmp_priority, NULL);
		sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);	
		intr_set_level(old_level);
	}

	while(!list_empty(&greater_list))
	{
		old_level = intr_disable();
		list_push_back(&ready_list, list_pop_front(&greater_list));
		intr_set_level(old_level);
	}
}

lock_acquire 함수는 주어진 락을 현재 스레드가 획득하려고 시도할 때 호출된다. 이미 누군가 그 락을 가지고 있다면, 현재 스레드는 대기 상태로 들어가게 되며, 락을 보유한 스레드가 lock_release를 호출하여 락을 해제할 때까지 기다려야 한다.

락의 holder가 NULL이 아니라면, 즉 누군가가 이미 락을 보유하고 있다면, 현재 스레드는 대기해야 한다. 이때, 현재 스레드의 우선순위가 락을 보유한 스레드의 우선순위보다 높다면, 우선순위 기부가 발생한다. 우선순위 기부는 락을 보유한 스레드의 우선순위를 현재 스레드의 우선순위로 상향 조정함으로써, 고우선순위 스레드가 더 빨리 실행될 수 있도록 한다.

이미 대기 중인 스레드가 있는 경우, 그 스레드들의 우선순위도 확인하고 필요에 따라 우선순위를 상속시켜 우선순위 역전 문제를 해결한다. 락을 획득할 수 있을 때까지 현재 스레드는 세마포어를 사용하여 대기 상태로 들어가고 sema_down 함수를 호출하여 세마포어의 값을 감소시키고, 필요하다면 스레드를 대기 상태로 만든다.

void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

	if(lock->holder != NULL)
	{
        thread_current()->wait_on_lock = lock;
        if(lock->holder->priority < thread_current()->priority)
        {
            list_insert_ordered(&lock->holder->donations, &thread_current()->d_elem, sleep_less, NULL);
		}
		struct lock *cur_wait_on_lock = thread_current()->wait_on_lock;
		while(cur_wait_on_lock  != NULL)
		{
			if(cur_wait_on_lock->holder->priority< thread_current()->priority)
			{
				cur_wait_on_lock->holder->priority = thread_current()->priority;
				cur_wait_on_lock = cur_wait_on_lock->holder->wait_on_lock;
			}
			else
				break;
		}
	}
	sema_down (&lock->semaphore);
	thread_current()->wait_on_lock = NULL;
	lock->holder = thread_current ();
}

sema_down 함수는 세마포어(semaphore)의 값을 감소시키려고 시도하는 연산이다. 세마포어는 동기화 목적으로 사용되는 변수로, 리소스의 사용 가능 여부를 나타낸다. sema_down 함수는 주로 락(lock) 획득이나 자원 접근 제어에 사용된다. 세마포어의 값이 0이면, 이는 해당 리소스가 사용 중임을 의미하며, 어떤 스레드도 리소스를 사용할 수 없다.

sema->value가 0인 경우, 이는 다른 스레드가 이미 리소스를 사용 중임을 의미하므로, 현재 스레드는 대기해야 한다. 이를 위해 현재 스레드는 세마포어의 대기 목록(sema->waiters)에 추가된다. 대기 목록에 추가될 때, 우선순위에 따라 정렬되어 대기 순서가 결정된다. 이후, thread_block 함수를 호출하여 현재 스레드를 대기 상태로 전환한다.

대기 중인 스레드 없이 sema->value가 0보다 큰 경우, 혹은 대기 중인 스레드가 깨어나 세마포어를 사용할 수 있는 경우, sema->value는 1 감소한다. 이는 리소스 하나가 사용 중임을 나타낸다.

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		list_insert_ordered (&sema->waiters, &thread_current ()->elem, cmp_priority, NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

lock_release 함수는 스레드가 보유한 락(lock)을 해제하고, 해당 락을 기다리는 다른 스레드들에게 양보한다.

락을 해제하는 스레드(lock->holder)의 우선순위 기부 목록(donations)을 확인하여, 이 락을 기다리고 있던 모든 스레드들의 기부 항목을 제거하고, 우선순위 기부 목록을 순회하면서, 현재 락(lock)을 기다리고 있던(wait_on_lock이 현재 락을 가리키는) 스레드를 찾아 해당 스레드의 d_elem(우선순위 기부 목록에서의 위치를 나타내는 리스트 요소)을 목록에서 제거하고, wait_on_lock을 NULL로 설정한다.(우선순위 기부가 더 이상 필요하지 않음)

우선순위 기부 목록이 비어있지 않다면(다른 스레드들로부터 우선순위 기부를 받고 있는 상황), 목록의 첫 번째 스레드(next_thread)의 우선순위를 현재 스레드의 우선순위로 설정한다.

우선순위 기부 목록이 비어있다면(더 이상 우선순위 기부를 받고 있지 않은 상황), 스레드의 우선순위를 원래의 우선순위(original_priority)로 복원한다.

락의 holder를 NULL로 설정하여, 락의 소유권을 해제하고, sema_up(&lock->semaphore)를 호출하여 세마포어의 값을 1 증가시키고, 세마포어 대기 목록에 있는 스레드 중 하나를 깨운다(있다면). 이는 락이 이제 사용 가능하게 되었음을 나타내며, 대기 중인 스레드가 락을 획득할 수 있게 한다.

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	if(!list_empty(&lock->holder->donations))
	{	
		struct list_elem *front_elem = list_begin(&lock->holder->donations);
		while(front_elem != list_end(&lock->holder->donations))
		{
			struct thread *front_thread = list_entry(front_elem, struct thread, d_elem);
			if(front_thread->wait_on_lock == lock)
			{
				list_remove(&front_thread->d_elem);
				front_thread->wait_on_lock = NULL;
			}			
			front_elem = list_next(front_elem);
		}
		if(!list_empty(&lock->holder->donations))
		{
			struct thread *next_thread = list_entry(list_front(&lock->holder->donations), struct thread, d_elem);
			lock->holder->priority = next_thread->priority;
		}
		else
			lock->holder->priority = lock->holder->original_priority;
	}
	lock->holder = NULL;
	sema_up (&lock->semaphore);
}

세마포어의 대기자 목록(sema->waiters)이 비어있지 않은 경우, 즉 대기 중인 스레드가 있는 경우에는 대기자 목록에서 가장 앞에 있는 스레드(가장 높은 우선순위를 가진 스레드)를 꺼내 thread_unblock 함수를 호출하여 실행 가능 상태로 만들고, 세마포어의 value를 1 증가시킨다. (추가적인 리소스가 사용 가능해졌거나, 더 이상 대기 중인 스레드가 없음)

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
	{
		list_sort(&sema->waiters, cmp_priority, NULL);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}
	sema->value++;
	intr_set_level (old_level);
	thread_yield();
}

donations가 만약 비어있다면, 현재 스레드의 priority 필드를 새로운 우선순위 값으로 업데이트를 하여 기부를 받고 있지 않을 때만 스레드의 우선순위를 직접 변경할 수 있게 해야한다.

void
thread_set_priority (int new_priority) {
	if(list_empty(&thread_current()->donations))
		thread_current ()->priority = new_priority;
		
	thread_current ()->original_priority = new_priority;

	struct thread *head_thread = list_entry(list_begin(&ready_list), struct thread, elem);
	if(head_thread->priority > new_priority)
		thread_yield();
}

조건 변수의 대기자 목록이 비어 있지 않다면, 대기자 목록을 우선순위에 따라 정렬해야한다. 대기자 목록(waiters)에서 가장 앞에 있는 세마포어 요소를 꺼내, 그 세마포어를 통해 대기 중인 스레드 중 하나를 깨운다.

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters))
		list_sort(&cond->waiters, cmp_condvar_priority, NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

조건 변수의 대기자 목록에 있는 두 개의 세마포어에서 객체를 가져와 두 스레드의 우선순위를 비교하여 첫 번째 스레드가 더 높다면, true 두 번째 스레드가 더 높다면 false를 반환한다.

bool
cmp_condvar_priority(const struct list_elem *a, const struct list_elem  *b, void *aux UNUSED) {
	struct semaphore_elem *sema_elem_a = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sema_elem_b = list_entry(b, struct semaphore_elem, elem);

	struct semaphore sema_a = sema_elem_a->semaphore;
	struct semaphore sema_b = sema_elem_b->semaphore;

	struct thread *t_a = list_entry(list_begin(&sema_a.waiters), struct thread, elem);
	struct thread *t_b = list_entry(list_begin(&sema_b.waiters), struct thread, elem);
	
	return t_a->priority > t_b->priority;
}

extra 문제인 MLFQS 빼고 전부 pass되었다.

master branch에 project1만 취급하는 코드가 있음

컨텍스트 스위칭(Context Switching)은 운영 체제의 멀티태스킹과 밀접하게 연관된 중요한 개념이다. 컴퓨터에서 여러 프로세스 또는 스레드가 동시에 실행되는 것처럼 보이게 하는 메커니즘으로, 실제로는 CPU가 빠르게 여러 작업 사이를 전환하면서 각각의 작업에 조금씩 처리 시간을 할당한다.

1. 실행 중인 프로세스의 현재 상태(컨텍스트)를 PCB 형태로 저장해야 한다. 이 컨텍스트에는 PID, 프로세스의 상태(우선순위 등), 프로세스 카운터(PC), 레지스터 세트, CPU 스케줄링 정보, 메모리 상태 등이 포함된다. 이 정보는 프로세스의 컨텍스트를 구성하며, 프로세스가 다시 CPU에서 실행을 계속할 수 있도록 필요한 모든 정보를 포함한다.

2. 스케줄러가 다음에 실행할 프로세스를 결정한다. 이 결정은 운영 체제의 스케줄링 알고리즘에 따라 달라진다.

3. 이전에 저장된 다음 프로세스의 컨텍스트를 복원한다. 이 과정에서 프로세스 카운터, 레지스터, 메모리 상태 등이 CPU에 로드된다.

4. 복원된 컨텍스트를 바탕으로 새로운 프로세스(또는 이전에 중단되었던 프로세스)가 실행을 시작한다.

컨텍스트 스위칭은 자원을 소모하는 작업이다. 컨텍스트를 저장하고 복원하는 데에 시간이 걸리며, 이로 인해 CPU 사용률이 실제 작업 처리에 사용되는 것보다 낮아질 수 있다. 또한, 캐시 메모리가 무효화되는 경우(캐시 콜드 미스)가 발생할 수 있어, 성능 저하를 초래할 수 있다.

프로세스 대신 스레드를 사용하면 컨텍스트 스위칭 비용을 줄일 수 있다. 스레드는 같은 프로세스 내에서 메모리와 자원을 공유하기 때문에 컨텍스트 스위칭 시 저장해야 할 정보가 적다. 운영 체제의 스케줄링 알고리즘 선택도 성능에 영향을 준다. 예를 들어, 시분할(Time-sharing) 시스템에서는 라운드 로빈(Round Robin) 스케줄링이 자주 사용된다.

비선점형 커널은 한 프로세스가 종료될 때까지 점유하기 때문에 경쟁상황이 발생하지 않는다.

​

선점형 커널은 계속해서 컨텍스트 스위칭이 일어나기 때문에 경쟁상황이 발생할 수 있는데 이를 피하기 위해 임계구역이라는 것을 만들어줘야 한다.

​

임계구역이란 파일의 입출력, 공유 데이터 등 원자적으로 실행할 필요가 있는 명령문 또는 코드의 일부 영역이다.

Race condition(경쟁 상황)은 두 개 이상의 프로세스가 공통자원을 병행적으로 읽거나 쓰는 동작을 할 때, 공유 데이터에 대한 접근이 어떤 순서에 따라 이루어 졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 의미한다.

​

경쟁상황은 불 충분한 동기화, 비 원자적인 작업, 실행 순서가 잘못 되었을 때 일어난다. 여기서 비원자적인 것은 어느한 단계를 걸쳐서 실행하는 큰 함수와도 같은 것들을 말한다. 원자적, 즉 더 이상 쪼갤 수 없는 작업 단위로 컨텍스트 스위칭이 일어나야한다.

​

두 개 이상의 프로세스의 Race condition이 일어날 때, 서로 동일한 자원을 두고 경쟁을 하는데 이 경쟁이 끝까지 끝나지 않을 경우를 교착 상태라고 한다. 즉, 두 개의 스레드가 하나의 자원을 놓고 서로 사용하지 않고 경쟁하는 상황이다.

​

Deadlock(교착 상태)은 임계구역에서 둘 이상의 프로세스가 서로 보유하고 있는 자원을 요구하여, 아무도 자신의 작업을 진행할 수 없게 되는 상태를 말한다.

​

Starvation(기아 상태)는 하나 이상의 프로세스가 자원에 대한 접근을 무한정 기다려야 하는 상황이다. 이는 특정 프로세스가 다른 프로세스에 비해 우선 순위가 낮거나, 자원 분배 알고리즘에 의해 불리하게 작용할 때 발생할 수 있다. 부족한 자원을 여러 프로세스가 점유하려고 경쟁할 때 발생한다.

​

Starvation은 SJF, SRT, SPN 처럼 우선순위를 길이로 판단하는 스케줄링을 사용했을 때 일어나며, 이를 방지하기 위해 FIFO같은 우선순위가 아닌 요청 순서대로 처리하는 큐를 사용하는게 좋다.

​

Deadlock은 시스템이 완전히 멈춰버린 상태로, 아무 진전이 없을 수도 있고 즉시 해결해야 하는 긴급한 문제이고, Starvation은 특정 프로세스가 진행할 수 없는 상태지만, 다른 부분은 여전히 작동가능하여 장기적인 관점에서 해결할 수 있는 문제이다.

세마포어(Semaphore): 동시성 프로그래밍에서 공유 자원에 대한 접근을 제어하기 위해 사용되는 변수나 추상 데이터 타입이다. 멀티 스레드나 프로세스 환경에서 여러 스레드 또는 프로세스가 동시에 공유 자원을 사용하려 할 때, 이를 안전하게 조정하기 위한 메커니즘 중 하나이다.

​

이진 세마포어(Binary Semaphore): 값이 0 또는 1만을 가질 수 있는 세마포어로, 뮤텍스(Mutex)와 유사한 기능을 한다. 이는 공유 자원에 단 하나의 스레드/프로세스만 접근할 수 있게 하여 상호 배제(Mutual Exclusion)를 구현한다.

​

카운팅 세마포어(Counting Semaphore): 값이 0 이상의 정수를 가질 수 있는 세마포어로, 한 번에 여러 스레드/프로세스가 공유 자원에 접근할 수 있게 한다. 카운팅 세마포어의 값은 동시에 접근할 수 있는 최대 스레드/프로세스 수를 의미한다.

​

세마포어는 주로 두 가지 기본 연산, wait()(또는 P(), acquire()) 연산과 signal()(또는 V(), release()) 연산을 사용한다.

​

wait() 연산: 스레드/프로세스가 공유 자원을 사용하기 전에 이 연산을 호출한다. 세마포어의 값이 0보다 크면, 세마포어의 값을 1 감소시키고 실행을 계속한다. 만약 세마포어의 값이 0이면, 공유 자원이 사용 가능해질 때까지 스레드/프로세스를 대기 상태로 만든다.

​

signal() 연산: 스레드/프로세스가 공유 자원의 사용을 마친 후에 이 연산을 호출한다. 세마포어의 값을 1 증가시키고, 대기 중인 스레드/프로세스 중 하나를 깨워 공유 자원을 사용할 수 있게 한다.

import threading
import time
import random

# 세마포어 생성, 동시에 리소스에 접근할 수 있는 스레드의 최대 수를 2로 설정
semaphore = threading.Semaphore(2)

class MyThread(threading.Thread):

    def run(self):
        # 세마포어 획득(리소스 접근)
        with semaphore:
            print(f"{self.name} is now sleeping")
            time.sleep(random.randint(1, 5))
            print(f"{self.name} is finished")

# 스레드 객체 생성
threads = []
for i in range(4):
    threads.append(MyThread())

# 모든 스레드 시작
for t in threads:
    t.start()

# 모든 스레드의 종료를 기다림
for t in threads:
    t.join()

​

뮤텍스(Mutex, Mutual Exclusion Object)

동시성 프로그래밍에서 공유 자원에 대한 동시 접근을 방지하기 위해 사용되는 동기화 메커니즘이다. 뮤텍스는 한 번에 하나의 스레드만 공유 자원을 사용할 수 있도록 보장함으로써, 데이터의 일관성과 무결성을 유지한다.

​

스레드가 공유 자원을 사용하기 전에 뮤텍스를 잠그거나 획득한다. 이 시점에서 해당 뮤텍스는 잠긴 상태가 되며, 다른 스레드는 그 자원을 사용할 수 없다.

​

뮤텍스를 성공적으로 잠근 스레드는 공유 자원을 안전하게 사용할 수 있다. 스레드가 자원 사용을 마치면 뮤텍스를 해제하거나 방출한다. 이로써 다른 스레드가 해당 자원에 접근할 수 있는 기회를 얻는다.

import threading
import time
import random

mutex = threading.Lock()

class ThreadOne(threading.Thread):

    def run(self):

        global mutex
		# 뮤텍스를 획득
        mutex.acquire()  

        print("The first thread is now sleeping")

        time.sleep(random.randint(1, 5))  # 1초에서 5초 사이의 랜덤한 시간 동안 대기

        print("First thread is finished")
        
        # 작업이 끝나면 뮤텍스를 해제
        mutex.release()  

class ThreadTwo(threading.Thread):

    def run(self):
    
        global mutex
        
		# 첫 번째 스레드가 뮤텍스를 해제할 때까지 대기
        mutex.acquire()  

        print("The second thread is now sleeping")
        
		# 1초에서 5초 사이의 랜덤한 시간 동안 대기
        time.sleep(random.randint(1, 5))  

        print("Second thread is finished")
        
		# 작업이 끝나면 뮤텍스를 해제
        mutex.release()  

t1 = ThreadOne()
t2 = ThreadTwo()

t1.start()
t2.start()

t1.join()  # 첫 번째 스레드가 종료될 때까지 메인 스레드 대기
t2.join()  # 두 번째 스레드가 종료될 때까지 메인 스레드 대기