[운영체제] 2. 프로세스 & 스레드(5/5), 3. 메모리 관리(1/3)

2.5.1 식샤하는 철학자 문제 : 제한된 개수의 자원을 배타적으로 접근하기 위해 경쟁하는 프로세스 모델링에 유용

 

다섯 명의 철학자가 앉아있다. 스파게티를 먹으려면 두 개의 포크가, 포크는 접시 사이에 있다.

먹거나, 쉬거나 할 수 있고 각 철학자는 해야할 일을 그대로 수행하며 중단되지 않아야 한다.

위 이미지는 잘못된 해법.

모두 동시에 왼쪽 포크를 집으면, 아무도 오른쪽 포크를 집을 수 없게 된다.

state[N] : 현재 상태를 저장

뮤텍스 하나, 5개의 세마포어 선언, 5개의 쓰레드가 philosopher함수 실행

take_forks : 상호배제를 위해 mutex를 찾고, 테스트에서 상호배제를 위해 state를 hungry로 바꾼 후 테스트 함수 호출(자신의 번호를 인자로 받음)

-> 테스트를 부른 철학자는 hungry상태, 좌우 철학자가 eating이 아니라면, 즉 포크를 집은 상태가 아니라면 이 철학자가 포크를 잡을 수 있는 환경이므로 if문을 돌게 됨. -> state를 eating으로 바꾸고 세마포어를 푼다. 이후 돌아감 -> 뮤텍스를 풀고 -> eat실행

 

put_forks : 상호배제를 위해 mutex잡고, state를 thinking으로 바꾸고 -> 테스트 레프트 라이트 하고 -> 세마포어를 풂

 

여기서, 내 왼 오 철학자 중 누군가가 eating이면 if문 수행 못하고 test가 반환되어 멈춰있게 되기 때문에, put_forks에서 자신의 왼 오 철학자가 eating이 아니면 세마포어를 풀어놓음 -> 그리고 up(&mutex)해서 다운세마포 했을 때 멈추게 됨.

-> 상태를 체크하고 기다리면 세마포를 풀어줌.

 

2.5.2 readers and writers problem : 데이터베이스 접근을 모델링.

writer가 왔는데, reader가 db세마포어를 잡고 있음. -> write는 down에서 기다림 ->  rc는 계속 증가

문제 -> 2초마다 독자가 오고, 독자가 작업에 5초가 걸리게 되면 작가는 데이터베이스에 접근할 수가 없음.

 

위 문제를 해결 : 대기시 작가에게 우선순

writer 쓰레드가 실행되면 최초 wrtier이라고 하면, read세마포어를 풀고, 이제 마지막 writer이면 read세마포어를 올림.

서로 상대방의 세마포어를 잡으려고 무한대기:데드락 할 수 있기 때문에, read->write이렇게 돌아가게끔해야 함.

리더가 들어오면 down(z)에서 멈춤. 

z세마포 : 기다리는 줄을 하나 더 만듦. z가 없으면 쓰레드 개수에 의해 우선순위가 정해질 것.

 

해결했으나, 병행성이 떨어짐.

 

 

 

 

 

3.1 메모리 추상화가 없는 컴퓨터

메모리-cpu-스토리지는 버스로 연결.

cpu가 메모리의 주소를 메모리 컨트롤러 쪽으로 알려줘야 하고, 주소를 만들어내는건 우리가 만든 프로그램(실행시 프로세스)

메모리에 프로세스의 실행이미지가 만들어짐. 코드, 데이터, 힙, 라이브러리 등의 형태로 메모리에 로드가 되고,  cpu가 이를 가져다 실행.

이 주소는 코드를 만들고 나면 컴파일러가 만들어줌. 이 주소가 가상일 경우 가상 메모리 시스템.

 

이 메모리 추상화가 없는게 리얼 메모리 시스템.

 

a : RAM 아래에 운영체제가 존재, 그 위에 사용자 프로그램이 존재

b : 상단의 ROM에 운영체제 존재

c : 상단의 ROM에는 디바이스 드라이버가 존재.

메모리 어드레스 0번지에는 인트럽트 벡터 테이블이 있어야함. 따라서 b는 사용 불가능.

 

물리 주소 공간 : 실제 시스템에서 보이는 주소.

로지컬 주소 공간 : 프로그램, 프로세스가 바라보는 메모리의 양 -> 실행시 물리 주소와 mapping

가상메모리 시스템은 이 프로그램이 cpu에서 지정할 수 있는 adress 공간보다 큼.

 

최초의 코드를 컴파일 -> 어셈블리어 코드 생성 -> 어셈블리시 머신코드 생성. foo가 75(메모리 어드레스)로 바뀜. -> 100까지 차 있으면 밀려서 175로 변경 -> 실제 메모리로 로드시 실제 적재 위치는 1100부터 1175까지. 따라서 실행시 메모리 위치를 재지정(175->1175) 해야 하는데, 이를 relocation이라고 함.

 

메모리 추상화 없이 여러 프로그램을 로드해서 실행시 컴파일러는 0부터 시작해서 프로그램을 실행

ex) a는 0부터 16380까지. c를 보면 a는 시작하자말자 jmp하여 잘 실행이 되지만, b는 a로 점프시켜 정상적으로 실행되지 않음.

-> 주소 재배치 필요

 

해결 1 : 파티셔닝 : 피지컬 메모리를 나눴음. 

-> 프로그램마다 크기가 다름. 위 이미지 처럼 특정 파티션에 프로세스가 몰린 케이스도 가능. -> 비효율적이며 사이즈가 맞지 않은 나머지 공간은 사용 불가능 : fregmentation

 

 

해결 2: 프로그램이 로드될 때 다시 주소를 바꿔서 로드하기(동적으로 주소 재배치)

cpu는 실행할 때 Program P의 로지컬 어드레스. 0번지 기준으로 만듦.

베이스 레지스터를 cpu내부에 둬서, cpu가 로지컬 어드레스를 통해 접근할 때(program 문맥 교환시) 베이스 레지스터에 있는 주소를 더하면 실제 주소가 됨.

리미트 레지스터는, 주소의 범위를 초과하면 예외를 발생시켜 OS의 엑셉션 핸들러를 실행시키고 종료.

-> placement의 비율 문제도 해결하며, 파티션을 나눌 이유도 없음. : 아래 이미지 참조

 

 

 

다이나믹 리로케이션 알고리즘

First fit : 순서대로 찾다가, 첫번째 만족하는 위치에 프로세스 이미지를 적재

-> 위쪽이 많이 사용 But 시간이 적게 들게 되고, 아래쪽이 많이 남아 메모리를 많이 차지하는 프로세스를 밑에 적재할 수도 있음

Best fit : 빈 공간을 다 뒤져 딱 맞는 것을 찾음 -> 검색시간 long

Worst fit : 가장 큰 공간에 적재 : 큰 공간의 나머지 공간 재활용

Next fit : 서치 포인트를 기억하다가, 해당 지점부터 서치

 

 

memory fregmantation : 조각난 프로그램들이 있는데, 큰 프로그램은 빈 공간에서 실행을 못하여 쓰여지지 못하는 메모리 존재

이전의 프레그맨 테이션은 파티션 내부 : internal fregmantation

위 이미지는 메모리 전체 : 파티션 밖에서 낭비 : external fregmantation

Coalescing : 집약 : 인접한 빈 공간을 합치는 것, Optimal : 최적의

 

Compaction : 병합 : 위로 쭉 당겨 붙여 큰 공간 생성 -> 복사를 많이 해야 해서 overhead가 큼.

-> 메모리 얼로케이션이 실패했거나, 사용량이 적거나, 혹은 주기적으로 dinamic program relocation이 가능해야 함.

But 알고리즘이 너무 어렵고, compaction동안 프로세스를 실행할 수 없어 시스템이 멈추게 됨.

 

3.2.2 스와핑

실제 시스템의 프로세스들이 필요로 하는 메모리는 실제 ram용량보다 큼. -> 모든 프로세스들을 메모리에 적재한다는 것은 불가능

 

Swapping : 프로세스가 더이상 실행되지 않을 경우 다시 디스크로 내려보냄. swap파일이 생김

 

 

 

프로그램 실행 이미지가 생기는데, 코드는 실행 프로그램에서 가져옴.

 

힙, 스택은 프로세스 이미지가 만들어질 시점에 메모리를 할당해주고, 메모리에서 만들어짐

 

-> 실행시키다 보면 힙, 스택이 커짐 -> 공간이 없어

 

-> 쫓아내야해 -> 스왑 공간에 쫓아내자.

 

 

 

오버레이 : real memory system에서는 메모리보다 큰 프로그램 실행 불가 -> 오버레이 기법 탄생

-> 컴파일 시점에 컴파일러가 함수를 모듈단위로 나눠주고, 필요할 때 메모리에 적재하여 실행

 

 

3.2.3 가용 메모리 공간 관리

비트맵 알고리즘 : 가장 효율적. 지금도 리눅스 시스템에서 사용, 메모리를 할당 단위(allocation unit)로 나누어 관리

-> 할당 단위가 작으면 비트맵 공간(차지하는 메모리가)이 커짐, 할당 단위가 커지면 일부 공간이 낭비 가능성

프로세스가 k개의 할당 단위를 요구했을 때 메모리 관리자가 비트맵에서 연속적인  k개의 0비트를 찾아야 함.

a : 메모리 상태 b : 비트맵 c:  리스트로 비트맵 정보를 표시

 

 

연결 리스트 알고리즘 : 리스트의 각 엔트리는 빈공간 or 내용을 담고있음을 나타내는 정보, 시작주소, 길이, 다음 엔트리 포인터로 구성

a : 빈공간을 H로 변경

b, c : 두 개의 엔트리가 통합 -> 전체 리스트에서 엔트리 -1

d : 3개의 엔트리가 하나로 통합 -> 전체 리스트에서 엔트리 -2

 

이중 연결 리스트 사용시 이전 엔트리를 찾고 통합이 가능한지 조사하는데 용이

 

 

메모리 공간가 빈 공간 주소값을 키로 정렬되어 있으면, 새로 생성되거나 스왑 인 되는 프로세스를 위한 공간할당는 알고리즘

-> 아까 위의 fit 알고리즘.