다락방

25. 병행성 관련 버그 25.1 비교착 상태 오류 원자성 위반 오류 다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성(serializability)이 보장되지 않았다.(즉, 코드의 일부에 원자성이 요구되었으나, 실행시에 그 원자성이 위반되었다.) 문제의 해결책은 공유 변수 참조 앞 뒤에 락을 추가해준다. 이 자료구조를 사용하는 모든 코드들이 이 락을 먼저 획득해야 한다. 순서 위반 오류 두 개의(그룹의) 메모리 참조 간의 순서가 바뀌었다.(즉, A가 항상 B보다 먼저 실행되어야 하지만 실행 중에 그 순서가 지켜지지 않았다.) 오류를 수정하는 방법은 순서를 강제하는 것이다. 이러한 종류의 동기화에는 컨디션 변수가 잘 맞는다. 쓰레드간의 순서가 문제가 된다면 컨디션 변수(또는 세마포어)를 사용하여 해결..

24. 세마포어 24.1 세마포어 : 정의 세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작할 수 있다. POSIX 표준에서 이 두 개의 루틴은 sem_wait()와 sem_post()이다. 세마는 초기 값에 의해 동작이 결정되기 때문에, 사용하기 전 제일 먼저 값을 초기화 해야한다. 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다. 두 루틴들은 동시에 다수 쓰레드들에 의해 호출될 수 있다. 임계영역이 적절히 보호되어야 한다. 임계영역 보호를 위해 사용할 함수내에서 임계영역 보호문제가 존재한다. sem_wait() 함수는 세마포어 값이 1 이상이면 즉시 리턴하거나, 해당 세마포어 값이 1 이상이 될 때까지 호출자를 대기시킨다. 다수의 쓰레드들이 sem_wait()을 호출 할 수 있기 때문에,..

22. 락 기반의 병행 자료 구조 자료구조에 락을 추가하면 해당 자료구조를 경쟁 조건으로부터 안전한 쓰레드 사용(thread safe) 자료 구조로 만들 수 있다. 락이 어떤 방식으로 추가되었느냐에 따라 그 자료구조의 정확성과 성능이 좌우된다. 22.1 병행 카운터 카운터는 가장 간단한 자료구조 중 하나이다. 보편적으로 사용되는 구조이면서 인터페이스가 간단하다. 간단하지만 확장성이 없다. 이 병행이 가능한 카운터는 간단하지만 정확하게 동작한다. 사실 이 카운터는 가장 간단하고 가장 기본적인 병행 자료 구조의 보편적인 디자인 패턴을 따른다. 자료구조를 조작하는 루틴을 호출할 때 락을 추가했고, 그 호출문이 리턴될 때 락이 해제되도록 하였다. 이 방식은 모니터(monitor)를 사용하여 만든 자료구조와 유사..

21. 락 프로그래머들은 소스코드의 임계영역을 락으로 둘러서 그 임계영역이 마치 하나의 원자단위 명령어인것 처럼 실행되도록 한다. 21.1 락 : 기본개념 락은 둘 중 하나의 상태를 갖는다. 첫 번째는 사용가능(available) 상태 (unblocked 또는 free) 이다. 즉, 어떤 쓰레드도 락을 소유하고 있지 않다. 두 번째는 사용 중(acquired) 상태이다. 즉, 임계영역에서 정확히 하나의 쓰레드가 락을 획득한 상태이다. lock과 unlock 루틴의 의미는 간단하다. lock() 루틴 호출을 통해 락 획득을 시도한다. 만약 어떤 쓰레드도 락을 갖고 있지 않으면 그 쓰레드는 락을 획득하여 임계영역 내로 진입한다. 이렇게 락을 획득한 쓰레드를 락 소유자(owner)라고 부른다. 만약 다른 쓰레..

20. 병행성 : 개요 하나의 쓰레드의 상태는 프로세스의 상태와 매우 유사하다. 쓰레드는 프로그램 카운터와 연산을 위한 레지스터들을 가지고 있다. 만약 두 개의 쓰레드가 하나의 프로세서에서 실행 중이라면 실행하고자 하는 쓰레드는 반드시 문맥교환을 통해 실행중인 쓰레드와 교체 되어야 한다. 프로세스의 쓰레드들의 상태를 저장하기 위해서는 하나 또는 그 이상의 쓰레드 제어블럭(TCB : thread control block)이 필요하다. 프로세스와의 가장 큰 차이는 프로세스의 경우와 달리 쓰레드간의 문맥 교환에서는 주소공간을 그대로 사용한다는 것이다.(사용하고 있던 페이지 테이블을 그대로 사용하면 된다.) 쓰레드와 프로세스의 또 다른 차이는 스택에 있다. 고전적 프로세스 주소 공간과 같은 모델(단일 쓰레드 프..

운영체제 19. 완전한 가상 메모리 시스템 19.1 VAX/VMS 가상 메모리 VMS는 컴퓨터의 구조적 결함을 소프트웨어로 보완한 훌륭한 사례다. 운영체제가 이상적인 개념과 환상을 제공하기 위해 하드웨어에 의존하지만, 하드웨어가 모든것을 해내지 못할 경우도 있다. 하드웨어 결함에도 불구하고 시스템이 효과적으로 작동하기 위해서 VMS 운영체제가 무엇을 하였는지 볼 것이다. 메모리 관리 하드웨어 VAX-11은 프로세스마다 512바이트 페이지 단위로 나누어진 32비트 가상주소 공간을 제공한다. 가상주소는 23비트 VPN과 9비트 오프셋으로 구성되어있다 VPN의 상위 두 비트는 페이지가 속한 세그멘트를 나타내기 위해서 사용되었다. 이 시스템은 하이브리드 구조를 갖고 있다. 주소공간의 하위 절반은 ‘프로세스 공간..

18. 물리 메모리 크기의 극복 : 정책 빈 메모리 공간이 거의 없으면 운영체제는 메모리 압박(memory pressure)을 해소하기 위해 다른 페이지들을 강제적으로 페이징 아웃(Paging out)하여 활발히 사용중인 페이지들을 위한 공간을 확보한다. 내보낼(evict) 페이지 선택은 운영체제의 교체정책(replacement policy) 안에 집약되어 있다. 18.1 캐시관리 캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간(AMAT : average memory access time)를 계산할 수 있다. AMAT = TM + (PMISS - TD) TM : 메모리 접근 비용 TD : 디스크 접근 비용 PMISS : 캐시에서 데이터를 못 찾을 확률 메모리의 데이터를 접근하는 비용은..

16. 페이징 : 더 작은 테이블 16.1 간단한 해법 : 더 큰 페이지 페이지 테이블의 크기를 간단하게 줄일 수 있는 방법이 있다. 페이지 크기를 증가 시키면 된다. 32비트 주소 공간에서 16KB 페이지를 가정해보자. 18비트의 VPN과 14비트의 오프셋을 갖게 된다. 각 PTE(4바이트)의 크기가 모두 동일하다면, 페이지 테이블에 2^18 개의 항목이 있으며, 페이지 테이블의 총 크기는 1MB가 된다. 기존 페이지 테이블 대비 크기가 1/4로 감소된다. 페이지 크기의 증가는 부작용을 수반한다. 가장 큰 문제는 페이지 내부의 낭비공간이 증가한다는 것이다. 이를 내부 단편화라 한다. 응용 프로그램이 여러 페이지를 할당 받았지만, 할당받은 페이지의 일부분만 사용하는터에, 결국 컴퓨터 시스템의 메모리가 금..

운영체제 15. 페이징 : 더 빠른 변환(TLB) 변환 - 색인 버퍼(TLB : translation - lookaside buffer) MMU의 일부다. 자주 참조되는 가상 주소 - 실 주소 변환 정보를 저장하는 하드웨어 캐시다. 주소 - 변환 캐시(address translation cache)가 조금 더 적합한 명칭이다. 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인한다. 만약 있다면 페이지 테이블(모든 변환 정보를 가지고 있다.) 를 통하지 않고 변환을 수행한다. 실질적으로 TLB는 페이징 성능을 엄청나게 향상시킨다. 15.1 TLB의 기본 알고리즘 하드웨어 부분의 알고리즘은 다음과 같이 동작한다. 먼저, 가상 주소에서 가상 페이지 번호(VPN : Virtual..

14. 페이징 개요 공간을 동일 크기의 조각으로 분할하는 것을 페이징(Paging)이라 부른다. 프로세스의 주소 공간을 몇 개의 가변 크기의 논리 세그멘트로 나누는 것이 아니라 고정 크기의 단위로 나눈다. 이 각각의 고정 크기 단위를 페이지(Page)라고 부른다. 상응하여 물리 메모리도 페이지 프레임(Page Frame) 이라고 불리는 고정 크기의 슬롯의 배열이라고 생각한다. 이 프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있다. 14.1 간단한 예제 및 개요 물리 메모리는 고정 크기의 슬롯들로 구성된다. 가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치되어 있다. 페이징의 장점은 유연성이다. 페이징을 사용하면 프로세스의 주소공간 사용 방식과는 상관없이 효율적으로 주소공간 개념을 지원 ..