Programming
가상메모리와 요구페이징
1. 가상 메모리(Virtual Memory) 가상메모리를 이용해 물리 메모리 크기의 한계를 극복할 수 있다. 예를 들어 100MB의 메인 메모리에서 200MB 크기의 프로세스를 실행하는 것을 불가능하다. 그러나 하드디스크의 일부를 메모리로 사용함으로써 물리 메모리보다 큰 프로세스를 실행할 수 있다. How? - 프로세스 이미지를 모두 메모리에 올릴 필요는 없다. - 현재 실행에 필요한 부분만 메모리에 올린다! - 오류 처리 제외, 배열 일부 제외, 워드프로세스에서 정렬, 표 기능 제외 등등 => 동적 적재(dynamic loading)과 비슷한 개념 2. 요구 페이징(Demand Paging) 프로세스 이미지는 backing store에 저장한다. 프로세스는 페이지의 집합이므로 지금 필요한 페이지만 메..
세그멘테이션(Segmentation)
1. 세그멘테이션(Segmentation) 세그멘테이션이란 프로세스를 논리적 내용(=세그멘트)으로 잘라서 메모리에 배치하는 방법을 말한다. 즉, 프로세스를 일정한 크기단위로 자르는 것이 아니라 의미 단위로 자르는 것을 말한다. - 프로세스는 세그멘트(segment)의 집합 - 세그멘트의 크기는 일반적으로 같지 않다. MMU 내의 재배치 레지스터 값을 바꿈으로서 세그멘트를 메모리에 할당한다. CPU는 프로세스가 연속된 메모리 공간에 위치한다고 착각하게 된다. MMU는 세그멘트 테이블(segment table) 이 된다. 2. 주소 변환(Address Translation) 1) 논리주소 (Logical address) - CPU가 내는 주소는 segment 번호(s) + 변위(d) 2) 주소변환 : 논리주..
페이징(Paging)
1. 페이징(Paging) 페이징을 통해 외부단편화 문제를 완전히 해결할 수 있다. 페이징(Paging)이란 프로세스를 일정 크기(=페이지)로 잘라서 메모리에 담는 기법을 말한다. - 프로세스는 페이지(page)의 집합 - 메모리는 프레임(frame)의 집합 MMU 내의 재배치 레지스터 값을 바꿈으로서 페이지를 프레임에 할당한다. 즉, 프로세스 조각들인 페이지가 어느 위치의 프레임에 저장될 지를 재배치 레지스터가 기억한다. 이를 통해, CPU는 프로세스가 연속된 메모리 공간에 위치한다고 착각하게 된다. MMU는 페이지 테이블(page table)이 된다. 2. 주소 변환(Address Translation) 1) 논리주소 (Logical address) - CPU가 내는 주소는 2진수로 표현 (전체 m ..
![[백준] 1520. 내리막 길 자바(Java) 풀이](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbkp5Oj%2Fbtrfp23mDG5%2FxS1iO7OeuoQlZu4wPI23Pk%2Fimg.png)
[백준] 1520. 내리막 길 자바(Java) 풀이
1. 접근 방법 M과 N이 최대 500까지이기에 완전탐색을 할 경우 시간초과가 납니다. 그래서 DP를 이용해 이미 방문한 지점의 경우 다시 방문하지 않도록 중복을 제거해야만 합니다. 이차원 배열 dp[][]를 만듭니다. 그리고 dp에 해당 지점에 도달할 수 있는 경우의 수를 누적해서 저장해야 합니다. 예제를 보면 빨간 박스친 지점에서 중복이 발생합니다. 20 지점의 경우 2가지 방법으로, 15 지점의 경우 총 3가지 방법으로 도착할 수 있습니다. 단순히 BFS로만 풀게되면 아직 방문하지 않은 지점을 큐에 담을 때 20 지점이 담긴 후 32 > 30 > 25 > 20 의 경우의 수를 갱신하기 전에 먼저 큐를 빠져나가게 됩니다. 20에 도달할 수 있는 모든 경우의 수가 dp에 담은 후에야 20인 지점이 큐를..
연속 메모리 할당 - 메모리단편화, 최초적합, 최적적합, 최악적합
1. 다중 프로그래밍 환경 다중 프로그래밍 환경이란 하나의 메인메모리에 여러 개의 프로세스가 실행될 수 있다. - 부팅 직후 메모리 상태 : O/S + big single hole - 프로세스 생성 & 종료 반복 → scattered holes 부팅 직후 메인메모리에는 어떠한 프로세스도 아직 올라와있지 않기 때문에 하나의 빈 공간(hole)만이 있다. 여기서 프로세스가 생성되고 종료되는 것을 반복하면 프로세스가 빠져나간 자리는 빈 공간으로 남는다. 2. 메모리 단편화 (Memory fragmentation) 프로세스 실행과 종료를 반복하고 나면 Hole들이 불연속하게 흩어져 있기 때문에 프로세스 적재가 불가능한 상태가 된다. 프로세스가 들어갈 공간이 충분한데도 불구하고 hole들이 흩어져있어 적재를 못하..
메모리 낭비 방지 - 동적적재, 동적연결, 스와핑
1. 동적 적재(Dynamic Loading) 적재란 실행 파일을 메모리에 올리는 것을 말한다.(O/S를 메모리에 올리는 것은 부팅) 동적 적재란 프로그램 실행에 반드시 필요한 루틴/데이터만 적재하는 것을 말한다. 동적 적재를 사용하는 이유 - 모든 루틴(routine)이 전부 사용되는 것은 아니다. (예: 오류처리, 오류가 발생할 때만 메모리로 올린다.) - 모든 데이터(data)가 전부 사용되는 것은 아니다. (예: 배열, char[] buffer = new char[1000]) - 자바 : 모든 클래스가 전부 사용되는 것은 아니다. => 실행 시 필요하면 그때 해당 부분을 메모리에 올린다. 2. 동적 연결(Dynamic Linking) 여러 프로그램에서 공통으로 사용되는 라이브러리를 공통 라이브러리..
주기억장치관리 - MMU
주기억장치관리의 핵심은 '메인 메모리를 어떻게 잘 관리할 수 있을까'에 있다. 1. 프로그램을 메모리에 올리기 실행파일을 메모리에 올릴 때 몇가지 해결해야할 이슈들이 있다. - 메모리 몇 번지에 올릴 것인가? - 만약 다중 프로그래밍 환경에서는? 1) MMU의 역할 a. 주소변환 메인메모리 안에서 매번 다른 address로 실행파일이 올라가더라도 MMU 덕분에 CPU는 정상적으로 data를 읽을 수 있다. 이것을 주소 변환(address translation)이라고 한다. 이를 이해하기 위해서는 CPU가 메인메모리로부터 데이터를 읽는 과정을 이해할 필요가 있다. 위 그림과 같이 CPU에서는 메모리에 접근하기 위해서 address를 보낸다. 주소를 보낸다는 것은 내가 몇번지를 읽겠다는 의미이다.그럼 그 주..
주기억장치관리 개요 (Main Memory Management)
1. 메모리의 역사 1) 메모리 역사 - Core memory - 진공관 메모리 - 트랜지스터 메모리 - 집적회로 메모리 : SRAM, DRAM 2) 메모리 용량 - 1970년대 : 8-bit PC 64KB - 1980년대 : 16-bit IBM-PC 640KB > 1MB > 4MB - 1990년대 : 수MB > 수십MB - 2000년대 : 수백MB > 수GB 2. 언제나 부족한 메모리 메모리 용량이 기하급수적으로 늘어났기에 현대에는 메모리관리가 필요하지 않다고 생각할 수 있다. 그러나 메모리는 언제나 부족하다. 메모리 용량의 증가하면서 프로그램의 크기도 증가했기 때문이다. 1) 프로그램 변천 - 기계어/어셈블리어 작성 - C언어 작성 - 자바, 객체지향형 언어 작성 - 숫자처리 > 문자처리 > 멀티미디..