블로그

최신순
인기순
좋아요순

[인프런 워밍업 클럽 2기 - CS] 발자국 - 1주차

회고 개인적인 일정으로 주말에 몰아서 강의를 보고, 미션도 완료했다.그러다보니 뭔가 숙제를 하는 기분이었다.미션의 답을 생각하다보니 코드를 짜보는것도 재밌을 것 같다는 생각을 했지만, 시간적인 여유로 인해 생각했던 코드 중 1개만을 작성했다.내일부터는 여유있게 작업해야겠다.++ 발자국에 공부한 내용을 담아야 된다는 내용을 보고, 개인 블로그에 비밀글로 작성했던 내용을 발자국에도 작성했었다.그런데 발자국 가이드를 다시 읽어보니 너무 자세한 강의 내용 작성은 피해달라는 말을 보고 급하게 내용을 수정하게 되었다. 작성하느라 고생했던 부분이 아쉽긴 하지만 실수를 하지 않았다는 점에서 만족해야겠다. 운영체제운영체제는 아는 부분도 있었지만 세부적으로는 모르는 부분들이 대부분이었다.몇번 돌려보니 기본적인 내용은 이해했으나, 세부적인 내용은 반복학습을 통해 암기할 필요가 있어보인다.PCB의 구조 같은것 말이다. 자료구조와 알고리즘이론적인 내용은 아직 쉽게 이해 가능하나, 구현하는 부분에 있어서는 시간적 여유로 인해 해보지 않고 시청만 했다보니 완벽하게 이해하지는 못했다. 시간을 내서 직접 코드를 작성해보고 테스트 해볼 필요가 있다.시간 복잡도에서 알고리즘의 반복문을 보고 성능 평가를 한다는 점과 Big-O 표기법에 대한 내용은 흥미로웠다.

[인프런 워밍업 클럽 2기 - CS] 1주차 발자국

강의 수강운영체제 : 운영체제의 탄생배경과 프로세스, 쓰레드에 대해서 자세히 배웠다. 수업을 차근차근 들으면서 머릿속의 파편화된 지식이 하나로 모아져 정리되는 느낌이었다. 특히 프로세스와 쓰레드에 자세히 배울수 있어서 좋았다. 다음은 프로세스와 쓰레드에 대해서 배운 부분을 간략히 요약했다.프로세스와 쓰레드프로그램 : 어플리케이션이나 앱이라고 부르고, 윈도우에서는 .exe 파일의 모습을 하고있다.프로세스 : 하드디스크에 저장된 프로그램이 메모리에 올라가 실행중인 프로그램을 말한다. 프로세스의 영역은 다음과 같다. ( 프로세스가 메모리에 올라간다는 것은 밑의 각 영역이 메모리에 할당된다는 것을 의미)code 영역 : 자신을 실행하는 코드가 저장되어 있음.data 영역 : 전역변수와 static 변수가 저장되어 있음.stack 영역 : 지역변수, 함수 호출시 필요한 정보들이 저장되어 있음.heap 영역 : 프로그래머가 동적으로 메모리를 할당하는데 쓰임그리고 프로세스는 운영체제의 의해 관리된다. CPU 입장에서 동작과정은 다음과 같다. CPU는 0과 1과 같은 기계어만을 실행하는데, CPU내의 제어장치가 숫자와 5와 7을 메모리에 저장시킨다. 그리고 이 메모리에 저장된 값을 레지스터(edx,eax)로 가져온다. 그리고 제어장치가 레지스터에 저장된 5와 7을 가지고 더하라는 명령을 하면 산술 논리 연산장치가 두 숫자를 더하고 그 결과인 12를 eax 레지스터에 저장한다. 그리고 다시 제어장치가 eax레지스터에 저장된 12을 가지고 메모리에 저장한다.자료구조 : 기존에 안다고 생각했던 자료구조도 강의를 수강하면서 더 자세히 알게 되어서 좋았다. 다음 주에는 좀더 시간을 투자해 자료구조를 집중적으로 공부하고 싶다. 추가적으로 다음주에는 평일부터 학습범위에 맞게 수업을 수강하고싶다. 미션문제를 읽고 먼저 답안보다 배운 것을 기억하려고 노력했고, 후에도 기억이 안 나는 부분은 복습을 통해서 답안을 작성했다. 확실히 미션이 있어서 복습을 할 수 있다는 점이 좋았다.

인프런 워밍업 클럽 스터디 2기 CS 1주차 발자국

운영체제처음에는 운영체제의 역사부터 시작해서 어떻게 해서 운영체제가 생겨났는지 알아보았다. 그 후 간단하게 컴퓨터의 구조를 알아보고 이후 프로그램과 프로세스의 차이, 운영체제가 어떻게 PCB를 통해 프로세스를 제어하는 지를 알아보았다. 그 밖에도 프로세스의 상태, 컨택스트 스위칭을 배우고 지금은 CPU가 스케줄링을 통해서 프로세스를 제어하는 다양한 방식을 배우고 있다. 자료구조 연결리스트메모리에 연속된 공간에 할당되는 배열과 달리, 각 노드끼리 포인터를 통해 메모리에 연속되지 않는 공간에 할당하여 사용할 수 있는 자료구조이다.배열과 연결리스트의 장단점 배열 새로운 데이터 추가 및 기존 데이터 삭제에는 시간이 오래 걸리나, 데이터 참조는 빠르게 가능하다.연결리스트새로운 데이터 추가 및 기존 데이터 삭제는 빠르게 가능하나, 데이터 참조는 오래 걸린다.각 상황에 맞는 자료구조를 사용하기! 스택FILO 자료구조로 제일 처음 들어간 데이터가 가장 마지막에 나오는 자료구조다. 탑을 쌓아 저장하는 자료구조라고 보면 된다. 큐FIFO 자료구조로 제일 처음 들어간 데이터가 제일 처음에 나오는 자료구조다. 들어간 순서대로 나오는 자료구조이다. 덱스택과 큐를 합쳐 한번에 두 자료구조를 사용할 수 있는 자료구조로, 가장 먼저 넣은 데이터를 꺼낼 수도 있고, 가장 마지막에 넣은 데이터를 꺼낼 수도 있다. 해시테이블key 값과 value 값을 가지는 자료구조로, 해시 함수를 통해 데이터들을 적절히 고르게 배분하면 해시 값을 통해 보다 빠른 데이터 검색을 할 수 있다.중복된 key는 허용하지 않지만, 중복된 value는 허용한다. 셋value 값만 가지는 자료구조로, 중복을 허용하지 않는다.셋은 중복된 데이터를 제거하거나, 특정 값의 존재 여부를 빠르게 확인할 때 사용할 수 있다.

[인프런 워밍업 스터디 클럽] 2기 - 첫 번째 발자국

드디어 인프런 워밍업 클럽 2기가 시작됐다. 사실, 수강 신청 전까지 끝까지 의심했다. 진짜 하고 싶은 일이 맞을까? 수강 신청이 열리는 순간부터 셔터 문 닫을 때까지, 약 2주 동안 고민하다 결국 신청했다. '시도하지 않으면 후회할꺼야'라는 마음의 소리를 이길 수 없었다. 강의수강 추상화를 주제로 이야기를 풀어간다. 추상화 덕분에 일상을 돌아봤다. 모든 것이 추상화다. 추상화되어있지 않은 사물이 바로 떠오르지 않는다. 발자국을 작성하도록 도와주는 노트북도 그렇다. 일정한 리듬에 맞춰 키보드를 두들기는데 글자가 모여 글이 된다. '추상화가 없다면 01001과 같은 숫자로 글을 작성하고 있지 않았을까?'라는 생각이 들었다. 추상화는 '친절'이라고 생각한다. 코드에 추상화를 더하는 전과정이 친절하지 않으면 불가능하다. 읽는 사람이 어떻게 조금 더 쉽게 읽을 수 있을까?를 고민하는 과정이 흥미롭다. 동작하는 코드 위에 의도를 전달하기 위해 친절을 베푼다. 코드, 글, 한편의 작품이 '쉽다'라는 이야기를 들으면 좋겠다. 한 순간에 가질 수 없다고 생각한다. 절반도 되지 않았지만, 객체 지향은 여러번 연습하지 않으면 익힐 수 없다는 느낌을 강하게 받았다. 체화되면 어떻게 코드가 보일지 기대된다. 미션객체 지향을 다루기 전, 미션은 비교적 간단했다. 아래 2가지를 중점으로 생각했다. 어떻게 해야 메시지를 전달할 수 있을까?미션의 의도가 무엇일까? 1기 백엔드 미션을 자주 돌아본다. 미션에서 나누고 싶은 이야기가 '자주 다루는 핵심'이라는 인상을 받았다. 과정이 3개월이 더 지났는데 배울 때마다 새롭다. 2기도 똑같은 출제자, 우빈 님의 의도가 무엇일지 생각했다. 도출한 결론은 '추상화'다. '만약 강의 내용을 주제로 대화를 나눠요'라는 미션이 주어졌을 때 추상화가 금지어라면 어떨까? 주어진 시간이 지옥이라고 느낄 것 같다. 다음 미션은 '객체 지향으로 추상화'를 어떻게 적용할 것인지 고민하는 시간을 가진다. 부족하다고 느꼈는데 잘됐다. 특히 다른 러너의 의견을 접하고 나누고 싶다. 자세한 내용은 블로그에 기록했다. 마치며어떤 행동을 시작할 때 항상 초심을 글로 작성한다. 작성한 글을 보며 '오늘 하루 최선이었나? 묻는다. 그런데 최선을 다하지 않았다. 왜 그랬을까? 시스템이 아니다. 4주라는 기간을 유지하려면 '리듬'이 중요하다고 생각한다. 그런데 자주 미뤘다. 난이도가 어렵다고 느껴지면 미뤘다. 숨을 고르는 건 좋다. 항상 전속력으로 달릴 수 없다. 하지만 학습을 이어가는 전환 속도가 느렸다. 그래도 어떻게든 계획된 진도를 마쳤다. 원하는 결과는 아니어서 아쉽지만 덕분에 다음 주 어떻게 지내야 할지 처절하게 느꼈다. 리듬을 찾자. 고통스럽다는 건, 적절한 난이도라는 증거다. 쉬우면 공부가 아니다. 고통을 극복했을 때 펼쳐지는 그림을 상상해 보자. 다음 주, 발자국에 어떻게 남길지 기대된다. 인프런 워밍업 클럽 스터디 - BE 클린 코드 & 테스트 과정

백엔드･인프런워밍업클럽

[인프런 워밍업 클럽 CS 2기] - CS 1주차 발자국

[CS 1주차 발자국] 강의 수강[운영체제]전반적인 운영체제 개요, 프로세스와 쓰레드, CPU 스케줄링에 대해 학습했습니다.[자료구조와 알고리즘]자료구조와 알고리즘 기초 지식과 전반적인 자료구조에 대해 학습했습니다. [회고]칭찬하고 싶은 점강의를 들으면서 노션으로 학습한 내용을 정리한 점이해하기 위해 여러 번 강의를 돌려 본 점아쉬웠던 점시간표에 맞게 학습을 하지 않은 점 (퇴근하고 공부하려니.....잘 안됐다)보완하고 싶은 점2주차부터는 시간표에 맞게 학습하기! 미션[회고]미션을 하면서 공부한 내용들을 다시 복습하는 점이 좋았다. 복습을 하면서 내가 놓쳤던 부분들을 알고 가니 더 이해가 되는 것 같다.

발자국

인프런 워밍업 클럽 스터디 2기 - CS 1주차 미션

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?폴링 대신 인터럽트 방식을 이용 (스킬을 사용한 후 인터럽트를 통해 알려주기) 프로그램과 프로세스가 어떻게 다른가요?프로그램은 정적인 실행 파일이고, 프로세스는 메모리에 올라가 실행 중인 프로그램 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 메모리에 여러 개의 프로세스가 올라오는 것, 멀티프로세싱은 CPU가 여러 개의 프로세스를 처리하는 것을 의미함 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB (Process Control Block) 컨텍스트 스위칭이란 뭔가요?하나의 프로세스를 실행하다가 다른 프로세스를 실행할 때, 이전 프로세스의 상태(컨텍스트)를 저장하고 새로운 프로세스의 상태를 불러오는 작업자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시테이블 / 키-값 구조로 빠른 데이터 읽기, 삽입/삭제 가능하므로 적합 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐 / FIFO의 구조를 가지고 있어 순서대로 주문을 처리하기에 적합

알고리즘 · 자료구조

[인프런 워밍업 클럽 2기 - CS] 미션 - 1주차

운영체제1) 아래 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 방식을 해결하기 위해서는 인터럽트 방식을 사용하는게 좋습니다.문제가 코드로 주어졌기 때문에 인터럽트와 비슷한 동작을 하는 코드를 만들어 보았습니다.// 1~4 중 랜덤한 초 후에 "skillActivated" 라는 log 출력과 true를 반환하는 함수 const skillActivate = () => { return new Promise((resolve) => { const randomTime = Math.floor(Math.random() * 4) + 1; console.log(`${randomTime}초`); setTimeout(() => { console.log("skillActivated"); resolve(true); }, randomTime * 1000); }); }; // 1초마다 "working" 이라는 log를 출력하며, // skillActivate 의 true 반환을 기다렸다가 isActivated가 true가 되면 log 메시지를 출력하고 종료 const work = async () => { let isActivated = false; const workingInterver = setInterval(() => { console.log("working"); }, 1000); isActivated = await skillActivate(); if (isActivated) { console.log("isActivated"); clearInterval(workingInterver); } }; work(); 2) 프로그램과 프로세스가 어떻게 다른가요? - 프로그램: 저장장치에 저장되어있는 상태 = HDD/SDD에 저장된 상태 = 수동적- 프로세스: 실행중인 프로그램 = RAM에서 실행중인 상태 = 능동적3) 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?- 멀티프로그래밍: 메모리 관점- 멀티프로세싱: CPU 관점메모리에 여러개의 프로세스가 있으면(멀티프로그래밍), 그걸 CPU가 돌아가면서 돌림(멀티프로세싱). 4) 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?프로세스의 정보를 가지고 있는 PCB라는 것을 만들고, 프로세스가 종료되면 해당 PCB를 연결리스트에서 제거합니다.5) 컨텍스트 스위칭이란 뭔가요?CPU는 시분할로 작동하기 때문에 A라는 작업을 하다가 B라는 작업을 해야되는 경우 같이 일을 스위칭 하는 것을 말합니다.스위칭 하는 과정에서 나중에 다시 해당 작업을 하기 위해 레지스터를 PCB에 저장하고 불러오는 방식으로 작업을 이어서 할 수 있습니다.자료구조와 알고리즘1) 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 저라면 배열을 사용하겠습니다.일반적으로 학교는 번호를 순서대로 매겨 학생의 정보를 입력합니다.때문에 index +1 이 학생의 번호가 될 수 있습니다.중간에 학생이 전학을 가더라도, 학생의 번호를 당겨올 필요가 없으며, 전학간 학생의 정보만을 전학으로 수정하면 됩니다.반대로 전학을 오는 학생이 있을 수 있으나 보통 2명이 넘지는 않기 때문에 교실의 학생 수 보다 +2 크기의 배열을 처음에 할당하면 된다고 생각합니다.이렇게 하면 배열의 장점인 빠른 읽기/쓰기를 사용하면서, 배열의 단점인 데이터 삽입에 대한 대비를 할 수 있습니다.2) 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.주문이 들어온 순서대로 처리 하려면, 들어온 순서대로 나가는 큐 구조를 사용할 것 입니다.이와는 좀 별개의 내용으로, 최근 흑백요리사를 보면서 분담 작업하는 것을 보았습니다.때문에 만약 주문처리 프로그램이 음식점이고, 메뉴별로 분담이 되어있는 상태라면, 주문이 순서대로 처리 되면서, 전체 주문음식 수가 표시되는 기능을 추가하는게 좋다고 생각합니다.만약 스택 구조로 지금 나가야되는 주문만 보고 해당되는 작업만을 하는 것은 비효율 적이기 때문에, 현재 주문 된 음식이 종류별로 몇개씩 있는지 확인 후, 한번에 여러개를 만든다든지, 자신에게 해당되는 음식이 없다면 많이 주문된 음식의 준비를 돕는등의 방식으로 처리하는게 더 효율적 이지 않을까 라는 생각을 해당 문제를 생각하면서 했습니다.

[인프런 워밍업 클럽 CS 2기] 1주차 발자국

자료구조와 알고리즘 자료구조(Data Structure)란 효율적인 데이터의 사용을 위해 데이터를 특정 방식으로 저장, 구성하는 방식이다.알고리즘(algorithm)이란 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다.자료구조와 알고리즘을 함께 공부하는 이유는, 자료구조에 따라 알고리즘이 달라지기 때문이다. 즉, 어떤 방식으로 데이터를 저장하고 구성했냐에 따라 문제를 해결하는 방식이 달라진다. 또한 같은 자료구조일지라도 알고리즘은 여러가지가 될 수 있다.개발자라면 문제 해결을 위한 가장 좋은 알고리즘을 선택할 수 있어야 하며 가장 좋은 알고리즘을 위해 어떤 자료구조를 사용할지 결정할 수 있어야 한다. 그렇다면, 좋은 알고리즘이란 무엇일까?일반적으로 알고리즘의 속도를 성능의 척도로 사용하여 문제를 해결하는 속도가 빠를수록 좋은 알고리즘이라고 할 수 있다. 속도는 어떻게 측정할까? 시간복잡도시간복잡도(Time Complexity)란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 뜻한다. 이 때의 시간은 초, 분을 뜻하는 것이 아니라 '문제해결을 위해 같은 방식을 몇 번이나 반복했는지'와 같은 반복 횟수를 뜻한다. 알고리즘에 대해 다음 세 가지 경우로 나누어 성능을 평가한다.최선의 경우: Big-Ω(빅-오메가).한 번에 데이터를 찾는 경우최악의 경우: Big-O(빅-오).마지막에 데이터를 찾는 경우평균의 경우: Big-Θ(빅-세타).배열 길이의 중간만큼 시간이 걸리는 경우가장 많이 사용하는 방법은 Big-O로, 앞으로 이야기하는 시간복잡도는 특정 알고리즘을 사용해 문제를 해결할 때 가장 오래걸리는 시간이다. 시간 복잡도에는 여러가지가 있는데, 입력량(데이터의 양)이 증가할수록 계산량도 비례하여 증가하는 일차함수의 모양을 띠는 O(n), 가장 성능이 좋은 O(1) 등이 있다. 자료구조 배열(Array)프로그래밍 언어에서 기본적으로 제공하는 자료구조로, 연속된 메모리 공간을 찾은 뒤 순서대로 데이터를 할당하고, 나머지 공간에 의미 없는 쓰레기 값을 저장한다.장점참조에 있어 O(1)의 좋은 성능을 보인다.단점데이터 삽입과 삭제에 대해 비효율적이다. 연결 리스트(LinkedList)저장하려는 데이터들을 메모리 공간에 분산해 할당한 뒤 이 데이터들을 노드로 연결하는 자료구조노드는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나를 가지고 있어 다음 노드와 연결이 가능하다.연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근이 가능하다.장점데이터의 삽입, 삭제에 유리단점참조에 있어 O(n)의 성능을 보여 비효율적이다. 데이터의 참조가 자주 발생한다면 배열을, 삭제 또는 삽입이 자주 발생한다면 연결 리스트를 쓰는 것이 효율적이다. 스택(Stack)First In Last Out(FILO) 즉, 가장 먼저 삽입된 데이터가 가장 나중에 나오는 특징을 가지는 자료구조이다.우리가 자주 사용하는 Ctrl+z(이전으로 되돌리기) 기능도 스택으로 구현된 것이다. 큐(Queue)First In First Out(FIFO) 즉, 먼저 들어간 데이터가 먼저 나오는 특징을 가지는 자료구조이다.FIFO 스케줄링에서 운영체제는 프로세스를 큐에 들어온 순서대로 넣고 CPU는 먼저 들어온 순서대로 프로세스를 처리한다. 덱(Deque)데이터의 삽입과 삭제를 head와 tail 두 군데에서 자유롭게 진행 가능한 자료구조이다. 해시 테이블(Hash Table)프로그래밍 언어에 따라 해시, 맵, 해시맵, 딕셔너리 등 다양한 이름으로 불린다. 해시와 테이블이 합쳐진 것으로, 특정 해시 함수에 따라 테이블의 Key와 Value에 매치된다.장점Key만 알면 Value에 O(1)의 성능으로 읽기가 가능하다.삽입, 수정, 삭제 또한 O(1)의 성능을 보인다.단점이미 어떤 Key에 대한 Value가 존재할 경우, 해당 Key에 대한 다른 데이터가 생성될 때 충돌이(Collision) 발생하는데, 이 충돌을 해결하기 위해 이전에 있던 Value와 새로 들어간 Value를 연결 리스트로 연결한다. 이후에 저장된 데이터에 접근하기 위해선 원래 있던 데이터에 먼저 접근 후 연결 리스트를 통해 다음 데이터로 접근한다. 이 때의 참조 성능은 O(n)이 된다. 그렇기 때문에 같은 Key에 여러 Value가 존재하지 않도록 데이터를 골고루 분산 시킬 수 있는 해시 함수의 선정이 중요하다.공간이 많이 필요해 메모리를 많이 차지한다. 셋(Set)데이터의 중복을 허용하지 않는 자료구조로, 해시 테이블을 이용해 구현할 수 있어 해시 셋(Hash set)이라고도 한다.해시 테이블의 Value값을 사용하지 않고 Key만 사용하여 구현한다. 즉, Key가 key이자 데이터가 되는 것이다. 운영체제(Operating System) 운영체제(Operating System)란 응용프로그램 또는 사용자가 컴퓨터 하드웨어를 편리하고 효율적으로 사용하게 하기 위하여 시스템 자원(메모리, 프로세서 등)을 관리하고 여러가지 프로그램이 필요로 하는 공통적인 서비스를 제공하는 소프트웨어이다. 운영체제의 역할프로세스 관리:여러가지 애플리케이션을 동시에 실행할 수 있도록 한다.메모리 관리: 여러가지 애플리케이션을 실행할 때 메모리를 관리한다.하드웨어 관리: 중요한 데이터를 보호하기 위해사용자의 하드웨어에 대한 직접적인 접근을 막는다. 파일 시스템 관리: 하드디스크에 파일들을 효율적으로 저장, 관리한다.운영체제의 구조커널: 프로세스와 메모리, 저장장치를 관리하는 운영체제의 핵심 부분. 사용자는 커널에 직접 접근하지 못하고, 인터페이스를 통해 접근 가능인터페이스: 사용자의 명령을 전달하고 실행 결과를 사용자에게 알려주는 역할시스템 콜: 사용자로부터 커널을 보호하기 위한 인터페이스. 하드웨어에 데이터 저장시 Write 함수를 통해 하드디스크의 빈 공간에 데이터를 저장해, 다른 데이터를 덮어쓰거나 침범하지 않도록 한다.드라이버: 하드웨어와 커널의 인터페이스. 운영체제는 많은 종류의 하드웨어를 지원하해야 하는데 마우스와 키보드같은 간단한 하드웨어 프로그램은 커널이 가지고 있기도 하지만, 보통 하드웨어는 그 하드웨어의 제조사가 드라이버를 만들어 제공한다. 사용자는 이런 디바이스 드라이버를 설치해서 사용을 할 수 있다. 컴퓨터와 하드웨어 구조오늘날 대부분의 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조.메인보드: 다른 하드웨어를 연결하는 장치.CPU(Central Processing Unit, 중앙처리장치)CPU의 구성산술논리 연산장치(Arithmetic and Logic Unit, ALU): 데이터 연산제어 장치(Control Unit): 모든 장치들의 동작 지시, 제어레지스터: CPU 내에서 계산을 위해 임시로 보관하는 장치메모리RAM(Random Access Memory)랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같다.전력이 끊기면 데이터를 읽어버린다. 메인 메모리로 사용ROM(Read Only Memory)전력이 끊겨도 데이터를 보관할 수 있지만 데이터를 한 번 쓰면 수정 불가컴퓨터 부팅과 관련된 BIOS 저장에 주로 쓰인다. CPU와 입출력 장치의 통신 방식폴링 방식: 입출력이 완료되는 시점을 몰라 주기적으로 확인해야 해 성능이 낮다.인터럽트: 폴링 방식의 단점을 해결하기 위한 방식. 입출력 관리자에게 입출력 명령을 내린 뒤 CPU는 다른 작업을 진행하고 입출력 완료 시 입출력 관리자가 CPU에게 신호를 주면 신호를 받은 CPU는 인터럽트 서비스 루틴(ISP)을 실행시켜 작업을 완료한다. 프로세스와 쓰레드프로그램(Program): 애플리케이션 또는 앱이라고도 불리며, 하드디스크 등과 같은 저장장치에 저장된 명령문의 집합체프로세스(Process): 실행 중인 프로그램, 즉 하드디스크에 저장된 프로그램이 메모리(RAM)에 올라갔을 때 프로세스의 구조Code: 자신을 실행하는 코드 저장Data: 전역 변수와 Static(정적) 변수가 저장Heap: 프로그래머가 동적으로 메모리를 할당할 수 있는 메모리 공간(malloc(), free())Stack: 지역 변수와 함수 호출을 했을 때 필요한 정보들 저장 PCB(Process Control Block)운영체제가 여러 개의 프로세스를 체계적으로 관리하기 위해 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 생성, 저장한다. 이 PCB는 연결 리스트 자료구조로 저장된다.PCB의 구조포인터: 프로세스의 한 상태에서 다른 상태로 전환될 때 저장프로세스 상태: 현재 프로세스의 다섯 가지 상태(생성, 준비, 실행, 대기, 완료) 표시프로세스 ID: 프로세스 식별 숫자 저장프로그램 카운터: 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장레지스터 정보: 프로세스가 실행될 때 사용했던 레지스터 값 저장메모리 관련 정보: 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계 레지스터 값 등 저장CPU 스케줄링 정보: CPU 스케줄링에 필요한 우선순위, 최종 실행 시간, CPU 점유 시간 등 저장 프로세스 상태오늘날 운영체제는 시분할 프로세스로 여러 개의 프로세스를 돌아가며 실행하며, 이를 위해 다섯 가지 상태를 가진다. 생성(New): PCB 생성 및 메모리에 프로그램 적재 요청. 요청 승인 시 준비 상태로 전이준비(Ready): CPU를 사용하기 위해 기다림. CPU 할당대기(Waiting): 실행 중이던 프로세스가 입출력 요청을 하면 CPU는 입출력이 완료될 때까지 기다리지 않고 이 프로세스를 대기 상태로 놓은 채 다른 프로세스를 가져와 실행한다. 대기 상태의 프로세스의 입출력 작업이 완료되면 다시 CPU 할당 기회를 주기 위해 준비 상태로 보낸다.실행(Running): 준비상태에 있는 프로세스가 CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태. 실행상태의 프로세스 개수는 CPU의 개수와 같다. 실행상태에 있는 프로세스도 부여된 시간 초과시 할당된 CPU를 빼앗긴다. 이 때 프로세스는 다시 준비 상태로 돌아간다.완료(Terminated): 프로세스가 종료된 상태. 프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거 컨텍스트 스위칭(Context Switching)프로세스 실행 중 다른 프로세스를 싱행하기 위해 실행중이던 프로세스를 저장하고 다른 프로세스의 상태값으로 교체하는 작업. CPU 점유시간 초과, I/O 요청, 다른 종류의 인터럽트 발생 시 컨텍스트 스위칭이 발생한다. 쓰레드(Thread)운영체제가 작업을 처리하는 단위는 프로세스로, 여러 작업을 요구할수록 프로세스 증가, PCB 증가 및 메모리에 각각의 코드, 데이터, 스택, 힙 영역 생성으로 컴퓨터가 느려지며 비용이 증가한다.한 개 이상의 쓰레드가 프로세스 내에 존재하며 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙 영역을 공유하며 스택은 각 쓰레드가 가지고 있다.작동 원리쓰레드 ID를 부여 및 Thread Control Block(TCB) 생성운영체제가 작업을 처리하는 단위가 프로세스에서 프로세스 내 쓰레드로 변경이제 여러 작업을 할 때 프로세스를 복사하는 것이 아닌 쓰레드를 생성프로세스와 쓰레드의 장단점안정성: 프로세스는 서로 독립적이기 때문에 하나의 프로세스에 이상이 생기더라도 다른 프로세스에는 영향이 없다. 반면 쓰레드는 자신이 속한 프로세스에 이상이 생기면 그 안에 있는 모든 쓰레드에도 문제가 생긴다.속도, 자원: 각각의 프로세스는 서로 고유한 자원을 소유(코드,데이터, 힙, 스택)하며 프로세스 간 통신을 할 때 IPC를 이용해야해 오버헤드가 크고 속도가 느리다. 반면 쓰레드는 스택을 제외한 자원을 공유하기 때문에 오버헤드가 적고 쓰레드 간 통신을 할 때 데이터를 공유할 수 있어 통신이 쉽지만 공유되는 공간에서 문제가 발생할 수 있다. CPU 스케줄링 CPU 스케줄링이란 운영체제(스케줄러)가 다음의 사항을 고려해 특정 방식으로 모든 프로세스에게 CPU를 할당/해제하는 작업이다.1. 어떤 프로세스에 CPU 리소스를 줄 것인가2. CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야 하는가 CPU 스케줄링 과정프로세스 실행 과정을 프로세스의 상태에 따라 조금 더 자세히 알아 보자.그 전에 먼저 이 과정에서 준비/대기 상태는 큐(Queue) 자료구조로 관리된다는 것을 인지하고 넘어가자. 큐(Queue) 자료구조는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In Fist Out) 방식의 자료구조이다.1. 프로그램을 실행해 프로세스와 프로세스의 정보를 담고 있는 PCB가 생성(New)되면 PBC는 준비(Ready) 상태의 다중큐에 들어가 실행되기를 기다린다.2. CPU 스케줄러는 준비 상태의 다중큐에 들어있는 프로세스 중 적당한 프로세스를 선택해 실행상태로 전환한다.3-1. 실행을 마치고 종료 시 프로세스는 완료(Terminated)된다.3-2. 하지만 프로세스가 CPU를 할당받아 실행되던 중 I/O 요청이 들어오면 대기(Waiting) 상태로 진입하는데, 이 때 I/O 작업 종류에 따라 분류된 큐(HDD, LAN, 키보드 등)로 들어가게 된다. 이 때 운영체제는 준비(Ready) 상태에 있던 다른 프로세스에 CPU를 할당해 실행시켜 CPU가 계속 일할 수 있도록 한다.4. I/O 작업 완료시 해당 큐에서 PCB를 꺼내 다시 준비(Ready) 상태의 다중큐에 위치시킨다. 이후 2번의 과정부터 다시 반복한다. 스케줄링 목표리소스 사용률: CPU 사용률 또는 I/O 디바이스 사용률 상승오버헤드 최소화공평성: 모든 프로세스에 공평하게 CPU 할당처리량: 같은 시간 내 더 많은 처리량 가지도록 함대기시간: 작업 요청 후 실제 작업 실행 전까지 대기 시간이 짧을 수 있도록응답시간: 대화형 시스템에서 사용자의 요청에 대해 빠른 응답목표 간 서로 상반되어 같이 달성할 수 없는 상황도 존재하기 때문에 사용하는 시스템에 따라 적절히 목표를 설정하여 스케줄링 한다. 회고생각보다 하루에 이해해야 할 양이 많았고, 구현 부분에서 시간이 많이 소요된다고 느꼈다. 하지만 이전까지 자료구조는 단순한 개념 중 하나라고만 생각했는데 구현을 해보니 조금 더 실체적으로 다가왔던 것 같다. 어렵다고도 생각했지만 그림과 함께 설명을 들으니 그래도 이해가 더 쉽고 빠르게 가능했다. 공부한 내용을 정리해 블로그에도 올리고, 깃헙 잔디도 심는 방식으로 발자취를 남긴 부분에서는 나 자신을 칭찬한다. 다만 지금까지는 구현할 때 알려주는 대로 따라 가고, 따라 치기만 했는데 다음에 그런 기회가 온다면 스스로 미리 구현해본다면 좋겠다고 생각했다.

알고리즘 · 자료구조･자료구조･알고리즘･운영체제

CS 전공지식 스터디 발자국 01

CS 전공지식 스터디 발자국 01 운영체제운영체제 구조커널 - 프로세스, 메모리, 저장장치 관리사용자는 GUI, CLI로 커널에 접근사용자 및 어플리케이션은 시스템 콜을 통해 커널에 접근 (커널을 보호)복잡한 하드웨어 등은 디바이스 드라이버를 설치하여 커널에 접근하여 동작컴퓨터 하드웨어와 구조메모리 내장 방식 - 메모리 위에서 프로그램을 동작CPU, 메모리, 하드디스크, 그래픽카드, 하드웨어CPU (Central Processing Unit) - ALU, Control Unit, Register메모리 종류 - RAM(Random Access Memory), ROM(Read Only Memory)컴퓨터의 부팅 과정ROM (바이오스): 주요장치 이상 확인 - MBR에 저장된 부트로더를 메모리로 가져와서 실행 - 운영체제 로드 - 프로그램은 메모리에 올라와서 운영체제가 관리프로그램 & 프로세스프로그램: 저장장치에 저장된 명령문의 집합체 (.exe)프로세스: 실행 중인 프로그램 (저장된 프로그램이 메모리에 올라갔을 때의 상태) - 능동적인 존재멀티프로그래밍 & 멀티프로세싱멀티프로그래밍: 메모리에 여러 개 프로그램이 올라온 것멀티프로세싱: CPU 관점으로 정의, CPU가 여러 개의 프로세스를 처리하는 것동시에 이용한다 (멀티프로그래밍으로 프로그램을 여러 개 올리고, 멀티프로세싱을 이용해 여러 개의 프로세스를 처리하게 됨)PCBPCB(Process Control Blcok): 연결리스트 구조, 프로세스가 만들어지면 해당 프로세스의 정보를 가지고 있는 PCB가 생성Context Switching하나의 프로세스를 실행하는 도중에 다른 프로세스를 실행하기 위해 다른 프로세스로 전환(인터럽트 발생) 원래 실행 중인 작업을 PCB에 저장하고 실행될 프로세스의 상태대로 다시 CPU 세팅 자료구조 및 알고리즘자료구조: 대량의 데이터를 효율적으로 관리할 수 있는 자료의 구조알고리즘: 문제를 해결하는 방식시간복잡도: 특정 알고리즘이 어떤 문제를 해결하는 데에 걸리는 시간어떻게 평가할까?시간을 측정하는 방식이 아닌, 코드 성능에 많은 영향을 주는 부분(반복문)을 보고 평가Big-O (최악의 경우를 평가)(ex) 배열에서 원하는 숫자를 찾는 알고리즘의 Big-O n번만에 데이터를 찾을 수 있음 → O(n)O(1), O(n), O(log n), O(n!) 등 배열인덱스로 접근하여 데이터 저장연결리스트각 Node가 서로 연결되어 있는 구조 (Head, Tail 존재)스택(LIFO)Last In First Out, 마지막으로 들어온 데이터가 먼저 나가는 구조큐(FIFO)First In First Out, 처음으로 들어온 데이터가 먼저 나가는 구조덱 (양쪽으로 삽입 삭제 가능)앞뒤로 삽입과 삭제가 가능한 구조해시테이블(Key, Value) 구조 - 해시함수를 적용하여 고유한 Index 생성

인프런 워밍업 클럽 2기 - 발자국 1주차

강의 수강운영체제 운영체제는 컴퓨터를 동작시키기 위해 존재하며, 그를 위한 CPU, 스레드, 프로그램, 프로세스, CPU 스케줄링 등에 대해서 알게 되었다. 간혹 이런이야기를 들은적 있다, 컴퓨터의 성능이 느려진다면 크롬을 의심해 봐라, 크롬은 너무 무겁다. 그래서 컴퓨터가 느려진다 싶을 때, cpu를 확인해 보면 크롬이 어마어마하게 커져있는 경우가 대부분이었다. (그리고 크롬 탭 종료🤣) 근데 사실 크롬은 무겁다라는 생각은 했지만, 그 이유는 생각해 본 적이 없었는데 이 강의를 들으면서 프로세스에 대해 생각해보면서 깨달았다. 크롬이 무거운 이유, 그럼에도 내가 크롬을 사용하는 이유. 그렇다 프로세스는 빠르니까... 그러면서 내가 프로그램을 개발한다면, 어느 방법을 사용해야할까라는 생각을 가질 수 있는 좋은 계기가 되었다. 자료구조자료구조에 대해서 배웠다. 해당 자료구조는 배열, 연결리스트, 스택, 큐, 덱, 해시테이블, 셋에 대해 학습하였으며, 해당 자료구조를 js로 구현하여 흐름을 파악하였다. 사실 알고리즘은 듣고싶은 강의는 아니였다. 어느정도 안다는 생각을 가지고 있었기 때문이었는데, 이것은 나의 자만...이었다. 들으면서 한번 더 정리할 수 있고 한번 더 생각할 수 있는 계기가 되었던 것 같다. 또한 구현해본적 없는 js로 구현하는 점이 새롭게 느껴졌다. 회고일단 미션과 발자국을 기간 내에 해냈다는 점을 칭찬하고 싶다. 잘했다 나😘다만... 금요일의 경우 당일 강의를 듣지 못하고, 주말에 대체했다는 점 아쉬웠다. 다음주에는 꼬박꼬박 강의를 듣고, 주말에는 한번 더 복습할 수 있는 시간으로 사용하면 좋겠다. 미션미션은 대체로 간단한 문제라, 배웠던 내용을 학습하면서 정리하며 적었다.다만 알고리즘의 경우 생각을 좀 해던것 같다. 조건을 토대로 어떤 알고리즘을 사용하면 좋을지 고민을 했는데, 일단 선택지를 삭제해가는 소거법으로 결론을 도출했다. 이 알고리즘은 성능이 문제가 생길 수 있고, 이 알고리즘은 이 부분보다 어느부분이 별로고, 라는 생각을 하면서 제외하면서 선택했다. 회고위의 알고리즘을 생각해면서 재밌었기 때문에 알고리즘을 좀 더 많이 파악하여, 생각할 수 있는 선택지를 늘리고 싶다.

워밍업클럽cs

인프런 워밍업 클럽 CS 2기 - 1주차 발자국

지난 일주일 동안의 강의 내용 중 일부를 발췌했습니다. 자세한 내용은 개인 노션 페이지에 타이핑했습니다.자료구조와 알고리즘자료구조: 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄 예시: 변수, 배열알고리즘: 어떤 문제를 해결하기 위한 확실한 방법자료구조에 따라 알고리즘이 달라짐. 즉, 자료구조에 많은 영향을 받음같은 자료구조더라도 여러 알고리즘이 있을 수 있음시간 복잡도: 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간특정 알고리즘의 성능을 평가할 때는 해당 알고리즘의 반복문을 보고 성능을 평가스택: First In Last Out(FILO): 먼저 들어간 데이터가 나중에 나온다.큐: First In First Out(FILO): 먼저 들어간 데이터가 먼저 나온다.덱: 데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조스택은 head에서만 처리할 수 있고, 큐는 head에서 삽입, tail에서 제거한다.해시테이블: 해시와 테이블이 합쳐진 자료구조테이블의 메모리를 적게 차지하고, 충돌이 덜 일어나도록 데이터를 골고루 분배시키는 좋은 해시 함수의 구현이 필수적운영체제커널프로세스와 메모리, 저장 장치를 관리하는 핵심적인 기능을 담당사용자는 커널에 직접 접근할 수 없으며, GUI/CLI를 통해 접근함 CPU를 구성하는 장치산술 논리 연산 장치: CPU에서 실제로 데이터 연산을 담당하는 장치제어 장치: 모든 장치들의 동작을 지시하고 제어하는 장치레지스터: CPU 내에서 계산을 위해 임시로 보관하는 장치메모리 종류램(RAM): 랜덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음. 전력이 끊기면 데이터를 잃어버리기 때문에 메인 메모리로 사용롬(ROM): 전력이 끊겨도 데이터를 계속 보관할 수 있지만, 데이터를 한번 쓰면 수정할 수 없으므로, 컴퓨터의 부팅과 관련된 바이오스를 저장하는데 주로 사용멀티프로그래밍메모리에 여러 개의 프로세스가 올라온 것 멀티프로세싱유니프로그래밍, 멀티프로그래밍을 메모리 관점에서 정의했다면, 멀티프로세싱은 CPU 관점으로 정의한 것CPU가 여러 개의 프로세스를 처리하는 것컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태 값으로 교체하는 작업컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경된다.FIFO(First In First Out)먼저 들어온 작업이 먼저 나간다는 뜻으로, 스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있다.회고잘한 점강의 계획 일정에 따라 밀리지 않고 들었다. 애매했던 개념을 잘 정리할 수 있어서 좋았다.아쉬운 점정해진 일정의 강의만 생각하다보니 생각의 유연함이나 확장이 부족했다. 주말 동안에 시간을 내서 보충했는데, 평일에 강의를 들으면서 조금만 더 시간을 투자하면 주말엔 다른 공부나 휴식하는 데 쓸 수 있을 듯하다. 목표꾸준히 강의 듣고 학습하기강의를 보면서 타이핑한 내용을 한 번만 보는 게 아니라 두 세번 보면서 이해하기이전에 배웠던 내용도 꾸준히 복습하기미션(https://inf.run/yyYhZ)미션을 해결한 과정한 주 동안의 강의 내용을 정리한 것을 보면서 미션을 해결했다. 강의에서는 나오지 않았지만, 비슷한 예시는 해당 강의를 다시 보면서 힌트를 얻었다. 회고강의와 똑같은 내용이 미션에 나오기보다, 비슷한 유형을 낸 미션이었다. 처음 만났을 땐 막막했지만, 강의 내용을 되새겨보면서 힌트를 얻을 수 있었고, 해결했다. 이후 미션에 어떤 문제가 나올지 모르겠지만, 최대한 적용할 수 있도록 강의를 한 번 보고 끝내는 게 아니라 이해할 수 있도록 노력해야겠다.

발자국･워밍업클럽･cs

[인프런 워밍업클럽 CS 2기] 1주차 발자국

1주차 학습 내용 '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 1, 2'그림으로 쉽게 배우는 운영체제' Section 1, 2, Section 3(Unit 1~4) '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 1, 2 Section 1. 개요자료구조와 알고리즘이란?자료구조데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄(ex, 변수, 배열)자료구조에 따라 처리 방법이 달라짐, 코드가 달라질 수 있음알고리즘어떤 문제를 해결하기 위한 확실한 방법한가지 자료구조에 대해서도 여러가지 알고리즘이 있을 수 있음 (ex, 표현방법에 따라) → 더 좋은 알고리즘을 사용시간 복잡도더 좋은 알고리즘이란?메모리 사용이 적은 것, 속도가 더 빠른 것 등 사용자에 따라 달라짐일반적으로 알고리즘의 속도를 성능의 척도로 사용 → 시간복잡도시간 복잡도란, 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 말함그러나 사용자마다 컴퓨터 사양이 다르기 때문에 시간을 측정하는 방식이 아닌, 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측함 → 반복문을 보고 성능 평가함표현 방법Big-Ω : 최선의 경우 한 번에 찾음Big-O : 최악의 경우 배열의 길이만큼 걸림Big-Θ : 평균의 경우 배열의 길이 중간 만큼 걸림 Section 2. 자료구조배열일반적으로 배열은 생성하게 되면 운영체제에서 배열의 크기만큼 메모리를 잡게 됨운영체제는 배열의 시작 주소만 기억하고, 배열의 index에 따라 한번에 접근하게됨배열의 참조 성능은 좋지만, 데이터의 삽입, 삭제 성능은 좋지 않음데이터 삽입 시 → 초기에 잡은 메모리 크기보다 큰 크기가 필요할 때, 그만큼의 연속된 메모리 공간을 또다시 찾아야 함. 또 기존 데이터를 복사도 해줘야 함.데이터 삭제 시 → 공간 낭비됨자바스크립트는 다른 프로그래밍 언어와 달리 배열이 연결리스트 형태로 되어 있어서 배열 생성 시 메모리가 연속적으로 있어야하는 단점을 해결함연결리스트저장하려는 데이터들을 메모리 공간에 분산해 할당하고, 이 데이터들을 서로 연결해줌 → Node를 만들어서 사용Node의 구조데이터를 담는 변수다음 노드를 가리키는 변수장점빈 메모리공간 아무 곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열에서 초기 크기를 알아야 하는 단점이 없음중간에 데이터 삽입 시, 연속된 공간 확보 필요 없이 앞, 뒤 노드의 다음을 가리키는 노드만 바꿔주면 됨단점기존 배열은 시작 주소만 알면 index에 따른 데이터의 접근이 쉽지만(O(1)), 연결리스트는 연결된 노드를 따라 접근해야함(O(n))스택(Stack)FILO(First In Last Out)데이터 삽입을 무조건 첫 번째 인덱스에 하고, 삭제 또한 첫번째 인덱스에서 함일상생활 예시엘리베이터 - 일찍타는 사람이 늦게 내리게 됨포토샵 - 작업 되돌리기 작업문법 에러 체크 시큐(Queue)First In First Out데이터 삽입을 첫 번째 인덱스에 하고, 삭제는 뒤에서부터 제거 함문제점기존 연결리스트에서 구현한 구조로는 맨 뒤의 인덱스에 접근을 하기 위해 O(n) 성능이 나옴.따라서 맨 뒤 인덱스를 가리키는 tail을 만들고, 노드에 이전 노드를 가리키는 변수를 추가해서 이중연결리스트를 만듦.O(1)의 성능으로 삭제를 할 수 있게 함일상생활 예시마트에서 줄 순서대로 계산운영체제 프로세스 처리 (FIFO 스케줄링)맛집, 놀이공원 줄덱(Deque)데이터의 삽입과 제거를 head와 tail 두군데서 자유롭게 할 수 있는 자료구조특성에 따라 스택과 큐 모두 구현할 수 있음해시테이블(Hash)프로그래밍 언어에 따라 해시, 맵, 해시맵, 딕셔너리라고도 불림배열의 공간 낭비를 줄이기 위해 어떤 계산을 거쳐 특정 공간 인덱스에 데이터를 저장하는 방법을 사용 → 어떤 계산 - 해시 함수 (ex, 선수 등번호 % 10)해시 함수에서의 충돌을 해결하기 위해 인덱스를 연결리스트로 구성해 데이터들을 연결함좋은 해시 함수는 데이터를 골고루 분배시켜주는 함수장점빠른 데이터 읽기, 삽입, 삭제 가능단점메모리를 많이 차지함해시 함수에 따라 메모리를 많이 차지할 수도 아닐 수도 있음셋(Set)데이터의 중복을 허용하지 않는 자료구조해시테이블을 사용해 Hash Set이라고 불리기도 함테이블의 value값은 사용하지 않고, key만 사용해서 구현함 '그림으로 쉽게 배우는 운영체제' Section 1, 2, Section 3(Unit 1~4) Section 1. 운영체제 들어가기운영체제 개요운영체제들개인용 컴퓨터 - Windows, MacOS대형 컴퓨터, 서버용 - 유닉스, 리눅스스마트폰, 테블릿 - iOS, Android스마트워치, 세탁기, 냉장고 - 임베디드 운영체제컴퓨터는 운영체제가 있어야 하는가?No, 그러나 원래 설계된대로만 쓸 수 있기에 기능을 추가할 수 있음 (ex, 예전 유선 전화기 vs 스마트폰)운영체제가 하는 일프로세스 관리 : 하나의 프로그램이 CPU를 독차지 하지 않고, 여러프로그램이 동시에 실행될 수 있도록 함메모리 관리 : 여러 프로그램을 메모리에서 관리함하드웨어를 관리 : 사용자의 하드웨어에 대한 직접적인 접근을 막음파일 시스템 관리 : 하드디스크에 많은 파일들의 효율적인 저장과 관리를 함운영체제 역사비싼 CPU를 더 많이 사용하려고 고민했었고, 오퍼레이터와 프로그래머 사이의 낭비되는 시간을 줄이려함 → CPU 사용률과 비용절감을 위한 노력으로 오늘날의 운영체제가 탄생함연도별 운영체제 발전애니악 출현 (1940년대)펜실베니아 대학교에서 미사일 탄도계산을 위해 개발된 컴퓨터 (세계에서 가장 큰 스케일의 전자디지털 계산기)스위치와 배선을 사람이 직접 연결함하드웨어의 비용이 비싸기 때문에 CPU를 최대한 많이 사용할 수 있는 방법에 대해 연구하게 됨직접회로(IC) 개발 (1950년도)진공관과 전선으로 만들어진 논리회로를 아주 작은 크기로 만듦 → 현대적인 컴퓨터의 모습CPU, 메모리는 있지만, 키보드와 마우스는 없음 → 프로그래머가 펀치 카드에 구멍을 뚫어서 프로그래밍을 함오퍼레이터가 직접 컴퓨터에 카드를 넣고 결과가 나오면 프로그래머에게 전달함싱글스트림 배치시스템 (1950년대 중후반)오퍼레이터 오버헤드가 커서 이를 해결하기 위해 프로그래머가 여러개의 펀치카드를 전달하고, 이를 CPU가 순서대로 처리해서 결과도 한번에 확인할 수 있도록 개발함 → CPU 사용률이 올라감I/O 디바이스 컨트롤러 개발(인터럽트) - 입출력 중에도 CPU가 계산할 수 있도록 만들어서 CPU 사용률을 더욱 높임그러나 입력의 경우 어쩔 수 없이 입력이 끝날 때까지 기다려야하기 때문에 CPU 사용률이 떨어지게 됨 → 싱글스트림 배치시스템 한계점시분할 시스템 (1960년대)메모리에 여러 프로그램을 올려놓고 시간을 나누어서 빠르게 돌아가며 실행시킴 → CPU 사용률 증가컴퓨터가 비싸기에 사용자가 여러개의 터미널을 두고 하나의 컴퓨터에 접근해서 사용 → 여러 사용자가 각자의 프로그램을 각각 사용 가능하게 됨 → 개인 컴퓨터같아져서 개인 파일을 저장하게 되면서 파일 시스템 개념이 생겨남 (AT&T 벨 연구소 - UNIX)문제점 생김메모리에 여러 프로그램이 올라와서 작업을 실행함에 따라 메모리 침범 이슈 생김여러 프로그램이 실행됨에 따라 프로그램의 메모리 위치가 변동됨 → 하드웨어적으로 베이스 레지스터를 추가하게 됨개인용 컴퓨터의 시대 (1970년대)애플 매킨토시(GUI 사용), 마이크로소프트 MS-DOS운영체제 구조커널프로세스, 메모리, 저장장치를 관리함사용자는 커널에 직접 접근할 수 없고, 인터페이스를 통해 접근 가능함인터페이스는 GUI, CLI가 있음어플리케이션은 시스템 콜을 이용해서 커널에 접근 가능 → 시스템 콜을 통해 안전하게 하드디스크 빈공간에 데이터를 저장하게 됨하드웨어는 드라이버를 이용해서 커널에 접근 가능 → 그래픽카드나 타블렛 같은 복잡한 장치들은 디바이스 드라이버를 설채해서 사용해야함컴퓨터 하드웨어와 구조폰 노이만 구조 - 프로그램 내장 방식 (프로그램을 메모리에 내장함)애니악 시절 사람이 직접 스위치와 배선을 매번 조정하던 불편함을 해결하기 위해 CPU와 메모리 사이를 버스로 연결하는 방법으로 데이터를 전달하도록 함메모리에 올라간 프로그램은 명령에 따라 처리되고, 소프트웨어만 바꿔주면 됨오늘날의 컴퓨터 하드웨어메인보드 - 다른 하드웨어 연결하는 장치CPU, 메모리, 하드디스크, 그래픽카드, 모니터, 마우스, 키보드, 스피커 등 연결CPU(Central Processing Unit)산술논리 연산장치, 제어 장치, 레지스터로 구성메모리RAM(Random Access Memory), ROM(Read Only Memory)로 구성RAM랜덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음전력이 끊기면 데이터를 잃어버림메인메모리로 사용됨ROM전력이 끊겨도 데이터를 계속 보관할 수 있음데이터를 한 번 쓰면 수정 불가능 → 따라서 컴퓨터 부팅과 관련된 바이오스를 저장하는 데에 주로 쓰임컴퓨터의 부팅과정전원 켬 → 바이오스 실행 (주요 하드웨어에 이상 여부 체크) → 이상 없을 시, 하드디스크의 마스터 부트 레코드에 저장된 부트로더를 메모리로 가져와서 실행 → 운영체제 선택 → 컴퓨터 바탕화면 보임 → 실행되는 모든 프로그램은 메모리에 올라와서 운영체제가 관리함인터럽트CPU 관점에서 입출력 완료 여부를 알 수 없기에 주기적으로 계속 체크함(Polling 방식) → 주기적으로 CPU가 체크해야하기 때문에 성능이 좋지 않음인터럽트Polling 방식의 단점을 해결한 방식입출력 관리자가 입출력이 완료되었을 때 CPU에게 신호를 주고, CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료 함인터럽트 서비스 루틴(ISR) - 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수인터럽트는 비동기적으로 동작하기 때문에 성능에 이점이 있음인터럽트 방식하드웨어 방식 - ex, 입출력소프트웨어 방식 - ex, 사용자 프로그램에서 발생한 인터럽트 (유효하지 않은 메모리 접근, 0으로 나누는 명령어) Section 2. 프로세스와 쓰레드프로그램과 프로세스프로그램하드디스크등과 같은 저장장치에 저장된 명령문의 집합체 (ex, 앱, .exe파일 등)컴퓨터 관점에서 저장장치만 사용하는 수동적인 존재프로세스실행중인 프로그램하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 실행중인 프로그램 → 프로세스라고 불림컴퓨터 관점에서 메모리, 운영체제의 CPU스케줄링 알고리즘에 따라 CPU 사용, 필요에 따라 입출력도 하기에 능동적인 존재프로세스의 구조Code, Data, Heap, Stack으로 나눠짐Code - 자신을 실행하는 코드 저장Data - 전역 변수, Static 변수 저장Stack - 지역 변수, 함수 호출 시 필요한 정보들이 저장Heap - 프로그래머가 동적으로 메모리를 할당하는 데 쓰임코드가 프로세스가 되는 과정코드(ex, C언어) → test.c → 전처리기 → test.i → 컴파일러 → test.s → 어셈블러 → test.o → 링커 → test.exe → 메모리에 올라감 → 프로세스(운영체제에 의해 관리됨)멀티프로그래밍과 멀티프로세싱유니프로그래밍 - 메모리에 오직 하나의 프로세스가 올라온 것(메모리 관점)멀티프로그래밍 - 메모리에 여러개의 프로세스가 올라온 것(메모리 관점)멀티프로세싱 - CPU가 여러개의 프로세스를 처리하는 것(CPU의 관점)오늘날의 OS는 멀티프로그래밍과 멀티프로세싱이 공존함예전에는 메모리의의 크기가 작았기 때문에 유니프로그래밍으로 멀티프로세싱 기법(메모리, 저장장치 데이터 스와핑)을 사용함PCB(Process Control Block)프로세스 생성 시, 프로세스의 정보를 가지고 있는 PCB를 만들고 저장함PCB들은 연결리스트로 저장됨운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거함PCB 구조포인터 - 부모와 자식 프로세스에 대한 포인터, 할당된 자원에 대한 포인터, 프로세스의 한 상태에서 다른 상태로 전환될 때 저장하는 포인터 가짐프로세스 상태 - 생성, 준비, 실행, 대기, 완료 나타냄프로세스 ID - 프로세스를 식별하기 위한 숫자 저장프로그램 카운터 - 다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터 저장(시분할처리로 여러 프로세스를 번갈아 실행시키기에 필요하게 됨)레지스터 정보 - 프로세스가 실행될 때 사용했던 레지스터 값들이 저장됨(프로그램 카운터와 마찬가지로 시분할처리에 필요)메모리 관련 정보 - 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기위한 경계레지스터 값 등 저장CPU 스케줄링 정보 - CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장프로세스 상태프로세스는 시분할 처리를 위한 다섯가지 상태를 가짐 : 생성, 준비, 실행, 대기, 완료생성 상태(New)PCB를 생성하고, 메모리에 프로그램 적재를 요청한 상태준비 상태(Ready)메모리에 프로그램 적재를 승인받으면 넘어오게 됨CPU를 사용하기위해 기다리고 있는 상태CPU스케줄러에 의해 CPU가 할당됨실행 상태(Running)준비상태에 있는 프로세스가 CPU스케줄러에 의해 CPU를 할당받아 실행되는 상태실행상태에 있는 프로세스의 수는 CPU의 개수만큼임부여된 시간만큼 CPU 사용 가능 → 시간이 초과되면 다시 준비상태로 돌아감대기 상태(Waiting)프로세스가 입출력 요청을 하면 입출력이 완료될 때까지 기다리는 상태완료 상태(Terminated)프로세스가 종료된 상태프로세스가 사용했던 데이터를 메모리에서 제거하고, 생성된 PCB도 제거함컨텍스트 스위칭(Context Switching)프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업PCB의 내용이 변경됨 - 실행중인 프로세스의 작업내용을 PCB에 저장하고, 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅됨컨텍스트 스위칭이 일어날 때, 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경됨컨텍스트 스위칭이 발생하는 이유CPU 점유시간이 다 됨I/O 요청이 있음다른 종류의 인터럽트가 있을 때프로세스 생성과 종료프로세스 생성 방법.exe 파일 실행 → 운영체제가 코드영역, 데이터영역을 메모리에 로드 → 빈 스택, 빈 힙을 만들어 공간 확보 → PCB 생성 및 값 초기화 (운영체제 부팅 후 0번 프로세스가 생성될 때 한 번 실행됨) → 부모 프로세스나머지 프로세스는 0번 프로세스를 복사하게 됨 (fork() 함수 이용) → 새로 생성하는 것보다 복사가 빠르기 때문 → 자식 프로세스자식 프로세스는 부모 프로세스의 코드, 데이터, 스택, PCB 내용 모두 복사함fork() → exex() 실행 시, 자식 프로세스의 코드, 데이터 영역을 원하는 값으로 덮어쓰게 됨 → 부모 프로세스와 다르게 동작함exit() → 자식 프로세스가 부모 프로세스에게 정상 종료를 알림 → 부모 프로세스가 자식 프로세스를 정리함좀비 프로세스 - 부모 프로세스가 먼저 종료되거나, 자식 프로세스가 exit()를 주지못해서 메모리에 계속 살아있는 상태쓰레드프로세스가 많아지면 PCB, 코드, 데이터, 스택, 힙영역도 만들어줘야하기 때문에 무거워짐 → 메모리 많이 차지함 → 쓰레드 고안쓰레드는 프로세스 내에 존재하는 것으로, 1개 이상 있을 수 있음PCB, 코드, 데이터, 힙영역을 공유함스택은 공유하지 않고 쓰레드마다 하나씩 가지고 있음쓰레드를 구분하기 위한 쓰레드ID, TCB(Thread Control Block) 생성프로세스, 쓰레드 장단점안정성 - 프로세스는 독립되어 있기에 다른 프로세스 문제에 영향을 받지 않음, 프로세스는 영향을 받음속도, 자원 - 프로세스는 각자 코드, 데이터, 힙, 스택을 가지고 있고 프로세스간 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느림, 프로세스는 스택영역을 제외한 영역은 모두 공유하기 때문에 오버헤드가 작음. 그러나 공유되는 공간에서 문제가 생길 수도 있음 Section 3. CPU 스케줄링 - (Unit 1~4)CPU스케줄링 개요컴퓨터 자원필수 장치 - CPU, 메모리주변 장치 - HDD, 키보드, 마우스CPU스케줄링운영체제가 모든 프로세스에게 CPU를 할당/해제 하는 것CPU가 스케줄링에서 고려할 사항어떤 프로세스에게 CPU 리소스를 줄 것인가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?CPU BurstCPU를 할당받아 실행하는 작업I/O Burst입출력 작업다중큐프로세스 상태에서 준비상태, 대기상태는 큐(Queue)라는 자료구조로 관리됨실행 → 준비 상태가 될 때, 운영체제는 그에 맞는 준비 큐에 넣음실행 → 대기 상태가 될 때, I/O 작업 종류에 따라서 분류된 큐에 들어가게 됨 (ex, 하드디스크 작업 → HDD 큐)정확히는 프로세스 정보를 가지고 있는 PCB가 들어가게 됨스케줄링 목표리소스 사용률CPU 사용률 높이기, I/O 디바이스의 사용률 높이기 등등오버헤드 최소화스케줄링을 하기 위한 계산이 너무 복잡해지거나, 컨텍스트 스위칭을 너무 자주하지 않도록공평성모든 프로세스에게 공평하게 CPU가 할당되어야 함공평의 의미는 시스템에 따라 달라질 수 있음처리량같은 시간 내에 더 많은 처리를 할 수 있는 방법대기 시간작업을 요청하고 실제 작업이 이루어지기 전까지 대기 시간이 짧은 것을 목표로 함응답 시간대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하기 때문에 응답시간이 짧은 것을 목표로 함목표간에 서로 상반되는 상황이 있는데, 이 때는 사용자가 사용하는 시스템에 따라 목표를 다르게 설정하게 됨 (ex, 터치스크린 → 응답시간 짧도록, 과학 계산 → 처리량이 높도록 초점 맞춤)FIFO(First In First Out)스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있음장점단순하고 직관적단점한 프로세스가 완전히 끝나야 다음 프로세스가 시작되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함I/O 작업이 있다면 끝날 때까지 쉬고있기 때문에 CPU 사용률이 떨어지게 됨스케줄링의 성능 → 평균 대기 시간으로 평가함프로세스의 실행 순서만 바꿔도 평균 대기 시간의 차이가 많이 남FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기 때문에 현대 운영체제에서 잘 쓰이지 않고, 일괄처리시스템에 쓰임 회고일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점칭찬하고 싶은 점 : 바쁜 일정 중에도 이번주 범위를 전체적으로 두 번 반복해서 강의를 들으면서 놓친 부분은 없는지 확인했던 점입니다.아쉬웠던 점 : 강의를 듣고 잘 이해했다고 생각했는데, 내 스타일로 아직 명확하게 정리가 되지 않아서 미션 수행 시 조금 당황했던 점입니다.보완하고 싶은 점 : 강의를 듣고 강의 내용에 대해 머릿속으로 정리해보는 시간을 좀 더 가지면 좋을 것 같습니다.다음주에는 어떤 식으로 학습하겠다는 스스로의 목표다음주에는 오늘 범위의 강의를 듣기 전에 어제 범위의 강의를 머릿속으로 다시 생각하고 정리하는 시간을 갖겠습니다.

알고리즘 · 자료구조･알고리즘･자료구조･운영체제

[인프런 워밍업 클럽 2기 CS] 1주차 미션

운영체제 1.while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?이러한 경우에는 인터럽트 방식을 사용하는 것이 적합합니다. 스킬이 활성화될 때만 시스템에 알림이 가므로, 지속적인 폴링 없이 효율적으로 이벤트를 처리할 수 있습니다. 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램 : 실행 가능한 코드가 저장된 정적인 파일프로세스 : 실행 중인 프로그램의 인스턴스. 메모리에 로드되어 실행되는 동적인 개체 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍 : 단일 CPU에서 여러 프로그램을 번갈아 실행하여 CPU 사용률을 높이는 기법멀티프로세싱 : 여러 CPU나 코어를 사용하여 실제로 여러 작업을 동시에 처리하는 기법 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 프로세스 제어 블록(Process Control Block, PCB)을 사용하여 프로세스를 관리합니다. PCB는 프로세스의 상태, 프로그램 카운터, 레지스터 등의 정보를 포함합니다. 5. 컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭은 현재 실행 중인 프로세스의 상태를 저장하고, 다음에 실행할 프로세스의 상태를 복원하는 과정입니다. 이를 통해 여러 프로세스를 번갈아 실행할 수 있습니다. 자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시 테이블 사용이 적합합니다.빠른 검색 속도: 학생 ID나 이름으로 O(1) 시간 복잡도로 정보 검색 가능효율적인 삽입과 삭제: 새로운 학생 추가나 졸업생 삭제도 O(1) 시간 복잡도로 가능유연성: 학생별로 다양한 정보를 키-값 쌍으로 저장 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐(Queue) 자료구조를 선택하는 것이 적합합니다.FIFO(First-In-First-Out) 원칙: 큐는 먼저 들어온 주문이 먼저 처리되는 FIFO 방식을 자연스럽게 구현간단한 구조: 간단한 주문 추가(enqueue)와 처리(dequeue) 연산공정성: 모든 주문이 들어온 순서대로 처리효율성: O(1) 시간 복잡도를 가지는 주문 추가와 처리 과정

알고리즘 · 자료구조･인프런･인프런워밍업클럽･CS･운영체제･자료구조･알고리즘･감자･1주차

[인프런 워밍업클럽 CS 2기] 1주차 미션

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?: 플레이어가 스킬을 사용했을 때 콜백을 받는 방식(비동기 프로그래밍 이벤트 처리)으로 문제를 해결할 수 있습니다.프로그램과 프로세스가 어떻게 다른가요?: 프로그램은 앱, .exe파일과 같은 저장장치에 저장된 명령문의 집합체이고, 프로세스는 프로그램이 메모리에 올라갔을 때 실행중인 프로그램입니다. 그래서 컴퓨터 관점에서 보면 프로그램은 저장장치만 사용하는 수동적인 존재이고, 프로세스는 운영체제의 CPU 스케줄링 알고리즘에 따라 CPU도 사용하고, 필요에 따라 입출력도 하기에 능동적인 존재라고 볼 수 있습니다.멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?: 멀티프로그래밍은 메모리 관점에서 메모리에 여러개의 프로세스가 올라온 것이고, 멀티프로세싱은 CPU의 관점에서 CPU가 여러개의 프로세스를 처리하는 것입니다.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?: 프로세스 생성 시, 프로세스의 정보를 가지고 있는 PCB를 만들고 저장합니다.PCB들은 연결리스트로 저장되고,운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거합니다.컨텍스트 스위칭이란 뭔가요?: 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 교체하는 작업입니다.좀 더 정확하게는 PCB의 내용이 변경되는 것으로 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경됩니다.컨텍스트 스위칭은CPU 점유시간이 다 되거나,I/O 요청이 있을 때, 또는다른 종류의 인터럽트가 있을 때 발생하게 됩니다. 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.: 학번을 key값으로 가지는 해시테이블을 선택할 것입니다. 학생이 전학가거나 오는 상황에 있어 고정된 크기를 가지는 배열보다는 동적으로 크기 조정이 가능한 해시테이블이 유연합니다.또한 해시테이블은 학번을 key값으로 사용하여 검색 시, 시간 복잡도 O(1)을 가지기 때문에 학생정보를 빠르게 검색할 수 있습니다.만약 동일한 해시값을 갖는다면, 연결리스트 사용 등으로 충돌을 해결할 수 있습니다.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.: 큐(Queue)를 선택할 것입니다. First In First Out의 특성을 가지는 자료구조로 들어온 순서대로 처리되는 주문에 적합하다고 생각합니다. 회고강의를 들을 때는 끄덕끄덕하며 다 이해되었다고 생각했는데, 막상 미션을 해결하려니 정리해서 작성하기에 조금 어려웠고, 또 가물가물한 부분도 있어 당황하기도 하였습니다. 그래서 다시 정리해뒀던 것을 찾아보며 미션을 하게 되었는데, 앞으로 일주일마다 제가 작성했던 발자국과 미션을 반복적으로 보면서 복습해야겠다고 생각하게 되었습니다.

알고리즘 · 자료구조･알고리즘･자료구조･운영체제

워밍업클럽CS2기 1주차 발자국: 자료구조

자료구조 개요자료구조와 알고리즘이란?자료구조데이터가 어떤 구조로 저장되고 어떻게 사용되는지 나타냄ex) 변수, 배열자료구조에 따라 처리방법이 달라지고 코드가 단순해질 수 있음알고리즘어떤 문제를 해결하기 위한 확실한 방법자료구조 영향을 많이 받고 같은 자료구조라도 알고리즘이 달라질 수 있음시간 복잡도특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간일반적으로 성능의 척도는 알고리즘 속도로 평가됨알고리즘을 평가할 때는 코드에서 성능에 영향을 많이 주는 부분을 찾아 실행시간을 예측함 => 반복문최선의 경우: Big - 오메가 최악의 경우: Big -O 평균의 경우: Big- 세타빅 오 표기법입력이 늘어날 때 계산이 늘어가는 척도를 나타냄자료구조배열인덱스 참조는 길이에 상관없이 한 번에 가져오기 때문에 O(1) 성능읽기, 쓰기, 참조에서 좋은 성능을 보임 크기 예측이 힘들어 메모리 낭비가 발생하기 때문에 데이터 삽입, 삭제 성능이 안좋음연결리스트필요한 데이터만큼 노드를 만들어 저장하고 다른 노드를 연결함첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근이 가능함저장하려는 데이터들을 메모리 공간에 분산해서 할당하고 이 데이터들을 서로 연결하는 노드를 활용하여 배열의 단점을 해결함배열과 연결리스트 비교배열은 시작주소만 알면 인덱스를 활용하여 뒤에 있는 데이터 접근이 쉬움연결리스트는 데이터들이 전부 떨어져있어 바로 접근할 수 없지만 배열 초기 크기를 몰라도 됨데이터 삽입 삭제가 자주 일어난다면 연결리스트, 참조가 자주 일어난다면 배열스택First In Last Out먼저 들어간 데이터가 나중에 나오는 규칙데이터 삽입과 제거를 무조건 첫번째 인덱스에 지정하면 연결리스트로 스택 구현 가능큐First In First out먼저 들어간 데이터가 먼저 나오는 규칙FIFO 스케줄링운영체제가 프로세스 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 처리함덱데이터 삽입과 제거를 head과 tail 두 군데서 자유롭게 할 수 있음덱을 이용하면 스택과 큐를 전부 구현 가능해시테이블해시와 테이블이 합쳐진 구조로 메모리 낭비를 줄이기 위해 어떤 계산을 하는 함수인 해시함수로 테이블의 인덱스를 새로 만듦읽기, 삽입, 수정, 삭제 O(1) 성능장점: 빠른 데이터 읽기, 삽입, 삭제단점: 공간 효율성이 좋지 않음, 해시함수에 따라 메모리 사용이 달라 좋은 해시함수가 필요함

알고리즘 · 자료구조･인프런워밍업클럽･자료구조･CS

[인프런 워밍업클럽 CS 2기] 1주차 발자국

자료구조와 알고리즘자료구조 : 데이터를 효율적으로 저장하고 관리하는 방법. 배열, 연결리스트, 스택, 큐, 트리, 그래프 등이 있다. 알고리즘 : 어떤 문제를 해결하기 위해 정해진 일련의 절차나 규칙을 의미하며, 주어진 입력에 대해 결과를 도출하는 과정이다. 시간 복잡도 : 알고리즘이 수행되는 데 걸리는 시간을 입력 크기에 대한 함수로 표현한 것. 주로 O(1), O(n), O(n²) 등의 표기법으로 나타낸다. 배열 : 고정된 크기의 연속된 메모리 공간에 데이터를 저장하는 자료구조. 인덱스를 통해 빠르게 접근할 수 있지만 크기가 고정되어 있으며 중간에 데이터를 삽입하거나 삭제하는 데는 비효율적이다. 시간 복잡도: 접근 O(1), 삽입/삭제 O(n) 연결 리스트(Linked List) :각 노드가 데이터와 다음 노드의 주소를 가지는 동적 자료구조. 삽입과 삭제가 용이하지만,특정 위치에 접근하려면 순차적으로 접근해야 하므로 시간이 더 걸린다.시간 복잡도: 접근 O(n), 삽입/삭제 O(1)export class Node{ constructor(data, next = null){ this.data = data; this.next = next; } } // * 연결 리스트 추상 자료형 // 1. 모든 데이터 출력 -> printAll(); // 2. 모든 데이터 제거 -> clear(); // 3. 원하는 인덱스에 데이터를 삽입 -> insertAt(index, data); // 4. 마지막 데이터 뒤에 데이터를 삽입 -> insertLast(data); // 5. 원하는 인덱스에 데이터를 삭제 -> deleteAt(index); // 6. 마지막 데이터를 제거 -> deleteLast(); // 7. 원하는 인덱스에 있는 데이터 읽기 -> getNodeAt(index); export class LinkedList { constructor(){ // 연결 리스트의 시작 Node를 가리킨다. this.head = null; // 총 저장된 Node의 수 this.count = 0; } /** * 원하는 인덱스에 데이터를 삽입 * @param {number} index - 삽입할 위치 index * @param {any} data - 삽입할 데이터 */ insertAt(index, data){ // 예외 처리 if(index > this.count || index < 0) throw new Error('범위를 넘어갔습니다.'); // 새로운 Node 생성 let newNode = new Node(data); if(index === 0){ // 리스트의 가장 앞부분에 삽입할 경우 // 1. 생성된 Node의 next가 head를 가리키도록 설정 newNode.next = this.head; // 2. 생성된 Node를 head로 설정 this.head = newNode; }else{ // 앞부분 삽입을 제외한 원하는 인덱스에 삽입할 경우 // head에서 부터 시작하기 때문에 head로 초기화 let currentNode = this.head; // 목표 인덱스 바로 전까지 next를 이용해 currentNode를 이동시킨다. for(let i=0; i<index -1; i++){ currentNode = currentNode.next; } // 1. 새로운 Node가 currentNode의 next Node를 가리키도록 설정 newNode.next = currentNode.next; // 2. currentNode가 새로운 Node를 가리키도록 설정 currentNode.next = newNode } // 새로운 Node가 삽입되었으니 count를 증가 this.count++; } /** * 모든 데이터 출력 * @returns {string} - 모든 Node의 data를 하나의 문자열에 담아 반환 */ printAll(){ let currentNode = this.head; let text = '[' while(currentNode){ text += currentNode.data currentNode = currentNode.next; if(currentNode) text += ', '; } text += ']'; console.log(text); return text; } /** * 모든 데이터 제거 */ clear(){ this.head = null; // head 초기화 this.count = 0; // count 초기화 } /** * 마지막 데이터 뒤에 데이터를 삽입 * @param {any} data - 삽입할 데이터 */ insertLast(data){ this.insertAt(this.count, data); } /** * 원하는 인덱스에 데이터를 삭제 * @param {number} index - 제거할 위치 index * @return {{data: number, next: {data: number, next: any} | null}} - 제거된 노드의 데이터와 그 다음 노드에 대한 정보. */ deleteAt(index){ // 예외 처리 if(index >= this.count || index < 0) throw new Error('제거할 수 없습니다.'); let currentNode = this.head; if(index === 0){ // 리스트의 가장 앞부분에 제거할 경우 // 반환하기 위해 삭제된 Node를 저장 const deleteNode = this.head; // head를 다음 Node인 head.next로 설정 this.head = this.head.next; // 제거했으므로 count를 내린다. this.count--; // 삭제한 Node 반환 return deleteNode; }else{ // 리스트의 가장 앞부분을 제외한 위치를 제거할 경우 // 제거할 Node 이전 Node까지 순회해 제거할 Node의 이전 Node를 가리키게 한다. for(let i=0; i<index -1; i++){ currentNode = currentNode.next; } // currentNode.next가 참조하고 있는 다음 Node 즉, 제거해야 할 Node를 저장 let deleteNode = currentNode.next; // 제거할 Node의 next Node를 가리키게 한다. currentNode.next = currentNode.next.next; // 제거했으므로 count를 내린다. this.count--; // 삭제한 Node 반환 return deleteNode; } } /** * 마지막 데이터를 제거 * @return {{data: number, next: {data: number, next: any} | null}} - 제거된 노드의 데이터와 그 다음 노드에 대한 정보. */ deleteLast(){ return this.deleteAt(this.count - 1); } /** * 원하는 인덱스에 있는 데이터 읽기 * @param {number} index - 읽고자하는 Node의 index * @return {{data: number, next: any}} - 해당 Node 반환 */ getNodeAt(index){ // 예외 처리 if(index >= this.count || index < 0) throw new Error('범위를 넘어갔습니다.'); let currentNode = this.head; // currentNode가 해당 index까지 순회한다. for(let i=0; i< index ; i++){ currentNode = currentNode.next; } // 최종적으로 이동한 Node를 반환 return currentNode; } } 스택(Stack) :후입선출(LIFO: Last In, First Out) 방식의 자료구조. 마지막에 추가된 요소가 먼저 제거된다. 함수 호출, 되돌리기 기능 등에서 사용된다.시간 복잡도: 접근/삽입/삭제 O(1)import { LinkedList } from './../LinkedList/LinikedList.mjs'; // * 스택의 추상자료형 // 1. 데이터 삽입 -> push(); // 2. 데이터 제거 -> pop(); // 3. top에 있는 데이터 참조 -> peek(); // 4. 스택이 비었는지 체크 -> isEmpty(); export class Stack{ constructor(){ this.list = new LinkedList(); } push(data){ this.list.insertAt(0, data); } pop(){ try { return this.list.deleteAt(0); } catch (error) { return null; } } peek(){ return this.list.getNodeAt(0); } isEmpty(){ return this.list.count === 0; } } 큐 (Queue):선입선출(FIFO: First In, First Out) 방식의 자료구조. 먼저 들어온 데이터가 먼저 처리된다. 대기열, 주문 처리 등 순차적으로 처리해야 할 때 사용된다.시간 복잡도: 접근/삽입/삭제 O(1) import { DoublyLinkedList } from "./DoublyLinkedList.mjs"; // * 기존에 구현한 Node에서 이전 Node도 가리킬 수 있도록 Node를 수정 // * 기존의 LinkedLst를 연결 리스트의 끝을 가리킬 수 있도록 수정 -> DoublyLinkedList // * 큐의 추상자료형 // 1. 데이터 삽입 -> enqueue(); // 2. 데이터 제거 -> dequeue(); // 3. 데이터 참조 -> front(); // 4. 큐가 비었는지 확인 -> isEmpty(); class Queue{ constructor(){ this.list = new DoublyLinkedList(); } enqueue(data){ this.list.insertAt(0, data); } dequeue(){ try{ return this.list.deleteLast(); } catch(e){ return null; } } front(){ return this.list.tail; } isEmpty(){ return (this.list.count == 0); } } export {Queue}; 운영체제폴링 방식 : 주기적으로 상태를 확인하는 방식.인터럽트 : 외부나 내부에서 발생하는 사건이 CPU의 주의를 끌어 현재 작업을 중단하고 즉시 그 사건을 처리하도록 하는 메커니즘.프로그램과 프로세스 :프로그램: 실행되지 않은 상태의 정적 코드. 하드디스크 등에 저장된 명령어 집합. 프로세스: 실행 중인 프로그램. 운영체제에서 메모리와 CPU 등의 자원을 할당받아 실행되는 단위.PCB : 프로세스 제어 블록으로, 운영체제가 프로세스를 관리하기 위한 정보(프로세스 상태, 프로그램 카운터, 메모리 정보 등)를 담고 있는 구조체.프로세스 : 실행 중인 프로그램으로, CPU와 메모리 자원을 할당받아 동작하며 독립적인 실행 단위를 형성한다.컨텍스트 스위칭: 하나의 프로세스나 스레드가 CPU에서 실행되다가 다른 프로세스로 전환될 때, 현재 프로세스의 상태를 저장하고 새로운 프로세스의 상태를 복구하는 과정.

알고리즘 · 자료구조･워밍업클럽･CS

[인프런 워밍업 클럽 2기 - CS] 1주차 미션

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?인터럽트 방식을 사용하는게 좋을 것 같습니다.인터럽트는 비동기적으로 동작하기 때문에 성능을 개선할 수 있는 이점이 있습니다.이와 같이 인터럽트를 사용하면 폴링 방식보다 더 효율적으로 스킬 사용 여부를 체크할 수 있으며,CPU 자원을 보다 효과적으로 활용할 수 있습니다. 프로그램과 프로세스가 어떻게 다른가요? 프로그램: 저장장치에 저장된 실행 가능한 코드(정적 개체)입니다.실행되기 전까지는 하드디스크나 메모리에만 존재하는 단순한 명령어 집합입니다.프로세스: 프로그램이 메모리에 적재되어 실행되고 있는 상태(동적 개체)입니다.프로세스는 운영체제에 의해 메모리, CPU 등 자원을 할당받고 실행됩니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍: 여러 프로그램이 메모리에 동시에 적재되어 실행되도록 하는 기법입니다.하나의 CPU가 각 프로그램을 번갈아가며 실행하는 방식입니다.즉, 프로그램 간 자원을 효율적으로 나누는 것을 목표로 합니다.멀티프로세싱: 둘 이상의 CPU(또는 코어)를 사용하는 기법으로, 여러 프로세스가 동시에 실행됩니다.각 프로세스는 독립된 CPU에서 병렬적으로 실행되므로 성능이 더 뛰어납니다. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요? 운영체제는 프로세스를 효율적으로 관리하기 위해 프로세스 제어 블록(PCB)을 사용합니다.PCB에는 프로세스의 상태, 메모리 정보, 프로그램 카운터, 레지스터 정보 등 프로세스의 실행 상태를 저장하고 있습니다.운영체제는 PCB를 기반으로 프로세스를 생성, 관리, 스케줄링합니다. 컨텍스트 스위칭이란 뭔가요? 컨텍스트 스위칭은 운영체제가 CPU에서 실행 중인 프로세스를 다른 프로세스로 교체할 때 발생하는 과정입니다. 실행 중이던 프로세스의 상태(레지스터, 프로그램 카운터 등)를 저장하고, 새로 실행할 프로세스의 상태를 복구하는 과정이 포함됩니다. 컨텍스트 스위칭은 프로세스나 스레드 간 전환을 가능하게 하지만, 빈번하게 발생하면 성능에 부담이 될 수 있습니다. 자료구조와 알고리즘여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?이유를 함께 적어주세요. 연결 리스트(Linked List) 자료구조를 사용하겠습니다.그 이유는 학생 정보가 추가되거나 삭제될 때 효율적으로 처리할 수 있기 때문입니다.배열과 달리, 연결리스트는 중간에 있는 학생 정보를 쉽게 추가하거나 삭제할 수 있어 유연한 데이터 관리를 할 수 있기 때문입니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다.주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요?이유를 함께 적어주세요. 큐(Queue) 자료구조를 사용하겠습니다.큐는 선입선출 방식으로 동작하는 자료구조로, 먼저 들어온 주문이 먼저 처리되도록 보장하므로 이는 실제 주문 시스템에서 자연스러운 흐름을 구현할 수 있기 때문입니다.

알고리즘 · 자료구조･워밍업클럽･CS

워밍업클럽CS2기 1주차 발자국: 운영체제

운영체제 운영체제 들어가기운영체제 개요운영체제가 하는 일프로세스 관리메모리 관리하드웨어 관리파일 시스템 관리 운영체제의 구조커널프로세스와 메모리, 저장장치를 관리하는 운영체제 핵심기능을 담당사용자는 운영체제 커널에 직접 접근할 수 없고, GUI나 CLI 등 인터페이스를 통해 접근 가능하다.시스템콜사용자로부터 커널을 보호하기 위한 인터페이스시스템 콜을 통해서 어플리케이션 접근사용자와 어플리케이션은 커널과 인터페이스로 시스템콜을 사용함드라이버하드웨어와 커널의 인터페이스ex) 디바이스 드라이버컴퓨터 하드웨어와 구조버스데이터를 전달하는 통로로 cpu와 메모리를 연결함메인보드하드웨어를 연결하는 장치메인보드의 버스가 장치 간의 데이터 전송을 담당CPU중앙처리장치로 ALU(산술논리연산장치), 제어장치, 레지스터 등으로 구성되어있다. 레지스터계산을 위해 데이터를 임시로 보관하는 장치RAM저장된 위치와 상관없이 읽는 속도가 같음.전력이 끊기면 데이터 손실메인 메모리로 사용한다.ROM전력이 끊겨도 데이터 손실 없다.데이터를 한 번 쓰면 수정이 불가함.바이오스 저장용컴퓨터의 부팅과정전원버튼을 누른다.ROM에 저장된 바이오스를 시작한다.하드웨어 이상 유무 체크부트로더 실행운영체제 메모리로 불러옴인터럽트폴링 방식 단점 해결CPU는 명령을 내리고 완료되면 신호를 받아 인터럽트 서비스 루틴을 작업시켜 작업을 완료함.인터럽트 서비스 루틴은 특정 인터럽트가 들어오면 인터럽트를 처리하는 함수로 비동기적으로 동작하여 성능에 이점이 있음. 프로세스와 쓰레드프로그램과 프로세스프로그램저장장치에 저장된 명령문의 집합체로, 저장장치만 사용하는 수동적인 존재프로세스하드디스크에 저장된 프로그램이 메모리에 올라간 상태로, 실행중인 프로그램메모리, CPU 스케줄링 알고리즘에 따라 CPU도 사용, 입출력 하는 능동적인 존재CODE, DATA, HEAP, STACK 영역으로 나누어짐CODE 영역 : 실행하는 코드 저장DATA 영역: 전역변수와 정적 변수 저장HEAP 영역: 런타임 시 할당할 수 있는 공간 (동적으로 메모리 할당)STACK 영역: 지역변수와 함수호출 했을 때 필요한 정보 (매개변수와 돌아갈 주소) 저장컴파일 과정전처리기 -> 매크로로 정의한 숫자 치환 및 필요한 파일 불러옴컴파일러 -> 어셈블리어로 변환어셈블리어 -> 기계어로 변환링커 -> 링킹 : 여러가지 라이브러리나 다른 소스코드로 연결.exe로 만들어짐메모리에 올라가는 프로그램이 되어 프로세스가 됨 -> 운영체제에 의해 관리 멀티프로그래밍과 멀티프로세싱유니프로그래밍메모리에 프로세스 1개멀티프로그래밍메모리에 여러개 프로세스멀티프로세싱CPU가 여러개의 프로세스를 처리함메모리가 작았던 과거에는 스와핑 활용스와핑: 메모리에 있는 데이터를 다른 저장장치로 보내고 다른 저장장치에서 메모리에 올림 PCB프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장함연결리스트 자료구조로 저장됨프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거함구조 : 프로그램카운터, 레지스터 정보 등프로세스 상태생성상태: PCB를 생성하고 메모리에 프로그램 적재 요청 -> 승인준비상태: CPU 스케줄러에 의해 CPU 할당실행상태: 실행상태에 있는 프로세스의 수는 CPU 갯수 -> (초과 시 강제로 뺏고 준비상태로 돌아감)인터럽트: CPU가 명령어를 수행하다 자신이 처리할 수 없는 명령이면 스스로 인터럽트를 건다. -> CPU는 하던 일을 멈추고 해당 인터럽트를 처리하려고 함대기상태: 입출력 요청 시 완료될 때까지 기다림완료상태: 프로세스 종료, 사용한 데이터 메모리에서 제거, 생성된 PCB 제거컨텍스트 스위칭프로세스 실행 중 다른 프로세스를 실행하기 위해 실행중인 프로세스 상태 저장, 다른 프로세스의 상태값으로 교체CPU 점유시간이 끝났거나, I/O 요청이 있거나 인터럽트가 있을 때 발생컨텍스트 스위칭 하는 상황프로세스 A의 점유 시간동안 실행 -> 초과 -> 인터럽트 발생 -> CPU 레지스터 값 등을 PCB A 저장 -> 프로세스 B 레지스터 값을 세팅 -> 프로그램 카운터(명령어 주소를 가지고 있음) 를 가지고 있어 명령어 바로 실행 가능 -> 프로세스 B 시간초과 -> 인터럽트 발생 -> 다시 프로세스 A 실행 프로세스 생성과 종료프로세스 생성운영체제 부팅 후 0번 프로세스가 생성될 때 딱 한 번 실행됨다른 프로세스(자식 프로세스)들은 fork() 함수를 사용하여 0번 프로세스(부모 프로세스)의 코드영역, 데이터 영역, 스택영역 등 PCB 내용 모두 복사해서 사용 => 생성보다 복사가 빠름 과정: .exe 파일 클릭 -> 운영체제는 프로그램의 코드영역과 데이터 영역을 메모리에 로드, 빈 스택과 빈 힙을 만들어 공간 확보 -> 관리하기 위한 PCB 생성 후 값 초기화프로세스 종료컴퓨터 껐다 키면 메모리가 초기화됨 쓰레드쓰레드는 프로세스 내부에 위치, 프로세스 내의 쓰레드 : 운영체제가 작업을 처리하는 단위한 프로세스 내의 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙 영역을 공유함 장단점안정성(프로세스 > 쓰레드)프로세스는 독립적으로 하나의 프로세스에 문제 생겨도 다른 프로세스는 영향 없음, 쓰레드는 해당 프로세스에 문제가 생기면 프로세스 내부의 모든 쓰레드에 영향있음.속도와 자원프로세스 간 통신은 오버헤드가 크고 속도가 느림스레드는 오버헤드가 작고 쉽게 공유할 수 있으나 공간에 문제가 생길 수 있음 CPU 스케줄링CPU 스케줄링 개요CPU 스케줄링운영체제는 모든 프로세스에게 CPU를 할당 및 해제하는 행위컴퓨터 성능에 큰 영향을 미침다중큐프로세스 정보를 담고 있는 PCB는 준비상태의 다중큐에 들어가서 실행되기를 기다리고 CPU 스케줄러에 의해 실행상태로 전환됨CPU 스케줄러는 준비상태의 다중큐를 참조하여 어떤 프로세스를 실행시킬지 결정스케줄링 목표사용자가 사용하는 시스템에 따라 스케줄링 목표가 달라짐FIFOFirst In First Out : 먼저 들어온 작업이 먼저 나간다스케줄링 큐에 들어온 순서대로 CPU를 할당 받음 -> 먼저 들어온 프로세스 종료 후 다음 프로세스 실행장점단순함, 직관적단점한 프로세스가 끝나야 프로세스가 시작됨실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업이 끝날 때까지 기다려야함 => 평균 대기 시간이 길어지면서 스케줄링 성능이 안 좋을 수 있음.

알고리즘 · 자료구조･인프런워밍업클럽･운영체제･CS

[CS스터디] 1주차 발자국

강의https://www.inflearn.com/course/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EB%B3%B8https://www.inflearn.com/course/%EB%B9%84%EC%A0%84%EA%B3%B5%EC%9E%90-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C자료구조와 알고리즘배열스택 (LIFO)컴퓨터 ctrl+z같이 되돌리기 작업 문법 검사 (같은 괄호 만나면 스택에서 꺼내기) Push, pop, peek, isEmpty -> 연결리스트로 구현 큐(FIFO) Head, tail 변수 두개로 양방향 조회 기능 CurrentNode 바꿔줘야 함 Enqueue, dequeue, front, isEmpty -> 이중연결리스트로 구현 운영체제구조커널 : 직접 접근 안됨인터페이스 : 커널에 접근 (gui, cli)시스템콜: 어플리케이션이 커널을 사용하기 위한 인터페이스드라이버: 하드웨어가 커널을 사용하기 위한 인터페이스 하드웨어와 구조메인보드: 하드웨어 연결, 버스가 연결해줌Cpu제어장치(Control Unit)산술논리연산장치 (ALU) : 실제로 연산하는 장치레지스터 : 연산하기 위해 잠시 저장; 변수라고 생각하면 된다 메모리 RAM : 메인 메모리, 임시, 속도 동일하게 데이터 조회ROM : 영구, 부팅 관련 데이터(바이오스) 연결단자: 스피커, 모니터, 키보드 등 인터럽트폴링 방식 : 주기적으로 cpu가 확인 -> 성능 안좋음인터럽트 방식: ISR(인터럽트 서비스 루틴) 실행, 비동기적으로 동작 -> 성능 좋음 하드웨어 방식 : 하드웨어 입출력소프트웨어 방식 : 유효하지 않은 메모리에 접근, 0으로 나누는 명령어 등 프로그램과 프로세스프로그램 : 애플리케이션, .exe프로세스: 실행중인 프로그램 하드웨어에 있는 프로그램이 RAM메모리에 올라갔을 때 실행 중인 프로그램 Code : 실행하는 코드 저장Data : 전역, static변수Heap: 지역변수, 함수호출시 필요한 정보 Stack : 사람이 동적으로 할당할 수 있는 공간 (malloc, free등) 멀티프로그래밍과 멀티 프로세싱멀티프로그래밍: 여러 개의 프로세스에 여러 개의 프로그램이 올라 온 것멀티프로세싱: CPU가 여러 개의 프로세스를 처리하는 것 (시분할) PCB (Process Control Block): 멀티 프로세싱을 위해서 OS는 해당 프로세스의 정보를 가지고 있는 것연결리스트로 저장 프로세스 종료시 PCB를 연결리스트에서 제거 포인터, 프로세스 상태, 프로세스ID, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보, CPU스케줄링정보 등… 프로세스 상태시분할 -> 여러 프로세스를 돌아가며 실행, 속도가 빨라서 동시처럼 보이지만 한번에 한 프로세스밖에 실행할 수 있음생성 : PCB생성 후 메모리에 프로그램 적재 요청 준비 : CPU 사용을 기다리고 있음, CPU 스케줄러에 의해 할당됨, 대부분의 상태로 존재실행 : 준비 상태에 있는 프로세스가 CPU를 할당받아 실행되는 상태, CPU개수만큼 실행할 수 있음, 할당받은 시간이 끝나면 준비상태로 돌아감대기 : 프로세스가 입출력 요청을 하면 입출력이 완료될때까지 기다림, 대기 상태에 두고 다른 프로세스를 실행 상태가 될 수 있음 -> 입출력이 느리기 때문에 효율적 완료 : 프로세스가 종료, PCB제거 컨텍스트 스위칭A 프로세스를 실행하는 중에 다른 B 프로세스를 실행하기 위해 실행 중이였던 A 프로세스 상태를 저장하고 다른 B 프로세스의 정보를 가져오는 상황이때 PCB(상태 저장하는 곳) 내용이 변경 됨 프로세스 할당 시간 끝남운영체제는 인터럽트를 발생시킴현재 CPU의 레지스터 값을 PCB A에 저장PCB B에 있는 값으로 CPU 레지스터 세팅프로그램 카운터(PC) 정보 포함: 다음 실행할 명령어의 주소 -> 바로 B실행 가능 B의 할당 시간 끝남인터럽트 발생B의 상태를 PCB B에 저장PCB A에서 A의 상태를 가져오고 다시 A를 실행 입출력 요청, 점유시간이 끝남, 인터럽트가 있을 때 등.. 프로세스 생성과 종료.exe 실행프로그램의 code영역과 data영역을 메모리에 로드빈 스택과 빈 힙을 만듦PCB 생성 후 값 초기화 일련의 과정은 부팅되고 0번 프로세스(부모) 실행할 때 딱 한번 실행이후엔 0번 프로세스를 복사(fork)해서 사용 (자식) 복사할 때 모든 프로세스 내용(code, data, heap, stack)과 PCB내용을 전부 복사해 옴 이 후 exec함수를 실행시키면 본인이 원하는 값으로 덮어쓰게 됨 쓰레드프로세스가 많아질수록 차지하는 메모리가 많이 차지하기 때문에 필요 -> 한개의 프로세스 내에 n개의 쓰레드가 있음Code, data, heap을 공유하며, stack은 쓰레드마다 하나씩 가지고 있음 쓰레드 id와 Thread Control Block (TCB) 생김 -> 운영체제가 작업을 처리하는 단위는 프로세스가 아닌 쓰레드임 CPU 스케줄링어떤 프로세스얼마의 시간동안CPU Burst: CPU할당받아 실행I/O Burst: 입출력 작업 다중큐준비, 대기상태는 큐로 존재실행->준비: 우선순위를 보고 그에 맞는 준비 큐에 PCB를 넣음 스케줄링 목표리소스 사용률 오버헤드 최소화공평성 처리량 대기시간응답시간 스케줄링 알고리즘FIFO 스케줄링 큐에 들어온 순서대로 할당 앞선 프로세스가 완전히 끝나야만 다음 프로세스가 실행할 수 있음 평균대기시간이 순서에 따라 차이가 심하게 남 -> 성능 차이 -> 일괄처리시스템에 보통 사용 미션운영체제인터럽트 방식으로 해결2. 프로그램: .exe형식의 애플리케이션 프로세스: 실행 중인 프로그램3. 멀티프로그래밍: 여러 프로그램을 실행 멀티프로세싱: (CPU관점) cpu가 여러 프로세스를 처리4. PCB를 사용하여 멀티 프로세싱을 가능하게 관리함5. 어떤 프로세스 실행 중에 다른 프로세스를 실행하기 위해 원래 프로세스 정보를 저장해두고 다른 프로세스를 처리하는 것자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?이유를 함께 적어주세요.프로그램의 목표: 저장 및 열람을 해야 함교실의 학생 정보: 자주 바뀌지 않음열람: 조회는 자주 함삽입 삭제는 자주 일어나지 않지만 조회는 많이 한다면 배열을 선택하는 것이 좋음 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.들어온 순서대로라면 fifo 즉 큐 자료구조가 필요하다

인프런 워밍업 클럽 2기 - CS 미션 1

운영체제while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? 인터럽트를 사용합니다. 인터럽터 방식은 작업이 완료됬을 때 신호를 받아 CPU가 인터럽트 서비스 루틴을 실행시켜 작업을 완료합니다. 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 디스크 등에 저장된 명령문의 집합입니다. (수동적 존재)프로세스는 프로그램이 메모리에 올라가 있는 상태입니다. (실행중인 프로그램) 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 '메모리 관점' 에서 메모리에 여러가지 프로세스가 올라온 것을 의미합니다.멀티프로세싱은 메모리에 올라와있는 여러 프로레스를 시분할처리로 CPU가 짧은 시간 교대로 실행하는 것을 의미합니다. 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?PCB 데이터 구조를 사용합니다. 각 프로세스의 상태, 프로그램 카운터, CPU 레지스터, 메모리 관리 정보 등이 포함되어 있습니다. 5. 컨텍스트 스위칭이란 뭔가요?운영체제는 CPU를 효율적으로 사용할 수 있도록 여러 프로세스를 번갈아가며 CPU를 할당합니다. 이떄 각 프로세스의 작업 진행 사항을 유지할 수 있도록 실행중인 PCB 를 저장하고, 실행될 기존의 PCB 내용을 CPU에 세팅하는 것을 의미합니다. 자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.헤시테이블을 선택하겠습니다. 학생에게는 구분을 위한 고유정보(학생번호) 등이 존재할 것입니다. 저장하고 열람한다는 조건을 따졌을 때, 해시테이블은 조회, 삽입 , 삭제 모두 O(1) 의 시간복잡도를 가져 , 빠르게 저장하고 열람할 수 있을 것입니다. 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐를 선택하겠습니다. 주문의 조건인 순서대로 처리하는 FIFO 방식인 큐가 적합한 자료구조라고 생각됩니다. 이 경우 주문의 삭제, 삽입은 모두 O(1)의 시간 복잡도를 가지게 됩니다. 물론 덱을 사용해도 성능상 차이는 없겠지만, 이 코드를 공유하게 될 동료들에게 '순서대로 처리한다' 라는 결론을 큐를 통해 직관적으로 전달할 수 있기 때문입니다.

워밍업클럽cs

인프런 워밍업 클럽 스터디 2기 CS | 1주차 발자국

"인프런 워밍업 클럽 스터디 2기 CS" 과정을 듣게 되었다.프로그래밍 언어 공부하기만 바빴지 CS에 대해서는 아는 것이 없었기에, 강의 수집가라 수집만 하고 완강을 한 적이 별로 없었기에, 항상 장바구니에 넣어두고 언젠가 사야지 고민하던 "감자"님 강의기에2일 정도 고민 후 바로 강의 구매 및 스터디 신청을 하게 되었다.그림으로 쉽게 배우는 운영체제섹션1) 운영체제 들어가기운영체제 개요컴퓨터는 운영체제가 없어도 동작할 수 있다. 하지만 다른 기능을 추가할 수 없다.운영체제 없는 컴퓨터 === 통화만 가능했던 옛날 유선 전화기요즘 컴퓨터 === 요즘 스마트폰 운영체제가 하는 일1. 프로세스 관리노래, 게임, 인터넷 서핑 전부 동시 실행 가능현재 실행 중인 것 외에는 백그라운드에서 실행됨만약 운영체제가 관리하지 않으면 CPU가 독차지 되어 동시에 실행 불가2. 메모리 관리모든 프로그램은 메모리에 올라와서 동작 3. 하드웨어 관리운영체제는 사용자의 하드웨어에 대한 직접적인 접근을 막음사용자가 데이터를 저장하려고 할 때 하드디스크의 특정 영역에 바로 저장 못 함운영체제가 판단해서 적절한 위치에 저장 하드디스크 특정 영역에 중요한 데이터가 존재할 수 있기 때문사용자의 악의적인 공격 방어 4. 파일 시스템 관리 운영체제의 역사비싼 CPU의 사용률을 늘릴려고 고민오퍼레이터와 프로그래머 사이에서 낭비되는 시간을 줄이려고 함 => 오늘날의 운영체제 탄생 운영체제의 구조이미지 참조 ) https://ko.wikipedia.org/wiki/%EC%BB%A4%EB%84%90_%28%EC%BB%B4%ED%93%A8%ED%8C%85%29운영체제의 핵심은 커널(kernel)컴퓨터 운영체제의 핵심이 되는 컴퓨터 프로그램, 시스템의 모든 것을 완전히 제어. 프로세스와 메모리, 저장장치를 관리하는 핵심적인 기능을 담당사용자는 운영체제의 커널에 직접 접근X, 인터페이스를 통해서 접근할 수 있음.인터페이스GUI(Graphic User Interface)e.g. windows, Mac OSCLI(Command-Line Interface)e.g. 유닉스, 리눅스시스템 콜(system call)시스템 호출 또는 시스템 콜, 간단히 시스콜은 운영체제의 커널이 제공하는 서비스에 대해 응용 프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스어플리케이션은 시스템 콜을 통해서 커널에 접근 가능드라이버하드웨어와 커널의 인터페이스e.g. 키보드, 마우스 등컴퓨터 하드웨어와 구조오늘날 대부분의 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조CPU와 메모리(RAM)를 두고 이들 사이는 버스로 연결버스: 데이터를 전달하는 통로프로그램은 메모리에 올려서 실행시키는데 프로그램을 메모리에 내장했다고 해서 프로그램 내장방식이라고 함메모리에 올라간 프로그램은 명령에 따라 처리컴퓨터 하드웨어가장 기본이 되는 것은 메인보드메인보드: 다른 하드웨어를 연결하는 장치장치 간에 데이터를 전송하는 건 메인보드의 버스가 담당CPU(Central Processing Unit) 구조중앙처리장치, 컴퓨터 시스템을 통제하고 프로그램의 연산을 실행, 처리하는 가장 핵심적인 컴퓨터의 제어 장치, 혹은 그 기능을 내장한 칩. 컴퓨터에서 기억, 해석, 연산, 제어라는 4대 주요 기능을 관할하는 장치산술논리 연산장치CPU에서 실제로 데이터 연산을 담당하는 것제어장치모든 장치들의 동작을 지시하고 제어하는 장치레지스터CPU 내에서 계산을 위해 임시로 보관하는 장치. 변수라고 생각해라메모리 종류RAM(Random Access Memory)램덤으로 데이터를 읽어도 저장된 위치와 상관없이 읽는 속도가 같음전력이 끊기면 데이터를 잃어버림메인 메모리로 사용ROM(Read Only Memory)전력이 끊겨도 데이터를 계속 보관할 수 있음데이터를 한 번 쓰면 수정 불가능컴퓨터 부팅과 관련된 바이오스를 저장하는 데에 주로 쓰임컴퓨터의 부팅과정컴퓨터 부팅 -> ROM에 저장된 바이오스 실행 -> 바이오스는 전원, CPU, 메모리, 키보드, 마우스, 하드디스크 등 주요 하드웨어에 이상유무 확인 -> 이상 없으면 부트로더 실행, 있으면 부팅 불가 -> 부팅 후 실행되는 모든 응용 프로그램은 메모리에 올라와서 운영체제가 관리인터럽트(Interrupt)프로세스 실행 중 예기치 않은 상황이 발행할 때 발생한 상황을 처리한 후 실행 중인 작업으로 복귀하는 것. CPU가 특정 기능을 수행하는 도중에 급하게 다른 일을 처리하고자 할 때 사용할 수 있는 기능 CPU가 입출력 장치에 데이터를 읽거나 쓰려고 하는 상황CPU는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령을 내림CPU 관점에선 입출력 명령이 언제 완료될 지 알 수 없음CPU는 주기적으로 계속 확인함 => 폴링(Polling)방식폴링 방식은 주기적으로 CPU가 확인해야 해서 성능이 안좋음폴링 방식의 단점을 해결한게 인터럽트 방식CPU가 입출력 관리자에게 입출력 명령을 내리고CPU는 다른 작업을 함입출력 관리자는 입출력이 완료되었을 때 CPU에게 신호를 주고 CPU는 그 신호를 받아 인터럽트 서비스 루틴(ISR)을 실행시켜 작업을 완료인터럽트 서비스 루틴(ISR): 특정 인터럽트가 들어오면 그 인터럽트를 처리하는 함수인터럽트는 비동기적으로 동작 => 성능에 이점인터럽트 2가지 방식하드웨어 인터럽트위의 입출력 등과 같은 인터럽트소프트웨어 인터럽트사용자 프로그램에서 발생한 인터럽트e.g. 유효하지 않은 메모리에 접근, 0으로 나누는 명령어 등 섹션2) 프로세스와 쓰레드프로그램과 프로세스프로그램(애플리케이션, 앱)하드디스크 등과 같은 저장장치(HDD, SSD)에 저장된 명령문의 집합체Windows 운영체제에서는 .exe 파일의 모습컴퓨터 관점에서 프로그램은 저장 장치만 사용하는 수동적인 존재프로세스하드디스크에 저장된 프로그램이 메모리에 올라갔을 때 실행 중인 프로그램컴퓨터 관점에서 프로세스는 메모리도 사용하고 운영체제의 CPU스케줄링 알고리즘에 따라서 CPU도 사용,필요에 따라 입력과 출력을 하기 때문에 능동적인 존재멀티프로그래밍과 멀티프로세싱유니프로그래밍메모리에 오직 하나의 프로세스가 올라온 것을 말함멀티프로그래밍메모리에 여러 개의 프로세스가 올라온 것을 말함멀티프로세싱CPU가 여러 개의 프로세스를 처리하는 것을 말함PCB(Process Control Block) 프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB를 만들고 저장PCB들은 연결리스트 자료구조로 저장 컨텍스트 스위칭프로세스 실행 중에 다른 프로세스로 변경하기 위해 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업 컨텍스트 스위칭이 발생할 때 PCB에서 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경컨텍스트 스위칭이 발생하는 이유는 CPU점유 시간을 초과했거나, I/O요청이 있거나 다른 종류의 인터럽트가 있을 때 발생프로세스 생성과 종료일반적인 프로세스 생성.exe파일 실행 -> 운영체제 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드 -> 빈 스택과 빈 힙을 만들어 공간 확보 -> 이 프로세스를 관리하기 위한 PCB를 만들어 값을 초기화운영체제가 부팅되고 0번 프로세스가 생성될 때 딱 한번만 실행 됨다음의 모든 프로세스는 새로 생성되지않고 0번 프로세스를 fork() 함수로 복사해 생성됨새로 생성하는 것보다 복사가 더 빠르기 때문복사된 프로세스는 자식 프로세스자식 프로세스 입장에서 0번 프로세스는 부모 프로세스fork()함수로 프로세스 복사 후 exec()함수를 실행하면 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓰게 됨exit()함수는 자식 프로세스가 부모 프로세스에게 정상 종료됨을 알리는 함수부모 프로세스는 자식 프로세스의 exit status를 읽고 자식 프로세스를 정리부모 프로세스가 자식 프로세스보다 먼저 종료되거나, 자식 프로세스가 비정상적으로 종료돼 exit()신호를 주지 못해 exit status를 읽지 못해 메모리에 계속 살아 있는 상태는 "좀비 프로세스"라고 부름쓰레드운영체제가 작업을 처리하는 단위는 프로세스기존 프로세스를 복사해서 사용하니 메모리를 많이 먹어 쓰레드가 등장쓰레드는 프로세스 내에 존재하는 것으로 1개의 프로세스에 여러개의 쓰레드가 존재 가능한 프로세스 내 쓰레드들은 그 프로세스의 PCB, 코드, 데이터, 힙 영역을 공유 => 메모리 절약스택은 공유하지 않고 쓰레드마다 하나씩 가지고 있음쓰레드와 프로세스의 장단점안정성프로세스 > 쓰레드프로세스는 서로 독립적이기 때문에 하나의 프로세스가 문제가 있어도 다른 프로세스 영향을 받지 않음. 안정성쓰레는 하나의 프로세스 내에 있기 때문에 프로세스가 문제가 생기면 안의 모든 쓰레드에 문제가 생김속도, 자원프로세스 < 쓰레드프로세스는 서로 고유한 자원을 가지고 있음. 프로세스간의 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느림쓰레드는 스택을 제외한 영역을 모두 공유하고 있기 때문에 오버헤드가 작음CPU스케줄링운영체제는 모든 프로세스에게 CPU를 할당/해제하는데 이를 CPU스케줄링이라고 함CPU스케줄링에서 스케줄러(운영체제)가 고려해야할 사항어떤 프로세스에게 CPU리소스를 줘야하는가?CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?CPU BurstCPU를 할당받아 실행하는 작업I/O Burst 다중큐프로세스 정보를 가지고 있는 PCB는 준비 상태의 다중큐에 들어가서 실행되기를 기다리고 있고 CPU스케줄러에 의해 실행상태로 전환이때 CPU스케줄러는 준비 상태의 다중큐를 참조해서 어떤 프로세스를 실행시킬지 결정I/O 작업 또한 실행 중인 프로세스에서 I/O 작업이 발생하면 해당 I/O 작업의 종류별로 나뉜 큐에 들어가고 CPU스케줄러는 이를 참조해서 스케줄링스케줄링 목표리소스 사용률CPU 사용률을 높이는 것을 목표로 함I/O 디바이스의 사용률을 높이는 것을 목표호 함오버헤드 최소화스케줄링을 하기 위한 계산이 너무 복잡하거나 컨텍스트 스위칭을 너무 자주 X공평성모든 프로세스에게 공평하게 CPU할당처리량같은 시간 내에 더 많은 처리를 할 수 있는 방법을 목표로 함대기 시간대기 시간이 짧은 것을 목표로 함응답 시간응답 시간이 짧은 것을 목표로 함사용자가 사용하는 시스템에 따라 목표를 다르게 설정해야 함터치스크린: 응답 시간이 짧게과학 계산: 처리량이 높게일반 사용자: 밸런스 유지FIFO(First In First Out)단순하고 직관적이나 한 프로세스가 완전히 끝나야 다음 프로세스가 시작된다는 단점이 있음I/O작업이 있다면 CPU는 끝날 때까지 쉬고 있기 때문에 CPU 사용률이 떨어짐스케줄링의 성능은 "평균 대기시간"으로 평가FIFO알고리즘은 프로세스의 Burst Time에 따라 성능 차이가 심하게 나기 때문에 현대 운영체제에서는 잘 쓰이지 않고 일괄처리 시스템에 쓰임그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 섹션1) 개요자료구조와 알고리즘이란?자료구조데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄변수, 배열알고리즘어떤 문제를 해결하기 위한 확실한 방법데이터가 어떤 자료구조를 하고 있는 지에 따라서 값을 구하는 방식이 달라짐 => 자료구조에 따라 알고리즘이 달라짐시간복잡도특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측 => 반복문최악의 경우를 평가하는 Big-O를 많이 사용성능을 정확하게 표현하진 못함 => 단순히 해당 알고리즘의 입력이 늘어날 때 계산량이 얼마나 늘어나는지 표현하는 방법일 뿐 O(n): 선형시간 알고리즘, 데이터가 많아지면 그와 비례해서 계산량이 많아짐O(1): 상수시간 알고리즘, 입력의 크기에 상관없이 상수의 시간이 소요O(logn), O(nlogn), O(n^2), O(2^n), O(n!) 등배열자바스크립트에서 배열은 불연속적으로 할당, 내부적으로 연결해서 사용자에게 배열인 것처럼 보이게 함연결리스트(Linked List)빈 메모리 공간 아무곳에 데이터를 생성하고 연결만 해주면 되기 때문에 배열 초기 크기를 몰라도 됨삽입, 삭제가 쉽다는 장점데이터들이 전부 떨어져있기 때문에 바로 접근할 수 없다는 단점데이터참조 O(n)의 성능스택(Stack)Fist In Last Out(FILO)먼저 들어간 데이터가 나중에 나오는 규칙head에만 삽입, 제거하는 자료구조큐(Queue)First In First Out(FIFO)먼저 들어간 데이터가 먼저 나오는 규칙운영체제에서 쓰는 FIFO 스케줄링: 먼저 들어온 프로세스 순으로 CPU가 처리head에서 삽입하고 tail에서 제거하는 자료구조덱(Deque)데이터의 삽입과 제거를 head와 tail 두 곳에서 자유롭게 할 수 있는 자료구조스택, 큐 전부 구현 가능해시테이블(Hash Table)해시와 테이블이 합쳐진 자료구조프로그래밍 언어에 따라서 조금씩 다른 이름을 가지고 있음해시, 맵, 해시맵, 딕셔너리장점Key만 알면 Value에 O(1)의 성능으로 읽기 가능삽입, 수정, 삭제 다 O(1)단점메모리를 많이 차지함좋은 해시 함수 구현이 필수해시충돌충돌을 해결하기 위해서 해당 인덱스를 연결리스트로 구성해 데이터들을 연결 => O(n)셋(Set)데이터의 중복을 허용하지 않는 자료구조해시 테이블을 사용한다고 해서 해시 셋(Hash Set)이라고도 불림회고운영체제를 처음 공부해서 그런지 낯선 단어들이 굉장히 많았다. 그래서인지 생각했던 시간보다 많이 소요되었다.알고리즘 개념은 어느정도 알고 있었지만 구현을 하려니 어려웠고 이것 또한 생각했던 것보다 시간이 많이 소요되었다...반복하다보면 익숙해지겠지 🙂 그리고 강의 들으면서 길게 작성하는 방법보단 강의의 핵심만 작성하도록 해야겠다.

웹 개발

[인프런 워밍업클럽 CS 2기] 1주차 미션

while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?- 인터럽터를 사용합니다.- 인터럽터는 비동기로 동작하고 기다리지 않고 다른작업을 합니다.- 비동기 작업을 사용하면 성능상의 이점이 있습니다. 프로그램과 프로세스가 어떻게 다른가요?- 프로그램 - 프로그램은 롤과, 지니뮤직, vscode, 크롬과 같은 HDD나SSD에 저장 되어 있는 수동적인 존재- 프로세스 - 프로세스는 프로그램이 실행되어 HDD에서 RAM(메모리)로 할당되면서 실행중인 프로그램입니다. - 프로세스는 필요에 따라 I/O(입출력) 작업이 이루어진다. - 운영체제의 CPU스케줄링 알고리즘에 따라서 CPU를 사용. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍은 메모리 관점 에서 여러개의 프로세스가 올라오는것이다.멀티 프로세싱은 CPU 관점 에서 CPU가 여러개의 프로세스를 처리 하는것. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?프로세스의 정보를 가지고 있는 PCB를 만들고, 저장합니다. PCB는 포인터, 프로세스 상태, 레지스터 정보, 메모리 관련 정보, CPU 스케쥴링 정보 등으로 구성되어 있습니다.운영체제는 프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거합니다.컨텍스트 스위칭이란 뭔가요?컨텍스트 스위칭이란 프로세스를 실행하는 도중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업 입니다.CPU에서 시분할 처리는 컨텍스트 스위칭이 매우 빠르게 일어나기 때문에, 여러 프로세스가 동시에 실행되는 것처럼 보이는 현상입니다. 해당 컨텍스트 스위칭을 하는 이유는 CPU 점유시간이 다되었거나, I/O 입출력 작업 요청이 있거나, 다른종류의 인터럽트가 있을때 발생합니다.컨텍스트 스위칭이 발생할때 프로세스가 하던일을 멈추고 CPU 건네주고 다시 자기 차례가 왔을때 이전에 하던 작업을 그대로 하기 위해서 컨텍스트 스위칭이 발생할때는 CPU레지스터 값과 프로그램 카운터(PC)등을 저장 해야 합니다.근데 이때 컨텍스트 스위칭이 CPU 점유시간이 다되었을때 발생하는데 CPU 점유 시간을 결정하는 것이 CPU 스케줄링 알고리즘 입니다. 자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.셋(Set) 자료형을 사용 할것 같습니다.- 셋 자료형을 중복을 허용하지 않기 때문입니다. 왜냐하면 학생 같은경우에는 각 학반, 학생번호, 이름이 있는데 이는 중복되지 않아야 하기 때문에 무결성을 보장 해야 합니다.- 셋 자료형은 해시테이블 기반으로 빠른 데이터 읽기, 삽입, 삭제가 가능하기 때문 입니다.- 셋도 해시테이블을 사용하기 때문에 해시 테이블의 단점인 메모리를 많이 차지한다는 점이 있는데 이는 학생이 중복 데이터가 발생하지 않기 때문에 1억건 이런식으로 발생하지 않기 때문에 메모리문제가 발생하지 않을것으로 예상 됩니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.> Queue 자료구조를 사용할것 같습니다. 이유는 위의 문제처럼 주문은 들어온 순서대로 처리 되어야 하기 떄문에 FIFO 먼저 들어온것이 먼저 나가는 구조를 가진 Queue 자료구조가 적합 합니다.>비슷한 자료구조인 Stack을 만약 사용해서 구현 했다고 가정하면 주문을 제일 먼저 한 사람이 제일 마지막에 처리 되면서 엄청난 컴플레인을 받을것 같습니다. 왜냐하면 마트에서 계산 할려고 줄을 섯는데 제일 마지막에 줄을 선사람부터 계산을 하게 된다고 가정을 하면 굉장히 불공평 하기 때문입니다. 미션 회고분명히 공부하고 정리 할때 까지만해도 이해한것 같았고 넘어갔는데 미션을 제 스스로의 힘으로 풀려고 하니까 벅찼다. 뭐랄까 아 이거 뭐였지? 저거 뭐였지? 공부를 했는데 기억이 안나는것은 정말 허무하다. 그래도 다시 보고 미션으로 정리를 한번 더 했으니 기억에 더 오래 남기를 빌어본다.다음 미션에서는 스스로 직접 60%이상 풀 수 있는걸 목표로 하자!

알고리즘 · 자료구조･알고리즘･자료구조･운영체제

[인프런 워밍업클럽 CS 2기] 1주차 발자국

이번주 공부 학습 내용운영체제폴링 방식: CPU가 입출력 관리자에게 명령을 내리고 주기적으로 상태를 확인하는 방식.인터럽트: 폴링 단점을 해결. 입출력 완료 시 CPU에 알림을 주고 작업을 계속 진행.하드웨어 인터럽트: 입출력 장치 (키보드, 마우스 등).소프트웨어 인터럽트: 프로그램 오류 시 발생 (예: 0으로 나누기).프로그램과 프로세스:프로그램: 저장된 명령문의 집합.프로세스: 실행 중인 프로그램.멀티 프로그래밍: 메모리에 여러 프로세스를 올림.멀티 프로세싱: CPU가 여러 프로세스를 처리.PCB: 프로세스 정보를 저장. 생성, 준비, 실행, 대기, 완료 상태로 관리.프로세스 상태:준비: CPU를 기다리는 상태.실행: CPU를 할당받은 상태.대기: 입출력 요청 중인 상태.완료: 프로세스 종료 상태.컨텍스트 스위칭: 프로세스 간 전환 시 상태 저장 및 복구.CPU 스케줄링 목표: 자원 사용률 극대화, 공평성, 처리량 최적화, 대기시간 감소.자료구조와 알고리즘자료구조: 데이터 구조와 사용 방식을 정의.알고리즘: 문제 해결을 위한 확실한 방법.배열: 읽기와 쓰기가 빠름 (O(1)).연결 리스트: 중간 삽입, 삭제가 쉬움.스택: FILO, 작업 되돌리기와 같은 기능.큐: FIFO, 운영체제 스케줄링 등에 사용.덱: 양쪽에서 삽입/제거 가능한 자료구조.해시 테이블: 키-값 쌍 저장. 빠른 접근 (O(1)).셋: 중복 허용하지 않음, 해시테이블 사용.일주일 간의 학습 내용 대한 간단한 회고일요일까지 목표 강의까지 완주 했다는것에 첫 번째로 만족하고, 바쁘다는 핑계나 귀찮다는 핑계로 평일 저녁이나 쉬는날에라도 학습을 하지않아서 주말에 몰아서 봤던거에 대한 반성을 하게 됩니다 ㅠㅠ다음주부터는 미루지 않고 하루에 제공되는 챕터를 꾸준히 공부하는 방식으로 바꾸도록 노력 할겁니다!

알고리즘 · 자료구조･알고리즘･자료구조･운영체제

[그림으로 쉽게 배우는 운영체제] 운영체제 프로세스 쓰레드 CPU 스케줄링(1)

* 해당 포스팅은 그림으로 쉽게 배우는 운영체제 - by 감자 멘토님 강의를 수강후 작성하는 글 입니다. KEYWORD- 운영체제: 하드웨어 자원을 관리하고 사용자와 시스템 간 인터페이스를 제공하는 소프트웨어.- 프로세스: 실행 중인 프로그램으로, CPU에서 작업이 진행되는 단위.- 프로그램: 실행 가능하지만 실행되지 않은 상태의 명령어 집합.- 쓰레드: 프로세스 내에서 실행되는 작은 작업 단위.- CPU: 명령어를 해석하고 연산을 수행하는 컴퓨터의 중앙 처리 장치.- 메모리: 데이터를 저장하고 프로세스가 작업을 수행할 때 사용되는 공간.- 애니악: 최초의 범용 전자 디지털 컴퓨터.- 펀치카드: 데이터를 입력하기 위해 구멍을 뚫어 정보를 표현하던 초기 입력 장치.- I/O 디바이스 컨트롤러: 입출력 장치와 시스템 간의 통신을 제어하는 장치.- 싱글스트림 배치시스템: 작업을 순차적으로 처리하는 초기 컴퓨터 운영 방식.- 시분할 시스템: 여러 사용자가 시스템을 동시에 사용할 수 있도록 자원을 할당하는 시스템.- 파일시스템: 데이터를 파일 형태로 저장하고 관리하는 시스템.- 유닉스: 멀티태스킹, 멀티유저 환경을 지원하는 운영체제.- 유니프로그래밍: 한 번에 하나의 프로그램만 실행하는 방식.- 멀티프로그래밍: 메모리에 여러 프로그램을 동시에 올려서 CPU가 번갈아 가며 처리하는 방식.- 멀티프로세싱: 여러 CPU가 동시에 여러 프로세스를 처리하는 방식.- 시분할처리: CPU 시간을 여러 작업에 나누어 사용하는 처리 방식.- 스와핑: 메모리에서 프로세스를 내보내고 다시 불러오는 과정.- 베이스 레지스터: 프로세스의 메모리 시작 주소를 저장하는 레지스터.- 커널: 운영체제의 핵심 부분으로 하드웨어와 소프트웨어 자원을 관리함.- 인터페이스: 시스템과 사용자 또는 다른 시스템 간의 상호작용을 위한 접점.- GUI: 그래픽을 통해 사용자와 컴퓨터가 상호작용하는 방식.- CLI: 명령어를 통해 사용자와 컴퓨터가 상호작용하는 방식.- 시스템 콜: 응용 프로그램이 운영체제의 기능을 요청할 때 사용하는 함수.- 드라이버: 하드웨어와 운영체제가 통신할 수 있도록 돕는 소프트웨어.- 그래픽카드: 그래픽 처리와 관련된 연산을 담당하는 하드웨어.- 폰노이만 구조: 프로그램과 데이터를 메모리에 저장하고 처리하는 컴퓨터 구조.- 메인보드: CPU, 메모리, I/O 장치가 연결된 컴퓨터의 중심 회로 기판.- 제어장치: CPU 내부에서 명령어의 실행을 제어하는 장치.- 산술논리 연산장치: CPU 내부에서 산술 및 논리 연산을 수행하는 장치.- 레지스터: CPU 내에서 데이터와 명령어를 일시적으로 저장하는 고속 메모리.- 프로그램 카운터: 다음에 실행할 명령어의 주소를 저장하는 레지스터.- 메모리 주소 레지스터: 메모리 내 데이터의 주소를 저장하는 레지스터.- 메모리 버퍼 레지스터: 메모리에서 읽거나 쓸 데이터를 임시 저장하는 레지스터.- 명령어 레지스터: 현재 실행 중인 명령어를 저장하는 레지스터.- RAM: 휘발성 메모리로, 데이터를 일시적으로 저장함.- ROM: 비휘발성 메모리로, 데이터를 영구적으로 저장함.- 바이오스: 컴퓨터 부팅 시 하드웨어 초기화와 운영체제 로딩을 관리하는 펌웨어.- 폴링방식: CPU가 장치의 상태를 주기적으로 확인하는 방식.- 인터럽트: 외부 신호로 CPU의 작업을 중단하고 다른 작업을 처리하게 하는 신호.- 인터럽트 서비스 루틴: 인터럽트 발생 시 실행되는 코드.- Code 영역: 프로그램의 명령어가 저장되는 메모리 영역.- Data 영역: 초기화된 전역 변수와 정적 변수가 저장되는 메모리 영역.- Heap 영역: 동적으로 할당된 메모리 공간.- Stack 영역: 함수 호출 시 생성되는 지역 변수와 함수 정보가 저장되는 메모리 영역.- 컴파일: 고급 프로그래밍 언어를 기계어로 번역하는 과정.- 어셈블리어: 기계어와 1:1 대응하는 저급 프로그래밍 언어.- 기계어: CPU가 직접 실행할 수 있는 이진 코드.- 링커: 여러 목적 파일을 결합해 실행 가능한 프로그램으로 만드는 도구.- 연결리스트: 노드가 서로 연결된 데이터 구조로, 각 노드는 데이터와 다음 노드의 참조를 포함함.- PCB: 프로세스 제어 블록으로, 프로세스에 대한 정보를 저장하는 데이터 구조.- 포인터: 메모리 주소를 가리키는 변수.- 컨텍스트 스위칭: CPU가 한 프로세스에서 다른 프로세스로 전환할 때 발생하는 작업.- 프로그램 카운터: 현재 실행 중인 명령어의 다음 명령어 주소를 가리키는 레지스터.- 부모프로세스: 다른 프로세스를 생성하는 프로세스.- 자식프로세스: 부모 프로세스에 의해 생성된 프로세스.- fork 함수: 새로운 프로세스를 생성하는 시스템 호출.- exit 함수: 프로세스가 실행을 종료할 때 호출하는 함수.- 좀비 프로세스: 실행이 종료되었으나 부모 프로세스가 회수하지 않은 프로세스.- IPC: 프로세스 간 통신으로, 프로세스 간 데이터를 주고받는 방법.- TCB: 쓰레드 제어 블록으로, 쓰레드의 실행 상태를 저장하는 데이터 구조.- 프로세스와 쓰레드 차이: 프로세스는 독립된 메모리 공간을 갖고, 쓰레드는 프로세스 내 자원을 공유함.- CPU Burst: 프로세스가 CPU를 사용하는 시간.- I/O Burst: 프로세스가 I/O 작업을 수행하는 시간.- 큐 자료구조(Queue): FIFO 방식으로 데이터를 저장하고 처리하는 자료구조.- CPU 스케줄링: 여러 프로세스 간에 CPU 시간을 배분하는 방식.- 생성상태: 프로세스가 생성된 초기 상태.- 준비상태: 프로세스가 실행 준비가 된 상태.- 대기상태: 프로세스가 입출력 작업을 기다리는 상태.- 실행상태: 프로세스가 CPU에서 실행 중인 상태.- 완료상태: 프로세스가 실행을 완료한 상태.- 스케줄러: CPU 자원을 프로세스에 할당하는 운영체제의 구성 요소.- 오버헤드: 시스템 자원 사용 시 발생하는 추가 비용.- 스케줄링 알고리즘: CPU 시간을 프로세스에 할당하는 방법을 결정하는 알고리즘.- FIFO (First In, First Out): 먼저 들어온 데이터가 먼저 나가는 방식으로, 큐 자료구조에서 사용하는 원칙.

시스템 · 운영체제･운영체제･프로세스･쓰레드･CPU