컴퓨터공학54 [운영체제] 페이징 교체 알고리즘 최적(OPT) 가장 오랫동안 참조되지 않을 페이지 교체 가장 낮은 페이지 폴트를 발생시키지만 미래를 예측할 수 없어 구현 불가능 → 다른 알고리즘을 평가하는 참고용으로만 쓰인다. LRU 가장 오랫동안 참조되지 않은 페이지 교체 최적에 근접한 성능이나 구현이 어렵고 오버헤드가 크다. 페이지 참조시간을 기록하는 공간이 사용된다 구현방법 각 페이지의 최종 참고시간을 기록하는 테이블을 생성한다. 이중연결리스트 스택을 이용한다. FIFO 가장 오래 전에 적재된 페이지 교체한다. 가장 쉽게 구현 가능하지만, 페이지 폴트 가능성이 높다. 교체되는 페이지 메모리 위치에 적재가 된다. FIFO라고 페이지가 큐처럼 움직이는 것이 아니다. LFU 가장 참조횟수가 적은 페이지 교체 교체 대상이 여러 개 이면 가장 오래된 페이.. 2023. 5. 25. [백준] 2887번: 행성 터널 | C++ https://www.acmicpc.net/problem/2887 2887번: 행성 터널첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이www.acmicpc.net 접근방법1. MST문제다. union-find 써야 할 것 2. 모든 행성 간 가중치를 구하려면 N! 인데? 3. 행성 간 가중치는 행성 간 3차원 거리가 아니라 min(|xA-xB|, |yA-yB|, |zA-zB|) 이다. 4. x, y, z 대로 정렬 3번 수행하고 인접한 행성의 거리를 구한다. 5. 힙에 넣어 가중치 최솟값을 구한다면? 라고 생각회로 거쳤다. 정렬.. 2023. 5. 22. [자료구조] 세그먼트 트리을 이용해 구간 합 구하기 구간 합 구간 합을 구하기 위해 사용되는 방법은 세 가지이다. 1. for문으로 해결하기 int ans = 0; for (int i=l; i 2023. 5. 21. [웹] HTTP/1.0 HTTP/1.1 HTTP/2, HTTP/3 차이 HTTP HTTP/0.9 GET 메서드만 지원됐고 헤더가 없었다. HTTP/1.0 기본적으로 한 연결당 하나의 요청을 처리하게 설계되었다. 따라서 요청을 할 때마다 클라이언트와 서버가 TCP 3-handshake를 수행했기 때문에 RTT(Round Trip Time, 패킷이 목적지에 도달하고 나서 다시 출발지로 돌아오기까지 걸리는 시간)가 증가하는 단점이 생겼다. 또, GET, POST, HEAD 메서드만 지원됐다. (HEAD는 헤더 정보만 전송된다.) HTTP/1.1 HTTP/1.0의 단점(매번 연결해야 함)을 해결하기 위해 발전한 버전이다. keep-alive 옵션으로 여러 번 송수신할 수 있게 바뀌었다. 처음 TCP 연결 후 지정한 timeout 동안 연결을 지속한다. 또 파이프라이닝 기능이 지원된.. 2023. 5. 18. [네트워크] TCP와 UDP 네트워크 기본 중 기본! OSI 4계층의 TCP와 UDP 프로토콜을 알아보자. TCP TCP(Transmission Control Protocol)와 UDP의 가장 차이점은 '연결' 아닐까! TCP는 연결 지향성이다. 한 번 연결을 하면 양방향으로 통신할 수 있다는 것을 의미한다. 또한 TCP는 흐름 제어, 에러 제어, 혼잡 제어 같은 기능을 제공한다. 연결 오버헤드와 순차성 제어를 위해 속도가 느리다. 연결 지향성이다. 연결 후 양방향 통신 흐름제어, 에러제어, 혼잡제어 기능 제공 흐름제어 : 송신측과 수신측 사이 데이터 처리 속도 차이로 인해 수신측의 버퍼가 오버플로우 나지 않도록 제어하기 위한 기능이다. 전송량 > 수신량일 경우 전송율을 낮춘다. stop and wait 방식 sliding wind.. 2023. 5. 16. [알고리즘] 해시 충돌 해결 방법 | Hash Collision Seperate Chaining 추가적인 공간을 활용해 충돌을 해결한다. seperate 뜻에 맞게 Linked-List를 사용한다. 보통 헤드에 삽입한다. (테일에 삽입하면 테일까지 가는 시간이 걸리기 때문) 최악의 경우 하나의 해시에 데이터가 몰리면, 조회할 때 Linked-list를 탐색하는 시간이 걸리게 된다. Open Addressing Linear Probing 해시 충돌 발생 시 충돌이 발생하지 않을 때까지 해시를 linear 하게 탐색한다. 단, clustering 군집현상이 발생할 수 있다. Quadratic Probing 충돌 발생 시 해싱 함수에 특정 연산을 더해 새로운 해시를 제작한다. 보통 제곱연산을 쓰는데 추가적인 상수곱이나 제곱연산이 가능하다. 사진을 예시로 3번째 값 hf_q.. 2023. 5. 3. [운영체제] 페이징과 외부 단편화, 내부 단편화 스와핑 메모리에 적재된 프로세스가 잠시 저장공간(SSD, HDD)에 물러났다가 다시 메모리로 적재되는 작업 가상 메모리를 이해하기 위한 약간의 지식 초기 메모리 관리법 MMU(Memory Management Unit)라는 논리 주소를 물리 주소로 변환하는 CPU 안의 장치를 이용해 메모리에 접근했다. (논리주소/물리주소에 자세히 알고 싶으면 아래 링크 참조) [운영체제 OS]Address Binding 주소 할당, 주소 바인딩, 논리적 주소(logical) vs 물리적 주소(physical), 컴 [운영체제 목차] 안녕하세요~!! ㅎㅎㅎ 메모리 관련 문의글이 많아, 가장 기초적인 주소 할당부터, 그 종류, 페이징, 캐시메모리...쪽을 한번 먼저 쭉 다뤄볼까해요 ㅎㅎ 요새 기다려주시는 사람 jhnyang... 2023. 5. 2. [운영체제] 교착상태와 은행원 알고리즘 교착상태 Dead Lock 프로세스들이 서로의 자원을 기다리며 무한히 기다리는 현상이다. 아래 4개 조건이 성립할 때 교착상태가 발생한다. 비선점 Non-Preemption : 자원을 선점하지 않음 환형대기 Circular Wait : 원형으로 꼬리물기처럼 대기 중 상호배제 Mutual Exclusion : 자원은 하나의 프로세스만 점유 가능 점유 대기 Hold and Wait : 자원을 점유하고 있으면서 추가로 다른 자원을 기다리고 있는 상태 교착상태 처리하기 예방 Prevention 상호배제 부정 : 여러 프로세스가 공유 자원 사용 점유대기 부정 : 프로세스 실행전 모든 자원을 할당 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납 순환대기 부정 : 자원에 고유번호 할.. 2023. 5. 1. 이전 1 2 3 4 5 6 7 다음
