CS운영체제3_쓰레드, 교착상태, 페이지폴트와 페이지 교체 알고리즘

 쓰레드 동기화 이슈

  앞선 포스팅에서 언급했듯이, 동일한 자원에 여러스레드가 접근할 경우 동기화 이슈가 발생할 수 있다.

동일한 자원에 접근 시 동기화 이슈 발생 -> 동일자원을 여러 스레드가 동시 수정시, 각 스레드 결과에 영향을 줌.

(동시에 읽는 것은 문제상황x, 수정하면 동기화 문제로 결과에 영향을 끼치게 됨.)

 

 동기화 이슈 해결방안

  어떤 공유자원에 접근(처리)하는 스레드가 있으면, 다른 스레드가 동시접근 못하도록 막는 방식으로 해결.

• Mutual Exclusion(상호배제): Exclusive Access로 어느 한 스레드가 공유변수를 갱신하는 동안 _다른 스레드 동시접근 불가하게 막는다.
• Mutex와 세마포어
  • • Mutex(binary semaphore) : 임계구역에 하나의 스레드만 들어갈 수 있음
    • Semaphore : 임계구역에 여러 스레드가 들어갈 수 있음 : counter를 두어서 동시에 리소스에 접근 할 수 있는 허용 가능한 스레드 수를 제어

교착상태와 기아상태

교착상태: 프로세스나 스레드가 서로 자원요청&점유한 상태 +다음 자원 기다림

                 -> 자원부족으로 다음 처리를 하지 못하고 모두 대기상태.(모든자원이 점유되어있어 더이상 자원할당이 안됨)

기아상태: 일부 프로세스나 스레드가 자원을 할당받지 못해 계속해서 대기하고 있는 상태.->일 처리 불가.

 

*식사하는 철학자문제

5명의 철학자(스레드)가 원형테이블에 앉아있음.

철학자마다 왼쪽과 오른쪽에 젓가락 5개(자원)가 한쪽씩 놓여있음.

두개의 젓가락을 들어야 음식(처리할 작업)을 먹을 수 있음. 한번에 한명의 철학자만 식사가능.

- 모든 철학자가 왼쪽젓가락을 들고 기다리면? = 교착상태

 

   해결 방법

• 4명만 테이블에 동시에 앉도록 하기. 
• 철학자는 양쪽젓가락을 모두 사용가능할때만 집을수 있도록 허용(*세마포어, **뮤텍스: 임계영역 내에서 해결)
• 비대칭해결 : 홀수번 철학자는 왼쪽젓가락을, 짝수번 철학자는 오른쪽젓가락을 먼저 집게 하기.

     *뮤텍스 = 임계 영역에 대한 접근을 허용하는 시스템 객체.

                     한 번에 하나의 스레드만이 뮤텍스를 획득할 수 있으며, 다른 스레드는 대기해야함.

                     철학자 문제에서 양쪽 젓가락을 모두 사용 가능할 때만 젓가락을 집을 수 있도록 하면, 한 번에 한명의 철학자만이 식사를 진행                       할 수 있고, 다른 철학자는 대기하게 됩니다.

    **세마포어 = 뮤텍스와 유사한 동기화 기법으로, 임계 영역의 접근을 제어하는 객체.

                        뮤텍스와는 다르게, 세마포어는 하나 이상의 스레드가 동시에 접근할 수 있도록 허용할 수도 있다.

                        철학자 문제에서 세마포어를 사용하면, A 철학자가 왼쪽 젓가락을 집었을 때 세마포어 값을 1 감소시킨다. 

                        그리고 C나 D 중에서 한 명이 오른쪽 젓가락을 집을 수 있도록 세마포어 값을 감소시킨다. 그러면 A와 C  또는 A와 D가

                            동시에 식사를 할 수 있게된다.

 

 

페이지폴트 = 페이지부재

-프로그램이 자신의 주소 공간에는 존재하지만 시스템의 RAM에는 현재 없는 데이터나 코드에 접근 시도하였을 경우 발생하는 현상

페이지 교체 알고리즘

운영체제에서 가상 메모리 관리를 위해 사용되는 알고리즘 중 하나.

 

메모리 공간은 한정되어 있음 -> 필요한 데이터만 메모리에 로드해 사용해야 할 필요가 있음.

but,모든 데이터를 메모리에 로드하면 메모리가 부족해짐 => 일부 데이터는 보조 기억장치에서 가져와야함.

 

페이지 교체 알고리즘은 메모리 내에 있는 페이지 중에서 어떤 페이지를 교체할지를 결정하는 알고리즘

대표적으로 FIFO, LRU, LFU, NUR, OPT 등이 있음.

1) FIFO(First In First Out) 

  가장 먼저 메모리에 올라온 페이지를 먼저 교체하는 방식.

  큐(Queue) 자료구조를 사용하여 페이지를 저장하고, 페이지 교체가 필요할 때 큐의 가장 앞에서부터 페이지를 교체함.

  단점: FIFO 알고리즘은 최근에 사용된 페이지를 교체해야 할 때 비효율적.

 

2) LRU(Least Recently Used)

  메모리에 있는 페이지들 중 가장 오래 사용되지 않은 페이지를 교체.

  최근에 사용되지 않은 페이지를 우선적으로 교체하기 때문에 효율적.

   단점: LRU 알고리즘은 페이지 사용 횟수를 기록해야 하기 때문에 구현이 복잡함.

 

3)LFU(Least Frequently Used)

  페이지 사용 횟수를 카운트하여 가장 적게 사용된 페이지를 교체

  LRU 알고리즘보다 성능이 좋을 수 있지만, 페이지 사용 횟수를 카운트하기 때문에 구현이 복잡합니다.

 

4) NUR(Not Used Recently)

  LRU 알고리즘과 유사하지만, 최근에 사용되지 않은 페이지를 우선적으로 교체

  사용 비트와 참조 비트를 이용하여 페이지의 상태를 기록하고, 교체할 페이지를 찾을 때 참조 비트와 사용 비트를 참고함.

 

5) OPT(Optimal)

  앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방식.

  최적의 페이지교체알고리즘(FIFO와 LRU알고리즘 단점 보완)

  실제로는 구현이 어려움(현재와 이후의 모든 페이지참조를 미리 예측해 교체대상페이지를 결정해야함)

 

메모리 관리 기법

운영체제에서는 메모리 관리를 위한 여러 가지 기법들이 사용된다. 대표적인 메모리 관리 기법인 가상 메모리, 페이징 시스템, 그리고 세그멘테이션에 대해 정리해보았다.

1. 가상 메모리: 실제 물리적인 메모리보다 더 큰 용량을 가상으로 생성하는 기법이다. 가상 메모리를 사용하면 여러 개의 프로세스를 실행할 때 각각의 프로세스가 물리적인 메모리 공간보다 크더라도 가상 메모리를 통해 모든 프로세스를 동시에 실행할 수 있다. 가상 메모리를 구현하기 위해서는 페이지 교체 알고리즘과 페이지 테이블을 사용해야한다.
2. 페이징 시스템 : 가상 메모리를 구현하기 위한 메모리 관리 기법 중 하나다. 페이징 시스템은 프로세스를 일정한 크기로 나누어 페이지(Page) 단위로 관리한다. 각 페이지는 일정한 크기의 블록으로 나누어져 있으며, 필요한 페이지만 물리적인 메모리에 로드하여 사용한다. 페이지 테이블을 사용하여 가상 주소와 물리 주소를 매핑한다.
3. 세그멘테이션: 프로세스의 메모리를 논리적인 단위인 세그먼트(Segment) 단위로 분할하여 관리하는 기법. 각 세그먼트는 서로 다른 크기를 가질 수 있으며, 주소 공간을 더욱 효율적으로 사용할 수 있다. 세그멘테이션은 페이징 시스템과 달리 메모리 공간을 분할하여 사용하기 때문에 내부 단편화가 발생하지 않는다. 세그멘테이션을 구현하기 위해서는 세그먼트 테이블을 사용하여 가상 주소와 물리 주소를 매핑한다.

세 가지 메모리 관리 기법 중 어떤 것을 선택할지는 운영체제 설계자가 결정한다. 페이징 시스템은 내부 단편화가 발생할 수 있지만, 메모리 접근이 빠르고 구현이 간단하다. 세그멘테이션은 내부 단편화가 발생하지 않지만, 메모리 접근이 느리고 구현이 복잡하다. 세그멘테이션은 논리적 주소가 실제 물리적 주소로 변환되기 위해서는 세그먼트 번호와 세그먼트 내에서의 오프셋으로 변환되어야 한다. 이를 위해 논리적 주소를 변환할 때마다 세그먼트 테이블을 참조해야 하기 때문에 세그멘테이션은 메모리 접근이 느리다.

또한, 세그멘테이션은 세그먼트의 크기가 가변적이므로 세그먼트 내부에서도 외부와 마찬가지로 내부 단편화가 발생할 수 있다. 이러한 내부 단편화는 세그먼트 크기를 조절하여 최소화할 수 있다.

세그멘테이션은 프로그램을 논리적인 단위인 세그먼트로 분할하여 메모리를 할당하는 방식으로, 가상 메모리와 함께 현대 운영체제에서 주로 사용되고 있다. 세그멘테이션은 프로세스의 논리적 구조를 반영하므로 프로세스 간의 메모리 공간 분리와 보호를 용이하게 한다.

 

---

참고내용

 

동기화 https://www.fun-coding.org/thread.html#gsc.tab=0

페이지교체알고리즘https://doh-an.tistory.com/28

세그멘테이션 https://steady-coding.tistory.com/524

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR

[OS] 페이징 시스템(Paging System)

가상 메모리 & 페이징 시스템

잔재미코딩 온라인 강의 사이트입니다

스레싱

반복적으로 페이지 폴트가 일어나서, 과도하게 페이지 교체 작업이 일어나, 실제로는 아무일도 못하는 상황

https://jwprogramming.tistory.com/56

Thrashing (쓰레싱)이란?