[워밍업 클럽 3기 CS 전공지식] 자료구조와 알고리즘 특별 미션

문제실수로 워밍업 클럽 출석을 빼먹었는데 우연히 데이터를 수정할 수 있는 권한이 주어졌습니다. 러너분의 이름(name)과 출석수(count)가 저장된 배열에서 여러분(나)의 데이터를 퀵정렬을 이용해 오름차순 정렬하고 가장 첫 번째 데이터인 여러분의 출석수를 변경하도록 코드를 작성해주세요. (퀵정렬 구현 부분도 변경)// 퀵소트 구현 부분...(생략) let user1 = { name: "홍길동", count: 5 }; let user2 = { name: "임꺽정", count: 4 } let user3 = { name: "이순신", count: 3 } let user4 = { name: "나", count: 1 } let user5 = { name: "짱구", count: 5 } let arr = [user1, user2, user3, user4, user5] console.log("===== 정렬 전 ====="); console.log(arr); quickSort(arr, 0, arr.length - 1); console.log("===== 정렬 후 ====="); console.log(arr);예상 결과===== 정렬 전 ===== [ { name: '홍길동', count: 5 }, { name: '임꺽정', count: 4 }, { name: '이순신', count: 3 }, { name: '나', count: 1 }, { name: '짱구', count: 5 } ] ===== 정렬 후 ===== [ { name: '나', count: 5 }, { name: '이순신', count: 3 }, { name: '임꺽정', count: 4 }, { name: '홍길동', count: 5 }, { name: '짱구', count: 5 } ] 문제 해결[깃허브 코드 - Java로 작성]이전에 작성한 퀵소트 정렬 코드 참고하기다른 점숫자 배열이 아닌 객체 배열을 만들어야 한다.객체 배열 안에서 count 로 오름차순을 한다.첫 번째 해결 - count로 오름차순하기name과 count를 함께 저장할 수 있는 Runner 클래스 생성이전 코드에서 int[] 배열 대신 Runner[] 배열로 변경package sectionThree.quickSort.specialMission; public class Runner { private String name; private int count; public Runner(String name, int count) { this.name = name; this.count = count; } public int getCount() { return count; } @Override public String toString() { return "{name: '" + name + "', count: " + count + '}'; } }package sectionThree.quickSort.specialMission; import java.util.Arrays; public class QuickSortMission { public static void quickSortM(Runner[] runners, int left, int right) { if (left = runners[leftStartIndex].getCount()) { leftStartIndex++; } while (rightStartIndex >= (left + 1) && pivot 결과===== 정렬 전 ===== [{name: '홍길동', count: 5}, {name: '임꺽정', count: 4}, {name: '이순신', count: 3}, {name: '나', count: 1}, {name: '짱구', count: 5}] ===== 정렬 후 ===== [{name: '나', count: 1}, {name: '이순신', count: 3}, {name: '임꺽정', count: 4}, {name: '홍길동', count: 5}, {name: '짱구', count: 5}] 두 번째 해결 - 가장 첫 번째 데이터인 여러분의 출석수를 변경3번 코드에서 추가한 부분quickSortM()을 호출하고 모든 재귀 함수 호출이 끝난 시점인 if 가 필요Runner 클래스에서 setCount() 을 호출해서 변경최소/최대 참여수는 불변값으로 변수 선언문제점이 있다. 5번에서 해결하기package sectionThree.quickSort.specialMission; public class Runner { private String name; private int count; private static final int MIN_CHECK = 0; // 최소 참여수 private static final int MAX_CHECK = 5; // 최대 참여수 public Runner(String name, int count) { this.name = name; this.count = count; } public int getCount() { return count; } public void setCount(int count) { if (!(MIN_CHECK package sectionThree.quickSort.specialMission; import java.util.Arrays; public class QuickSortMission { public static void quickSortM(Runner[] runners, int left, int right) { if (left = runners[leftStartIndex].getCount()) { leftStartIndex++; } while (rightStartIndex >= (left + 1) && pivot 결과===== 정렬 전 ===== [{name: '홍길동', count: 5}, {name: '임꺽정', count: 4}, {name: '이순신', count: 3}, {name: '나', count: 1}, {name: '짱구', count: 5}] ===== 정렬 후 ===== [{name: '나', count: 5}, {name: '이순신', count: 3}, {name: '임꺽정', count: 4}, {name: '홍길동', count: 5}, {name: '짱구', count: 5}] 두 번째 해결 이어서 - 가장 첫 번째 데이터인 여러분의 출석수를 변경현재 코드결과는 예상 결과처럼 잘 나온다.그런데 피벗을 기준으로 정렬할 때마다 Runner[] 첫 번째 배열의 count가 5로 변경된다.정렬 도중에 여러 번 첫 번째 요소의 값을 변경할 가능성이 있어서 의도한 대로 동작하지 않을 수 있다.내가 원했던 로직모든 정렬이 끝난 후 Runner[] 첫 번째 배열의 count가 5로 변경된다.해결 방법quickSortM() 함수 종료 후 main() 함수에서 runners[0].setCount(5); 진행 - 강사님 픽quickSortM() 에 depth 변수를 추가해서 정렬 후 0 depth인 경우에 runners[0].setCount(5); 를 진행해결 방법 2번으로 진행해보자package sectionThree.quickSort.specialMission; import java.util.Arrays; public class QuickSortMission { public static void quickSortM(Runner[] runners, int left, int right, int depth) { if (left = runners[leftStartIndex].getCount()) { leftStartIndex++; } while (rightStartIndex >= (left + 1) && pivot 결과===== 정렬 전 ===== [{name: '홍길동', count: 5}, {name: '임꺽정', count: 4}, {name: '이순신', count: 3}, {name: '나', count: 1}, {name: '짱구', count: 5}] ===== 정렬 후 ===== [{name: '나', count: 5}, {name: '이순신', count: 3}, {name: '임꺽정', count: 4}, {name: '홍길동', count: 5}, {name: '짱구', count: 5}]

[워밍업 클럽 3기 CS 전공지식] 3주차 자료구조와 알고리즘 미션

지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘장점이해가 쉽고 구현이 간단합니다. 단점O(n^2) 으로 성능이 좋지 않습니다.시간 복잡도이중 for문이 핵심 로직으로 O(n^2) 입니다.선택 정렬정렬된 영역과 정렬되지 않은 영역을 나눠서 정렬되지 않은 영역을 비교하는 알고리즘장점이해가 쉽고 구현이 간단합니다. 단점O(n^2) 으로 성능이 좋지 않습니다.시간 복잡도이중 for문이 핵심 로직으로 O(n^2) 입니다.삽입 정렬정렬되지 않은 영역에서 데이터(가장 앞에 있는 숫자)를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘장점이해가 쉽고 구현이 간단합니다. 단점O(n^2) 으로 성능이 좋지 않습니다.시간 복잡도이중 for문이 핵심 로직으로 O(n^2) 입니다.병합 정렬재귀를 이용해 정렬하는 알고리즘 (분할 정복) 장점 O(nlogn) 으로 성능이 좋습니다. 단점재귀적인 기법으로 이해하기 어렵습니다.구현이 어렵다.시간 복잡도각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 logn분할된 배열을 병합할 때는 n개의 데이터를 n번 비교=> n, nlogn 곱해서 O(nlogn) 성능이 나옵니다.퀵 정렬재귀를 이용해 정렬하는 알고리즘 (분할 정복)한 번 진행될 때마다 피벗이 정렬되고 정렬된 배열을 좌우로 나눠서 같은 방식으로 재귀 호출을 해 모든 배열을 정렬합니다. 장점 O(nlogn) 으로 성능이 좋습니다. 단점재귀적인 기법으로 이해하기 어렵습니다.구현이 어렵습니다.시간 복잡도피벗을 기준으로 반을 나눕니다. -> 수가 1개 남을 때까지 반으로 나눕니다. logn나눠진 단계를 배열의 원소 수 n만큼 진행=> n, nlogn 곱해서 O(nlogn) 성능이 나온다. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.재귀로 쉽게 구현이 가능하다고 했으니 먼저 메모이제이션을 이용해서 문제를 해결할 거 같습니다.구현을 하고 실행했을 때 메모리를 어느 만큼 사용하는지 측정해보고 계속 사용할 지 판단하겠습니다.메모제이션으로 구현을 했는데 메모리가 부족하다면 그 때 타뷸레이션을 이용해 문제를 해결하겠습니다. ※ 출처[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 6~10)]

[워밍업 클럽 3기 CS 전공지식] 3주차 운영체제 미션

메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터 가장 빠른 기억 장소 CPU 내에 존재합니다.컴퓨터의 전원이 꺼지면 데이터가 사라지기 때문에 휘발성 메모리라고 부릅니다.캐시레지스터와 메인메모리의 속도 차이를 해결해줍니다.메인메모리에 있는 값을 레지스터로 옮기려면 한참 걸리기 때문에 필요할 것 같은 데이터를 미리 가져옵니다.메인메모리운영체제와 다른 프로세스들이 올라가는 공간입니다.전원이 공급되지 않으면 데이터가 지워지기 때문에 휘발성 메모리라고 부릅니다.하드디스크(HDD)나 SSD 보다 속도는 빠르지만 가격이 비싸서 데이터를 저장하기 보다는 실행 중인 프로그램만 올립니다.보조저장장치 (HDD, SSD)사무용 프로그램이나 게임, 작업한 파일을 저장할 때 필요합니다.메인메모리에 비해 가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리 입니다.메모리에 접근하는 시간이 보조저장장치 쪽으로 갈수록 느려집니다. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터CPU 내에 존재하는 레지스터로 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지검사하고 만약 벗어났다면 해당 프로세스를 종료 시킵니다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식장점메모리에 연속된 공간에 할당되기 때문에 낭비되는 공간이 없습니다. (내부 단편화가 없습니다.)프로세스 크기에 딱 맞게 할당됩니다.단점'외부 단편화'가 발생합니다.프로세스가 사용한 메모리를 반납 후 다른 프로그램이 메모리를 사용하려고 할 때반납된 메모리 2개 영역을 합치면 다른 프로그램이 메모리를 사용할 수 있는데 연속되지 않은 메모리 공간이라서 사용하지 못합니다.고정 분할 장식장점구현이 간단하고 오버헤드가 적습니다.같은 크기로 나누기 때문에 단순합니다.단점작은 프로세스도 큰 영역에 할당되어서 공간이 낭비되는 '내부 단편화'가 발생합니다. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱해결 방법하드웨어적으로 해결메모리 크기를 늘립니다.소프트웨어적으로 해결프로세스가 실행되면 일정량의 페이지가 할당됩니다.Page Fault 가 발생하면 더 많은 페이지를 할당합니다.Page Fault 가 너무 적게 발생하면 메모리가 낭비되는 것이라고 판단해 페이지를 회수합니다.=> 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정됩니다. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?이유를 함께 적어주세요.필요하다고 생각합니다.컴퓨터가 부팅되면 HDD나 SSD에 저장되어 있는 운영체제가 메모리에 올라오게 됩니다.만약에 운영체제 없이 컴퓨터만 실행 한다면 필요 없을 수도 있습니다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?특정 파일을 삭제할 때 파일 시스템은 파일의 모든 정보를 지우는 것이 아닙니다.파일 테이블의 헤더를 삭제하고 free block list에 추가를 합니다.이렇게 처리하면 사용자는 파일이 삭제된 것처럼 느껴지지만 사용했던 블록의 데이터는 그대로 남아있습니다.그래서 데이터를 복구할 수 있습니다. ※ 출처[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 8~10]

[워밍업 클럽 3기 CS 전공지식] 3주차 회고

[3 주차 시작하기 전 다짐]아침에 일어나서 주어진 강의 분량을 다 듣기틈날 때 강의 듣기저녁에 집에 와서 다시 듣기 또는 실습 진행강의 들으면서 강의 노트도 실시간으로 작성하기! 강의 노트 작성 후 당일에 정리하기 [3 주차 회고]칭찬할 점스터디 계획에 맞춰서 모든 강의를 들었다.=> 뿌듯하다.아쉬운 점 강의를 듣고 정리를 하는 것이 어려웠다.모든 내용이 다 중요해 보이고 알아야 하지 않을까 라는 생각에 내용 정리라고 하기에는 모든 내용을 적기만 했다.=> 강의를 듣고 어떻게 정리해야 할 지 고민을 해봐야겠다.역시 한 번 듣고 이해하는 건 어렵다. 반복해서 들어야 한다.=> 스터디가 끝나고 나서도 반복해서 강의를 들어야겠다. [강의 내용 정리][운영체제][가상메모리]가상메모리 개요 (한 번 더 정리하기) - 부족한 물리메모리를 가상메모리를 이용해서 해결하는 방법 운영체제나 프로세스가 4GB 메모리에서 동작하도록 만들어졌다면 이보다 작은 메모리를 가진 컴퓨터는 실행되지 않는다.이런 문제를 '가상메모리'는 완벽하게 해결했다.프로세스는 물리메모리에 직접 접근할 일이 없고 메모리 관리자(MMU)에게 요청만 하면 된다.메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시켜 준다.가상메모리 시스템은 저장 공간보다 많은 프로세스가 있을 경우물리메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리메모리로 가져와 실행시킨다.동적 주소 변환(Dynamic Address Translation)메모리 관리자는 물리메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주소를 물리 주소로 변환한다.동적 주소 변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리메모리에 배치할 수 있다.가상메모리 시스템에서는 운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당메모리 분할 방식과 마찬가지로 가변 분할 방식과 고정 분할 방식으로 나뉜다.가변 분할 방식가상메모리 시스템에서는 가변 분할 방식을 이용한 세그멘테이션단점외부 단편화가 있다.고정 분할 방식고정 분할 방식을 이용한 페이징단점내부 단편화가 있다.이 단점들을 보완한 '세그멘테이션-페이징 혼용' 기법을 사용한다.가상 메모리 시스템에서 가상 주소는 메모리나 스왑 영역 한 곳 중에 위치메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리 [가상메모리가 메모리 분할하는 방법] - 가상메모리가 메모리를 어떻게 분할하는지 알아보자세그멘테이션(배치정책) 가변 분할 방식 이용프로그램은 함수나 모듈 등으로 세그먼트를 구성논리 주소사용자와 프로세스, CPU가 바라보는 주소물리 주소로 변환은 중간에서 메모리 관리자가 해준다.메모리 관리자가 논리 주소를 물리 주소로 변환해주는 방법메모리 관리자는 세그멘테이션 테이블이라는 것을 가진다.세그멘테이션 테이블Base Address 와 Bound Address 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산한다. CPU에서 논리 주소를 전달해주면 메모리 관리자는 해당 논리 주소가 몇 번 세그먼트인지를 알아낸다.메모리 관리자 내에 Segment Table Base Register(물리메모리n번지에 저장되어 있음, CPU를 사용하고 있는 프로세스의 물리주소값?이 저장되어 있음) 이용해서 물리메모리 내에 있는 세그멘테이션 테이블을 찾는다.세그먼트 번호를 인덱스로 Base Address 와 Bound Address 를 찾는다.Bound Address 는 세그먼트의 크기를 나타낸다.메모리 관리자는 CPU에서 받은 논리 주소와 Bound Address 의 크기를 비교한다.if (논리 주소 else if (논리 주소 > Bound Address) 메모리를 침범했다고 생각하고 에러를 발생시킨다.장점메모리를 가변적으로 분할할 수 있다.코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있기 때문에 공유와 각 영역에 대한 메모리 접근 보호가 편리하다.단점가변 분할 방식의 단점인 '외부 단편화'가 발생한다.페이징(배치정책)고정 분할 방식을 이용한 페이징세그멘테이션의 단점인 '외부 단편화'를 해결하기 위해 고안되었다. -> 조각모음은 오버헤드가 크다.메모리를 할당할 때 정해진 크기의 페이지로 나눈다.장점모든 페이지는 크기가 같기 때문에 관리가 쉽다.일정한 크기로 나눴기 때문에 외부 단편화 현상이 일어나지 않는다.단점'내부 단편화' 발생한다.논리 주소 공간사용자와 프로세스가 바라보는 주소 공간페이징에서는 논리 주소 공간을 일정한 크기로 균일하게 나눈다.이것을 '페이지'라고 부른다.물리 주소 공간실제 메모리에서 사용되는 주소 공간페이지의 크기와 동일하게 나뉘는데 '프레임'이라고 부른다.페이징에서 주소 변환을 어떻게 하는지 알아보자세그멘테이션과 마찬가지로 메모리 관리자는 테이블을 가지고 있다.이를 '페이지 테이블'이라고 부른다.페이징의 주소 변환 1. CPU에서 논리 주소를 전달2. 메모리 관리자는 논리 주소가 몇 번 페이지인지, 오프셋은 얼마인지 알아낸다.3. 메모리 관리자 내에 Page Table Base Register(PTBR)를 이용해서 물리메모리에 있는 페이지 테이블을 찾는다.4. 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리주소로 변환한다.오프셋은 계산을 통해 쉽게 구할 수 있다.페이지 테이블에 Invalid 로 표시되어 있으면 스왑 영역, 즉 하드디스크에 저장되어 있다는 의미이다.5. 세그멘테이션과 마찬가지로 Page Table Base Register 는 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해준다.세그멘테이션과 페이징 차이점페이지 크기세그멘테이션프로세스마다 크키가 달라 Bound Address 를 가지고 있다.외부 단편화 발생한다.페이징모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address는 필요하지 않다.외부 단편화는 발생하지 않지만 내부 단편화가 발생한다.페이지 크기 때문에 생긴 차이세그멘테이션논리적인 영역별로 세그먼트를 나눈다.세그먼트마다 크기를 다르게 나눌 수 있으니 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다. 페이징페이지의 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라페이지로 나누기 때문에 논리적인 영역을 나눌 수 없다.특정 영역만 딱 떼어내서 공유하거나 권한을 부여하는 게 어렵다.페이징에서 신경써야 할 것각 프로세스마다 페이지 테이블을 가지고 있다.프로세스가 많아질수록 페이지 테이블도 많아지기 때문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.메모리 관리자가 참조하는 페이지 테이블도 물리메모리의 운영체제 영역에 저장되어 있기 때문에페이지 테이블의 크기가 너무 크면 사용자 영역이 부족하게 된다.때문에 페이지 테이블의 크기를 적절하게 유지하는 것이 중요하다. 페이지드 세그멘테이션(배치정책)세그멘테이션과 페이징을 혼합해 장점을 취한 방식세그멘테이션 장점가변 분할 장식으로 코드, 데이터, 스택, 힙 영역을 세그먼트로 관리할 수 있다.다른 프로세스와 공유하기 편하고 각 영역에 대한 메모리 접근 보호를 하기 쉽다.페이징 장점고정 분할 방식으로 메모리를 효율적으로 관리할 수 있다.오버헤드가 적다.메모리 접근 권한메모리의 특정 번지에 부여된 권한읽기(Read), 쓰기(Write), 실행(Execute) 세 가지가 있다.예시0x0~0x1000까지는 읽기 권한만 설정0x1000~0x2000까지는 읽기, 쓰기 권한 설정프로세스 영역마다 접근 권한이 있다.코드 영역 : 읽기/실행 권한프로그램 그 자체이므로 수정되면 안된다.데이터 영역 : 읽기/(쓰기) 권한일반 변수, 전역 변수, 상수로 선언한 변수가 저장된다.실행 권한은 없다.스택, 힙 영역 : 읽기/쓰기 권한실행 권한은 없다.메모리 접근 권한에 대한 검사가상주소에서 물리주소로 변환될 때마다 일어난다.권한을 위반하면 에러를 발생 시킨다.테이블 구성세그멘테이션 테이블에 권한 비트 추가Base Address는 페이지 넘버로 변경 (페이지 테이블의 인덱스를 가리킴)Bound Address는 페이지 개수로 바뀜페이지 테이블은 프레임 번호로 구성단점물리메모리에 접근하기 위해서 메모리에 접근을 두 번해야 한다.첫 번째 메모리 접근은 세그멘테이션 테이블을 참조두 번째 메모리 접근은 페이지 테이블을 참조이런 단점 때문에 현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 사용한다. 메모리 계층 구조메모리는 레지스터, 캐시, 메인메모리(RAM), 보조저장장치(HDD, SSD) 로 나눌 수 있다.레지스터CPU 내에 존재하고 CPU의 한 사이클에 접근할 수 있어서 빠르다.캐시CPU의 수 사이클에서 수십 사이클에 접근할 수 있다.메인메모리수백 사이클이 걸린다.보조저장장치수백만 사이클이 걸려 오래 걸린다.메모리에 접근하는 시간이 보조저장장치 쪽으로 갈수록 느려진다. 디맨드 페이징(가져오기 정책)프로세스가 실행될 때 모든 모듈(코드, 데이터, 힙, 스택 영역)이 메모리에 올라오는 것이 아니라 필요한 모듈만 올라와서 실행된다.조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑 영역으로 이동시키는 정책이다.=> 지역성 이론을 구현한 정책지역성 이론조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능을 향상시킨다.스왑 영역을 보조저장장치에 저장하는데 성능 향상을 위해서는 스왑 영역으로 데이터를 이동시키는 것을 최소화해야 한다.보조저장장치에 접근하는 건 최대한 적을 수록 좋다.스왑 영역에서 물리메모리로 데이터를 가져오는 것을 스왑인이라고 부른다.물리메모리에서 스왑영역으로 데이터를 보내는 것을 스왑아웃이라고 부른다.페이지 테이블가상주소가 주어지면 메모리 관리자는 페이지 테이블을 참조해서 물리메모리가 있는 프레임을 알아내거나 스왑영역의 위치를 알아내야 하는데 이를 위해 페이지 테이블에 여러가지 비트가 있다.접근 비트페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트메모리에 읽거나 실행 작업을 했다면 1로 바뀐다.변경 비트페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트메모리에 쓰기 작업을 했으면 1로 바뀐다.유효 비트페이지가 물리모리에 있는지 알려주는 비트1이라면 페이지가 스왑 영역에 있고 0이라면 물리메모리에 있다.권한 비트읽기/쓰기/실행해당 메모리에 접근 권한이 있는지 검사하는 비트프레임가상 메모리 주소가 물리메모리와 스왑영역에 참조되는 세 가지 상황1. 스왑이 필요없는 경우페이지가 물리메모리에 있다.2. 스왑 영역에 있는 데이터를 참조하는 경우페이지가 스왑영역에 있다는 뜻그럼 물리메모리에 적절히 빈 공간을 찾는다.스왑 영역에 저장된 것을 물리메모리 프레임으로 가져오고페이지 테이블에서 해당 엔트리의 유효비트를 0으로 프레임 넘버를 수정한다.그리고 프로세스에게 데이터를 참조하게 해준다.3. 물리메모리가 꽉 찼을 때 스왑 영역에 있는 데이터를 참조하는 경우페이지가 스왑영역에 있다는 뜻물리메모리로 가져오기 위해 적절히 빈 곳을 찾지만 꽉 차서 여유가 없다.그럼 현재 물리메모리에서 필요하지 않다고 판단하는 영역을 스왑 영역으로 옮긴다.물리메모리에 필요없는 영역을 스왑영역으로 옮기면 페이지 테이블에서 해당 영역의 유효 비트를 1로, 프레임 넘버를 변경한다.이제 물리메모리에 공간이 생겼기 때문에 스왑 영역에 있는 필요한 영역을 물리메모리로 가져온다.페이지 테이블에서 옮겨온 영역의 유효비트를 0으로 프레임 넘버를 수정한다.그리고 프로세스에게 데이터를 참조하게 해준다. 페이지 교체정책스왑 영역에서 물리메모리로 가져오는 스왑인과 물리메모리에서 스왑영역으로 보내는 스왑아웃을 할 때 어떤게 적절한 지는 운영체제가 판단한다.이 판단하는 것을 페이지 교체 알고리즘이라고 부르고 페이지 교체 알고리즘에 대해서는 알아보자.메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 보낼 지 결정하는 페이지 교체 정책첫 번째 : 무작위로 선택무작위로 선택해서 교체지역성을 고려하지 않기 때문에 자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다.거의 사용되지 않는다.두 번째 : 메모리에 들어온 지 가장 오래된 페이지를 선택하는 방법FIFO(First In First Out)자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지가 교체되면 공평하지 않다.구현이 간단하고 성능도 괜찮아서 조금 변형해서 많이 쓰인다.세 번째 : 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법Optimum사실상 구현이 불가능한 이론적인 선택하는 방법앞으로 누가 가장 사용되지 않을지 모른다.구현이 불가능해서 필요 없을 것 같지만 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰인다.네 번째 : 최근에 가장 사용이 적은 페이지를 선택하는 방법LRU(Least Recently Used)Optimum 알고리즘에 근접한 성능을 보인다.페이지 테이블 엔트리는 여러 개의 비트와 페이지 넘버가 저장되지만 이곳에 시간을 기록하려면 비트가 많이 필요하게 된다.많은 비트를 준비하기는 어려우니 LRU를 구현할 때는 접근 비트를 이용해서 LRU에 근접하게 구현한다.Page Fault 발생메모리에 페이지가 없고 스왑 영역에 페이지가 있는 경우Optimum이후에 어떤 요청이 있는지 전부 알고 있기 때문에 뒤를 훑어본다.FIFO먼저 들어온 페이지가 먼저 나간다.LRU최근에 가장 사용이 적은 페이지가 나간다.최근에 들어온 페이지의 참조 수를 계산한다.LRU 와 유사하게 구현하는 방법 - 클락 알고리즘(Clock Algorithm)클락 알고리즘은 접근 비트 하나만 이용한다.일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화한다.접근 비트의 초기값은 0으로 설정되어 있다.만약 페이지가 참조되었다면 1로 설정된다.그럼 일정 시간 간격마다 페이지가 참조 되었는지 참조되지 않았는지 확인할 수 있다.클락 알고리즘은 페이지를 원형으로 연결한다.스왑영역으로 옮길 페이지를 포인터로 가리키는데 이 포인트를 '클락 핸드'라고 부른다.클락 핸드는 시계 방향으로 돈다.만약 Page Fault 가 발생해서 스왑영역으로 보내야하는 상황이 나오면 클락 핸드는 현재 참조하고 있는 페이지의 접근 비트를 본다.만약 접근비트가 1이라면 해당 접근비트를 0으로 바꾸고 클락핸드가 다음 페이지를 가리킨다.반복하다가 접근비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.메모리에서 접근비트가 0인 페이지를 스왑영역으로 보냄2차 기회 페이지 교체 알고리즘FIFO 방식에서 자주 사용하는 페이지에게 또 한 번의 기회를 준다.FIFO 방식과 동일하게 동작하지만 만약 Page Fault 없이 페이지 접근에 성공했다면해당 페이지를 큐의 맨 뒤로 이동 시켜 수명을 연장 시켜주는 방식이다.LRU 보다는 성능이 좋지 않고 FIFO 보다는 성능이 좋다. [스레싱과 워킹셋]스레싱CPU 사용률을 높이려고 했지만 더 떨어지는 상황멀티 프로그래밍 정도(동시에 실행하는 프로세스의 수)가 늘어나면 제한된 물리메모리에 모든 프로세스를 올려야 하고 당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑 영역에 저장되고 Page Fault 가 많이 발생한다.그러면 CPU 가 작업하는 시간보다 스왑 작업의 시간이 더 길어지고 CPU 사용률은 떨어진다.CPU 스케줄러는 CPU 사용률이 낮아지면 더 많은 프로세스를 메모리에 올리게 되고 프로세스를 더 실행시켜 CPU 사용률을 올린다.이렇게 반복하다 보면 어느새 CPU 사용률이 0에 가깝게 떨어진다.근본적인 원인은 물리메모리의 크기가 부족한 것이다.하드웨어적으로 해결메모리 크기를 늘린다.소프트웨어적으로 해결프로세스가 실행되면 일정량의 페이지를 할당Page Fault 가 발생하면 더 많은 페이지를 할당Page Fault 가 너무 적게 발생하면 메모리가 낭비되는 것이라고 판단해 페이지를 회수프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정됨적절한 페이지 수를 결정했다면 어떤 페이지들을 유지할 것인지 알아야 한다.지역성 이론을 따른다.현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올린다.이를 워킹셋이라고 부른다.워킹셋은 프로세스가 준비 상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용한다. [입출력 장치]주변장치(I/O 디바이스, 저장장치)그래픽 카드, 하드디스크, SSD, 키보드, 마우스 등이 여러 가지가 있다.주변 장치 내부구조주변 장치들은 메인보드에 있는 버스로 연결한다.하나의 버스는 Address 버스와 Data 버스, Control 버스로 이루어져 있다.장치의 상태와 데이터를 보관할 수 있는 각종 레지스터들이 존재한다.이 레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할을 한다.CPU가 사용하기 위해 메모리로 이동하기도 한다.주변 장치 2가지데이터의 전송 단위가 캐릭터(글자), 블록으로 나눈다.캐릭터 디바이스마우스, 키보드, 사운드 카드, 직렬/병렬 포트 등이 있다.데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작다.상대적으로 적은 양의 데이터를 전송한다.블록 디바이스하드디스크, SSD, 그래픽 카드 등이 있다.데이터 전송 단위가 블록(범위)으로 상대적으로 크기가 크다.많은 양의 데이터를 전송한다.입출력 제어기(I/O Controller)CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 실행한다.입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분한다.시스템 버스고속으로 작동하는 CPU와 메모리가 사용한다.그래픽 카드대용량 데이터로 고속 입출력 버스로 감당이 안된다.입출력 버스에 있지 않고 시스템 버스에 바로 연결해 사용한다.입출력 버스주변장치가 사용한다.세부적으로 느린 장치와 빠른 장치를 구분하기 위해 고속 입출력 버스와 저속 입출력 버스가 있다.느린 장치와 빠른 장치를 구분해 속도 차이로 인한 병목 현상을 해결했다. 하드디스크/Flash Memory(SSD)주변 장치 중 블록 디바이스의 한 종류 하드디스크기계적으로 헤드를 움직여 속도가 많이 느리고 소음이 난다.자기적으로 처리해서 자석을 가져다 대면 데이터가 손상된다.스핀들처럼 회전축 같은 것들이 있어서 충격에 매우 약하다.블록 디바이스의 또 다른 종류 SSD하드디스크보다 Flash Memory를 더 많이 사용한다.전기적으로 읽기 때문에 굉장히 빠르고 조용하다.충격에 약하지 않다.데이터 손상이 되지 않는다.단점특정한 지점에 데이터를 썼다면 덮어쓰기가 불가능하다.똑같은 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야하는데지우기 가능한 횟수가 정해져 있다.똑같은 지점에 지우기/쓰기를 계속하면 망가져 사용할 수 없다. [파일 시스템]파일과 파일시스템파일은 하드디스크나 SSD와 같은 저장장치에 저장된다.사용자가 운영체체를 통해 요청하면 운영체제가 안전하게 저장해준다.운영체제는 파일을 관리하기 위해 파일 관리자를 뒀는데 이를 파일시스템이라고 한다.파일 관리자파일 테이블을 이용해서 파일을 관리한다.파일 시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권한 관리다른 사용자로부터 파일을 보호하기 위해 접근 권한을 관리무결성 보장파일의 내용이 손상되지 않도록 무결성을 보장백업과 복구예기치 못한 사고로부터 백업과 복구암호화파일을 암호화해 파일을 보호파일 시스템 전송 단위 블록하드디스크와 Flash Memory(SSD) 같은 저장 장치에 저장되기 때문에 단위가 블록이다.저장 장치의 전송 단위는 블록이지만 사용자는 바이트 단위로 파일에 접근 한다.이는 파일 관리자가 중간에서 관리해준다.파일헤더와 데이터로 이루어져 있다.헤더에는 파일의 속성들이 담겨져 있다.운영체제는 파일을 관리하기 위해 파일 제어 블록(File Control Block,FCB)에 정보를 보관한다.이를 파일 디스크립터(File Descriptor)라고 부른다.파일 시스템(운영체제)이 관리한다.사용자가 직접 참조할 수 없다.사용자는 파일 시스템이 건네준 파일 디스크립터로 파일에 접근할 수 있다.파일은 데이터의 집합으로 어떻게 구성하느냐에 따라 종류를 나눌 수 있다.순차 파일 구조파일의 내용이 연속적으로 이어진 형태장점모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순하다.단점특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸린다.직접 파일 구조저장하려는 데이터를 해시 함수를 통해 저장 위치를 결정하는 파일 구조자료구조에서 해시 테이블이라는 이름으로 불리는 방식예시: 데이터 포맷인 json장점해시 함수를 이용하기 때문에 데이터 접근이 빠르다.단점해시 함수의 선정이 중요하다.해시 함수를 잘 골라야 한다는 점과 저장 공간이 낭비될 수 있다.인덱스 파일 구조순차 접근과 직접 접근 방식의 장점을 취한 것 -> 두 가지 방식 모두 가능 디렉토리관련 있는 파일을 모아둘 수 있다.1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있다.여러 층으로 구성되어 있다.최상위에 있는 디렉토리를 루트 디렉토리라고 부른다.유닉스나 리눅스의 경우 루트 디렉토리를 "/"로 표시하고디렉토리와 디렉토리 구분을 위해서도 "/"를 사용한다.윈도우즈의 경우 루트 디렉토리는 파티션 이름으로 사용하는데 보통 "C:"로 표시한다.디렉토리와 디렉토리 구분을 "\"로 한다.디렉토리도 파일이다.일반 파일에는 데이터가 저장되어 있다.디렉토리에는 파일 정보가 저장되어 있다.디렉토리 구조초기 파일 시스템의 디렉토리는 단순한 구조루트 디렉토리에만 디렉토리가 존재할 수 있다.다른 디렉토리에서는 하위 디렉토리는 만들 수 없다.파일이 많아지면서 다단계 디렉토리 구조 등장디렉토리에서 하위 디렉토리를 만들 수 있는 트리 구조이다.우리가 쓰는 운영체제는 트리 구조에서 순환이 생긴다.바로가기 기능 때문이다.윈도우즈는 바로가기 아이콘을 만들어 특정 디렉토리에서 다른 디렉토리로 바로 이동하는 기능이 있기 때문에 순환이 있는 트리 구조이다. 파일과 디스크전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당해 관리한다.일정한 크기로 나눈 공간을 파일 시스템에서는 블록이라고 부른다.한 블록의 크기는 1~8KB 이다.파일 시스템은 파일 정보를 파일 테이블로 관리하는데 파일이 시작하는 블록의 위치 정보도 담겨있다.하나의 파일은 여러 개의 블록으로 이루어져 있다.이 블록들을 어떻게 연결하는 지에 따라 "연속할당"과 "불연속할당"으로 나눌 수 있다."연속 할당"파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식파일의 시작 블록만 알면 파일의 전체를 찾을 수 있다.외부 단편화가 발생, 사용되지 않는 방식이다."불연속할당"디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식분산된 블록은 파일 시스템이 관리한다.불연속 방식으로 "연결 할당"과 "인덱스 할당"이 있다."불연속할당(연결할당)"파일에 속한 데이터를 연결리스트로 관리파일 테이블에 시작 블록에 대한 정보만 저장연결리스트를 이용해 다른 블록에 접근하는 방식시작 위치에서 null을 만날 때까지 데이터를 참조하면 모든 데이터를 얻을 수 있다."불연속할당(인덱스할당)"테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아니라데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블을 확장할 수 있다. 디스크일정한 크기의 블록으로 나뉘고 블록의 크기는 1~8KB 이다.디스크를 1KB 로 나누면 낭비되는 공간을 줄일 수 있지만 관리해야 할 블록의 수도 많아진다.8KB 로 나누면 관리해야 하는 블록의 수는 적지만 내부 단편화로 낭비되는 공간이 많아진다.파일 시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있다.특정 파일을 삭제한다면 파일 시스템은 파일의 모든 정보를 지우는 것이 아니다.파일 테이블의 헤더를 삭제하고 free block list에 추가한다.이렇게 처리하면 사용자는 파일이 삭제된 것처럼 느껴지는데 사용했던 블록의 데이터는 그대로 남아있다.범죄를 저질러서 증거를 인멸하더라도 포렌식을 통해 데이터를 복구할 수 있다. [자료구조와 알고리즘][java로 실습한 것은 깃허브에 올려두었다.]정렬 - 삽입정렬동작선택 정렬과 마찬가지로 배열을 두 영역으로 나눠서 진행정렬되지 않은 영역에서 데이터(가장 앞에 있는 숫자)를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘정렬되지 않은 영역의 첫 번째 원소를 정렬된 영역의 가장 뒤에 있는 원소부터 역순으로 비교성능버블정렬, 선택정렬과 같은 패턴 : 이중 for문O(n제곱)장점이해가 쉽고 구현이 간단하다.단점성능이 좋지 않다. 정렬 - 병합정렬해결하기 힘든 문제가 발생한다면 한 번에 해결하려 하지 말고,해결하기 쉬울 정도로 문제를 쪼갠 다음 하나씩 해결 - 분할 정복(divide and conquer)예시 8개 요소를 정렬해야 한다면4개로 반으로 쪼갠다.2개로 반으로 쪼갠다.1개로 반으로 쪼갠다.1개부터 2개로 올라갈 때 정렬을 한다.재귀 함수를 호출한 모양과 비슷하다.병합정렬은 재귀로 정렬하는 알고리즘성능성능을 평가하는 부분은 흩어진 배열을 합치는 부분이다.하나의 데이터와 하나의 데이터가 두 개로 합쳐질 때 비교 연산을 두 번 한다.두 개의 데이터와 두 개의 데이터가 네 개로 합쳐질 때 비교가 네 번 이루어 진다.각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 logn이다.=> 분할된 배열을 병합할 때는 n개의 데이터를 n번 비교하므로 n, nlogn 곱해서 O(nlogn) 성능이 나온다.장점성능은 O(nlogn)으로 지금까지 배운 정렬보다 성능이 훨씬 좋다.단점 재귀적인 기법으로 이해하기 어렵다.구현이 어렵다. 정렬 - 퀵정렬병합정렬과 같이 분할 정복 알고리즘재귀를 사용한다.한 번 진행될 때마다 피벗이 정렬되고 정렬된 배열을 좌우로 나눠서 같은 방식으로 재귀 호출을 해 모든 배열을 정렬한다.동작 전 준비정렬하기 전 배열에 있는 숫자 중 하나를 '피벗'으로 설정피벗 설정은 여러 가지가 있는데 설명은 배열의 가장 왼쪽에 있는 값을 피벗으로 설정배열의 시작과 끝을 가리키는 left 와 right 로 설정피벗을 제외한 배열의 양쪽에서 값을 비교하기 위한 변수 필요왼쪽에서 오른쪽으로 이동하는 변수를 leftStartIndex오른쪽에서 왼쪽으로 이동하는 변수를 rightStartIndex동작1. leftStartIndex가 이동, 오른쪽으로 이동하다가 피벗보다 큰 값을 만나면 멈춘다.2. rightStartIndex가 이동, 왼쪽으로 이동하다가 피벗보다 작은 값을 만나면 멈춘다.3. leftStartIndex 의 값과 rightStartIndex 의 값을 교환해준다. (swap)4. 1~3 반복5. leftStartIndex 와 rightStartIndex 가 서로의 방향으로 이동하다 보면 결국에는 서로 지나치게 된다. 그러면 더이상 이동하지 않고 멈춘다.6. 피벗과 rightStartIndex 의 값을 교환해준다.피벗이 중간에 위치하게 된다.7. 피벗 왼쪽에 있는 배열을 1~6 반복하면 왼쪽의 모든 데이터가 정렬된다.8. 피벗 오른쪽에 있는 배열을 1~6 반복하면 오른쪽의 모든 데이터가 정렬된다.성능피벗을 기준으로 반을 나눈다. -> 수가 1개 남을 때까지 반으로 나눈다.=> logn나눠진 단계를 배열의 원소 수 n만큼 진행평균적인 경우 세타(nlogn)피벗이 매번 배열의 반을 가르는 경우최악의 경우피벗이 중간이 아닌 한쪽으로 치운친 경우 - 피벗이 배열을 반 가르지 않고 한 쪽에 쏠리는 경우O(n제곱)하지만 대부분의 경우 좋은 피벗을 선택하고 최악의 경우가 발생할 확률은 극히 낮다.그래서 평균적인 성능을 말하면 된다.성능만 보면 병합정렬이 더 좋아보이지만 실제로 비교하면 퀵 정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가된다.장점성능은 O(nlogn)으로 지금까지 배운 정렬보다 성능이 훨씬 좋다. 단점재귀적인 기법으로 이해하기 어렵다.구현이 어렵다. 동적 프로그래밍 - 메모이제이션이전에 재귀를 이용해서 큰 문제를 작은 문제로 분할해서 해결했고 이를 분할 정복이라고 했다.하지만 재귀를 사용하면 함수가 호출되어 콜스택의 영역을 차지하는 단점 외에도 성능에 크게 영향을 미치는 단점이 있다.예시피보나치 수열재귀를 이요해서 하향식 계산을 해서 간단하게 문제를 해결할 수 있다.그런데 이미 계산했던 걸 또 다시 계산하는 경우가 발생한다.이 중복 계산으로 인해 낭비되는 시간을 줄여야 한다.계산 결과를 저장하면 된다. 같은 계산이 필요할 때 저장된 결과를 사용하면 된다.그러면 함수의 호출 수가 줄어들고 성능이 향상된다.메모이제이션계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법동작계산하려는 데이터가 있는지 '검색'하고 없다면 함수를 호출해서 계산을 하고 그 결과를 '저장' 시키면 된다.해시 테이블의 자료구조를 사용한다.해시 테이블 장점빠른 데이터 탐색, 삽입, 삭제해시 테이블의 key로 계산하려는 값을, value로 계산 결과를 저장해주면 계산하려는 값의 검색을 아주 빨리 할 수 있다.결과만 보면 재귀, 메모이제이션 성능 차이를 못 느낀다.계산할 값이 커질 수록 엄청나게 차이가 난다.피보나치 재귀 성능 O(2의 제곱)피보나치 메모이제이션 성능 O(n)메모이제이션 기법이 강력하지만 속도를 위해서 메모리(공간)을 사용한다. 동적 프로그래밍 - 타뷸레이션분할 정복을 하기 위해서 하향식 계산 방식인 메모이제이션을 이용했다.메모이제이션 장점재귀적인 기법으로 어려운 문제를 단순히 푼다.계산 결과를 해시 테이블에 저장하고 재사용하기 때문에 속도가 빠르다.메모이제이션 단점함수를 여러 번 호출하는 재귀를 사용하기 때문에 함수 하나를 호출하는 것보다 오버헤드가 더 크다.타뷸레이션상향식 계산 방식으로 계산에 필요하지 않을 수도 있는 값도 미리 계산해 테이블에 저장한다.계산되어 저장된 값을 필요할 때 사용해 빠르게 계산한다.피보나치 구현 비교메모이제이션여러 번의 함수 호출로 메모리 공간에 스택을 차지해시 테이블 공간까지 차지하기 때문에 메모리 더 많이 사용타뷸레이션적은 메모리 사용인데도 빠른 시간으로 해결한다.분할 정복을 해결할 때 재귀가 더 직관적이라면 메모이제이션을 이용하는 것이 유리하다.재귀가 직관적이지 않을 경우 상향식 접근인 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 해결할 수 있다. ※ '강의 내용 정리' 출처[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 8~10][인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 6~10)]

[워밍업 클럽 3기 CS 전공지식] 2주차 자료구조와 알고리즘 미션

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀 함수가 계속 자신을 호출하면서 콜스택에 쌓이게 됩니다.콜스택에 메모리 공간이 가득차서 원하는 결과를 얻지 못하고 자동으로 종료됩니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.코드 작성 전 생각해보기num 이 홀수인지 짝수인지 구하기홀수면 그대로 사용하고 짝수면 num-1 을 하기더해서 결과를 보여줘야 하니 반환되는 값이 필요합니다. (반환 타입 int)이미 해결을 한 상황을 예상해보기 (하위 문제)num + sumOdd(num-2)홀수에서 -2 하면 홀수입니다.기저 조건(탈출 조건)1까지 도달했을 때 더이상 -2로 홀수를 찾아올 수 없으므로 값 그대로 1을 반환합니다.[깃허브 코드 - Java로 작성]public static int sumOdd(int num) { // 기저 조건 (탈출 조건) if (num == 1) return 1; // 처음 들어온 num 이 짝수인 경우 -1로 홀수 만들어주기 if (num%2==0) num = num - 1; return num + sumOdd(num - 2); } public static void main(String[] args) { System.out.println(sumOdd(10)); // 25 } 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.변경 전[깃허브 코드 - Java로 작성]import java.io.File; import java.util.Stack; public class FileSearch { public static void traverseDirectory(String dir) { File startDir = new File(dir); Stack stack = new Stack(); // 순회해야 할 디렉토리를 저장할 스택 File[] startFiles = startDir.listFiles(); // 인자로 주어진 경로의 디렉토리에 있는 파일 or 디렉토리들 for (int i = 0; i 변경 후코드 작성 전 생각해보기유효성 검사traverseDirectory() 에 매개변수 dir문자열로 받아와서 값이 null 이거나 빈문자열인지 확인파일로 만든 후에 '디렉토리가 있는지 파일이 있는지' 확인traverseDirectory() 안에서 출력하므로 반환없이 void로 설정이미 해결을 한 상황을 예상해보기 (하위 문제)dir 에서 파일, 디렉토리 리스트를 가져오기for문을 반복하면서if 디렉토리면 경로 출력 및 traverseDirectory() 호출else 파일이면 경로 출력기저 조건(탈출 조건)files로 디렉토리에 있는 파일 및 디렉토리를 for문으로 모두 순회하면 자연스럽게 함수를 종료합니다.[깃허브 코드 - Java로 작성]import java.io.File; public class FileSearchRecursion { public static void traverseDirectory(String dir) { if (dir == null || dir.isEmpty()) return; File startDir = new File(dir); if (!startDir.exists()) { System.out.println(dir + " 디렉토리 또는 파일은 존재하지 않습니다."); return; } File[] files = startDir.listFiles(); if (files == null) return; for (File file : files) { File filePath = new File(String.valueOf(file)); if (filePath.isDirectory()) { System.out.println("디렉토리:" + filePath); traverseDirectory(filePath.getAbsolutePath()); // 재귀함수 호출 } else { System.out.println("파일:" + filePath); } } } public static void main(String[] args) { traverseDirectory("."); } } ※ 출처[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 1~5)]

[워밍업 클럽 3기 CS 전공지식] 2주차 운영체제 미션

FIFO 스케줄링의 장단점이 뭔가요?장점먼저 들어온 작업이 먼저 처리되기 때문에 공평하게 프로세스들에게 CPU를 할당할 수 있습니다.단점먼저 들어온 프로세스가 완전히 끝나야지만 다음 프로세스가 실행될 수 있습니다.먼저 들어온 프로세스의 Burst Time(실행 시간)이 긴 경우 나중에 들어온 Burst Time이 짧은 프로세스의 오래 대기해야 합니다. SJF를 사용하기 어러운 이유가 뭔가요?Burst Time이 짧은 프로세스를 먼저 실행해서 대기 시간을 줄여 성능을 최적화 한다는 이상이 있습니다.하지만 먼저 들어온 Burst Time이 긴 프로세스 있어도 나중에 들어온 Burst Time이 짧은 프로세스가 먼저 작업을 처리되므로 Burst Time이 긴 프로세스가 작업이 처리되는데 오래 걸립니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?프로세스 간 컨텍스트 스위칭이 자주 발생합니다.컨텍스트 스위칭이 일어날 때 프로세스들의 정보를 저장하고 정보를 불러오는 작업으로 인해 오버헤드가 발생할 수 있습니다.프로세스 자체가 작업하는 시간보다 컨텍스트 스위칭 작업에 더 많은 시간이 들여집니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?프로세스에게 CPU를 할당하고 운영체제가 준 타임 슬라이스를 다 쓰고 강제로 빼앗기는 경우 CPU 사용률이 많다고 판단하고 CPU Bound Process 라고 인지합니다.프로세스에게 CPU를 할당하고 운영체제가 준 타임 슬라이스를 다 쓰지 않고 CPU 할당 해제한 경우 CPU 사용률이 적다고 판단하고 I/O Bound Process 라고 인지합니다. 공유자원이란무엇인가요?여러 프로세스 또는 여러 쓰레드 간에 공동으로 사용되는 자원(변수나 파일들)을 뜻합니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착상태가 발생하기 위해서는 4가지 필요 조건이 모두 충족되어야 합니다.상호배제자원은 한 번에 하나의 프로세스만 사용할 수 있어야 합니다.프로세스A가 한 자원을 점유했다면 그 자원은 프로세스B에게 공유될 수 없습니다.비선점이미 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 합니다.프로세스A가 자원을 점유하고 있는데 프로세스B가 그 자원을 빼앗을 수 없어야 합니다. 점유와 대기프로세스가 이미 하나 이상의 자원을 점유한 상태에서 다른 프로세스가 사용하고 있는 자원을 추가로 요청하며 대기해야 합니다.어떤 프로세스가 자원A를 가지고 있는 상태에서 자원B를 원하며 대기하는 상태여야 합니다.원형 대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있습니다. ※ 출처[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 4~7]

[워밍업 클럽 3기 CS 전공지식] 2주차 회고

[2 주차 시작하기 전 다짐]아침에 일어나서 주어진 강의 분량을 다 듣기틈날 때 강의 듣기저녁에 집에 와서 다시 듣기 또는 실습 진행강의 들으면서 강의 노트도 실시간으로 작성하기![2 주차 회고]칭찬할 점2 주차 다짐을 모두 지켰다!=> 꾸준히 하는 걸 힘들어하는 나에게 칭찬하고 싶다.아쉬운 점 강의 노트를 적는 동안은 생각을 안 하고 따라 치기만 한 것 같다.=> 강의를 듣고 그 날 강의 노트를 정리하는 시간을 가지자. [강의 내용 정리][운영체제][프로세스 동기화]프로세스 간 통신프로세스는 독립적으로 실행되기도 하지만 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있다.종류한 컴퓨터 내에서 프로세스 간 통신파일을 이용한 방법통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법파이프를 이용한 방법운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법한 프로세스 내에서 쓰레드 간 통신쓰레드는 코드, 데이터, 힙 영역을 공유하고 스택만 자기의 것을 가진다.데이터 영역에 있는 전역변수나 힙을 이용하면 통신이 가능하다.네트워크를 이용한 통신운영체제가 제공하는 소켓 통신하는 방법다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신하는 방법공유자원과 임계구역공유자원프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일들문제여러 프로세스가 공유하고 있어서 각 프로세스의 접근 순서에 따라 결과가 달라진다.컨텍스트 스위칭으로 시분할 처리를 하기 때문에 어떤 프로세스가 먼저 실행될 지 예측하기 어렵다.연산 결과를 예측하기 힘들다. 여기서 발생한 문제가 '동기화 문제' 이다.그러니 예측 불가능하고 손 댈 수 없는 운영체제 보다는 예측 가능하고 손 댈 수 있는 코드를 수정하는 게 최선이다.동기화 문제여러 프로세스 또는 여러 쓰레드가 공유 자원에 동시에 접근할 때 발생하는 문제이다.적절한 제어 없이 데이터가 동시에 수정되면 경쟁 조건(Race Condition)이 발생하여 예측 불가능한 결과나 데이터 불일치가 일어난다.해결 방법으로는 세마포어, 모니터 등의 동기화 기법을 사용한다.임계구역(Critical Section)여러 프로세스가 동시에 사용하면 안되는 영역임계구역 문제를 해결하기 위해서는 '상호 배제(Mutual Exclusion)' 메커니즘'이 필요하다.상호 배제(Mutual Exclusion) 요구사항 세가지임계영역에는 동시에 하나의 프로세스만 접근한다.(동시에) 여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야 한다.그렇지 않으면 다른 프로세스들이 오래 기다려야 한다. 세마포어(Semaphore)상포배제 메커니즘의 한 가지이다.정수형 변수이다.공유되는 자원의 개수에 따라 세마포어의 초기값 숫자를 설정한다.wait() 함수로 시작하고 signal() 함수로 끝나야 한다. 사이에 코드 작성세마포어를 이용하면 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않는다.단점wait(), signal() 함수의 순서를 이상하게 호출해서 잘못 사용할 경우가 있다.=> 이것을 해결한 방법은 '모니터'이다.모니터(Monitor)세마포어의 단점을 해결한 상호배제 메커니즘운영체제가 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법대표적으로 Java 에서 모니터를 지원synchronized 키워드해당 키워드가 붙은 함수들은 동시에 여러 프로세스에서 실행시킬 수 없다.상호배제가 완벽하게 이루어진다. [데드락]교착 상태(데드락)여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태발생 이유여러 프로세스가 공유하는 자원 때문이다.자원을 공유하지 않으면 교착 상태가 발생하지 않는다.유명한 예시식사하는 철학자교착 상태의 필요조건교착상태가 발생하기 위해서는 4가지 필요 조건이 모두 충족되어야 한다.상호배제프로세스A가 한 자원을 점유했다면 그 자원은 프로세스B에게 공유가 되면 안된다.비선점프로세스A가 자원을 점유하고 있는데 프로세스B가 자원을 빼앗을 수 없어야 한다.점유와 대기어떤 프로세스가 자원A를 가지고 있는 상태에서 자원B를 원하는 상태여야 한다.원형 대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있다.해결교착 상태 회피(Deadlock avoidance)프로세스들에게 자원을 할당할 때 어느 정도 자원을 할당 했을 때 교착 상태가 발생하는지 파악해서 교착 상태가 발생하지 않는 수준의 자원을 할당한다.전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태(Safe state)와 불안정 상태(Unsafe state)로 나뉜다.운영체제가 최대한 안정 상태를 유지하려고 한다.불안정 상태에 있더라도 무조건 교착 상태에 빠지는 건 아니고 교착 상태에 빠질 확률이 높아진다.은행원 알고리즘돈을 빌려줄 때 사업가들의 상환 능력도 보면서 빌려준다.교착 상태 발생했을 때 해결교착 상태를 막지 못한다. 그래서 교착 상태가 발생했을 때 해결하는 방법을 알아보자.가벼운 교착 상태 검출타이머를 이용한 방식프로세스가 일정 시간 동안 작업을 진행하지 않는다면 교착상태가 발생한 걸로 간주하고 해결한다.교착 상태 해결일정 시점마다 체크포인트를 만들어 작업을 저장한다.타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.무거운 교착 상태 검출자원 할당 그래프를 이용현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.프로세스들 간 자원 점유와 대기가 순환구조가 생긴다면 교착상태가 생긴 그래프이다.교착상태를 검출했다면 교착상태를 일으킨 프로세스를 강제종료 시킨다.그리고 다시 실행시킬 때 체크포인트로 롤백을 시킨다.운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.가벼운 교착상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않는다. [프로그래밍 언어, 프로세스] 프로그래밍 언어컴파일 언어개발자가 코드를 작성하고 컴파일 과정을 거쳐서 0과 1로된 기계어로 실행파일을 만든다.컴파일 과정에서 문법 오류를 검사하고 CPU에서 처리가능한 기계어로 실행파일을 만들어 놓기 때문에 속도가 빠르다.C, C++, C# 등이 이에 속한다.인터프리터 언어개발자가 작성한 코드를 미리 기계어로 만들지 않고 실행 시 코드를 한 줄씩 해석해 실행하는 언어이다.미리 검사를 하지 않기 때문에 실행할 때 오류가 날 수 있고 속도도 컴파일 언어와 비교하면 느리다.JavaScript, Python, Ruby 등이 이에 속한다.프로세스의 메모리 구조코드 영역, 데이터 영역, 스택 영역, 힙 영역으로 나뉜다.코드 영역말 그대로 실행해야 할 코드가 들어가는 영역데이터 영역전역변수나 배열이 들어가는 영역스택과 힙은 프로세스가 실행될 때 할당되는 메모리스택 영역지역변수와 함수 관련 값들힙 영역실행중에 메모리 공간을 할당할 수 있는 유동적인 공간프로그램을 실행 시켰을 때사용자가 프로그램을 실행시키면 운영체제가 프로세스를 만든다.운영체제는 exe 파일에 있는 코드 영역과 데이터 영역을 가져온다.프로세스의 코드 영역과 데이터 영역에 넣어준다.빈 상태의 스택과 힙을 할당한다.PCB(Process Control Block)를 만들어 관리가 가능하도록 만든다.프로그램 카운터 즉, 다음 실행할 명령어의 주소를 생성한 프로세스의 코드 영역의 첫 번째 주소로 설정한다.운영체제의 CPU 스케줄링에 따라서 프로세스가 실행되다기 작업을 마친다. [메모리]메모리 종류레지스터, 캐시, 메인메모리(RAM), 보조저장장치(하드디스크(이하 HDD), SSD)오른쪽으로 갈수록 가격은 싸지고 용량은 커진다. 속도는 느려진다.레지스터가장 빠른 기억 장소로 CPU 내에 존재한다.컴퓨터 전원이 꺼지면 데이터가 사라진다. 휘발성 메모리라고 부른다.32bit 레지스터를 가지고 있으면 32bit CPU라고 말한다.64bit 레지스터를 가지고 있으면 64bit CPU라고 말한다.CPU는 계산 할 때 메인메모리에 있는 값을 레지스터로 가져와서 계산한다. 계산 결과는 다시 메인메모리에 저장시킨다.캐시레지스터와 메인메모리에서 중간 단계 역할을 한다.레지스터는 CPU가 사용하는 메모리로 굉장히 빠르다. 그에 비해 메인메모리는 너무나 느리다.메인메모리에 있는 값을 레지스터로 옮기려면 한참 걸린다. 그래서 필요할 것 같은 데이터를 미리 가져오기로 한다.미리 가져온 데이터를 저장하는 곳이 바로 캐시이다.메인메모리(RAM)운영체제와 다른 프로세스들이 올라가는 공간이다.전원이 공급되지 않으면 데이터가 지워져 휘발성 메모리이다.HDD나 SSD 보다는 속도는 빠르지만 가격이 비싸기 때문에 데이터를 저장하기 보다 실행중인 프로그램만 올린다.보조저장장치인 HDD와 SSD가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리이다.저장 작업하기에 좋다. 메모리와 주소운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매긴다.이 숫자를 '주소'라고 부른다. - 1바이트(8비트)마다 주소를 가지고 있다.물리 주소와 논리 주소물리 주소메모리 0x0번지부터 시작하는 주소 공간논리 주소사용자 관점에서 바라본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.경계 레지스터하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터절대 주소와 상대 주소절대 주소실제 프로그램이 올라간 주소는 0x4000번지로 메모리 관리자가 바라본 주소이다.상대 주소컴파일러는 0x0번지라고 가정해서 프로그램 만든다.사용자가 바라본 주소인 '상대 주소'는 '논리 주소 공간'이라고 부른다.메모리 관리자가 바라본 주소인 '절대 주소'는 '물리 주소 공간'이라고 부른다.메모리 관리자CPU가 요청한 상대 주소와 재배치 레지스터에 있는 절대 주소를 더해서 데이터에 접근한다.재배치 레지스터프로그램의 시작 주소가 저장되어 있다.시작 영역이 바뀌면 재배치 레지스터만 변경해주면 된다. 그래서 굉장히 유연하다.메모리 할당방식유니프로그래밍 환경에서 메모리보다 더 큰 프로그램을 실행시키는 방법메모리 오버레이(memory overlay)큰 프로그램을 작게 나누어 일부만 실행하고 일부는 HDD의 스왑 영역에 저장된다.스왑(swap)스왑 영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑 영역으로 옮긴다.멀티프로그래밍 환경에서 메모리 관리가변 분할 방식프로세스의 크기에 따라 메모리를 나누는 방식프로세스가 크면 메모리도 크게 할당한 프로세스가 메모리에 연속된 공간에 할당되서 '연속 메모리 할당'이라고 한다.장점메모리에 낭비되는 공간이 없다. - 내부 단편화가 없다.단점외부 단편화가 발생한다.외부 단편화메모리 할당 해제 된 자리를 더하면 새로운 프로그램을 올릴 수 있는데 따로 따로 자리가 있어서 다른 프로그램을 올릴 수 없다.해결외부 단편화가 발생한 공간을 합쳐주는 조각모음을 하면된다.고정 분할 방식프로세스의 크기와는 상관없이 메모리를 정해진 크기로 나누는 방식프로세스 크기와 상관없이 메모리를 할당한 프로세스가 메모리에 분산되어 할당되어서 '비연속 메모리 할당'이라고 한다.장점구현이 간단하고 오버헤드가 적다.단점메모리에 낭비되는 공간이 있다. - 내부 단편화가 발생한다.가상 메모리에서 가변 분할 방식은 '세그멘테이션', 고정 분할 방식은 '페이징'이라고 부른다.버디 시스템가변 분할 방식과 고정 분할 방식의 단점을 최소화한 시스템2의 승수로 메모리를 분할해 메모리를 할당하는 방식프로세스가 사용을 마치고 메모리에서 나가도 근접한 메모리 공간을 합치기 쉽다.장점가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라진다.외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.고정 분할 방식처럼 내부 단편화가 발생하기는 하지만 많은 공간의 낭비가 발생하지 않는다. [자료구조와 알고리즘][java로 실습한 것은 깃허브에 올려두었다.]재귀사전적 정의 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것재귀 함수재귀적으로 정의된 함수기저 조건(탈출 조건)이 반드시 있어야 한다.if() 로 함수를 종료하지 않으면 콜스택에 메모리 공간이 가득 차서 자동으로 종료된다.=> java.lang.StackOverflowError 에러 발생콜스택함수가 호출되면서 올라가는 메모리 영역으로 스택이라고 부른다.스택의 특성처럼 먼저 들어온 데이터가 나중에 나간다. (FILO : First In Last Out)함수를 호출하면 해당 함수는 콜스택에 올라가게 되고 함수가 종료되면 콜스택에서 제거된다.public class Recursion { public static void main(String[] args) { myFunction(1); } public static void myFunction(int number) { if (number > 10) return; System.out.println(number); myFunction(number + 1); } }재귀 함수 - 팩토리얼n이 주어질 때 1부터 n까지 모든 수의 곱을 말한다.예시) 5! => 5*4*3*2*1 => 120재귀 함수 쉽게 작성하는 방법재귀 함수 내에서 자기 자신을 호출할 때 이 함수가 벌써 구현이 되어 있다고 가정하자.5! 구현하기5 * 4!(4*3*2*1) => 하위 4 * 3!(3*2*1) => 하위 3 * 2!(2*1) => 하위 2 * 1!(1)factorial() 함수가 이미 구현되었다고 가정하면 5 * factorial(4)를 호출하면 된다.이를 일반화 하면 number * factorial(number-1)그리고 중요한 기저 조건을 만들어야 한다.1이 되면 팩토리얼은 종료된다.0! 은 1이기 때문에 같이 기저 조건에 넣겠다.public class Factorial { public static void main(String[] args) { System.out.println(factorial(5)); // 120 } public static int factorial(int number) { if (number == 1 || number == 0) { return 1; } else { return number * factorial(number - 1); } } }재귀적으로 생각하기패턴1단순히 반복 실행콜스택 공간을 많이 차치해 성능은 for문보다 좋지 않다.패턴2하위 문제의 결과를 기반으로 현재 문제를 계산하는 것재귀를 이용해 하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식 - 하향식 계산재귀를 이용해서 상향식 계산도 가능하다.재귀 함수의 진정한 위력은 하향식 계산에서 발휘된다. 재귀 - 하노이탑 (정리 한번하기) 재귀 함수의 대표적인 예시하향식 계산 방식을 보여줄 수 있는 좋은 예시이다.세 개의 기둥과 서로 다른 크기의 원반들이 있다.가장 큰 원반이 아래에 있고 위로 갈수록 작은 원반으로 이루어져 있다.현재 기둥에서 다른 기둥으로 옮겨야 한다.규칙한 번에 하나의 원반을 움직일 수 있다.가장 위에 있는 원반만 옮길 수 있다.아래에 작은 원반이 올 수 없다.하위 문제 찾기 (재귀함수를 이용해서 하향식으로 접근)[깃허브 코드]이미 해결을 한 상황을 예상해보기 (하위 문제)첫 번째 목표 : 원반3을 기둥A에서 기둥C로 옮긴다. 하위 문제1 : 원반3 위에 있는 원반1,2를 기둥A에서 기둥B로 옮겨야 한다.hanoi(count - 1, from, temp, to);하위 문제2 : (하위 문제1) 이 해결되었다면 출력System.out.printf("원반 %d을/를 %s에서 %s로 이동%n", count, from, to);=> 원반 3을 A에서 C로 이동하위 문제3 : (하위 문제2) 가 해결되었다면 => 두 번째 목표 : 원반1,2를 기둥 B에서 기둥C로 옮겨야 한다.hanoi(count - 1, temp, to, from);기저 조건(탈출 조건)원반이 없는 경우, 옮길 원반이 없을 때if (count == 0) return; 정렬 - 버블정렬가장 쉽게 생각할 수 있는 정렬 중 하나이다.구현하기 쉽지만, 성능은 좋지 않다.앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘이다.방식앞에서부터 요소들을 하나씩 비교한다.가장 큰 숫자는 자기 위치를 찾아 가장 끝에 정렬된다.이미 정렬된 마지막 원소를 제외하고 앞에서부터 다시 요소를 검사한다.남은 원소가 하나이면 더이상 정렬을 할 필요가 없다.성능반복 횟수 for문 * 원소비교 for문 => O(n제곱)성능이 좋지 않다.장점가장 쉽게 생각할 수 있는 정렬 방법으로 이해와 구현이 간단하다.단점성능이 O(n제곱)으로 좋지 않다. 정렬 - 선택정렬버블정렬과 마찬가지로 구현이 쉬운 알고리즘이해와 구현이 간단하지만 성능이 아쉽다.방식정렬된 영역과 정렬되지 않은 영역을 나눠서 정렬되지 않은 영역을 비교한다.정렬되지 않은 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져온다.첫 번째 원소는 정렬된 영역으로 제외하고 다시 정렬되지 않은 영역을 비교한다.정렬되지 않은 영역에 요소가 한 개 남으면 정렬할 필요없이 끝이난다.성능반복 횟수 for문 * 원소비교 for문 => O(n제곱)성능이 좋지 않다.장점이해하기 쉽고 구현이 간단하다.단점성능이 O(n제곱)으로 좋지 않다. ※ '강의 내용 정리' 출처[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 4~7][인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 1~5)]

[워밍업 클럽 3기 CS 전공지식] 1주차 자료구조와 알고리즘 미션

자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.특별한 기능으로 저장하고 열람이 있습니다.데이터 저장에 유리한 연결리스트가 있지만 자료를 열람할 때 비효율적일 거 같습니다.데이터를 열람하는 건 배열의 인덱스 참조로 빠르게 열람할 수 있을 겁니다. 하지만 저장할 때 성능이 좋지 않습니다.그래서 빠른 데이터 읽기, 삽입을 할 수 있는 해시 테이블을 사용하려고 합니다.해시 함수를 이용해서 데이터에 빠르게 접근할 수 있고 값을 연결리스트로 구현할 시 데이터 저장, 삭제가 용이합니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐 자료구조를 사용할 겁니다.먼저 들어온 작업을 먼저 처리하는 규칙을 활용하기 위해서 입니다. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.기존에 작성한 Stack 코드에서 삽입, 제거, 참조의 인덱스 0을 변경했습니다.삽입의 경우 제일 끝자리에 새로 추가하는 값이라서 list 의 count 로 변경했습니다.제거와 참조의 경우 list 의 count 에서 -1 로 값을 변경했습니다. (인덱스는 0부터 시작)[깃허브 코드]/* 스택에 필요한 연산 */ // 1. push - 데이터 삽입 public void push(Object data) { // 연결리스트의 head 에 삽입 this.list.insertAt(this.list.getCount(), data); } // 2. pop - 데이터 제거 public Node pop() { try { // 연결리스트의 head 에서 꺼내기 return this.list.deleteAt(this.list.getCount() - 1); } catch (Exception e) { // 비어있는 리스트 지울경우 예외 던지기 return null; } } // 3. peek - 데이터 참조 public Node peek() { return this.list.getNodeAt(this.list.getCount() - 1); } 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력name 을 Object 타입으로 받아서 name이 String 타입이라는 걸 알려주기 위해 String 으로 형변환 했습니다.set() 의 경우 key, value 매개변수는 값을 HashData 에 저장할 때 사용해야 해서 이름을 바꾸지 않았습니다.hashFuntion() 에 매개변수로 value 를 주었습니다.get(), remove() 메서드의 매개변수에서 받아오는 타입을 Object 로 문자열을 받아올 수 있게 변경했습니다. [깃허브 코드]public int hashFunction(Object name) { String name1 = (String) name; return name1.charAt(0) % 10; } public void set(int key, Object value) { DoublyLinkedList list = (DoublyLinkedList) this.arr[this.hashFunction(value)]; } public Object get(Object key) { DoublyLinkedList list = (DoublyLinkedList) this.arr[this.hashFunction(key)]; } public DoublyNode remove(Object key) { DoublyLinkedList list = (DoublyLinkedList) this.arr[this.hashFunction(key)]; } ※ 출처[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 1~2]

[워밍업 클럽 3기 CS 전공지식] 1주차 운영체제 미션

while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }1.위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 서비스 루틴(ISR)을 이용해야 합니다. 매번 확인하는 것이 아닌 플레이어 스킬 사용 작업을 맡기고 CPU 는 다른 작업을 하러 갑니다.사용했다는 신호를 CPU에게 전달을 하면 인터럽트 서비스 루틴을 실행시켜 작업을 완료합니다. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 하드디스크에 저장된 실행 파일입니다.프로세스는 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 실행 중인 프로그램입니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리에 여러 개의 프로세스를 올려서 처리하는 것입니다.멀티 프로세싱은 멀티 프로세서로 작업을 처리하는 것입니다.멀티 프로세서는 CPU를 한 개가 아닌 여러 개를 이용하는 것을 말합니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장합니다.운영체제가 프로세스를 CPU에 할당할 때 해당 프로세스의 정보를 가지고 있는 PCB 를 읽어서 작업을 진행합니다. 컨텍스트 스위칭이란 뭔가요?프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태 값으로 교체하는 작업입니다. ※ 출처[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 1~3]

[워밍업 클럽 3기 CS 전공지식] 1주차 회고

[1 주차 시작하기 전 다짐]아침에 일어나서 주어진 강의 분량을 다 듣기틈날 때 강의 듣기저녁에 집에 와서 다시 듣기 또는 실습 진행[1 주차 회고]칭찬할 점한 번 듣고 이해를 할 수 없다고 판단이 되어서 반복해서 들으려고 노력했다.=> 5 일간 진행하는 동안 '시작하기 전 다짐'을 꼭 지켰다.현재 내가 공부하는 언어 java이다. 그런데 javascript로 진행되는 실습이라서 나는 코드를 java로 바꿔서 실습 해야 했다.=> java로 바꾸는 과정이 어렵지 않았다. 스스로에게 놀랐다. java를 공부한 보람을 느낄 수 있었다.아쉬운 점듣기만 하고 정리를 하지 못했다.다음 주차부터는 듣고, 더 오래 기억에 남을 수 있게 정리를 하면서 들어야겠다.=> 영상을 보면서 강의 노트를 작성하는 부분을 활용해 봐야겠다. [강의 내용 정리][운영체제]운영체제프로세스 간의 실행을 스케줄링 해주는 스케줄러 운영체제 구조커널프로세스와 메모리, 저장 장치를 관리하는 핵심적인 기능 담당사용자는 커널에 직접 접근 할 수 없다. 프로그램과 프로세스프로그램은 하드디스크에 저장된 실행 파일이다.프로세스는 하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 실행중인 프로그램이다. 멀티프로그래밍과 멀티프로세싱멀티프로그래밍은 메모리에 여러 개의 프로세스를 올려서 처리하는 것이다.멀티 프로세싱은 멀티 프로세서로 작업을 처리하는 것이다.멀티 프로세서는 CPU를 한 개가 아닌 여러 개를 이용하는 것을 말한다. 컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고다른 프로세스의 상태 값으로 교체하는 작업이다. 쓰레드프로세스 내에 1개 이상 존재하는 작업을 뜻한다.한 프로세스 내에 쓰레드들은 PCB, 코드, 데이터, 힙 영역을 공유한다.스택은 쓰레드마다 하나씩 가지고 있다.장점한 프로세스 내에서 스택 영역을 제외한 모두 공유하기 때문에 오버헤드가 작다.단점쓰레드간 통신은 데이터를 공유를 쉽게 할 수 있다. 그러나 공유되는 공간에 문제가 생길 수 있다. => 프로세스 동기화 cpu 스케줄링운영체제가 모든 프로세스에게 CPU 를 할당/해제 하는 것을 말한다.목표리소스 사용률 - CPU 사용률 또는 I/O 사용률을 높이는 것이다.오버헤드 최소화 - 스케줄링 계산이 복잡하거나 컨텍스트 스위칭이 자주 발생하면 안된다.공평성 - 특수한 경우를 제외하고 모든 프로세스에게 CPU 가 골고루 할당 되어야 한다.처리량 - 같은 시간 내에 더 많은 처리를 할 수 있어야 한다.대기 시간 - 작업을 요청하고 실제 작업이 이루어지기 전까지 대기하는 시간이 짧아야 한다.응답 시간 - 대화형 시스템에서 사용자의 요청에 얼마나 빨리 반응하는 지가 중요하다. cpu 스케줄링 알고리즘FIFO(First In First Out)스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식일괄처리 시스템에 쓰인다.장점단순하고 직관적이다.단점먼저 들어온 프로세스가 완전히 끝나야지만 다음 프로세스가 실행될 수 있다.실행 시간(Burst Time)이 짧고 늦게 도착한 프로세스가 실행 시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 한다. SJF(Shortest Job First)Burst Time이 짧은 프로세스를 먼저 처리한다.문제 2가지프로세스가 얼마나 실행될 지 예측하기 어렵다.Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.이러한 문제로 SJF 알고리즘은 사용되지 않는다.RR (Round Robin)FIFO 알고리즘의 단점을 해결한다.타임 슬라이스(프로세스에게 할당하는 일정 시간)만큼 CPU를 할당하고 할당된 시간이 지니면 강제로 다른 프로세스에게 CPU를 할당한다.강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려난다.타임 슬라이스의 값에 따라 성능이 크게 달라진다.MLFQ(Multi Level Feedback Queue)RR 의 업그레이드된 알고리즘이다.기본적으로는 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택한다.작동 원리우선순위를 가진 큐를 여러 개 준비를 한다.우선수위가 높으면 타임 슬라이스가 작고 우선순위가 낮을수록 타임 슬라이스 크기가 커진다.프로세스가 타임 슬라이스 크기를 오버해서 강제로 CPU 를 빼앗긴다면 프로세스는 원래 있던 큐보다우선순위가 더 낮은 큐로 이동하게 된다.최종적으로 타임 슬라이스가 무한초에 가깝게 할당되기 때문에 FIFO 처럼 연속적으로 작업을 마칠 수 있게 된다. [자료구조와 알고리즘][java로 실습한 것은 깃허브에 올려두었다.]자료구조와알고리즘자료구조는 데이터가 어떤 구조로 저장되고 어떻게 사용되는 지를 나타내는 것이다.예시변수 - 하나의 값을 저장배열 - 여러 개의 값을 연속적으로 저장알고리즘은 어떤 문제를 해결하기 위한 확실한 방법이다.데이터가 어떤 자료구조를 하고 있는 지에 따라서 알고리즘이 달라진다.시간 복잡도알고리즘이 어떤 문제를 해결하는데 걸리는 시간이다.알고리즘을 평가할 때 시간을 측정하는 방식이 아닌 코드에서 성능에 영향을 주는 부분을 찾아 실행을 예측하는 것이다.반복문이 성능에 많은 영향을 준다. 최악의 경우를 평가하는 빅오입력이 늘어날 때 계산량이 늘어나는 척도를 나타낸다.계산에 가장 많은 영향을 미치는 항만 표기 한다. 상수는 제거해준다.예시n제곱 + 2n + 100 -> O(n제곱)3n제곱 + 100 -> O(n제곱) 자료구조배열(Array)모든 프로그래밍 언어에서 기본적으로 제공하는 자료구조요청한 크기만큼 메모리에 연속된 공간을 할당한다.운영체제는 배열의 시작 주소만 기억한다.길이가 10인 배열의 세 번째 값에 접근하고 싶다면 arr[2] 인덱스로 한 번에 접근 가능하다.장점배열의 인덱스 참조는 길이에 상관없이 한 번에 가져온다. O(1) 성능단점데이터 삽입, 삭제 성능이 좋지 않다.크기를 예측할 수 없어서 메모리가 낭비될 수 있다. 연결리스트(LinkedList)저장하려는 데이터들을 메모리 공간에 분산해 할당하고 데이터들을 서로 연결해준다.노드를 만들어서 수행데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있다.첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있다.장점데이터 추가 시 빈 메모리 공간에 데이터를 생성하고 연결만 해주면 된다. (초기 크기를 알 필요 없다.)중간에 데이터를 삽입, 삭제할 때 다음 가리키는 노드만 변경하면 되기 때문에 아주 간단한 작업이 된다.단점데이터들이 전부 떨어져 있어서 원하는 데이터에 바로 접근할 수 없다.데이터를 찾으려면 첫 노드부터 차례대로 탐색 해야 한다. 데이터 참조가 O(n) 의 성능을 가진다.스택(Stack)FILO(FIrst In Lost Out) - 먼저 들어간 데이터가 나중에 나오는 규칙이다.실생활 예시엘리베이터에 모든 사람이 같은 층에 내린다면 먼저 들어간 사람이 나중에 내린다.연결리스트로 스택 구현head 를 이용한다.데이터 삽입을 무조건 첫 번째 인덱스에 한다.데이터 제거도 무조건 첫 번째 인덱스에 한다.큐(Queue)FIFO(FIrst In First Out) - 먼저 들어간 데이터가 먼저 나오는 규칙이다.실생활 예시마트 계산대에 들어온 순서대로 계산한다.운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 꺼내서 처리 (FIFO 스케줄링)이중연결리스트로 큐 구현이중연결리스트(양방향 연결리스트)큐의 데이터 삽입head 로 가장 앞부분에 삽입한다.큐의 데이터 제거가장 뒤에서부터 데이터를 제거한다.뒷부분에서 데이터를 제거하고 가리키는 tail 은 이전 노드를 가리킨다.덱(Deque)데이터의 삽입과 제거를 head 와 tail 두 군데서 자유롭게 할 수 있는 자료구조이다.덱을 이용하면 스택과 큐를 전부 구현할 수 있다.해시 테이블(HashTable)해시와 테이블이 합쳐진 자료구조이다.해시 함수로 테이블의 인덱스를 새로 만든다.Key 와 Value 로 이루어져 있다. Value 부분에서 원하는 데이터의 키를 찾는 건 O(n) 의 성능을 가진다.장점빠른 데이터 읽기, 삽입, 삭제가 가능하다. O(1) 의 성능단점메모리를 많이 차지한다.미리 많은 공간을 마련해줘야 한다.좋은 해시 함수의 구현이 필수데이터를 골고루 분배 시켜주는 함수가 좋은 해시 함수이다.셋(Set)데이터의 중복을 허용하지 않는 자료구조이다.해시 테이블을 이용해서 쉽게 구현할 수 있다.해시 테이블의 Value 부분에서 HashData 로 저장을 한다.HashData 에 key만 사용하고 value 부분은 사용하지 않는다.key가 key임과 동시에 데이터로 쓰인다. ※ '강의 내용 정리' 출처[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 1~3][인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 1~2]