전체 글
디스크 스케쥴링(Disk scheduling) - FCFS,SSTF, SCAN
1. 디스크 스케쥴링 디스크 접근 시간은 Seek time + rotational delay + transfer time 의 합이다. 이때 다음 실린더를 탐색하는 시간(seek time)이 가장 오래 걸린다. 다중 프로그래밍 환경 다중 프로그래밍 환경에서 디스크 큐(disk queue)에는 많은 요청(request) 들이 쌓여있다. 프로세스들이 디스크로 계속해서 읽기, 쓰기 요청을 하기 때문이다. 이러한 요청들을 어떻게 처리해야 탐색시간을 줄일 수 있을까? 2. 디스크 스케쥴링 알고리즘 1) FCFS Scheduling FCFS는 First-Come First-Served의 약자로 먼저 들어온 요청을 먼저 처리하는 방법이다. 가장 단순하며 공정한 방법이다. 예제 200 cylinder disk, 0 ....
파일 할당(File Allocation)
컴퓨터 시스템 자원 관리 - CPU : 프로세스 관리 (CPU 스케쥴링, 프로세스 동기화) - 주기억장치 : 메인 메모리 관리 (페이징, 가상 메모리) - 보조기억장치 : 파일 시스템 보조기억장치 (하드디스크) - 하드디스크 : track(cylinder), sector - Sector size = 512 bytes, cf.Block size 하드디스크의 섹터 사이즈는 보통 512bytes 이며 이 섹터들을 모아 블록 단위로 헤더가 읽는다. - 디스크 = pool of free blocks => 각각의 파일에 대해 free blcok을 어떻게 할당해줄까? 효과적으로 하드디스크 용량을 관리하는 것과 파일 탐색 및 읽는 시간을 모두 고려해야 한다! 1. 파일 할당 방법 1) 연속 할당 연속 할당이란 각 파일..
프레임 할당 (Allocation of Frames)
1. 쓰레싱(Thrashing) 1) CPU utilization vs Degree of multiprogramming CPU 이용률 vs 메인메모리에 올라와있는 프로세스의 개수 일반적으로 프로세스의 개수가 증가하면 CPU 이용률이 증가한다. CPU가 노는 시간이 줄어들기 때문이다. 그러나 프로세스가 일정 범위를 넘어서면 CPU 이용률이 감소하게 된다. 이러한 현상을 Thrashing이라 한다. 2) 쓰레싱 극복 Thrashing이 일어나는 이유는 빈번한 page in/out 때문이다. 프로세스가 늘어나면서 i/o 시간이 증가하기 때문에 CPU 이용률이 급격히 감소하는 Thrashing 이 발생하게 된다. 쓰레싱을 극복하기 위한 방법은 여러가지가 있다. 1) Global replacement 대신 loc..
페이지 교체 알고리즘 - FIFO, OPT, LRU
1. 페이지 교체 1) 요구 페이징(Demand Paging) 요구되어지는 페이지만 backing store 에서 메모리로 가져온다. 프로그램이 계속 실행되면서 요구 페이지가 늘어나고, 언젠가는 메모리가 가득 차게 된다. => Memory full! 메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아내고(page-out) 그 빈 공간으로 페이지를 가져온다.(page-in) 용어 : victim page ; victim이란 말은 희생양 이라는 뜻이다. 즉, 페이지 교체를 위해 backing store로 쫓겨난 페이지를 말한다. 2. Victim Page 페이지 교체를 위해 어느 페이지를 몰아낼 것인가? => i/o 시간 절약을 위해 기왕이면 modify 되지 않..
가상메모리와 요구페이징
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인 지점이 큐를..