helloahram

1. 문제N명의 사람이 원을 이루면서 앉아있고, 순서대로 K번째 사람을 제거한다원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다 (N, K)-요세푸스 순열을 구하는 프로그램 작성하기 2. 제한시간 제한 2초, 메모리 제한 512MB1  3. 알고리즘 분류* 구현* 자료 구조* 큐 4. 접근 방식 원을 이루는 형태라고 해서 처음에는 원형큐를 이용해서 접근해 보려고 했었는데생각처럼 구현이 쉽지 않아서 결국 포인터 배열을 이용해서 풀었다 다음에 풀 때는 원형큐나 Linked List, 아니면 파이썬으로 덱을 이용해서 풀어봐야지  그리고 제거할 사람을 구하는 인덱스를 계산하는 방식을 찾는데 애를 좀 먹었다 5. 전체 코드// https://www.acmicpc.net/problem/11866..

Demand-Zero Memory가상 메모리 관리 기법 중 하나페이지가 실제로 사용되기 전까지는 물리적 메모리에 할당되지 않는 방식 실제로 해당 페이지가 접근되어 사용될 때 '0' 으로 채워진 페이지를 할당하고 초기화한다 Demand-Zero Memory 동작 방식 1. 페이지 폴트아직 메모리에 적재되지 않은 주소에 프로세스가 접근하려고 하면 페이지 폴트가 발생한다 2. 디맨트 제로페이지 폴트 핸들러가 해당 페이지를 물리적 메모리에 맵핑하고, '0'으로 초기화한다 3. 사용초기화된 페이지는 이제 프로세스에 의해 사용될 수 있으며프로세스는 '0'으로 초기화된 메모리를 사용하여 자신의 데이터를 저장할 수 있다 Demand-Zero Memory 장점1. 메모리 절약실제로 사용되지 않은 메모리는 물리적 메모리를..

mmap() - Memory Mapping 1) 파일 처리 성능 개선 기법 - 메모리에 파일을 매핑하기 프로세스에서 파일을 읽을 때, OS의 System Call을 시작으로 저장 매체에 접근하고 파일을 읽기까지의 과정이 복잡하고 오래 걸린다 또한, 내부적으로 OS가 처리해야 하는 과정이 많아 CPU의 성능이 떨어지기 때문에 파일에 접근하는 과정의 효율성을 높이기 위해 사용하는 함수가 mmap() 이다 2) mmap() 의 동작 방식 mmap() 은 파일의 내용을 메모리에 맵핑하여 올려서 파일이 마치 메모리에 있는 배열처럼 동작하게 만든다 파일을 읽기 위해서 저장 매체에 접근하는 것이 아닌 메모리의 데이터에 접근하는 방식이다 OS의 개입과 저장 매체로의 접근이 필요하지 않아 성능이 개선된다  3) mmap..

힙 정렬 Heap Sort힙의 특성을 이용하여 정렬하는 알고리즘힙은 '부모의 값이 자식보다 항상 크다'는 조건을 만족하는 완전 이진 트리이 때 부모의 값이 항상 자식보다 작을 때도 힙을 만족한다즉, 이러한 자식 부모 사이의 대소 관계가 일정하면 힙이다 * 힙 Heap - 쌓아 놓음, 쌓아 놓은 더미  힙에서 부모와 자식 간의 관계는 일정하지만, 형제 사이의 대소 관계는 일정하지 않으므로부분 순서 트리 Partial Ordered Tree 라고 한다  힙 정렬의 특징 힙 정렬은 '힙에서 최대값은 루트에 위치한다'는 특징을 이용하여 정렬하는 알고리즘이다 - 힙에서 최대값인 루트를 꺼낸다 - 루트 이외의 부분을 힙으로 만든다  이 과정에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다 루트를 삭제한 힙의 재..

직접 메모리 접근 DMA, Direct Memory Access CPU 개입 없이 주변 장치가 메모리에 접근하는 하드웨어 기능 주변 장치의 데이터는 장치 컨트롤러에 의해 로컬 버퍼로 이동하며, 특히 전송할 데이터 양이 많을 경우 더욱 효과적이다 전송할 데이터가 많은 경우 많은 양의 데이터 이동으로 인한 부담을 줄이기 위해 DMA를 이용한다 장치 컨트롤러가 데이터의 한 블록을 이동시키는 과정에서 CPU의 개입을 없애고, CPU에서는 데이터 이동이 완료되었다는단 한 번의 인터럽트만 발생시킴으로써, 데이터가 전송되는 동안 CPU는 다른 작업을 수행할 수 있어 효율성이 높아진다  DMA 작동 방식1. DMA 컨트롤러DMA 연산은 DMA 컨트롤러라는 특수한 하드웨어에 의해 수행된다이 컨트롤러는 주변 장치와 메모..

시스템 콜 System Call 대다수의 운영체제들은 커널 모드 Kernel Mode 와 사용자 모드 User Mode 가 구분되어 있다커널 모드는 커널 및 커널에 붙는 드라이버들이 작동되는 영역으로 모든 컴퓨터 리소스에 접근할 수 있고 하나의 가상 메모리 영역만을 공유하여 커널과 드라이버가 서로 접근할 수 있다 사용자 모드는 일반 프로그램들이 실행되는 영역으로 컴퓨터 리소스에 제한적으로만 접근할 수 있다 각 프로그램은 독립된 메모리 공간을 사용하는 프로세스로 실행되며, 프로세스 간의 직접적인 메모리 접근은 불가능하다  일반적인 프로그램들은 사용자 모드에서 실행되므로 커널 모드에 대해 직접적인 접근이 불가능하다 하지만 읽기/ 쓰기, 메모리 할당, 프로세스 생성과 같은 거의 모든 시스템 작업은 커널 모드에..

CH09 가상메모리9.9 동적 메모리 할당  추가적인 가상메모리를 런타임에 획득할 필요가 있을 때, 동적 메모리 할당기를 사용하는 것이 좀 더 편리하고 호환성이 좋다-> 프로그램이 실행되는 도중에 추가적인 가상메모리가 필요해질 경우, 동적 메모리 할당기를 사용하는 것이 더 좋다 동적 메모리 할당기는 힙 Heap 이라고 하는 프로세스의 가상메모리 영역을 관리한다  힙은 일반화의 오류를 범하지 않는 한도에서 힙이 미초기화된 데이터 영역 직후에 시작해서 위쪽으로 (높은 주소 방향으로) 커지는 무요구 메모리 영역이라고 가정한다 각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가리키는 변수 brk ("break" 라고 발음한다) 를 사용한다  할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다, 각 블록은 할..

단편화 Fragmentation 기억 장치의 빈 공간 또는 자료가 여러 개의 조각으로 나뉘는 현상 기억 장치의 사용 가능한 공간을 줄이거나, 읽기와 쓰기의 수행 속도를 늦추는 문제점을 야기한다 내부 단편화 할당된 블록이 데이터 자체보다 더 클 때, 할당된 블록 내에서 사용되지 않는 공간이 발생하는 현상 (컴퓨터 시스템 책 CH9.9.4)일정 크기의 페이지에 프로세스 할당 시, 프로세스의 크기가 페이지보다 작을 경우 내부 단편화가 발생한다 외부 단편화전체 가용 블록 공간은 충분하지만, 가용 블록이 여러 조각으로 나뉘어져 단일한 가용 블록은 없는 현상 프로그램이 메모리를 할당받고 종료되면 그 메모리 공간이 해제되는데, 이 공간이 다른 프로그램과 조각나게 되어 빈 공간이 생긴다 외부 단편화는 이전 패턴의 요청..

CH14 막간 - 메모리 관리 API 이번 장에서는 UNIX 의 메모리 관리 인터페이스에 대해 논의한다 핵심 질문 - 어떻게 메모리를 할당하고 관리해야 하는가UNIX/ C 프로그램에서 메모리를 할당하고 관리하는 방법은 강력하고 안정적인 소프트웨어를 구축하는 데 중요하다일반적으로 어떤 인터페이스가 사용되는가? 어떤 실수를 해서는 안 되는가?  14.1 메모리 공간의 종류C 프로그램이 실행되면, 두 가지 유형의 메모리 공간이 할당된다 1) 스택 Stack - 컴파일러가 관리 컴파일러에 의해 할당과 반환이 암묵적으로 이루어지기 때문에 자동 Automatic 메모리라고 불린다 func() 라는 함수 안에서 x 라 불리는 정수를 선언할 때 아래와 같이 선언한다 void func() { int x; // 스택에 i..

Week06 기간 2024.10.18 FRI - 2024.10.24 THU 조원 ㄷㅎ ㅇㅈ  Data Structure 구현 malloc No.To-do-List구현 여부 1가용리스트 조작 매크로 2mm_init 3extend_heap 4mm_free 5coalesce 6mm_malloc 7find_fit (first/next fit 둘중 한개는 필수구현) 8find_fit (그외 추가 구현) 9place 10realloc 테스트 케이스No.Test Case Check진행 여부 1short1-bal.rep : valid yes 2short2-bal.rep : valid yes 3amptjp-bal.rep : valid yes 4cccp-bal.rep : valid yes 5cp-decl-bal.rep :..