지금의 기록이 미래의 자산이 된다.

• 18. Paging

  2023-02-02

  devfancy

  OS
  • Concept of Paging
  • Advantages Of Paging
  • A Simple Paging
  • How To Store Address Translation
  • Address Translation

  이 글의 사진과 내용은 공룡책 과 컴퓨터학부 수업인 운영체제 강의자료를 기반으로 작성했습니다.

  Concept of Paging

  • Paging은 프로세스의 가상 주소 공간을 고정적인 크기(fixed-sized)로 나누어서 메모리에 할당하는 방식이다. 이때 고정적인 크기 단위를 page라고 부른다.

  • 그리고 이러한 가상공간의 page 를 실제 메모리에 할당할 때 이를 page frame이라고 부른다.

  • 즉 가상 메모리(주소 공간)에서는 page, 실제 메모리(주소 공간)에서는 frame 이라고 불리는 고정 크기의 공간으로 프로세스를 실행하겠다는 의미이다.

  Advantages Of Paging

  • Flexibility : 주소 공간의 추상화를 효율적으로 지원한다.

    • 얼마나 heap과 stack이 커지고 사용하는지에 대한 고민을 할 필요가 없다.

  • Simplicity : 여유 공간(free-space)의 관리가 쉽다.

    • 가상 메모리의 page와 page frame이 같은 크기를 가진다.

    • 할당이 쉽고 여유 공간을 유지한다.

  A Simple Paging

  • 128-byte physical memory with 16 bytes page frames

  • 64-byte address space with 16 bytes pages

  

  • 위의 그림에서 4개의 page로 구성된 가상 주소 공간을 8개의 page frame으로 쪼갠 것을 볼 수 있다.

  How To Store Address Translation

  • Paging 기법을 사용하기 위해서 가상 주소 공간에 있는 프로세스의 page들이 실제 메모리의 어디에 위치를 하는 지를 기억하는 Page table을 가지고 있어야 한다.

  

  • Page table 이란 가상 주소 공간의 page가 실제 메모리(주소 공간)에 어디에 위치해 있는 지를 기록한다.

    • Per-process structure(프로세스별 구조)

    • OS 가상 메모리의 영역에 저장된다.

  Address Translation

  • Paging 기법을 이용하여 주소 변환을 구하는 방법에 대해 알아보자.

  • 가상 주소 공간에는 두 가지 요소가 있다.

    • VPN : Virtual Page Number -> 상위 2개의 bit이 Page를 표현한다.

    • Offset : page 안에 있는 offset -> 나머지 4개의 bit이 offset을 표현한다.

  

  • Example: virtual address 21 in 64-byte address space

  

  A Simple 64-byte Address Space

  

  • Page table을 통해서 Virtual Page, Physical Page frame 의 i번째를 찾는다.

    • VPN 에서 상위 2개의 bit 값이 1이므로 page 1에 해당한다.

  • Offset을 통해 그 Page 안에 몇번째 메모리 주소인지 찾는다.

    • offset 값이 5이므로 16부터 시작해서 5번째인 21를 의미한다.
  Read All

  ---

• [Programmers] 17680. [1차] 캐시

  2023-01-31

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.01.31)
  • Answer Code2(23.02.20)
  • Review
  • Reference

  문제 링크

  성능 요약

  • 메모리: 78.5 MB, 시간: 2.76 ms - Answer Code1(23.01.31)

  • 메모리: 81.4 MB, 시간: 2.66 ms - Answer Code2(23.02.20)

  구분

  코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT

  Answer Code1(23.01.31)

  import java.util.*;
  
  class Solution {
      public int solution(int cacheSize, String[] cities) {
          int answer = 0;
          ArrayList<String> cache = new ArrayList<>();
  
          if(cacheSize == 0) // 캐시크기가 0
              return cities.length * 5;
  
          for(int i=0; i<cities.length; i++) {
              cities[i] = cities[i].toUpperCase(); // 대소문자 구분X
              if(cache.contains(cities[i])) { // cache hit
                  cache.remove(cities[i]);
                  cache.add(cities[i]);
                  answer += 1;
              }
              else { // cache miss
                  if(cache.size()==cacheSize) {
                      cache.remove(0);
                      cache.add(cities[i]);
                  }
                  else
                      cache.add(cities[i]);
                  answer += 5;
              }
          }
          return answer;
      }
  }
  

  Answer Code2(23.02.20)

  import java.util.*;
  
  class Solution {
      public int solution(int cacheSize, String[] cities) {
          int answer = 0;
          
          List<String> cacheList = new ArrayList<>();
          
          if(cacheSize == 0) {
              return cities.length * 5;
          }
          
          for(int i = 0; i < cities.length; i++) {
              cities[i] = cities[i].toLowerCase(); // 소문자로 변환
              //cache hit
              if(cacheList.contains(cities[i])) {
                  cacheList.remove(cities[i]);
                  cacheList.add(cities[i]);
                  answer += 1;
              }
              //cache miss
              else {
                  answer += 5;
                  if(cacheList.size() == cacheSize) {
                      cacheList.remove(0);
                      cacheList.add(cities[i]);
                  }
                  else {
                      cacheList.add(cities[i]);
                  }
              }
          }
          
          return answer;
      }
  }
  

  Review

  • LRU(Least Recently Used)에 대해 알고 있어야 풀 수 있는 문제였다.

    • LRU : 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.

    • LRU 알고리즘 구현을 보통 자료구조 Queue(큐)로 사용하면 편리하지만, Java에서는 LikedList가 Queue의 구현체이므로 Likedlist로 구현했다.

  • cache hit 인 경우(캐시에 존재한 경우) hit된 데이터를 기존 위치에서 가장 최근 위치로 이동 시킨다.(기존 위치를 제거하고 맨 뒤에 데이터를 추가한다)

  • cache miss 인 경우

    • 새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일한다면, 꽉차있는 의미이므로 가장 오랫동안 사용하지 않은 것을 제거하고, 맨 뒤에 데이터를 추가한다.

    • 새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일하지 않다면, 맨 뒤에 데이터를 추가한다.

  Reference

  • LRU 개념
  Read All

  ---

• [Programmers] 92334. 신고 결과 받기

  2023-01-29

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.01.29)
  • Review

  문제 링크

  성능 요약

  메모리: 70.2 MB, 시간: 0.49 ms

  구분

  코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT

  Answer Code1(23.01.29)

  import java.util.*;
  
  class Solution {
      public int[] solution(String[] id_list, String[] report, int k) {
          int[] answer = new int[id_list.length];
          ArrayList<User> users = new ArrayList<>();
          HashMap<String,Integer> suspendedList = new HashMap<>();
          HashMap<String,Integer> idIdx = new HashMap<String,Integer>();
          int idx = 0;
  
          //각 유저에 대한 고유 index를 setting후 users ArrayList에 User 객체 추가
          for(String name : id_list) {
              idIdx.put(name, idx++);
              users.add(new User(name));
          }
  
          //users의 idIdx.get(str[0])번째 index에 reportList에 피신고자 추가
          //users의 idIdx.get(str[1])번째 index에 reportedList에 신고자 추가
          for(String re : report){
              String[] str = re.split(" ");
              users.get(idIdx.get(str[0])).reportList.add(str[1]);
              users.get(idIdx.get(str[1])).reportedList.add(str[0]);
          }
  
          //reportedList의 크기가 주어진 k와 같거나 크면 suspendedList의 피신고자 put
          for(User user : users){
              if(user.reportedList.size() >= k)
                  suspendedList.put(user.name,1);
          }
  
          //answer 배열 각 index에 해당하는 유저의 신고당한 횟수를 count up
          for(User user : users){
              for(String nameReport : user.reportList){
                  if(suspendedList.get(nameReport) != null){
                      answer[idIdx.get(user.name)]++;
                  }
              }
          }
          return answer;
      }
  }
  
  class User{
      String name;                        //해당 유저명
      HashSet<String> reportList;		    //피신고자 리스트
      HashSet<String> reportedList;	    //신고자 리스트
      public User(String name){
          this.name = name;
          reportList = new HashSet<>();
          reportedList = new HashSet<>();
      }
  }
  

  Review

  • 해당 문제를 제대로 이해하지 못한다면 2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

    를 참고하자.

  Read All

  ---

• [Programmers] 77484. 로또의 최고 순위와 최저 순위

  2023-01-29

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.01.29)
  • Review

  문제 링크

  성능 요약

  메모리: 73.4 MB, 시간: 0.04 ms

  구분

  코딩테스트 연습 > 2021 Dev－Matching：웹 백엔드 개발자（상반기）

  Answer Code1(23.01.29)

  import java.util.*;
  
  public class Solution {
  
    public int[] solution(int[] lottos, int[] win_nums) {
      int[] answer = new int[2];
  
      Map<Integer, Integer> compareRank = init();
  
      int zero_count = 0, same_number = 0;
  
      for (int i = 0; i < 6; i++) {
        if (lottos[i] == 0) {
          zero_count += 1;
          continue;
        }
        for (int j = 0; j < 6; j++) {
          if (lottos[i] == win_nums[j]) {
            same_number += 1;
            break;
          }
        }
      }
  
      answer[0] = compareRank.get(same_number + zero_count);
      answer[1] = compareRank.get(same_number);
  
      return answer;
    }
  
    private Map<Integer, Integer> init() {
      Map<Integer, Integer> ret = new HashMap<>();
      int rank = 6;
      for (int i = 0; i <= 6; i++) {
        if (i == 0 || i == 1) {
          ret.put(i, rank);
          continue;
        }
        rank -= 1;
        ret.put(i, rank);
      }
      return ret;
    }
  }
  

  Review

  • HashMap 사용법을 잊어먹어서 푸는데 시간이 좀 걸렸다.
  Read All

  ---

• [Programmers] 67256. 키패드 누르기

  2023-01-29

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.01.29)
  • Review

  문제 링크

  성능 요약

  메모리: 74.3 MB, 시간: 0.27 ms

  구분

  코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT

  Answer Code1(23.01.29)

  class Solution {
    public String solution(int[] numbers, String hand) {
      StringBuilder sb = new StringBuilder();
  
      int left = 10;
      int right = 12;
  
      for (int i = 0; i < numbers.length; i++) {
        int n = numbers[i];
  
        if (n == 1 || n == 4 || n == 7) {
          left = n;
          sb.append("L");
        }
        if (n == 3 || n == 6 || n == 9) {
          right = n;
          sb.append("R");
        }
        if (n == 2 || n == 5 || n == 8 || n == 0) {
          if( n == 0 ) n = 11;
  
          int leftDiff = (Math.abs(n - left) / 3) + (Math.abs(n - left) % 3);
          int rightDiff =(Math.abs(n - right) / 3) + (Math.abs(n - right) % 3);
  
          if (leftDiff == rightDiff) {
            if (hand.equals("right")) {
              right = n;
              sb.append("R");
            }else{
              left = n;
              sb.append("L");
            }
          } else if (leftDiff > rightDiff) {
            right = n;
            sb.append("R");
          } else {
            left = n;
            sb.append("L");
          }
        }
      }
      return sb.toString();
    }
  }
  

  Review

  • StringBuilder() 클래스와 Math 클래스에 대해 다시금 개념을 복습하게 핸 문제였다.

  • 다음 복습에는 조금 더 효율적이면서 깔끔한 코드를 만드는 것을 목표로 하자.

  Read All

  ---