생성자 기반 주입이 아닌 속성 기반 주입에 대해 알아볼 것이다. 그 전에 알아두어야 하는 것은 만일 클래스가 또다른 클래스를 상속하지 않는다면 웬만해선 생성자 기반 주입을 사용하도록 공식문서에서는 권장하고 있다.

언제 property-based 주입을 사용하면 좋은가?

최상위 클래스가 하나 혹은 여러개의 provider에 의존하는 경우 원래라면 이를 상속하는 모든 하위 클래스들의 내부 생성자에서 super()를 호출하여 provider를 전부 전달해야 한다.

이러한 귀찮은 작업을 하지 않기 위해 속성 수준(멤버 변수 필드)에서 @Inject() 데코레이터를 사용할 수 있다.

import { Injectable, Inject } from '@nestjs/common';

@Injectable()
export class HttpService<T> {
  @Inject('HTTP_OPTIONS')
  private readonly httpClient: T;
}

출처

내가 정글에 오면서 세웠던 단 하나의 목표가 끝까지 수료하기였는데 모든 과정을 포기하지 않고 잘 수료했기에 굉장히 만족하고 나에게 칭찬한다. 솔직히 과정 자체가 굉장히 컴팩트하게 많은 것들을 배워야하고 스케줄도 살인적이여서 빨래할 시간도 부족하다.

참여하신 다른 분들도 힘들어했는데 특히 20대를 캐나다에서 보낸 나는 초반에 더욱 적응하기 힘든 환경이었던 것 같다.

야자를 한 적이 없던 나는 이러한 단체 생활도 처음이고, 여중 여고였기에 남자 무리도 처음이었고, 항상 내가 막내였다가 나보다 어린 여자 무리가 처음인것 등 모든게 적응이 너무 안되서, 첫 2개월 정도는 잠을 제대로 잔 적이 없었고 먹는 것도 잘 못해서 살이 10kg이 넘게 빠졌었다.

잠을 잘 못자니까 ADHD 증상이 너무 심해져서 일상생활이 어려울 정도였다. 그러니 당연히 정글의 커리큘럼을 따라가기에 굉장히 벅찼다. 한번은 한 문장을 읽는데에 한 시간이 넘게 걸렸었다.

성격도 많이 변했었다. 원래 굉장히 활발한 성격이라 많은 사람들과 이야기하고 친하게 지내는데, 굉장히 내성적으로 변해서 그렇게 싫어하던 혼밥을 하게 되면 내심 기쁠 정도였다.

원래 공부던 운동이던 뭐든 한 집단에서 열심히 하면 항상 상위권에 있던 나였기 때문에 무언가를 잘 못하는 나 자신을 정면으로 바라보면서 이 상황을 피하고 싶었다. 나의 100% 120%를 끌어내서 잘하고 싶고, 나도 남들을 도와주고 싶은데 나는 평소의 성능의 50%도 나오지 않았다. 내가 나를 받아들이는 것도 힘들고 남들이 나를 이런식을 인식하는 것도 정신적으로 견디기 힘들었다.

이 지경에 이르니 심각하게 건강을 생각해서 진지하게 퇴소를 고려했었는데, 버티고 싶었다. 내 생에 다시는 오지 않을 기회라 여겼고 나는 간절했다.

그래서 근처 병원에 가서 약 복용을 시작했고 나에게 맞는 약을 찾기까지 시간이 오래 걸리고 부작용에 힘들었지만 열심히 약을 먹고 열심히 적응해나가면서 극복하게 되었다.

사실 나에게는 이런 내부적인 어려움들이 있었기 때문에 정글의 미친 커리큘럼이나 나만무를 하면서 겪었던 체력적 어려움과 야근들은 상대적으로 그렇게까지 힘들다고 느껴지지 않았다.

오히려 어느정도 적응하고 나니 정글에서 동료들과 공부하고 일하는게 즐거웠다.

그렇게 나는 견뎌내어 결국엔 팀프로젝트까지 성공적으로 마칠 수 있었다.

우리 팀은 맛스페이스 라는 맛집 추천 웹서비스를 만들었다. 친구들 혹은 동료들끼리 함께 갈 식당을 정할 때 서로 원하는 취향과 먹고 싶은 음식을 맞추기 위해 시간을 많이 사용한다. 그래서 우리는 각자 취향의 교집합 혹은 중간 지점을 구해주면 어떨까 하는 발상에서 시작되었다.

기능을 한 줄로 요약하면 개인의 취향에 맞는 식당을 추천해주고, 식당과 식당의 중간 지점에 있는 식당들을 추천해준다. 자세한건 아래 노션페이지에서 확인할 수 있다.

[github link] (https://github.com/Moojuck-KJ3/backend-python) 팀 소개 노션 페이지

내가 어떤 것들을 했는지

추천 파이프라인 설계 및 알고리즘 구현

• selenium과 konlpy를 활용하여 데이터 수집 및 가공
• word2vec을 파인튜닝하여 상용모델 Fasttext사용 대비 유사성 3.6배 가량 향상시킴
• KNN알고리즘 사용하여 벡터 간 인접한 벡터를 구하여 서로 다른 식당 사이에 존재하는 식당 구하는 기능 개발

  백엔드 API 개발(FastAPI-RESTful)]

• Python으로 백엔드 주요 기능 개발(연관 단어 맵핑 기능, 개인 식당 추천 기능, 교집합 식당 추천 기능)
• FastAPI로 RESTful API 개발
• python 백엔드 서버 Docker로 배포

추천 파이프라인 설계 및 알고리즘 구현(python)

처음엔 단순하게 식당들이 가지고 있는 키워드 태그들을 가지고 각 식당을 벡터화 시켜서 식당 데이터셋을 꾸리고 A식당과 B식당 각각 특정 거리에 있는 이웃 식당들을 구하고 겹치는 교집합 이웃 식당들을 반환해주면 되겠다 라고 생각했는데, 실제로 해보니 겹치는게 존재하지 않는 경우가 많았다.

그래서 A벡터와 B벡터의 거리를 계산하고 그 중간 지점에서부터 이웃 식당들을 구하는 방식으로 변경했다. 거리를 계산하는데는 유클리드 알고리즘을 사용하였고 중간 지점에서부터 인접한 벡터들을 구할 때는 KNN알고리즘을 사용하였다.

벡터 데이터셋에서 특정 벡터로부터 인접한 벡터들을 구할 때 코사인유사도를 사용하지 않고 KNN을 사용한 이유는 코사인 유사도 알고리즘이 데이터셋이 비교적 작고 차원이 높은 경우에 특히 유용하다고 알려져 있지만 코사인 유사도 알고리즘은 유사도 임계값을 설정하여 인접한 벡터를 결정하기 때문에 특정 백터 주변에 인접한 백터가 없는 경우에는 해당 알고리즘으로 인접한 백터를 구할 수 없기 때문에 아무리 멀어도 그나마 가까이 인접해 있는 백터를 알아낼 수 있는 KNN알고리즘을 사용하였다.

서비스는 총 4명의 사용자가 각자 선택한 식당을 넣으면 조합된 식당을 확인할 수 있는 기능이 있는데 이 때에도 알고리즘을 비슷하게 위의 방식과 비슷하게 짰다. A, B, C, D 의 식당이 있을 때 A와 B의 식당의 중간값과 C와 D식당의 중간값, 그리고 이들의 중간 값을 4명의 중간값, 센터값이라고 했을 때, 센터와 A의 중간값, 센터와 B의 중간값, 이런식으로 식당을 추천하였다.

그런데 아쉬운 점은 결국 내가 추천하는 식당은 백터 A와 B 사이의 중간 지점에 있는 백터 즉, A와 B로부터 가장 먼 백터였다. 그러니까, A와 B가 멀다면 이들의 중간 지점이 엉뚱하게 보일 수 있다는 것이다.

그래서 완전 중간에 인접해 있는 백터들이 아니라 어느정도 떨어져 있는 백터들을 추천해 주었어야 했으면 더 합리적으로 보일 수 있었을 것 같다. (그랬더라면 시연때 최소한 4명의 중간 식당으로 디저트 가게가 나오는 참사는 막을 수 있었을 것 같기도...ㅠㅠ)

지금 코드 구현된 방식은 가장 가까이 인접한 벡터를 우선적으로 보여주는데 위와 같이 보여주고 싶으면 5번인덱스부터 7번인덱스 사이에 골라서 보여주는 방식으로 간단하게 바꿔볼 수도 있을 것 같다.

생각치도 못했는데 해보지 못해 아쉬운 점이 또 있는데 이미 잘 알려진 성능평가방법을 활용하여 알고리즘의 성능을 평가해보지 못한 것이다. 추후에 알고리즘을 개선한다면 순위 기반의 Precision, Recall, MAP, NDCG의 지표를 활용하여 알고리즘의 성능이 개선되는 정도를 확인하며 개발할 수 있을 것 같다.

자체 언어 모델 구현

단어를 백터라이징 하기 위해서는 언어모델이 필요한데 처음에 모르는 단어에 대한 대응이 word2vec 보다 뛰어나고 노이즈가 많은 코퍼스에서 강점을 가지는 fasttext를 선택하여 사용하였다. 그런데 실제로 돌려보니 유사성이 생각보다 좋지 않아서 사용하기 어려운 정도였다. 유사성은 숫자가 낮을 수록 유사한 것이라고 보는데, 유사하다고 생각하는 식당들이 덜 유사하다고 생각되는 식당들보다 유사성이 떨어지는 결과가 나온 것이다. (유사성은 유클리드거리의 거리로 판단했다.)

예를들어, 아래의 두 식당의 경우 사용한 분위기 태그가 비슷하니까 숫자가 낮을 것으로 예상한다.

나폴리회관 강남역점,"['깔끔한', '시끌벅적한'] 청담이상 강남역점,"['예쁜', '시끌벅적한'] 유클리드 거리: 1.205982344248324

그런데 유사성이 떨어져보이는 아래의 두 식당이 위의 식당보다 숫자가 더 높아야하는데 오히려 더 낮게 나오는 현상을 확인할 수 있었다.

나폴리회관 강남역점,"['깔끔한', '시끌벅적한'] 대진도원참치 강남역점 ['조용한', '고급스러운'] 유클리드 거리: 0.6086120995497456

그래서 이대로 이 모델을 사용할 수 없는 상황이었고, 다른 모델을 사용해볼까 하다가 수집해놓은 리뷰데이터들을 가지고 모델을 학습시키면 어떨까 하고 바로 실험해 보았는데 fasttext보다 기대한대로 유사성이 높게 잘 나오는 것을 확인할 수 있었다.

나폴리회관 강남역점,"['깔끔한', '시끌벅적한'] 청담이상 강남역점,"['예쁜', '시끌벅적한'] 유클리드 거리: 5.451761920716737

나폴리회관 강남역점,"['깔끔한', '시끌벅적한'] 대진도원참치 강남역점 ['조용한', '고급스러운'] 유클리드 거리: 7.012567671092597

문장을 단어단위로 tockenize/연관단어 추출

사용자가 원하는 음식점의 카테고리나, 식당의 분위기에 대한 정보를 입력받을 때 음성인식으로 받기로 해서 파이썬 서버에서 문장을 단어 단위로 토크나이즈하고 연관 단어를 추출하여 사용자에게 보여주는 것을 구현하였다. 토크나이즈는 코앤엘파이를, 연관 단어는 word2vec의 similarity 함수를 사용하여 우리가 정의한 키워드 중에 유사성이 높은 단어들을 보여주는 형식으로 구현하였다.

데이터 수집/가공

오픈API로 가져올 수 있는 데이터는 한계가 있었고 공공데이터도 생각보다 우리가 필요로하는 데이터의 한계가 있었다. 그래서 어쩔 수 없이 불법적이지만 크롤링도 실력이지 않나..하는 합리화를 되새기면서 크롤링을 시작하였다.

나는 사실 이번에 처음 데이터 크롤링을 시도해보았는데 생각보다 까다로운 작업이었다. 셀레니움으로 시도하였는데 잘 되는듯 하다가도 난관에 부딛히기 일쑤였다. 시간이 꽤 오래리고 있었는데 다른 백엔드 동료는 API

추천 관련 백엔드 API 명세/개발 (FastAPI)

Django, Flask, FastAPI 중에 FastAPI를 선택한 이유는 첫번째, 가볍고 (장고 탈락~) 두번째, 사용자수가 증가하고 있기 때문에 FastAPI를 선택하였다. fastAPI는 실제로 사용해보니 정말로 빠르고 가벼워서 만족도가 굉장히 높았다. 그리고 프로젝트 규모가 굉장히 작다보니 사용하기 아주 적절하지 않았나 싶다.

가장 힘들었던 트러블

단연 환경설정 😵‍💫

이번에 파이썬 환경설정 때문에 정말 많은 나의 머리카락이 뽑혔다. 정확하게 얘기하자면 로컬에서 잘 작동하는데 우분투 서버에서 빌드가 되지 않는 현상이 문제였다.

파이썬 버전이나 다른 패키지들의 버전이 안맞는게 있어서 그런가 싶어서 문서를 찾아보고 버전을 업그레드 해보았다가, 다운그레이드도 해보았다가, 그래도 안되서 지웠다가(파이썬을 지우는 작업도 간단한 작업이 아니다.) 다시 깔아도 보고 했지만 그래도 여전히 되지는 않았다...

이 작업을 하필이면 설에 하느라 동료가 본가에 가있느라 혼자 끙끙싸맸다. 너무 안풀려서 이제 도커라이징이 잘못되었나 싶어서 주변 사람들에게도 다 물어보고 그렇게 2-3일을 씨름하다가 어떤 외국 인터넷 사이트에서 어떤 사람이 파이썬 패키지를 시스템에 깔면 안된다? 이런 말을 보고 아 설마 내 시스템 환경에 잘못 깔려있나 싶어서 내 맥에 usr안에 들어가서 파이썬 .bash_profile 이랑 .bashrc 를 뒤져보는데 환경변수에 이상한 것들이 많이 연결되어있었다.

아하 이거구나 싶어서 어떤게 문제인가 환경변수를 하나씩 지워보면서 확인하고 있는데 어떤걸 지우니까 아얘 내 맥에 깔려있는 모든 프로그램들을 사용할 수가 없게 되었다. 심지어는 vi도 되지 않아서 파일을 수정하지도 못하는 지경에 이르렀다. 또 끙끙 싸매다가 결국 고쳐냈다.

그렇지만 여전히 원인을 알 수가 없어서 동료의 로컬에서 시도해 보았는데 잘 안되길래 freeze > requiremets.txt를 하고 필요한 패키지들이 자동으로 깔리고 난 뒤 다시 시도해보니까 그렇게 안되어던 빌드가 잘 되는것을 확인할 수 있었다.

스스로 부족했다고 느끼는 부분

체력관리

나만무 기간에 B형 독감에 걸렸었는데 건강관리도 정말 중요하다고 느꼈다. 아무리 바빠도 하루에 30정도는 운동을 하는 동료를 보면서 체력관리를 어떻게 해야하는지 배웠다. 제일 잘 알려져있는 같은 시간에 먹고 자기가 제일 중요한데 바쁘다보니 끼니를 거르거나 야근을 하느라 잠을 줄인다거나 하면서 몸의 균형이 깨지면서 면역 시스템이 무너지는 것을 경험했다.

action plan🔥

1. 아무리 바빠도 하루에 30분 걷거나 운동하기
2. 같은 시간에 자고 일어나기
   

-> 위의 두가지를 지킬 수 있는 쉬운 방법!!
매일 10시에 자고 5시에 일어나서, 일어나자마자 30분 산책하기!

시간 / 일정 관리

정글에 들어온 뒤로 나는 ADHD증상이 심해져서 약까지 복용하고 있었지만 시간관리와 일정관리가 정말 힘들었다. 스스로 현재 중요하지 않은 일을 하고 있다는 것을 알면서도 우선순위대로 일을 처리하지 못하는 나를 보면서 자괴감이 많이 들었는데 이는 흔히 ADHD 환자가 잘 못하는 것이라고 한다.

하지만 나는 사람이 자신의 약점을 잘 알고 개선시키려는 의지가 있다면 오히려 보통 사람들보다 더 나아질 수 있다고 생각하기 때문에 나의 약점을 장점으로 가져가려 한다.

action plan🔥

1. 아침 산책 후 오늘의 일정 정리하는 시간 5분 갖기(우선순위 정렬)
2. 야근 안하기 위해 업무시간에 최대한 집중하기
3. 아무리 일이 많아도 9시까지 공부/일 마무리하기 (잘 되고 있어서 아쉽다면 다음날 계속 할 수 있는 동력이 되고, 잘 안되고 있었다면 자고 일어나면 더 잘 될것이니!)
4. 하루 일과를 마무리하기 전에 다음날 해야하는 일 정하기

F들과 피드백 주고받기

나는 ENTP/INTP 이고 T와 F가 거의 6:4 정도라서 나름 F친화적인 T라 스스로를 여겨왔지만, 업무에 있어서는 나도 몰랐던 나의 T성향이 굉장히 나오는듯 했다.

예를들어, 회의때 서로의 피드백을 주고 받을 때 나는 어떤 아이디어가 별로라고 생각되면 '이건 이런이런 이유에서 별로인것 같아요. 그보다 이렇게 하면 더 좋을 것 같은데 어떻게 생각하시나요?' 라고 나의 의견을 먼저 말하는 편이다.

T들과 소통할 때는 문제가 없었는데 이번 팀원들은 나를 제외하고 모두 F 사람들이었기에 문제가 생겼다.

어떤 팀원이 나의 피드백 방식에 상처를 조금 받았다고 말해주었다. (그 당시에는 이 정도에 상처받는다고? 어이없어 했지만 사실 말해줬다는 사실에 그 팀원에게 참 감사하다)

그래서 일단 칭찬하고 나의 의견을 조심스럽게 제시하는 쪽으로 자연스럽게 나의 소통방식이 바뀌었다. 예를들어, '오! 좋은데요? 혹시 이렇게하면 더 좋을까요?' 혹은 고개를 끄덕이며 '음~ 좋네요~' 라고 듣고 난 뒤에 조심스럽게 '좋은데 다만 우려되는 부분으로 ~게 있긴 한 것 같아요' 라고 한다던가.

이렇게 바뀐 부분은 소통에서 조금 더 시간을 잡아먹어서 생산성이 이전 방식 보다는 떨어질 수 있지만 우리는 로봇이 아니고 인간과 대화하며 일을 하기 위해서는 조금 불편하더라도 서로 존중하고 조심해야 하는게 맞는 것 같다.

이번에 나와 참 다른 성격의 팀원들을 만나서 어려운 점도 많았짐나 결국 내가 이렇게나 발전할 수 있었기에 너무 감사하다.

끝으로 나만무 최종발표때 정성훈 멘토님💛과 찍은 사진을 첨부한다!

우분투에서 서버 실행시켰때 안되는 이유 찾기

이 태스크가 3일이나 걸렸다. 도대체 아무리 새로 가상환경을 만들고 깔고 파이썬을 지웠다가 깔았다가 다운그레이드 했다가 우분투를 새로 팠다가 다시 세팅해도 되질 않았다.

그러다 우연히 어떤 외국 레딧에서 시스템 전역변수에 파이썬 패키지 깔면 안된다 라는 말 보고 설마 하고 내 시스템 환경변수 들어가서 보니까 이상하게 전역변수에 파이썬 관련 패키지가 너무 많았다.

그런데 그렇다 하더라도 가상환경 위에서 개발하면 시스템 환경과는 별개로 분리되어야 하는 것 아닌가 하는 찜찜함이 있지만 무튼 테스트를 위해 환경변수 설정을 잠깐 없에고 서버를 실행시켜보니 역시나 돌아가지 않았다.

일단 합리적 의심이라 정리하고 급한대로 다른 컴퓨터에서 실행시키고 필요한 패키지들을 pip freeze > requirements.txt 로 뽑고 도커로 만뒤 우분투에서 도커로 배포해보니 정상작동하였다. 하하...

이번에는 지난번에 연습해보지 못해 아쉬웠던 깃크라켄, 깃이슈와 PR을 연동하여 브랜치를 관리하는 방법을 연습 삼아 시도해 볼 예정입니다.

깃 이슈를 생성하고 PR생성해서 이슈를 참조하고 main branch에 sub branch를 merge하고 병합된 이슈를 close하는 과정이 아래 블로그에 잘 나와있어서 참고했습니다. https://minny27.tistory.com/50

이번 과제는 벨로그에 따로 정리하지 않고 기능별로 이슈를 발행해서 이슈안에 documentation을 할 예정입니다.

오늘 환경설정 한 이슈와 그 안에 document 한 내용 https://github.com/geeks-lab/practicing_mern/issues/1

언어를 스프링과 노드중에 선택해야 하는데 한지 오래되긴 했지만 익숙한 스프링을 할까 아니면 몇번 안해본 노드를 할까 고민을 하다가, 노드를 이번에 해야겠다 생각했습니다. 이유는 다음과 같습니다.

1. 내가 회사를 다니면서 혼자 개인프로젝트를 하면 어떤 걸 쓸까 생각했을 때 아무래도 스프링보다는 노드로 빠르게 구현하는게 편할 것 같아서.
2. 이직할 때 아무래도 나는 외국이나 스타트업으로 가지 않을까 해서. 거기는 자바보다 노드를 쓰는 비율이 크지 않나해서.

그런데 말입니다... 그냥 게시판은 너무 재미가 없지 않겠습니까? 하하하 그래서 인프런을 구경하다가 너무 구미가 당기는 수업을 발견했습니다. 강의링크

강의 내용은 이미지 관리 노하우(AWS Lambda를 사용하여 파일 읽기 속도 개선해서 이미지 로딩을 빠르게)가 뾰족한 파트이고 거기에 내가 공부해야하는 Node.js, React을 사용해서 기본적인 기능들(DB연동, Authentication, pagenation, Infinite Scroll, etc) 다루기 때문에 굉장히 재밌을 것 같습니다😎

이렇게 이미지 로딩속도가 느린 경험을 누구나 한번쯤은 해봤을 것 입니다. 이커머스와 같은 특정 도메인에서는 이러한 페이지 로딩 시간이 크리티컬하기 때문에 이미지 파일을 잘 처리하고 관리하는 게 서비스 개발에 무척 중요한 요인이라고 합니다. 2주간 이 문제를 개선할 수 있는 방법을 이번에 기술적 챌린지로 가져가보면 너무 좋을 것 같습니다.

• Node.js, Express
• React, React Hooks
• MongoDB
• AWS S3, CloudFront, presignedUrl
• 이미지 리사이징 & AWS Lambda
• IntersectionObserver를 이용한 Infinite Scroll
• Session 기반 Authentication & Authorization

위의 기술을 사용해서 아래의 것들을 구현해볼 것입니다.(짱신나!)

강의를 잘 따라가면 아래와 같은 사진첩 서비스를 만들 수 있다고 하기 때문에 저기에서 약간만 변경해서 게시판 서비스를 만들면 될 것 같습니다.

week 07-09 git repo https://github.com/hnjog/pintos-kaist/tree/geeks-lab

week 10-11 git repo https://github.com/sylee6529/PintOS-VM/tree/geeks-lab

1. Oh MY 나 자신, 칭찬합니다!

   • C언어, 포인터 개념에 친숙해진 것.
   • 디버깅 툴이나 방법 자체에 익숙해진 것. (부끄럽게도 그동안 break point걸고 이동하거나 깊게 파고들면서 까지의 디버깅을 해 본적이 없던 것 같다)
   • 다른 분들의 공부 방식을 보고 내 공부 방식을 발전 시킬 수 있었던 것(혼자 공부 했더라면 불가능 했을 부분)
   • 부끄러워도 내가 겪고 있는 문제를 동료에게 오픈하고 도움을 요청하는 것이 는 것.(나와 같은 프로젝트를 하고 있는 동료는 내 문제를 이미 겪었을 가능성이 높기 때문에 더욱 그랬다)
   • PintOS과제가 워낙 악명이 높기도 하고 지난 기수 분들이 너무 힘들었다고 하시니까 두려움이 컸는데, 그리고 하면서 실제로도 힘들기도 했지만 생각했던 것 만큼 힘들지...는 않았던 것 같다. 물론 끝까지 블로그나 동료 코드를 보지 않았더라면 이렇게 말하진 못했을 것 같지만^^. 어찌됐든 개인적인 일들, 건강 이슈등이 있었음에도 불구하고 끝까지 포기하지 않고 끝낸 것!!! 제일 칭찬해.

2. 다음에 더 발전시킬 수 있는 부분들!

   • 시간, 건강 관리를 더 열심히 촘촘하게 했더라면 시간을 좀 더 활용할 수 있었을텐데 사실 이 부분이 스스로 제일 아쉽다. 같은 반의 어떤 분은 헬스장에 다니면서도 할 일을 다른 분들보다 더 많이 하시는 걸 보면서 반성을 했다. 시간이 없다는 것은 변명이다. 지난 주차들을 되돌아보면 쓸데없이 흘려 보냈던 시간들이 많았다.
     • 🔥 Action Plan : 일어나는 시간, 퇴근하는 시간, 운동하는 시간 만이라도 스스로 정하고 루틴화하기.
   • 도커로 해볼걸 시도하다가 너무 쉽게 포기함.
   • 깃 크라켄이나 깃 데스크탑으로 기능별로 브랜치를 만들어서 브랜치 관리를 연습을 해볼 수 있었는데 못한 것.
     • 추가로, 이슈를 발행해서 트러블 슈팅을 정리하고 커밋 메세지에 이슈를 달아서 document 할 걸 그랬다.(왜냐하면 블로그에 적는거는 나중에 찾아볼때 한계가 있을 것 같다. 최소한 벨로그는 불편함)
   • 동료에게 도움 많이 못드린 것
     • 이건 건강 이슈 때문에 내가 교육장에 오랜 시간 있지 못해서 그랬던 것도 있지만 그래도 좀 더 열심히 빨리 해서 도움을 드렸더라면 덜 아쉬웠을 것 같다.
   • 초반 project 1,2 에서는 큰 흐름을 먼저 파악하고 코드를 써내려간 것 같은데 특히 project3 에서는 당장 테스트 케이스만 통과하기 위해 코드를 쓰지 않았나 하는 아쉬움이 남는다. 나 스스로 그림 그려보며 추상화를 하며 큰 그림을 이해하는 작업이 꼭 필요한 것 같다.

3. 끝나고 더 공부해보고 싶은 것들

   • 권영진 교수님 OS 특강 열려있을 때 다시한번 보고 정리해보기
   • 키워드 면접 질문 대비용으로 아무것도 안보고 설명해보기
     • 스레드(싱글, 멀티), 프로세스, 스케줄링, 세마포어, 락, race condition, 데드락, 페이지, 세그멘테이션,
   • 운영체제 교재였던 Three Easy Pieces 재밌어보이는데 읽어봐야겠다.
   • csapp도 못읽었던 부분들 읽어봐야겠다.
   • C에서 헤더파일이 어떤 방식으로 읽히는지 원리 파악해보기
     • 이 날 헤더파일 때문에 고생했었다. https://velog.io/@gigis-note/1130-trouble-shootingpintos-project-1.-donations

스택그로스는 이 레퍼런스를 참고해서 구현했더니 바로 관련 테스트케이스가 통과했다.

다만 조건문중에 아주 복잡한 부분이 있어서 짚고 넘어갔다.

스택 확장으로 처리할 수 있는 폴트인 경우를 표현하기 위해 (USER_STACK - (1 << 20) <= rsp - 8 && rsp - 8 == addr && addr <= USER_STACK) 이렇게 된 모습이다.

연산자 우선순위에 의해서

1. 1 << 20: 비트 왼쪽 시프트 연산은 가장 높은 우선순위를 갖는데, 이는 1을 20만큼 왼쪽으로 비트 이동시키는 연산입니다.
2. USER_STACK - (1 << 20): 뺄셈 연산은 비트 시프트 연산보다 우선순위가 낮습니다. 따라서 USER_STACK에서 (1 << 20)을 뺀 값이 계산됩니다.
3. rsp - 8: 뺄셈 연산은 비트 시프트 연산보다 우선순위가 낮기 때문에, rsp에서 8을 뺀 값이 계산됩니다.
4. addr == rsp - 8: 비교 연산은 뺄셈보다 우선순위가 높으므로, rsp - 8과 addr이 같은지 비교합니다.
5. USER_STACK - (1 << 20) <= rsp - 8: 이전 단계에서 계산된 값과 USER_STACK - (1 << 20)을 비교합니다.
6. addr <= USER_STACK: 비교 연산은 뺄셈보다 우선순위가 높으므로, addr과 USER_STACK을 비교합니다.
7. 마지막으로 논리 AND (&&) 연산자를 사용하여 앞선 모든 비교를 연결합니다.

현재 전체 테스트케이스 결과 모습

특이 케이스 처리

아래의 특수 테스트 케이스를 해결해야 한다.

FAIL tests/vm/pt-write-code2 FAIL tests/vm/pt-grow-stk-sc

이건 동료 document 의 도움을 받아 해결했다.

현재까지 상황 27 of 141 tests failed.

page-merge-seq page-merge-par page-merge-stk

이 세개 fail 떴었다가 다시 돌리니까 두개 fail 뜬다...

왜이럴까? 일단 제쳐두고 mmap하자.

Memory Mapped Files

syscall_handelr()

mmap()

void *mmap(void *addr, size_t length, int writable, int fd, off_t offset) {
    if (!addr || addr != pg_round_down(addr)) return NULL;  // addr 없는 경우

    if (offset != pg_round_down(offset))
        return NULL;  // offset이 page aligned 되지 않은 경우

    if (!is_user_vaddr(addr) || !is_user_vaddr(addr + length))
        return NULL;  // addr이 user 영역이 아닌 경우

    if (spt_find_page(&thread_current()->spt, addr))
        return NULL;  // spt에 있는 경우

    struct file *f = process_get_file(fd);
    if (f == NULL) return NULL;  // file이 없는 경우

    if (file_length(f) == 0 || (int)length <= 0)
        return NULL;  // file의 길이가 0 혹은 음수인 경우

    return do_mmap(addr, length, writable, f,
                   offset);  // 파일이 매핑된 가상 주소 반환
}

do_mmap()

매핑을 진행할 때는 간단하게 (페이지 주소 addr + PGSIZE에 위치하는) 다음 페이지에 이어서 매핑하면 되지만, 매핑을 해제할 때는 몇 번째 페이지까지 해제해야 하는지를 알아야 한다. 따라서 총 몇 페이지를 사용해서 매핑이 이루어졌는지에 대한 정보도 page 구조체에 함께 저장해 둔다. 출처

void *do_mmap(void *addr, size_t length, int writable, struct file *file,
              off_t offset) {
    struct file *f = file_reopen(file);
    // this is for returning mapped virtual address when the mapping is suceeded
    void *start_addr = addr;
    // Total number of page for mapping
    int total_page_count = length <= PGSIZE  ? 1
                           : length % PGSIZE ? length / PGSIZE + 1
                                             : length / PGSIZE;

    size_t read_bytes = file_length(f) < length ? file_length(f) : length;
    size_t zero_bytes = PGSIZE - read_bytes % PGSIZE;

    ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
    ASSERT(pg_ofs(addr) == 0);     // page alignment for the upage
    ASSERT(offset % PGSIZE == 0);  // page alignment for the ofs

    while (read_bytes > 0 || zero_bytes > 0) {
        /* 이 페이지를 채우는 방법을 계산합니다.
        파일에서 PAGE_READ_BYTES 바이트를 읽고
        최종 PAGE_ZERO_BYTES 바이트를 0으로 채웁니다. */
        size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
        size_t page_zero_bytes = PGSIZE - page_read_bytes;

        struct lazy_load_arg *lazy_load_arg =
            (struct lazy_load_arg *)malloc(sizeof(struct lazy_load_arg));
        lazy_load_arg->file = f;
        lazy_load_arg->ofs = offset;
        lazy_load_arg->read_bytes = page_read_bytes;
        lazy_load_arg->zero_bytes = page_zero_bytes;

        // vm_alloc_page_with_initializer를 호출하여 대기 중인 객체를
        // 생성합니다.
        if (!vm_alloc_page_with_initializer(VM_FILE, addr, writable,
                                            lazy_load_segment, lazy_load_arg))
            return NULL;

        struct page *p = spt_find_page(&thread_current()->spt, start_addr);
        p->mapped_page_count = total_page_count;

        /* Advance. */
        // 읽은 바이트와 0으로 채운 바이트를 추적하고 가상 주소를 증가시킵니다.
        read_bytes -= page_read_bytes;
        zero_bytes -= page_zero_bytes;
        addr += PGSIZE;
        offset += page_read_bytes;
    }

    return start_addr;
}

Trouble shooting

mmap-read, overlap

위 테케 포함 중간중간 mmap 관련 테스트 실패

try

syscall.c 의 syscall_handler에서 SYS_MMAP에서 mmap함수 결과를 rax 레지스터에 담았다

before

after

현재상황

mmap-inherit 빼고 mmap 관련 테케 성공

여태까지 상황

Issue #1: "Timer: #ticks" message

이쯤에서 다시 원인분석

현재 상황은 테케를 돌리면 이렇게 뜨는 상황이다.

try #1

디버깅을 해봤다.

• 지금 나는 exec도 못들어가고 있는 상황.

• init.c 의 main 함수를 돌고 나서 child process인 test가 돌아가는 건데 나는 main함수도 못돌고 있다.

• 근데 죽는 지점이 매번 다르다…?🙃

• run_actions 에서 여기서 죽음

• 이번엔 fsutil_put()에서 죽음🙃

• 이번엔 lock_release()에서 죽음🙃

• 디버깅을 해봐도 죽는 지점이 계속 달라서 혼란의 연속이었다.

• 그러다 구세주 프린트신공 마찬옥님 등장.

• 그도 고군분투를 하다 갑자기 프린트문이 찍히면 안되는 곳에서 찍혀서 이러는것이 아니냐는 합리적의심 후 쓸모없는 프린트문 모두 제거.

  • 해당 오류가 사라져 버렸다…!🥹
  • 포기하지 않고 문제를 찾아버린 마찬옥님께 감사의 인사를…🙏

Issue #2: vm.c 에서 "threads/mmu.h" library 추가 안함

try

vm.c에서 #include "threads/mmu.h" 추가

cause

pml4관련 함수를 vm_do_claim_page()에서 pml4_set_page() 이렇게 버젓이 사용하고 있는데 라이브러리 선언을 위에 안했어서 함수 사용을 실질적으로 못하고 있었다.

Issue #3: anon_initializer()에서 return ture 안함

pintos -v -k -T 60 -m 20 --fs-disk=10 -p tests/userprog/args-single:args-single --swap-disk=4 -- -q -f run 'args-single onearg' 했을 때

try

여기서 return true;를 해주지 않았어서 추가했다.

cause

anon_initializer()에서 true를 반환해주지 않으면 vm_alloc_page_with_initializer()에서 uninit_new에서 false 값이 넘어가기 때문에 초기화가 제대로 이루어지지 않아서 해당 부분에서 문제가 생겼던 것이다.

Issue #4: switch (type) -> switch (VM_TYPE(type))

try

vm_alloc_page_with_initializer() 함수에서 스위치문 안이 의심스러웠다. 처음엔 switch (VM_TYPE(type)) 했다가 다른 사람 코드에 switch (type) 되어 있는걸 보고 바꿨던게 문제가 될 수도 있겠어서 원래코드로 바꿨다.

before :switch (type) after : switch (VM_TYPE(type))

역시 이 문제가 맞았었다.

cause

그냥 type과 VM_TYPE(type)이 어떻게 값이 찍히는지 프린트문으로 찍어봤다.

근데 같다..?

하지만 맨끝에 7번째에는 다르다. VM_TYPE(type)은 0x1이고 type은 0x9로 찍힌다.

마지막에 그렇게 나오는 이유는 type이 유저스택의 스택에 있는 페이지라서 type이 0x9로 찍힌 것이다. 그 이유는 우리가 setup_stack()에서 스택을 할당할 때 이렇게 하기 때문에 VM_MARKER_0을 넣어주었었기 때문이다. (VM_MARKER_0 이 1000 ->8임)

VM_TYPE()은 이렇게 define 되어있다.

0x9는 이진수로 나타내면 1001이고, 7은 이진수로 나타내면 0111 이걸 AND 연산하면 0001 이다.

따라서, VM_TYPE()으로 감싸줘야 0x1이 된다.

오늘 꽤 오랜시간 나의 에러 해결에 큰 도움을 주신 마찬옥님께 다시한번 감사의 인사를 올린다.

여기까지 했을 때 일단 fork 전까지 성공했다. 이제 copy kill 해야하고 stack growth 한 다음에 mmap하면 ...된다...하하

project2 debugging: copy,kill 구현

/* Copy supplemental page table from src to dst */
// 자식 프로세스 생성할때 spt()
bool supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED,
                                  struct supplemental_page_table *src UNUSED) {
    struct hash_iterator i;
    hash_first(&i, &src->spt_hashmap);
    while (hash_next(&i)) {
        struct page *src_page =
            hash_entry(hash_cur(&i), struct page, hash_elem);
        enum vm_type type = src_page->operations->type;
        void *upage = src_page->va;
        bool writable = src_page->writable;

        // type이 uninit이면
        if (type == VM_UNINIT) {  // uninit page 생성 & 초기화
            vm_initializer *init = src_page->uninit.init;
            void *aux = src_page->uninit.aux;
            vm_alloc_page_with_initializer(VM_ANON, upage, writable, init, aux);
            continue;
        }

        // type이 uninit이 아니면
        if (!vm_alloc_page(type, upage, writable))  // uninit page 생성 & 초기화
            return false;

        // vm_claim_page으로 요청해서 매핑 & 페이지 타입에 맞게 초기화
        if (!vm_claim_page(upage)) return false;

        // 매핑된 프레임에 내용 로딩
        struct page *dst_page = spt_find_page(dst, upage);
        memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE);
    }
    return true;
}

void hash_page_destroy(struct hash_elem *e, void *aux) {
    struct page *page = hash_entry(e, struct page, hash_elem);
    destroy(page);
    free(page);
}

/* Free the resource hold by the supplemental page table */
void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED) {
    /* TODO: Destroy all the supplemental_page_table hold by thread and
     * TODO: writeback all the modified contents to the storage. */
    hash_clear(&spt->spt_hashmap,
               hash_page_destroy);  // 해시 테이블의 모든 요소를 제거
}

issue 1

annonymous 관련 코드 짠 후 돌려보니 돌리자마자 바로 커널 패닉🫠

밑에서 세번째 줄에 filesys/fsutil.c:160 in fsutil_get(): db: open failed

왜 저기서 터지는지 모르겠다.

debugging 해보고 싶은데 launch.json에 문제가 있다면서 안돌아간다. (내일 팀원한테 어떻게 하는지 물어봐야지)

할 수 있는 걸 해보자.

콜스택을 백트레이스 해봤다.

try #1

동료가 vm_get_frame()에서 frame에 NULL을 넣어줬던거를 말록으로 바꿨더니 문제가 해결됐다고 해서 나도 해보았다.

before

after

fsutil_get()에서 터지는 문제는 넘어가고 is_thread()에서 터지는 현상이 나타났다.

issue 2

try #1

현재 내 코드에 따르면 vm_claim_page가 성공하면 user_stack과는 상관없이 무조건 true 리턴하는 형식이라 setup_stack의 success와 vm_claim_page의 success를 분리시켜야 할 것 같다고 했다.

아래와 같이 바꿔봤다.

before

after

try #2

비록 결과는 똑같이 is_thread에서 커널 패닉이 나지만.. 유의미한 코드 수정이였다.

주석친 부분이 page_fault() 에서 project 2 작업할 때 넣었던 코드인데 이게 project 3에서 문제가 될 수 있을 것 같아서 주석처리를 해보았다.

static void
page_fault (struct intr_frame *f) {
    bool not_present;  /* True: not-present page, false: writing r/o page. */
    bool write;        /* True: access was write, false: access was read. */
    bool user;         /* True: access by user, false: access by kernel. */
    void *fault_addr;  /* Fault address. */

    /* Obtain faulting address, the virtual address that was
       accessed to cause the fault.  It may point to code or to
       data.  It is not necessarily the address of the instruction
       that caused the fault (that's f->rip). */

    fault_addr = (void *) rcr2();

    /* Turn interrupts back on (they were only off so that we could
       be assured of reading CR2 before it changed). */
    intr_enable ();


    /* Determine cause. */
    not_present = (f->error_code & PF_P) == 0;
    write = (f->error_code & PF_W) != 0;
    user = (f->error_code & PF_U) != 0;

    // int PHYS_BASE = 0x80040000;
    // int VIRTUAL_BASE = 0x00000000;
    // // printf("page fault at %p\n", fault_addr);
    // /* Handle kernel-mode page faults. */
    // if (!user) {
    //     // printf("not user\n");
    //     if (is_kernel_vaddr(fault_addr)) {
    //         // printf("is kernel vaddr\n");
    //         if (fault_addr >= PHYS_BASE) {
    //             // printf("fault addr >= phys base\n");
    //             exit(-1);
    //         }
    //         else {
    //             // printf("fault addr < phys base\n");
    //         }

    //     }

    //     else {
    //         // printf("not kernel vaddr\n");
    //         exit(-1);
    //     }
    // }

    // /* Handle user-mode page faults. */
    // else {
    //     // printf("user\n");
    //     if (is_kernel_vaddr(fault_addr)) {
    //         // printf("is kernel vaddr\n");
    //         exit(-1);
    //     }
    //     else {
    //         // printf("not kernel vaddr\n");
    //         if (fault_addr <= VIRTUAL_BASE) {
    //             // printf("fault addr <= virtual base\n");
    //             exit(-1);
    //         } else {
    //             // printf("fault addr > virtual base\n");
    //         }
    //     }
    // }

#ifdef VM
    /* For project 3 and later. */
    if (vm_try_handle_fault (f, fault_addr, user, write, not_present))
        return;
#endif

    /* Count page faults. */
    page_fault_cnt++;

    /* If the fault is true fault, show info and exit. */
    printf ("Page fault at %p: %s error %s page in %s context.\n",
            fault_addr,
            not_present ? "not present" : "rights violation",
            write ? "writing" : "reading",
            user ? "user" : "kernel");
    kill (f);
}

오! 주석처리 하니 일단 is_thread()에서 터지는 문제는 넘어가서 해당 코드는 삭제해두었다.

issue 3

이제는 page_fault발생하고 나서 exception.c의 kill()에서 문제가 터진다.

Kernel PANIC at ../../userprog/exception.c:97 in kill(): Kernel bug - unexpected interrupt in kernel

try #1

• va를 매개변수로 받아서 그걸로 page find 해야하는데 여기서 넘어오는 va가 값이 page단위가 아니라 페이지 중간 값일 수 있어서 페이지 단위로 라운드 해줘야 찾을 수 있기 때문에 pg_round_down()함수로 주소를 맞춰줬다.

• page에 palloc을 해주는 이유를 모르겠어서 뺐다.

• page에 NULL을 넣어주고 시작했는데 NULL을 넣어줄 필요성을 못느껴 뺐다.

before

after

결과는 에러가 해결되지 않고 똑같은 모습이였다.

에러를 다시 보았다. exception.c의 에러가 나는 곳으로 이동하니 이러한 주석이 쓰여있다.

Kernel's code segment, which indicates a kernel bug. Kernel code shouldn't throw exceptions. (Page faults may cause kernel exceptions--but they shouldn't arrive here.) Panic the kernel to make the point. 커널 코드는 예외를 던져서는 안된다. 페이지 폴트는 커널 익셉션을 야기할 수 있다. 하지만 여기에 와서는 안된다.

try #2

하..vm_alloc_page_with_initializer()의 함수를 찬찬히 뜯어보다가 if문 괄호가 닫히기 전에 err: return false;를 하고있는 모습을 보고 띠용했다. 보는 순간 직감한다. 이것이 이 문제의 근원이라는 것을... 돌려보니 역시나 커널패닉이 드디어 해결되었다.

before

after

result

그렇지만 테스트케이스는 FAIL 이었다.

issue 4

• spt_find_page()에서 hash_find()하고 free 안해주고 있어서 free 해줬다

try #1

• spt_insert_page() 에서 insert하기 전에 넣으려 하는 가상주소가 존재하지 않는지 검사하는 코드가 없어서 추가하고 succ 를 리턴하는 형식으로 바꿨다.

원래 return hash_insert(&spt, &page->hash_elem) == NULL ? true : false; 이렇게 리턴해줬다가 위처럼 바꿨더니 다시 커널 패닉이 exception.c kill()에서 난다🫠 동료에게 물어봤더니 spt에 존재하는지 체크 예외처리를 해주지 않아도 괜찮다고 해서 다시 돌려놨다.

a few fixes #1

음 이건 해당 에러를 고치기 위해서가 아니라 코드를 보다 고쳐 놓아야 할듯 해서 고쳐놓는다.

syscall.c 의 check_address()에서 lazy loading 으로 바뀌었기 때문에 pml4에서 보이지 않더라도 정상적인 상황일 수 있기 떄문에 예외처리를 살짝 수정해 주어야 한다.

void check_address(void *addr) {
    struct thread *t = thread_current();

    /*  이전 코드
    if (!is_user_vaddr(addr) || addr == NULL || pml4_get_page(t->pml4 , addr)
    == NULL) {     exit(-1);
    }
    */

    if (!is_user_vaddr(addr) || addr == NULL) {
        exit(-1);
    }

    if (pml4_get_page(t->pml4, addr) == NULL) {
        // pml4에 없고, spt에 있으면 정상적인 lazy loading 상황 -> 에러 아님!
        if (!spt_find_page(&t->spt, addr)) {
            exit(-1);
        }
    }
}

a few fixes #2

spt_insert_page(spt, p); 이렇게 해주고 있었다. hashmap에 넣어줘야 하는게 맞기에 find하는 함수들과 insert하는 함수들의 spt를 &spt->spt_hashmap 으로 수정.

이쯤에서 다시 원인분석

현재 상황은 테케를 돌리면 이렇게 뜨고,

• 지금 나는 exec도 못들어가고 있는 상황.

• init.c 의 main 함수를 돌고 나서 child process인 test가 돌아가는 건데 나는 main함수도 못돌고 있다.

• run_actions 에서 죽음.

• 여기서 죽음

롸?

memory management missing part

<vm.c?>
/* Return true on success */
bool vm_try_handle_fault(struct intr_frame *f UNUSED, void *addr UNUSED,
                         bool user UNUSED, bool write UNUSED,
                         bool not_present UNUSED) {
    struct supplemental_page_table *spt UNUSED = &thread_current()->spt;
    if (spt == NULL) return false;

    return vm_claim_page(addr);
}

이렇게 vm_claim_page(addr); 하면 해당 함수에서 spt에서 va에 해당하는 page 찾아서 return vm_do_claim_page(page); 이렇게 vm_do_claim_page함수를 호출한다.

Anonymous page

Anonymous page 구현 들어가기 전에 page 초기화 흐름을 살펴보자

출처: 링크텍스트

anonymous page 시작해보자.

team todo list on Anonymous Page

• 목표: Page Type에 따라 알맞게 처리하고, lazy loading을 구현한다.
• 구현
  • page type에 따른 initializer 호출
  • struct anon_page에 필요한 멤버 추가 가능
  • 처음은 무조건 uninit 페이지로 생성, 페이지 구조만 할당
  • lazy loading을 위해 load_segment while문 로직, setup_stack 로직 수정
  • Page Fault Handler에서 Valid한 Fault인지 체크 [여기까지 하면 fork 제외 Project2 테케 모두 통과]
  • fork를 고려한 SPT copy, kill 함수 구현
  • uninit_destroy, anon_destroy 구현 [ 여기까지 하면 Project2 테케 모두 통과 ]

1) vm_alloc_page_with_initializer

bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
        vm_initializer *init, void *aux) {

    ASSERT (VM_TYPE(type) != VM_UNINIT)

    struct supplemental_page_table *spt = &thread_current ()->spt;

    /* Check wheter the upage is already occupied or not. */
    if (spt_find_page (spt, upage) == NULL) {
        struct page *p = (struct page *)malloc(sizeof(struct page));
        bool (*page_initializer)(struct page *, enum vm_type, void *);
        switch (VM_TYPE(type))
        {
        case VM_ANON:
            page_initializer = anon_initializer;
            break;
        case VM_FILE:
            page_initializer = file_backed_initializer;
            break;
    }
    uninit_new(p, upage, init, type, aux, page_initializer);
    p->writable=writable; // 순서 중요. 필드 수정을 uninit_new 이후에 해야함.
    return spt_insert_page(spt, p);
err:
    return false;
}

2) load_segment

When is this function called?

inside of the load function(fuc loads the executable file to the current thread) when the process is executed.

what does this function do?

• loads the file's content to the upage.
• Be awere that this function shouldn't load a file's content directly, but hand over the ingredients for the actual loading such as function and arguments to "lazy_load_segment()"

struct lazy_load_arg

Need a structure that includes the information for the loading to write load_segment.

"include/vm/file.h"
struct lazy_load_arg {
    struct file* file;
    uint32_t read_bytes;
    uint32_t zero_bytes;
    off_t ofs;
    void *open_addr;
    void *close_addr;
};

"userprog/process.c"
static bool load_segment(struct file *file, off_t ofs, uint8_t *upage,
                         uint32_t read_bytes, uint32_t zero_bytes,
                         bool writable) {
    ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
    ASSERT(pg_ofs(upage) == 0);
    ASSERT(ofs % PGSIZE == 0);

    while (read_bytes > 0 || zero_bytes > 0) {
        /* Do calculate how to fill this page.
         * We will read PAGE_READ_BYTES bytes from FILE
         * and zero the final PAGE_ZERO_BYTES bytes. */
        size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
        size_t page_zero_bytes = PGSIZE - page_read_bytes;

        struct lazy_load_arg *lazy_load_arg =
            (struct lazy_load_arg *)malloc(sizeof(struct lazy_load_arg));
        lazy_load_arg->file = file;
        lazy_load_arg->ofs = ofs;                      // location will start to read
        lazy_load_arg->read_bytes = page_read_bytes; // bytes the page need to read
        lazy_load_arg->zero_bytes = page_zero_bytes; // bytes need to be filled with 0
        void *aux = NULL;
        if (!vm_alloc_page_with_initializer(VM_ANON, upage, writable,
                                            lazy_load_segment, aux))
            return false;

        /* Advance. update for the repeat */
        read_bytes -= page_read_bytes;
        zero_bytes -= page_zero_bytes;
        upage += PGSIZE;
        ofs += page_read_bytes;
    }
    return true;
}

3) lazy_load_segment

When is this function called?

When the first page fault is called

what does this function do?

• This function is responsible for loading, practically.
• As the physical frame mapping is done before this function is called, just need to do loading the content to the physical frame.
• The Argument aux is the info that is set on the lazy_load_arg, which is the information that needs to find the file

static bool lazy_load_segment(struct page *page, void *aux) {
    void *kva_ = page->frame->kva;

    struct lazy_load_arg *lla = (struct lazy_load_arg *)aux;
    // set ofs as file's position
    file_seek(lla->file, lla->ofs);
    // reading(loading) the content to the physical frame
    if (file_read(lla->file, kva_, lla->read_bytes) != (int)(lla->read_bytes)) {
        palloc_free_page(kva_);
        return false;
    }
    memset(kva_ + lla->read_bytes, 0, lla->zero_bytes);
    return true;
}

4) setup_stack

When is this function called?

Inside of load function when the process is running

what does this function do?

Creates a page of stack at the point downwards as PGSIZE from USER_STACK where the stack's start point.

Note that the lazy loading is not necessary for the first stack page. Becuase when the process is executed, this address is accessed right away after this function is called in order to add commmand line args to the stack.

Therefore, we don't have to wait for the fault, but get a physical frame right away.

When a page is allocated, suppliment marker can be used to indicate the page is stack page by using VM_MARKER_0 with the type.

Lastly, change the rsp to USER_STACK so that the argument_stack function can push the args from the rsp.

"userprog/process.c"
static bool setup_stack(struct intr_frame *if_) {
    bool success = false;
    void *stack_bottom = (void *)(((uint8_t *)USER_STACK) - PGSIZE);

    /* TODO: Map the stack on stack_bottom and claim the page immediately.
     * TODO: If success, set the rsp accordingly.
     * TODO: You should mark the page is stack. */
    /* TODO: Your code goes here */
    if(vm_alloc_page(VM_ANON|VM_MARKER_0, stack_bottom, 1)) {
        // map the physical frame to the allocated page.
        success = vm_claim_page(stack_bottom);
        if (success) {
            if_->rsp = USER_STACK;
        }
    }
    return success;
}

5) vm_try_handle_fault

When is this function called?

what does this function do?

when the page fault is occured, this function gets the control.

이 함수에서 할당된 물리 프레임이 존재하지 않아서 발생한 예외일 경우에는 매개변수인 not_present에 true를 전달받는다. 그럴 경우, SPT에서 해당 주소에 해당하는 페이지가 있는지 확인해서 존재한다면 해당 페이지에 물리 프레임 할당을 요청하는 vm_do_claim_page 함수를 호출한다. 이 함수에서는 위에서 설정한대로 각 페이지에 맞는 초기화 함수가 호출된다. not_present 값이 false인 상황을 살펴보면, 물리 프레임이 할당되어 있지만 page fault가 일어난 것이므로 그 경우는 read-only page에 write를 한 경우가 된다. 따라서 not_present가 false인 경우는 예외로 처리하면 된다. (return false) not_present가 true인 경우에도, read-only page에 write 요청을 할 경우가 생길 수 있으므로 이에 대한 예외 처리를 추가한다.

    /* Return true on success */
    bool vm_try_handle_fault(struct intr_frame * f UNUSED, void *addr UNUSED,
                             bool user UNUSED, bool write UNUSED,
                             bool not_present UNUSED) {
        struct supplemental_page_table *spt UNUSED = &thread_current()->spt;

        if (addr == NULL | is_kernel_vaddr(addr)) return false;
        // if the physical page doesn't exit
        if (not_present) {
            page = spt_find_page(spt, addr);
            if (page == NULL) return false;
            if (write == 1 &&
                page->writable ==
                    0) {  // if it's asking to write in unwritable page
                return false;
            }
            return vm_do_claim_page(page);
        }
        return false;
    }

Memory Management

• 목표: 물리 메모리 로드 대신, supplement page table으로 메모리를 관리한다
• 구현
  • Page Fault Handler 수정: kill 하지말고 spt에서 page를 찾고, 있으면 pte를 추가
  • struct thread, page, supplement_page_table, frame에 필요한 멤버 추가 가능
  • spt 관련 기본 함수 구현 (init, copy, kill 3가지)
  • 종료 시 SPT를 참조하여 어떤 리소스를 해제할 지 결정
  • spt 관련 page 연산 함수 구현 (find, insert, remove)
  • frame 관련 함수 구현 (get, claim, do_claim)
  • Free Frame이 없으면(swap slot이 가득차면), victim page 선택(eviction policy 구현)

    Anonymous Page

• 목표: Page Type에 따라 알맞게 처리하고, lazy loading을 구현한다.
• 구현
  • page type에 따른 initializer 호출
  • struct anon_page에 필요한 멤버 추가 가능
  • 처음은 무조건 uninit 페이지로 생성, 페이지 구조만 할당
  • lazy loading을 위해 load_segment while문 로직, setup_stack 로직 수정
  • Page Fault Handler에서 Valid한 Fault인지 체크 [여기까지 하면 fork 제외 Project2 테케 모두 통과]
  • fork를 고려한 SPT copy, kill 함수 구현
  • uninit_destroy, anon_destroy 구현 [ 여기까지 하면 Project2 테케 모두 통과 ]

    Stack Growth

• 목표: 스택이 현재 크기보다 커지면(Stack Access) 추가 페이지를 할당한다.
• 구현
  • 스택 포인터의 잘못된 access를 어디에서 체크할건지 고민
  • page fault handler에서 vm_stack_groth 호출, 구현 (최대 1MB 제한)

    Memory Mapped Files

• 목표: File-backed Page를 구현한다.
• 구현
  • lazy하게 do_mmap, do_munmap 구현
  • exit될 때 매핑 해제
  • file_init, initializer, destroy 구현

    Swap In/Out

• 목표: 메모리 할당량이 가득 차면, 프레임을 디스크로 교체한다.
• 구현
  • Anon일 경우 anon_init, initializer 수정 swap_in, swap_out 구현(out을 먼저)
  • file-backed인 경우, 매핑된 파일에 다시 기록됨 init, initializer 수정 backed_swap_in, backed_swap_out 구현

Memory Management

현재 상태는 페이지 테이블만 있음(pml4).

1. Implementing Supplemental Page Table

supplemental page table 구조체가 비어있다. 어떠한 정보가 필요한가?

페이지 폴트와 자원 관리를 처리해야함. 그럼 hash table이 일단 필요하겠다. hash 구조체 구경하기

• Hash 구조체를 supplemental_page_table 구조체 안에 추가

  <vm.h>
  struct supplemental_page_table { 
    struct hash spt_hash;
  };

• hash.h 에 주석을 보면 Instead, each structure that can potentially be in a hash must embed a struct hash_elem member. 이라고 되어있어서 page에 hash_elem 구조체 추가함

  <vm.h>
  struct page { 
    '''
    struct hash_elem hash_elem;
    '''
  };

그리고 세가지 function을 손봐야한다.

1.1 supplemental_page_table_init()

• void supplemental_page_table_init (struct supplemental_page_table *spt);

  • spt를 initialize 하기 위해 hash_init이라는 함수를 사용하고 싶은데 인자로 hash_hash_func라는 hash 값을 구해주는 함수포인터와 hash_less_func라는 해쉬 엘리먼트들의 크기를 비교해주는 것들을 넘겨야한다. bool hash_init (struct hash *h, hash_hash_func *hash, hash_less_func *less, void *aux) 그렇다면 hash_hash_func와 hash_less_func를 참고해서 page_hash, page_less함수를 만들자. 만들었으니 hash_init함수를 사용해서 한줄로 초기화를 해버리자.

  • <vm.c>
    /* Computes and returns the hash value for hash element E, */
    unsigned
    page_hash (const struct hash_elem *he, void *aux UNUSED) {
    const struct page *p = hash_entry(he, struct page, hash_elem);
    // hash_bytes: returns a hash of the size(sec arg) bytes in BUF(first arg) 
    return hash_bytes (&p->va, sizeof(p->va));
    }
    /* Returns true if A is less than B, or false if A is greater than or equal to B */
    bool
    page_less (const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED) {
    const struct page *pa = hash_entry(a, struct page, hash_elem);
    const struct page *pb = hash_entry(b, struct page, hash_elem);
    return pa->va < pb->va;
    }
    /* Initialize new supplemental page table */
    void
    supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
    hash_init(spt, page_hash, page_less, NULL);
    }

    1.2 spt_find_page()

• struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

  • hash_find() 함수 사용하자. 주석 설명 Finds and returns an element equal to E in hash table H, or a null pointer if no equal element exists in the table. 그렇다면 spt_find_page에서 인자로 받아오는 spt가 hash이니까 첫번째 매개변수로 넘기고, va를 아니까 page 할당받아서 va넣고 그 페이지의 hash_elem 을 넘기자.

    /* Find VA from spt and return page. On error, return NULL. */
    struct page *
    spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
    struct page *page = NULL;
    
    page = palloc_get_page(PAL_USER);
    page->va = va;
    
    struct hash_elem *e;
    e = hash_find(&spt, &page->hash_elem);
    
    return e!=NULL ? hash_entry(e, struct page, hash_elem):NULL;
    }

    1.3 spt_insert_page()

• bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

  • hash_insert(&spt, &page->hash_elem) 이렇게 쓰면 될것같은데 존재하지 않을 경우에만이라는 조건을 어떻게 넣을 수 있을까. hash_insert 함수의 주석을 보고 아이디어를 얻었다. Inserts NEW into hash table H and returns a null pointer, if no equal element is already in the table. If an equal element is already in the table, returns it without inserting NEW. 그럼 없던 데이터를 넣을 땐 null pointer를 반환하니까 함수 값이 널일 때만 실행 되게 하면 되겠다.

    /* Insert PAGE into spt with validation. */
    bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
                     struct page *page UNUSED) {
    int succ = false;
    
    return hash_insert(&spt, &page->hash_elem) == NULL ? true : false;
    }

    2. Frame Management

Implement vm_get_frame, vm_claim_page and vm_do_claim_page in vm/vm.c.

2.1 vm_get_frame

/* Gets a new physical page from the user pool by calling palloc_get_page.
 * When successfully got a page from the user pool, also allocates a frame,
 * initialize its members, and returns it.
 * 사용자 풀에서 페이지를 성공적으로 가져오면, 프레임을 할당하고 해당 프레임의
 * 멤버를 초기화한 후 반환한다. 페이지 할당을 실패할 경우, PANIC ("todo")로
 * 표시한다. (swap out을 구현한 이후 변경한다.)
 *
 * palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
static struct frame *vm_get_frame(void) {
    struct frame *frame = NULL;
    /* TODO: Fill this function. */
    void *kva = palloc_get_page(PAL_USER);

    if (kva == NULL) {
        PANIC("todo");
    }
    // 프레임을 할당하고 해당 프레임의 멤버를 초기화한 후 반환한다
    frame = malloc(size_of(struct frame));
    frame->kva = kva;

    ASSERT(frame != NULL);
    ASSERT(frame->page == NULL);
    return frame;
}

2.2 vm_do_claim_page

git book 설명 Claims, meaning allocate a physical frame, a page. You first get a frame by calling vm_get_frame (which is already done for you in the template). Then, you need to set up the MMU. In other words, add the mapping from the virtual address to the physical address in the page table. The return value should indicate whether the operation was successful or not.

프레임을 vm_get_frame으로 얻으라고 해서 얻고 frame이랑 page랑 밑에 함수에서 엮어주길래 나도 엮어주고 까지는 했는데 그 다음에서 add the mapping from the virtual address to the physical address in the page table 그니까 page table에서 가상주소에서 물리주소로 맵핑해줘라인데 page table에 어떻게 해줘야할지 난감했다.

page table 관련 함수가 threads/mmu.c에 있어서 함수를 뒤지다가 pml4_set_page() 함수의 주석을 보고 이놈으로 결정했다. 주석은 이렇다.

Adds a mapping in page map level 4 PML4 from user virtual page UPAGE to the physical frame identified by kernel virtual address KPAGE.

근데 pml4가 어디에 있느냐 말이다. 아 thread 구조체 안에 있다.

/* Claim the PAGE and set up the mmu. */
static bool vm_do_claim_page(struct page *page) {
    struct frame *frame = vm_get_frame();

    /* Set links */
    frame->page = page;
    page->frame = frame;

    // add the mapping from the virtual address to the physical address in the
    // page table (pml4_set_page())
    struct thread *curr = current_thread();
    pml4_set_page(curr->pml4, page->va, frame->kva, page->writable);

    return swap_in(page, frame->kva);
}

2.3 vm_claim_page

Claims the page to allocate va. You will first need to get a page and then calls vm_do_claim_page with the page.

/* Claim the page that allocate on VA. */
bool vm_claim_page(void *va UNUSED) {
    struct page *page = NULL;
    // spt에서 va에 해당하는 page 찾기
    page = spt_find_page(&thread_current()->spt, va);
    return vm_do_claim_page(page);
}

Memory Management

• 목표: 물리 메모리 로드 대신, supplement page table으로 메모리를 관리한다
• 구현
  • Page Fault Handler 수정: kill 하지말고 spt에서 page를 찾고, 있으면 pte를 추가
  • struct thread, page, supplement_page_table, frame에 필요한 멤버 추가 가능
  • spt 관련 기본 함수 구현 (init, copy, kill 3가지)
  • 종료 시 SPT를 참조하여 어떤 리소스를 해제할 지 결정
  • spt 관련 page 연산 함수 구현 (find, insert, remove)
  • frame 관련 함수 구현 (get, claim, do_claim)
  • Free Frame이 없으면(swap slot이 가득차면), victim page 선택(eviction policy 구현)

    Anonymous Page

• 목표: Page Type에 따라 알맞게 처리하고, lazy loading을 구현한다.
• 구현
  • page type에 따른 initializer 호출
  • struct anon_page에 필요한 멤버 추가 가능
  • 처음은 무조건 uninit 페이지로 생성, 페이지 구조만 할당
  • lazy loading을 위해 load_segment while문 로직, setup_stack 로직 수정
  • Page Fault Handler에서 Valid한 Fault인지 체크 [여기까지 하면 fork 제외 Project2 테케 모두 통과]
  • fork를 고려한 SPT copy, kill 함수 구현
  • uninit_destroy, anon_destroy 구현 [ 여기까지 하면 Project2 테케 모두 통과 ]

    Stack Growth

• 목표: 스택이 현재 크기보다 커지면(Stack Access) 추가 페이지를 할당한다.
• 구현
  • 스택 포인터의 잘못된 access를 어디에서 체크할건지 고민
  • page fault handler에서 vm_stack_groth 호출, 구현 (최대 1MB 제한)

    Memory Mapped Files

• 목표: File-backed Page를 구현한다.
• 구현
  • lazy하게 do_mmap, do_munmap 구현
  • exit될 때 매핑 해제
  • file_init, initializer, destroy 구현

    Swap In/Out

• 목표: 메모리 할당량이 가득 차면, 프레임을 디스크로 교체한다.
• 구현
  • Anon일 경우 anon_init, initializer 수정 swap_in, swap_out 구현(out을 먼저)
  • file-backed인 경우, 매핑된 파일에 다시 기록됨 init, initializer 수정 backed_swap_in, backed_swap_out 구현

kaist list

https://www.youtube.com/watch?v=8twIUEo1mIs

• Enable Demand paging/swapping
• Enable Strck Growth
  • Dynamic page allocation for page fault on stack
• Implement Memory mapped file
  • Implement mmap() and munmap()
  • differentiate file backed page and anonymous page
• Enable Accewnssign user memory

page_fault()

Userprog/exception.c
page_fault()
{

}

• Check if the memory ref is valid

  • valid
    • vm page에 들어가야하는 내용 locate하기 (공유페이지가 구현되어있다면, 페이지가 페이지 테이블에는 없는데 이미 페이지 프레임에 있을 수도 있다)
  • invalid
    • could be the invalid user address or Kernel address or permission error

• Allocate page frame

  • 페이지 폴트가 나면 os는 모든 페이지 프레임을 스캔하고 하나의 페이지 프레임을 선택해서 디스크에서부터 완벽한 페이지를 load? allocate 해야한다

• Fetch the data form the disk to the page frame

• Update page table

additional info for the individual virtual pages

• Virtual page num
• Read/Write permission
• Type of virtual page
  • (unwritable&unmodifiable) a page of EyLF executable file
  • a page of general file
  • (anonymous) a page of swap area
• (memory mapped file) Reference to the file object(info about which file it is from?) and offset
• amount of date in the page : the content size out of 4KB
• location the swap area
• In-momory flag: is it in memeory?

vm_entry(data structure: set of attribute each page)

what I have done

Memory Management

• 목표: 물리 메모리 로드 대신, supplemental page table으로 메모리를 관리한다
• 구현 list
  • 1. Page Fault Handler 수정: kill 하지말고 spt에서 page를 찾고, 있으면 pte를 추가
  • 2. struct thread, page, supplement_page_table, frame에 필요한 멤버 추가 가능
  • 3. spt 관련 기본 함수 구현 (init, copy, kill 3가지)
  • 4. 종료 시 SPT를 참조하여 어떤 리소스를 해제할 지 결정
  • 5. spt 관련 page 연산 함수 구현 (find, insert, remove)
  • 6. frame 관련 함수 구현 (get, claim, do_claim)
  • 7. Free Frame이 없으면(swap slot이 가득차면), victim page 선택(eviction policy 구현)

현재 상태는 페이지 테이블만 있음(pml4).

1번 Page Fault Handler 수정: kill 하지말고 spt에서 page를 찾고, 있으면 pte를 추가

1.1 Implementing Supplemental Page Table

supplemental page table 구조체가 비어있다. 어떠한 정보가 필요한가?

페이지 폴트와 자원 관리를 처리해야함. 그럼 hash table이 일단 필요하겠다. hash 구조체 구경하기

• Hash 구조체를 supplemental_page_table 구조체 안에 추가

  <vm.h>
  struct supplemental_page_table { 
    struct hash spt_hash;
  };

• hash.h 에 주석을 보면 Instead, each structure that can potentially be in a hash must embed a struct hash_elem member. 이라고 되어있어서 page에 hash_elem 구조체 추가함

  <vm.h>
  struct page { 
    '''
    struct hash_elem hash_elem;
    '''
  };

그리고 세가지 function을 손봐야한다.

• void supplemental_page_table_init (struct supplemental_page_table *spt);

  • spt를 initialize 하기 위해 hash_init이라는 함수를 사용하고 싶은데 인자로 hash_hash_func?라는 것과 hash_less_func라는 function pointer들을 넘겨야한다. bool hash_init (struct hash *h, hash_hash_func *hash, hash_less_func *less, void *aux) 그렇다면 hash_hash_func와 hash_less_func를 참고해서 page_hash, page_less함수를 만들자. 만들었으니 hash_init함수를 사용해서 한줄로 초기화를 해버리자.

  • <vm.c>
    /* Computes and returns the hash value for hash element E, */
    unsigned
    page_hash (const struct hash_elem *he, void *aux UNUSED) {
    const struct page *p = hash_entry(he, struct page, hash_elem);
    // hash_bytes: returns a hash of the size(sec arg) bytes in BUF(first arg) 
    return hash_bytes (&p->va, sizeof(p->va));
    }
    /* Returns true if A is less than B, or false if A is greater than or equal to B */
    bool
    page_less (const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED) {
    const struct page *pa = hash_entry(a, struct page, hash_elem);
    const struct page *pb = hash_entry(b, struct page, hash_elem);
    return pa->va < pb->va;
    }
    /* Initialize new supplemental page table */
    void
    supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
    hash_init(spt, page_hash, page_less, NULL);
    }

• struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

  • hash_find() 함수 사용하자. 주석 설명 Finds and returns an element equal to E in hash table H, or a null pointer if no equal element exists in the table. 그렇다면 spt_find_page에서 인자로 받아오는 spt가 hash이니까 첫번째 매개변수로 넘기고, va를 아니까 page 할당받아서 va넣고 그 페이지의 hash_elem 을 넘기자.

    /* Find VA from spt and return page. On error, return NULL. */
    struct page *
    spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
    struct page *page = NULL;
    
    page = malloc(size_of(struct page)); // 얘는 왜이래
    page->va = va;
    
    struct hash_elem *e;
    e = hash_find(&spt, &page->hash_elem);
    
    return e!=NULL ? hash_entry(e, struct page, hash_elem):NULL;
    }

• bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

  • hash_insert(&spt, &page->hash_elem) 이렇게 쓰면 될것같은데 존재하지 않을 경우에만이라는 조건을 어떻게 넣을 수 있을까. hash_insert 함수의 주석을 보고 아이디어를 얻었다. Inserts NEW into hash table H and returns a null pointer, if no equal element is already in the table. If an equal element is already in the table, returns it without inserting NEW. 그럼 없던 데이터를 넣을 땐 null pointer를 반환하니까 함수 값이 널일 때만 실행 되게 하면 되겠다.

    /* Insert PAGE into spt with validation. */
    bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
                     struct page *page UNUSED) {
    int succ = false;
    
    return hash_insert(&spt, &page->hash_elem) == NULL ? true : false;
    }

quiz

1번 문제: TLB

1.1 TLB 가 어떻게 페이지 테이블의 성능을 향상시키는지?

1.1 TLB는 Table Load Buffer 의 약자로 가상주소를 물리주소로 변환하는 것을 위한 페이지 테이블의 성능을 향상시키기 위해 있는 것으로, cache 기능과 비슷하게 시간지역성을 활용해서 한번 페이지 테이블을 통해 가져온 데이터를 TLB에 업데이트하여 다음에 같은 페이지를 참조하게 되면 TLB를 먼저 확인해서 페이지 테이블을 통해 변환하는 작업을 하지 않아도 되게 하는 것이다.

1.2 TLB miss 가 발생하면 시스템이 어떤 과정을 거쳐 메모리에 접근하는지?

1.2 TLB miss가 나면 크게 하드웨어가 처리하느냐, 소프트웨어가 처리하느냐에 따라 처리 방식이 다르다. 전통적으로는 하드웨어가 처리하는 방식인데 이는,

1. 페이지 참조가 유효한지 확인하고
2. 페이지 테이블에서 사용가능한 page를 확인하고 (사용 가능한 free page가 없다면 eviction policy에 따라 victim 을 선정하고 swap disk 에 swap 한다)
3. backup disk 에서 완벽한 free frame을 load하고
4. 페이지 테이블과 TLB를 업데이트한다.

소프트웨어가 처리하는 방식은 페이지 테이블을 거치지 않고 바로 가져와서 업데이트하는데 정확히는 기억이 나질 않는다. -> 이부분 찾아보기

내가 잘못 생각했던거 TLB 미스나면 페이지테이블 참조하는건데..! 아는건데 잘못생각했었다.

정답

2번 문제: Belady의 역설

paging 기법을 사용하는데 page fault 의 발생 빈도가 더 늘어나는 현상. 원인과 방지하는 해결방법.

정답

3번 문제: Thrashing 현상이란

page 부재가 너무 많이 발생하여 cpu 성능이 떨어지는 현상

"프로세스가 페이지 부재를" 이라고 설명하면 더 좋겠다

정답

4번 문제: 운영체제가 anonymous page를 0으로 초기화 하는 이유

anonymous page는 이미 페이지와 파일이 맵핑되어있는 file backed page 혹은 memory mapped page와는 다르게 페이지가 아무런 파일과도 맵핑되어 있지 않는 페이지를 말하는데 이를 초기화하지 않으면 페이지에 쓰레기 값이 들어가 있기 때문에 0으로 초기화 하는것이 좋다는 것으로 알고있다.

정답

5번 문제: LRU 캐시 알고리즘

5-1. 요청순서 9번의 캐시상태를 쓰시오 -> 5967 5-2.

clock 알고리즘 LRU와 비슷하게 성능을 낼 수 있는데 현실적으로 cost가 더 적어서 LRU대신 많이 쓰이는 것으로 알고 있다.

알고리즘 작동 방식은 정확하게는 모르겠다.. 2 [1, 2, 3, 4] [1, 1, 1, 1] 5 [1, 5, 3, 4] [0, 1, 0, 0] 1 [1, 5, 3, 4] [1, 1, 0, 0] 2 [1, 5, 2, 4] [0, 0, 1, 0] 3 [1, 2, 3, 4] [1, 1, 1, 1] 4 [1, 2, 3, 4] [1, 1, 1, 1] 5 [1, 2, 3, 4] [1, 1, 1, 1]

정답

https://www.youtube.com/watch?v=C26qsPwf-Js

이 아저씨가 푸는 방식으로 풀면 엄청 쉽다.

rule 몇가지만 유의하면서 풀면 된다.

• 누굴 쫓아낼 필요 없을때

  • frame에 넣고 ref를 1로 set (나머지 애들의 ref를 바꿀 필요는 없다)

• 쫓아내야할 때 (second chance를 주는 것임을 기억하자) (page fault가 발)

  • victim frame의 page를 보고 1이면 기회를 한번 더 주는 의미로 0으로 바꾸고 다음걸로 넘어간다. (0을 만날때까지 반복)
  • 어떤 페이지의 ref가 0이면 킥하고 새로 넣은 page의 ref를 1로 set.
    • 나머지 프레임(아래로만 바꾸고 맨 위로 올라가진 않는다)들의 ref를 0으로 set
    • victim page를 하나 아래로 바꾼다.

• 1218 월요일

• 권영진교수님 os강의
• 동료학습(keywords, and git book)
• filling the gap -> 아파서 나중에
• Gitbook/PPT 등 보고 Task 리스트업&구현 순서 생각

https://joong-sunny.github.io/swjungle%20survive/week11-1/

충격적인 사실. 내가 아는거. 책에서 배운거. 그니까 리눅스에서의 할당과 pintos에서의 할당이 다르다고한다

말록으로 할당하면 힙 영역에 mmap으로 할당하면 memory mapped 영역에 할당한다.

근데 pintos 에서는 memory mapped 영역도 없고 힙도 없다. 유저 옵션을 주지 않으면 모두 커널 pool에 할당되게 된다.

하..미치겠다

userstack at Linux

userstack at Pintos

pintos에는 mapped memory 영역이 없다

일단 내가 아는거는 이런시긍로 스택과 힙영역 사이에 shared memory영역이 즉, memory mapped 영역이 존재하는데 pintos에는 없다

• 1216 토요일 - 10시 30분 출근 (점심 2시간)

• [O] Keywords 정리
• kaist gitbook Project3 FAQ, Appendix Memory Allocation, Virtual Address, Page Table 읽기
• ostep or concepts 읽으면서 키워드 보충하기
• TIL

keywords

Virtual Memory

benefits

• 메모리 크기 프로그램이 더이상 물리메모리의 크기에 제약을 받지 않는다.

• 시스템 성능 향상 (better CPU Util, throughput) 각 프로그램은 물리메모리에 크기를 적게 차지하기 때문에 더 많은 프로그램들이 동시에 실행될 수 있게되어 CPU 활용도와 처리량이 증가하게 된다. 이로 인해 응답시간, 반환 시간은 증가하지 않으면서도 시스템 성능 향상.

• 시스템 속도 향상 프로그램이 메모리에 로드하고 스왑하는 I/O 작업이 적게 필요하게 되어 각 프로그램은 더 빠르게 실행될 수 있다.

목표

• 투명성(transparency) 운영체제는 실행 중인 프로그램이 가상 메모리의 존재를 인지하지 못하도록 가상 메모리 시스템을 구현해야 한다.

• 효율성(eiciency) 운영체제는 가상화가 시간과 공간 측면에서 효율적이도록 해야 한다. 시간적으로는 프로그램이 너무 느리게 실행되서는 안되고, 공간적으로는 가상화를 지원하기 위한 구조를 위해 너무 많은 메모리를 사용해서는 안된다.

• 보호(protection) 운영체제는 프로세스를 다른 프로세스로부터 보호해야하고 운영체제 자기 자신도 보호해야 한다. 프로세스가 탑재, 저장, 혹은 명령어 반입 등을 실행할 때 어떤 방법으로든 다른 프로세스나 운영체제의 메모리 내용에 접근하거나 영향을 줄 수 있어서는 안 된다.

우리가 c언어를 작성할 떄 볼 수 있는 주소는 물리주소일까 가상주소일까? 정답은 가상주소. 그렇다면 우리는 물리주소를 프로그래밍을 통해 볼 수 있을까? 정답은 NO. 오로지 운영체제 뿐이 명령어와 데이터가 탑재되어 있는 물리 메모리의 주소를 알 수 있다.

shared libraries

논리 메모리와 물리 메모리를 나눔으로써 두개 이상의 프로세스들이 파일(standard C library)과 메모리를 공유할 수 있게 한다. 프로세스 생성 중에 fork() 시스템콜을 사용함으로써 페이지들을 공유함으로써 프로세스의 생성을 더 빠르게 한다.

Page Table

• 페이지테이블 관리 코드 @ threads/mmu.c

• 페이지 테이블은 CPU가 가상 주소를 물리 주소로 변환하는 데 사용하는 데이터 구조. 페이지에서 프레임으로 변환하는 도구. Virt Addr -> Phys Addr

  Translation Lookaside Buffer (TLB)

• 특수한 작은 고속 룩업 하드웨어 캐시를 사용함. (기능도 캐시랑 거의 비슷)

• 히트율이 높은 이유 시간 지역성(temporal locality) 으로 인해 TLB의 히트율이 높아진다. 시간 지역성이란 한번 참조된 메모리 영역이 짧은 시간 내에 재 참조되는 현상을 일컫는다. 다른 캐시와 마찬가지로 TLB의 성공 여부는 프로그램의 공간 지역성과 시간 지역성 존재 여부에 달려 있다. 만약 프로그램이 공간 혹은 시간 지역성을 보이는 경우, TLB 사용 효과가 더욱 두드러지게 나타날 것이다.

• TLB가 가득 차 있으면 어떡하나? 기존 내역을 하나 골라서 새로 넣을 걸로 교체해야함(LRU, RR, or Random 정책들 중에서 골라서. tmi: LRU연산은 너무 비싸서 잘 안한다고 하고, 랜덤 정책은 은근 hit ratio가 평균값 나오기 때문에 자주 쓰인다고 함)

• TLB miss 를 누가 처리하나? -> either hardware or software depends on the operating system.

  • by hardware (Intel x86 is the example of managed by HW that uses multi-level page table)
    • (흐름 아래 그림 참고)
    • 페이지 테이블에서 원하는 페이지 테이블 엔트리 찾는다
    • 필요한 변환 정보를 추출한다
    • TLB를 갱신한다
    • TLB 미스가 발생한 명령어를 재실행한다
  • by software (RISC라는 CISC보다 최근에 등장한 컴퓨터 구조로 RISC기반 컴퓨터에서는 TLB miss를 처리하는 과정을 살펴보자)
    • TLB에서 주소 찾기 실패시 하드웨어가 예외 시그널 발생
    • 시그널을 받은 os는 명령어 실행을 일시 정지하고 실행모드에서 커널모드로 변경함으로 커널 코드 실행을 준비한다
    • 트랩 핸들러를 실행한다
    • 페이지 테이블을 검색해서 변환 정보를 찾고 TLB 접근이 가능한 "previleged" 명령어를 사용해서 TLB를 갱신한 후에 리턴한다
    • 하드웨어가 명령어를 재실행한다

흐름

[하드웨어가 TLB miss를 처리하는 경우]

• case(1) cpu ➡️ TLB @MMU ➡️ HIT! ➡️ Phys Addr

• case(2) cpu ➡️ TLB @MMU ➡️ MISS! ➡️ Page Table @MainMemory ➡️ HIT! ➡️ Phys Addr

• case(3) cpu ➡️ TLB @MMU ➡️ MISS! ➡️ Page Table @MainMemory ➡️ MISS! ➡️ Page Fault

Page Fault

Supplemental Page Table의 vip 손님은 page fault handler 임.

• 페이지 폴트 핸들러가 의미하는 바

프로젝트 2 에서는 페이지 폴트는 항상 커널이나 유저 프로그램의 버그를 나타냄. 프로젝트 3 에서는 더이상 저것만을 의미하지는 않는다. (좀 더 명확해졌다)

이제 페이지 폴트는 단순히 파일이나 스왑슬롯에서 페이지를 가져와야 한다는 뜻, 아니면 단순히 모든 비트가 0인 페이지 라거나. (페이지 폴트가 의미하는 경우의 수는 줄어들었지만 이제 이렇게 바뀌기 위해서는 우리(학생)가 page fault handler를 좀 더 손봐야 한다.)

페이지 폴트 발생 이후 프로시저

1. 내부 테이블(보통 PCB, Process Control Block)을 확인해서 해당 프로세스의 메모리 참조가 유효한지 아닌지 결정하기 위해 확인한다.

2. 유효하지 않은 참조라면 프로세스를 종료시킨다. 유효한데 해당 페이지에 가져오지를 못한거라면 이제 가져온다.

3. free-frame list에서 하나의 free frame을 찾는다.

4. 원하는 페이지를 새로 할당된 프레임으로 읽어오기 위해 보조 저장 장치 작업을 스케줄한다.

5. 저장소로부터 읽어오는게 끝났다면 내부 테이블을 새로 메모리에 적재된 페이지를 가르킬 수 있도록 업데이트한다.

6. 인스트럭션을 재시작해서 프로세스가 이제 해당 페이지에 접근할 수 있게한다. 마치 항상 메모리에 있었던 것처럼.

페이지 폴트 핸들러의 프로시저(more like orders)

• 페이지 폴트 핸들러는 누가 호출?

userprog/exception.c 에 있는 page_fault() 가 vm/vv.c 에 있는 vm_try_handle_fault()라는 이름을 가진 페이지 폴트 핸들러를 호출한다.

1. supplemental page table에서 부재가 발생한 페이지 찾기.
2. 페이지를 저장하기 위해 프레임을 획득하기.
3. 데이터를 파일시스템이나 스왑에서 읽어오기. (읽어오거나 0으로 초기화하는 방식으로 만들어서 프레임으로 가져옴)
4. 폴트가 발생한 가상 주소에 대한 PTE가 물리 페이지를 가리키도록 지정하기.

Lazy Loading

보통 lazy loading이라고 하면 웹에서 사용하는 기술을 이야기 하는데 OS에서도 virtual memory에서 비슷한 개념이 쓰이는데 Demand paging이라고 한다.

Demand-paged virtual memeory 에서는 프로그램 실행 중에 페이지가 요구될 때만 로드된다. 이는

Page Replacement Policy

Anonymous page

Swap Disk

File-backed Page

Direct Memory Access

운영체제가 Crash consistency 를 해결 못해주면 application programmer가 해야하는데 이거 잘 안함. 그러나 너무 중요.

foo 를 bar로 업데이트해줄거면 foo 아니면 bar만 accept

Rollback logging

create(/a/log) write(/a/log, "Foo") write(/a/file, "Bar") unlink(/a/log)

but

Possible cases

Fao For

해결 방법 -> fsync

create(/a/log) write(/a/log, "Foo") fsync(/a/log) write(/a/file, "Bar") fsync(/a/file) unlink(/a/log)

but still possible cases

Fao For

but still problem

create하는 동시에 directory block(이것마저 디스크에 적어야하기때문에) 해결하기위해 디렉토리에 fsysnc를 하나 더 넣음

create(/a/log) write(/a/log, "Foo") fsync(/a/log) fsync(/a/) ---> added one write(/a/file, "Bar") fsync(/a/file) unlink(/a/log)

End of Abstraction stories

Protection and Isolation

OS must regain control from app -> timer interrupt

1. Privileged instruction
   • 하드웨어가 디텍트해서 익셉션을 커널에게 보내고 커널이 결정한다
   • 즉, 하드웨어가 결정권을 커널에게 endorse 함으로써 protection한다.
   • 하드웨어가 privilge 가 더 높음. 결정권을 os에게 endorse
   • 하드웨어는 detect를 하는 매커니즘을 가지고 있고 os가 이걸 어떻게 할지에 대한 policy를 가진다. 즉, detect <-> policy(seperate design term)
2. Memory protection
3. (Timer) interrupt

Isolation

Isolation 이라고 하는건

1. data read & write 를
2. control (내 코드로 다른 앱으로 점프 하면 안돼)

Isolation by protection domain = process

Isolation boundary -> process

memory abstraction -> virtual address space를 분리시킴으로써 isolation을 한다.

File은 Isolation을 permission system으로 함. 모든 메커니즘과 policy가 OS가 해줌. 권한 체크해주는 polocy에 해당되는 친구가 Reference monitor임

Web P 사이에 communication 할 수 있게 하는 것. IPC라고 한다. IPC 기법에는 두가지가 있다.

• Shared memory (공유 물리 메모리)
• message passing with buffer (pipe, filefor, sema, etc)

같은 물리주소에서 어느 vm으로 가야한다고 알 수 있는 것이 cache coherence.

프로세스에서 다른 프로세스에게 값이 바뀌었다고 어떻게 알려줄 수 있는가? Signal. but it's slow. 그래서 쓰는게 Polling.

shared memory는 data copy가 안일어난다

msg passing 은 data copy가 일어난다

그래서

데이터가 작으면 카피 코스트가 적으니까 msg passing 데이터가 크면 shared memeory 쓴다

근데 일반적으로 편해서 데이터 커도 msg passing 쓴다

sharing

• Time sharing -> cpu -> scheduling
• Space sharing -> memory
  • 
  • page eviction은 File backed, swap은 Anon

sch

• fifo
  • con: convoy effect(high response time)
• SJF
  • con: starvation
• RR
  • con: turnaound time(low throughput)

Annon : 최초 - 0으로 밀어 / swap된 page 가져오기 File backed : loading from file/binary

page eviction하는걸 page reclamation(?)이라고

page replacement policies LRU 는 구현코스트가 너무 비쌈. 커널에 page fault 계속 내야해 Clock은 LRU를 approximates해서 사용한다. 근데 1번이 누군지는 몰라. 그렇지만 맨 뒤에가 누군지만 알면 되는거니까 ㄱㅊ

• 1215 금요일 - 10시 출근 (1시간 커피챗)

• kaist gitbook Project3 Virtual Memory 읽기
• kaist gitbook Project3 FAQ, Appendix Memory Allocation, Virtual Address, Page Table 읽기
• 공부 키워드 TIL 정리

by metamong

gitbook Project3 Virtual Memory - Intro

https://casys-kaist.github.io/pintos-kaist/project3/introduction.html

Source files

• include/devices/block.h, devices/block.c

Provides sector-based read and write access to block device. You will use this interface to access the swap partition as a block device.

이라고 나와있는데 이상함. 경로에 해당 파일 없음

아, 깃북 업뎃이 안된거라고 한다. 현재 위치는 아래임 include/devices/disk.h, devices/disk.c

Memory Terminology

pages

• 페이지, 때로 가상 페이지라고도 불리는 것은 길이가 4,096바이트(페이지 크기)인 가상 메모리의 연속된 영역이다.

• 페이지는 무조건 'page-aligned' 되어야하며, 페이지 크기로 균등하게 나눌 수 있는 가상 주소에서 시작해야 한다.

• 64비트 가상 주소의 마지막 12비트는 페이지 오프셋(또는 단순히 오프셋)이다. (상위 비트는 페이지 테이블에서의 인덱스를 나타냄)

• 각 프로세스는 하나의 독립적인 set of user(virtual)pages 를 가진다. which 가상주소 KERN_BASE(0x8004000000) 아래에 있는

• set of kernel (virtual) pages는 전역이므로 어떤 스레드나 프로세스가 실행 중이든 위치가 동일함

• 커널은 유저페이지 & 커널페이지에 접근 가능. but 유저페이지는 자신의 사용자 페이지에만 접근 가능

Frames

• 프레임(physical frame or a page frame)은 물리 메모리의 연속된 영역임

• 페이지와 마찬가지로 프레임은 page-size이며 page-aligned 되어야 함. (noticed point: 뭔가 프레임 사이즈? 라고 할 것 같은데 프레임도 페이지 사이즈, 페이지 얼라인 되어야한다고 한다)

• x86-64 아키텍처에서는 물리 주소에 직접적으로 접근할 수 있는 방법을 제공하지 않음.

• Pintos는 이를 우회하기 위해 커널 가상 메모리를 물리 메모리에 직접 매핑함.

TLB (translation look-aside buffer)

• 직역하면 변환 색인 버퍼라는 이름. 특수한 작은 고속 룩업 하드웨어 캐시를 사용함. (기능이 캐시랑 거의 비슷한듯)

• TLB가 가득 차 있으면 기존 내역을 하나 골라서 새로 넣을 걸로 교체해야함(LRU, RR, or Random 정책들 중에서 골라서. tmi: LRU연산은 너무 비싸서 잘 안한다고 하고, 랜덤 정책은 은근 hit ratio가 평균값 나오기 때문에 자주 쓰인다고 함)

Page Tables

• 페이지테이블 관리 코드 @ threads/mmu.c

• 페이지 테이블은 CPU가 가상 주소를 물리 주소로 변환하는 데 사용하는 데이터 구조. 페이지에서 프레임으로 변환하는 도구. Virt Addr -> Phys Addr

흐름 정리

• case(1) cpu ➡️ TLB @MMU ➡️ HIT! ➡️ Phys Addr

• case(2) cpu ➡️ TLB @MMU ➡️ MISS! ➡️ Page Table @MainMemory ➡️ HIT! ➡️ Phys Addr

• case(3) cpu ➡️ TLB @MMU ➡️ MISS! ➡️ Page Table @MainMemory ➡️ MISS! ➡️ Page Fault

Resource Management Overview

Supplemental page table

supplementing 페이지 테이블을 제공해서 페이지 폴트 핸들링이 작동할 수 있게 함.

Enables page fault handling by supplementing the page table. See Managing the Supplemental Page Table below.

Frame table

물리프레임의 효율적인 방출 정책 구현을 허용(?)

Allows efficient implementation of eviction policy of physical frames. See Managing the Frame Table below.

Swap table

스왑 스롯의 사용 상태를 트랙할 수 있음

Tracks usage of swap slots. See Managing the Swap Table below.

근데 이 세 개의 독립적인 데이터구조를 구현할 필요는 없음. 관련 리소스를 완전히 아님 부분적으로 통합해서 통일된 제이터 구조로 구성하는 것이 편리할 수 있음

내가 해야할 것은 각 엘리먼트에 어떤 정보가 담겨야 하는지, 데이터 구조의 스콥(local or global), 몇개의 인스턴스가 스콥 안에 필요로 할지 임.

설계를 간단하게 하기 위해서 non-pageable memory (e.g., memory allocated by calloc or malloc)에 자료구조를 저장하면 좋다.

구현시 고를 수 있는 옵션

• 리스트나 배열은 비효율적이라 추천하는건 비트맵 or 해시테이블. (Pintos에는 lib/kernel/bitmap.c 및 include/lib/kernel/bitmap.h에 비트맵 데이터 구조가 포함되어 있음)

• 비트맵은 참 또는 거짓이 되는 비트의 배열임.

• 비트맵은 보통 동일한 리소스의 사용을 추적하는데 사용됨.

• 핀토스의 비트맵은 크기가 고정되어있음. 하지만 크기 조정가능하게 확장도 가능함.

• 해시테이블은 다양한 크기의 테이블에서 효율적인 삽입 삭제를 지원함

Managing the Supplemental Page Table

• "보충 페이지 테이블" why 보충?

왜 Page Table 이라고 안하고 Supplemental Page Table 라고 하냐면,

보충 페이지 테이블은 페이지 테이블의 형식에 따른 제약으로 인해 각 페이지에 대한 추가 데이터를 제공하는 데이터 구조인데 이게 주로 "페이지 테이블" 이라고 불려서 혼란을 막기 위해 앞에 "보충" 이라는 말음 붙였다.

• Supplemental Page Table의 목적 주요 두 가지

첫 째로, (주요 목적) 페이지 폴트가 났을 때, Supplemental Page Table에서 부재가 발생한 가상 페이지를 조회하여 해당 위치에 어떤 데이터가 있어야 하는지 확인 하는 것이다.

둘 째로, 프로세스가 종료될 때, 어떤 자원을 해제할지 결정하기 위해 Supplemental Page Table를 참고한다.

Organization of Supplemental Page Table

• Supplemental Page Table를 꾸리는 두 가지 방법
  • 세그먼트를 기준으로
    • 여기서 말하는 세그먼트는 연속된 페이지 그룹을 말함. 예를들어, 실행 가능한 파일이나 메모리 맵핑 파일을 포함하는 메모리 영역
  • 페이지를 기준으로
  • (Optionally) 역설적이긴 한데 보충 테이블 페이지의 멤버를 tracking하기 위해 페이지 테이블을 사용하는 것도 가능. (잘하는 학생들에게만 추천요)

Handling page fault

Supplemental Page Table의 vip 손님은 page fault handler 임.

• 페이지 폴트 핸들러가 의미하는 바

프로젝트 2 에서는 페이지 폴트는 항상 커널이나 유저 프로그램의 버그를 나타냄. 프로젝트 3 에서는 더이상 저것만을 의미하지는 않는다. (좀 더 명확해졌다)

이제 페이지 폴트는 단순히 파일이나 스왑슬롯에서 페이지를 가져와야 한다는 뜻, 아니면 단순히 모든 비트가 0인 페이지 라거나. (페이지 폴트가 의미하는 경우의 수는 줄어들었지만 이제 이렇게 바뀌기 위해서는 우리(학생)가 page fault handler를 좀 더 손봐야 한다.)

• 페이지 폴트 핸들러는 누가 호출?

userprog/exception.c 에 있는 page_fault() 가 vm/vv.c 에 있는 vm_try_handle_fault()라는 이름을 가진 페이지 폴트 핸들러를 호출한다.

• 페이지 폴트 핸들러가 해야하는 일들(more like orders)
  1. supplemental page table에서 부재가 발생한 페이지 찾기.
  2. 페이지를 저장하기 위해 프레임을 획득하기.
  3. 데이터를 파일시스템이나 스왑에서 읽어오기. (읽어오거나 0으로 초기화하는 방식으로 만들어서 프레임으로 가져옴)
  4. 폴트가 발생한 가상 주소에 대한 PTE가 물리 페이지를 가리키도록 지정하기.

Managing the Frame Table

• 하는 일 비어있는 프레임이 없을 때 쫓아낼 페이지를 골라줌. 즉, eviction policy를 구현할 수 있도록 해줌

• 구성

  • 프레임 테이블 안의 각 프레임은 하나의 엔트리 정보를 갖음
  • 각 엔트리에는 해당 엔트리를 차지하고 있는 페이지에 대한 포인터(있으면)와 내가 선택해서 넣을 수 있는 기타 데이터들이 있음

• 사용 방법

  • 유저 페이지를 위해 프레임을 사용하고 싶으면 palloc_get_page(PAL_USER) 호출.(이렇게 해야 유저 풀에서 획득된 것임이 확실함)
  • 사용되지 않은 프레임을 획득하는 것이 중요. 근데 free상태인 프레임이 없으면 몇몇 페이지들을 쫓아내서 그 프레임을 free 상태로 만들어 줘야 함

• eviction 절차

  1. 페이지 재배치 알고리즘 이용해서 victim 고르기. 페이지 테이블에 있는 "accessed", "dirty" 비트들이 유용.
  2. 해당 프레임을 참조하는 모든 페이지 테이블에서 참조를 제거. (공유를 구현하지 않았을 경우는 해당 프레임을 참조하는 페이지는 항상 한 개만 존재 해야 함)
  3. (if necessary) 페이지를 파일 시스템이나 스왑에 write하기. (쫓겨난 프레임은 이제 다른 페이지를 저장하는 데에 사용할 수 있음)

Accessed and Dirty Bits

• 페이지에 read 하면 CPU는 페이지의 PTE에 있는 accessed bit를 1로 설정한다.

• write 할 때는 accessed bit 와 dirty bit 를 1로 설정한다.

• CPU는 절대 이 비트들을 0으로 되돌릴 수 없음. only the OS can.

• 같은 프레임을 참조하는 두 개이상의 페이지들인 aliases 를 유의해야한다. aliased 프레임이 accessed 될 때, accessed 비트와 dirty 비트는 하나의 페이지 테이블 엔트리에서만 업데이트됨

• pintos에서 모든 유저 가상 페이지는 커널 가상 페이지에 alias 되어있음. 내가 이 alias들을 관리해야 함

• alias 관리 예시

  • 내 code가 accessed 와 dirty 비트를 업데이트 할 때 양쪽 주소 모두를 확인하고 업데이트 해야함
  • 유저 가상 주소를 통해서만 유저 데이터에 접근하게 함으로써 커널이 이 문제를 피하게 할 수 있음

Managing the Swap Table

• 역할
  • 스왑테이블은 사용중인 스왑 슬롯과 빈 스왑 슬롯들을 추적하기.
  • 페이지가 다시 읽히거나 페이지 주인인 프로세스가 종료되어 버릴 경우엔 스왑 테이블이 스왑 슬롯을 free 하는거 승낙해주기.

• n-MB swap partition을 포함하는 디스크 생성 방법

• swap.dsk를 생성하려면 vm/build 경로에서 pintos-mkdisk swap.dsk --swap-size=n 명령어를 사용
• swap.dsk를 만들면 pintos 실행할 때 자동으로 추가 디스크로 연결됨.

흐름 이해에 도움이 되었던 그림

아쉬운 점 1

돌아는 가지만 가독성이 매우 떨어집니다

스택포인터 형변환 한번 하려고 하면...

문제가 뭐였을까

스택포인터 인자를 이렇게 받았던 것

그래서 한번 쓰려고 하면

parse[i] -> *(char **) rsp parse[i][j] -> **(char **) rsp

주소값 저장하는 코드

더 좋은 방법

BEFORS

AS

(char *)rsp ➡ (void*)(if_->rsp)

아쉬운점 2

비효율적인 문자열 저장 방식

동료 코드

system call

작성예정

느낀점

1) 도큐먼트도 좋지만 남들은 어떻게 하는지 관찰하자.

2)TIL은 사진이다.

왜냐

1. 여행가서 남는건 사진 밖에 없듯이 공부 후 남는건 정리한 글 뿐. 기억력을 믿지 말자.

2. 순간이 지나가면 놓치고 만다. 오늘 하루가 가기 전에 잡아두자.

• process_exec()

  • file_name문자열을파싱
  • 첫번째토큰을thread_create()함수에스레드이름으로전달

• start_process()

  • file_name문자열파싱 <- 여기서 또?
  • argument_stack()함수를이용해스택에토큰들을저장

• arguement_stack()

  • 유저스택에프로그램이름과인자들을저장하는함수
  • parse: 프로그램이름과인자가저장되어있는 메모리공간, count: 인자의개수, esp: 스택포인터를가리키는주소

한양대 슬라이드 내용인데 왜 process-exec에서 첫번쨰 토큰을 thread_create()함수에 전달하나?

음..큰그림을 모르겠다. 이해를 돕기 위해 블로그 참고 블로그

<init.c> → int main(void) → run_actions(argv) → run_task(char **argv) → process_wait(process_create_initd (task));

<process.c> → process_create_initd(task) → thread_create(file_name, PRI_DEFAULT, initd, fn_copy) → initd() → process_exec() → load(입력값, if) load에서 입력값 parsing, if에 주소저장, load 성공 후 실행할 명령어 주소저장 // 이진 파일을 디스크에서 메모리로 로드한다. // 로드된 후 실행할 메인 함수의 시작 주소 필드 초기화 (if.rip) // user stack의 top 포인터 초기화 (if_.rsp) // 위 과정을 성공하면 실행을 계속하고, 실패하면 스레드가 종료된다.

잠깐, 조금 더 큰 그림으로 프로그램의 전체 흐름을 다시 제대로 짚고 넘어가자

처음 시도한 코드

#include "userprog/process.h"
#include <debug.h>
#include <inttypes.h>
#include <round.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "userprog/gdt.h"
#include "userprog/tss.h"
#include "filesys/directory.h"
#include "filesys/file.h"
#include "filesys/filesys.h"
#include "threads/flags.h"
#include "threads/init.h"
#include "threads/interrupt.h"
#include "threads/palloc.h"
#include "threads/thread.h"
#include "threads/mmu.h"
#include "threads/vaddr.h"
#include "intrinsic.h"
#ifdef VM
#include "vm/vm.h"
#endif

static void process_cleanup(void);
static bool load(const char *file_name, struct intr_frame *if_);
static void initd(void *f_name);
static void __do_fork(void *);

/* General process initializer for initd and other process. */
static void
process_init(void)
{
    struct thread *current = thread_current();
}

/* Starts the first userland program, called "initd", loaded from FILE_NAME.
 * The new thread may be scheduled (and may even exit)
 * before process_create_initd() returns. Returns the initd's
 * thread id, or TID_ERROR if the thread cannot be created.
 * Notice that THIS SHOULD BE CALLED ONCE. */
tid_t process_create_initd(const char *file_name)
{
    char *fn_copy;
    tid_t tid;

    /* Make a copy of FILE_NAME.
     * Otherwise there's a race between the caller and load(). */
    fn_copy = palloc_get_page(0);
    if (fn_copy == NULL)
        return TID_ERROR;
    strlcpy(fn_copy, file_name, PGSIZE);

    /* --------------project 2 : arguemnt passing------------ */
    char *save_ptr;
    strtok_r(file_name, " ", &save_ptr);
    /* ------------------------------------------------------ */

    /* Create a new thread to execute FILE_NAME. */
    tid = thread_create(file_name, PRI_DEFAULT, initd, fn_copy);
    if (tid == TID_ERROR)
        palloc_free_page(fn_copy);
    return tid;
}

/* A thread function that launches first user process. */
static void
initd(void *f_name)
{
#ifdef VM
    supplemental_page_table_init(&thread_current()->spt);
#endif

    process_init();

    if (process_exec(f_name) < 0)
        PANIC("Fail to launch initd\n");
    NOT_REACHED();
}

/* Clones the current process as `name`. Returns the new process's thread id, or
 * TID_ERROR if the thread cannot be created. */
tid_t process_fork(const char *name, struct intr_frame *if_ UNUSED)
{
    /* Clone current thread to new thread.*/
    return thread_create(name,
                         PRI_DEFAULT, __do_fork, thread_current());
}

#ifndef VM
/* Duplicate the parent's address space by passing this function to the
 * pml4_for_each. This is only for the project 2. */
static bool
duplicate_pte(uint64_t *pte, void *va, void *aux)
{
    struct thread *current = thread_current();
    struct thread *parent = (struct thread *)aux;
    void *parent_page;
    void *newpage;
    bool writable;

    /* 1. TODO: If the parent_page is kernel page, then return immediately. */

    /* 2. Resolve VA from the parent's page map level 4. */
    parent_page = pml4_get_page(parent->pml4, va);

    /* 3. TODO: Allocate new PAL_USER page for the child and set result to
     *    TODO: NEWPAGE. */

    /* 4. TODO: Duplicate parent's page to the new page and
     *    TODO: check whether parent's page is writable or not (set WRITABLE
     *    TODO: according to the result). */

    /* 5. Add new page to child's page table at address VA with WRITABLE
     *    permission. */
    if (!pml4_set_page(current->pml4, va, newpage, writable))
    {
        /* 6. TODO: if fail to insert page, do error handling. */
    }
    return true;
}
#endif

/* A thread function that copies parent's execution context.
 * Hint) parent->tf does not hold the userland context of the process.
 *       That is, you are required to pass second argument of process_fork to
 *       this function. */
static void
__do_fork(void *aux)
{
    struct intr_frame if_;
    struct thread *parent = (struct thread *)aux;
    struct thread *current = thread_current();
    /* TODO: somehow pass the parent_if. (i.e. process_fork()'s if_) */
    struct intr_frame *parent_if;
    bool succ = true;

    /* 1. Read the cpu context to local stack. */
    memcpy(&if_, parent_if, sizeof(struct intr_frame));

    /* 2. Duplicate PT */
    current->pml4 = pml4_create();
    if (current->pml4 == NULL)
        goto error;

    process_activate(current);
#ifdef VM
    supplemental_page_table_init(&current->spt);
    if (!supplemental_page_table_copy(&current->spt, &parent->spt))
        goto error;
#else
    if (!pml4_for_each(parent->pml4, duplicate_pte, parent))
        goto error;
#endif

    /* TODO: Your code goes here.
     * TODO: Hint) To duplicate the file object, use `file_duplicate`
     * TODO:       in include/filesys/file.h. Note that parent should not return
     * TODO:       from the fork() until this function successfully duplicates
     * TODO:       the resources of parent.*/

    process_init();

    /* Finally, switch to the newly created process. */
    if (succ)
        do_iret(&if_);
error:
    thread_exit();
}

/* Switch the current execution context to the f_name.
 * Returns -1 on fail. */
int process_exec(void *f_name)
{
    char *file_name = f_name;
    bool success;

    /* We cannot use the intr_frame in the thread structure.
     * This is because when current thread rescheduled,
     * it stores the execution information to the member. */
    struct intr_frame _if;
    _if.ds = _if.es = _if.ss = SEL_UDSEG;
    _if.cs = SEL_UCSEG;
    _if.eflags = FLAG_IF | FLAG_MBS;

    /* We first kill the current context */
    process_cleanup();

    /* --------------project 2 : arguemnt passing------------ */
    int argc = 0;
    char *argv[64];
    char *ret_ptr, *next_ptr;

    ret_ptr = strtok_r(file_name, " ", &next_ptr);
    while (ret_ptr) // Until ret_ptr is not NULL
    {
        argv[argc++] = ret_ptr;                      // Store the current token on argv array
        ret_ptr = strtok_r(NULL, " ", &next_ptr); // Find the next token from next_ptr and store at the ret_ptr including NULL
    }
    /* ------------------------------------------------------ */

    /* And then load the binary */
    success = load(file_name, &_if);

    /* --------------project 2 : arguemnt passing------------ */
    argument_stack(argv, argc, &_if); // Create the argument stack
    printf('Im having a nightmare indeed -------------------------!');
    hex_dump(_if.rsp, _if.rsp, USER_STACK - (uint64_t)_if.rsp, true); // Display the contents of the arg stack using hex_dump
    /* ------------------------------------------------------ */

    /* If load failed, quit. */
    palloc_free_page(file_name);
    if (!success)
        return -1;

    /* Start switched process. */
    do_iret(&_if);
    NOT_REACHED();
}

/* Waits for thread TID to die and returns its exit status.  If
 * it was terminated by the kernel (i.e. killed due to an
 * exception), returns -1.  If TID is invalid or if it was not a
 * child of the calling process, or if process_wait() has already
 * been successfully called for the given TID, returns -1
 * immediately, without waiting.
 *
 * This function will be implemented in problem 2-2.  For now, it
 * does nothing. */
int process_wait(tid_t child_tid UNUSED)
{
    /* XXX: Hint) The pintos exit if process_wait (initd), we recommend you
     * XXX:       to add infinite loop here before
     * XXX:       implementing the process_wait. */
    for (int i = 0; i < 100000000; i++)
    {
    } // temeral code to test the argument passing
    return -1;
}

/* Exit the process. This function is called by thread_exit (). */
void process_exit(void)
{
    struct thread *curr = thread_current();
    /* TODO: Your code goes here.
     * TODO: Implement process termination message (see
     * TODO: project2/process_termination.html).
     * TODO: We recommend you to implement process resource cleanup here. */

    process_cleanup();
}

/* Free the current process's resources. */
static void
process_cleanup(void)
{
    struct thread *curr = thread_current();

#ifdef VM
    supplemental_page_table_kill(&curr->spt);
#endif

    uint64_t *pml4;
    /* Destroy the current process's page directory and switch back
     * to the kernel-only page directory. */
    pml4 = curr->pml4;
    if (pml4 != NULL)
    {
        /* Correct ordering here is crucial.  We must set
         * cur->pagedir to NULL before switching page directories,
         * so that a timer interrupt can't switch back to the
         * process page directory.  We must activate the base page
         * directory before destroying the process's page
         * directory, or our active page directory will be one
         * that's been freed (and cleared). */
        curr->pml4 = NULL;
        pml4_activate(NULL);
        pml4_destroy(pml4);
    }
}

/* Sets up the CPU for running user code in the nest thread.
 * This function is called on every context switch. */
void process_activate(struct thread *next)
{
    /* Activate thread's page tables. */
    pml4_activate(next->pml4);

    /* Set thread's kernel stack for use in processing interrupts. */
    tss_update(next);
}

/* We load ELF binaries.  The following definitions are taken
 * from the ELF specification, [ELF1], more-or-less verbatim.  */

/* ELF types.  See [ELF1] 1-2. */
#define EI_NIDENT 16

#define PT_NULL 0            /* Ignore. */
#define PT_LOAD 1            /* Loadable segment. */
#define PT_DYNAMIC 2        /* Dynamic linking info. */
#define PT_INTERP 3            /* Name of dynamic loader. */
#define PT_NOTE 4            /* Auxiliary info. */
#define PT_SHLIB 5            /* Reserved. */
#define PT_PHDR 6            /* Program header table. */
#define PT_STACK 0x6474e551 /* Stack segment. */

#define PF_X 1 /* Executable. */
#define PF_W 2 /* Writable. */
#define PF_R 4 /* Readable. */

/* Executable header.  See [ELF1] 1-4 to 1-8.
 * This appears at the very beginning of an ELF binary. */
struct ELF64_hdr
{
    unsigned char e_ident[EI_NIDENT];
    uint16_t e_type;
    uint16_t e_machine;
    uint32_t e_version;
    uint64_t e_entry;
    uint64_t e_phoff;
    uint64_t e_shoff;
    uint32_t e_flags;
    uint16_t e_ehsize;
    uint16_t e_phentsize;
    uint16_t e_phnum;
    uint16_t e_shentsize;
    uint16_t e_shnum;
    uint16_t e_shstrndx;
};

struct ELF64_PHDR
{
    uint32_t p_type;
    uint32_t p_flags;
    uint64_t p_offset;
    uint64_t p_vaddr;
    uint64_t p_paddr;
    uint64_t p_filesz;
    uint64_t p_memsz;
    uint64_t p_align;
};

/* Abbreviations */
#define ELF ELF64_hdr
#define Phdr ELF64_PHDR

static bool setup_stack(struct intr_frame *if_);
static bool validate_segment(const struct Phdr *, struct file *);
static bool load_segment(struct file *file, off_t ofs, uint8_t *upage,
                         uint32_t read_bytes, uint32_t zero_bytes,
                         bool writable);

/* Loads an ELF executable from FILE_NAME into the current thread.
 * Stores the executable's entry point into *RIP
 * and its initial stack pointer into *RSP.
 * Returns true if successful, false otherwise. */
static bool
load(const char *file_name, struct intr_frame *if_)
{
    struct thread *t = thread_current();
    struct ELF ehdr;
    struct file *file = NULL;
    off_t file_ofs;
    bool success = false;
    int i;

    /* Allocate and activate page directory. */
    t->pml4 = pml4_create();
    if (t->pml4 == NULL)
        goto done;
    process_activate(thread_current());

    /* Open executable file. */
    file = filesys_open(file_name);
    if (file == NULL)
    {
        printf("load: %s: open failed\n", file_name);
        goto done;
    }

    /* Read and verify executable header. */
    if (file_read(file, &ehdr, sizeof ehdr) != sizeof ehdr || memcmp(ehdr.e_ident, "\177ELF\2\1\1", 7) || ehdr.e_type != 2 || ehdr.e_machine != 0x3E // amd64
        || ehdr.e_version != 1 || ehdr.e_phentsize != sizeof(struct Phdr) || ehdr.e_phnum > 1024)
    {
        printf("load: %s: error loading executable\n", file_name);
        goto done;
    }

    /* Read program headers. */
    file_ofs = ehdr.e_phoff;
    for (i = 0; i < ehdr.e_phnum; i++)
    {
        struct Phdr phdr;

        if (file_ofs < 0 || file_ofs > file_length(file))
            goto done;
        file_seek(file, file_ofs);

        if (file_read(file, &phdr, sizeof phdr) != sizeof phdr)
            goto done;
        file_ofs += sizeof phdr;
        switch (phdr.p_type)
        {
        case PT_NULL:
        case PT_NOTE:
        case PT_PHDR:
        case PT_STACK:
        default:
            /* Ignore this segment. */
            break;
        case PT_DYNAMIC:
        case PT_INTERP:
        case PT_SHLIB:
            goto done;
        case PT_LOAD:
            if (validate_segment(&phdr, file))
            {
                bool writable = (phdr.p_flags & PF_W) != 0;
                uint64_t file_page = phdr.p_offset & ~PGMASK;
                uint64_t mem_page = phdr.p_vaddr & ~PGMASK;
                uint64_t page_offset = phdr.p_vaddr & PGMASK;
                uint32_t read_bytes, zero_bytes;
                if (phdr.p_filesz > 0)
                {
                    /* Normal segment.
                     * Read initial part from disk and zero the rest. */
                    read_bytes = page_offset + phdr.p_filesz;
                    zero_bytes = (ROUND_UP(page_offset + phdr.p_memsz, PGSIZE) - read_bytes);
                }
                else
                {
                    /* Entirely zero.
                     * Don't read anything from disk. */
                    read_bytes = 0;
                    zero_bytes = ROUND_UP(page_offset + phdr.p_memsz, PGSIZE);
                }
                if (!load_segment(file, file_page, (void *)mem_page,
                                  read_bytes, zero_bytes, writable))
                    goto done;
            }
            else
                goto done;
            break;
        }
    }

    /* Set up stack. */
    if (!setup_stack(if_))
        goto done;

    /* Start address. */
    if_->rip = ehdr.e_entry;

    /* TODO: Your code goes here.
     * TODO: Implement argument passing (see project2/argument_passing.html). */

    success = true;

done:
    /* We arrive here whether the load is successful or not. */
    file_close(file);
    return success;
}

/* Checks whether PHDR describes a valid, loadable segment in
 * FILE and returns true if so, false otherwise. */
static bool
validate_segment(const struct Phdr *phdr, struct file *file)
{
    /* p_offset and p_vaddr must have the same page offset. */
    if ((phdr->p_offset & PGMASK) != (phdr->p_vaddr & PGMASK))
        return false;

    /* p_offset must point within FILE. */
    if (phdr->p_offset > (uint64_t)file_length(file))
        return false;

    /* p_memsz must be at least as big as p_filesz. */
    if (phdr->p_memsz < phdr->p_filesz)
        return false;

    /* The segment must not be empty. */
    if (phdr->p_memsz == 0)
        return false;

    /* The virtual memory region must both start and end within the
       user address space range. */
    if (!is_user_vaddr((void *)phdr->p_vaddr))
        return false;
    if (!is_user_vaddr((void *)(phdr->p_vaddr + phdr->p_memsz)))
        return false;

    /* The region cannot "wrap around" across the kernel virtual
       address space. */
    if (phdr->p_vaddr + phdr->p_memsz < phdr->p_vaddr)
        return false;

    /* Disallow mapping page 0.
       Not only is it a bad idea to map page 0, but if we allowed
       it then user code that passed a null pointer to system calls
       could quite likely panic the kernel by way of null pointer
       assertions in memcpy(), etc. */
    if (phdr->p_vaddr < PGSIZE)
        return false;

    /* It's okay. */
    return true;
}

#ifndef VM
/* Codes of this block will be ONLY USED DURING project 2.
 * If you want to implement the function for whole project 2, implement it
 * outside of #ifndef macro. */

/* load() helpers. */
static bool install_page(void *upage, void *kpage, bool writable);

/* Loads a segment starting at offset OFS in FILE at address
 * UPAGE.  In total, READ_BYTES + ZERO_BYTES bytes of virtual
 * memory are initialized, as follows:
 *
 * - READ_BYTES bytes at UPAGE must be read from FILE
 * starting at offset OFS.
 *
 * - ZERO_BYTES bytes at UPAGE + READ_BYTES must be zeroed.
 *
 * The pages initialized by this function must be writable by the
 * user process if WRITABLE is true, read-only otherwise.
 *
 * Return true if successful, false if a memory allocation error
 * or disk read error occurs. */
static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage,
             uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
    ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
    ASSERT(pg_ofs(upage) == 0);
    ASSERT(ofs % PGSIZE == 0);

    file_seek(file, ofs);
    while (read_bytes > 0 || zero_bytes > 0)
    {
        /* Do calculate how to fill this page.
         * We will read PAGE_READ_BYTES bytes from FILE
         * and zero the final PAGE_ZERO_BYTES bytes. */
        size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
        size_t page_zero_bytes = PGSIZE - page_read_bytes;

        /* Get a page of memory. */
        uint8_t *kpage = palloc_get_page(PAL_USER);
        if (kpage == NULL)
            return false;

        /* Load this page. */
        if (file_read(file, kpage, page_read_bytes) != (int)page_read_bytes)
        {
            palloc_free_page(kpage);
            return false;
        }
        memset(kpage + page_read_bytes, 0, page_zero_bytes);

        /* Add the page to the process's address space. */
        if (!install_page(upage, kpage, writable))
        {
            printf("fail\n");
            palloc_free_page(kpage);
            return false;
        }

        /* Advance. */
        read_bytes -= page_read_bytes;
        zero_bytes -= page_zero_bytes;
        upage += PGSIZE;
    }
    return true;
}

/* Create a minimal stack by mapping a zeroed page at the USER_STACK */
static bool
setup_stack(struct intr_frame *if_)
{
    uint8_t *kpage;
    bool success = false;

    kpage = palloc_get_page(PAL_USER | PAL_ZERO);
    if (kpage != NULL)
    {
        success = install_page(((uint8_t *)USER_STACK) - PGSIZE, kpage, true);
        if (success)
            if_->rsp = USER_STACK;
        else
            palloc_free_page(kpage);
    }
    return success;
}

/* Adds a mapping from user virtual address UPAGE to kernel
 * virtual address KPAGE to the page table.
 * If WRITABLE is true, the user process may modify the page;
 * otherwise, it is read-only.
 * UPAGE must not already be mapped.
 * KPAGE should probably be a page obtained from the user pool
 * with palloc_get_page().
 * Returns true on success, false if UPAGE is already mapped or
 * if memory allocation fails. */
static bool
install_page(void *upage, void *kpage, bool writable)
{
    struct thread *t = thread_current();

    /* Verify that there's not already a page at that virtual
     * address, then map our page there. */
    return (pml4_get_page(t->pml4, upage) == NULL && pml4_set_page(t->pml4, upage, kpage, writable));
}

/* --------------project 2 : arguemnt passing------------ */
/*
| Address      | Name         | Data        | Type        |
| -------------|--------------|-------------|-------------|
| 0x4747fffc   | argv[3][...] | 'bar\0'     | char[4]     |
| 0x4747fff8   | argv[2][...] | 'foo\0'     | char[4]     |
| 0x4747fff5   | argv[1][...] | '-l\0'      | char[3]     |
| 0x4747ffed   | argv[0][...] | '/bin/ls\0' | char[8]     |
| 0x4747ffe8   | word-align   | 0           | uint8_t[]   |
| 0x4747ffe0   | argv[4]      | 0           | char *      |
| 0x4747ffd8   | argv[3]      | 0x4747fffc  | char *      |
| 0x4747ffd0   | argv[2]      | 0x4747fff8  | char *      |
| 0x4747ffc8   | argv[1]      | 0x4747fff5  | char *      |
| 0x4747ffc0   | argv[0]      | 0x4747ffed  | char *      |
| 0x4747ffb8   | return addr  | 0           | void (*)()  |

<argument stack downwards using rsp stack pointer>
if_->rsp:   struct intr_frame 구조체의 rsp 멤버 변수는 스택 포인터
if_->R:     struct intr_frame 구조체의 R 멤버 변수는 레지스터의 값
if_->R.rdi: R.rdi는 함수 호출 시 첫 번째 인수를 전달하는 레지스터
if_->R.rsi: R.rsi는 함수 호출 시 두 번째 인수를 전달하는 레지스터
*/
void argument_stack(char **argv, int argc, struct intr_frame *if_)
{
    /* Copy the argument string to the stack. */
    for (int i = argc - 1; i >= 0; i--) // Minus i to store the elements from the end of the array.
    {
        int N = strlen(argv[i]) + 1;  // Plus 1 to consider sentinel(`\0`) which need to be located at the end of string.
        if_->rsp -= N;                  // Decrement the stack pointer to make space for the argument string.
        memcpy(if_->rsp, argv[i], N); // Copy the argument string to the stack.
        argv[i] = (char *)if_->rsp;      // Update the argument pointer to point to the copied string on the stack.
    }

    /* word alignment */
    if (if_->rsp % 8)
    {
        int padding = if_->rsp % 8;
        if_->rsp -= padding;          // Align the stack pointer to an 8-byte boundary if needed.
        memset(if_->rsp, 0, padding); // Fill the padding bytes with zeros.
    }

    /* for NULL sentinel of argv array */
    if_->rsp -= 8;
    memset(if_->rsp, 0, 8); // Place a NULL sentinel at the bottom of the stack.

    /* Copy the argument pointer to the stack */
    for (int i = argc - 1; i >= 0; i--)
    {
        if_->rsp -= 8;                   // Decrement the stack pointer to make space for the argument pointer.
        memcpy(if_->rsp, &argv[i], 8); // Copy the argument pointer to the stack.
    }

    /* fake return address */
    if_->rsp -= 8;
    memset(if_->rsp, 0, 8); // Place a fake return address (0) at the bottom of the stack.

    if_->R.rdi = argc;                   // Set rdi (the first function parameter) to argc.
    if_->R.rsi = (char *)if_->rsp + 8; // Set rsi (the second function parameter) to &argv[0] which is the stack pointer's next address.
}
/* ------------------------------------------------------ */

#else
/* From here, codes will be used after project 3.
 * If you want to implement the function for only project 2, implement it on the
 * upper block. */

static bool
lazy_load_segment(struct page *page, void *aux)
{
    /* TODO: Load the segment from the file */
    /* TODO: This called when the first page fault occurs on address VA. */
    /* TODO: VA is available when calling this function. */
}

/* Loads a segment starting at offset OFS in FILE at address
 * UPAGE.  In total, READ_BYTES + ZERO_BYTES bytes of virtual
 * memory are initialized, as follows:
 *
 * - READ_BYTES bytes at UPAGE must be read from FILE
 * starting at offset OFS.
 *
 * - ZERO_BYTES bytes at UPAGE + READ_BYTES must be zeroed.
 *
 * The pages initialized by this function must be writable by the
 * user process if WRITABLE is true, read-only otherwise.
 *
 * Return true if successful, false if a memory allocation error
 * or disk read error occurs. */
static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage,
             uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
    ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
    ASSERT(pg_ofs(upage) == 0);
    ASSERT(ofs % PGSIZE == 0);

    while (read_bytes > 0 || zero_bytes > 0)
    {
        /* Do calculate how to fill this page.
         * We will read PAGE_READ_BYTES bytes from FILE
         * and zero the final PAGE_ZERO_BYTES bytes. */
        size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
        size_t page_zero_bytes = PGSIZE - page_read_bytes;

        /* TODO: Set up aux to pass information to the lazy_load_segment. */
        void *aux = NULL;
        if (!vm_alloc_page_with_initializer(VM_ANON, upage,
                                            writable, lazy_load_segment, aux))
            return false;

        /* Advance. */
        read_bytes -= page_read_bytes;
        zero_bytes -= page_zero_bytes;
        upage += PGSIZE;
    }
    return true;
}

/* Create a PAGE of stack at the USER_STACK. Return true on success. */
static bool
setup_stack(struct intr_frame *if_)
{
    bool success = false;
    void *stack_bottom = (void *)(((uint8_t *)USER_STACK) - PGSIZE);

    /* TODO: Map the stack on stack_bottom and claim the page immediately.
     * TODO: If success, set the rsp accordingly.
     * TODO: You should mark the page is stack. */
    /* TODO: Your code goes here */

#     return success;
}
#endif /* VM */

결과

os 왜필요하냐

1. API(read,write)를 제공함으로써 하드웨어를 사용할 수 있게 함
2. 하드웨어의 추상화

운영체제를 이해할 땐 탑다운을 이해해야함 추상화를 왜 이렇게 했는지를 이야기하기 위해 탑다운으로 이야기해야한다. -> 메타 놀리지 왓

추상화란?

1. 불필요한 것을 없엔다 -> 쉬운 이해(easy to use)

making sth easier to understand by ignoring some of details

what is the most important idea in terms of software architecture? layers of abstraction! but the John Ousterhout says plus, problem decomposition(DP)

처음 os디자인의 생각 1)쉬워야하고 2)하드웨어가 관리되어야하고 3)보호되어야한다 -> 프로세스: 하나의 컴퓨터처럼 보이게. 즉 프로세스란 하나의 컴퓨터를 추상화 한 것.

프로세스 CPU - virtualizing CPU Memeory - Virtual address space Storage -

이렇게 추상화해서 각 애플리케이션이 개별적인 컴퓨터를 사용하는것처럼 만들기 위해서는 "프로세스"

Knowlege for you guys 전역변수는 데이터영역 지역변수는 힙영역 char *p에서 p변수 자체는 stack영역에 p가 가르키는 주소는 어디에 존재? heap영역에

앱스트랙션: 각각의 컴포넌트를 디컴포즈

물리메모리

주소 추상화

각 물리주소를 페이지 단위(4kb)로 쪼개고 가상주소로 맵핑해주는 것

어떻게 하느냐?

• 세그멘티이션
• 페이징
• 세그멘티드 페이징

그렇지만 얘네들은 어디까지 주소를 추상화하기 위한 툴일 뿐 얘네들은 MMU안에 구현이 되어있음. 왜그랬을까? 너무빨라서 하드웨어에게 부탁. <- 이해안감

MMU가 접근이 가능한지 안한지 판단한다. 어떤것을 기준으로? protection. 이 정보는 어디에 써있냐? 페이지테이블을 보고 판단. 허용하면 안되는 곳을 접근하면 page fault handler가 page fault를 냄 세그멘테이션 폴트는 왜 난다는지 못들음

page table 디테일을 찾아보라 멀테레벨, 싱글 어쩌고 저쩌고 장단점 찾아보라

TMB라는 하드웨어 캐싱같이 도와주는 애인데 찾아봐라

페이지 테이블이 어디에 저장되어있냐->메모리

페이지 테이블 값 세팅 누가하냐 -> 커널 운영체제가 세팅해준걸 누가 사용하냐 -> 하드웨어

물리주소를 언제 할당해주냐 -> 사용할 때 그럼 운영체제는 사용하는 시점을 알아야하는데 어떻게 아냐 즉 디멘드 페이징을 어떻게 하느냐? Application first accesses unallocated physical memory 이렇게 도는동안 어플리케이션이 멈춘다. 그래서 옵티마이즈가 중요한데 이중에서 Zero the page가 제일 오래걸린다. 왜 지워야하냐? 보안 문제때문에. protection!

가상메모리

다시 페이지 폴트 핸들링

after fault : 메모리에 없어서 디스크까지 다녀오는거 file backed memeory

VA -> Function -> PM

Two types of memeory

1) file backed memeory 2) anonymous memeory

• Swap disk, etc

DMA는 IO시간을 옵티마이즈 하기 위해서 함. Read가 끝났어요 라고 알려주는 메커니즘을 뭐라할까요? 인터럽트~

Storage Abstraction(File system)

file system 은 memeory system 과 공통점과 차이점이 있다. File : a logical unit of storage

file도 VA -> Function -> PM 구조와 비슷함 It's called Level of indirection 물리주소에서는 실제 공간의 위치와 상관이 없음. 로지컬만 붙어있으면 됨 물리주소 어디에 맵핑할지 어떻게 정하냐? 데이터의 file과 offset을 가지고

HOW Indexed allocation, FAT, BTE, Extent tree allocation 하면 Pysical block을 리턴한다. MMU는 HW에서 하는데, File system은 인덱싱을 SW에서 한다. 왜? 느려도 되서 <- 이해안감

Metadata of a file 을 inode라고 함

인터널 노드는 어디에 저장되어있나? 메모리? 스토리지? 아니 둘다!

하드웨어가 도와줄 필요가 있나? 아니 느려서 ㄱㅊ

얼로케이트 언제해주냐? 사용할때! (페이지폴트같은 메커니즘은 필요없다) -> fsync 파일 시스템만이 가지고 있는 독특한 시스템콜이 불릴때 얼로케이션이 일어남.

데이터를 디램에 놓고 디램에서 꺼내 쓴다. 그렇게 하기 위해 있는것이 버퍼 캐시 or 페이지 캐시

또하나의 특징이 시스템 콜 인터페이스와 캐시 사이에 추상화된 VFS가 있음

classic consistency 가 뭔지 못들음 이걸 잘 하지 못하면 이케됨

User mode vs Kernel mode

User mode

• 한정된 권한: 보안과 안정성을 위해 유저 모드에서는 실행 중인 프로그램이 시스템 리소스에 직접 접근할 수 있는 권한이 제한되어 있다.
• 응용 프로그램 실행: 주로 응용프로그램은 응용 프로그램에서 실행된다. 사용자가 작성한 프로그램도 유저모드에서 동작한다.
• 시스템 콜 호출: 유저 모드에서 커널모드로의 전환은 exception(인터럽트, 폴트, 트랩핑 시스템 콜과 같은)을 통해 이루어진다. 사용자 프로그램이 커널의 서비스를 필요로 할 때, 시스템콜을 호출하여 커널모드로 전환하고 필요한 작업을 커널에서 수행하고 다시 유저모드로 돌아온다.

  이 부분에 대한 책에 나와있는 내용은 이렇다. Exception이 발생하고 control이 exception handler한테 전달될 때, 프로세서는 유저모드에서 커널모드로 바꾼다. 그리고 나서 어플리케이션 코드로 돌아왔을 때 프로세서는 모드를 커널모드에서 다시 유저모드로 변경한다.(csapp p.761)

Kernel Mode

• 전체 권한: 커널 모드에서 실행중인 코드는 시스템의 모든 자원에 대한 완전한 권한을 갖는다.
• 운영 체제 수행: 운영체제의 핵심 부분인 커널은 커널모드에서 동작한다. 커널은 하드웨어 리소스를 관리하고 다양한 프로세스 간의 스케줄링 및 통신을 담당한다.

  이 부분에 대한 책에 나와있는 내용은 이렇다. 커널은 각 프로세스마다 context를 유지한다. context는 선점된 프로세스를 다시 시작하기 위해 커널이 필요로 하는 상태이다. 이 context는 아래와 같은 값의 오브젝트로 구성되어 있다. general-purpose registers, the floating-point registers, the program counter, user’s stack, status registers, kernel’s stack, and various kernel data structures such as a page table and a file table(csapp p.762)

• 인터럽트 및 예외 처리: 커널 모드에서는 하드웨어 인터럽트 및 예외를 처리할 수 있다. 이는 운영 체제가 하드웨어 이벤트에 반응하고 시스템을 안정적으로 유지하기 위해 필요한 기능이다.

🙋🏻quick question: 커널이 실행되고 있는 동안 문맥교환이 발생할 수 있을까? 정답은 "있다" -> 커널은 유저를 대신해서 시스템콜을 실행해서 context switch를 일어나게 할 수 있다. 대표적으로 sleep 시스템콜이 있다.

시스템은 일반적으로 주기적인 타이머 인터럽트를 생성하는 메커니즘을 가지고 있고 이 인터럽트는 일반적으로 1ms 또는 10ms마다 발생한다. 타이머 인터럽트가 발생할 때마다 커널은 현재 프로세스가 충분히 실행되었다고 판단하고 새로운 프로세스로 전환할 수 있다.

Register vs Memory

공통점

• 데이터 저장: Register와 Memory는 모두 데이터를 저장하는 용도

• CPU와 상호작용: CPU와 직접적으로 상호 작용하여 데이터 처리 및 프로그램 실행에 기여함

• 핵심적 하드웨어 구성 요소: 둘 다 컴퓨터 시스템의 핵심 하드웨어 구성 요소임

  차이점

• 저장 용량과 속도: Register와 Memory는 모두 데이터를 저장하는 용도

• 용도: register는 주로 CPU의 연산 및 제어 목적으로 사용되고, Memory는 데이터와 프로그램 코드를 저장하는데 사용됨. (메모리는 주 기억장치(메인메모리)와 보조 기억장치로 나뉨)

  • 주 기억장치 (Main Memory 또는 RAM): 주로 현재 실행 중인 프로그램 및 데이터를 임시로 저장하는 용도로 사용됩니다. CPU가 직접 액세스할 수 있는 공간이며, 빠른 속도로 데이터에 접근할 수 있습니다. 전원이 꺼지면 저장된 데이터가 소멸된다.

  • 보조 기억장치 (Secondary Storage): 데이터의 영구 저장을 담당하며, 주로 하드 디스크, SSD, 광 디스크 등이 포함됩니다. 주로 대용량 데이터와 프로그램이 저장되어, 전원이 꺼져도 데이터가 보존됩니다.

• 접근방식: Register는 직접적인 연산 및 명령어 수행에 사용되므로 CPU 내부에서 직접적으로 접근된다. Memory는 CPU가 주소를 통해 간접적으로 access한다.

User Stack

힙과 마찬가지로 유저 스택은 프로그램 실행 중에 동적으로 확장 및 축소된다. 함수를 호출할 때마다 스택이 확장되고, 함수에서 반환할 때마다 축소된다. 유저스택은 가장 큰 유효한 사용자 주소(2^48-1) 아래에서 시작해서 작은 메모리 주소 방향으로 즉, 아래로 자란다.

여기서 스택을 break down 해보면 아래와 같다. (스택의 가장 밑바닥부터 - 윗윗 그림에서는 맨위, 바로 위 그림에서는 맨 아래칸부터)

• 스택 프레임 스택의 맨 밑에는 system start-up function, libc_start_main이라는 스택프레임이 있다.
• argv - argv[0], ... argv[argc-1], argv[argc] = NULL
  • argv 라는 포인터 변수는 각각 인자 문자열을 가리키는 포인터로 이루어진 null로 끝나는 배열을 가르키고 있다.
  • 유저-레벨 어플리케이션은 %rdi, %rsi, %rdx, %rcx, %r8, %r9 시퀀스들을 전달하기 위해 정수 레지스터를 사용합니다.(리턴값이 있다면 %rax에 저장됨)
  • %rsi를 argv 주소(argv[0]의 주소)를 가리키게, %rdi 를 argc 로 설정합니다.
• envp - envp[0], ... envp[n-1], envp[n] == NULL
  • envp 포인터 변수는 null로 끝나는 포인터 배열을 가르키며 각 포인터는 환경변수 문자열을 가르키고 있다. (각 문자열은 name=value 형식의 name-value의 쌍으로 구성된다)

argc와 argv의 차이

1. argc (Argument Count):
   • argc는 명령행 인자의 개수를 나타냅니다.
   • 프로그램을 실행할 때 명령행에 전달되는 인자의 총 개수가 여기에 저장됩니다.
   • 프로그램 실행 시 최소한 1이며, 프로그램 이름 자체도 하나의 인자로 간주됩니다.
2. argv (Argument Vector):
   • argv는 명령행 인자의 배열이며, 각 요소는 문자열로서 하나의 명령행 인자를 나타냅니다.
   • argv[0]은 프로그램의 이름을 가리킵니다.
   • argv[1], argv[2], ... 등은 추가적인 명령행 인자를 가리킵니다.

• Null-terminated environment variable strings (null-terminated array of pointers, which points to an envrionment variable string on the stack. environ이라는 전역변수가 해당 포인터들의 첫번째 요소를 가르킨다(envp[0])).
• Null-terminated command-line arg strings

System Call

csapp p.756

exception 두가지

1. external device hw exception=interrupt
2. user로 부터의 sw exception=fault, trap, abort

git book

File Descriptor

개념 복습

파일 디스크립터 in terms of File I/O : 파일을 열거나 읽거나 쓸 때 시스템은 각 파일에 대해 고유한 파일 디스크립터를 할당한다.

이 file descriptor는 파일에 대한 이후 모든 작업에서 사용됨

커널은 열린 파일에 대한 모든 정보를 추적. 애플리케이션은 디스크립터만 추적.

리눅스 쉘에 의해 생성된 프로세스는 세 개의 열린 파일을 가진다.

1. 표준 입력 - descriptor 0
2. 표준 출력 - descriptor 1
3. 표준 에러 - descriptor 2

open 함수는 파일 이름을 파일 디스크립터로 변환하고 해당 디스크립터 번호를 반환합니다. 반환된 디스크립터는 항상 프로세스에서 현재 열려 있지 않은 가장 작은 디스크립터입니다. flags 인자는 프로세스가 파일에 접근할 의도를 나타냅니다.

Cache

1. 캐시의 동작 원리:

Locality (지역성): 프로그램이 특정 데이터나 명령어에 접근할 때, 이와 주변에 있는 데이터에 대한 접근이 높은 확률이 있습니다. 캐시는 이러한 지역성을 활용하여 주로 사용되는 데이터를 저장합니다.

캐시 블록과 세트: 캐시는 일정 크기의 블록으로 데이터를 저장하며, 이러한 블록들을 셋(set)으로 구성합니다. 블록은 일반적으로 메모리에서 연속된 주소 공간을 차지하며, 각 블록은 캐시의 한 셋에 속합니다.

캐시 태그: 캐시에 저장된 데이터가 메모리에서 어디에 위치하는지를 나타내기 위해 태그(tag)라는 정보를 사용합니다. 캐시에 저장된 데이터에 접근할 때, 태그와 비교하여 원하는 데이터를 찾습니다.

캐시 미스(Cache Miss)와 비용: 캐시에 데이터가 없어서 메모리에서 가져와야 할 때, 이를 캐시 미스라고 합니다. 캐시 미스는 비용이 높은 작업으로 간주되며, 메모리로부터 데이터를 읽어와 캐시에 적재합니다.

2. 캐시 메모리의 설계와 최적화:

적절한 크기와 조직: 캐시의 크기와 조직은 성능에 큰 영향을 미칩니다. 적절한 캐시 크기와 구조를 선택하여 데이터 지역성을 잘 활용하는 것이 중요합니다.

캐시 지역성 활용: 시간 지역성(특정 데이터가 재사용되는 경향)과 공간 지역성(한 번에 여러 데이터가 사용되는 경향)을 활용하여 캐시의 효율을 높일 수 있습니다.

3. 캐시 미스(Cache Miss)의 비용:

Cold Miss: 처음 발생하는 캐시 미스. 초기화되지 않은 데이터에 접근할 때 발생하며, 초기 비용이 높을 수 있습니다.

Conflict Miss: 캐시의 한 셋에 여러 데이터가 들어가 있는 경우 발생하는 미스. 캐시의 셋 수를 늘리거나 다양한 방법으로 충돌을 해결해야 합니다.

Capacity Miss: 캐시가 꽉 차서 새로운 데이터를 적재할 수 없는 경우 발생하는 미스. 캐시 크기를 늘리거나 교체 알고리즘을 최적화하여 해결할 수 있습니다.

4. 캐시 지역성:

시간 지역성(Time Locality): 특정 데이터에 한 번 접근하면 가까운 시간 내에 다시 접근할 확률이 높음.

공간 지역성(Spatial Locality): 특정 데이터에 접근하면 그 주변의 데이터에도 접근할 확률이 높음.

Atomic Operation

개념 복습

원자적 연산은 다른 스레드나 프로세스의 동시적인 접근에 대해 불변성을 보장하는 연산입니다. 이는 연산이 전체적으로 완전히 실행되거나 전혀 실행되지 않는 것을 의미합니다. 즉, 다른 연산이 중간에 끼어들거나 일부만 실행되지 않습니다.

원자적 연산은 다중 스레드 환경에서 공유 자원에 안전하게 접근하기 위해 사용됩니다. 여러 스레드가 동시에 같은 자원에 접근하는 경우, 원자적 연산을 사용하면 경쟁 조건(Race Condition)과 같은 문제를 방지할 수 있습니다.

pintos project 에서의 원자적 연산

인터럽트 비활성화 및 활성화: intr_disable() 및 intr_enable() 함수를 사용하여 인터럽트를 비활성화하고 활성화합니다. 이러한 함수는 인터럽트를 원자적으로 다루어 공유 자원에 대한 안전한 접근을 보장합니다.

임계 영역 진입 및 이탈: lock_acquire() 및 lock_release() 함수를 사용하여 임계 영역에 진입하고 이를 이탈합니다. 이 함수들은 락(lock)을 원자적으로 획득하고 해제하여 여러 스레드 간의 동기화를 제어합니다.

Condition Variable 조작: cond_wait(), cond_signal(), cond_broadcast() 함수를 사용하여 condition variable을 조작합니다. 이러한 함수들은 스레드 간의 신호 전달 및 대기를 원자적으로 처리합니다.

세마포어 조작: sema_down() 및 sema_up() 함수를 사용하여 세마포어를 조작합니다. 세마포어는 스레드 간의 상호 배제와 동기화를 위해 사용되며, 이러한 함수들은 세마포어를 원자적으로 다룹니다.

페이지 테이블 조작: 페이지 테이블에 접근할 때 원자적으로 조작해야 합니다. 페이지 테이블 업데이트와 관련된 연산들은 스레드 간의 메모리 관리에서 중요한 부분이기 때문입니다.

파일 디스크립터 관리: 파일 디스크립터를 할당하거나 해제할 때 원자적으로 조작해야 합니다. 파일 디스크립터를 관리하는 동안 스레드 간의 충돌을 피하기 위해 특히 주의해야 합니다.

rax register

rax 레지스터는 x86 아키텍처에서 사용되는 64비트 레지스터 중 하나입니다. 이 레지스터는 다양한 목적으로 사용되며, 그 중 일부는 다음과 같습니다:

1. 함수 반환 값: 함수가 값을 반환할 때, 보통 rax 레지스터에 반환값이 저장됩니다. 이 규칙은 x86_64 아키텍처에서 cdecl 호출 규약을 따르는 경우에 해당합니다.

2. 시스템 호출 인터페이스 (System Call Interface): x86_64 리눅스에서는 시스템 호출 시 rax 레지스터에 시스템 호출 번호가 저장됩니다. 시스템 호출의 종류를 나타내는 중요한 정보를 포함합니다.

3. 산술 연산: rax 레지스터는 일반적인 산술 연산에 사용됩니다. 산술 연산 결과가 여기에 저장됩니다.

4. 임시 데이터 저장: 함수나 루틴에서 임시로 데이터를 저장하는 데 사용될 수 있습니다.

5. 부울 플래그 반환: 어셈블리 레벨에서는 일부 명령이 실행 후 상태에 따라 rax 레지스터에 부울 플래그 값을 저장할 수 있습니다.

6. 메모리 주소 저장: 포인터나 메모리 주소를 저장하는 데도 사용될 수 있습니다.

이외에도 다양한 용도로 rax 레지스터가 활용될 수 있습니다. 프로그램이나 컨텍스트에 따라서 그 목적이 달라집니다.

32 bit OS vs 64 bit OS