당신이 무엇을 배우고 있다는것은 어제의 당신보다 훨씬 높은 가치가 되었다는 것이다

■  뮤텍스와 세마포어

이 글은 Niclas Winquist씨가 2005년에 쓴 화장실에 비유한 글을 번역하였습니다.

뮤텍스 : 뮤텍스는 화장실에 들어가기 위한 열쇠로 비유할 수 있습니다. 즉 화장실에 들어갈 수 있는 열쇠를 한 사람이 갖고 있다면, 한 번에 열쇠를 갖고 있는 그 한 사람만이 들어갈 수 있습니다. 화장실에 열쇠를 갖고 있는 사람이 들어가 볼일을 다 본 후에는 줄을 서서 기다리고 있는(대기열-큐) 다음 사람에게 열쇠를 주게 됩니다.  

공식적인 정의(심비안 개발자 라이브러리에서 발췌) : 뮤텍스는 한 번에 하나의 쓰레드만이 실행되도록 하는 재 입장할 수 있는 코드 섹션에 직렬화된  접근이 가능하게 할 때 사용됩니다. 뮤텍스 객체는 제어되는 섹션에 하나의 쓰레드만을 허용하기 때문에 해당 섹션에 접근하려는 다른 쓰레드들을 강제적으로 막음으로써 첫 번째 쓰레드가 해당 섹션을 빠져나올 때까지 기다리도록 합니다.

뮤텍스는 값이 1인 세마포어입니다.

세마포어: 세마포어는 빈 화장실 열쇠의 갯수라고 보면 됩니다. 즉, 네 개의 화장실에 자물쇠와 열쇠가 있다고 한다면 세마포어는 열쇠의 갯수를 계산하고 시작할 때 4의 값을 갖습니다. 이 때는 이용할 수 있는 화장실 수가 동등하게 됩니다. 이제 화장실에 사람이 들어갈 때마다 숫자는 줄어들게 됩니다. 4개의 화장실에 사람들이 모두 들어가게 되면 남은 열쇠가 없게 되기 때문에 세마포어 카운트가 0이 됩니다. 이제 다시 한 사람이 화장실에서 볼일을 다 보고 나온다면 세마포어의 카운트는 1이 증가됩니다. 따라서 열쇠 하나가 사용가능하기 때문에 줄을 서서 기다리고 있는 다음 사람이 화장실에 입장할 수 있게 됩니다.

공식적인 정의(심비안 개발자 라이브러리에서 발췌): 세마포어는 공유 리소스에 접근할 수 있는 최대 허용치만큼 동시에 사용자 접근을 할 수 있게 합니다. 쓰레드들은 리소스 접근을 요청할 수 있고 세마포어에서는 카운트가 하나씩 줄어들게 되며 리소스 사용을 마쳤다는 신호를 보내면 세마포어 카운트가 하나 늘어나게 됩니다.

윈도우에서 가상 메모리는(페이징 파일은) 실제 물리적인 메모리 공간(RAM) 외에 하드 디스크에 파일 형태로 따로 준비하는가상의 메모리 공간으로, 부족한 시스템 메모리를 보조해주는 역할을 하게 됩니다. 그런데 간혹 가상 메모리를 실제 메모리 공간처럼 사용하는 줄 아시는 분들이 계시더군요. [실제 메모리 + 가상 메모리] 이렇게 메모리의 용량이 늘어나는 것으로 착각하시는 거죠. 사실은 그게 아닙니다. 다시 말하지만 가상 메모리는 실제 메모리를 보조해주는 역할입니다. 그렇다면 가상 메모리는 어떻게 실제 메모리를 보조해주는 것일까요?

윈도우의 메모리 관리자는 만약 실제 메모리 공간이 가득차서 용량이 부족하게 되면, 실제 메모리에 저장되어 있는 내용 중 당장 사용되지 않는 내용들을 미리 준비된 하드 디스크의 페이징 파일(Pagefile.sys)로 옮겨 실제 메모리에 여유 공간을 확보합니다. 그러다 페이징 파일에 옮겨둔 내용이 필요하면 다시 실제 메모리로 옮겨서 사용하는 것이죠. 즉, 윈도우의 가상 메모리는 프로그램의 사용 상황에 맞춰 실제 메모리와 가상 메모리 사이에서 데이터를 스왑(교환)하는 방식으로 부족한 실제 메모리의 공간을 알맞게 조절하는 기능입니다.

실제론 이것보단 좀 더 복잡하고 페이지 폴트와 같은 전문 용어도 있음. 하지만 매우 단순화시키면 대충 이런 식!

즉, 윈도우의 가상 메모리는 실제 메모리의 남은 공간이 부족하게 되면 사용되는 일종의 임시 공간입니다. 그래서 만약 실제 메모리의 용량이 충분하다면 거의 사용되지 않는 특성이 있습니다. 만약 실제 메모리 공간이 부족하여 가상 메모리가 사용되기 시작하면 위에서 이야기한 것과 같이 [실제 메모리 <-> 가상 메모리] 사이로 데이터를 옮기는 과정들이 추가되기 때문에 그만큼 시스템이 전체적으로 느려지게 됩니다. 특히나, 실제 메모리 공간인 램에 비해 가상 메모리 공간인 디스크는 매우 느리기 때문에 더더욱 느려지는 것이죠.

그래서 가상 메모리는 되도록 사용되지 않을 수록 좋습니다. 그럴려면 실제 메모리 즉, 램의 용량이 충분해야 하죠. 하지만 꼭 메모리 공간이 부족하지 않더라도 일부 프로그램의 경우 반드시 이러한 가상 메모리를 사용하는 경우도 있습니다.

가상 메모리(페이징 파일)은 기본적으로 윈도우가 자동으로 관리를 하고 있습니다. 가상 메모리인 페이징 파일은 보통 부팅 파티션에 위치하고[VHD 부팅이라면 VHD 파일이 위치한 파티션] 그 크기는 동적으로 윈도우가 알아서 자동으로 사용량에 맞춰 크기를 조절하는 형식으로 관리가 되는 것이 기본입니다.

이제 이러한 페이징 파일을 사용자가 원하는대로 관리하기 위해선 아래와 같이 설정하시면 됩니다.

이렇게 설정한 가상 메모리 - 페이징 파일은 해당 드라이브의 루트에 pagefile.sys 로 저장이 되어 있습니다.

이러한 pagefile.sys 파일은 현재 윈도우에서 사용 중인 파일이기 때문에 윈도우 탐색기를 통해 임의로 삭제할 수 없으며[다른 윈도우의 pagefile.sys 는 삭제 가능, 하지만 해당 윈도우로 부팅하면 다시 생깁니다.], 위와 같은 방식으로 해당 드라이브의 가상 메모리 옵션을 페이징 파일 없음으로 설정하게 되면 자동으로 제거됩니다.

1. 가상 메모리는 가장 빠른 디스크에 설정하는 것이 좋다.

널리 알려진 가상 메모리의 최적화 방법 중에 하나가 가상 메모리를 윈도우가 설치된 디스크와 물리적으로 분리된 다른 디스크의 드라이브로 옮겨주는 것입니다. 이렇게 하면 윈도우와 가상 메모리에서 동시에 발생하는 엑세스 부하를 줄여줄 수 있기 때문이죠.

하지만 한 가지 알아두셔야 할 것이 이러한 내용은 두 디스크가 동일한 성능을 가졌다는 전제 조건이 필요합니다. 즉, [HDD + HDD] 구성이나 [SSD + SSD] 구성과 같이 현재 윈도우가 설치된(현재 가상 메모리가 위치한) 디스크와 새롭게 가상 메모리를 옮겨 줄 디스크의 성능이 서로 비슷할 때에 적용되는 내용이란 것이죠.

만약 현재 SSD 에 윈도우와 가상 메모리가 위치해 있는데 이를 분리해 준다고 가상 메모리를 HDD 쪽으로 옮겨 준다면? 엑세스 부하를 줄여서 얻는 이득보다 훨씬 느린 HDD 에서의 엑세스 속도 저하로 인한 손해가 더 큽니다.

부하 분산도 좋지만 포르쉐 타고 잘 달리고 있는데 경운기로 갈아타라면? 기분 좋겠습니까?

고로 [SSD + HDD] 와 같이 급이 다른 성능을 가진 디스크가 혼합된 구성을 가진 시스템이라면 가상 메모리는 무조건 빠른 디스크에(SSD 로) 위치시켜 주시는 것이 좋습니다.




2. 램 용량이 충분하다면 가상 메모리는 아예 없애는 것이 좋다?

실제로 램 용량이 충분하면 가상 메모리가 전혀 사용되지 않을 가능성이 높기 때문에 가상 메모리 없이 사용하시는 분들도 많습니다.

가상 메모리를 아예 없앤 경우.

보통 이렇게 사용해도 문제가 없지만 일부 프로그램은 램 용량에 상관없이 반드시 가상 메모리를 필요로 하기도 합니다. 즉, 시스템에 가상 메모리가 전혀 없으면 오류를 일으키는 프로그램이 소수지만 존재한다는 것입니다. 그래서 어떤 프로그램이 이러한지 정확하게 알 수 없으니 저는 가상 메모리를 아예 끄는 것보다는 사용자 지정 크기 옵션을 통해 처음 크기를 소용량(1GB 이하)으로 설정해놓고 최대 크기는 적절히 지정해서 사용하는 것을 추천합니다.

이렇게 하는 이유가 지금 당장 사용하는 프로그램들에는 문제가 없을지라도 나중에 어떤 프로그램을 추가로 설치하여 사용할 지 모르고, 만약 그 때가 되어 문제가 발생하면 이게 가상 메모리 때문에 발생한 문제인지 모르고 엉뚱한 곳에서 헤메이게 될 공산이 크기 때문이죠. [덤으로 오류가 발생했을 때 기록되는 덤프 파일도 가상 메모리 용량이 최소 200MB 이상 되어야 생성 가능한 점도 있습니다.]


이런 내용을 듣고 "어라? 그럼 소용량의 램 디스크를 만들어서 그곳에 가상 메모리를 작게 넣어두면 되겠네?" 라는 생각이 불현듯 치고 나올 수도 있습니다.

하지만 생각을 해보죠. 이렇게 램 용량이 충분하면 실제로 가상 메모리가 사용될 확률은 매우 적습니다. 이야기한 것과 같이 소수의 프로그램에서 아주 가끔 사용될 수도 있는 것이 전부겠죠. 그래서 가상 메모리도 오류 방지를 위해 최소한의 용량으로 만들어만 둔다는 의미가 강합니다. 극히 적은 확률로 사용될 가능성이 있는 가상 메모리를 위해 램 디스크 프로그램을 설치하고 설정하여 관리까지 한다?

뭐 램 용량이 정말 차고 넘쳐날 정도로 많거나, 그렇게 차고 넘쳐서 다른 용도로 어느 정도 넉넉하게 램 디스크를 사용한다면, 이러한 램 디스크에 가상 메모리도 작게 설정해두는 것은 고려해봄직 하긴 합니다. 하지만 일부러 오직 가상 메모리만을 위해서 램 디스크를 설치하는 것은 제 개인적인 의견일 수도 있지만 크게 효용 가치는 없다고 생각합니다. 그래서 디스크에서 1GB 정도를(물론 더 작게 설정해도 되고) 혹시 모를 오류를 위해 투자한다고 생각하시고 잊어버리시는게 좋지 않을까 생각합니다.




3. 가상 메모리는 고정된 크기로 설정하는 것이 좋다?

가상 메모리를 사용자 정의 크기 옵션을 통해 처음 크기와 최대 크기를 동일하게 설정해주어 가상 메모리의 크기가 동적으로 변하지 않게 해주는 것이 좋다는 이야기가 있습니다.

페이징 파일의 크기 고정

일단 가상 메모리의 크기가 동적으로 늘어나는 이유는 무엇일까요? 그것은 실제 램 공간은 물론 가상 메모리 공간조차도 부족하여 윈도우가 가상 메모리의 크기를 자동으로 늘리는 것입니다. 즉, 우선 이건 문제 해결의 초점이 잘못 맞춰진 경우입니다. 우리가 초점을 맞춰야 할 곳은 가상 메모리의 크기가 줄었다 늘었다하는 점이 아닌 "현재 설정된 가상 메모리의 크기" 조차도 부족하여 가상 메모리의 크기가 자꾸 늘어난다는 점입니다. 이는 가상 메모리의 처음 크기가 자신의 램 용량과 프로그램 사용량에 비해 너무 작게 설정되어 있음을 의미합니다. 이럴 땐 가상 메모리의 처음 크기를 좀 더 여유 있게 늘려주어야 함이 옳은 것이죠.

다음으로 애초에 가상 메모리의 크기를 전혀 부족하지 않게끔 크게 설정한 후 그 크기를 고정하는 방향으로 설정하는 경향도 있습니다. 물론 이렇게 해두면 가상 메모리가 늘었다 줄었다 하는 것을 보지 않아도 되는 이점은 있습니다. 하지만 쓸데없이 크게 설정한 가상 메모리는 디스크의 공간만 낭비하는 꼴입니다. 또한 그러한 설정 방식이 가상 메모리의 성능을 높여주는 것도 아닙니다.

결국 적절히 자신에게 맞는 크기를 스스로 찾아 그에 맞춰 설정해주는 것이 가장 좋습니다.




4. 나에게 적당한 가상 메모리 용량은 얼마일까?

가상 메모리의 최소 크기는 램 용량의 몇 배에서... 이러한 내용은 예전 램이 128MB 나 256MB 정도 밖에 달리지 않았을 때를 기준으로 한 것이라 너무 오래된 정보이고 요즘의 실정에는 잘 맞지 않습니다. 또한 요즘은 시스템에 장착되는 램 용량이 상당히 크기 때문에 윈도우에서 관리하는 기본 설정 값이 너무 큰 경우가 대부분입니다.

그래서 가장 좋은 것은 역시나 자신이 직접 자신에게 맞는 최적화된 값을 찾아내는 것입니다. 방법은 간단합니다. 사용자 지정 크기를 통해 가상 메모리의 처음 크기를 최소값인 (64bit 기준) 16MB 로 설정하고 최대 크기는 일단 충분히 크게 지정합니다.

처음 크기를 최소 크기로 최대 크기는 충분히 늘어날 수 있을 만큼

이와 같이 설정을 한 후 재부팅하여 변화를 적용하고, 이제 평상시 사용하는 정도로 프로그램들을 실행하는 겁니다. 인터넷 익스플로러나 크롬과 같은 웹 브라우저는 열린 창의 개수에 비례해 램 용량을 그만큼 더 잡아먹기 때문에 인터넷 창도 대충 평상시 자신의 습관에 알맞게 적당히 띄워줍니다.

이제 그렇게 프로그램들이 실행된 상태에서 가상 메모리 설정 창으로 들어가 봅니다. 그럼 자신이 사용한만큼 가상 메모리의 크기가 늘어나 있을 겁니다. 만약 가상 메모리가 전혀 늘어나지 않았다면 그건 아직 그정도로는 가상 메모리가 사용되지 않을 만큼 여러분의 램 용량이 충분하다는 것입니다.[그게 가장 좋습니다.]

자신의 사용량에 맞춰 늘어난 가상 메모리 용량

하지만 램 용량이 1GB~2GB 로 소용량이시거나 사용하는 프로그램들이 굉장히 무거운 경우 보통 가상 메모리 크기가 처음에 비해 어느 정도 늘어나 있을 겁니다. 그 용량이 자신에게 필요한 평균적인 가상 메모리의 크기입니다.

결론 나왔죠? 이제 그 크기에 약간의 여유를(약 1.2 ~ 1.5 배 정도면 충분) 주어 가상 메모리의 처음 크기를 설정해주고, 최대 크기도 마찬가지로 처음 크기에서 어느 정도의 여유를 더 주는 방향으로 설정해주시면 됩니다. 이런 식으로 자신에게 맞는 가상 메모리의 크기를 찾으시고 그에 맞춰 설정해주는 거죠. 간단하죠?


그런데 만약 가상 메모리의 크기가 무슨 주유소 기름값 마냥 무서운 줄 모르고 쭉쭉~ 치고 올라가면서 버벅인다면? 그건 현재 램 용량이 그만큼 부족한 겁니다. 램 용량 좀 업그레이드 하세요.




5. 가상 메모리는 사용되지 않을 수록 좋다.

처음에 밝힌 것과 같이 가상 메모리는 실제 메모리의 공간이 부족할 때 사용되는 것입니다. 실제 메모리와 가상 메모리의 속도 차이 즉, 램과 디스크의 속도 차이는 하늘과 땅 차이라고 할 수 있습니다. 앞서 SSD 와 HDD 를 농담삼아 포르쉐와 경운기에 비교했지만, 램과 디스크는 램의 속도를 전투기에 비유하자면 디스크의 속도는 거북이에 비유할 수 있을 정도입니다.

애초에 둘을 비교하는 것 자체가 넌센스

이건 디스크에서 그 빠르다는 SSD 가 출동해도 램에게는 게임이 안 되는 겁니다. 아무튼 그래서 윈도우가 가상 메모리를 자주 그리고 많이 사용하게 되면 램보다 느린 디스크로 인해 그만큼 시스템의 성능 또한 뚝뚝 떨어지게 됩니다. 소위 버벅이는 거죠. 그래서 가상 메모리는 되도록이면 사용되지 않는 것이 가장 좋습니다. 

가상 메모리가 자주 그리고 많이 사용된다는 것은 현재 시스템의 물리적인 메모리의 용량(RAM 용량)이 부족하다는 것을 의미합니다. 이것은 램 용량을 충분하게 늘려 윈도우가 가상 메모리를 사용할 가능성을 최대한 줄여주는 것 외에는 방법이 없습니다. 즉, 시스템에 충분한 용량의 램을 장착해 주어야 문제를 해결할 수 있다는 것이죠. 고로

램에 돈을 좀 꽂아주면 됩니다.

돈이 세상의 전부는 아니지만, 돈을 바르기 시작하면 안 되는 것도 드물죠. 아무리 최적화하고 용을 쓰고 별에 별 팁을 다 적용해도 돈을 들이붓는 놈한테는 못 당해요. 잔인하지만 사실이잖아요? 그러니 우리는 램 용량에 과감히 투자를 해야 합니다. 다행히도 몇 년 전부터 램 값이 많이 쌉니다.

일단 램 용량은 무조건 크면 클 수록 좋습니다. 이건 진리입니다. 그래도 이야기를 해 보자면 일반적으로 간단한 웹 서핑 및 소소한 인터넷 캐쥬얼 게임용이라면 최소 2GB 적정 4GB, 인터넷 창도 수십 개씩 좀 화끈하게 띄우고 프로그램도 한 번 열면 닫을 줄을 모른다면 8GB 정도 생각하시면 된다고 할 수 있습니다.

사실 보통 이야기하는 것에 비해 좀 많은 것 아닌가? 라는 생각이 들 수 있을 정도로 추천을 했는데요. 제 오랜 경험상 램 용량은 그 사람이(자신이) 현재 원하는 작업 수준보다 한 단계 더 높게 약간 넘치는 듯한 느낌이 들 정도의 용량으로 셋팅해주는 것이 좋습니다. 그리고 이렇게 보다 큰 용량을 자신있게 추천을 하는 이유는 요즘 램 값이 싸니까요.

이제 가상 머신 두 세 개는 우습게 돌리면서 이것 저것 무거운 프로그램들을 많이 쓰시거나, 캐드 다루시거나, 동영상을 전문적으로 편집하시거나, 포토샵으로 수백 메가짜리 파일들을 우습게 여시는 분들은 메인보드가 지원하는 한 최대로 꽂아주시는게 무조건 좋습니다. 꽂아 넣을 수 있을 때까지 꽂아 넣으세요. 그건 돈지랄이 아니에요. 그리고 요즘 램 값이 많이 싸잖아요?

1 년 전에 윈도우 7 을 기준으로 하여 포스팅했던 것을 약간의 설명을 더 추가하고 전체 윈도우에 맞춰 설명을 수정하여 다시 재 포스팅하였습니다. 크게 바뀐 부분은 없지만 어떻게 그때보다 글이 더 잘 나왔는지 모르겠네요. 아무튼, 1 년 전에도 그랬고, 지금도 그렇지만 윈도우 가상 메모리의 진리는 하나입니다.

지금이 램 뱅크를 풀로 채워볼 적기입니다.

램 용량을 좀 충분하게 업그레이드 하시고 가상 메모리는 대충 쓰시면 됩니다. 32GB 풀 뱅크를 노려보세요. 이상입니다. ^^;;

1. Page table management

- user mode인데 page가 없고 write mode : user memory에 page 할당

- kernel mode        ""           ""      : kernel memory에 page 할당

- stack 범위 내에 존재하지 않을 경우 프로세스 종료시킴

크리스마스에 프로젝트는 무슨ㅗㅗㅗㅗㅗ

pintos tip

- 매뉴얼과 보고서를 매우 자세히 읽어본다

- 각 헤더파일들을 잘 읽어본다 특히 thread.h, process.h 

- 족보는 한번만 슥 보고 머리속에 잊어버린다

- 컴터에 리눅스깔아서 한다고 깝치지말고 cspro에서 한다

- gdb 쓴다고 깝치지말고 printf를 적극활용 한다

- 집에서 혼자한다고 깝치지말고 랩실가서 동기들과 함께한다

- 치킨은 이틀에 한마리씩 먹는다

- 너무 어렵다면 드랍하고 막학기에 듣고 프로젝트 안하고 D만 받고 졸업한다

- 아니면 복전을 한다

- 박성용 교수님 짱짱맨

1. What?

1.1 System calls about file system

1.2 Synchronization

2. How?

2.1 System calls about file system

- file system 을 위해서 thread는 child list외에도 file list가 필요함. 파일이 만들어질 때마다 파일 리스트에   추가해서 thread의 파일 들을 관리함.

- 파일 멤버는 fd(file descriptor), file pointer, file_elem 을 포함해야함

2.2 Synchronization

- process wait, exit 함수에서는 zombie process 처리 필요.

- 부모가 wait할 때는 자식이 zombie일 때, sema_up을 해서 정상적으로 종료 될 수 있도록 다시 꺠워줌

- 자식이 exit할 때는, sema_down을 통해서 재워야함. 부모가 wait해줄 때까지 기다려야함

- 실행 중인 file에 write하면 안됨. file_deny_write 함수를 통해 가능

- load & execute process 들을 synchronization

3. Detail

3.1 System calls about file system

- project 2-1과 마찬가지로, system call handler에서 user function이 system call function을 호출한다

  대신 각 함수마다 추가 작업이 필요하다. 

- user_create : filesys_create 호출

- user_open : filesys_open 호출, file member가 만들어졌으면 file descriptor(fd)를 초기화 후 고유 값으로               지정. 그리고 thread의 file list에 추가해줌

- user_close : file list에서 닫으려는 파일을 찾은 후 리스트에서 지우고, file_close 호출

- user_remove : filesys_remove 호출

- user_read : file list에서 읽으려는 파일을 찾고, file_read로 파일을 읽음

- user_write : user_read와 마찬가지, list에서 파일 찾고, file_write로 씀

3.2 Synchronization

- zombie semaphore와 load semaphore를 추가해줌

3.2.1 process_wait

- parent가 wait하면, wait flag를 setting한다. child는 exit할 때, flag를 통해 zombie인지 아닌지 확인     할 수 있다.

- parent가 child list에서 인자로 받은 tid와 일치하는 child를 찾는다.

  zombie이면 process의 zombie semaphore를 up시켜서 process_exit 에서 zombie process가 block   된 상태의 뒷 부분을 수행 한 후 정상적인 종료가 될 수 있도록 한다.

- zombie가 아니라면 정상적으로 wait operation을 한다.

  child는 process_exit에서 parent의 sema를 up시켜, block 상태에서 깨우고, child list에서 자신을 삭   제한다

- wait 마지막에서 parent는 child의 exit status를 리턴한다.

3.2.2 process_exit

- process_exit가 호출되면 process가 zombie인지 확인한다

  parent가 wait하고 있지 않으면(wait flag가 없으면) 자식은 zombie process이다.

- zombie process임을 확인했으면, zombie sema를 down시켜 재워버린다

  바로 resource deallocation되면 안되고, parent가 제대로 wait을 호출할 때 까지 기다린다

- zombie가 아니면 parent의 sema를 up시켜서 wait중인 parent를 꺠운다. 

3.2.3 denying writes to executables

- file open할 때, 실행 파일에 대해 쓰기 거부를 설정함

  메모리에 파일을 load한 후에 수정하면 안되니까

- user_open system call에서, 파일을 open하면 file list에 삽입

  file list를 탐색해서 일치하는 file을 찾으면 file_deny_write를 통해 쓰기 거부 설정

3.2.5 synchronization in load & execute

- parent가 10개의 child를 생성하고, 각각 load와 execute를 함

  한 child가 execute 하는 도중 다른놈이 load하면 안됨

- execute 하던 놈은 load sema를 down시켜서 block 후 대기

  load 하던놈이 끝나면 load sema를 up시켜 block을 해제 해서 다시 execute

1. What?

1.1 Argument passing & User memory access

1.2 System call infrastructure

1.3 Process operation

2. How?

2.1 Argument passing & User memory access

- parse_filename 함수에서 command line을 argument parsing 한다.

  strtok_r() 함수를 이용, parsing 후 argv(argument vector) 에 저장한다

- construct_esp 함수에서 parsing 된 argument들을 stack에 저장한다

  argv를 인자로 받아와서 stack에 차례로 push한다. 하나 저장할 때 마다 esp를 하나씩 감소시킨다.

- user program 실행 시, kernel memory를 침범했을 때 error 처리를 한다

  stack pointer가 PHYS_BASE보다 작아야함, is_user_vaddr() 함수를 이용

2.2 System call infrastructure

- 시스템으로부터 넘겨받은 intr_frame 정보로, 각 system call number에 해당하는 system call을 호출.

  system call 호출 시 필요한 argument들을 같이 넘겨줘야함. intr_frame의 esp 포인터를 이용해서     argument들을 인자로 전달할 수 있다. (esp+1, esp+2, etc)

2.3 Process operation

- process wait : semaphore ( sema_down() ) 을 이용해서 process wait을 구현한다.

- process exit : process(child)가 종료될 때 필요한 작업을 수행해야함. wait 중인 process(parent)를 깨워                   줘야함. sema_up() 으로 가능, 그 후 parent의 child list에서 child process를 삭제

- process execute : filesys_open() 을 통해서 유효하지 않은 process에 대해 에러처리

3. Detail

3.1 Argument passing & User memory access

3.1.1 pares_filename() 

- 입력받은 command line을 tokenize, token들은 argv에 저장하고, token의 개수를                       count하여 return한다. return된 count는 argc에 저장된다.

3.1.2 construct_esp() 

- esp를 감소시키면서(PHYS_BASE부터 아래로 내려가므로), 저장된 argv들을 stack에 저장한다.

3.1.3 user_memory access 

- user memory를 벗어나 kernel memory에 침범했을 시, 에러처리해야함.                         is_user_vaddr() 함수를 사용하면 된다.

3.2 System call infrastructure

- user program이 실행되면 interrupt를 통해 system call handler가 호출된다. (system call은 user program   에서 호출한 function들과, kernel function 사이의 interface와 같은 것임)

- system call handler는 interrupt frame을 인자로 전달받는데, 호출하려는 system call의 number를 알 수     있다. 분기문을 통해 system call의 number에 해당하는 system call function을 호출하면 된다.

- frame의 esp를 통해 stack에 접근할 수 있다. command를 parsing하면서 저장한 argument을 가져올 수   있는 것이다. 이 argument들을 system call 함수 호출시 인자로 넘겨줘야 한다.

3.3 Process operation

3.3.1 process wait

- process wait을 하려는 process는 parent process이다. user program은 child process로서, parent로   부터 만들어진 후 실행 된다. 따라서 parent는 child가 모든 실행을 끝마치고 값을 return할 때 까지     wait해야 한다.

     - parent process의 child list에서(원래 없음 만들어야함), 함수의 인자로 전달된 child_tid와 일치하는           child process를 찾는다. 

     - 그 후 parent의 sema를 down 시킨다. 그러면 parent는 child가 작업이 끝난 후 sema up 시킬 때까          지 wait하게 된다.

3.3.2 process exit

- child process가 실행을 마친 후 종료될 때 먼저 wait중인 parent process를 깨운다. sema_up을 통해   깨울 수 있다. sema_up의 인자로 parent의 sema structure를 넘겨주면 된다. 

     - 그 후에는 child의 page directory가 삭제 된다 (이건 원래 구현되어있음). 그리고 현재 child를 부모의        child list에서 삭제해준다.

     - 마지막으로 현재 child를 block 시킨다. thread_block을 하면 현재 process의 status가 running에서           blocked로 바뀌게 된다. interrupt를 disable 시켜야 thread block이 가능하다 

3.3.3 process excute

-  제대로 생성되지 않은 file에 대한 예외처리만 해주면 된다. filesys_open 함수를 통해 file을 open하      는데, 성공시 true, 실패 시 NULL을 return한다. 값이 NULL이면 -1을 return해주고 끝내면 된다.

1. What?

1.1 alarm clock 구현, busy waiting 해결

1.2 priority scheduler 구현

1.3 priority aging 구현

2. How?

2.1 alarm clock

- 기존의 timer sleep이 busy waiting으로 되어있음, while을 계속 확인해야한다. cpu time 낭비

- timer interrupt 사용, 설정 시간이 지났을 때 ready state로 바꾸고 ready list에 삽입해줌 

  (timer interrupt handler에서 처리해줌)

2.2 priority scheduling

- 기존에는 thread가 생성된대로 scheduling 되고 있음, convoy effect이 발생할 수 있고, average waiting     time이 길다. thread가 생성될 때( thread_create() ), thread_unblock() 을 호출하면서 ready list의 맨 뒤    에 삽입됨.

- thread들이 priority에 따라 scheduling 되도록 구현

2.3 priority aging

- 기본적인 priority scheduling은 starvation 문제가 발생할 수 있음

- thread가 생성된 시간에 비례하여 priority를 증가시키는 aging을 구현

3. Detail

3.1 alarm clock

- timer_sleep이 호출될 때, timer_sleep() 에서 wake up time을 thread의 wakeup_time에 저장후, sleep list   에 저장

- thread를 block시키고 context switching 되는데, 이 때 interrupt는 disable 되어야함

- 일정 시간마다 timer interrupt가 발생하고, timer_interrupt() 에서는 sleep list 내의 thread들을 확인, 조건   문을 통해 wake up time이 지났는지 확인

- 확인되었으면 sleep list에서 삭제한 후, thread를 unblock 시켜줌 

3.2 priority scheduling

- 기존의 방식은 FCFS, scheduler는 ready list의 맨 앞에 있는 thread부터 처리함

- scheduler는 priority가 큰 순서대로 처리하므로, ready list를 priority가 큰 순서대로 정렬해야함

- list를 정렬하기 위해 compare 함수를 만들음

3.3 priority aging

- ready list를 정렬하면서 priority가 작은 thread들은 ready list의 맨 뒤로 밀려남

- ready list의 맨 끝의 thread들의 priority를 증가시켜줌 

Chapter 8 Memory-Management Strategies

8.1 Background

8.1.1 Basic Hardware

8.1.2 Address Binding

8.1.3 Logical versus Physical Address Space

8.1.4 Dynamic Loading

8.1.5 Dynamic Linking and Shared Libraries

8.2 Swapping

8.3 Contiguous Memory Allocation

8.3.1 Memory Mapping and Protection

8.3.2 Memory Allocation

8.3.3 Fragmentation

8.4 Paging

8.4.1 Basic Method

8.4.2 Hardware Support

8.4.3 Protection

8.4.4 Shared Pages

8.5 Structure of the Page Table

8.5.1 Hierarchical Paging

8.5.2 Hashed Page Tables

8.5.3 Inverted Page Tables

8.6 Segmentation

8.6.1 Basic Method

8.6.2 Hardware

8.7 Example : The Intel Pentium

8.7.1 Pentium Segmentation

8.7.2 Pentium Paging

8.7.3 Linux on Pentium Systems

8.8 Summary

------------------------------------------------------------------------

8장 Memory-Management Strategies

이 장에서는 메모리를 관리하기 위한 다양한 방법들을 알아본다.

memory management 알고리즘들은 고전적인 bare-machine적 접근에서부터 paging과 segmentation 까지 다양한 

방법들이 있다. memory management 방법은 시스템의 하드웨어적 디자인에 많은 영향을 받는다.

8장에서 많이 사용할 용어들.

base register = relocation register

limit register

logical address = virtual address

physical address

메모리를 할당하는 법

1) contiguous --> partition

fixed sized의 partition과 dynamic sized의 partition 방법이 존재.

2) noncontiguous --> paging, segment

paging은 크기별로 나누는 것. segment는 기능별로(모듈별로) 나누는 것.

8.1 Background

8.1.1 Basic Hardware

cpu안에 내장된 레지스터들은 일반적으로 1 cycle의 cpu clock내에 접근이 가능하다.

메인 메모리의 경우는 그렇지 못한데, 메모리에 대한 접근은 많은 cycle의 cpu clock을 가지게 된다.

그렇기 때문에 cpu와 메인 메모리 사이에 빠른 메모리를 사용하는데, 이러한 메모리 버퍼를 cache라 한다.

8.1.2 Address Binding

보통 프로그램은 binary executable file로 디스크 안에 존재한다. 프로그램이 실행되기 위해서는 반드시 메모리로 옮

겨져 프로세스 안에 위치되어야 한다. 디스크 안에서 메모리로 옮겨지길 기다리는 프로세스들은 input queue를 형성

한다. 그러면 input queue에 있는 프로세스들 중 하나를 선택해 메모리로 프로세스를 로드한다.(일반적 방법)

많은 경우에 유저 프로그램은 실행되기 전에 많은 단계들을 거치게 된다. 이 단계들을 거치는 과정에서 주소값들은 다

양한 방식으로 표현된다. 소스 프로그램 내의 주소들은 일반적으로 symbolic address로 표현이 되는데, 컴파일러가

이러한 symbolic address를 relocatable address로 bind한다. linkage editor나 loader는 이 relocatable address를 

다시 absolute address로 bind한다. bind 한다는 것은 하나의 address 공간을 다른 address 공간으로 mapping 하는 

것을 의미한다. 

일반적으로 instruction들과 data들을 메모리 주소로 바인딩 하는것은 다음 방식을 통해 이루어질 수 있다.

1) Compile time

컴파일 타임때 프로세스가 메모리의 어디에 위치할  것인지를 알고있다면 absolute code가 만들어 질 수 있다.

2) Load time

컴파일 타임때 프로세스가 메모리의 어디에 위치할 지 알 수 없다면 컴파일러는 반드시 relocatable code를 만들어야 

한다. 이경우 최종적인 바인딩은 load time까지 미뤄진다.

3) Execution time

만약 프로세스가 실행중에 한 메모리 segment에서 다른 segment로 옮겨질 수 있다면 바인딩은 반드시 run time때까

지 미뤄져야 한다. 특별한 하드웨어가 이러한 scheme이 동작하기 위해 가능해야 한다. 

가장 일반적인 목적의 os들이 이 방식을 사용한다.

8.1.3 Logical versus Physical Address Space

cpu에 의해 만들어지는 주소는 보통 logical address라고 하는데, 이에 반해 memory unit에 의해 보여지는 주소를

physical address라고 부른다. (메모리의 memory-address 레지스터로 로드되는 주소)

compile time과 load time 때의 address binding 방식은 동일한 logical address와 physical address들을 만들어낸

다. 하지만 execution-time의 address binding 방식은 서로 다른 logical address와 physical address를 만들어낸다.

(일반적으로 logical address를 virtual address라고 부른다.)

virtual address에서 physical address로의 run-time mapping은 MMU라고 하는 하드웨어 디바이스에 의해 이루어진

다. 이러한 mapping을 하기 위한 수많은 방법들을 8.3장부터 8.7장까지 알아본다.

여기서는 8.1.1장에서 소개한 base-register scheme의 일반화된 MMU scheme을 이용해 이 mapping을 소개해본다.

base register는 이제 relocation register라고 부른다.

relocation register에 있는 값은 유저프로세스에 의해 만들어지는 모든 주소들이 메모리에 보내질 때 더해진다.

유저 프로그램은 절대 실제 physical address들을 볼 수 없다. 유저프로그램은 logical address들을 다룬다.

memory-mapping hardware(MMU)는 logical address들을 physical address들로 변환시킨다.

유저는 오직 logical address들만 만들어내는데 이러한 logical address들은 반드시 사용되기 전에 physical

address 들로 mapping되어야 한다.

8.1.4 Dynamic Loading

좀더 효율적으로 메모리 공간을 사용하기 위해 우리는 dynamic loading을 사용한다. dynamic loading을 사용하면

routine이 called 되기전까지 load되지 않는다. 모든 routine들은 relocatable load의 format으로 디스크에 위치해있는

다. 메인 프로그램은 메모리에 로드되어 실행된다. routine이 다른 routine을 호출해야할 상황이 발생하면, 호출하는 

routine은 먼저 다른 routine이 로드되어있는지를 확인한다. 로드되어있지 않는다면 해당 routine을 메모리에 로드하기

위해 relocatable linking loader를 호출한다. 그러고나면 새로 로드된 routine에게 컨트롤이 전달된다.

dynamic loading의 장점 : 사용되지 않는 routine은 절대 로드되지 않는다. 자주 발생하지 않지만 처리를 위해 많은 양

의 코드가 필요한 경우 유용할 수 있음 (ex error routine)

또한 dynamic loading은 os로부터 특별한 지원이 필요 없다.

8.1.5 Dynamic Linking and Shared Libraries

몇몇 os들은 static linking만을 지원하는데, static linking이란 시스템 language 라이브러리들이 다른 object module

과 같이 취급되어 로더에 의해 binary 프로그램 이미지로 합쳐지는 것을 의미한다.

반면 Dynamic linking은 dynamic loading과 유사한데, linking이 execution time때까지 미뤄지는 것을 의미한다.

dynamic linking에서는 stub이 각각의 라이브러리 루틴 참조를 위해 이미지 안에 포함되어 있다.

stub이란 루틴이 없을 때 어떻게 라이브러리를 옮길 것인지에 대한 것을 가리키는 작은 코드 조각이라 할 수 있다

stub이 실행되면, stub은 필요한 루틴이 메모리에 있는지를 확인한다. 메모리에 없는 경우 프로그램은 해당 루틴을

메모리에 로드한다. stub은 자기 자신을 루틴의 어드레스로 대체하고 해당 루틴을 실행한다.

그렇기 때문에 다음번에 실행될때는 해당 라이브러리의 루틴이 바로 실행될 수 있다.

dynamic loading과는 다르게 dynamic linking은 일반적으로 os의 도움을 필요로 한다.

8.2 Swapping

프로세스가 실행되기 위해서는 반드시 메모리에 위치해있어야 한다. 하지만 프로세스는 일시적으로 메모리에서

backing store로 swapped될 수 있으며 연속적인 실행을 위해 다시 메모리로 불러들여질 수 있다.

이러한 방식은 Round-Robin의 cpu 스케쥴링 알고리즘에서 사용될 수 있다.

그리고 swapping policy의 변형이 priority-based 스케쥴링 알고리즘에서 사용된다.

높은 우선순위의 프로세스가 도착했을때 낮은 우선순위의 프로세스가 swap out 되고 높은 우선순위의 프로세스가

swap in 된다. 높은 우선순위의 프로세스가 실행을 마치면 다시 낮은 우선순위의 프로세스가 swap in되어 실행을 

계속한다. priority 기반의 스케쥴링에서는 이를 roll out, roll in이라 부른다.

일반적으로 swapped out된 프로세스는 자신이 차지하던 동일한 메모리 공간으로 다시 swapped in 되어진다.

하지만 만약 binding이 assembly time이나 load time때 행해진다면 프로세스는 다른 공간으로 쉽게 옮겨갈 수 없다. 

반면 execution-time 바인딩이 사용된다면 프로세스는 다른 메모리 공간으로 swapped in 될 수 있는데, 왜냐하면 

physical address가 execution time 때 계산되기 때문이다.

이러한 swapping 시스템에서 컨텍스트 스위칭 타임은 꽤나 비중이 높아진다.

8.3 Contiguous Memory Allocation

메인메모리는 os와 다양한 유저 프로세스들을 수용해야 한다. 따라서 메인 메모리는 가장 효율적으로 할당되어야 한

다. 이번 장에서는 contiguous memory allocation이라는 하나의 방법을 설명한다.

메모리는 일반적으로 os를 위한 공간과 유저 프로세스들을 위한 공간으로 나뉘어진다.

우리는 input queue에 있으면서 메모리로 불려지길 기다리는 프로세스들에게 어떻게 이용가능한 메모리들을 할당할

수 있는지를 고려해봐야 한다.

contiguous memory allocation에서는, 각각의 프로세스들이 메모리의 인접한 하나의 공간에 위치하게 된다.

8.3.1 Memory Mapping and Protection

memory allocation에 대해 얘기 하기 전에, memory mapping과 protection에 대해서 이야기 해 보자.

우리는 memory mapping과 protection을 relocation register와 limit register를 함께 이용해서 제공할 수 있다.

relocation register는 smallest physical address의 값을 가지고 있다.

limit register는 logical address의 범위를 가지고 있다.

각각의 logical address들은 반드시 limit register보다 작아야 한다.

MMU는 logical address에 relocation register의 값을 dynamically 하게 더함으로써 mapping한다.

이렇게 mapping된 주소가 메모리로 보내진다.

cpu에 의해 만들어지는 모든 주소가 이들 레지스터들을 가지고 체크되어지기 때문에 os와 유저들의 프로그램들이 

수정되지 않도록 보호할 수 있다.

8.3.2 Memory Allocation

프로세스들에게 메모리를 contiguous 하게 할당하는 방법

1) fixed-sized partition --> interal fragmentation 발생

2) variable-sized partition(dynamic) --> external fragmentation 발생

메모리를 할당하는 가장 쉬운 방법은 메모리를 여러개의 fixed-sized partition들로 나누는 것이다.

각각의 파티션들은 정확히 하나의 프로세스를 포함할 수 있다. 그렇기 때문에 파티션들의 갯수에 따라 

multiprogramming의 정도가 결정된다. 이러한 multiple-partition 방법에서는 파티션이 비어있을 때 프로세스가 

input queue로부터 선택되어서 해당 파티션으로 로드된다. 

다음으로 소개할 방법은 variable-partition scheme이다.

여기서 os는 메모리의 어느 부분이 이용가능하고 어느 부분이 차지되고 있는지를 나타내는 table을 가지고 있다. 

프로세스가 시스템에 진입하게되면 프로세스들은 input queue에 들어간다. os는 각각의 프로세스들이 요구하는 메모

리의 양과 사용가능한 메모리 공간을 고려해서 프로세스에게 메모리 공간을 할당한다.

프로세스가 종료되면 프로세스는 자신의 메모리 공간을 release하며 os는 그 자리에 다른 프로세스들을 채워넣는다.

프로세스들이 메모리에 할당되고 release 되고를 반복하다보면 메모리 내에는 다양한 크기의 hole들이 생기게 된다.

프로세스가 메모리를 요구할때 시스템은 프로세스가 요구하는 메모리공간에 맞는 hole을 찾아야 하는데, 여기에는 

3가지 방법이 존재한다.

1) First fit

맨 처음 찾아낸 할당할 수 있는 크기의 hole을 할당한다. 

2) Best fit

딱 맞는 크기의 hole을 할당한다. 전체 list를 다 뒤져봐야 한다.

3) Worst fit

가장 큰 hole을 할당한다. 역시 전체 list를 다 뒤져봐야 한다.

일반적으로 first fit과 best fit이 worst fit보다 시간감소와 storage utilization 측면에서 낫다.

8.3.3 Fragmentation

fragmentation의 종류

1) external fragmentation

variable-sized partition(dynamic) 에서 프로세스들이 메모리에 들어가고 나감에 따라 생기게 되는 빈 공간들을 의미한다.

2) internal fragmentation

프로세스가 partition에 들어갈 때, partition의 크기보다 프로세스의 공간이 약간 작아서 생기게 되는 남은 공간을 의미한다.

--> partition에 internal하다

external fragmentation 문제의 해결방법은 다음 두가지가 있다.

1) compaction

남는 메모리 공간들을 하나로 모으는 것인데, relocation이 dynamic하고 execution time때 수행될때만 가능한 방법

이다.

2) logical address space를 noncontiguous 하도록 허락.

프로세스들의 logical address space를 noncontiguous 하도록 허락함으로써, 메모리가 이용가능할때마다 프로세스

가 physical memory에 할당되는 것을 허락하는 방법이다. Paging과 segmentation이 이러한 방법을 사용한다.

8.4 Paging

Paging이란 프로세스의 physical address space를 noncontiguous하도록 허락하는 memory management 방법이다.

Paging은 equal size의 fixed-sized partition과 유사하다.

장점 : external fragmentation이 일어나지 않기 때문에 compaction이 필요 없다.

(남게 되는 frame들을 다른 프로세스에게 할당할 수 있기 때문이다.)

단점 : internal fragmentation은 일어날 수 있다.

8.4.1 Basic Method

paging을 구현하는 기본적인 방법은 physical 메모리를 frame이라고 하는 fixed sized block들로 나누고,

logical memory를 page라고 하는 같은 크기의 block으로 나누는 것이다.

프로세스가 실행될때 프로세스의 page들은 backing store에서 사용가능한 아무 메모리 frame들로 로드된다.

backing store역시 메모리 frame들과 동일한 크기의 fixed sized block들로 나눠진다.

cpu에 의해 만들어지는 logical address들은 두개의 파트로 나누어진다.

1) page number (p)

2) page offset (d)

pagenumber는 page table의 인덱스로 사용된다. page table은 각각의 page들에 대한 base address를 가지고 있다.

이 base address는 page offset과 결합되어 physical memory address를 정의하게 되고, 이 주소가 메모리 유닛에게

보내진다.

예제는 330p 참고

paging 그자체는 dynamic relocation의 한 형태이다.

모든 logical address들이 paging hardware에 의해 physical address로 bind된다.

paging을 사용하는 것은 base register들의 table을 사용하는 것과 유사하다.

첫번째 프로세스의 page가 frame에 할당되면 해당 frame number가 page table에 저장된다.

그다음 page가 다른 frame에 할당되면 해당 frame number가 page table에 저장되고.. 이런식이다.

paging에서 중요한 면은 유저가 보는 memory 관점과 실제 physical memory 관점이 완벽하게 분리되어 있다는 것이

다. 유저 프로그램은 메모리를 자신의 프로그램만 포함하는 하나의 공간으로 인식한다. 하지만 사실 유저의 프로그램

은 physical memory 곳곳에 흩어져 있다. cpu가 만들어내는 logical address들은 address-translation hardware에

의해 physical address들로 변환된다. 이러한 mapping은 유저에게 가려져 있고 os에 의해 컨트롤된다.

프로세스는 자신의 page table 바깥의 메모리공간에 접근할 수 없으며 page table은 해당 프로세스가 소유하고 있는

page만을 포함하고 있다. paging은 컨텍스트 스위칭 타임을 증가시키는데, 각각의 프로세스들마다 page table의

copy를 os가 갖고 있어야 하기 때문이다.

8.4.2 Hardware Support

하드웨어적으로 page table을 구현하는 방법은 여러가지가 있다.

1) 여러 레지스터들을 사용하여 page table을 만들기

장점 : 레지스터를 사용하기 때문에 속도가 빠르고 효율이 높아진다.

단점 : 대부분의 컴퓨터들은 page table이 매우 크기 때문에 현실적으로 힘들다.

그래서 일반적으로 page table을 메인 메모리에 두고서, page-table base register(PTBR)가 page table을 가리키게 한다.

이 방식에서는 byte에 접근하기 위해 두번의 메모리 access가 필요하다. (한번은 page-table entry, 한번은 byte)

두 번의 메모리 access에 따른 딜레이는 대부분의 환경에서 부적합하다.

2) translation look-aside buffer(TLB) 사용

일반적인 해결법은 translation look-aside buffer(TLB)라고 하는 특별하고 작고 빠른 lookup hardware cache를 사용

하는 것이다. TLB안의 entry는 page number와 frame number로 이루어져 있고, TLB는 일부의 page-table entry들만

을 포함한다. 먼저 cpu에 의해 logical address가 만들어지면, logical address의 page number를 TLB 안에서 찾는

다. page number가 찾아지면, 해당 page number의 frame number는 즉시 이용가능하며 메모리에 access하기 위해

사용된다. 만약 page number가 TLB안에 없다면(이를 TLB miss라 함) 메모리로 가서 page table에 접근해 page

number를 찾아야 한다. frame number가 획득되어지면 우리는 이를 통해 메모리에 access 할 수 있게된다. (fig 8.11)

TLB miss가 났을 때에는 해당 page number와 frame number를 TLB에 저장하고 다음번 참조때 더 빨리 찾아질 수 있

게 한다. 특정 page number가 TLB안에서 찾아질 확률을 hit ratio라 한다.

만약 TLB안에서 page number를 못찾으면 메모리를 두번 access해야 한다.

8.4.3 Protection

paged 환경에서의 memory protection은 valid-invalid bit이라는 하나의 bit을 사용하는데, 이 bit를 page table의

각각의 entry들에 붙여 memory를 protect 한다.

bit이 valid로 설정되어 있다면, 관련된 page가 프로세스의 logical address space에 있으며 valid page임을 나타낸

다. bit이 invalid로 설정되어 있으면 page는 프로세스의 logical address space에 있지 않음을 나타낸다.

운영체제는 각각의 page마다 이 bit들을 set함으로써 page에 대한 접근을 허용하거나 허용하지 않는다.

몇몇 시스템들은 page-table length register(PTLR)이라는 형태의 hardware를 제공하는데, PTLR은 page table의 사

이즈를 가리킨다. 이 값이 모든 logical address에 대해 체크되어서 address가 프로세스의 valid range에 있는지를

확인한다.

8.4.4 Shared Pages

paging의 장점은 같은 코드를 sharing 할 수 있다는 점에 있다.

이는 time-sharing 환경에서 특히 중요하다. 만약 코드가 reentrant code이면 프로세스들끼리 share가 가능하다.

오직 한 프로그램(예를 들면 editor)의 copy만이 physical memory에 존재하고, 유저들의 각각의 page table들은

editor의 동일한 physical copy를 mapping 시켜놓는다. 그리고 유저 각각들이 사용하는 data는 서로다른 frame으로

mapping시켜 사용한다.

8.5 Structure of the Page Table

이 장에서는 page table을 구조화 하는 일반적인 기술들에 대해 살펴본다.

8.5.1 Hierarchical Paging

왜 이 개념이 나오게 되었는가?

대부분의 현대 컴퓨터 시스템들은 커다란 logical address space를 지원한다.(32bit, 64bit)

이러한 환경에서 page table은 그자체의 사이즈가 굉장히 커질 수 있다.

ex)

32-bit의 logical address space를 가지는 시스템이 있고 시스템의 page size가 4KB인 경우

page table은 그 자체로 백만개의 entry들을 가지게 된다. 각각의 entry들이 4byte로 이루어졌다고 가정하면

각각의 프로세스들의 page table을 저장하기 위해서 최대 4MB의 physical address space 공간이 필요하다.

그래서 나오게 된 개념이 Hierarchical Paging이다.

Hierarchical Paging이란 page table들을 작은 조각들로 나눠서 사용하는 것이다.

이 때 two-level paging 알고리즘을 사용한다.

32-bit logical address space와 4KB의 page size를 사용하는 시스템을 생각해보자.

logical address는 20bit의 page number와 12bit의 page offset으로 나뉘어진다.

여기서 20bit의 page number가 다시 10-bit page number와 10-bit page offset으로 나뉘어진다.

반면 64-bit logical address space의 시스템에서는 two-level paging 방법이 더이상 적합하지 않게된다.

여기서 two-level paging을 적용하면 outer page의 사이즈가 다시 막대하게 되므로 이를 피하기 위해 outer page

table을 다시 작은 조각들로 나눈다. (three-level paging, four-level paging..)

단점 : 그래도 결국 64-bit 아키텍쳐들에서 hierarchical page table은 일반적으로 부적합하다.

8.5.2 Hashed Page Tables

왜 이 개념이 나오게 되었는가?

Hierarchical page table과 같이 32bit보다 큰 address space들을 효율적으로 다루기 위해서 등장하였다.

hash page table의 각각의 element들은 다음 세가지 field들로 구성된다.

1) the virtual page number

2) the value of the mapped page frame

3) a pointer to the next element in the linked list

알고리즘은 다음과 같이 동작한다.

virtual address에 있는 virtual page number가 hash table에 hashed 된다.

virtual page number가 linked list의 첫 element의 virtual page number와 비교된다.

match가 존재하면 일치하는 page frame이 사용되어 physical address를 만들어낸다.

match가 없으면 linked list의 이어지는 entry들을 가지고 virtual page number와의 matching을 조사한다.

한편 clustered page tables 라는 것도 있는데, hashed page tables와 비슷하지만 hash table의 각각의 entry들이 

single page라기 보다는 다수의 page들을 가리킨 다는 점이 다르다. 그러므로 하나의 page-table entry가 

다수의 physical-page frame들에 대한 mapping들을 저장할 수 있다.

8.5.3 Inverted Page Tables

왜 이 개념이 나왔는가?

앞에서와 같이 각각의 page table들의 사이즈가 매우 클 수 있기 때문에 사용한다.

inverted page table은 memory내의 각각의 frame들에 대해 하나의 entry만을 가지고 있다. 

각각의 entry들은 page number 뿐만 아니라 그 page를 소유하는 프로세스에 대한 정보도 함께 가지고 있다.

그래서 오직 하나의 page table만이 시스템에 있으며 page table은 physical memory의 각각의 page에 대해 오직 하

나의 entry만을 가진다. Fig 8.17은 inverted page table의 연산을 보여준다. 이 그림과 표준적인 page table을 보여주

는 Fig 8.7을 비교 해보아라. IBM RT에서 쓰이는 inverted page table의 경우 시스템 내의 각각의 virtual address는

다음 세가지로 이루어져 있다.

1) process-id

2) page-number

3) offset

각각의 inverted page-table entry들은 process-id와 page-number를 가지고 있는데 process-id가 address-space

identifier의

역할을 하게된다. 메모리 참조가 일어나게 될때, inverted page table은 match를 위해 검색된다.

단점 : 

1) page 참조가 발생할 때 table을 검색하는데 필요한 시간의 양을 증가시킨다.

2) shared memory를 구현하기 어렵다. 

shared memory는 일반적으로 하나의 physical address로 mapping되는 여러개의 virtual address들의 형태로 구현

된다. (virtual address 하나당 한 프로세스)

이러한 방식은 inverted page tables과 함께 사용될 수 없는데, 왜냐하면 모든 physical page에 대해 오직 하나의

virtual page entry가 있고, 하나의 physical page는 두개 이상의 shared virtual address들을 가질 수 없기 때문이다.

8.6 Segmentation

paging을 사용했을 때 피할수 없게되는 memory management의 중요한 측면은 실제 physical memory로부터 유저의 

memory를 보는 시각에 분리가 일어난다는 것이다. 우리가 앞서 봤듯이, 유저의 시각에서 메모리는 실제 physical 

memory와 동일하지 않다. 유저의 시각은 physical memory로 mapping된다. 이러한 mapping이 logical memory와 

physical memory 사이를 차이나게 한다. Segmentation은 variable-sized partition과 유사하다.

segment들은 일반적으로 크기가 크기 때문에 빈 공간을 차지하기가 힘들다. 따라서 일반적으로 segment들을 page로 

관리한다.

8.6.1 Basic Method

유저들이 memory를 instruction들과 data들을 포함하는 linear한 바이트들의 배열로 생각할까? 대부분의 사람은 그렇

지 않다. 대신 유저들은 메모리를 variable-sized의 segment들의 집합으로 생각한다.

당신이 프로그램을 작성할 때 프로그램을 어떻게 생각하는지 생각해보아라. 너는 프로그램을 main program과

method들, 프로시져들, 혹은 함수들의 집합으로 생각할 것이다.

Segmentation은 이렇게 유저가 바라보는 메모리의 관점을 생각한 memory-management scheme이다. logical

address space는 segment들 의 집합이다. 

결론적으로 말하면 paging은 크기별로 나누는거고, segment는 기능(모듈)별로 나누는 것이다.

logical address는 다음과 같은 두개의 tuple로 이루어져 있다.

1) segment-number

2) offset

이 방법과 반대로 paging 방식에서는 유저가 오직 하나의 address만을 명시했는데, 하나의 address가 하드웨어에 의

해 page number 와 offset으로 나누어졌었다.

일반적으로 유저 프로그램이 컴파일되면 컴파일러는 자동적으로 segment들을 구축한다.

컴파일 타임때 링크되는 라이브러리들은 독립된 segment들로 할당된다.

8.6.2 Hardware

유저가 이제 프로그램 내의 object들에 대해 two-dimensional address로 접근할 수 있음에도 불구하고, 실제

physical memory는 여전히 one-dimensinal sequence의 바이트들이다. 그러므로 우리는 반드시 two-dimensional

user-defined address 들을 one-dimensional physical address들로 mapping하기 위한 implementation을 정의해야 

한다. 이러한 mapping은 segment table에 의해 될수있다.

segment table의 각각의 entry들은 segment base와 segment limit을 가지고 있다. segment base는 메모리 내에 

segment가 위치하는 starting physical address를 가지고 있으며 segment limit은 segment의 길이를 명시한다.

segment table의 사용은 Fig 8.19에 나와있다.

segment number는 segment table의 인덱스로 사용된다. offset d는 반드시 0과 segment limit의 사이여야 한다. 그렇

지 않으면 운영체제에게 trap 하게 된다.(logical addressing 접근이 segment의 끝을 초과하므로)

offset이 합법적이면 offset이 segment의 base에 더해져서 physical memory 내의 desired byte의 address를 만들어

낸다. segment table은 그러므로 필수적으로 base-limit 레지스터 pair들의 배열이 된다.

예제는 344p 참조

8.7 Example : The Intel Pentium

생략

TLB (Translation Lookaside Buffer)
    
모든 virtual memory reference는 2개의 physical memory access가 필요함.
    
        1. appropriate page table entry
        2. the desired data
        
straightforward virtual memory scheme이 memory access time을 2배로 만든다.
    
이 문제를 극복하기 위해서, 대부분의 virtual memory scheme은 TLB라고 불리는 page table entry들을 위한 특별한 고속의 cache를 사용한다. 이 cache는 memory cache와 동일한 기능을 수행한다. 가장 최근에 사용되었던 page table entry들을 저장한다.

                                                                     <TLB 구조>



동작 방식
    
만약 desired page table entry가 TLB 상에 존재한다면, (TBL hit 면) frame number가 검색되고, read address가 형성된다. desired page table entry가 없다면, processor는 process page table을 indexing하는 page number를 사용하고 이에 대응하는 page table entry를 검사한다. present bit가 set되면, page는 main memory 내에 있는 것이고, 그렇다면, processor는 frame number를 page table entry로부터 검색해서 real address를 구성할 수 있다.
    
processor는 새로운 page table entry를 포함 시키기 위해서 TLB를 update한다. present bit가 not set이면, 원하는 page가 main memory 내에 없다는 것이고, memory access는 fault를 만든다. 이것이 page fault이다. 
    --> page fault 발생
   
이 경우, hardware의 영역을 떠나고, OS를 호출하여 필요한 page를 load하고 page table을 update한다. page fault interrupt는 page fault handling routine을 호출하게 된다. locality에 의해서 대부분의 reference는 page table 내에 존재한다.

끝에 수동으로 NULL을 입력해줘야한다!!

1. making & using the file system

- creating

pintos-mkdisk filesys.dsk --filesys-size=2

: 현재 폴더에다가 filesys.dsk 라는 이름으로 simulated diks를 만든다

- formating

pintos -f -q

: 현재 폴더에 있는 filesys.dsk 를 포맷한다

 userprog 폴더에서 실행해야 제대로 작동한다 씨발 좆같은

- copying 'user program file' into the pintos file system

pintos -p ../../examples/ehco -a echo -- -q

: exmaples폴더의 echo를 filesys.dsk에 복사한다. -a 옵션을 줘서 'echo' 라고 이름을 지정할 수 있다

- running

pintos -q run 'echo x'

:filesys.dsk에 복사한 echo를 실행한다

2. gdb

pintos --gdb -- run alarm-multiple 

을 먼저 실행 한후, 다른 터미널 창을 띄워서

pintos-gdb kernel.o

를 실행한다. kernel.o 를 디버깅할거니까, kernel.o 가 존재하는 threads/build 에서 실행해야 한다

target remote localhost:15031

gdb를 실행한후 위 커맨드를 실행한다. 두개의 터미널로 띄웠으니 remote localhost를 target으로 지정해줘서 access 해야한다

진짜 토나올거같다 진짜 속이 안좋다 담배피다가 토할뻔 지금은 새벽다섯시

3. user program

user program을 사용하기 위해서, user는 system call 을 사용한다

user가 system call을 하면, system call interface에서 interrupt를 발생시킨다

이 system call interface의 수행을 하는것이 init.c 에 있는 syscall_init() 인것 같다.

그리고 syscall_init() 이 호출되면 자동으로 syscall_handler()가 호출되는데

syscall_handler가 호출되는 과정이 system call table 에 access 한 것 같다

그럼 이제 해야할 일은 system call table에서 system call에 대한 번호를 할당 한 후에,

할당된 번호에 해당하는 handler를 작성하는 것 같다

남은 건 내일해야겟다 이 시발롬아

4. syscall.c 에 보면 

이래 되어있다

syscall_init에서는 여러 parameter를 패싱하면서 intr_register_int 를 호출하는데

6. process_execute() 안에서

thread를 생성해주고 - thread_create() 

프로세스를 실행한다 - start_process() 

start_process()에서는 내가 실행시킨 user program을 로드시켜주는데  - load()

load()안에 parse_filename()과 construct_ESP(esp)가 필요하다

각각 커맨드를 파싱해주고 파싱한 내용으로 스택을 구성한다

simulated disk에 'echo'라는 실행파일이 있었지만 나는 'echo x' 를 실행시켰고

이는 load가 아직 파싱을 하지 못했기때문에 filesys에서 일치하는 실행파일을 못찾았기 때문이다

exit보다 먼저 할일은 argument_parsing 이다

서서히 윤곽이 잡히는것 같기도 하고 아닌것같기도 하고 시방

7. 스택 or 페이지 접근?

우아앙아아앙 우여곡절 끝에 argument parsing하고 stack에 쳐넣은것 같다

parsing은 strtok_s로 그냥 똑같이 하면되고

stack은 그냥 스택포인터를 이용해서 접근하니까 된것 같다

스택포인터를 하나 내린후에, 그곳에 값 저장하고, 또 내리고 저장하고 반복

잘 찾아보니

thread structure의 member중에 stack pointer와 page directory 가 있다

thread랑 process랑 같은걸로 생각하라 했으니 아마 thread structure가 PCB와 같은 역할을 하는것 같다

system call handler에서 current_thread()를 이용해 저 stack pointer로 스택에 접근해서

passing해줬던 argument들을 받아와서 system call에게 인자로 넘겨주면 되지않을까?

페이지 디렉토리는 뭔지 아직 잘모르겠다

thread의 esp로 하니까 안되네

intr_frame에도 여러 멤버있는데 거기도 esp가 있긴하다 이걸로해봐야겠다

8. thread

thread.c 파일을 잘 읽어봐야겠다

thread에 대한 함수들의 설명이 잘나와있다

9.

Q2. exit 뿐만 아니라 모든 시스템콜들이 lib/user/syscall.c 안에 이미 있죠?

유저 프로그램 (echo 같은 것) 에서 exit()를 호출하면 일단 lib/user/syscall.c 안의 exit가 호출됩니다. 그러면 exit 함수 안에서 syscall1(SYS_EXIT, status) 라는 매크로를 사용하는데, (syscall1 매크로는 같은 파일 위쪽에 보면 있습니다) syscall1 매크로가 0x30 인터럽트를 발생시키면 인터럽트 벡터 테이블을 참조하여 시스템콜 핸들러를 호출하게 되는데, 이 시스템콜 핸들러에서, 해당하는 시스템콜, 그러니깐 우리가 구현해야하는 exit 함수를 호출하게 되는 것입니다. 

정리하면 lib/user/syscall.c 안의 exit는 유저 프로그램에서 exit를 호출했을 때, 우리가 구현해야하는 exit()를 호출해주기 위한 인터페이스(?) 같은 것이라 보면 됩니다.

10. 해야되는거

- process_wait 에서 어떻게 exit의 리턴값을 받음???? 어떻게 종료시킴????

- tid 가지고 thread의 status 가져오기

  (child list 만들어야되나)

- excetion 대체 어떻게 돌아가는거야

11. 에이 시발

돌아가는꼬라지를 보니

process.c 의 process_execute()에서

tid = thread_create (file_name, PRI_DEFAULT, start_process, fn_copy);

이 부분 호출하기전까지는 file_name 이 파싱되지않은 raw command 이다

start process 가 호출인자라서, start process 안에서 load부르고 parsing하고

그러고나서 parsing된 file_name이 들어갈줄 알았는데 그게 아닌것 같다

parising된 file_name을 인자로 전달할 수 있도록 해야겠다

그리고

run_task에서 

process_wait (process_execute (task));

12. sys_call.c 안에, user_exit()에서 구현할 내용

1. child를 죽일떄는 부모 안에서, 부모의 child list를 통해서 접근해야함

 실행된 child process가 비정상인 bad pointer가 들어 올 수도 있기도 하고

 지금 실행되는 child process가 자기 안에서 자기 자신을 죽이면 안되고

 부모의 process로 들어가서 child를 죽여야함

2. 부모가 있는지 확인 해야함

3. child넘어올때 parent block 해야됨

4. 지금 돌아가고있는 애를 block 걸면 무한 루프 돌수도

5. 이제 child를 exit할때는 부모를 unblock하고 

6. kernel에 있는 syscall에서 syscall number와 status를 push해주므로

esp, esp+4 로 접근해주면 된다

int status = (int*)esp 이렇게인가?

13. process_wait 안에서 구현할거

예를 들어, thread가 생성될때 wait_status라는 member를 추가하고

thread가 종료될때 그 값을 변경하도록 한다

그리고 while문을 돌리다가 그 값이 변경됨을 확인하면 그때 break하도록 한다

마지막으로 값을 리턴하게 되는데

이 리턴값이 음수 인지 아닌지만 구별하면된다

-1이 리턴되면 커널이 알아서 error인지 인식하고 알아서 오류띄우든가 할거고

아니면 그냥 정상처리된걸로 생각한다

14. user program의 큰? 그림

 OS kernel <-> kernel-function  <내가 연결> your_function <-sys_handler-> user_prog : some function call;

어떤 user program이 호출되었고

그 프로그램안에서 printf등등 system call을 필요로 한다하면

system call handler를 호출하게 된다

내가 할일을 바로 이 handler안에서 kernel function 호출해주는것

15. process wait operation

1. process wait에서 parent는 child가 죽을때까지 기다린다

2. parent가 child를 기다리때, parent는 자신의 실행을 중단시킨다. 언제까지? child가 자신의 execution을 끝내고     exit status를 리턴할 때까지

3. parent는 자신의 execution을 중단시키는데 child의 pcb중 wait semaphore를 재워서 중단시킨다

(왜 자기가 아니라 child의 wait semaphore를 중단시키지???)

4. child는 자신의 execution이 끝나면 parent를 깨우고, 자신의 zombie semaphore를 block시킨다

5. parent는 child의 exit status를 받아오고  child를 unblock시키고, child는 자기자신을 완전히 죽인다. 그리고     parent의 child list에서 제거시킨다

16. process termination

1. 프로세스에 의해 실행중인 executable을 닫는다. 그러면 executable 에 대해 write가 re-enable됨

2. 모든 open file들을 닫는다

3. 현재 process에게 잡혀진 모든 lock을 release한다

4. process의 살아있는 childe들의 zombie semaphore를 up 시킨다

5. base page directory를 activate시키고 process의 page directory를 죽여버린다

6. waiting parent에게 신호를 보낸다

7. process의 zombie semaphore를 down시킨다

17. synchronization

1. wait operation

- wait semaphore를 down 시킴

- zombie semaphore를 up 시킴

2. exit operation

- wait semaphore를 up 시킴

- zombie semaphore를 down 시킴