전체 글 (73) 썸네일형 리스트형 분기한정법 Branch-and-Bound 백트래킹과 같이 상태공간트리를 구축해서 해결 최적의 해를 구하는데 사용 어차피 다 확인해봐야해서 dfs 든 bfs든 상관없음(백트래킹은 dfs) 분기한정 알고리즘 원리 현재 있는 마디가 유망한지(promising)한지의 여부를 bound를 통해 결정한다. bound는 그 가지의 해답값의 한계를 나타낸다. 간단한 그림으로 분기한정법의 예시를 나타낸다. A와 B의 코스의 최소거리가 팻말에 나타나 있다. 이런 경우 당연히 A와 B는 고려하지 않는다(not-promising) 이런 경우에는 A를 먼저 탐색하는게 효율적이다. A에서의 최적의 해가 200이하면 B는 갈 필요 없기 때문 그렇다면 이 방법을 배낭채우기 문제에 적용해보자. 배낭에 채울 수 있는 최대 무게가 W 라고하자 n개의 아이템의 가격이 p 무게가 .. Virtual Memory Management-2 Least Recently Used (LRU) Algorithm 그렇다면 LRU를 어떻게 구현할까? 1. Timestamp 모든 page마다 counter를 가지게해서 구현한다 2. Stack stack 형태로 구현한다 1, 2번 모두 overhead가 크고 이를 지원할만 한 hw도 없다. 따라서 Referenced bit을 이용해서 Approximation 대충 근사치를 구해보자 referenced bit은 처음 os에 의해 0으로 설정되어있다가 페이지가 참조되었을 때 hw에 의해 1로 set된다. LRU-Approximation 1. Reference bit을 이용하는 방법 각 page마다 8bit짜리 참조비트를 부여한 다음 일정시간(timer interrupt마다 참조되었을경우 shift 연산을 수.. Virtual Memory Management 이전까지 배운건 Virtual physical로 변환하는 방법이다. 이제는 확장해서 Virtual Memory가 어떻게 무한하게 쓰이는지 알아본다. Demand Paging 하드에 저장돼있는 많은 pages중에 필요한 page만 제공한다 이게 어떻게 동작하냐? Locality라는 특성 때문이다. 모든 page를 physical에 올리 필요없이 Locality하게 작동시켜도 문제없다. 어차피 쓰는애들만 쓰고 쓰는애들은 그 주변 pages을 대부분 사용한다. Demand paging 기법을 사용하기 위해 Valid-Invalid Bit을 이용한다. 1 -> in-memory 0-> not-in-memory, 진짜 유요하지 않은경우 8번 이상은 진짜 유요하지 않아서 in-valid고 0~7번이 in-valid.. 컴퓨터구조 20 - Memory Hierarchy 그렇다면 왜 계층적 메모리 구성인가? 우리는 빠르고 큰 메모리를 원함 근데 싱글 level of memory에서는 제약이 많다. Idea : processor에 가까이있을수록 memory faster하다. 따라서 processor가 필요한 data를 빠른쪽에 두자. Locality Temporal Locality : cpu가 뭔가를 했으면 곧 똑같은 행동을 또 할것이다. int a b c 선언해놓고 쓰면 높은 확률로 a b c 쓸거니까 캐시에 올려놓고 쓰면 개이득 Spatial Locality : a를 갖다쓰는 순간에 근접한 b c 도 그냥 줘버림 이 두가지 원칙으로 cache 만든다. 책장으로 메모리구조를 비유하자면 내 손에 있는 책 : 레지스터파일 Desk : level 1 cache Bookshel.. Memory Management Strategies - 3 Valid (v) or Invalid (i) Bit In A Page Table 9장에서 배울 내용이라 간략하게 설명하면 이전 방식에서 memory protection을 위해서는 address의 시작과 끝만 알고있으면 됐다. 근데 paging하니까 page의 번호를 알고 있어야 한다. 그것도 단순히 시작과 끝이아닌 현재 physical memory 위에 page가 올라가있으면 valid 잠시 하드로 내려가 있거나 사용 불가능하면 invalid를 부여해 메모리를 보호한다. Page 크기가 너무 크다 줄이기위한 설계를 알아보자. Two -Level Paging Example 두개의 계층적 구조로 설계한다. 이런 다단계 paging의 장점은 메모리를 절약할 수 있다. 쪼갠 table이 invalid한 경우 아.. Memory Management Starategies -2 프로그램 내부에서 사용하는 주소 logical(virtual) 실제 메모리에 올라가는 주소 physical 밑에와 같은 프로그램을 실행시켜보면 #include int n = 0; int main () { printf (“&n = 0x%08x\n”, &n); } % ./a.out &n = 0x08049508 % ./a.out &n = 0x08049508 n에 대하여 같은 주소가 나오는데 이는 실제로 같은 physical한 주소로 올라가는 것이 아니다. 프로그램 내부에서 사용되는 주소가 출력되므로 같은 값이 나오는 것이다. MMU 이전 시간에 excution time에 memory를 binding할때 도와주는 hw인 mmu에 대해서 간략하게 배웠다. 이러한 mmu는 어떻게 설계 되어야할가? 첫번째로 할수 있.. Memory Management Starategies 운영체제의 기능 : hw 관리해 주는거 이전에 배운 스케줄링이나 쓰레드는 cpu에 주로 효과적인 전략 이번에는 메모리에서 쓰이는 전략을 알아보자구~ 멀티프로그래밍 환경에서 메모리 사용시 고려할 점이 있다. 이러한 문제를 해결하는 방법이 VM 메모리에는 두 종류가 있다. physical과 virtual(logical) physical은 실제 우리가 보는 메모리이고 virtual(logical)은 프로그램 내부에서 사용되는 주소이다. 가상메모리를 이용해서 physical memory 고려하지 않고 프로그래밍 할 수 있어 편하다 실제 메모리보다 더 큰 영역 제공가능하다 (안쓰는 프로세스 hdd로 잠시 보낸다) 전체 physical memory가 4GB라도 각 process의 주소공간의 합은 이것보다 크게 사용.. 컴퓨터구조 19 - Memory Hierarchy Memory Hierarchy : 메모리 계층구조 컴퓨터 성능을 올리기위해선 cpu 비해 매우 느린 메모리를 향상시켜줘야한다. 현실적으로는 불가능. CS가아닌 hw적으로 설명해주셔서 이해가 잘 안된다. pmos transister? 1bit를 저장하는 거라는데 반도체 : 특정한 조건에 따라 도체, 비도체 성질을 둘다 띄는거. 이 조건을 pmos가 설정해준다. 전압은 정적상태 전류는 흐르는 상태?? 그냥 가만히있어도 전압이 센다 그래서 refresh해준다?? 계속 돌면서 값 유지하고 있는다. 좀 옛날거긴한데 암튼 DRAM이 느리다보니까 손해가 크다. 이전 1 ··· 5 6 7 8 9 10 다음
